Cryptology ePrint Archive: Report 2017/386

Four Round Secure Computation without Setup

Zvika Brakerski and Shai Halevi and Antigoni Polychroniadou

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. 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 \emph{distributed setup procedure} (vs. the trusted setup required in previous LWE based constructions). This lets us construct a 3-round semi-malicious protocol without setup 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.

Category / Keywords: foundations / LWE, Multikey FHE, MPC, Round efficiency

Date: received 2 May 2017, last revised 25 May 2017

Contact author: antigonipoly at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170525:065740 (All versions of this report)

Short URL: ia.cr/2017/386

Discussion forum: Show discussion | Start new discussion