Abstract
Consider a challenge-response protocol where the probability of a correct response is at least α for a legitimate user and at most β<α for an attacker. One example is a CAPTCHA challenge, where a human should have a significantly higher chance of answering a single challenge (e.g., uncovering a distorted letter) than an attacker; another example is an argument system without perfect completeness. A natural approach to boost the gap between legitimate users and attackers is to issue many challenges and accept if the response is correct for more than a threshold fraction, for the threshold chosen between α and β. We give the first proof that parallel repetition with thresholds improves the security of such protocols. We do this with a very general result about an attacker’s ability to solve a large fraction of many independent instances of a hard problem, showing a Chernoff-like convergence of the fraction solved incorrectly to the probability of failure for a single instance.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Bellare, R. Impagliazzo, M. Naor, Does parallel repetition lower the error in computationally sound protocols? In Proceedings of the Thirty-Eighth Annual IEEE Symposium on Foundations of Computer Science (1997), pp. 374–383
R. Canetti, S. Halevi, M. Steiner, Hardness amplification of weakly verifiable puzzles, in Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, pp. 17–33
O. Goldreich, N. Nisan, A. Wigderson, On Yao’s XOR-Lemma. Electronic colloquium on computational complexity, TR95-050 (1995)
T. Holenstein, Key agreement from weak bit agreement, in Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (2005), pp. 664–673
R. Impagliazzo, R. Jaiswal, V. Kabanets, Approximately list-decoding direct product codes and uniform hardness amplification, in Proceedings of the Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science (2006), pp. 187–196
R. Impagliazzo, R. Jaiswal, V. Kabanets, Chernoff-type direct product theorems, in Advances in Cryptology—CRYPTO 2007, Twenty-Seventh Annual International Cryptology Conference (2007), pp. 500–516
R. Impagliazzo, R. Jaiswal, V. Kabanets, A. Wigderson, Uniform direct-product theorems: Simplified, optimized, and derandomized, in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (2008), pp. 579–588
R. Impagliazzo, A. Wigderson, P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma, in Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (1997), pp. 220–229
R. Pass, M. Venkitasubramaniam, An efficient parallel repetition theorem for Arthur–Merlin games, in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (2007), pp. 420–429
K. Pietrzak, D. Wikstrom, Parallel repetition of computationally sound protocols revisited, in Theory of Cryptography, Fourth Theory of Cryptography Conference, TCC 2007, pp. 86–102
L. von Ahn, M. Blum, N.J. Hopper, J. Langford, CAPTCHA: Using hard AI problems for security, in Advances in Cryptology—EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques (2003), pp. 294–311
A.C. Yao, Theory and applications of trapdoor functions, in Proceedings of the Twenty-Third Annual IEEE Symposium on Foundations of Computer Science (1982), pp. 80–91
Author information
Authors and Affiliations
Corresponding author
Additional information
Russell Impagliazzo: Research partially supported by NSF Awards CCR-0515332 and CNS-0716790. Views expressed are not endorsed by the NSF.
Ragesh Jaiswal: Research partially supported by NSF Awards CCR-0515332, CCF-0634909, CNS-0524765 and CNS-0716790. Views expressed are not endorsed by the NSF.
Rights and permissions
About this article
Cite this article
Impagliazzo, R., Jaiswal, R. & Kabanets, V. Chernoff-Type Direct Product Theorems. J Cryptol 22, 75–92 (2009). https://doi.org/10.1007/s00145-008-9029-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-008-9029-7