学习&转载文章：安全多方计算(5)：隐私集合求交方案汇总分析
前言
随着数字经济时代的到来，数据已成为一种基础性资源。然而，数据的泄漏、滥用或非法传播均会导致严重的安全问题。因此，对数据进行隐私保护是现实需要，也是法律要求。隐私集合求交（Private Set Intersection, PSI）作为解决数据隐私保护的方案之一，受到广泛关注和研究。
隐私集合求交使得持有数据参与方通过计算得到集合的交集数据，而不泄露任何交集以外的数据信息，其功能如图1所示。作为安全多方计算中的一个重要分支，其不仅具有重要的理论意义，也具有广泛的应用场景。例如：隐私保护位置共享[1]、在线广告的有效转换率衡量以及基于人类基因组序列[2]的亲子鉴定、疾病预测和血统测试等。
图1 隐私集合求交功能示意图
PSI分类
隐私集合求交的研究主要聚焦在两个参与方，因此，本文主要针对两方隐私集合求交进行阐述。两方PSI可根据参与方的数据集大小分为三类，如图2所示。根据双方数据集大小差异可将其分为对称数据集和非对称数据集（非平衡），对于对称数据集，又可分为大数据集和小数据集。本文针对对称数据集及不同场景的需求，介绍与之对应的隐私集合求交方案。
图2 隐私集合求交分类示意图
- 小集合：百
- 大集合：百万
- 非对称：100亿
PSI方案介绍
基于DH的PSI方案
基于DH的PSI方案[3]流程如图3所示，该方案基于DH密钥交换的思路，实现两次可以交换加密顺序的加密操作，使得参与双方对于交集数据，得到完全相同的不可逆密文。
图3 基于DH的PSI方案流程示意图
基于DH的PSI方案主要分为以下3个步骤：
这里所谓说的“公钥加密”，公钥是:\((H(x)^a)^b\)
-
Alice选择随机数\(s\)作为私钥。对于每一个数据\(x\)，Alice首先对其进行哈希操作，再基于其哈希值使用私钥对其加密，生成密文，并将此密文发送给Bob。
-
Bob选择随机数\(b\)作为私钥，对于每一个数据\(y\)，Bob首先对其进行哈希操作，再基于其哈希值使用私钥对其加密，并将此密文发送给Alice。对于接收到Alice的密文，Bob使用私钥对其进行二次加密。
-
Alice对于接收到的密文，基于私钥对其进行二次加密
结论：若Alice和Bob拥有相同的数据，则两次加密得到的密文一致。
- 以上实际上就是基于DH实现的OPRF。
基于DH的PSI方案思想简单，易于实现，但也具有一定的局限性，例如：基于公钥加密实现PSI功能会产生较大的计算开销。因此，适用于数据量较小的场景。
- 基于公钥加密的PSI会产生较大的计算开销。
基于OT的PSI方案
预备知识
不经意传输（Oblivious Transfer, OT）[4]是安全多方计算最基础的协议之一，在之前的文章中已做了详细介绍安全多方计算(1)：不经意传输协议。
本部分我们仅使用了2选1的不经意传输协议，其功能如图4所示。Alice有两条消息，Bob可以通过比特\(b\)获取消息，而无法获得的任何消息。Alice无法获得关于\(b\)的任何信息，即：Alice不知道Bob获取了哪条消息。
图4 不经意传输功能示意图
方案详解
在本部分，我们简述经典的基于OT的PSI方案，其流程如图5所示。该方案的核心思想为执行多次二选一的不经意传输协议，并结合伪随机函数，使得参与双方对于交集数据得到相同的随机数。
图5 基于OT的PSI方案流程示意图
基于OT的PSI方案主要分为以下4个步骤：
-
Alice生成随机数\(w\)；Bob生成随机数\(r_0\)，并基于与本方数据的伪随机函数值生成\(r_1\).
-
Alice与Bob基于\(w\)和\(r_0,r_1\)执行次二选一的不经意传输，其中\(\lambda\)为比特长度。
-
Alice基于多次不经意传输结果生成\(q\)，Bob计算\(r_0\)的哈希值。
-
Alice计算本方数据的随机值。
结论：若Alice和Bob拥有相同的数据，则两份数据得到相同的随机值，即\(\boldsymbol{x}_{\boldsymbol{j}}=\boldsymbol{y}_{\boldsymbol{i}} \leftrightarrow H\left(q \oplus\left(F\left(x_{j}\right) \cdot w\right)\right)=H\left(r_{0}\right)\)。
- 我们以两种极端情况论述方案的正确性：
图6 基于OT的PSI方案正确性验证
- 普通情况，假设\(w=010\)，则\(q=r_0[1]||r_1[2]||r_0[3]=r_0[1]||r_0[2]\oplus F(y_i)[2]||r_0[3]=r_0\oplus F(y_i)[2]\)，即\(q \oplus\left(F\left(x_{j}\right) \cdot w\right.)=r_0\oplus F(y_i)[2]\oplus F(x_j)[2]=r_0\)
- 以上推到不完全正确，欢迎交流～
基于OT的PSI方案规避了大量的公钥加密，使用效率更高的对称加密完成大部分操作，但通信开销较大，适用于数据量较大的场景。
经典的基于OT的PSI方案仍具有很大的计算开销及通信开销，但是OT的扩展协议为构建高效的PSI方案提供了理论支撑。在3.3中，我们以OPRF为例，介绍基于OT扩展协议的高效PSI方案。
基于OPRF的PSI方案
预备知识
不经意伪随机函数（Oblivious Pseudorandom Function, OPRF）[5]属于不经意传输的扩展协议，它允许执行少量的基础OT，通过轻量级的对称加密来实现大量的OT实例，OPRF的功能如图7所示。
对OPRF的定义是不对的，OPRF可以有多种方式实现，其中OT/OTE只是其中之一。
Alice生成伪随机函数的密钥\(k\)，可基于\(k\)获得本方数据\(x\)的伪随机函数值\(F_k(x)\)。Bob以本方数据\(y\)作为OPRF协议的输入，协议执行完成后，Bob可得到\(y\)的伪随机函数值\(F_k(y)\)，但无法获得关于\(k\)的任何信息。
图7 不经意伪随机函数功能示意图
方案详解
在本部分，我们简述基于OPRF的PSI方案[6]，其总体流程如图8所示。为便于阐述，我们将Alice作为数据拥有者，记为DO（Data Owner）；Bob作为请求者，记为Re(Requester)。
图8 基于OPRF的PSI方案总体流程示意图
我们将基于OPRF的PSI方案分为以下步骤进行阐述：
- 请求者（Bob）将数据映射：映射过程如图9所示。首先，请求者随机生成\(m\)行\(w\)列的二进制矩阵\(A\in (0,1)\)，其中\(m\)为数据集大小。对于每个数据，请求者计算其伪随机函数值，并将伪随机函数值与二进制矩阵A相结合，获取二进制比特串。同时，将对应位置标记为数据位（如图9中蓝色部分）。然后基于二进制比特串执行哈希操作，得到数据映射值【留着待比较】。
- 将\(v_i\)映射到\(A\)中，以下面为例：\(v_1[1]=3\)，则选择\(A_1[v_1[1]]=A[v_1[1],0]=0\)
图9 请求者数据映射流程图
- 请求者（Bob）生成矩阵\(B\)：请求者生成一个\(m\)行\(w\)列的全1矩阵\(D\in (1)\)，将第1步标记的数据位部分置为0【这里是两个数据\(x_1,x_2\)】。然后将矩阵\(A\)与矩阵\(D\)执行异或操作得到矩阵\(B\)。因此，矩阵\(A、B\)具有如下特性：矩阵\(A、B\)对于（标记的）数据位的比特值相同；对于（没有标记的）非数据位的比特值相反。这一步主要是为了二选一的不经意传输做准备。
图10 矩阵B生成示意图
- 数据拥有者（Alice）获得矩阵\(C\)：这一步的核心思想是请求者与数据拥有者执行\(w\)次不经意传输，其执行过程如图11所示。通过1、2步，请求者已获得\(A、B\)矩阵；在第3步，数据拥有者生成长度为\(w\)的二进制比特串【如何生成？】。在每一次OT执行中，请求者以\(A、B\)矩阵的第\(i\)列作为输入；数据拥有者以比特串\(s\)的第\(i\)位{\(s[i]\)}作为输入，若\(s[i]=0\)，则数据拥有者得到\(A\)的列；若\(s[i]=1\)，则数据拥有者得到\(B\)的列，最终数据拥有者得到矩阵\(C\)。矩阵\(A、B、C\)具有如下特性：此三个矩阵对于（标记的）数据位的比特值相同；而通过不经意传输，矩阵\(C\)的非数据位已被置乱。
图11 不经意传输执行示意图
- 数据拥有者（Alice）将数据映射，映射过程如图12所示。对于每个数据，这一步与第1步的流程类似，其目的是为了对于参与双方的交集数据生成完全相同的随机映射值。首先数据拥有者计算其本方数据的伪随机函数值，并将伪随机函数值与第3步得到的二进制矩阵C相结合，获取二进制比特串\(C_1[v_i[1]]||...||C_w[v_i[1]]\)，然后基于二进制比特串执行哈希操作，得到数据映射值【发送过去比较】。
图12 数据拥有者数据映射流程图
- 数据拥有者（Alice）将其本方所有数据映射值发给请求者，请求者对比两方数据映射值确定交集数据，而其不会获得数据拥有者的任何非交集数据信息。至此协议完成。
总结
本文介绍了基于两方对称数据集的三种隐私集合求交方案，其中基于DH的PSI方案适用于小数据的场景；基于OT的PSI方案适用于大数据集的场景，但其依然有较大的通信开销，因此，介绍了基于OPRF的PSI方案，其在计算开销和通信开销方面均具有良好的表现。
| 方案 | 效率 | 适合数据集 |
|---|---|---|
| 基于DH的PSI | 计算开销大 | 小数据集 |
| 基于OT的PSI | 通信开销大 | 大数据集 |
| 基于OPRF的PSI | 计算和通信均好 |
随着隐私计算技术的发展，多方及外包隐私集合求交方案也在被逐渐关注与研究，我们在后续文章中进行介绍。
参考文献
[1] NARAYANAN A, THIAGARAJAN N, LAKHANI M, et al. Location Privacy via Private Proximity Testing[C]//Proceedings of the Network and Distributed System Security Symposium, NDSS 2011, San Diego, California, USA, 6th February - 9th February 2011. 2011.
[2] SHAFIN K, PESOUT T, LORIG-ROACH R, et al. Nanopore sequencing and the Shasta toolkitenable efficient de novo assembly of eleven human genomes[J]. Nature Biotechnology, 2020(Suppl.2).
[3] Meadows C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party[C]//1986 IEEE Symposium on Security and Privacy. IEEE, 1986: 134-134.
[4] RABIN M O. How to Exchange Secrets by Oblivious Transfer[J]. Technical Memo TR-81, 1981.
[5] FREEDMAN M J, ISHAI Y, PINKAS B, et al. Keyword Search and Oblivious PseudorandomFunctions[C]//KILIAN J. Theory of Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg,2005: 303-324.
[6]CHASE M, MIAO P. Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF[C]//MICCIANCIO D, RISTENPART T. Advances in Cryptology – CRYPTO 2020. Cham: Springer International Publishing, 2020: 34-63.
标签：求交,方案,基于,PSI,汇总,Alice,隐私,Bob,数据 From： https://www.cnblogs.com/pam-sh/p/17001213.html