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 \ge 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 min 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Pseudorandom Correlation Generators for Multiparty Beaver Triples over  \(\mathbb {F}_2\)

  • Peihan Miao,
  • Alice Murphy,
  • Akshayaram Srinivasan,
  • Max Tromanhauser

摘要

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 \ge 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 min 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.