技术分享 | 隐私集合求交（PSI）技术体系整理

0

前言

数字经济时代，数据已经成为基础性关键战略资源、第五大核心生产要素。但是数据要素流通也面临着一系列严峻的安全挑战。如何在保障数据安全的同时又不影响数据要素的使用，隐私计算技术应运而生。其中，隐私集合求交作为一项典型的隐私保护分布式计算技术，在金融、医疗、交通、政务等诸多领域具有广泛应用场景，深受学术界和工业界的关注。
1

隐私集合求交概念

隐私集合求交（Private Set Intersection, PSI）是安全多方计算（Multi-Party Computation, MPC）领域的一类专有协议，其允许一组参与方输入私有集合共同计算集合交集，且保证除集合交集结果外无任何额外元素信息的泄露。由于PSI无需采用基于电路的通用MPC框架进行设计，针对某一特定场景可采用更轻量级的密码原语构建PSI协议，由此摆脱混淆电路带来的昂贵开销并带来了巨大的性能提升，但专有协议需要配置一套完整的安全性证明用于证明专有协议的安全性。PSI依据参与方数量可分为两方PSI（传统PSI）和多方PSI，功能示意图如1-1所示：

图1-1 PSI功能示意图（参与方数量不同）

PSI依据对交集的重解释性可分为传统交集PSI、阈值交集PSI、超阈值交集PSI，功能示意图如1-2所示：

图1-2 PSI功能示意图（交集定义不同）

另外，PSI基于敌手的行为方式可分为半诚实安全PSI协议、恶意安全PSI协议，敌手行为如下：

• 半诚实敌手：诚实的执行协议，但主动收集和分析协议消息。

• 恶意敌手：可任意偏离协议规则执行协议。

本文将从两方隐私集合求交、多方隐私集合求交来阐述现有PSI协议进展。

2

两方隐私集合求交两方PSI更纯粹于关注底层密码原语[1][2]（Diffie-Hellman, DH、Oblivious Transfer Extension, OTE、Garbled Circuit, GC、Homomorphic Encryption, HE）的更新，是近些年研究最为广泛的PSI协议。依据相关经验可知：（1）计算性能：OTE和DH加密原语的性能远优于GC和HE加密原语。
（2）并行化：DH、HE加密元素相互独立，OTE需要执行大规模的矩阵向量乘难以并行化，GC的计算具有顺序性因此无法并行处理。
（3）适用场景：OTE的生成需要固定公钥加密和大量对称密钥构建，适用于大集合场景。DH相较于OTE更适合小集合场景。HE具有明文计算和密文计算等价特性，常用于构建非平衡场景。GC可实现交集结果成秘密共享方式存储，常用于在交集结果上执行对称函数操作（求势、求和等）。（4）内存消耗情况：DH-PSI协议的元素处理过程流式化，因此消耗低。GC-PSI协议由电路深度决定（电路深度与集合大小相关），内存消耗大。OTE的主要内存消耗为编码矩阵和存储元素的编码向量，内存消耗中等。朴素HE-PSI协议的内存仅与密文大小相关，内存消耗低。但涉及数据预处理存储以实现高效的非平衡PSI则内存消耗巨大。2.1 ECDH-PSI基于DH的PSI协议主要是利用离散对数困难问题构建密钥协商协议来保证PSI协议的安全性。DH-PSI可分为有限域上DH的PSI协议和椭圆曲线上DH的PSI协议，基础思想均是将明文元素的比较转换为协商密钥的匹配。基于椭圆曲线上DH的PSI协议相较于基于有限域上DH的PSI协议具有更好的性能：（1）密钥长度更短：椭圆曲线（Elliptic Curve Cryptography，ECC）上DH和有限域上DH在保证同一安全水准时，椭圆曲线上DH具有更短的密钥长度，因此ECDH-PSI协议拥有更低的通信开销。（当计算安全参数为128时，有限域上DH密钥长度2048 == 椭圆曲线上DH密钥长度256）（2）更多样的群结构：椭圆曲线可借助参数的变化得到不同的曲线，例如FourQ, Curve25519, sm2p256v1, Secp256k1等，相较于有限域上DH具有更多样的群结构。（3）ECC点乘替换模幂运算，提高数据传输效率。基础协议：如图2-1 ECDH-PSI协议流程图所示，我们给出了两种ECDH-PSI流程图(严格讲为DH-PSI，ECDH-PSI唯一的不同之处为将下述的模幂操作转换为ECC点乘操作)。
图2-1(a)基础协议流程[3]：--假设参与方Alice和Bob已共享曲线参数(椭圆曲线E,阶N,基点G),理想置换（1）--Bob生成随机整数a作为私钥--Bob对基点G和a执行ECC点乘得到G*a,并将其发送给Alice（2）--Alice为其每个元素生成对应的随机整数作为其私钥，最后得到私钥集合--Alice对基点G和执行ECC点乘得到交换消息集合--Alice对交互消息集合A执行理想置换得到集合A'={}--Alice以作为键，作为值构建多项式,将P发送给Bob（3）--Bob计算协商密钥 ,最后得到协商密钥集合,Shuffled(K)后发送给Alice（4）--Alice对G*a和执行ECC点乘得到协商密钥 ,对其和Shuffled(K)比较得到交集结果。
图2-1(b)基础协议流程[4][5]：--假设参与方Alice和Bob已共享曲线参数（椭圆曲线E,阶N,基点G）（1）--Alice生成随机整数a作为私钥

