Paper 2021/120

Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits

Aner Ben-Efraim, Kelong Cong, Eran Omri, Emmanuela Orsini, Nigel P. Smart, and Eduardo Soria-Vazquez


We present a secure multiparty computation (MPC) protocol based on garbled circuits which is both actively secure and supports the free-XOR technique, and which has communication complexity $O(n)$ per party. This improves on a protocol of Ben-Efraim, Lindell and Omri which only achieved passive security, without support for free-XOR. Our construction is based on a new variant of LPN-based encryption, but has the drawback of requiring a rather expensive garbling phase. To address this issue we present a second protocol that assumes at least $n/c$ of the parties are honest (for an arbitrary fixed value $c$). This second protocol allows for a significantly lighter preprocessing, at the cost of a small sacrifice in online efficiency. We demonstrate the practicality of our evaluation phase with a implementation.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2021
Contact author(s)
anermosh @ post bgu ac il
kelong cong @ esat kuleuven be
omrier @ gmail com
emmanuela orsini @ kuleuven be
nigel smart @ kuleuven be
eduardo @ cs au dk
2021-02-05: received
Short URL
Creative Commons Attribution


      author = {Aner Ben-Efraim and Kelong Cong and Eran Omri and Emmanuela Orsini and Nigel P.  Smart and Eduardo Soria-Vazquez},
      title = {Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2021/120},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.