一、理论基础-PSI

之前参加了隐语第2期，对隐语SecretFlow框架有了大致的了解，这次参加隐语第4期，学习下PSI和PIR。

一、PSI定义

首先介绍PSI的定义，PSI（隐私集合求交，Private Set Intersection即PSI)是安全多方计算（Multi-Party Computation，MPC）领域的一类专有协议，针对两个或以上参与者之间私有集合共同计算集合交集，参与者之间只能看到共同交集的内容，而无法看到交集以外的内容，从而保证参与者交集以外元素信息的泄露。

二、分类

在分类上，根据参与者数量不同，一般分为两方和多方，两方只需保证两者的交集元素信息可共同计算即可，而多方则需保证所有参与者之间的交集元素可见，其中任意两者的交集元素信息是不包含在PSI内的。

在这里插入图片描述根据对交集的重解释下可分为传统交集PSI、阈值交集PSI、超阈值交集PSI

在这里插入图片描述另外，如果从敌手行为方式来分的话，还可以分为半诚实安全PSI协议、恶意安全PSI协议，这两个敌手行为方式基本是密码学分析安全性经常用的两种模型。

半诚实安全：参与者在交互时能够严格遵守并执行双方的协议，但会主动收集和分析协议消息
恶意安全：攻击者可任意偏离协议规则执行协议。

目前在两方半诚实安全PSI协议中有三个问题：

隐藏非交集元素。在 PSI 协议中，任何非交集的元素（即集合 $X$ 和 $Y$ 中 $X \cap Y$ 的元素）都必须对对方保持隐私。这要求协议能够有效隐藏非交集元素的内容，防止它们被推断或计算。如果只是仅简单地传输数据进行比较地话，攻击者可能通过暴力攻击如穷举法或数据推测来恢复非交集元素，造成数据泄露，特别是对一些低熵数据（身份证号、手机号等），这种攻击成功率很高。可以引入单项哈希函数、伪随机函数、差分隐私等来避免非交集元素信息泄露
单向哈希函数：
- 将元素通过加密哈希映射到随机值，以隐藏其原始内容。
- 哈希函数的单向性能够确保对方无法反推出原始数据。
伪随机加密：
- 使用伪随机生成器对非交集元素加密，增加其不可预测性。
差分隐私结合：
- 对非交集元素的处理加入噪声，降低推断可能性。
确保只计算交集元素。在进行交集计算时，需要满足3个条件，一是在密码学安全的前提下，协议需要确保只有相等的而元素才能被标记为交集；二是在交集计算过程中要避免附加信息泄露，不能泄露元素的额外属性或关联信息；三是要避免参与方伪造数据进行攻击，破坏交集的真实性和机密性。一般也有以下三种方法：

基于 Diffie-Hellman 密钥交换的比较：
- 通过加密和交换密钥确保交集元素的验证，仅当密钥匹配时才能揭示相等性。
基于 Oblivious PRF（OPRF）的比较：
- 使用 OPRF 对每个元素进行伪随机映射，然后比较映射值是否相等。
- 这种方法避免泄露原始值，且计算高效。
零知识证明：
- 双方可通过零知识证明协议证明交集元素的相等性，而无需披露其内容。
效率问题。这个问题基本也是密码学面临的通用问题，目前密码学在实际应用中经常面临安全性和效率成本的平衡问题，既要适用于大规模数据集，能够处理百万甚至数十亿级别的数据，还要能够高效计算，降低通信开销。不同的角度也有不同的方法。
计算复杂度：Cuckoo Hashing 优化：
- 使用 Cuckoo 哈希将数据映射到多个小的哈希桶中，仅比较桶内元素。
- 减少了不必要的比较次数，提高效率。
通信开销：基于 OT-extension 的方法：
- 使用 OT-extension（如 IKNP 协议）减少 Oblivious Transfer 的通信开销。
计算效率：并行计算和硬件加速：
- 使用并行化的计算框架或硬件加速（如 GPU 或 FPGA）提高协议的计算速度。

三、技术路线

接下来是实现PSI的三个基本路线

1：基于Hash的PSI

