Paper 2017/386

Four Round Secure Computation without Setup

Zvika Brakerski, Shai Halevi, and Antigoni Polychroniadou


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. Lin, Pass and Soni (FOCS '17) provide an adaptively secure commitment scheme from Time-Lock Puzzles. 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.

Note: The instantiation of the adaptive commitment is no longer based on the scheme of Pandey, Pass, and Vaikuntanathan (CRYPTO'08) albeit under a non-standard assumption. Instead, it is based on the commitment scheme of Lin, Pass and Soni (FOCS'17).

Available format(s)
Publication info
Preprint. MINOR revision.
LWEMultikey FHEMPCRound efficiency
Contact author(s)
antigonipoly @ gmail com
2018-03-10: last of 2 revisions
2017-05-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zvika Brakerski and Shai Halevi and Antigoni Polychroniadou},
      title = {Four Round Secure Computation without Setup},
      howpublished = {Cryptology ePrint Archive, Paper 2017/386},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.