--Alice对集合hash到E上某一点的x值得到

--Alice对和私钥a执行ECC点乘得到A=,将A发送给Bob

（2）--Bob生成随机整数b作为私钥

--Bob对和私钥b执行ECC点乘得到B=

--Bob对集合hash到E上某一点的x值得到

--Bob对和私钥b执行ECC点乘得到C=,将B和C发送给Alice

（3）--Alice对C和私钥a执行ECC点乘得到C'=

--Alice通过比较C'和B中相等的元素得到集合交集

图2-1 ECDH-PSI协议流程图

以上协议的安全性保证基于椭圆曲线的离散对数困难性问题:给定椭圆曲线上的一点G，整数a，求解ECC点乘P=G*a是简单的，而给定一点G和P，求解a是困难性问题。

基础密码学组件：椭圆曲线算法（128bit的计算安全性，密钥长度需要256bit）

--FourQ:运算速率超快,可抵御侧信道攻击

--Curve25519:运算速率快，但更容易遭受侧信道攻击

--Secp256k1:运算速率一般，可抵御侧信道攻击,方程系数存在来历不明随机数

--sm2p256v1:运算速率一般，国产商用椭圆曲线。

半诚实模型下理论通信比较：ECDH-PSI(a)相较于ECDH-PSI(b)少通信开销。

2.2 OTE-PSI

基于OTE的PSI协议利用构建OT实例的Base-OT（基于公钥的OT协议）和纠错编码函数的汉明距离来保证PSI协议的安全性，并利用OT实例构建不经意伪随机函数(Oblivious Evaluation of Pseudorandom Functions, OPRF)实现PSI功能。

基于公钥的OT协议是非常昂贵的，如果只采用少量的公钥密码和大量的对称密码实现大量的OT实例（公钥密码的数量取决于计算安全参数），将使得OT协议具有非常高效的计算性能，具有此类特性的OT协议称为不经意传输扩展（Oblivious Transfer Extension, OTE），由OTE构建的PSI协议因此也具有计算效率高的特点。

OTE依据构造特性可分为基于矩阵变换的IKNP类-OTE（主要实现为对于ROT的高效扩展）和基于函数秘密共享的向量不经意评估（ Vector-OLE，VOLE）（主要实现为对COT的高效扩展）。IKNP类-OTE具有最佳的计算效率、但通信开销为该方案在广域网场景下的主要瓶颈，基于该OTE构建PSI协议的代表性文章KKRT16[6]，CM20[7]。VOLE类-OTE在通信开销和计算效率上做到了均衡、在广域网下性能更具有优势，基于该OTE构建PSI协议的代表性文章VOLE21[8],RR22[9],BC22[10]。

本小节将首先介绍如何基于OPRF构建PSI协议和三类OT协议，再介绍两类OTE的实现方式及如何通过OTE构建OPRF，最后介绍如何降低通信(OKVS)。

基于OPRF可以很简单的构建出PSI协议，OPRF构建PSI基础思想如图2-2所示，步骤如下：

--参数：发送方拥有私有集合,接收方拥有私有集合

--OPRF阶段：双方执行OPRF协议：

输入：接收方输入私有集合，发送方无输入

输出：接收方输出OPRF值集合

--交集计算阶段：发送方基于密钥k计算OPRF值得到OPRF值集合，将发送给接收方。接收方通过比较集合和得到交集集合。

图2-2基于OPRF构建PSI基础流程图

标准-OT：

--输入：接收方R输入选择比特，发送方S输入消息对

--输出：接收方R输出消息

随机-OT:

--输入：接收方R输入选择比特

--输出：发送方S输出消息对，接收方R输出消息

相关-OT：

--输入：接收方R输入选择比特,发送方S输入相关函数

--输出：相关-OT随机产生消息，发送方S输出消息对，接收方R输出消息

2.2.1 IKNP类-OTE的构建

本小节将首先介绍如何基于少量公钥加密实现大量2选1 ROT实例(Ishai03[11]),其次介绍如何通过编码重解释将Ishai03-2选1 ROT扩展为选1OT(KK13[12])。再介绍通过伪随机编码替换纠错编码实现选1 ROT(KKRT16[6])。最后将选1 ROT解释为OPRF。思路如图2-3所示：

