[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.

BibTeX

Copy

@Article{BluMic84,
  author = {Manuel Blum and Silvio Micali},
  title = {How to Generate Cryptographically Strong Sequences of Pseudorandom Bits},
  pages = {850--864},
  journal = {{SIAM} Journal on Computing},
  volume = {13},
  number = {4},
  year = {1984},
}