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.
Next sessions
-
SoK: Security of the Ascon Modes
Speaker : Charlotte Lefevre - Radboud University
The Ascon authenticated encryption scheme and hash function of Dobraunig et al (Journal of Cryptology 2021) were recently selected as winner of the NIST lightweight cryptography competition. The mode underlying Ascon authenticated encryption (Ascon-AE) resembles ideas of SpongeWrap, but not quite, and various works have investigated the generic security of Ascon-AE, all covering different attack[…] -
Comprehensive Modelling of Power Noise via Gaussian Processes with Applications to True Random Number Generators
Speaker : Maciej Skorski - Laboratoire Hubert Curien
The talk examines power noise modelling through Gaussian Processes for secure True Random Number Generators. While revisiting one-sided fractional Brownian motion, we obtain novel contributions by quantifying posterior uncertainty in exact analytical form, establishing quasi-stationary properties, and developing rigorous time-frequency analysis. These results are applied to model oscillator[…]-
Cryptography
-
TRNG
-
-
CryptoVerif: a computationally-sound security protocol verifier
Speaker : Bruno Blanchet - Inria
CryptoVerif is a security protocol verifier sound in the computational model of cryptography. It produces proofs by sequences of games, like those done manually by cryptographers. It has an automatic proof strategy and can also be guided by the user. It provides a generic method for specifying security assumptions on many cryptographic primitives, and can prove secrecy, authentication, and[…]-
Cryptography
-