Under the assumption that solving the discrete logarithm problem modulo an
n-bit prime
p is hard even when the exponent is a small
c-bit number, we construct a new and improved pseudo-random bit generator. This new generator outputs
n -
c - 1 bits per exponentiation with a
c-bit exponent.
Using typical parameters, n = 1024 and c = 160, this yields roughly 860 pseudo-random bits per small exponentiations. Using an implementation with quite small precomputation
tables, this yields a rate of more than 20 bits per modular multiplication, thus much faster than the the squaring (BBS) generator
with similar parameters.