Type of Talk: UTCS Colloquium

Speaker/Affi

liation: Russell Impagliazzo UC San Diego

Date/Time: Monday Augu

st 20 2007 11:00 a.m.

Location: ACES 6.304 (Please Note New Room

Number)

Host: David Zuckerman

Talk Title: A Chernoff-style

Direct Product Theorem

Talk Abstract:
Consider a challenge-re

sponse protocol where
the probability of a correct response is at least

p
for a legitimate user and at most q < p for an attacker.
One exa

mple is a CAPTCHA challenge where a human
should have a significantly

higher chance of answering
a single challenge (e.g. uncovering a disto

rted letter)
than an attacker. Another example would be an argument

system without perfect completeness. A natural approach
to boost the ga

p between legitimate users and attackers
would be to issue many challen

ges and accept if the response
is correct for more than a threshold fr

action for a threshold
chosen between p and q. We give the first proof
that parallel
repetition with thresholds improves the security of such<

br>protocols. We do this with a very general result about an
attacker''s
ability to solve a larger than expected fraction
of many independent in

stances of a hard problem. We show
a Chernoff-like convergence of the fr

action solved incorrectly
to the probability of failure for a single ins

tance.