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

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

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

Abstract

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.

Metadata

Available format(s): PDF
Category: 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
History: 2021-02-05: received
Short URL: https://ia.cr/2021/120
License: CC BY

BibTeX

@misc{cryptoeprint:2021/120,
      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{https://eprint.iacr.org/2021/120}},
      url = {https://eprint.iacr.org/2021/120}
}