On cryptographic propagation criteria for Boolean functions


Claude Carlet
GREYC, Université de Caen
and
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Claude.Carlet@inria.fr

Information and Computation, 151, pages 32-56, 1999.
(Special Issue on Cryptology in Honor of Professor Arto Salomaa on Occasion of His 65th Birthday), invited paper

Abstract

We determine the functions on GF(2)n which satisfy the propagation criterion of degree (n-2), PC(n-2). We study subsequently the propagation criterion of degree l and order k and its extended version EPC. We determine those Boolean functions on GF(2)n which satisfy PC(l) of order greater than or equal to (n-l-2). We show that none of them satisfies EPC(l) of same order. We finally give a general construction of nonquadratic functions satisfying EPC(l) of order k. This construction uses the existence of nonlinear, systematic codes with good minimum distances and dual distances (e.g. Kerdock codes and Preparata codes).