Paper 2012/032
Counterexamples to Hardness Amplification Beyond Negligible
Yevgeniy Dodis, Abhishek Jain, Tal Moran, and Daniel Wichs
Abstract
If we have a problem that is mildly hard, can we create a problem that is significantly harder? A natural approach to hardness amplification is the ``direct product''; instead of asking an attacker to solve a single instance of a problem, we ask the attacker to solve several independently generated ones. Interestingly, proving that the direct product amplifies hardness is often highly non-trivial, and in some cases may be false. For example, it is known that the direct product (i.e. ``parallel repetition'') of general interactive games may not amplify hardness at all. On the other hand, positive results show that the direct product does amplify hardness for many basic primitives such as one-way functions/relations, weakly-verifiable puzzles, and signatures.
Even when positive direct product theorems are shown to hold for some primitive, the parameters are surprisingly weaker than what we may have expected. For example, if we start with a weak one-way function that no poly-time attacker can break with probability
Note: This is a full version of a TCC 2012 paper. It includes all proofs and appendices.
Metadata
- Available format(s)
-
PDF PS
- Category
- Foundations
- Publication info
- Published elsewhere. TCC 2012
- Keywords
- hardness amplificationdirect product
- Contact author(s)
- wichs @ cs nyu edu
- History
- 2012-01-29: revised
- 2012-01-29: received
- See all versions
- Short URL
- https://ia.cr/2012/032
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2012/032, author = {Yevgeniy Dodis and Abhishek Jain and Tal Moran and Daniel Wichs}, title = {Counterexamples to Hardness Amplification Beyond Negligible}, howpublished = {Cryptology {ePrint} Archive, Paper 2012/032}, year = {2012}, url = {https://eprint.iacr.org/2012/032} }