Description
La distance d'une fonction booléenne f de m variables au code de Reed-Muller est une mesure la non-linearité de f. Il s'agit d'une notion importante en cryptographie. L'analyse de Fourier est une méthode d'approche normale de cette question. En particulier, la non-linéarité de f est égale à [ 2^m - R(f) ] /2, où R(f) est l'amplitude spectrale de f i.e. le module maximal de ses coefficients de Fourier.<br/> Un des problèmes majeurs consiste à déterminer la valeur minimale (rayon spectral) de R(f) lorsque f décrit l'ensemble de toutes les fonctions booléennes, équivalent à déterminer le rayon de recouvrement du code de Reed-Muller du premier ordre.<br/> Le rayon spectral est facile à calculer lorsque m est pair, il est réalisé par les fonctions quadratiques non-dégénérée. Le cas impair est encore ouvert, sauf pour les petites valeurs de m : 3, 5 et 7. Dans les années 80, Paterson-Wiedemann ont découvert une fonction booléenne de 15 variables moins linéaire que les fonctions quadratiques : contre-exemple à une conjecture formulée dans les années 70 par Mykkelveit.<br/> Au cours de mon exposé, je montrerai d'autres contre-exemples plus linéaire mais mieux structurés construits à partir des sommes de Gauss. Enfin, je discuterai de la conjecture de Patterson et Wiedemann qui affirme l'équivalence asympototique entre le rayon spectral R(m) et 2^{m/2}.<br/> Philippe Langevin, janvier 2003.
Prochains exposés
-
Random lattices that are modules over the ring of integers
Orateur : Nihar Gargava - Institut de Mathématiques d'Orsay
We investigate the average number of lattice points within a ball where the lattice is chosen at random from the set of unit determinant ideal or modules lattices of some cyclotomic number field. The goal is to consider the space of such lattice as a probabilistic space and then study the distribution of lattice point counts. This is inspired by the connections of this problem to lattice-based[…]-
Cryptography
-
-
Schéma de signature à clé publique : Frobénius-UOV
Orateur : Gilles Macario-Rat - Orange
L'exposé présente un schéma de signature à clé publique post-quantique inspiré du schéma UOV et introduisant un nouvel outil : les formes de Frobénius. L'accent est mis sur le rôle et les propriétés des formes de Frobénius dans ce nouveau schéma : la simplicité de description, la facilité de mise en oeuvre et le gain inédit sur les tailles de signature et de clé qui bat RSA-2048 au niveau de[…] -
Yoyo tricks with a BEANIE
Orateur : Xavier Bonnetain - Inria
TBD-
Cryptography
-
Symmetrical primitive
-