Rafail Ostrovsky - Publications

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

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti


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]shoed 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 sub exponentially 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-manysimulation-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 out work. comment: CRYPTO (2) 2017: 127-157

Fetch PDF file of the paper

Back to Publications List