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 \alpha for a legitimate user, and at most
\beta < \alpha 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 \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 incorrectly to the probability of failure for a single
instance.
Versions