International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at)


Burton Stephen Kaliski Jr. (#493)
Name Burton Stephen Kaliski Jr.
Topic of his/her doctorate. Elliptic Curves and Cryptography: A Pseudorandom Bit Generator and Other Tools
Category public-key cryptography
Keywords cryptography, elliptic curves, pseudorandom bit generators
Ph.D. Supervisor(s) Ronald Linn Rivest
Year of completion 1988

In recent years there has been much research concerning randomness and the generation of pseudorandom strings of bits. The purpose of this thesis is to develop a new pseudorandom bit generator based on one of the most interesting topics in cryptograpy today, elliptic curves. But this is not the only result, and a number of other tools, relating both to elliptic curves and to cryptography, are developed as well in the course of constructing the generator. The other tools make use of other new results in cryptography and set the ground for a general approach for generating pseudorandom bits.

This thesis outlines the problems encountered in constructing new pseudorandom bit generators and presents methods for solving them. For elliptic curves, each of the problems is solved completely in the thesis. In general there remain open questions for further research.

Among the secondary results are the following:

1. a probabilistic polynomial time algorithm for testing whether the order of an element is maximum in a finte commutative group whose size is known;

2. a new reduction which holds in any finite commutative group of bounded rank showing that if logarithms are hard to compute in the group then the most significant bit of the logarithm cannot be predicted in polynomial time with probability significantly more than 1/2.

Last Change 2011-04-22 04:15:14
To provide an update on this entry, please click .

Contact: phds (at)

[ IACR home page ] [ IACR PhDs page ] © IACR