Welcome to the resource topic for 2007/099
Title:
Inferring sequences produced by a linear congruential generator on elliptic curves missing high–order bits
Authors: Jaime Gutierrez, 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.
ePrint: https://eprint.iacr.org/2007/099
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .