International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Aner Ben-Efraim , Ariel University
Kelong Cong , imec-COSIC, KU Leuven
Eran Omri , Ariel University
Emmanuela Orsini , imec-COSIC, KU Leuven
Nigel P. Smart , imec-COSIC, KU Leuven; University of Bristol
Eduardo Soria-Vazquez , Aarhus University
DOI: 10.1007/978-3-030-77883-5_2 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
Abstract: Whilst secure multiparty computation (MPC) based on garbled circuits is concretely efficient for a small number of parties $n$, the gap between the complexity of practical protocols, which is $O(n^2)$ per party, and the theoretical complexity, which is $O(n)$ per party, is prohibitive for large values of $n$. In order to bridge this gap, Ben-Efraim, Lindell and Omri (ASIACRYPT 2017) introduced a garbled-circuit-based MPC protocol with an almost-practical pre-processing, yielding $O(n)$ complexity per party. However, this protocol is only passively secure and does not support the free-XOR technique by Kolesnikov and Schneider (ICALP 2008), on which almost all practical garbled-circuit-based protocols rely on for their efficiency. In this work, to further bridge the gap between theory and practice, we present a new $n$-party garbling technique based on a new variant of standard LPN-based encryption. Using this approach we can describe two new garbled-circuit based protocols, which have practical evaluation phases. Both protocols are in the preprocessing model, have $O(n)$ complexity per party, are actively secure and support the free-XOR technique. The first protocol tolerates full threshold corruption and ensures the garbled circuit contains no adversarially introduced errors, using a rather expensive garbling phase. The second protocol assumes that at least $n/c$ of the parties are honest (for an arbitrary fixed value $c$) and allows a significantly lighter preprocessing, at the cost of a small sacrifice in online efficiency. We demonstrate the practicality of our approach with an implementation of the evaluation phase using different circuits. We show that like the passively-secure protocol of Ben-Efraim, Lindell and Omri, our approach starts to improve upon other practical protocols with $O(n^2)$ complexity when the number of parties is around $100$.
Video from EUROCRYPT 2021
  title={Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits},
  author={Aner Ben-Efraim and Kelong Cong and Eran Omri and Emmanuela Orsini and Nigel P. Smart and Eduardo Soria-Vazquez},