[Resource Topic] 2017/734: Round Optimal Concurrent Non-Malleability from Polynomial Hardness

Welcome to the resource topic for 2017/734

Round Optimal Concurrent Non-Malleability from Polynomial Hardness

Authors: 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.

ePrint: https://eprint.iacr.org/2017/734

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .