Paper 2004/329

Hardness amplification of weakly verifiable puzzles

Ran Canetti, 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.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Appeared in the proceedings of TCC'05
Keywords
average-case hardnessCAPTCHAscomputationally-sound proofsinteractive proofsone-way functionssoundness errorweakly-verifiable puzzles
Contact author(s)
shaih @ alum mit edu
History
2004-11-29: revised
2004-11-27: received
See all versions
Short URL
https://ia.cr/2004/329
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/329,
      author = {Ran Canetti and Shai Halevi and Michael Steiner},
      title = {Hardness amplification of weakly verifiable puzzles},
      howpublished = {Cryptology ePrint Archive, Paper 2004/329},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/329}},
      url = {https://eprint.iacr.org/2004/329}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.