Paper 2017/734

Round Optimal Concurrent Non-Malleability from Polynomial Hardness

Dakshita Khurana


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
non-malleable commitmentspolynomialthree round
Contact author(s)
dakshita @ cs ucla edu
2017-08-01: received
Short URL
Creative Commons Attribution


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