图2-3 IKNP类-OTE思路图

OT实例功能介绍，功能图如2-4所示，x选1-OT功能如下：

--输入：发送方S输入x个秘密消息,接收方R输入选择比特

--输出：接收方R输出选择消息

--安全性：要求发送方S不知晓接收方R的选择比特信息,接收方除选择消息外不知晓其它秘密消息。

图2-4 1-x OT功能示意图

2选1-OTE(Ishai03[11])：

--参数：发送方S，接收方R(发送方和接收方的定义依据最终OT实例中输入选择比特和输出2选1OT值定义为接收方，另一方为发送方)，最终需要m个OT实例。

--接收方R随机生成选择比特串,随机生成m*k的矩阵T。令表示矩阵T的第j行。基于比特串r和矩阵T生成矩阵U，其中矩阵U的第j行。如图2-5的步骤1.

--发送方S随机选择一个随机字符串。如图2-5步骤2.

--双方执行k个2选1base-ot，对于第i个ot，发送方S输入选择比特,接收方输入消息对。发送方输出消息。执行完k个OT后，发送方获得一个m*k的矩阵Q。如图2-5步骤3.

--对矩阵Q、矩阵T、选择比特串r、随机字符串s从观察得到如下结论，如图2-5步骤4：

如果,则,无论s的值为什么，都有，将其写为

如果,则,故对于，将其写为

最终得到

--基于上述观察我们得到m个随机OT：

首先我们需要利用一个关联健壮哈希函数H,其作用是每个ot协议都共用了相同的s,以解决相关性问题，使其独立伪随机。如图2-5步骤5.

--发送方S获得两个消息

--接收方R获得一个消息,其依据选择bit只能属于发送方S中的一个消息

--将随机OT转换为标准OT，见图2-5步骤6.

--发送方S输入两个消息给接收方R

--接收方R计算

获得其中一个消息

（相关OT：COT转为标准OT的方法：先通过hash函数进行hash得到ROT，ROT转标准OT见图2-5步骤6.）

图2-5 1-2 OTE功能示意图

选1-OTE(KK13[12]): KK13对图2-5步骤1通过生成矩阵U的过程解释为对选择比特r的重复编码。若不再是一个bit而是l个bit,即可实现选1-OT。变换如下，如图2-6所示：

--变换1：对于第一步，令,C：l维线性纠错码，其汉明距离至少为安全参数

--变换2：对于第四步，

由此实现选1-OT，发送方可计算个秘密值，因为发送方知晓。

图2-6 1- OTE功能示意图

选1OT(KKRT16[6]):KKRT16通过观察KK13中的线性编码C，发现整个协议过程中并没有使用编码C的解码功能，且仅要求编码C对于其的汉明距离最小为计算安全参数即可。也就是说只需要一个函数F，其满足的最小汉明距离为计算安全参数即可。因此本文采用伪随机函数替换了线性纠错码，并给出了当伪随机函数的输出长度为时即可满足最小汉明距离为计算安全参数。

IKNP类-OTE讨论：OTE矩阵的宽度k等于线性纠错码C的码字长度，其决定了协议的通信开销大小。2选1-OTE(Ishai03)的码字长度为计算安全参数因此设置。选1-OTE(KK13)的码字长度为2倍计算安全参数因此设置.伪随机函数的输出长度为，因此宽度。

IKNP类-OTE构建OPRF：

单点OPRF(KKRT16)[6]：可将选1OTE中的看作OPRF函数，其中发送方获取密钥q和s。接收方输入获取OPRF值。

KKRT16文献抽象的，其中,当具有足够的汉明距离时具有伪随机性。

针对单点OPRF的两个OPRF值的比较，我们可以描述为如下步骤：

（1）接收方R随机生成字符串,计算,y为比较元素。

（2）发送方S生成选择字符串。

（3）发送方S和接收方R执行K次base-ot，对于第i次OT:

--输入：发送方S输入第i个选择比特s[i]，接收方R输入第i对消息

--输出：发送方S输出

K次base-ot后，发送方获得

（4）OPRF值比较：接收方R元素y的OPRF值计算为,发送方元素x的OPRF值计算为，当且仅当x=y时。

多点OPRF(CM20)[7]: 多点OPRF的目的是为了消除发送方的每个元素需要OPRF评估多次的计算和通信开销，使得发送方的每个元素只需要评估一次。

单点-OPRF(KKRT16)：由于每一行的密钥均不同，若直接采用单点-OPRF进行元素比较，则发送方的每个元素需要OPRF评估n次(n为接收方集合大小)如图2-7步骤1。

