TY - GEN
T1 - Round optimal concurrent non-malleability from polynomial hardness
AU - Khurana, Dakshita
N1 - The full version of this paper is available at http://eprint.iacr.org/2017/734. Research supported in part by the UCLA Dissertation Year Fellowship 2017–18. Research also supported in part from a DARPA/ARL SAFEWARE award, NSF Frontier Award 1413955, NSF grants 1619348, 1228984, 1136174, and 1065276, BSF grant 2012378. This material is based upon work supported by the Defense Advanced Research Projects Agency through the ARL under Contract W911NF-15-C-0205. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, or the U.S. Government.
PY - 2017
Y1 - 2017
N2 - 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 ZAPs, as well as one out of DDH/QR/ Nth residuosity. Our protocols also satisfy concurrent non-malleability.
AB - 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 ZAPs, as well as one out of DDH/QR/ Nth residuosity. Our protocols also satisfy concurrent non-malleability.
UR - https://www.scopus.com/pages/publications/85033791200
UR - https://www.scopus.com/pages/publications/85033791200#tab=citedBy
U2 - 10.1007/978-3-319-70503-3_5
DO - 10.1007/978-3-319-70503-3_5
M3 - Conference contribution
AN - SCOPUS:85033791200
SN - 9783319705026
T3 - Lecture Notes in Computer Science
SP - 139
EP - 171
BT - Theory of Cryptography - 15th International Conference, TCC 2017, Proceedings
A2 - Kalai, Yael
A2 - Reyzin, Leonid
PB - Springer
T2 - 15th International Conference on Theory of Cryptography, TCC 2017
Y2 - 12 November 2017 through 15 November 2017
ER -