Paper 2016/621

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

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, and Ivan Visconti

Abstract

How many rounds and which computational assumptions are needed for concurrent non-malleable commitments? The above question has puzzled researchers for several years. 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.

Note: The last revisions fixed some typos and extended the comparison with the state of the art.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
non-malleabilitydelayed-input protocols
Contact author(s)
ivan visconti @ gmail com
History
2016-09-15: last of 6 revisions
2016-06-17: received
See all versions
Short URL
https://ia.cr/2016/621
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/621,
      author = {Michele Ciampi and Rafail Ostrovsky and Luisa Siniscalchi and Ivan Visconti},
      title = {4-Round Concurrent Non-Malleable Commitments from One-Way Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/621},
      year = {2016},
      url = {https://eprint.iacr.org/2016/621}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.