Peihan Miao
Brown University, Providence, USA

Alice Murphy
Oregon State University, Corvallis, USA

Akshayaram Srinivasan
University of Toronto, Toronto, Canada

Max Tromanhauser
Cornell University, Ithaca, USA

Keywords: Pseudorandom Correlation Generators, Beaver Triples, Learning Parity with Noise

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 ≥ 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³⁰ 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.4x when generating N = 2³⁶ triples between three parties and is 1.2x 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.