Welcome to the resource topic for 2004/329
Title:
Hardness amplification of weakly verifiable puzzles
Authors: Ran Canetti, Shai Halevi, 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.
ePrint: https://eprint.iacr.org/2004/329
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .