Cubic Boolean functions with highest resiliency
Claude Carlet and Pascale Charpin
University of Paris 8 and INRIA projet CODES
Claude.Carlet@inria.fr
Pascale.Charpin@inria.fr
Presented at ISIT 2004, Chicago, USA.
Regular paper in IEEE Transactions on Information Theory.
Vol. 51, No 2, pp. 562-71, February 2005.
Abstract
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.
Keywords
Boolean function, cubic function, resilient function,
Reed-Muller code, Hamming weight,
symmetric cryptography, stream cipher.