Propagation characteristics and correlation-immunity of highly nonlinear Boolean functions


Anne Canteaut
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Anne.Canteaut@inria.fr

Claude Carlet
GREYC, Université de Caen
and
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Claude.Carlet@inria.fr

Pascale Charpin
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Pascale.Charpin@inria.fr

Caroline Fontaine
LIFL
Université des Sciences et Technologies de Lille
59655 Villeneuve d'Ascq Cedex, France
Caroline.Fontaine@lifl.fr

In Advances in Cryptology - EUROCRYPT 2000 , LNCS, Springer-Verlag, 2000.
To appear.

Abstract

We investigate the link between the nonlinearity of a Boolean function and its propagation characteristics. We prove that highly nonlinear functions usually have good propagation properties regarding different criteria. Conversely, any Boolean function satisfying the propagation criterion with respect to a linear subspace of codimension~1 or~2 has a high nonlinearity. We also point out that most highly nonlinear functions with a three-valued Walsh spectrum can be transformed into 1-resilient functions.

Keywords

Boolean functions, nonlinearity, propagation criterion, correlation-immunity.