Welcome to the resource topic for 2013/270
Title:
Pseudorandom Generators from Regular One-way Functions: New Constructions with Improved Parameters
Authors: 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.
ePrint: https://eprint.iacr.org/2013/270
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .