Correlation-immune and resilient functions over a finite alphabet and their applications in cryptography.


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

Designs, Codes and Cryptography, 16, pages 121-149, 1999.


Abstract

We extend the notions of correlation-immune functions and resilient functions to functions over any finite alphabet. A previous result due to Gopalakrishnan and Stinson is generalized as we give an orthogonal array characterization, a Fourier transform and a matrix characterization for correlation-immune and resilient functions over any finite alphabet endowed with the structure of an Abelian group. We then point out the existence of a tradeoff between the degree of the algebraic normal form and the correlation-immunity order of any function defined on a finite field and we construct some infinite families of t-resilient functions with optimal nonlinearity which are particularly well-suited for combining linear feedback shift registers. We also point out the link between correlation-immune functions and some cryptographic objects as perfect local randomizers and multipermutations.

Keywords

correlation-immune functions, resilient functions, orthogonal arrays, pseudo-random generators, multipermutations