CryptoDB
Hardness amplification of weakly verifiable puzzles
Authors: |
- Ran Canetti
- Shai Halevi
- Michael Steiner
|
Download: |
- URL: http://eprint.iacr.org/2004/329
- Search ePrint
- Search Google
|
Abstract: |
Is it harder to solve many puzzles than it is to solve just one? This
question has different answers, depending on how you define puzzles.
For the case of inverting one-way functions it was shown by Yao that
solving many independent instances simultaneously is indeed harder
than solving a single instance (cf. the transformation from weak to
strong one-way functions). The known proofs of that result, however,
use in an essential way the fact that for one-way functions, verifying
candidate solutions to a given puzzle is easy. We extend this result
to the case where solutions are efficiently verifiable only by
the party that generated the puzzle. We call such puzzles weakly
verifiable. That is, for weakly verifiable puzzles we show that if no
efficient algorithm can solve a single puzzle with probability more
than $\eps$, then no efficient algorithm can solve $n$ independent
puzzles simultaneously with probability more than $\eps^n$. We also
demonstrate that when the puzzles are not even weakly verifiable,
solving many puzzles may be no harder than solving a single one.
Hardness amplification of weakly verifiable puzzles turns out to be
closely related to the reduction of soundness error under parallel
repetition in computationally sound arguments. Indeed, the proof of
Bellare, Impagliazzo and Naor that parallel repetition reduces
soundness error in three-round argument systems implies a result
similar to our first result, albeit with considerably worse
parameters. Also, our second result is an adaptation of their proof
that parallel repetition of four-round systems may not reduce the
soundness error.
|
BibTeX
@misc{eprint-2004-12293,
title={Hardness amplification of weakly verifiable puzzles},
booktitle={IACR Eprint archive},
keywords={foundations / average-case hardness, CAPTCHAs, computationally-sound proofs, interactive proofs, one-way functions, soundness error, weakly-verifiable puzzles},
url={http://eprint.iacr.org/2004/329},
note={Appeared in the proceedings of TCC'05 shaih@alum.mit.edu 12751 received 26 Nov 2004, last revised 29 Nov 2004},
author={Ran Canetti and Shai Halevi and Michael Steiner},
year=2004
}