原理：先利用哈希函数对输入数据进行转换，再通过参与者之间的交互式比较，得到哈希值相等的交集元素，算法如下：
输入：参与方A拥有的集合 $x_1,x_2,...,x_n$ ，参与方B拥有的集合 $y_1,y_2,...,y_n$ .
输出：集合的交集
$\begin{align*} &输入：参与方A拥有的集合x_1,x_2,...,x_n，参与方B拥有的集合y_1,y_2,...,y_n.\\ &输出：集合的交集\\ &1、A和B协商一个共同的哈希函数 \\ &2、A和B分别对各自的输入执行哈希运算，即U=H(x_1),...,H(x_n)、V=H(y_1),...,H(y_n)。\\ &3、A将U发送给B；B将V发送给A。\\ &4、A判断H(x_i)和H(y_i)是否相等。\\ &5、B判断H(y_i)和H(x_i)是否相等。\\ &6、如果哈希值相等，则A和B分别输出相等元素。\\ \end{align*}$
这种方法的优势是计算速度很快，只需哈希做比较即可，但只适用于高熵即无序混乱没有规律的数据，现实中大多数数据往往是有规律性的低熵数据，如身份证号、手机号、地址等。安全性上不够高，也无法防止暴力攻击，如果有攻击者通过伪造数据进行哈希比较那么就能推测出对方的数据。此外在通信上存在安全问题，如果遇到中间人攻击，也可能会泄露数据。

2：基于Diffie-Hellman Key Exchange的PSI

