You are looking at a specific version 20180426:050642 of this paper. See the latest version.

Paper 2017/1088

Promise Zero Knowledge and its Applications to Round Optimal MPC

Saikrishna Badrinarayanan and Vipul Goyal and Abhishek Jain and Yael Tauman Kalai and Dakshita Khurana and Amit Sahai

Abstract

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^{th}-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^{th}-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^{th}-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.

Note: Improved assumptions and simplified analysis.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Zero knowledgeMPCCoin Tossing
Contact author(s)
saikrishna at cs ucla edu
History
2018-04-26: last of 5 revisions
2017-11-10: received
See all versions
Short URL
https://ia.cr/2017/1088
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.