An efficient discrete log pseudo random generator

Abstract

The exponentiation function in a finite field of order p (a prime number) is believed to be a one-way function. It is well known that O(log log p) bits are simultaneously hard for this function. We consider a special case of this problem, the discrete logarithm with short exponents, which is also believed to be hard to compute. Under this intractibility assumption we show that discrete exponentiation modulo a prime p can hide n − Ω(log n) bits (n = [log p] and p=2q+1, where q is also a prime). We prove simultaneous security by showing that any information about the n − Ω(log n) bits can be used to discover the discrete log of g ^s mod p where s has Ω(log n) bits. For all practical purposes, the size of s can be a constant c bits. This leads to a very efficient pseudo-random number generator which produces n − c bits per iteration. For example, when n = 1024 bits and c = 128 bits our pseudo-random number generator produces a little less than 900 bits per exponentiation.