On propagation characteristics of resilient functions

Pascale Charpin

BP 105
78153 Le Chesnay Cedex, France

Enes Pasalic
Department of Information Technology,
Lund University,
P. O. Box 118, 221 00 Lund, Sweden.

Selected Areas in Cryptography, SAC~2002 , August 2002, LNCS, to appear


In this paper we derive several important results towards a better understanding of propagation characteristics of resilient Boolean functions. We first introduce a new upper bound on nonlinearity of a given resilient function depending on the propagation criterion. We later show that a large class of resilient functions admit a linear structure; more generally, we exhibit some divisibility properties concerning the Walsh-spectrum of the derivatives of any resilient function. We prove that, fixing the order of resiliency and the degree of propagation criterion, a high algebraic degree is a necessary condition for construction of functions with good autocorrelation properties. We conclude by a study of the main constructions of resilient functions. We notably show how to avoid linear structures when a linear concatenation is used and when the recursive construction introduced in \cite{EnSub} is chosen.


Boolean functions, nonlinearity, propagation characteristics, resiliency, linear space.