在隐语SecretFlow v0.7版中，隐私集合求交(Private Set Intersection,PSI)新增了基于PCG的PSI方案[BC22]，该方案可对[KKRT16]进行优化，在计算量和通信两方面都有了很大改进，从成本(monetary cost)角度更能满足实际业务需求。引言
[KKRT16][1]是第一个千万规模（224）求交时间在1分钟之内的PSI方案，但也有通量大的问题，低带宽情形时运行时间会显著增加。PSI性能常用的考量指标包括:运行时间、通信量、高峰内存量，[PRTY19]中引入云环境下成本的考量指标。成本是对运行时间和通信量平衡得到的指标，下图[PRTY19]Figure 1中给出了不同带宽下的几种PSI协议的运行时间对比，可以看到带宽对[KKRT16]的运行时间影响还是很大。
1.背景知识
1.1 伪随机相关生成器(PCG)
伪随机相关生成器(Pseudorandom Correlation Generator,PCG)是最近几年MPC方向的一个热点，可以用来构造高效的OT和VOLE，为MPC带来性能提升。[BC22][2]将PCG用于提升PSI的性能，可以降低PSI的计算量和通信量。
PCG由两个算法构成Gen和Expand,如下图所示。
- PCG.Gen(
：是一个概率多项式时间(PPT)算法，给定安全参数λ，输出一对seeds
。 - PCG.Expand
:是一个多项式时间算法，给定σ∈{0,1}和seed
，输出一个bit string
。
(PCG.Gen,PCG.Expand)满足两个性质：
- 正确性: 得到的
满足对应的相关性，例如：RandomOT、VOLE中的相关性。 - 安全性: 对于任意σ∈{0,1},攻击者利用
和
攻击后，无法获取
的信息。
1.2 基于向量的不经意线性函数计算(VOLE)
不经意线性函数计算(Oblivious Linear-function Evaluation, OLE)是个两方协议(函数)。Alice生成
，Bob生成
，运行OLE协议后，Alice得到
。基于向量的不经意线性函数计算(Vector Oblivious Linear-function Evaluation, VOLE)是[ADI+17][3]中对OLE扩展，如下图所示。
一类特殊的VOLE称为subfield VOLE，即上图中
，其它的
，其中
是
的子域。
1.3 布谷鸟哈希(CuckooHash)
[PSSZ15][4]和[KKRT16]中的PSI方案使用了Cuckoo Hash将数据映射到bins，对两方bin之间数据进行对比得到交集。CuckooHash的参数包括(h,s)，其中h表示使用的hash函数的个数，s表示stash的数量。[PSZ18][5]中引入了stashless的方案，即s=0，要求hash函数的数量h≥3。
Cuckoo Hash的使用流程，以h=3为例，bins的数量≈1.2𝑛，对于PSI两方，Receiver将数据插入到CuckooHashTable，Sender将数据插入到SimpleHashTable。CuckooHashTable: 对𝑟∈𝑅，将𝑥插入到
或
对应的位置。
SimpleHashTable: 对𝑠∈𝑆，将𝑦插入到
和
对应的位置。
[BC22]引入了对Cuckoo Hash的推广Generalized Cuckoo Hash(GCH)，GCH的CuckooHashTable每个bin可以有𝑑＞1个元素，这样可以使用2个hash函数得到stashless方案。
1.4 基于置换的哈希函数(Permutation based hash)
[BC22]中使用的是[PSSZ15]中的Permutation based hash方案，
映射
到bin
，可以保证不同𝑥之间不会有冲突。我们的实现中使用了[CLR17][6]中的[ANS10][7] Permutation based hash方案，该方案可以降低table中实际存储数据的比特长度。对于任意长度的数据𝑥应用密码学Hash(SHA256或Blake3)，对齐得到128bit，
。计算
计算
CuckooHashTable和SimpleHashTable存储
用于比较，可以证明对bin内数据
，
比较相等时，对应𝑥=𝑦。
2. [BC22] PCG PSI原理介绍
2.1 sVOLE-Based BaRK-OPRF[BC22]给出了基于sVOLE的BaRK-OPRF构造方法，相比[KKRT16]基于OT-Extension的BaRK-OPRF构造，计算量和通信量更低。
𝑑是每个bin最大的数据量，𝑁是Bin的总数，𝑛=𝑁*𝑑。BaRK-OPRF协议流程：
1、Sender和Receiver执行PCG-VOLE，得𝑛=𝑁*𝑑到维的向量，Receiver得到两个随机向量
,
，Sender得到
。
2、Receiver端CuckooHashTable每个bin最多有𝑑个数据，不足𝑑个数据的填充到𝑑个数据，对𝑑个数据计算插值多项式得到
。
3、Receiver得到
，计算
，将
发送给Sender。
4、Receiver计算
，其中𝑖∈[1,𝑁]，𝑗∈[1,𝑑]，得到的
的BaRK-OPRF。
5、Sender定义
，每个bin的BaRK-OPRF密钥
是
，其中𝑖∈[1,𝑁]。
6、Sender计算
内数据的PRF值，
，并发送给Receiver。BaRK-OPRF的正确性和安全性可以参考[BC22]论文里的证明。
2.2 基于PCG构造半诚实PSI协议
基于上面的sVOLE-Based BaRK-OPRF和GCH，[BC22]构造semi-honest模型的PSI协议。
PCG PSI协议流程：
1、Sender 和 Receiver 共同协商GCH参数，默认选取（3,2）-Generalized CuckooHash
。2、执行PCG/VOLE协议 , 
, Sender得到
和△, Receiver得到
和
, 其中
。3、Receiver将
放入
或
对应的bin。4、Sender将
放入
和
对应的bin。5、Receiver发送掩盖的Bin多项式系数给Sender，计算本方数据集的 BaRK-OPRF。6、Sender发送
对应的PRF值给Receiver。7、Receiver比较两个PRFs集合，得到交集。
[BC22]论文4.5节semi-honest PSI描述中每个bin数据不足𝑑时，给出了不填充到𝑑个数据的构造方法，但是需要额外的
sVOLE，隐语SPU还是采用了填充到𝑑个数据的方案。
3. 实现和性能数据
隐语的[BC22] PCG PSI协议实现已经开源，详细代码请参考secretflow/spu。开源实现中GCH参数选用的是(3,2)，即使用两个hash函数，每个bin最大的数据量是3个。PCG/VOLE使用了emp-zk中的[WYKW21][8]实现，后续会持续关注PCG方面的最新进展，在隐语中增加相应的实现。SPU中PSI协议的性能数据如下：
从上表可以看到对于2^24数据集，SPU中实现的BC22 PCG-PSI的通信量是KKRT16的40%左右，运行时间只有KKRT16的一半。
备注：
上表中KKRT16的性能是隐语SecretFlow V0.6中的性能。
KKRT16 OT-Extension中计算量较大的两个运算是：
- 位矩阵(bit-Matrix)转置
- 采用AES作为Random Oracle[GKWW20][9])，需要大量的AES计算
隐语SecretFlow V0.7中的KKRT16协议实现近期采用emp-tool中的ParaAES(详细参见[VASA][10])，实现可以利用intel的Vector Aes，实现一次计算多组aes计算，大幅提升了kkrt PSI的整体性能，详细的性能数据还在测试中，目前初步测试2^24数据集求交时间是35s左右，比KKRT16论文中的58s，性能提升40%左右。
4. 参考文献
[1] [KKRT16]KKRT16. V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu.Efficient batched oblivious PRF with applications to private set intersection.In ACM CCS 2016, pages 818–829. ACM Press, October 2016.[2] [BC22] Dung Bui and Geoffroy Couteau.Private set intersection from pseudorandom correlation generators.Cryptology ePrint Archive, Paper 2022/334, 2022.[3] [ADI17] B. Applebaum, I. Damgård, Y. Ishai, M. Nielsen, and L. Zichron.Secure arithmetic computation with constant computational overhead.LNCS, pages 223–254. Springer, Heidelberg,2017.[4] [PSSZ15] Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner.Phasing: Private set intersection using permutation-based hashing.In Jaeyeon Jung and Thorsten Holz, editors, 24th USENIX Security Symposium, USENIX Security 15, pages 515{530. USENIX Association, 2015.[5] [PSZ18] B. Pinkas, T. Schneider, and M. Zohner.Scalable private set intersection based on ot extension.ACM Transactions on Privacy and Security (TOPS), 21(2):1–35, 2018.[6] [CLR17] Chen, H., Laine, K., Rindal, P.Fast private set intersection from homomorphic encryption.In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017. pp. 1243{1255. ACM Press (Oct / Nov 2017). https://doi.org/10.1145/3133956.3134061[7] [ANS10] Yuriy Arbitman, Moni Naor, and Gil Segev. 2010.Backyard cuckoo hashing: Constant worst-case operations with a succinct representation.In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. IEEE, 787–796.[8] [WYKW21] C. Weng, K. Yang, J. Katz, and X. Wang.Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits.In 2021 IEEE Symposium on Security and Privacy (SP), pages 1074–1091. IEEE, 2021.[9] [GKWWY20] Efficient and Secure Multiparty Computation from Fixed-Key Block CiphersIEEE (S&P), 2020[10] [VASA] Jean-Pierre Münch and Thomas Schneider and Hossein Yalame VASA: Vector AES Instructions for Security Applications[11] [BCGI18] Elette Boyle, Geo roy Couteau, Niv Gilboa, and Yuval Ishai.Compressing Vector OLE.In: ACM Conference on Computer and Communications Security. ACM, 2018, pp. 896.[12] [BCG19b] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl.Efficient pseudorandom correlation generators: Silent OT extension and more.In CRYPTO 2019, Part III, LNCS 11694, pages 489–518. Springer, Heidelberg, August 2019.[13] [CRR21] G. Couteau, P. Rindal, and S. Raghuraman.Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes.LNCS, pages 502–534. Springer, Heidelberg, 2021[14] [PSZ14] B. Pinkas, T. Schneider, and M. Zohner.Faster private set intersection based on OT extension.In USENIX Security 2014, pages 797–812. USENIX Association, August 2014.[15] [RS21] P. Rindal and P. Schoppmann.VOLE-PSI: Fast OPRF and circuit-PSI from vector-OLE.LNCS, pages 901–930. Springer, Heidelberg, 2021.ps：文中素材来自公开发表论文，如有不妥，将立即删除
