Paper 2021/833

ATLAS: Efficient and Scalable MPC in the Honest Majority Setting

Vipul Goyal, Hanjun Li, Rafail Ostrovsky, Antigoni Polychroniadou, and Yifan Song


In this work, we address communication, computation, and round efficiency of unconditionally secure multi-party computation for arithmetic circuits in the honest majority setting. We achieve both algorithmic and practical improvements: -- The best known result in the semi-honest setting has been due to Damgard and Nielsen (CRYPTO 2007). Over the last decade, their construction has played an important role in the progress of efficient secure computation. However despite a number of follow-up works, any significant improvements to the basic semi-honest protocol have been hard to come by. We show 33% improvement in communication complexity of this protocol. We show how to generalize this result to the malicious setting, leading to the best known unconditional honest majority MPC with malicious security. -- We focus on the round complexity of the Damgard and Nielsen protocol and improve it by a factor of 2. Our improvement relies on a novel observation relating to an interplay between Damgard and Nielsen multiplication and Beaver triple multiplication. An implementation of our constructions shows an execution run time improvement compared to the state of the art ranging from 30% to 50%.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2021
Multiparty ComputationInformation-theoretic CryptographyCommunication Complexity
Contact author(s)
goyal @ cs cmu edu
lihanjun1212 @ gmail com
rafail @ cs ucla edu
antigonipoly @ gmail com
yifans2 @ andrew cmu edu
2021-06-21: received
Short URL
Creative Commons Attribution


      author = {Vipul Goyal and Hanjun Li and Rafail Ostrovsky and Antigoni Polychroniadou and Yifan Song},
      title = {{ATLAS}: Efficient and Scalable {MPC} in the Honest Majority Setting},
      howpublished = {Cryptology ePrint Archive, Paper 2021/833},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.