[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

@Inproceedings{FOCS:BluMic82,
  author = {Manuel Blum and Silvio Micali},
  title = {How to Generate Cryptographically Strong Sequences of Pseudo Random Bits},
  pages = {112--117},
  booktitle = {23rd Annual Symposium on Foundations of Computer Science},
  address = {Chicago, Illinois},
  month = {nov~3--5},
  publisher = {{IEEE} Computer Society Press},
  year = {1982},
  doi = {10.1109/SFCS.1982.72},
}