International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Black-Box Non-Interactive Non-Malleable Commitments

Rachit Garg , UT Austin
Dakshita Khurana , UIUC
George Lu , UT Austin
Brent Waters , UT Austin and NTT Research
DOI: 10.1007/978-3-030-77883-5_6 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
Abstract: There has been recent exciting progress in building non-interactive non-malleable commitments from judicious assumptions. All proposed approaches proceed in two steps. First, obtain simple “base” commitment schemes for very small tag/identity spaces based on a various sub-exponential hardness assumptions. Next, assuming sub-exponential non-interactive witness indistinguishable proofs (NIWIs), and variants of keyless collision-resistant hash functions, construct non-interactive compilers that convert tag-based non-malleable commitments for a small tag space into tag-based non-malleable commitments for a larger tag space. We propose the first black-box construction of non-interactive non-malleable commitments. Our key technical contribution is a novel implementation of the non-interactive proof of consistency required for tag amplification. Prior to our work, the only known approach to tag amplification without setup and with black-box use of the base scheme (Goyal, Lee, Ostrovsky, and Visconti, FOCS 2012) added multiple rounds of interaction. Our construction satisfies the strongest known definition of non-malleability, i.e., CCA (chosen commitment attack) security. In addition to being black-box, our approach dispenses with the need for sub-exponential NIWIs, that was common to all prior work. Instead of NIWIs, we rely on sub-exponential hinting PRGs which can be obtained based on a broad set of assumptions such as sub-exponential CDH or LWE.
Video from EUROCRYPT 2021
  title={Black-Box Non-Interactive Non-Malleable Commitments},
  author={Rachit Garg and Dakshita Khurana and George Lu and Brent Waters},