原理：利用Diffie-Hellman密钥交换协议在不安全的信道中协商一个会话密钥，并用该密钥加密通信内容。也就是双重加密，在哈希函数加密元素的基础上，再利用会话密钥再进行一次加密来保证这个会话信息的安全。算法如下：
$\begin{align*} &输入：参与方A拥有的集合x_1,x_2,...,x_n，参与方B拥有的集合y_1,y_2,...,y_n，A和B协商出的一个共同的哈希函数H\\ &输出：集合的交集\\ &1、A生成密钥a，并对自己的数据执行哈希运算，得到H(x_1),...,H(x_n)。\\ &2、B生成密钥b，并对自己的数据执行哈希运算，得到H(y_1),...,H(y_n)。\\ &3、A计算U=H(x_1)^a,...,H(x_n)^a，并将U发送给B。\\ &4、B计算V=H(y_1)^b,...,H(y_n)^b和U^{'}=H(x_1)^{ab},...,H(x_n)^{ab}，并将V和U^{'}发送给A。\\ &5、A计算V^{'}=H(y_1)^{ba},...,H(y_n)^{ba}。\\ &6、A判断H(x_i)^{ab}和H(y_i)^{ba}是否相等。\\ &7、如果计算值相等，则A和B分别输出相等元素。\\ \end{align*}$
这种方法的安全性是基于Diffie-Hellman的离散对数难题，在通信安全性上是有保障的。

成本：

计算开销：因为每个元素都要进行模幂运算（ $g^{x·a}$ mod $p$ ），随着集合大小的增加，指数计算次数呈线性增长，成本较大
通信成本:交换数据量与参与者所拥有的集合大小呈线程关系，计算复杂度一般是 $O (n)$ 级

目前这种方法也是使用比较多的。但是依然无法防止伪造数据的猜测碰撞攻击。此外，当参与者所拥有的数据量不平衡时，对于较大集合的参与者来说，效率可能比较低。

3、基于OPRF的PSI

在OPRF之前先讲下基于OT（Oblivious Transfer，不经意传输）的PSI。

OT最初在1981年由Rabin提出来时，是为了解决如下问题产生的：

Alice 拥有秘密 $S_A$ ，Bob 拥有秘密 $S_B$ 。Alice 和 Bob 想要交换秘密，要求两方都有可能得到秘密并且秘密拥有方不知道对方是否得到秘密。简单来说，在A向B传输时传输多条数据，实现A不知道B选了什么，B除了要获取的消息外，不知道A所传输的其他内容。

当参与方A和参与方B分别只拥有一个元素时，此时的隐私集合求交就变成了隐私等值比较；在不泄露用户隐私的情况下，比较双方持有的元素是否相等。假设A拥有 $x = 010$ ，B拥有 $y = 001$ ，隐私等值比较协议能够在不泄露各自输入的条件下比较 $x = y$ 这个等式是否成立。在仅有一个元素的情况下进行等值比较的核心思想是通过OT协议，对 $x$ 和 $y$ 进行逐比特位比较。

算法如下：
$\begin{align*} &输入：参与方A拥有x=010，参与方B拥有y=001，且x和y的比特串长度均为λ，k为安全参数\\ &输出：判断x=y是否成立\\ &1、B为数据的每一位生成两个长度为k比特的字符串（分别对应0和1，简称比特串），即λ个字符串对。\\ &2、A对需要比较的字符串x中的每一位使用OT协议，不经意地获取B地每个字符串对中地一个长度为k地比特串。\\ &3、A对收到的λ个比特串做异或操作，得到字符串K_x。\\ &4、B对其待比较字符串y中的每一位执行异或操作，得到字符串K_y并发送给A。\\ &5、A比较K_x和K_y。\\ &6、如果K_x=K_y成立，则x=y成立，否则x=y不成立。\\ \end{align*}$
采用OT协议在A和B之间不经意地传输数据，A（B）无法知道B（A）所拥有的数据。同时，应为采用异或操作得到B的字符串，A也无法反推出B的数据。

虽然借助OT协议能够显著提高PSI过程中的安全性，但也带来了效率低下的问题。例如，当两个参与方分别拥有n个数据时，如果借助隐私等值比较来实现n个数据间的PSI，那么就需要比较 $O(n^2)$ 次，并且每一次比较时都需要使用λ次OT协议来不经意地传输数据，计算开销显然是非常大的。

为了减少OT协议使用的次数，可以采用不经意伪随机函数（Oblivious Pseudo Random Function，OPRF）来构造隐私等值比较协议。将输入数据的二进制看作一个整体，在每次比较时只需要使用一次OPRF即可实现隐私等值比较。与每次比较使用λ次OT协议相比，OPRF通过不限制参与方输入字符的长度，从根本上减少了OT的使用次数。
在这里插入图片描述接收方输入数据 $x_i$ ,发送方输入密钥 $k_i$ ，在OPRF执行完毕后，接收方会收到 $x_i$ 的伪随机函数值，记为 $F(k_i,x_i)$ 。接收方能够在密钥 $k_i$ 的作用下，对其输入数据 $y_i$ 直接进行计算，产生 $F(k_i,y_i)$ 并发送给接收方。接收方通过比较 $F(k_i,x_i)$ 和 $F(k_i,y_i)$ ，即可实现隐私等值比较。在该过程中，接收方只能获取 $F(k_i,x_i)$ ，对密钥 $k_i$ 一无所知；同时，发送方对输入数据 $x_i$ 也一无所知。如果 $x \neq = y$ ，那么 $f(k_i,y_i)$ 对接收方来说是随机的。

这里基于KKRT16 $^{[1]}$ 的文章扩展下OPRF。这部分内容需要一些基础知识~，这篇文章里，作者提出了一种方法BaRK-OPRF（batched,related-key OPRF）

Oblivious Pseudo-Random Functions（OPRF），是一种改进的OPRF协议，基于IKNP OT-extension框架的优化，目标是在接收方能够计算 $F (s, r)$ 的情况下：

发送方拥有种子 $s$ ，从而能够评估伪随机函数$ F(s,\cdot)$的任何值；
接收方仅能获取其选择输入 $r$ 对应的伪随机函数值$ F(s,r)$，而无法推断其他值。

原理：

OT-extension 框架：
- 利用 IKNP OT-extension 扩展初始 OT 实例
- 接收方通过选择位 $r$ 生成矩阵 $T$ 和 $U$ ，满足：$ t_j \oplus u_j = r_j \cdot 1_k$
- 发送方选择随机种子 $s$ ，并通过 OT 交互获取矩阵 $Q$ ，其中： $q_j = t_j \oplus [r_j \cdot s]$
伪随机函数计算：
- 使用哈希函数 $H$ 计算伪随机值： $F((q_j, s), r) = H(q_j \oplus [C(r) \cdot s])$
伪随机编码：
- 替代传统错误校验码的伪随机编码 $C (r)$ ，满足最低汉明距离要求，从而提供安全性。

安全性上，发送方无法得知接收方的选择输入 $r$ ，接收方只能获得单个伪随机函数输出，无法推断其他值。

依赖假设：哈希函数的相关性鲁棒性和伪随机编码的汉明距离安全性。

在上述OPRF的隐私等值比较中，利用一次OPRF协议可以取代每次比较时使用λ次OT协议，效率得到提升。但是在n个数据间进行求交操作时，将接收方的每个数据和发送方的每个数据通过利用一次OPRF协议进行隐私比较的方式，得到两个集合的交集，其比较次数仍为 $O(n^2)$ 。

可以结合布谷鸟哈希，利用OPRF思想，能够将隐私集合求交的计算复杂度降低到 $O (n)$ 级。

在这里插入图片描述

算法如下：
$\begin{align*} &输入：参与方A持有的一组输入X，参与方B持有的一组输入Y，其中|X|=|Y|=n；A和B共同选择的3个哈希函数h_1、h_2、h_3。\\ &输出：集合的交集\\ &1、B对其持有的n个元素使用布谷鸟哈希，并入1.2n个桶与一个大小为s的储藏桶中；B构造假数据，将这些桶和储藏桶都填满，使每个桶中均有一个元素，且储藏桶中有s个元素。\\ &2、A产生1.2n+s个OPRF密钥k_i。\\ &3、B作为接收方，为其桶中的每一个元素执行OPRF。对于B的输入数据来说，如果y被放在i号桶中，则获得F(k_i,y_i)；如果y被放在储藏桶中的第j个位置，则获得F(k_{1.2n+j},y_{1.2n+j})。\\ &4、A作为发送方，为其输入x任意地计算伪随机函数F(k_i,\cdot)，得到以下两个集合：\\ &H={F(k_{h_{i}(x)})|x∈X,i∈{1,2,3}}\\ &S={F(k_{1.2n+j},x)|x∈X,j∈{1,2,...,s}}\\ &5、A将集合H和集合S中地元素打乱，并发送给B。\\ &6、对于B来说，如果一个元素y被映射到储藏桶中，则B可以在集合S中查找是否包含y对应的OPRF输出；否则，就在集合H中查找。\\ &7、B通过查找地方式得到X与Y的交集\\ \end{align*}$
在这个算法里，集合H的大小为3n，集合S的大小为sn，因此A和B之间的通信开销为（s+3）n，比较计算的复杂度将为 $O (n)$

四、应用

比较简单的一个就是黑白名单的对比，在多个组织之间通过PIS来对比验证黑名单（欺诈账户列表）、白名单合法用户，而无需泄露各自的信息。

也可以通过PSI来进行数据库的撞库，来进行比如密码是否匹配一致。

比较大的场景应用是联邦学习数据集的处理，在联邦学习中，通常需要受限对数据进行对齐，而PSI及其变体就可以在联邦学习的数据对齐的过程中，不透漏给对方额外信息的情况下对齐数据，从而保护隐私。

另外一个应用是在可搜索加密场景中保护查询模式和访问模式，可搜索加密允许用户将加密数据上传后，向不可信的服务器发起查询请求，在密文环境中进行搜索，并保证查询的正确性和数据的安全性。但实际上，在交互过程中或多或少会泄漏一些查询模式和访问模式给服务器来完成查询或者加快查询任务速度，目前许多工作表明，只要有部分的查询模式或访问模式，并对数据库有一部分的先验知识，云服务器就可以恢复用户的查询隐私或最终的结果。为了避免这个问题，就可以利用PSI的安全性来保护查询模式和访问模式

五、PSI和其他隐私计算技术结合

PSI严格上来说属于安全多方计算的内容，也可以和其他隐私计算技术结合起来进行互补，如差分隐私、TEE等。
1、安全求交集+差分隐私
通过差分隐私给元素信息添加噪音，在保护交集中的个体的同时但不影响交集整体的统计属性
2、安全求交集+可信执行环境
TEE是一种硬件隔离环境，能够在硬件级别的安全性

TEE 创建 Salt（随机盐值）：
- TEE 内部生成一个随机的 salt，用于对参与方的数据进行哈希操作。
- 该 salt 在 TEE 内部是安全的，未被外界泄露。
参与方对数据加盐后哈希：
- 各方使用 TEE 生成的 salt 对各自的数据集合进行哈希处理。
- 加盐哈希确保即使数据相同，外部无法直接推测出原始数据。
TEE 内完成 PSI 计算：
- 各方将加盐后的哈希值上传到 TEE，TEE 内部通过比对哈希值完成 PSI 计算。
- 交集计算仅发生在 TEE 内，数据在 TEE 外部始终是加密或哈希形式。
结果返回参与方：
- 交集结果从 TEE 返回给参与方。
- TEE 可以配置为只返回交集统计信息（如交集大小），或返回完整的交集内容。

六、References

[1]Kolesnikov V, Kumaresan R, Rosulek M, et al. Efficient batched oblivious PRF with applications to private set intersection[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016: 818-829.