Parity-Check Relations on Combination Generators

Abstract : A divide-and-conquer cryptanalysis can often be mounted against some keystream generators composed of several (possibly 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 formulas for this bias in some particular cases which are commonly used in cryptography, namely resilient functions and plateaued functions. We also show how to build parity-check relations with the highest possible bias in some particularly relevant cases.
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2012, 58 (6), pp.3900-3911. 〈10.1109/TIT.2012.2184736〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01110509
Contributeur : Anne Canteaut <>
Soumis le : mercredi 28 janvier 2015 - 13:12:41
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

Collections

Citation

Anne Canteaut, María Naya-Plasencia. Parity-Check Relations on Combination Generators. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2012, 58 (6), pp.3900-3911. 〈10.1109/TIT.2012.2184736〉. 〈hal-01110509〉

Partager

Métriques

Consultations de la notice

92