Distribution of Boolean functions Nonlinearity

Parmi les différents critères qu'une fonction booléenne doit satisfaire en cryptographie, on s'intéresse à la non-linéarité. Pour une fonction booléenne donnée, cette notion mesure la distance de Hamming qui la sépare des fonctions de degré au plus 1. C'est un critère naturel pour évaluer la complexité d'une fonction cryptographique, celle-ci ne devant pas admettreune approximation qui soit simple, comme par une fonction de degré 1, ou plus généralement une fonction de bas degré. Ainsi, il est important de considérer plus généralement, la non-linéarité d'ordre supérieur, qui pour un ordre donné r, mesure la distance d'une fonction donnée à l'ensemble des fonctions de degré au plus r. Cette notion est également importante pour les fonctions vectorielles, i.e., celles à plusieurs sorties. Quand le nombre de variables est grand, presque toutes les fonctions ont une non-linéarité (d'ordre 1) voisine d'une certaine valeur, assez élevée. Dans un premier travail, on étend ce résultat à l'ordre 2. Cette méthode qui consiste à observer comment les boules de Hamming recouvrent l'hypercube des fonctions booléennes, nous conduit naturellement vers une borne de décodage théorique des codes de Reed-Muller d'ordre 1, coïncidant au même endroit où se concentre la non-linéarité de presque toutes les fonctions ; une approche nouvelle pour un résultat pas entièrement nouveau. On étudie aussi la non-linéarité des fonctions vectorielles. On montre avec une approche différente, que le comportement asymptotique est le même que celui des fonctions booléennes: une concentration de la non-linéarité autour d'une valeur assez élevée.Among the different criteria that a Boolean function must satisfy in symmetric cryptography, we focus on the nonlinearity of these. This notion measures the Hamming distance between a given function and the set of functions with degree at most 1. It is a natural criterion to evaluate the complexity of a cryptographic function that must not have a simple approximation as by a function of degree 1, or more generally, a function of low degree. Hence, it is important to consider the higher order nonlinearity, which for a given order r, measures the distance between a given function and the set of all functions of degree at most r. This notion is equally important for multi-output Boolean functions. When the number of variables is large enough, almost all Boolean functions have nonlinearities lying in a small neighbourhood of a certain high value. We prove that this fact holds when considering the second-order nonlinearity. Our method which consists in observing how the Hamming balls pack the hypercube of Boolean functions led quite naturally to a theoretical decoding bound for the first-order Reed-Muller code, coinciding with the concentration point of the nonlinearity of almost all functions. This was a new approach for a result which is not entirely new. We also studied the nonlinearity of multi-output functions. We proved with a different approach, that the asymptotic behaviour of multi-output functions is the same as the single-output ones: a concentration of the nonlinearity around a certain large value