A pseudo-random bit generator based on elliptic logarithms. (English) Zbl 0635.94011

Kaliski, Burton S. jun.

Advances in cryptology, Proc. Conf., Santa Barbara/Calif. 1986, Lect. Notes Comput. Sci. 263, 84-103 (1987).

Summary: [For the entire collection see Zbl 0624.00026.]
Recent research in cryptography has led to the construction of several pseudo-random bit generators, programs producing bits as hard to predict as solving a hard problem. In this paper: 1. We present a new pseudo- random bit generator based on elliptic curves. 2. To construct our generator, we also develop two techniques that are of independent interest: (a) an algorithm that computes the order of an element in an arbitrary Abelian group; and (b) a new oracle proof method for demonstrating the simultaneous security of multiple bits of a discrete logarithm in an arbitrary Abelian group. 3. We present a new candidate hard problem for future use in cryptography: the elliptic logarithm problem.

MSC:

94A60	Cryptography
65C10	Random number generation in numerical analysis

Keywords:

pseudo-random bit generator; elliptic curves; order of an element in an arbitrary Abelian group; oracle proof method; simultaneous security; discrete logarithm; elliptic logarithm problem

Citations:

Zbl 0624.00026