Inferring Sequences Produced by Nonlinear Pseudorandom Number Generators Using Coppersmith's Methods

Abstract : Number-theoretic pseudorandom generators work by iterating an algebraic map F (public or private) over a residue ring ℤ N on a secret random initial seed value v 0 ∈ ℤ N to compute values for n ∈ ℕ. They output some consecutive bits of the state value v n at each iteration and their efficiency and security are thus strongly related to the number of output bits. In 2005, Blackburn, Gomez-Perez, Gutierrez and Shparlinski proposed a deep analysis on the security of such generators. In this paper, we revisit the security of number-theoretic generators by proposing better attacks based on Coppersmith's techniques for finding small roots on polynomial equations. Using intricate constructions, we are able to significantly improve the security bounds obtained by Blackburn et al..
Type de document :
Communication dans un congrès
Marc Fischlin, Johannes Buchmann & Mark Manulis. Public Key Cryptography - PKC 2012, 2012, Darmstadt, Germany. Springer, 7293, pp.609-626, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-30057-8_36〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00871331
Contributeur : Damien Vergnaud <>
Soumis le : mercredi 9 octobre 2013 - 14:38:11
Dernière modification le : jeudi 11 janvier 2018 - 06:22:10

Identifiants

Collections

Citation

Aurélie Bauer, Damien Vergnaud, Jean-Christophe Zapalowicz. Inferring Sequences Produced by Nonlinear Pseudorandom Number Generators Using Coppersmith's Methods. Marc Fischlin, Johannes Buchmann & Mark Manulis. Public Key Cryptography - PKC 2012, 2012, Darmstadt, Germany. Springer, 7293, pp.609-626, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-30057-8_36〉. 〈hal-00871331〉

Partager

Métriques

Consultations de la notice

260