Abstract
Can a one-way function f on n input bits be used with fewer than n bits while retaining comparable hardness of inversion? We show that the answer to this fundamental question is negative, if one is limited black-box reductions.
Instead, we ask whether one can save on secret random bits at the expense of more public random bits. Using a shorter secret input is highly desirable, not only because it saves resources, but also because it can yield tighter reductions from higher-level primitives to one-way functions. Our first main result shows that if the number of output elements of f is at most 2k, then a simple construction using pairwise-independent hash functions results in a new one-way function that uses only k secret bits. We also demonstrate that it is not the knowledge of security of f, but rather of its structure, that enables the savings: a black-box reduction cannot, for a general f, reduce the secret-input length, even given the knowledge that security of f is only 2− k; nor can a black-box reduction use fewer than k secret input bits when f has 2k distinct outputs.
Our second main result is an application of the public-randomness approach: we show a construction of a pseudorandom generator based on any regular one-way function with output range of known size 2k. The construction requires a seed of only \(2n+{\mathcal O}(k {\rm log} k)\) bits (as opposed to \({\mathcal O}(n \log n)\) in previous constructions); the savings come from the reusability of public randomness. The secret part of the seed is of length only k (as opposed to n in previous constructions), less than the length of the one-way function input.
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
Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: 23rd FOCS, pp. 112–117 (1982)
Carter, I., Wegman, M.: Universal classes of hash functions. In: 9th ACM Symposium on Theory of Computing, pp. 106–112 (1977)
Dedić, N., Harnik, D., Reyzin, L.: Saving private randomness in one-way functions and pseudorandom generators. Technical Report 2007/458, Cryptology e-print archive (2007), http://eprint.iacr.org
Dodis, Y., Smith, A.: Correcting errors without leaking partial information. In: 37th STOC, pp. 654–663 (2005)
Goldreich, O., Impagliazzo, R., Levin, L., Venkatesan, R., Zuckerman, D.: Security preserving amplification of hardness. In: 31st IEEE Symposium on Foundations of Computer Science, pp. 318–326 (1990)
Goldreich, O., Krawczyk, H., Luby, M.: On the existence of pseudorandom generators. SIAM Journal of Computing 22(6), 1163–1175 (1993)
Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: 21st ACM Symposium on the Theory of Computing, pp. 25–32 (1989)
Goldreich, O.: Foundations of Cryptography. Cambridge University Press, Cambridge (2001)
Haitner, I., Harnik, D., Reingold, O.: Efficient pseudorandom generators from exponentially hard one-way functions. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 228–239. Springer, Heidelberg (2006)
Haitner, I., Harnik, D., Reingold, O.: On the power of the randomized iterate. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 22–40. Springer, Heidelberg (2006)
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM Journal of Computing 29(4), 1364–1396 (1999)
Herzberg, A., Luby, M.: Pubic randomness in cryptography. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 421–432. Springer, Heidelberg (1993)
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)
Impagliazzo, R., Nisan, N., Wigderson, A.: Pseudorandomness for network algorithms. In: 26th STOC, pp. 356–364 (1994)
Levin, L.A.: Average case complete problems. SIAM Journal on Computing 15(1), 285–286 (1986)
Levin, L.A.: One-way functions and pseudorandom generators. Combinatorica 7, 357–363 (1987)
Levin, L.A.: Randomness and nondeterminism. The Journal of Symbolic Logic 58(3), 1102–1103 (1993)
Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica 12(4), 449–461 (1992)
Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing 22(4), 838–856 (1993)
Wegman, M., Carter, J.: New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences (1981)
Yao, A.C.: Theory and application of trapdoor functions. In: 23rd IEEE Symposium on Foundations of Computer Science, pp. 80–91 (1982)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dedić, N., Harnik, D., Reyzin, L. (2008). Saving Private Randomness in One-Way Functions and Pseudorandom Generators. In: Canetti, R. (eds) Theory of Cryptography. TCC 2008. Lecture Notes in Computer Science, vol 4948. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78524-8_33
Download citation
DOI: https://doi.org/10.1007/978-3-540-78524-8_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78523-1
Online ISBN: 978-3-540-78524-8
eBook Packages: Computer ScienceComputer Science (R0)