Skip to Main content Skip to Navigation
Conference papers

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

Aurélie Bauer 1 Damien Vergnaud 2, 3, 4 Jean-Christophe Zapalowicz 5
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
5 CELTIQUE - Software certification with semantic analysis
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
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
Contributor : Damien Vergnaud <>
Submitted on : Wednesday, October 9, 2013 - 2:38:11 PM
Last modification on : Friday, July 2, 2021 - 3:37:41 AM

Links full text



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⟩



Record views