Four-Round Concurrent Non-Malleable Commitments from One-Way Functions

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti

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


How many rounds and which assumptions are required for concurrent non-malleable commitments? The above question has puzzled researchers for several years. Pass in [TCC 2013] showed a lower bound of 3 rounds for the case of black-box reductions to falsifiable hardness assumptions with respect to polynomial-time adversaries. On the other side, Goyal [STOC 2011], Lin and Pass [STOC 2011] and Goyal et al. [FOCS 2012] showed that one-way functions (OWFs) are sufficient with a constant number of rounds. More recently Ciampi et al. [CRYPTO 2016] showed a 3-round construction based on subexponentially strong one-way permutations.

In this work we show as main result the first 4-round concurrent non-malleable commitment scheme assuming the existence of any one-way function.

Our approach builds on a new security notion for argument systems against man-in-the-middle attacks: Simulation-Witness-Independence. We show how to construct a 4-round one-many simulation-witnesses-independent argument system from one-way functions. We then combine this new tool in parallel with a weak form of non-malleable commitments constructed by Goyal et al. in [FOCS 2014] obtaining the main result of our work.
Original languageEnglish
Title of host publicationAdvances in Cryptology -- CRYPTO 2017
EditorsJonathan Katz, Hovav Shacham
Place of PublicationCham
PublisherSpringer International Publishing AG
Number of pages31
ISBN (Electronic)978-3-319-63715-0
ISBN (Print)978-3-319-63714-3
Publication statusPublished - 29 Jul 2017
EventCRYPTO 2017: 37th Annual International Cryptology Conference - University of California, Santa Barbara, Santa Barbara, United States
Duration: 20 Aug 201624 Aug 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Cham
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceCRYPTO 2017
Abbreviated titleCRYPTO 2017
CountryUnited States
CitySanta Barbara
Internet address


Dive into the research topics of 'Four-Round Concurrent Non-Malleable Commitments from One-Way Functions'. Together they form a unique fingerprint.

Cite this