Concurrent Non-Malleable Commitments (and More) in 3 Rounds

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti

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


The round complexity of commitment schemes secure against man-in-the-middle attacks has been the focus of extensive research for about 25 years. The recent breakthrough of Goyal et al. [22] showed that 3 rounds are sufficient for (one-left, one-right) non-malleable commitments. This result matches a lower bound of [41]. The state of affairs leaves still open the intriguing problem of constructing 3-round concurrent non-malleable commitment schemes.

In this paper we solve the above open problem by showing how to transform any 3-round (one-left one-right) non-malleable commitment scheme (with some extractability property) in a 3-round concurrent non-malleable commitment scheme. Our transform makes use of complexity leveraging and when instantiated with the construction of [22] gives a 3-round concurrent non-malleable commitment scheme from one-way permutations secure w.r.t. subexponential-time adversaries.

We also show a 3-round arguments of knowledge and a 3-round identification scheme secure against concurrent man-in-the-middle attacks.
Original languageEnglish
Title of host publicationAdvances in Cryptology -- CRYPTO 2016
EditorsMatthew Robshaw, Jonathan Katz
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages30
ISBN (Electronic)978-3-662-53015-3
ISBN (Print)978-3-662-53014-6
Publication statusPublished - 21 Jul 2016
Event36th Annual International Cryptology Conference - University of California, Santa Barbara, United States
Duration: 14 Aug 201618 Aug 2016

Publication series

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


Conference36th Annual International Cryptology Conference
Abbreviated titleCRYPTO 2016
Country/TerritoryUnited States
CitySanta Barbara
Internet address

Cite this