Cryptology ePrint Archive: Report 2021/120

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

Aner Ben-Efraim and Kelong Cong and Eran Omri and Emmanuela Orsini and 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.

Category / Keywords: cryptographic protocols /

Original Publication (with major differences): IACR-EUROCRYPT-2021

Date: received 2 Feb 2021

Contact author: anermosh at post bgu ac il, kelong cong@esat kuleuven be, omrier@gmail com, emmanuela orsini@kuleuven be, nigel smart@kuleuven be, eduardo@cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20210205:123340 (All versions of this report)

Short URL: ia.cr/2021/120


[ Cryptology ePrint archive ]