On propagation characteristics of resilient functions
Pascale Charpin
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France Pascale.Charpin@inria.fr
Enes Pasalic
Department of Information Technology,
Lund University,
P. O. Box 118, 221 00 Lund, Sweden. enes@it.lth.se
Selected Areas in Cryptography, SAC~2002 , August 2002,
LNCS, to appear
Abstract
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.
Keywords
Boolean functions, nonlinearity, propagation
characteristics, resiliency, linear space.