Institut de Mathématiques de Luminy

Abstract 2002-07

Rodier François.
Sur la non-linéarité des fonctions booléennes

Résumé :
On montre dans cet article que la valeur de la nonlinéarité des fonctions booléennes à m variables est généralement assez proche de sa valeur maximale. De plus, on discute une conjecture de Patterson et Wiedemann sur la valeur du maximum de cette nonlinéarité.

Abstract :
Boolean functions with m variables are not only important in the theory of error-correcting codes, but also in cryptography, where they occur in private key systems. In these two cases, the nonlinearity of these function is a main concept. In this article, I show that the nonlinearity of boolean functions is generally rather close to its upper bound. Moreover I examine a conjecture of Patterson et Wiedemann about the maximum value of this nonlinearity. I also study a weaker conjecture about the moments of order 4 of their Fourier transform. This article is inspired by works of Salem, Zygmund, Kahane and others about the related problem of real polynomials with random coefficients.

Mots clés : rayon de recouvrement, code correcteur d'erreur, cryptographie, nonlinéarité, fonction booléenne, polynôme aléatoire, transformation de Fourier.


Last update : may 21, 2002, EL.