Round Optimal Concurrent Non-malleability from Polynomial Hardness
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 commit
- PDF / 765,176 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 78 Downloads / 190 Views
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 nonmalleable 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/N th residuosity. Our protocols also satisfy concurrent non-malleability.
1
Introduction
Non-malleable commitments are a fundamental primitive in cryptography, that help prevent man-in-the-middle attacks. A man-in-the-middle (MIM) adversary participates simultaneously in multiple protocol executions, using information obtained in one execution to breach security of the other execution. To counter such adversaries, the notion of non-malleable commitments was introduced in a seminal work of Dolev et al. [7]. From their inception, non-malleable commitments have been instrumental to building various several important 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. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 139–171, 2017. https://doi.org/10.1007/978-3-319-70503-3_5
140
D. Khurana
non-malleable protocols, including but not limited to non-malleable proof systems and round-efficient constructions of secure multi-party computation. A commitment scheme is a protocol between a committer C and receiver R, where the committer has an input message m. Both parties engage in an interactive probabilistic commitment protocol, and the receiver’s view at the end of this phase is denoted by com(m). Later in a opening phase, the committer and receiver interact again to generate a transcript, that allows the receiver to verify whether the message m was actually committed to, during the commit phase. A cryptographic commitment must be binding, that is, with high probab
Data Loading...
