Constructing a pseudorandom generator requires an almost linear number of calls

Thomas Holenstein, Makrand Sinha

Research output: Contribution to journalConference articlepeer-review

Abstract

We show that a black-box construction of a pseudorandom generator from a one-way function needs to make Ω(n/log(n)) calls to the underlying one-way function. The bound even holds if the one-way function is guaranteed to be regular. In this case it matches the best known construction due to Gold Reich, Krawczyk, and Luby (SIAM J. Comp. 22, 1993), which uses O(n/log(n)) calls.

Original languageEnglish (US)
Article number6375349
Pages (from-to)698-707
Number of pages10
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs
StatePublished - 2012
Externally publishedYes
Event53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 - New Brunswick, NJ, United States
Duration: Oct 20 2012Oct 23 2012

Keywords

  • Black-box separation
  • One-way Functions
  • Pseudorandom Generators

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'Constructing a pseudorandom generator requires an almost linear number of calls'. Together they form a unique fingerprint.

Cite this