On cryptographic propagation criteria for Boolean functions

Claude Carlet

GREYC, Université de Caen
BP 105
78153 Le Chesnay Cedex, France

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


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).