Black-Box Non-Interactive Non-Malleable Commitments

Rachit Garg, Dakshita Khurana, George Lu, and Brent Waters

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 way of implementing the non-interactive proof of consistency required by the tag amplification process. 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.

Note: Revised version with a weaker notion of binding. Fixed an issue with the old version by having better compatibility with the existing scheme of LPS17.

Metadata
Available format(s)
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2021
Keywords
non malleable commitmentsnon-interactive
Contact author(s)
rachit0596 @ gmail com
dakshkhurana @ gmail com
georgelu97 @ gmail com
bwaters @ cs utexas edu
History
2021-08-26: last of 2 revisions
2020-10-06: received
See all versions
Short URL
https://ia.cr/2020/1197
License

CC BY

BibTeX

@misc{cryptoeprint:2020/1197,
author = {Rachit Garg and Dakshita Khurana and George Lu and Brent Waters},
title = {Black-Box Non-Interactive Non-Malleable Commitments},
howpublished = {Cryptology ePrint Archive, Paper 2020/1197},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1197}},
url = {https://eprint.iacr.org/2020/1197}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.