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
-
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},
url = {https://eprint.iacr.org/2017/734}
}
