引言

不经意间线性计算 (Oblivious linear functional evaluation, OLE) 及其变体 Vector OLE (VOLE) 是多方安全计算中的核心组件之一。它们可以广泛应用于 OT 扩展 [BCGI18][BCG+19a][BCG+19b]、产生乘法三元组、隐私集合求交 [RR22] 和零知识证明 [WYKW21] 等场景中。因此，如何高效的产生随机 VOLE 组 (VOLE correlation) 一直是密码学学界研究的重点。

[BCGI18] 提出了伪随机相关生成器 (pseudorandom correlation generator, PCG) 的概念，它的核心思想是：通过“少量的通信”使参与方得到“短”的种子，随后参与方利用这些种子产生“大量”的相关随机数。同时，[BCGI18] 还给出了 PCG-based VOLE 的构造框架，并提出了亚线性通信复杂度的 OT 扩展协议 Silent OT extension。

[BCG+19b] 的实验结果显示，相比传统的 OT extension [IKNP03][KOS16]，Silent OT extension 在低带宽的网络环境下性能更佳。在带宽为 10 Mbps 的环境下，产生 组 OT 仅需 8000 ms，比传统的 OT extension 提速了约 15 倍。

图片出自  [BCG+19b] table 2.

一、背景知识

1.1 OLE/VOLE

OLE 是一类两方的协议，其中 Sender 输入 ，Receiver 输入  并获得 。而 VOLE 则是 OLE 的向量版本。

当 ，即 时，OLE/VOLE 会退化为 OT。

1.2 伪随机相关生成器 (PCG)

PCG 是近年 MPC 研究的热点，它的本质是通过“短的种子”生成“长的随机串”（即相关随机数）。而在 MPC 应用中，“离线”阶段不再需要存储大量的相关随机数，而只需要存储少量的 PCG 种子。当“在线”阶段需要消耗相关随机数时，各方不需要任何交互，可以直接通过 PCG 种子产生所需的相关随机数。

两方的伪随机相关生成器由 PCG.Gen 和 PCG.Extend 两个算法构成，其中 PCG.Gen 可以由可信第三方或两方协议实现 [BCGI18][BCG+19b]。

 ● ：随机算法，给定安全参数 ，输出一对种子 。

 ● ：确定性算法，给定  及种子 ，输出伪随机串 ，并且满足 。

1.3 （多）点函数秘密共享

点函数 是一种特殊的函数，当且仅当输入 时，输出 ，否则输出 。而点函数秘密共享 DPF (distributed point function) 是由 Gilboa 等人在 2014 年提出的 [GI14]，它可以直接应用于 PIR (private information retrieval) 和安全关键字搜索 (secure keyword search) 中。两方的 DPF 通常会使用 GGM-tree punctured PRF 实现。它主要由 和 两个算法组成：  ● ：随机算法，给定安全参数 ，两个整数 和 ，输出一对密钥  。  ● ：确定性算法，给定 和 ，输出结果 。

正确性：

安全性：存在一个模拟算法 ，它与真实产生的密钥 是计算不可区分的。

如上图所示，定义算法 遍历 。

而多点函数 则是点函数的扩展，若 时，则输出 。否则，输出 。分布式多点函数一般是通过复合使用 个 DPF 实现。与 DPF 相似，它也是由两个算法组成：

● ：随机算法，给定安全参数 ，两个集合 ，输出一对

● ：确定性算法，给定 和 ，输出结果 。其中，上述算法需要满足以下性质：

正确性：

同理，可以定义相应的算法  遍历 。

1.4 LPN（Learning Parity with Noise）

LPN 是密码学领域上一个非常著名的问题 [BFK+93]。它描述的是给定一个随机矩阵 ，秘密选取随机向量 和“错误扰动”向量 。分布  与均匀随机的 是计算不可区分的。

同时，LPN 与其对偶版本是等价的。寻找矩阵  s.t. ，那么会有 ，此时 也是与均匀随机分布 是计算不可区分的。

二、PCG-based VOLE 原理介绍

