کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436028 | 689964 | 2015 | 12 صفحه PDF | دانلود رایگان |
We revisit the problem of basing pseudorandom generators on regular one-way functions, and present the following constructions:
• For any known-regular one-way function (on n-bit inputs) that is known to be ε -hard to invert, we give a neat (and tighter) proof for the folklore construction of pseudorandom generator of seed length Θ(n)Θ(n) by making a single call to the underlying one-way function.
• For any unknown-regular one-way function with known ε -hardness, we give a new construction with seed length Θ(n)Θ(n) and O(n/log(1/ε))O(n/log(1/ε)) calls. Here the number of calls is also optimal by matching the lower bounds of Holenstein and Sinha (2012) [6]. Both constructions require the knowledge about ε , 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 O˜(n) and O˜(n/logn) calls, where O˜ omits a factor that can be made arbitrarily close to constant (e.g. logloglognlogloglogn or even less). This improves the randomized iterate approach by Haitner et al. (2006) [4] which requires seed length O(n⋅logn) and O(n/logn) calls.
Journal: Theoretical Computer Science - Volume 569, 2 March 2015, Pages 58–69