Four-Round Black-Box Non-Malleable Commitments from One-Way Permutations

Michele Ciampi; Emmanuela Orsini; Luisa Siniscalchi

Paper 2022/1543

Four-Round Black-Box Non-Malleable Commitments from One-Way Permutations

Michele Ciampi

, University of Edinburgh

Emmanuela Orsini

, KU Leuven

Luisa Siniscalchi

Abstract

We construct the first four-round non-malleable commitment scheme based solely on the black-box use of one-to-one one-way functions. Prior to our work, all non-malleable commitment schemes based on black-box use of polynomial-time cryptographic primitives require more than $16$ rounds of interaction. A key tool for our construction is a proof system that satisfies a new definition of security that we call non-malleable zero-knowledge with respect to commitments. In a nutshell, such a proof system can be safely run in parallel with a (potentially interactive) commitment scheme. We provide an instantiation of this tool using the MPC-in-the-Head approach in combination with BMR.

Note: More details on formal protocols description and full proofs added.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in TCC 2022
Keywords: non-malleable commitments zero-knowledge BMR MPC-in-the-head
Contact author(s): michele ciampi @ ed ac uk
emmanuela orsini @ kuleuven be
luisa siniscalchi88 @ gmail com
History: 2022-11-07: approved; 2022-11-07: received; See all versions
Short URL: https://ia.cr/2022/1543
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1543,
      author = {Michele Ciampi and Emmanuela Orsini and Luisa Siniscalchi},
      title = {Four-Round Black-Box Non-Malleable Commitments from One-Way Permutations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1543},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1543}
}