Paper 2007/099

Inferring sequences produced by a linear congruential generator on elliptic curves missing high--order bits

Jaime Gutierrez and Alvar Ibeas

Abstract

Let $p$ be a prime and let $E(\F_p)$ be an elliptic curve defined over the finite field $\F_p$ of $p$ elements. For a given point $G \in E(\F_p)$ the linear congruential genarator on elliptic curves (EC-LCG) is a sequence $(U_n)$ of pseudorandom numbers defined by the relation $$ U_n=U_{n-1}\oplus G=nG\oplus U_0,\quad n=1,2,\ldots,$$ where $\oplus$ denote the group operation in $E(\F_p)$ and $U_0 \in E(\F_p)$ is the initial value or seed. We show that if $G$ and sufficiently many of the most significants bits of two consecutive values $U_n, U_{n+1}$ of the EC-LCG are given, one can recover the seed $U_0$ (even in the case where the elliptic curve is private) provided that the former value $U_n$ does not lie in a certain small subset of exceptional values. We also estimate limits of a heuristic approach for the case where $G$ is also unknown. This suggests that for cryptographic applications EC-LCG should be used with great care. Our results are somewhat similar to those known for the linear and non-linear pseudorandom number congruential generator.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. pseudorandom numbers, elliptic curves
Contact author(s)
jaime gutierrez @ unican es
History
2007-03-22: received
Short URL
https://ia.cr/2007/099
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/099,
      author = {Jaime Gutierrez and Alvar Ibeas},
      title = {Inferring sequences produced by a linear congruential generator on elliptic curves missing high--order bits},
      howpublished = {Cryptology ePrint Archive, Paper 2007/099},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/099}},
      url = {https://eprint.iacr.org/2007/099}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.