Chernoff-type direct product theorems
Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets
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 would be an argument system without perfect completeness. A natural approach to boost the gap between legitimate users and attackers would be 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.
Versions
- journal version in Journal of Cryptology 22(1):75-92, 2009.
- extended abstract in Advances in Cryptology - Proceedings of CRYPTO'07, pages 500-516, 2007.