Chernoff-Type Direct Product Theorems Export

@article{citeulike:3616421, abstract = {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.}, author = {Impagliazzo, Russell and Jaiswal, Ragesh and Kabanets, Valentine}, citeulike-article-id = {3616421}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/s00145-008-9029-7}, citeulike-linkout-1 = {http://www.springerlink.com/content/tn1708k537347j0x}, doi = {10.1007/s00145-008-9029-7}, journal = {Journal of Cryptology}, keywords = {captcha}, posted-at = {2009-08-26 05:41:14}, priority = {2}, title = {Chernoff-Type Direct Product Theorems}, url = {http://dx.doi.org/10.1007/s00145-008-9029-7} }

TY - JOUR ID - citeulike:3616421 L3 - citeulike-article-id:3616421 N2 - 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. JF - Journal of Cryptology TI - Chernoff-Type Direct Product Theorems KW - captcha AU - Impagliazzo, Russell AU - Jaiswal, Ragesh AU - Kabanets, Valentine UR - http://dx.doi.org/10.1007/s00145-008-9029-7 ER -