[GGM86] How to construct random functions

Authors: Oded Goldreich, Shafi Goldwasser, Silvio Micali | Venue: Journal of the ACM 1986 | Source

Abstract

A constructive theory of randomness for functions, based on computational complexity, is developed, and a pseudorandom function generator is presented. This generator is a deterministic polynomial-time algorithm that transforms pairs ($g$, $r$), where $g$ is \textit{any} one-way function and $r$ is a random $k$-bit string, to polynomial-time computable functions ${ƒ}_r$: {1, …, $2^k$} → {1, …, $2^k$}. These ${ƒ}_r$‘s cannot be distinguished from \textit{random} functions by any probabilistic polynomial-time algorithm that asks and receives the value of a function at arguments of its choice. The result has applications in cryptography, random constructions, and complexity theory.

BibTeX

Copy

@Article{GolGolMic86,
  author = {Oded Goldreich and Shafi Goldwasser and Silvio Micali},
  title = {How to Construct Random Functions},
  pages = {792--807},
  journal = {Journal of the {ACM}},
  volume = {33},
  number = {4},
  month = {oct},
  year = {1986},
  doi = {10.1145/6490.6503},
  annote = {Full version of \cite{FOCS:GolGolMic84}},
}