Generalization of Siegenthaler inequality and Schnorr-Vaudenay multipermutations


Paul Camion

INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Paul.Camion@inria.fr

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

In Advances in Cryptology - CRYPTO'96 , LNCS 1109, pages 372-386.
Springer-Verlag, 1996.


Abstract

Siegenthaler inequality shows the existence of a tradeoff between the correlation-immunity order and the nonlinearity order of a Boolean functions. We generalize this result to correlation-immune functions over any finite field. We then construct a family of correlation-immune functions achieving this bound; these functions are notably well-suited for combining linear feedback shift registers. We also apply this result to the cryptanalysis of any cryptographic primitive based on boxes connected by a network. Schnorr and Vaudenay have previously recommended that these boxes should be multipermutations; we here refine this condition since we show that each binary component of these multipermutations, seen as a Boolean function, should have low degree.