Description
A toute fonction booléenne f à n variables on peut associer canoniquement un graphe : son diagramme de décision binaire quasi réduit (qROBDD). Cette technique est utilisée depuis longtemps dans la vérification des circuits. A ce graphe on associe son profil qui est un n+1-uple d'entiers p(f) = (p0,p1,...,pn) (pi est le nombre de sommet à distance i de l'origine du graphe) et une complexité c(f) = p0 + ... + pn (la taille du graphe).v La caractérisation des profils parmi tous les n-uples et leur énumération est possible. On montre qu'on peut aussi énumérer les fonctions booléennes de profil donné. On fait ainsi apparaître plusieurs suites de nombres remarquables (et peut-être nouvelles) qui s'interprètent très simplement par une technique d'analyse p-adique : le développement de Mahler.<br/> Les fonctions de complexité maximum sont aussi descriptibles complètement : nous les appelons les multiplexeurs twistés. Elles apparaissent en cryptographie dans toutes les lignes des boîtes S du DES.<br/> Ces résultats suggèrent une possible interprétation intéressante des fonctions booléennes et des qR0BDD par l'immeuble de Bruhat-Tits pour SL2(Z2) et un parallèle plus classique avec le relèvement très actuel des questions de géométrie en caractéristique p vers la caractéristique 0 via les p-adiques. En ce quiconcerne précisément la cryptographie, deux directions de recherche sur ces techniques sont suggérées : les fonctions de non-linéarité maximale ou Bent, les calculs de bases de Gröbner booléennes.
Prochains exposés
-
Adelic reduction of module lattices
Orateur : Henry Bambury - DGA-MI et Inria Rennes
We give a strict generalisation of the LLL algorithm over number fields, based on the reduction theory of $GL(n)$ over the adele ring of a number field. Our algorithm is free of heuristics, with rigorous bounds on output quality and complexity. -- based on joint work with Seungki Kim, Changmin Lee and Phong Nguyen ---
Cryptography
-
-
European Cyber Week: atelier cryptographie post-quantique
Dans la continuité des éditions 2021, 2022 et 2024, la DGA — en partenariat avec CREACH LABS et avec le soutien de l'ANSSI, de l'IRISA, de l'IRMAR et du Pôle d'Excellence Cyber — organise la 4e édition de l'atelier consacré à la cryptographie post-quantique dans le cadre de l'European Cyber Week 2026. Attention, il faut s'inscrire (gratuitement) au préalable — s'inscrire à la conférence Les[…] -
Post-quantum day of the cryptography seminar
A scientific day devoted to post-quantum cryptography, held in the wake of the European Cyber Week, with talks more technical than those presented at the ECW.