cette page en français
## Attacks on low-weight cryptosystems

and construction of t-resilient functions

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

## Abstract

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.

## Committee

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)