Access Restriction

Author Goldreich, Oded ♦ Goldwasser, Shafi ♦ Micali, Silvio
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1986
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
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 $(\textit{g},$ $\textit{r}),$ where $\textit{g}$ is $\textit{any}$ one-way function and $\textit{r}$ is a random $\textit{k}-bit$ string, to polynomial-time computable functions $ƒ\textit{r}:$ {1, … , $2\textit{k}}$ → {1, … , $2\textit{k}}.$ These $ƒ\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1986-08-10
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 33
Issue Number 4
Page Count 16
Starting Page 792
Ending Page 807

Open content in new tab

   Open content in new tab
Source: ACM Digital Library