## CryptoDB

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

Authors: 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 EUROCRYPT 2021 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$.
##### BibTeX
@inproceedings{eurocrypt-2021-30784,
title={Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-77883-5_2},
author={Aner Ben-Efraim and Kelong Cong and Eran Omri and Emmanuela Orsini and Nigel P. Smart and Eduardo Soria-Vazquez},
year=2021
}