Institut de Mathématiques de Luminy

Abstract 2006-13

Rodier François.
Borne sur le degré des polynômes presque parfaitement non-linéaires

The vectorial Boolean functions are employed in cryptography to build block coding algorithms. An important criterion on these functions is their resistance to the differential cryptanalysis. Nyberg defined the notion of almost perfect non-linearity (APN) to study resistance to the differential attacks. Up to now, the study of functions APN was especially devoted to the function powers. Recently, Budaghyan and al. showed that certain quadratic polynomials were APN. Here, we will give a criterion so that a function is not almost perfectly non-linear. H. Janwa showed, by using Weil's bound, that certain cyclic codes could not correct two errors. A. Canteaut showed by using the same method that the functions powers were not APN for a too large value of the exponent. We could generalize this result to all the polynomials by using a result of P. Deligne (or more exactly an improvement given by Ghorpade and Lachaud) on the Weil's conjectures. We show therefore that a polynomial cannot be APN if its degree is too large.


Last update : july 4, 2006, EL.