Abstract
It is well known that two random variables X and Y with the same range can be viewed as being equal (in a well-defined sense) with probability 1 − d(X,Y), where d(X,Y) is their statistical distance, which in turn is equal to the best distinguishing advantage for X and Y. In other words, if the best distinguishing advantage for X and Y is ε, then with probability 1 − ε they are completely indistinguishable. This statement, which can be seen as an information-theoretic version of a hardcore lemma, is for example very useful for proving indistinguishability amplification results.
In this paper we prove the computational version of such a hardcore lemma, thereby extending the concept of hardcore sets from the context of computational hardness to the context of computational indistinguishability. This paradigm promises to have many applications in cryptography and complexity theory. It is proven both in a non-uniform and a uniform setting.
For example, for a weak pseudorandom generator (PRG) for which the (computational) distinguishing advantage is known to be bounded by ε (e.g. \(\epsilon=\frac{1}{2}\)), one can define an event on the seed of the PRG which has probability at least 1 − ε and such that, conditioned on the event, the output of the PRG is essentially indistinguishable from a string with almost maximal min-entropy, namely log(1/(1 − ε)) less than its length. As an application, we show an optimally efficient construction for converting a weak PRG for any ε< 1 into a strong PRG by proving that the intuitive construction of applying an extractor to an appropriate number of independent weak PRG outputs yields a strong PRG. This improves strongly over the best previous construction for security amplification of PRGs which does not work for \(\epsilon \geq \frac{1}{2}\) and requires the seed of the constructed strong PRG to be very long.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-642-11799-2_36
Chapter PDF
Similar content being viewed by others
Keywords
- Security Parameter
- Conditional Probability Distribution
- Cryptographic Primitive
- Oracle Query
- Output Length
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
Bennett, C.H., Brassard, G., Robert, J.-M.: Privacy amplification by public discussion. SIAM Journal on Computing 17(2), 210–229 (1988)
Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: FOCS 1982: Proceedings of the 23rd IEEE Annual Symposium on Foundations of Computer Science, pp. 112–117 (1982)
Dodis, Y., Impagliazzo, R., Jaiswal, R., Kabanets, V.: Security amplification for interactive cryptographic primitives. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 128–145. Springer, Heidelberg (2009)
Goldreich, O., Nisan, N., Wigderson, A.: On Yao’s XOR-lemma. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 2(50) (1995)
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 on Computing 28(4), 1364–1396 (1999)
Hoeffding, W.: Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58(301), 13–30 (1963)
Holenstein, T.: Key agreement from weak bit agreement. In: STOC 2005: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 664–673 (2005)
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.: Hard-core distributions for somewhat hard problems. In: FOCS 1995: Proceedings of the 36th IEEE Annual Symposium on Foundations of Computer Science, pp. 538–545 (1995)
Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions (extended abstracts). In: STOC 1989: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 12–24 (1989)
Kamp, J., Rao, A., Vadhan, S., Zuckerman, D.: Deterministic extractors for small-space sources. In: STOC 2006: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 691–700 (2006)
Maurer, U., Pietrzak, K., Renner, R.: Indistinguishability amplification. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 130–149. Springer, Heidelberg (2007)
Maurer, U., Tessaro, S.: Computational indistinguishability amplification: Tight product theorems for system composition. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 350–368. Springer, Heidelberg (2009)
Myers, S.: Efficient amplification of the security of weak pseudo-random function generators. Journal of Cryptology 16, 1–24 (2003)
Shaltiel, R.: Recent developments in explicit constructions of extractors. Bulletin of the EATCS 77, 67–95 (2002)
Yao, A.C.: Theory and applications of trapdoor functions. In: FOCS 1982: Proceedings of the 23rd IEEE Annual Symposium on Foundations of Computer Science, pp. 80–91 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Maurer, U., Tessaro, S. (2010). A Hardcore Lemma for Computational Indistinguishability: Security Amplification for Arbitrarily Weak PRGs with Optimal Stretch. In: Micciancio, D. (eds) Theory of Cryptography. TCC 2010. Lecture Notes in Computer Science, vol 5978. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11799-2_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-11799-2_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11798-5
Online ISBN: 978-3-642-11799-2
eBook Packages: Computer ScienceComputer Science (R0)