Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / non-malleable commitments, polynomial, three round

Date: received 30 Jul 2017, last revised 31 Jul 2017

Contact author: dakshita at cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20170801:152007 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]