International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Direct Product Hardness Amplification

David Lanzenberger
Ueli Maurer
DOI: 10.1007/978-3-030-90453-1_21
Search ePrint
Search Google
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.
Video from TCC 2021
  title={Direct Product Hardness Amplification},
  booktitle={Theory of Cryptography;19th International Conference},
  author={David Lanzenberger and Ueli Maurer},