cette page en franšais

Attacks on low-weight cryptosystems
and construction of t-resilient functions

Anne Canteaut, PhD Thesis, UniversitÚ Paris VI, 1996.


This thesis is dedicated to the study of cryptographic objects connected with combinatorics and coding theory. We especially focus on the public-key systems relying on the hardness of finding a minimum-weight word in any linear code, and on the correlation-immune and resilient functions which are essential tools to the generation of pseudo-random sequences and to the conception of conventional cryptographic primitives.
We develop a probabilistic algorithm for finding low-weight words in a large linear code which improves all the previously known attacks on the cryptosystems using low-weight codewords. Studying its complexity with the Markov chain theory notably shows that McEliece's cipher with its original parameters does usually not provide a sufficient security-level. This algorithm also enables us to determine the minimum distance of some BCH codes of length 511.
On the other hand we generalize the notions of correlation-immune and resilient functions to the functions defined on any finite alphabet and we characterize these properties in different ways. We then point out the existence of a trade-off between the degree of the algebraic normal form and the correlation-immunity order of any function defined on a finite field and we construct some infinite families of t-resilient functions with optimal degree. This result implies a new security criterion for conventional cryptographic primitives, which enriches the concept of multipermutation introduced by Schnorr and Vaudenay. We finally develop a general construction which provides new resilient functions with a great number of variables.


Paul Camion (CNRS)
Claude Carlet (UniversitÚ de Caen)
Pascale Charpin (INRIA)
Alain Lanusse (DRET)
Michel Minoux (UniversitÚ Paris VI)
James L. Massey (ETH ZŘrich)
Jacques Stern (ENS Ulm)