Cubic Boolean functions with highest resiliency

Claude Carlet and Pascale Charpin

University of Paris 8 and INRIA projet CODES

Presented at ISIT 2004, Chicago, USA.
Regular paper in IEEE Transactions on Information Theory.
Vol. 51, No 2, pp. 562-71, February 2005.


We classify those cubic m-variable Boolean functions which are (m-4)-resilient.
We prove that there are four types of such functions, depending on the stucture of the support
of their Walsh spectra. Our proof is based on the work of Kasami and al. (1970)
providing the characterization of the codewords of low weights of Reed-Muller codes.

We are able to determine, for each type, the Walsh spectrum and, then, the nonlinearity of the
corresponding functions. We also give the dimension of their linear space.
This dimension equals (m-k) where k=3 for the first type, k=4 for the second type, k=5
for the third type and 5<= k <= 9 for the fourth type.


Boolean function, cubic function, resilient function, Reed-Muller code, Hamming weight,
symmetric cryptography, stream cipher.