Paper 2024/429

FOLEAGE: $\mathbb{F}_4$OLE-Based Multi-Party Computation for Boolean Circuits

Maxime Bombar, Centrum Wiskunde & Informatica
Dung Bui, IRIF, Université Paris Cité
Geoffroy Couteau, CNRS, IRIF, Université Paris Cité
Alain Couvreur, French Institute for Research in Computer Science and Automation, Computer Science Laboratory of the École Polytechnique, Institut Polytechnique de Paris
Clément Ducros, IRIF, Université Paris Cité
Sacha Servan-Schreiber, Massachusetts Institute of Technology

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. The main efficiency bottleneck in MPC protocols comes from interaction between parties. To limit the interaction, 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. 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 interactively generate a large number of oblivious transfers, which induces an $\Omega(N^2 \cdot 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 triples using only $N \cdot m + O(N^2 \cdot \log m)$ bits of communication for N -parties, and can concretely produce over 11 million triples per second on one core of a commodity machine. Our result builds upon an efficient Pseudorandom Correlation Generator (PCG) for multiplications triples over the field $\mathbb{F}_4$. 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 supporting any field size $q \ge 3$.

Available format(s)
Cryptographic protocols
Publication info
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
2024-03-15: approved
2024-03-12: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.