图2-7：OPRF值评估数量

Cuckoo+单点-OPRF(KKRT16): 采用cuckoo-hash后，发送方的每个元素需要OPRF评估hash函数个数+stash大小，如图2-7步骤2。

多点OPRF(CM20)主要思想是将密钥替换为一个大小为m*k的矩阵M。多点OPRF表示为。

针对多点OPRF的两个OPRF值的比较，我们可以描述为如下步骤：

（1）接收方R随机生成一个m*k的矩阵A,m为集合大小。对于元素x，计算F(x)=v，将设置为0,得到m*k矩阵B'，然后将矩阵A和矩阵B异或得到矩阵B。此时矩阵A和矩阵B在位置的比特值相同，而其它位置相反。

（2）发送方S生成选择字符串。

（3）发送方S和接收方R执行K次base-ot，对于第i次OT:

--输入：发送方S输入第i个选择比特s[i]，接收方R输入第i对消息向量

--输出：发送方S输出

K次base-ot后，发送方获得m*k矩阵C

（4）OPRF值比较：接收方R元素y的OPRF值计算为,发送方元素y的OPRF值计算:首先计算F(y)=u，然后计算，当且仅当x=y时。

KKRT16 和 CM20通信分析：

2.2.2VOLE类-OTE构建

VOLE类-OTE由两阶段组成[13]：第一阶段为函数秘密共享：参与方之间交互分布式生成的秘密共享，其中标量只有发送方知晓，随机稀疏向量e只有接收方知晓。目的：双方获得相关性长向量。第二阶段为LPN扩展：参与方在无任何交互下本地扩展共享值，将的秘密共享值与公共矩阵G相乘得到的秘密共享值。目的：双方获得伪随机相关长向量。VOLE类-OTE示意图如图2-8所示:

图2-8VOLE类-OTE示意图

VOLE类-OTE构建OPRF的过程[8]也相对简单，如图2-9所示，构建过程如下：

--双方执行VOLE后发送方获得伪随机长向量W和标量，接收方获得伪随机长向量U,V。

--接收方对其集合Y执行不经意键值对存储(Oblivious key-value store,OKVS)(将在下一节介绍几种常见的OKVS)得到编码向量OKVS.enc(H(Y)),采用U盲化得到U'=U+OKVS.enc(H(Y))，将U'发送给发送方。

--将上述伪随机相关长向量解释为OPRF：

接收方输入元素，输出OPRF值

发送方定义密钥

和OPRF函数

图2-9 VOLE类-OTE构建OPRF示意图

VOLE-OTE与IKNP-OTE比较：参与方执行k次base-OT协议时，VOLE-OTE交换的是k个种子信息，而IKNP-OTE交换的是k个长为m(m>>k)的向量，这使得VOLE-OTE具有更低的通信开销，具体比较见表2-1（参考文献Boy19+b[13]）。但VOLE-OTE在函数秘密共享阶段计算复杂度较大，在LPN矩阵编码阶段也不能实现高效的计算。接下来将从函数秘密共享和LPN矩阵编码两方面介绍优化历程。

函数秘密共享：从分布式点函数（Distributed Point Function, DPF）到基于GGM-tree的分布式穿孔伪随机函数（Puncturable Pseudorandom Function, PPRF）优化。主要贡献为降低通信轮数和通信开销。

下面简单介绍基于GGM-tree构建的PPRF：

--参数:元素域,密钥空间,域.

基于GGM-tree的PPRF功能如下：

--输入:发送方输入和，接收方输入

--输出: 接收方输出穿孔密钥和

--要求发送方不知晓,接收方不知晓

如图2-10所示，具体步骤如下:

--发送方拥有密钥K，因此发送方可以通过随机生成器评估GGM-tree的每一个节点

--发送方和接收方并行执行l个:

--对于:

输入：接收方输入选择.发送方输入消息对,其中分别为GGM tree第i层的左节点异或，右节点异或组成。（由于发送方有,因此GGM tree任何一个节点的值都可以评估出来）

输出：接收方输出消息.

（如图2-10步骤1,接收方选择接收左消息，则接收方的左子树的任何一个节点的值都可以评估）

（如图2-10步骤2,接收方选择接收右消息，则接收方通过a3^b3^a3得到右节点b3,则以b3为根节点的所有子树可以评估计算）

--对于第l层:

输入：接收方输入选择（反转bit）。发送方输入消息对,其中分别为GGM tree第l层的左节点相加、右节点相加组成。

输出：接收方输出消息

（例如图2-10步骤3，接收方计算出b6）

--发送方发送给接收方（和上述OT并行）

--接收方本地计算穿孔密钥K{a},和秘密共享值t

（例如图2-10步骤4,接收方计算出秘密共享值t）

（例如图2-10步骤5,发送方拥有和,接收方拥有，由此得到相关短种子）

