Welcome to the resource topic for 2025/1182
Title:
Pseudorandom Correlation Generators for Multiparty Beaver Triples over \mathbb{F}_2
Authors: Peihan Miao, Alice Murphy, Akshayaram Srinivasan, Max Tromanhauser
Abstract:We construct an efficient pseudorandom correlation generator (PCG) (Boyle et al., Crypto’19) for two-party 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.
ePrint: https://eprint.iacr.org/2025/1182
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .