Attacking the linear congruential generator on elliptic curves via lattice techniques

Abstract

In this paper we study the linear congruential generator on elliptic curves from the cryptographic point of view. We show that if sufficiently many of the most significant bits of the composer and of three consecutive values of the sequence are given, then one can recover the seed and the composer (even in the case where the elliptic curve is private). The results are based on lattice reduction techniques and improve some recent approaches of the same security problem. We also estimate limits of some heuristic approaches, which still remain much weaker than those known for nonlinear congruential generators. Several examples are tested using implementations of ours algorithms.