Paper 2024/429
FOLEAGE: $\mathbb{F}_4$OLE-Based Multi-Party Computation for Boolean Circuits
Abstract
Secure Multi-party Computation (MPC) allows two or more parties to compute any public function over their privately-held inputs, without revealing any information beyond the result of the computation. Modern protocols for MPC generate a large amount of input-independent preprocessing material called multiplication triples, in an offline phase. This preprocessing can later be used by the parties to efficiently instantiate an input-dependent online phase computing the function. To date, the state-of-the-art secure multi-party computation protocols in the preprocessing model are tailored to secure computation of arithmetic circuits over large fields and require little communication in the preprocessing phase, typically O(N · m) to generate m triples among N parties. In contrast, when it comes to computing preprocessing for computations that are naturally represented as Boolean circuits, the state-of-the-art techniques have not evolved since the 1980s, and in particular, require every pair of parties to execute a large number of oblivious transfers before interacting to convert them to N-party triples, which induces an Ω(N^2 · m) communication overhead. In this paper, we introduce FOLEAGE, which addresses this gap by introducing an efficient preprocessing protocol tailored to Boolean circuits. FOLEAGE exhibits excellent performance: It generates m multiplication triples over F2 using only N · m + O(N^2 · log m) bits of communication for N-parties, and can concretely produce over 12 million triples per second in the 2-party setting on one core of a commodity machine. Our result builds upon an efficient Pseudorandom Correlation Generator (PCG) for multiplication triples over the field F4. Roughly speaking, a PCG enables parties to stretch a short seed into a large number of pseudorandom correlations non-interactively, which greatly improves the efficiency of the offline phase in MPC protocols. Our construction significantly outperforms the state-of-the-art, which we demonstrate via a prototype implementation. This is achieved by introducing a number of protocol-level, algorithmic-level, and implementation-level optimizations on the recent PCG construction of Bombar et al. (Crypto 2023) from the Quasi-Abelian Syndrome Decoding assumption.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Secure ComputationMPCPseudorandom Correlation GeneratorsPCGOblivious Linear EvaluationOLE
- Contact author(s)
-
maxime bombar @ cwi nl
bui @ irif fr
couteau @ irif fr
alain couvreur @ inria fr
cducros @ irif fr
3s @ mit edu - History
- 2024-05-29: revised
- 2024-03-12: received
- See all versions
- Short URL
- https://ia.cr/2024/429
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/429, author = {Maxime Bombar and Dung Bui and Geoffroy Couteau and Alain Couvreur and Clément Ducros and Sacha Servan-Schreiber}, title = {{FOLEAGE}: $\mathbb{F}_4${OLE}-Based Multi-Party Computation for Boolean Circuits}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/429}, year = {2024}, url = {https://eprint.iacr.org/2024/429} }