Institut de Mathématiques de Luminy

Abstract 2003-10

Rodier François.
Asymptotic nonlinearity of Boolean functions

Boolean functions on the space $F_{2}^m$ are not only important in the theory of error-correcting codes, but also in cryptography. In these two cases, the nonlinearity of these functions is a main concept. Carlet, Olejár and Stanek gave an asymptotic lower bound for the nonlinearity of most of them, and I gave an asymptotic upper bound which was strictly larger. In this article, I improve the bounds and get an exact limit for the nonlinearity of most of them. This article is inspired by a paper of G. Halácz about the related problem of real polynomials with random coefficients.

Keywords : covering radius, error-correcting code, cryptography, nonlinearity, Boolean function , Fourier transform..


Last update : september 29, 2003, EL.