Consider a challenge-response protocol, where a legitimate user should have probability at least $\alpha$ of responding correctly, whereas an attacker has probability at most $\beta < \alpha$ of responding correctly. 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 a zero-knowledge 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, where the threshold is chosen between $\alpha$ and $\beta$. 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 correctly to the probability of failure for a single instance.
This is joint work with Russell Impagliazzo (UCSD) and Ragesh Jaiswal (UCSD), to appear in CRYPTO'07.
Valentine Kabanets obtained his PhD from the University of Toronto under the supervision of Stephen Cook. He then was a postdoc at the Institute for Advanced Study (Princeton) and the Univesity of California, San Diego. Currently he is a faculty member at Simon Fraser University (Vancouver, Canada). His main research interests are in computational complexity theory, especially the role of randomness in computation.