Rafail Ostrovsky - Publications

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

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti


The round complexity of commitment scheme secure against main-in-the-middle attacks has been the focus of extensive research for about 25 years. The recent breakthrough of Goyal et al. [22] shoed 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. subexponetial-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.

comment: CRYPTO (3) 2016: 270-299

Fetch PDF file of the paper

Back to Publications List