Four Round Secure Computation Without Setup
We construct a 4-round multi-party computation protocol in the plain model for any functionality, secure against a malicious adversary. Our protocol relies on the sub-exponential hardness of the Learning with Errors (LWE) problem with slightly super-polyn
- PDF / 1,562,335 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 104 Downloads / 212 Views
Weizmann Institute of Science, Rehovot, Israel [email protected] 2 IBM, Yorktown Heights, USA [email protected] 3 Cornell Tech, New York, USA [email protected]
Abstract. We construct a 4-round multi-party computation protocol in the plain model for any functionality, secure against a malicious adversary. Our protocol relies on the sub-exponential hardness of the Learning with Errors (LWE) problem with slightly super-polynomial noise ratio, and on the existence of adaptively secure commitments based on standard assumptions. Our round complexity matches a lower bound of Garg et al. (EUROCRYPT ’16), and outperforms the state of the art of 6 rounds based on similar assumptions to ours, and 5 rounds relying on indistinguishability obfuscation and other strong assumptions. To do this, we construct an LWE based multi-key FHE scheme with a very simple one-round distributed setup procedure (vs. the trusted setup required in previous LWE based constructions). This lets us construct the first 3-round semi-malicious MPC protocol without setup from standard LWE using the approach of Mukherjee and Wichs (EUROCRYPT ’16). Finally, subexponential hardness and adaptive commitments are used to “compile” the protocol into the fully malicious setting.
1
Introduction
Secure Multi-party Computation (MPC) allows mutually suspicious parties to evaluate a function on their joint private inputs without revealing these inputs to each other. One fruitful line of investigation is concerned with the round Z. Brakerski—Supported by the Israel Science Foundation (Grant No. 468/14) and Binational Science Foundation (Grants No. 2016726, 2014276) and ERC Project 756482 REACT. S. Halevi—Supported by the Defense Advanced Research Projects Agency (DARPA) and Army Research Office (ARO) under Contract No. W911NF-15-C-0236. A. Polychroniadou—Supported by the National Science Foundation under Grant No. 1617676, IBM under Agreement 4915013672, the Packard Foundation under Grant 2015-63124, and the Danish National Research Foundation and the National Science Foundation of China (under the grant 61361136003) for the Sino-Danish Center for the Theory of Interactive Computation. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the sponsors. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part I, LNCS 10677, pp. 645–677, 2017. https://doi.org/10.1007/978-3-319-70500-2_22
646
Z. Brakerski et al.
complexity of these protocols. More specifically, we consider a model where at each round, each party is allowed to broadcast a message to everyone else. We allow the adversary to be malicious and corrupt any fraction of the parties. If a Common Random String (CRS) is allowed, then two rounds are necessary and sufficient for secure multi-party protocols under plausible cryptographic assumptions [GGHR14,MW16]. Without relying on trusted setup, it was still known that constant round protocols are pos
Data Loading...
