Computing the biases of parity-check relations

Anne Canteaut (1) , Maria Naya-Plasencia (1)

1 SECRET - Security, Cryptology and Transmissions

A divide-and-conquer cryptanalysis can often be mounted against some keystream generators composed of several (nonlinear) independent devices combined by a Boolean function. In particular, any parity-check relation derived from the periods of some constituent sequences usually leads to a distinguishing attack whose complexity is determined by the bias of the relation. However, estimating this bias is a difficult problem since the piling-up lemma cannot be used. Here, we give two exact expressions for this bias. Most notably, these expressions lead to a new algorithm for computing the bias of a parity-check relation, and they also provide some simple formulae for this bias in some particular cases which are commonly used in cryptography.

Domaines: Cryptographie et sécurité [cs.CR]

Anne Canteaut, Maria Naya-Plasencia. Computing the biases of parity-check relations. 2009 IEEE International Symposium on Information Theory (ISIT2009), Jun 2009, Seoul, South Korea. pp.1-5. ⟨hal-00379454⟩