Inferring Sequences Produced by a Linear Congruential Generator on Elliptic Curves Using Coppersmith's Methods

Thierry Mefenza (1, 2)

1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
2 DI-ENS - Département d'informatique - ENS Paris

We analyze the security of the Elliptic Curve Linear Con-gruential Generator (EC-LCG). We show that this generator is insecure if sufficiently many bits are output at each iteration. In 2007, Gutierrez and Ibeas showed that this generator is insecure given a certain amount of most significant bits of some consecutive values of the sequence. Using the Coppersmith's methods, we are able to improve their security bounds.

Mots clés: Elliptic Curve Linear Congruential Generator; Lattice reduction; Coppersmith's methods; Elliptic Curves

Domaines: Informatique [cs]

Thierry Mefenza. Inferring Sequences Produced by a Linear Congruential Generator on Elliptic Curves Using Coppersmith's Methods. COCOON 2016, Aug 2016, Ho Chi Minh City, Vietnam. pp.12, ⟨10.1007/978-3-319-42634-1_24⟩. ⟨hal-01381658⟩