VOLE 和 Random VOLE 的功能如下所示，其中 [BCGI18] 论证了两者是等价的。

在 [BCGI18] 中，Boyle 等人提出了一套基于 MPFSS 和 LPN 构造 Random VOLE 的框架：

1. Receiver 会选择元素 ，Sender 选择“稀疏”的扰动向量 。

2. Receiver 和 Sender 调用 的分布式算法，并分别得到 和 ，使得 。（具体可见 [SGRR19] Protocol 4)

3. Receiver 设置 ，并利用公开的 dual-LPN 矩阵 计算向量；而 Sender 设置 ，然后计算    和  。

具体运行流程，如下图所示：

根据分布式多点函数性质：

可以得：

根据对偶 LPN，显然向量 是“均匀随机”的。

三、相关研究

近年来，也有不少学者对 PCG-based VOLE 进行改进。在 [BCG+19b] 中，提出了使用 GGM-tree PPRF 替换 DPF，使得 DPF 的“种子”可以通过 OT 产生，无需可信第三方参与；在 [SGRR19] 中，实现和构造了在整环 和 上的 VOLE；随后，在 [YWL+20] 中，提出了 bootstrapping 的思想，使得 PCG-based VOLE 只需进行一次 one-time setup；而在 [CRR21] 和 [BCG+22] 中，分别提出了两种 LPN-friendly 的编码技术，使得向量与 dual-LPN 矩阵的乘运算更加高效；此外，[GYW+23] 中，提出了一种 correlated GGM-tree 的构造，使得每一层的左右子树的和都为定值，使得 GGM-tree 所需的通信量和计算量都降低了一半。

四、参考文献

• [BFK+93] Blum A, Furst M, Kearns M, et al. Cryptographic primitives based on hard learning problems[C]//Advances in Cryptology—CRYPTO’93: 13th Annual International Cryptology Conference Santa Barbara, California, USA August 22–26, 1993 Proceedings 13. Springer Berlin Heidelberg, 1994: 278-291.
  
• [BI14] Gilboa N, Ishai Y. Distributed point functions and their applications[C]//Advances in Cryptology–EUROCRYPT 2014: 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings 33. Springer Berlin Heidelberg, 2014: 640-658.
  
• [BCGI18] Boyle E, Couteau G, Gilboa N, et al. Compressing vector OLE[C]//Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018: 896-912.
  
• [SGRR19] Schoppmann P, Gascón A, Reichert L, et al. Distributed vector-OLE: improved constructions and implementation[C]//Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019: 1055-1072.
  
• [BCG+19a] Boyle E, Couteau G, Gilboa N, et al. Efficient pseudorandom correlation generators: Silent OT extension and more[C]//Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part III 39. Springer International Publishing, 2019: 489-518.
  
• [BCG+19b] Boyle E, Couteau G, Gilboa N, et al. Efficient two-round OT extension and silent non-interactive secure computation[C]//Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019: 291-308.
  
• [YWL+20] Yang K, Weng C, Lan X, et al. Ferret: Fast extension for correlated OT with small communication[C]//Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. 2020: 1607-1626.
  
• [CRR21] Couteau G, Rindal P, Raghuraman S. Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[C]//Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part III. Cham: Springer International Publishing, 2021: 502-534.
  
• [WYKW21] Weng C, Yang K, Katz J, et al. Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits[C]//2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021: 1074-1091.
  
• [BCG+22] Boyle E, Couteau G, Gilboa N, et al. Correlated pseudorandomness from expand-accumulate codes[C]//Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part II. Cham: Springer Nature Switzerland, 2022: 603-633.
  
• [RR22] Raghuraman S, Rindal P. Blazing fast PSI from improved OKVS and subfield VOLE[C]//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022: 2505-2517.
  
• [GYW+23] Guo X, Yang K, Wang X, et al. Half-tree: Halving the cost of tree expansion in cot and dpf[C]//Advances in Cryptology–EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part I. Cham: Springer Nature Switzerland, 2023: 330-362.