Speaker: Valentine Kabanets Simon Fraser University
Time: 2007-05-15 14:00-2007-05-15 15:00
Venue: FIT Building 4-603, Tsinghua University

Abstract:

    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.
 

Short Bio:

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.