International Association for Cryptologic Research

International Association
for Cryptologic Research

ASIACRYPT 2024

FOLEAGE: F4OLE-Based Multi-Party Computation for Boolean Circuits


Maxime Bombar
IMB, Université de Bordeaux

Dung Bui
IRIF, Université Paris Cité

Geoffroy Couteau
CNRS, IRIF, Université Paris Cité

Alain Couvreur
INRIA, Laboratoire LIX

Clément Ducros
IRIF, Université Paris Cité, INRIA

Sacha Servan-Schreiber
MIT, Cambridge MA


Keywords:


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 Ω(N2· m) communication overhead.

In this paper, we introduce F4OLEAGE, which addresses this gap by introducing an efficient preprocessing protocol tailored to Boolean circuits. F4OLEAGE exhibits excellent performance: it generates m multiplication triples over F2 using only N · m + O(N2 · 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 multiplications 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.

Publication

ASIACRYPT 2024

Paper

Artifact

Artifact number
asiacrypt/2024/a8

Artifact published
February 7, 2025

Badge
IACR Results Reproduced

README

gz (240 KB)  

View on Github

License
This work is licensed under the MIT License.


BibTeX How to cite

Bombar, M., Bui, D., Couteau, G., Couvreur, A., Ducros, C., & Servan-Schreiber, S. (2024). FOLEAGE: F4OLE-Based Multi-Party Computation for Boolean Circuits. In: Chung, KM., Sasaki, Y. (eds) Advances in Cryptology — ASIACRYPT 2024. pp. 69—101. Lecture Notes in Computer Science, Vol. 15489. Springer, Singapore. https://doi.org/10.1007/978-981-96-0938-3_3. Artifact at https://artifacts.iacr.org/asiacrypt/2024/a8.