图2-10 基于GGM-tree的PPRF示意图

LPN矩阵编码：从dual-LPN矩阵编码到primal-LPN矩阵编码，以解决编码计算效率问题（因为dual-LPN矩阵为生成矩阵，是一个稠密矩阵需要大量的时间计算随机数，但在实际应用中却没有任何操作。而primal-LPN矩阵为奇偶校验矩阵，可以很好的解决上述问题）。dual-LPN和primal-LPN的简单原理如图2-11所示：

图2-11 dual-LPN与Primal-LPN等价示意图(摘自CRR21)[14]

基于VOLE的PSI协议通信分析：

2.2.3不经意键值对存储(OKVS)

并隐藏键信息的一类数据结构，其在PSI协议中主要有两点作用：

（1）降低通信开销的工具

（2）解决cuckoo table表无法抵御恶意攻击。

上述基于OTE构建PSI协议时，由于每一行的密钥均不同，若直接采用OPRF值进行元素比较，则发送方需要发送通信开销为(n为集合大小),接收方需要发送的通信开销为n如图2-12步骤1。用cuckoo-hash后，发送方需要发送通信开销为hash函数个数*n+stash大小*n,接收方需要发送的通信开销为1.2n（1.2为cuckoo表膨胀系数）如图2-12步骤2。而采用OKVS时，发送方需要发送通信开销为n,接收方需要发送的通信开销为rn（r为OKVS的膨胀系数），如图2-12步骤3。

图2-12不同数据存储结构下PSI参与方的通信开销示意图

针对现存的OKVS依据膨胀系数(数据结构大小与集合大小的比较)、编码时间、解码时间比较对其进行比较：

接下来简单介绍2H-GCT[15]和RR22[9]两种高效OKVS的实现方式：

2H-GCT采用先剥离再填充的思想进行编码，如图2-13所示：

（1）Peel:采用两个hash函数和键构造Cuckoo 图。如步骤1所示

（2）fill: 初始化栈P。寻找S中度为1的节点,然后将其进栈P。对于节点(m为向量S的长度),如果则其为单节点:然后将入栈P.如步骤2所示，节点s[2]仅被一个超边接触，则将其入栈，并在图中消除该超边。以此规则元素依次入栈P

（3）peel:对栈P中的元素依次出栈，并按的方式填充编码向量S.如图2-13步骤3所示

图2-13 2H-GCT算法简单示意图

针对2-core问题：指步骤2剥离到最后图中剩下的所有节点的度至少为2。解决方式：定义数据结构S=L||R，其中L由图的节点组成，R为额外增加的节点再采用高斯消去法消去（n表示2-core中的节点数量，d(n)为上限）。具体步骤如下：

--参数：哈希函数:,随机函数:l(·),r(·)，其中l(x)输出长度为m的位向量除外的其它位置为0，r(x)输出长度为r的随机位向量

--初始化：初始化向量和。初始化栈P

--度为1节点入栈：(识别仅被一个超边接触过的节点,然后将其进栈P)(peel):对于节点,如果是单节点:则将入栈P

--2-core节点:对于:求解,将解分配给S中相应的位置.（对于2-core中的节点，将值设置在L中的2个节点和R中的一个节点）

--peel:当P为不为空时：

(a):从P中出栈

(b):L至少在中的某个位置为空，设置为.(对度为1的节点，将值设置在L中的三个节点)

--对于L和R中为空的位置随机选择随机数填充.输出向量S=L||R

OKVS（RR22[9]）采用最简行阶梯形矩阵快速求解线性方程组的思想获得编码向量：

回顾OKVS的定义，求解得到编码向量P，其中P隐藏键的信息。是一个矩阵A，P和为m维向量V。因此可将上述方程理解为如何快速求解线性方程组，其中A和V已知。

化最简行阶梯形解过程如下：

--行阶梯形：找一个可逆矩阵B'，使得B'A为行阶梯形，则方程组化为

--行最简形：找一个可逆矩阵B''，使得B'AB''为行最简形，则方程组化为。先求的解P'再求P=B''P'.

OKVS（RR22[RR22]）的具体步骤如下：

（1）选取函数和将集合映射为矩阵H,其中前m'列是稀疏矩阵，元素全为0或1, 每行有w个1, 其余为0. 后列为稠密矩阵,元素属于域F。

（2）H行阶梯形：下三角化：对H进行一系列行置换和列置换，使得F为下三角矩阵。零化C：要求B为可逆矩阵，乘以可零化C。最终达到H为近似行阶梯形矩阵

（3）H行最简形：对稠密矩阵B实行行变换，找到可逆矩阵乘以H可将B转为行最简型。由此得到行最简矩阵H。

（4）将对H的操作重新作用于向量V

