Abstract
We revisit “the randomized iterate” technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma (which is folklore in leakage resilient cryptography), and use it to provide a simpler and more modular proof for the Haitner-Harnik-Reingold PRGs from regular OWFs.
We introduce a more general class of OWFs called “weakly-regular one-way functions” from which we construct a PRG of seed length O(n·logn). More specifically, consider an arbitrary one-way function f with range divided into sets \({\mathcal{Y}}_1\), \({\mathcal{Y}}_2\), …, \({\mathcal{Y}}_n\) where each \({\mathcal{Y}}_i\stackrel{\sf def}{=}\{y:2^{i-1}\le|f^{-1}(y)|<2^{i}\}\). We say that f is weakly-regular if there exists a (not necessarily efficient computable) cut-off point max such that \({\mathcal{Y}}_{\rm max}\) is of some noticeable portion (say n − c for constant c), and \({\mathcal{Y}}_{{\rm max}+1}\), …, \({\mathcal{Y}}_{n}\) only sum to a negligible fraction. We construct a PRG by making \(\tilde{O}(n^{2c+1})\) calls to f and achieve seed length O(n·logn) using bounded space generators. This generalizes the approach of Haitner et al., where regular OWFs fall into a special case for c = 0. We use a proof technique that is similar to and extended from the method by Haitner, Harnik and Reingold for hardness amplification of regular weakly-one-way functions.
Our work further explores the feasibility and limits of the “randomized iterate” type of black-box constructions. In particular, the underlying f can have an arbitrary structure as long as the set of images with maximal preimage size has a noticeable fraction. In addition, our construction is much more seed-length efficient and security-preserving (albeit less general) than the HILL-style generators where the best known construction by Vadhan and Zheng (STOC 2012) requires seed length \(\tilde{O}(n^3)\).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barak, B., Dodis, Y., Krawczyk, H., Pereira, O., Pietrzak, K., Standaert, F.-X., Yu, Y.: Leftover hash lemma, revisited. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 1–20. Springer, Heidelberg (2011)
Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudorandom bits. In: Proceedings of the 23rd IEEE Symposium on Foundation of Computer Science (FOCS 1982), pp. 112–117 (1982)
Dedić, N., Harnik, D., Reyzin, L.: Saving private randomness in one-way functions and pseudorandom generators. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 607–625. Springer, Heidelberg (2008)
Dodis, Y., Pietrzak, K., Wichs, D.: Key derivation without entropy waste. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 93–110. Springer, Heidelberg (2014)
Dodis, Y., Yu, Y.: Overcoming weak expectations. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 1–22. Springer, Heidelberg (2013)
Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press (2001)
Goldreich, O., Krawczyk, H., Luby, M.: On the existence of pseudorandom generators. SIAM Journal on Computing 22(6), 1163–1175 (1993)
Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC 1989), pp. 25–32 (1989)
Goldreich, O., Levin, L.A., Nisan, N.: On constructing 1-1 one-way functions. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 13–25. Springer, Heidelberg (2011), http://dx.doi.org/10.1007/978-3-642-22670-0_3
Haitner, I., Harnik, D., Reingold, O.: On the power of the randomized iterate. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. CRYPTO 2006, pp. 22–40. Springer, Heidelberg (2006)
Haitner, I., Harnik, D., Reingold, O.: On the power of the randomized iterate. SIAM Journal on Computing 40(6), 1486–1528 (2011), http://www.cs.tau.ac.il/~iftachh/papers/RandomizedIteate/RandomIterate.pdf
Haitner, I., Reingold, O., Vadhan, S.P.: Efficiency improvements in constructing pseudorandom generators from one-way functions. In: Proceedings of the 42nd ACM Symposium on the Theory of Computing (STOC 2010), pp. 437–446 (2010)
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: Construction of pseudorandom generator from any one-way function. SIAM Journal on Computing 28(4), 1364–1396 (1999)
Holenstein, T.: Pseudorandom generators from one-way functions: A simple construction for any hardness. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 443–461. Springer, Heidelberg (2006)
Holenstein, T., Sinha, M.: Constructing a pseudorandom generator requires an almost linear Number of calls. In: Proceedings of the 53rd IEEE Symposium on Foundation of Computer Science (FOCS 2012), pp. 698–707 (2012)
Impagliazzo, R., Nisan, N., Wigderson, A.: Pseudorandomness for network algorithms. In: Proceedings of the 26th ACM Symposium on the Theory of Computing (STOC 1994), pp. 356–364 (1994)
Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica 12(4), 449–461 (1992)
Vadhan, S.P., Zheng, C.J.: Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In: Proceedings of the 44th ACM Symposium on the Theory of Computing (STOC 2012), pp. 817–836 (2012)
Yao, A.C.C.: Theory and applications of trapdoor functions (extended abstract). In: Proceedings of the 23rd IEEE Symposium on Foundation of Computer Science (FOCS 1982), pp. 80–91 (1982)
Yu, Y., Gu, D., Li, X., Weng, J.: The randomized iterate revisited - almost linear seed length PRGs from a broader class of one-way functions. Tech. Rep. 2014/392, Cryptology e-print archive, full version of this work, http://eprint.iacr.org/2014/392
Yu, Y., Li, X., Weng, J.: Pseudorandom generators from regular one-way functions: New constructions with improved parameters. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 261–279. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 International Association for Cryptologic Research
About this paper
Cite this paper
Yu, Y., Gu, D., Li, X., Weng, J. (2015). The Randomized Iterate, Revisited - Almost Linear Seed Length PRGs from a Broader Class of One-Way Functions. In: Dodis, Y., Nielsen, J.B. (eds) Theory of Cryptography. TCC 2015. Lecture Notes in Computer Science, vol 9014. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46494-6_2
Download citation
DOI: https://doi.org/10.1007/978-3-662-46494-6_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46493-9
Online ISBN: 978-3-662-46494-6
eBook Packages: Computer ScienceComputer Science (R0)