Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Hardness Amplification, Direct Product Theorem

Original Publication (with minor differences): IACR-TCC-2021

Date: received 17 Sep 2021, last revised 20 Sep 2021

Contact author: landavid at inf ethz ch

Available format(s): PDF | BibTeX Citation

Version: 20210920:135257 (All versions of this report)

Short URL: ia.cr/2021/1229


[ Cryptology ePrint archive ]