（5）反向传播求解出向量P

2.3 FHE-PSI

基于FHE的PSI协议采用全同态加密保证PSI协议的安全性，并利用同态加密密文运算和明文运算等价的特点实现PSI功能。FHE-PSI协议常见于非平衡场景，即接收方集合大小远小于发送方集合大小。因为现有基于OTE的高效PSI协议，其通信开销始终与参与方的最大集合呈线性相关，而对于非平衡场景，应尽可能的使通信开销和小集合大小相关。当结合离线-在线技术、PSI常见优化技术(OPRF、Hash to bin、Partition)及同态加密一系列优化方式(Batching、Window\Extremal postage stamp bases、Paterson-Stockmeyer、Depth-free homomorphic Frobenius automorphisms、Modulus switch)时，可以使基于FHE实现的PSI协议在非平衡场景下计算性能和通信开销优于基于OTE的PSI协议。本小节将首先介绍基于FHE的PSI协议基础构造思想，然后依次介绍CCS17[16]、CCS18[17]、CCS21[18]的优化。

简单介绍基于FHE的PSI协议构造基本思想如下：

上述方案共次同态乘法与加法， FHE密文通信开销，一轮通信，从通信复杂度看，协议的性能是可观的。但直接采用上述方案会带来两个问题：（1）一个FHE密文大小远大于元素大小，导致通信开销大（2）第三步计算中，发送方需执行高幂次同态计算，使得电路深度与发送方集合大小相关，导致协议性能差。

优化(CCS17[16])：

（1）Hashing to shorter strings:

依据统计安全参数和集合大小将元素hash到较小字符串，是PSI协议中一种常见提高性能的方法。半诚实模型，缩短的元素长度至少为。恶意模型下缩短的元素长度至少为计算安全参数.

（2）Cuckoo hash:

cuckoo hash也是PSI协议中一种常见降低通信的方法。接收方采用cuckoo hash将元素映射到cuckoo表，发送方采用simple hash将元素映射到simple，hash映射保证若发送方和接收方具有同一元素则必定映射在同一行。这一特性将基于OTE-PSI的通信开销从O(n*n)下降到O(n)，而在FHE-PSI协议中这一技术将帮助在第3步中对接收方集合执行批处理操作的同时对接收方的集合执行批处理操作，通过两者的结合使通信和计算开销降低n(SIMD大小)倍。

简单介绍cuckoo hash思想：对于元素e的插入：计算h1(e)和h2(e),若T[h1(e)]或T[h2(e)]中任意一个位置为空，则将元素e插入到空的位置(T为cuckoo表)。若均不为空则随机选择一个位置，替换原有元素e'插入e.再对e'执行上述操作。若如此循环t(阈值)次，则将第t个插入元素放入stash中。

simple hash思想：对于元素e的插入：计算h1(e)和h2(e),将元素e插入T[h1(e)]和T[h2(e)]中(T为simple表)

图2.3-1 cuckoo hash和simple hash插入示意图

（3）Batching：

将多个元素打包为一个明文多项式的过程称为SIMD编码，后续执行密文加或密文乘时只需对一个明文多项式操作实现多个元素的批处理操作，是FHE的常见优化操作。一个明文多项式的大小n={4096,8192,16384}。通过此批处理将通信开销从下降到,发送方的多项式求值电路计算深度从下降到。

（4）Window/Extremal postage stamp bases：

接收方计算Enc(X)=C的更多次幂发送给发送方。减少发送方的乘法深度和设置的加密参数大小。例如：，通过上述幂可计算出。

（5）Splitting

发送方将Simple hash表B按列划分a份即B[i,1],...,B[i,a],1≤i≤m,1≤a≤3.。且限制每份的列数最大为B’。将a个多项式发送给接收方。虽然通信量增加了a倍，但可以减少加密参数的大小，其作用是降低电路深度。

（6）Modulus switching：

FHE技术中常用于降低密文噪声，以此降低密文大小和降低通信开销。假设原始密文通过模转换后密文，其中

优化(CCS18[17]):

（1）OPRF预处理

使用OPRF更新交集，其中只有发送方知道key。其作用是保证发送方的集合被保密,抵御恶意接收方。（1）无需在FHE中执行 noise flflooding，因此可以高度优化FHE参数，提高性能和通信开销（2）hash不需要填充虚拟元素（3）发送方构建的多项式不需要添加随机值。

优化(CCS21[18]):

（1）Paterson-Stockmeyer

采用Paterson-Stockmeyer算法计算多项式，可优化通信和计算开销。

另外基于FHE的PSI协议当携带label时，可以作为keyword-PIR协议，如图2.3-2所示，将离线和在线计算做了区分示意：

图2.3-2带label-PSI协议离线-在线示意图

2.4 Circuit-PSI

