Recently, Pass in [TCC 2013] proved a lower bound of 3 rounds when security is proven through black-box reductions to falsifiable assumptions. On the other side, positive results of Goyal [STOC 2011], Lin and Pass [STOC 2011] and Goyal et al. [FOCS 2012] showed that one-way functions are sufficient with a constant (at least 6) number of rounds. More recently Ciampi et al. [CRYPTO 2016] showed that subexponentially strong one-way permutations are sufficient with just 3 rounds.
In this work we almost close the above open question by showing a 4-round concurrent non-malleable commitment scheme that only needs one-way functions. Our main technique consists in showing how to upgrade basic forms of non-malleability (i.e., non-malleability w.r.t. non-aborting adversaries) to full-fledged non-malleability without penalizing the round complexity.
Category / Keywords: non-malleability, delayed-input protocols Date: received 14 Jun 2016, last revised 14 Sep 2016 Contact author: ivan visconti at gmail com Available format(s): PDF | BibTeX Citation Note: The last revisions fixed some typos and extended the comparison with the state of the art. Version: 20160915:005511 (All versions of this report) Short URL: ia.cr/2016/621 Discussion forum: Show discussion | Start new discussion