CryptoDB
Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits
| Authors: |
|
|---|---|
| Download: |
|
| 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
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
}