Circuit-PSI指允许一组参与方计算交集，最终交集结果未泄露给任何一方，而是在参与方之间秘密共享，保证元素信息、交集基数等均未被泄露。其后可在秘密共享的交集结果上执行求势、求交集和、门限等功能，但不泄露交集信息。此类PSI协议虽然通信、计算、内存开销较大，但可在交集秘密共享上执行任意的对称函数计算。

本文展示一个基于OPRF和OKVS实现Circuit-PSI的通用框架，如图2.4-1所示,步骤如下：

（1）双方执行OPRF: 接收方输入集合Y输出OPRF值集合F。发送方输出OPRF密钥k。

（2）发送方执行OKVS编码，以为键，为值进行OKVS编码得到向量P

（3）接收方执行OKVS解码，输入键输出值,计算。(如果,则)

（4）双方执行两方电路协议：首先比较然后计算,并发送给双方。()

图2.4-1基于OPRF和OKVS实现Circuit-PSI的通用框架

2.5 对比分析

理论开销比较：

小集合(n<512)下ECDH-PSI的通信开销更小、 大集合下VOLE22的通信开销更小。

实验比较：

注：

（1）ECDH(隐语)对椭圆曲线进行优化、并支持一次运算8个ecc点乘

（2）AES计算优化(KKRT16(隐语))：EMP-tool的ParaAES可实现利用inter的VectorAes实现一次计算多组aes计算

（3）LPN生成矩阵(VOLE22)：

QuasiCyclic：具有拟环结构的生成矩阵G已被充分验证为可抵御后量子的LPN假设

Silver：具有最大最小距离编码的生成矩阵G.还在试验阶段

3

多方隐私集合求交

严格的多方隐私集合求交(Multi-party Private Set Intersection,MP-PSI)允许一组参与方输入私有集合，共同计算集合交集，保证仅能获取多方交集，并抵御m-1方合谋。MP-PSI相较于两方PSI需要额外关注通信结构、抵御多方合谋技术。现有高效的MP-PSI协议采用星型网络结构进行通信：减少参与方之间的中间交流，但给中心方带来了很高的通信要求。抵御多方合谋技术主要分为有条件零共享、无条件零共享、阈值同态加密，元素加密原语和打包技术两方PSI协议中已介绍。因此可将现有MP-PSI的实现分为OPPRF+零共享框架和阈值同态加密框架。接下来将分别介绍两类框架：

OPPRF+零共享框架[KMPRT17][GPR21][NTY21][19]：

不经意可编程伪随机函数(Oblivious Programmable Pseudo-Random Function, OPPRF)：由OPRF和OKVS构建，使其具有OPRF的安全性和OKVS的可编程性。OPPRF的功能如图3-1所示：发送方OPRF阶段获得元素的加密值。OKVS阶段，发送方将编程值采用加密值盲化后作为OKVS-value,元素作为键，执行OKVS编码得到向量P。最后将P发送方给接收方，接收方对元素解码得到value,如果，则value等于然后异或得到可编程值。

图3-1 OPPRF功能示意图

MP-PSI框架如下,如图3-2所示：

（1）抵御多方合谋技术：所有参与方执行零共享协议，获得抵御多方合谋盲化因子。零共享协议分为有条件零共享和无条件零共享。

（有条件零共享）：-参与方为其每个元素生成m+1个秘密共享值其满足。

-参与方与每一个执行OPPRF协议:

输入:输入键值对,输入ID集合

输出:输出OPRF密钥k,输出OKVS解码值，如果，则value等于然后异或得到可编程值。

-执行完m-1次OPPRF值后，如果为交集元素则有条件零共享值为否则为随机值。

（无条件零共享）：-参与方给每一个(j<i)随机采样并发送给。

-参与方计算盲化种子。

-参与方的元素的无条件获得零共享值为。

（2）加密原语技术：参与方与其它参与方分别执行OPPRF协议：

输入:输入键值对,输入ID集合

输出:输出OPRF密钥k,输出OKVS解码值，如果，则value等于然后异或得到可编程值。

-如果为交集元素，则否则为随机值。

图3-2：OPPRF+零共享框架

阈值同态公钥加密框架[BEHSV21][HV17][20]：

（1）抵御多方合谋技术TPKE.GEN(): --参与方拥有一个私有的加法同态阈值公钥加密方案的秘密共享私钥。所有参与方采用同一公钥PK。

（2）加密原语TPKE.ENC()：

--参与方采用公钥加密元素得到发送给中心方

--中心方同态计算所有参与方发送的加密值得到，并将C进行广播

（3）部分解码TPKE.ShDec():

--参与方采用私钥对C进行部分解密得到,将发送给

（4）组合TPKE.comb():

--参与方计算comb()如果结果为0则为交集

图3-3：阈值同态公钥加密框架

