Highly nonlinear balanced Boolean functions with a good correlation-immunity


Eric Filiol
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
and
Ecoles Militaires de Coëtquidan, DGER/CREC
56381 Guer Cedex, France
Eric.Filiol@inria.fr

Caroline Fontaine
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Caroline.Fontaine@inria.fr

Advances in Cryptology - EUROCRYPT'98, LNCS 1403, pages 475-488.
Springer-Verlag, 1998.

Abstract

We study a corpus of particular Boolean functions: the idempotents. They enable us to construct functions which achieve the best possible tradeoffs between the cryptographic fundamental properties: balancedness, correlation-immunity, a high degree and a high nonlinearity (that is a high distance from the affine functions). They all represent extremely secure cryptographic primitives to be implemented in stream ciphers.

Keywords

Boolean function, correlation, nonlinearity, balancedness, idempotent, stream cipher.