Paper 2017/734

Round Optimal Concurrent Non-Malleability from Polynomial Hardness

Dakshita Khurana

Abstract

Non-malleable commitments are a central cryptographic primitive that guarantee security against man-in-the-middle adversaries, and their exact round complexity has been a subject of great interest. Pass (TCC 2013, CC 2016) proved that non-malleable commitments with respect to commitment are impossible to construct in less than three rounds, via black-box reductions to polynomial hardness assumptions. Obtaining a matching positive result has remained an open problem so far. While three-round constructions of non-malleable commitments have been achieved, beginning with the work of Goyal, Pandey and Richelson (STOC 2016), current constructions require super-polynomial assumptions. In this work, we settle the question of whether three-round non-malleable commitments can be based on polynomial hardness assumptions. We give constructions based on polynomial hardness of Decisional Diffie-Hellman assumption or Quadratic Residuosity or Nth Residuosity, together with ZAPs. Our protocols also satisfy concurrent non-malleability.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
non-malleable commitmentspolynomialthree round
Contact author(s)
dakshita @ cs ucla edu
History
2017-08-01: received
Short URL
https://ia.cr/2017/734
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/734,
      author = {Dakshita Khurana},
      title = {Round Optimal Concurrent Non-Malleability from Polynomial Hardness},
      howpublished = {Cryptology ePrint Archive, Paper 2017/734},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/734}},
      url = {https://eprint.iacr.org/2017/734}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.