Skip to Main content Skip to Navigation
Conference papers

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..
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-00871331
Contributor : Damien Vergnaud Connect in order to contact the contributor
Submitted on : Wednesday, October 9, 2013 - 2:38:11 PM
Last modification on : Thursday, March 17, 2022 - 10:08:36 AM

Links full text

Identifiers

Citation

Aurélie Bauer, Damien Vergnaud, Jean-Christophe Zapalowicz. Inferring Sequences Produced by Nonlinear Pseudorandom Number Generators Using Coppersmith's Methods. PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, May 2012, Darmstadt, Germany. pp.609-626, ⟨10.1007/978-3-642-30057-8_36⟩. ⟨hal-00871331⟩

Share

Metrics

Record views

156