**Hardness amplification of weakly verifiable puzzles**

*Ran Canetti and Shai Halevi and Michael Steiner*

**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.

**Category / Keywords: **foundations / average-case hardness, CAPTCHAs, computationally-sound proofs, interactive proofs, one-way functions, soundness error, weakly-verifiable puzzles

**Publication Info: **Appeared in the proceedings of TCC'05

**Date: **received 26 Nov 2004, last revised 29 Nov 2004

**Contact author: **shaih at alum mit edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20041129:204407 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]