We give new proofs for the hardness amplifcation of efficiently samplable predicates and of
weakly verifable puzzles. More concretely, in the first part of the paper, we give a new proof of
Yao's XOR-Lemma as well as related theorems in the cryptographic setting. Our proof seems
simpler than previous ones, yet immediately generalizes to statements similar in spirit such as
the extraction lemma used to obtain pseudo-random generators from one-way functions [Hastad,
Impagliazzo, Levin, Luby, SIAM J. on Comp. 1999].

In the second part of the paper, we give a new proof of hardness amplifcation for weakly
verifable puzzles, which is more general than previous ones in that it gives the right bounds for
arbitrary monotone function applied to the checking circuit of the underlying puzzle.

Both our proofs are applicable in many settings of interactive cryptographic protocols because they satisfy a property that we call \non-rewinding". In particular, we show that any
weak cryptographic protocol whose security is given by the unpredictability of single bits can
be strengthened with a natural information theoretic protocol. As an example, we show how
these theorems solve the main open question from [Halevi and Rabin, TCC2008] concerning bit
commitment.

###
Versions

- Full Version [arXiv]
- In Proceedings of
* The 8th Theory of Cryptography Conference* TCC '11 [paywall]

[
back to Grant's homepage]