Paper 2013/270

Pseudorandom Generators from Regular One-way Functions: New Constructions with Improved Parameters

Yu Yu

Abstract

We revisit the problem of basing pseudorandom generators on regular one-way functions, and present the following constructions: (1) For any known-regular one-way function (on $n$-bit inputs) that is known to be $\eps$-hard to invert, we give a neat (and tighter) proof for the folklore construction of pseudorandom generator of seed length $\Theta(n)$ by making a single call to the underlying one-way function. (2) For any unknown-regular one-way function with known $\eps$-hardness, we give a new construction with seed length $\Theta(n)$ and $O(n/\log{(1/\eps)})$ calls. Here the number of calls is also optimal by matching the lower bounds of Holenstein and Sinha [FOCS 2012]. Both constructions require the knowledge about $\eps$, but the dependency can be removed while keeping nearly the same parameters. In the latter case, we get a construction of pseudo-random generator from any unknown-regular one-way function using seed length $\tilde{O}(n)$ and $\tilde{O}(n/\log{n})$ calls, where $\tilde{O}$ omits a factor that can be made arbitrarily close to constant (e.g. $\log\log\log{n}$ or even less). This improves the \emph{randomized iterate} approach by Haitner, Harnik and Reingold [CRYPTO 2006] which requires seed length $O(n{\log}{n})$ and $O(n/\log{n})$ calls.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in ASIACRYPT 2013
Keywords
one-way functionspseudorandom generatorsrandomized iterate
Contact author(s)
yuyuathk @ gmail com
History
2013-09-18: last of 3 revisions
2013-05-13: received
See all versions
Short URL
https://ia.cr/2013/270
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/270,
      author = {Yu Yu},
      title = {Pseudorandom Generators from Regular One-way Functions: New Constructions with Improved Parameters},
      howpublished = {Cryptology ePrint Archive, Paper 2013/270},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/270}},
      url = {https://eprint.iacr.org/2013/270}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.