Black-Box Non-interactive Non-malleable Commitments

Rachit Garg, Dakshita Khurana, George Lu, Brent Waters

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

There has been recent exciting progress on 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsAnne Canteaut, François-Xavier Standaert
PublisherSpringer
Pages159-185
Number of pages27
ISBN (Print)9783030778828
DOIs
StatePublished - 2021
Event40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2021 - Zagreb, Croatia
Duration: Oct 17 2021Oct 21 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12698 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2021
Country/TerritoryCroatia
CityZagreb
Period10/17/2110/21/21

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Black-Box Non-interactive Non-malleable Commitments'. Together they form a unique fingerprint.

Cite this