Highly nonlinear resilient functions through disjoint codes in projective spaces


Pascale Charpin and Enes Pasalic


INRIA, projet CODES
Pascale.Charpin@inria.fr, enespasalic@yahoo.se

Designs, Codes and Cryptography, 37, 319-346, 2005.

Abstract

Functions which map n-bits to m-bits are important cryptographic sub-primitives in the design of
additive stream ciphers. We construct highly nonlinear t-resilient such functions ((n,m,t) functions) by
using a class of binary disjoint codes, a construction which was recently introduced by Johansson and
Pasalic. Our main contribution concerns the generation of suitable sets of such disjoint codes.
We propose a deterministic method for finding disjoint codes of length um by considering the points of
PG (u-1,GF(2^m)). We then obtain some lower bounds on the number of disjoint codes, by fixing some
parameters. Through these sets, we deduce in certain cases the existence of resilient functions
with very high nonlinearity values. We show how, thanks to our method, the degree and the differential properties
of (n,m,t) functions can be improved.

KEYWORDS
Boolean function, $n$-input $m$-output function, resilient function, nonlinearity, propagation characteristic,
symmetric cryptography, stream cipher, linear code, projective space, complete weight enumerator.