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

Jaime Gutierrez; Alvar Ibeas

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 = n G \oplus U_{0}, n = 1, 2, \dots,$ 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 and sufficiently many of the most significants bits of two consecutive values of the EC-LCG are given, one can recover the seed (even in the case where the elliptic curve is private) provided that the former value does not lie in a certain small subset of exceptional values. We also estimate limits of a heuristic approach for the case where 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: 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},
      url = {https://eprint.iacr.org/2007/099}
}