[BM84] How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits

Authors: Manuel Blum, Silvio Micali | Venue: SIAM Journal on Computing 1984 | Source

Abstract

We present a polynomial-time algorithm that, given a short random seed, generates a sequence of pseudo-random bits that is computationally indistinguishable from a truly random sequence. The construction is based on the assumed difficulty of the discrete logarithm problem: given $g^x\mathrm{mod}p$, it is hard to compute $g^{x-1}\mathrm{mod}p$ or to predict the most significant bit of $x$. The security of the generator is proved under this assumption. This was the first construction of a cryptographically secure pseudorandom generator based on a concrete computational hardness assumption, introducing the notion of a pseudorandom generator formally and establishing the connection between one-way functions and pseudorandomness that was later generalized by HILL99.