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 nontrivial, 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 oneway functions/relations, weaklyverifiable 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 oneway function that no polytime attacker can break with probability $> \frac{1}{2}$, then the direct product provably amplifies hardness to some negligible probability. Naturally, we would expect that we can amplify hardness exponentially, all the way to $2^{n}$ probability, or at least to some fixed/known negligible such as $n^{\log n}$ in the security parameter $n$, just by taking sufficiently many instances of the weak primitive. Although it is known that such parameters cannot be proven via blackbox reductions, they may seem like reasonable conjectures, and, to the best of our knowledge, are widely believed to hold. In fact, a conjecture along these lines was introduced in a survey of Goldreich, Nisan and Wigderson (ECCC '95). In this work, we show that such conjectures are false by providing simple but surprising counterexamples. In particular, we construct weakly secure signatures and oneway functions, for which standard hardness amplification results are known to hold, but for which hardness does not amplify beyond just negligible. That is, for any negligible function $\eps(n)$, we instantiate these primitives so that the direct product can always be broken with probability $\eps(n)$, no matter how many copies we take.
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
 20120129: revised
 20120129: 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}, note = {\url{https://eprint.iacr.org/2012/032}}, url = {https://eprint.iacr.org/2012/032} }