Paper 2021/1229
Direct Product Hardness Amplification
David Lanzenberger and Ueli Maurer
Abstract
We revisit one of the most fundamental hardness amplification constructions, originally proposed by Yao (FOCS 1982). We present a hardness amplification theorem for the direct product of certain games that is simpler, more general, and stronger than previously known hardness amplification theorems of the same kind. Our focus is two-fold. First, we aim to provide close-to-optimal concrete bounds, as opposed to asymptotic ones. Second, in the spirit of abstraction and reusability, our goal is to capture the essence of direct product hardness amplification as generally as possible. Furthermore, we demonstrate how our amplification theorem can be applied to obtain hardness amplification results for non-trivial interactive cryptographic games such as MAC forgery or signature forgery games.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in TCC 2021
- Keywords
- Hardness AmplificationDirect Product Theorem
- Contact author(s)
- landavid @ inf ethz ch
- History
- 2021-09-20: revised
- 2021-09-20: received
- See all versions
- Short URL
- https://ia.cr/2021/1229
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1229,
author = {David Lanzenberger and Ueli Maurer},
title = {Direct Product Hardness Amplification},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/1229},
year = {2021},
url = {https://eprint.iacr.org/2021/1229}
}
