CryptoDB
Pseudorandom Correlation Generators for Multiparty Beaver Triples over $\mathbb{F}_2$
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2025 |
| Abstract: | We construct an efficient pseudorandom correlation generator (PCG) (Boyle et al., Crypto'19) for two-party {\it programmable oblivious linear evaluation (OLE)} functionality over $\mathbb{F}_2$. Our construction (i) has an efficient seed expansion phase, and (ii) comes with a concretely efficient protocol for distributing the seeds that makes black-box use of cryptography and runs in a constant number of rounds. PCGs for programmable OLE are known to imply PCGs for generating $n$-party Beaver triples over $\mathbb{F}_2$. The resultant PCG has a seed setup phase whose communication cost is $n(n-1)$ times than that of the programmable OLE protocol. The per-party seed size and the seed expansion time have a multiplicative overhead of $2(n-1)$. Prior constructions for efficiently generating multiparty Beaver triples only worked for finite fields $\mathbb{F}_q$ where $q \geq 3$ or required one bit of per-party communication for each triple generated (and hence, do not satisfy the PCG definition). Thus, ours is the first concretely efficient PCG for generating Beaver triples over $\mathbb{F}_2$ in the multiparty setting. Our distributed seed generation protocol generates $N = 2^{30}$ two-party programmable OLEs in 3.5 minutes with 255 MB of communication over a LAN network. The PCG seed size is around 55 MB and the expansion phase requires 10 PRG calls and around 229 thousand XOR and AND operations per triple, producing roughly 31,000 triples per second. Our PCG for generating multiparty Beaver triples has lower concrete communication cost than the state-of-the-art for small number of parties. When compared to the FOLEAGE protocol (Bombar et al, Asiacrypt 2024) which requires one bit of per-party communication per triple that is generated, our communication cost is lower by $2.4\times$ when generating $N = 2^{36}$ triples between three parties and is $1.2 \times $ lower for the case of five parties. At a conceptual level, our protocol deviates from the prior approaches which relied on variants of dual learning parity with noise (LPN) assumption. Instead, our construction combines both the primal and dual versions of LPN to achieve the aforementioned efficiency. |
BibTeX
@inproceedings{asiacrypt-2025-36068,
title={Pseudorandom Correlation Generators for Multiparty Beaver Triples over $\mathbb{F}_2$},
publisher={Springer-Verlag},
author={Peihan Miao and Alice Murphy and Akshayaram Srinivasan and Max Tromanhauser},
year=2025
}