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

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.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2022
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
2022-11-07: approved
2022-11-07: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.