TY - GEN
T1 - Promise zero knowledge and its applications to round optimal MPC
AU - Badrinarayanan, Saikrishna
AU - Goyal, Vipul
AU - Jain, Abhishek
AU - Kalai, Yael Tauman
AU - Khurana, Dakshita
AU - Sahai, Amit
N1 - S. Badrinarayanan, D. Khurana and A. Sahai—Research supported in part from a DARPA/ARL SAFEWARE award, NSF Frontier Award 1413955, NSF grants 1619348, 1228984, 1136174, and 1065276, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, an equipment grant from Intel, and an Okawa Foundation Research Grant. 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. Fifth author’s research also supported by the UCLA Dissertation Year Fellowship. V. Goyal—Work supported in part by a grant from Northrop Grumman. A. Jain—Supported in part by a DARPA/ARL Safeware Grant W911NF-15-C-0213, and a subaward from NSF CNS-1414023.
PY - 2018
Y1 - 2018
N2 - We devise a new partitioned simulation technique for MPC where the simulator uses different strategies for simulating the view of aborting adversaries and non-aborting adversaries. The protagonist of this technique is a new notion of promise zero knowledge (ZK) where the ZK property only holds against non-aborting verifiers. We show how to realize promise ZK in three rounds in the simultaneous-message model assuming polynomially hard DDH (or QR or N (formula presented) -Residuosity). We demonstrate the following applications of our new technique: We construct the first round-optimal (i.e., four round) MPC protocol for general functions based on polynomially hard DDH (or QR or N (formula presented) -Residuosity).We further show how to overcome the four-round barrier for MPC by constructing a three-round protocol for “list coin-tossing” – a slight relaxation of coin-tossing that suffices for most conceivable applications – based on polynomially hard DDH (or QR or N (formula presented) -Residuosity). This result generalizes to randomized input-less functionalities. Previously, four round MPC protocols required sub-exponential-time hardness assumptions and no multi-party three-round protocols were known for any relaxed security notions with polynomial-time simulation against malicious adversaries. In order to base security on polynomial-time standard assumptions, we also rely upon a leveled rewinding security technique that can be viewed as a polynomial-time alternative to leveled complexity leveraging for achieving “non-malleability” across different primitives.
AB - We devise a new partitioned simulation technique for MPC where the simulator uses different strategies for simulating the view of aborting adversaries and non-aborting adversaries. The protagonist of this technique is a new notion of promise zero knowledge (ZK) where the ZK property only holds against non-aborting verifiers. We show how to realize promise ZK in three rounds in the simultaneous-message model assuming polynomially hard DDH (or QR or N (formula presented) -Residuosity). We demonstrate the following applications of our new technique: We construct the first round-optimal (i.e., four round) MPC protocol for general functions based on polynomially hard DDH (or QR or N (formula presented) -Residuosity).We further show how to overcome the four-round barrier for MPC by constructing a three-round protocol for “list coin-tossing” – a slight relaxation of coin-tossing that suffices for most conceivable applications – based on polynomially hard DDH (or QR or N (formula presented) -Residuosity). This result generalizes to randomized input-less functionalities. Previously, four round MPC protocols required sub-exponential-time hardness assumptions and no multi-party three-round protocols were known for any relaxed security notions with polynomial-time simulation against malicious adversaries. In order to base security on polynomial-time standard assumptions, we also rely upon a leveled rewinding security technique that can be viewed as a polynomial-time alternative to leveled complexity leveraging for achieving “non-malleability” across different primitives.
UR - http://www.scopus.com/inward/record.url?scp=85052378174&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052378174&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-96881-0_16
DO - 10.1007/978-3-319-96881-0_16
M3 - Conference contribution
AN - SCOPUS:85052378174
SN - 9783319968803
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 459
EP - 487
BT - Advances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings
A2 - Boldyreva, Alexandra
A2 - Shacham, Hovav
PB - Springer
T2 - 38th Annual International Cryptology Conference, CRYPTO 2018
Y2 - 19 August 2018 through 23 August 2018
ER -