前言：隐私求交（Private Set Intersection, PSI）作为一种发展比较成熟的安全计算技术，在撞库、隐私数据对齐等许多现实场景中有广泛的应用。在近 2～3 年，得益于 (subfield) (Vector) Oblivious Linear Evauluation (sVOLE / VOLE/ OLE) 原语技术的发展，越来越多的研究人员希望使用其替换传统 PSI 中的 Oblivious Transfer (OT) 来进一步提升 PSI 性能。例如：
Peter Rindal and Phillipp Schoppmann. 2021. VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE. In EUROCRYPT 2021 [1]
Wutichai Chongchitmate, Yuval Ishai, Steve Lu, and Rafail Ostrovsky. 2022. PSI from Ring-OLE. In CCS '22 [2]
Srinivasan Raghuraman and Peter Rindal. 2022. Blazing Fast PSI from Improved OKVS and Subfield VOLE. In CCS '22 [3]
我们这篇文章着重介绍一下 2022 年 CCS 的文章 “Blazing Fast PSI from Improved OKVS and Subfield VOLE”。在具体介绍协议细节之前我们先看一下文中给出的新 PSI 性能与已有 PSI 性能比较（单线程、LAN、CPU=Intel i7 9750H、RAM=16GB、计算双方数据量相同）
在 2^20 = 1048576 大小的数据集上
新协议时间：0.37s
KKRT 协议时间：2.07s
Blazing Fast 文章使用了两个关键技术，相比于以往的 PSI 得到了比较好的通信性能提升。由于篇幅原因，本文不对以下两个技术的具体实现细节展开（感兴趣的小伙伴可以参考原论文），而是把重点放在解释如何使用这两种工具构建高效的 PSI 算法。
Subfield VOLE (Vector Oblivious Linear Evaluation) [6]
Improved OKVS (Oblivious Key-Value Store) 参考原始论文实现
注：本文中仅对半诚实模型下的协议进行了探讨，恶意安全协议请参考原始文章。
1.完整 PSI 协议流程
注意：在本文中，我们假设做 PSI 协议的两个参与方所持有的数据集大小是相等的。这样的假设更多的是为了方便我们进行复杂度的计算，并更容易与已有方案之间做比对。
本文大写字母表示矩阵，例如
，大写字母 + 箭头表示向量，例如
；为了大家的习惯，本文依旧使用X，Y分别表示 Receiver 数据集以及 Sender 数据集。
Blazing fast PSI 协议是建立在 OKVS-based PSI 框架之上的。Oblivious Key-Value Store 机构在 [4] 中被首次提出，并应用在高性能的 PSI 协议构建，具体 PSI 协议流程如下所示：
我们先给出上图黑盒调用模块的具体定义：
定义：OKVS (Oblivious Key Value Store)
编码函数
，给定输入数据：
，输出数据：
解码函数
，给定输入数据：
，输出数据：
Obliviousness性质，即：对于任意
，以及均匀随机的
，有：
常用的 Decoding “同态” 的 OKVS 定义（注：上图中的 OKVS-PSI 使用的就是 Linear OKVS）
Linear OKVS，假设
是一个长度扩展 PRG
Encode 函数为乘法运算，即
Decode 函数为内积乘法运算
定义：VOLE (Vector Oblivious Linear Evaluation)
在计算结束后，其中一个参与方获得：有限域整数
，向量
在计算结束后，另一个参与方获得: 向量
，其中
我们首先来验证一下协议的正确性，由于 Correlation-Robust Hash 并不会影响正确性，因此我们只需要比对 Decoding 过程的安全性即可。
1.首先根据定义，我们有上图中的
2.那么 Sender 端的计算结果
可以分步骤被拆解
我们可以看到，当
那么
，那么最终结果为
，最终 decode 结果为
与 Reciver 端一致。
而对于安全性来说，在半诚实的安全模型下，我们需要保证在
时，Receiver端收到的
与任意一个随机的
的
无法区分。而由于我们使用了 Random Oracle 
，因此可以保证安全性。
注：此处属于安全性描述，并不严谨，请参考原始原始论文中的形式化安全证明。
2. 使用 Subfield VOLE 进行性能提升
VOLE 的具体定义如下图所示，而 Subfield VOLE 属于一种特殊的 VOLE，其在调用时需要设定参数：一个“比较小”的域
和一个“比较大”的域
，而通常在 VOLE 里面我们会设定
。
在计算结束后，其中一个参与方获得：有限域整数
，向量
在计算结束后，另一个参与方获得: 向量
，其中
例：某些 Subfield VOLE 应用会设定
，以及
结合 OKVS-PSI 的原协议，我们可以发现可以在不影响安全性的前提下将图中 VOLE 修改为 subfield VOLE，好处是：
Subfield VOLE 的构造速度比 VOLE 快
可以有效减少
产生的 Online 通信（从
到
）
OKVS 的 Encode 发生在比较小的有限域
上
那么我们应该如何选取
和
？
由于OPRF最终的结果在
上，为了保证较小的OPRF碰撞概率，因此需要
。再者，我们同样需要保证
（这里
为计算安全参数）
3. 结尾
在学术界，PSI 协议近两年处于快速进步的时间点，隐语致力于对用户提供易用的、稳定的、可证安全的高性能密码模块，请期待隐语后续的更新。
Reference
[1] Peter Rindal and Phillipp Schoppmann. 2021. VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE. In Advances in Cryptology – EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part II. Springer-Verlag, Berlin, Heidelberg, 901–930. https://doi.org/10.1007/978-3-030-77886-6_31
[2] Wutichai Chongchitmate, Yuval Ishai, Steve Lu, and Rafail Ostrovsky. 2022. PSI from Ring-OLE. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS '22). Association for Computing Machinery, New York, NY, USA, 531–545. https://doi.org/10.1145/3548606.3559378
[3] Srinivasan Raghuraman and Peter Rindal. 2022. Blazing Fast PSI from Improved OKVS and Subfield VOLE. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS '22). Association for Computing Machinery, New York, NY, USA, 2505–2517. https://doi.org/10.1145/3548606.3560658
[4] Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. 2020. PSI from PaXoS: Fast, Malicious Private Set Intersection. In Advances in Cryptology – EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part II. Springer-Verlag, Berlin, Heidelberg, 739–767. https://doi.org/10.1007/978-3-030-45724-2_25
[5] Garimella, G., Pinkas, B., Rosulek, M., Trieu, N., Yanai, A. (2021). Oblivious Key-Value Stores and Amplification for Private Set Intersection. In: Malkin, T., Peikert, C. (eds) Advances in Cryptology – CRYPTO 2021. CRYPTO 2021. Lecture Notes in Computer Science(), vol 12826. Springer, Cham. https://doi.org/10.1007/978-3-030-84245-1_14
[6] Couteau, G., Rindal, P., Raghuraman, S. (2021). Silver: Silent VOLE and Oblivious Transfer from Hardness of Decoding Structured LDPC Codes. In: Malkin, T., Peikert, C. (eds) Advances in Cryptology – CRYPTO 2021. CRYPTO 2021. Lecture Notes in Computer Science(), vol 12827. Springer, Cham. https://doi.org/10.1007/978-3-030-84252-9_17
