Tanja Lange: Pseudorandom number generators based on elliptic curves

This is a joint work with Igor E. Shparlinski.

We give an overview of pseudorandom number generators (PRNGs) based on elliptic curves over finite fields. Many PRNGs proposed for the multiplicative group of a finite field can be generalized to the group of $\mathbb{F}_q$-rational points of elliptic curves - clearly with different bounds. We consider in detail the power generator - starting from a point $P$ the sequence $s(0)=P, s(i)=es(i-1)=e^iP$ for some (secret) integer $e$. So following elements of the sequence can be constructed if the discrete logarithm problem is easy, i.e. if $e$ can be computed from the knowledge of $P$ and $eP$. This study also serves a second purpose - if the sequence of powers of an element would turn out to be biased, e.g. some bits were fixed for certain multiples, the discrete logarithm problem would be weaker than assumed as some bits of the exponent would leak. To compute scalar multiples on elliptic curves one can use Koblitz curves, these are curves defined over a small finite field which are then considered over a large extension field. We state results on the distribution of the scalar multiples of points.

Bibliography

1

Tanja Lange and Igor E. Shparlinski.
Certain exponential sums and random walks on elliptic curves.
(to appear in J. Canad. Math. Soc).

2

Tanja Lange and Igor E. Shparlinski.
Collisions in fast generation of ideal classes and points on hyperelliptic and elliptic curves.
(to appear in J. AAECC).

Back to the Index