4

总结与展望

隐私集合求交作为一项典型的隐私保护分布式计算技术，在金融、医疗、交通、政务等诸多领域具有广泛应用场景，深受学术界和工业界的关注。金智塔科技有限公司作为隐私计算行业领先服务商，目前已开发部署两方-PSI协议（ECDH-PSI、VOLE-PSI），并基于OPPRF+零共享框架开发部署多方-PSI协议（a. 适用于小集合多参与方的MP-PSI协议（ECDH+OKVS+零共享实现），b. 适用于大集合少量参与方的MP-PSI协议（VOLE+OKVS+零共享实现））。未来，金智塔科技有限公司将继续挖掘隐私集合求交场景并开发高效的专用算子，例如阈值交集PSI、超阈值交集PSI、Circuit-PSI等。

5

参考文献

[1]崔泓睿, 刘天怡, & 郁昱. (2019). 带隐私保护的集合交集计算协议的发展现状综述. 信息安全与通信保密, (3), 48-67.

[2]魏立斐, 刘纪海, & 张蕾. (2022). 面向隐私保护的集合交集计算综述. 计算机研究与发展, 59(8), 1782-1799.

[3] Rosulek, M., & Trieu, N. (2021, November). Compact and malicious private set intersection for small sets. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (pp. 1166-1181).

[4]《Private set intersection with ECDH》，2020年06月19日， https://blog.willclark.tech/tech/2020/06/19/psi-with-ecdh.

[5]《隐语PSI benchmark 白皮书，新鲜出炉》，2022年11月08日https://mp.weixin.qq.com/s/TvY4morH-dRsaCm5JI6eig

[6] Kolesnikov, V., Kumaresan, R., Rosulek, M., & Trieu, N. (2016, October). Efficient batched oblivious PRF with applications to private set intersection. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (pp. 818-829).

[7] Chase, M., & Miao, P. (2020). Private set intersection in the internet setting from lightweight oblivious PRF. In Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part III 40 (pp. 34-63). Springer International Publishing.

[8]Rindal, P., & Schoppmann, P. (2021, June). 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 (pp. 901-930). Cham: Springer International Publishing.

[9]Rindal, P., & Raghuraman, S. (2022). Blazing Fast PSI from Improved OKVS and Subfield VOLE. IACR Cryptol. ePrint Arch., 2022, 320.

[10]Bui, D., & Couteau, G. (2022). Private Set Intersection from Pseudorandom Correlation Generators. IACR Cryptol. ePrint Arch., 2022, 334.

[11]Ishai, Y., Kilian, J., Nissim, K., & Petrank, E. (2003, August). Extending Oblivious Transfers Efficiently. In Crypto(Vol. 2729, pp. 145-161).

[12]Kolesnikov, V., & Kumaresan, R. (2013). Improved OT extension for transferring short secrets. In Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II (pp. 54-70). Springer Berlin Heidelberg.

[13]Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Rindal, P., & Scholl, P. (2019, November). Efficient two-round OT extension and silent non-interactive secure computation. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (pp. 291-308).

[14]Couteau, G., Rindal, P., & Raghuraman, S. (2021, August). Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes. In Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part III (pp. 502-534). Cham: Springer International Publishing.

[15]Garimella, G., Pinkas, B., Rosulek, M., Trieu, N., & Yanai, A. (2021). Oblivious key-value stores and amplification for private set intersection. In Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part II 41 (pp. 395-425). Springer International Publishing.

[16]Chen, H., Laine, K., & Rindal, P. (2017, October). Fast private set intersection from homomorphic encryption. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security(pp. 1243-1255).

[17]Chen, H., Huang, Z., Laine, K., & Rindal, P. (2018, October). Labeled PSI from fully homomorphic encryption with malicious security. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (pp. 1223-1237).

[18]Cong, K., Moreno, R. C., da Gama, M. B., Dai, W., Iliashenko, I., Laine, K., & Rosenberg, M. (2021, November). Labeled PSI from homomorphic encryption with reduced computation and communication. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security(pp. 1135-1150).

[19]Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., & Trieu, N. (2017, October). Practical multi-party private set intersection from symmetric-key techniques. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security(pp. 1257-1272).

[20]Bay, A., Erkin, Z., Hoepman, J. H., Samardjiska, S., & Vos, J. (2021). Practical multi-party private set intersection protocols. IEEE Transactions on Information Forensics and Security, 17, 1-15.

（本文来自金智塔科技投稿）

END

往期推荐

1.FedPAC | 概率近似正确联邦学习
2.Turbospeedz: 使用函数相关预处理技术提高SPDZ协议在线效率3.中国密码学会及各分支机构2023年主要学术活动计划4.笔记分享 | 冯登国院士MPC讲座（2）——基于秘密分享方法的安全多方计算协议