【关键词】：隐私凑集求交，安全多方打算，不经意传输
1 弁言隐私凑集求交（PSI）是安全多方打算（MPC）中的一种密码学技能，它许可参与打算的双方，在不获取对方额外信息（除交集外的其它信息）的根本上，打算出双方数据的交集。随着大数据，人工智能，云打算等技能的兴起，企业和个人对隐私数据的保护越来越重视。隐私凑集求交，作为安全多方打算中的关键技能，在近年来的理论研究也得到了长足的发展。
在数字经济的浩瀚安全威胁中，数据透露已成为环球范围高发的安全事宜之一，且这个趋势仍在持续。
在这些数据安全问题中，有人为缘故原由的故意透露，也有技能毛病导致的数据透露。数据隐私问题，直接影响着企业的利益和信用，乃至因此导致企业倒闭。
随着中国在信息化和数字化的持续发展，大量具有敏感性和私密性的个人和企业信息在互联网上传播。如何安全地利用这些信息为企业和个人供应便捷的做事，同时又能保障信息不在传输过程中被透露，对数字经济的康健发展，有着非常主要的浸染和意义。2021 年 6 月 10 日，十三届人大常委会第二十九次会议通过了《数据安全法》2021 年 8 月 20 日，十三届人大常委会第三十次会议表决通过《中华公民共和国个人信息保护法》。可以预见，对个人和企业隐私数据的保护，会被越来越多的企业和个人重视。我们通过对隐私凑集求交的现状和发展的综述，重点先容隐私凑集求交的技能事理，为建立企业和个人对隐私数据保护的重视和信赖，供应理论依据，并对隐私凑集求交的发展前景进行剖析，推进隐私打算的根本研究和商业运用发展。
2 根本原语2.1 安全模型安全模型又被称为对手模型或敌手模型，被用来衡量一个协议的安全等级。基于模型的安全假设，常日把安全模型分为老实（honest），半老实（semi-honest）和恶意（malicious）三种。
老实型对手会完备按照密码学的协议实行，并且不会主动考试测验获取额外的信息。半老实型对手会完备按照密码学的协议实行，但会尽可能考试测验从收到的信息中获取额外的信息。恶意模型不会严格按协议实行，他们可以做任何事情来达到获取额外信息的目的。迄今为止，隐私凑集求交的协议，大多基于对手模型是半老实模型的条件下进行的研究。对抗恶意模型的协议，虽然供应了更好的安全保障，但常日具有较为低下的实行效率 [8]。虽然半老实模型不能对协议的双方供应完备的安全保护，但基于半老实模型的协议的研究，可以为对抗恶意模型的协议，供应技能储备。并且基于对手模型为半老实模型的协议，可以通过合营诸如随机预言，惩罚性方法等多种技能手段，来达到靠近恶意模型下的协议的效果。
2.2 秘密共享秘密共享（Secret Sharing，SS）是将一份原始秘密信息，拆分成多份。再把多份数据，分给不同的用户持有。个中的任何一份数据，都不能够完备恢复原始的秘密信息。只有达到指天命量的用户，凑集他们手中持有的秘密，经由打算才能得出原始的秘密信息。秘密共享的关键在于秘密的拆分办法和规复方法。秘密共享已经成为密码学中的一个主要分支，是信息安全和数据保密中的主要手段，被广泛运用于电子支付，密钥托管和隐私保护领域。
2.3 同态加密同态加密（Homomorphic Encryption，HE）是将数据加密后，对加密数据进走运算处理，之后对数据进行解密，解密结果等同于数据未进行加密，并进行同样的运算处理。目前，同态加密支持的运算紧张为加法运算和乘法运算。按照其支持的运算程度，同态机密分为半同态加密（Partially Homomorphic Encryption, PHE）和全同态加密（Fully Homomorphic Encryption, FHE）。半同态加密在数据加密后只持加法运算或乘法运算中的一种，根据其支持的运算的不同，又称为加法同态加密或乘法同态加密。半同态加密由于机制相对大略，相对付全同态加密技能，拥有着更好的性能。全同态加密对加密后的数据支持任意次数的加法和乘法运算。
3 隐私凑集求交的紧张技能方案3.1 朴素哈希求交技能图 1 朴素哈希求交法
朴素哈希（simple hashing）求交技能 [1] 的事理是利用哈希函数，把凑集中的元素映射到一个均匀分布的空间。利用哈希函数的不可逆的性子，传输映射后的数据并进行比对求交。
朴素哈希求交法是一种非安全的求交方法。如果发送者 Alice 持有的数据集 X 的样本空间 Ω 较小（比如手机号码或特定的电子邮件等），那么 Bob 在吸收数据后，可以进行对样本空间内的所有数据进行哈希打算来破解。纵然要比对的数据拥有足够大的样本空间，朴素哈希求交法也并非绝对安全，吸收者 Bob 仍可以根据获取到的打算后的数据，判断 Alice 是否具有哪些特定的信息。
实际运用中，为了对抗彩虹表攻击，朴素哈希求交法一样平常会在运行时通信双方临时协商一个随机的盐值，在哈希打算时利用对应的盐值进行加盐哈希打算。加盐朴素哈希的隐私凑集求交一样平常过程为：
发送者 Alice 持有数据 X={x1, x2, ..., xm}, 吸收者 Bob 持有数据 Y={y1, y2, ..., yn}Alice 和 Bob 利用相同的哈希函数 HAlice 天生随机盐值 Salt 并发送给 BobBob 利用 salt 对所有 Y 进行哈希打算 hyi = H(yi, salt)Alice 利用 Salt 对所有 X 进行哈希打算 hxi = H (xi, salt), 并发送 hxi 给 BobBob 打算 {hx1, hx2, ..., hxm }∩{hy1, hy2, ..., hyn } 的结果为 Alice 和 Bob 数据的交集朴素哈希求交法，是目前 PSI 协议中，性能最优的协议。由于协议本身不具备安全求交能力，一样平常只能运用在特定问题下的非敏感数据的求交场景。
3.2 姚氏稠浊电路姚氏稠浊电路（Yao’s Garbled Circuits）[2] 协议由 1986 年由图灵奖得到者姚期智院士提出，用来办理著名的姚氏百万财主问题。稠浊电路利用布尔电路（与，或，非等）构建电路表，保障打算的过程中，双方的数据不被透露。终极根据稠浊电路的打算结果，以及稠浊电路表，可以打算双方数据的打算结果。
图 2 完全的姚氏电路 [2]
一个范例的姚氏稠浊电路的打算过程分为稠浊电路天生阶段，电路实行阶段和电路评估阶段。
稠浊阶段，Alice 天生一个布尔稠浊电路表，利用稠浊电路表为每个布尔值天生密钥。Alice 对稠浊电路的打算结果，利用布尔电路中对应的密钥进行加密，打乱顺序后和自己持有的数据 X 对应的密钥信息发送给 Bob。实行阶段，Bob 根据自己持有的数据 Y，通过 OT 协议获取稠浊电路表对应的密钥信息。Bob 利用自己持有的数据对应的密钥和 Alice 给的密钥对 Alice 发送过来的稠浊电路的打算结果进行解密，个中，只有 Alice 和 Bob 持有的数据对应的稠浊电路的数据，能够被正常解密。评估阶段，Bob 发送解密后的值给 Alice，Alice 对照稠浊电路打算结果，得出终极的打算结果。图 3 用于相等比较的稠浊电路设计
稠浊电路的设计不仅可以运用在隐私凑集求交的数据相等的比较场景，也可以运用于安全的数据大小比较，模糊查询等场景。 基于稠浊电路的方案相较于热门的基于不经意传输的方案在性能上处于劣势，且同样基于半老实的对手模型，使得此方案目前在实际运用中利用较少。
3.3 基于同态加密图 4 基于全同态加密的隐私凑集求交协议 [5]
2017 年，Hao Chen 等人，给出基于全同态加密（FHE）的隐私凑集求交方法 [5]。基于同态加密的隐私凑集求交方法紧张是对数据进行同态加密，并利用加密后的数据和原始数据构建多项式并打算多项式的值。其紧张步骤为：
发送者 Alice 持有数据 X={x0, x1, ..., xn-1}, 吸收者 Bob 持有数据 Y={y0, y1, ..., ym-1}Bob 天生同态加密密钥，并对凑集中的所有数据进行全同态加密天生新的凑集 C = {c0, c1, ..., cm-1}Alice 天生随机一组随机数 R，并利用如下公式来打算多项式的值。Alice 将打算结果的数据集 {d0, d1, ..., dn-1} 发送给 BobBob 对数据集进行解密，网络所有解密结果为 0 的数据，即是数据集 X 与数据集 Y 的交集。在交互过程中，Alice 收到的是同态加密后的数据，以是 Alice 不知道 Bob 的数据集 Y 的信息。Bob 收到的是经由多项式打算后的同态加密数据，如果解密后的结果为 0，Bob 知道对应的数据存在于 Alice 的数据集 X 中，否则解密后的数据对付 Bob 来说是一个随机数。
在上述过程中，Bob 对数据集 Y 内的所有数据进行同态加密，Alice 打算高阶多项式，和 Bob 对多项式打算结果进行解密是方案中对性能负面影响较大的行为。在 Chen 等人的方法中，针对这些问题进行了一些列的优化处理，个中包括利用布谷鸟哈希方法和批处理同态加密，降落协议的打算开销和通信开销。利用分窗的方法来加速高阶多项式打算。
基于同态加密的隐私凑集求交，只对一方的数据进行同态加密和解密，使得此方案适宜双方的数据集大小差异较大的场景（n>>m）。
同态加密算法目前是一种低效的加密算法，全同态加密的密文长度常日非常大，使得目前基于同态加密的隐私凑集求交方案在性能上不霸占上风。特殊地，Chen 的基于全同态加密的隐私凑集求交方案，只对接管者一侧实行同态加密，这使得算法适宜运行在求交的凑集差异较大的场景。
3.4 基于公钥加密图 5 RSA 盲署名协议 [7]
基于 RSA 的求交法 [6] 最早由 Meadows 等人于 1986 年提出，协议的紧张思想是通信的双方各自天生一个大素数，对数据进行乘方运算，并比对打算的结果。2010 年，Cristofaro 等人提出的基于 RSA 盲署名的隐私凑集求交技能 [7]，是目前性能最好的基于公钥加密的隐私凑集求交技能。其一样平常步骤为：
发送者 Alice (Server) 持有数据 S={s1, s2, ..., sw}, 吸收者 Bob 持有数据 C={c1, c2, ..., cv}Alice 和 Bob 利用相同的哈希函数 H 和 H`，Bob 有持有 RSA 的私钥 (n, e)，并将公钥 (n, d) 发送给 Alice离线阶段：3.1. Alice 利用公钥对每个 S 打算 hsj = H(sj), Ks:j = RSA(hsj ), tj = H`(Ks:j)3.2. Bob 天生随机数 Rc:i (Rc:i< n 且 gcd (Rc:i, n) = 1)，并利用私钥对数据 C 打算 hci = H(ci), yi = hci RSA(Rc:i)
4. 在线阶段：
4.1. Bob 发送所有 yi 给 Alice4.2. Alice 利用私钥打算 yi' = RSA(yi)4.3. Alice 发送所有 yi' 和 tj 给 Bob4.4. Bob 打算 Kc:i = (yi' / Rc:i) mod n, ti' = H'(Kc:i)。之后打算 { t1' , t2', ..., tn' }∩{t1, t2, ..., tw}, 输出的结果为 Bob 和 Alice 数据的交集
基于 RSA 的求交协议，比较范例的是 RSA 盲署名求交协议。RSA 盲署名求交协议是对基于 RSA 的求交协议（基于 RSA 的密钥交流方法）的改进方法，可以在对手是恶意模型时，安全打算数据的交集，并供应了更好的打算性能。算法分为离线阶段和在线阶段，个中离线阶段操作可以在数据预处理阶段完成。实际实行求交算法时，只对一方的数据实行一次 RSA 加密操作，相较于其它基于 RSA 的求交协议，具有更好的性能上风。RSA 盲署名算法的精确性基于如下公式 (把稳原论文中的 Kc:i = yi' / Rc:i, 实际应为 Kc:i = (yi' / Rc:i) mod n, 作者在后续论文中有纠正):
其事理是利用大数的离散对数没有有效的打算方法的特点，Alice 对 Bob 持有的伪随机数据进行署名，Bob 去除伪随机得到署名过的自己的数据，再和 Alice 真个署名数据做比拟求交。
由于 RSA 打算繁芜度较高，协议中 RSA 的打算次数会随着数据量的增大呈线性增长，使得基于 RSA 的求交方法，在数据量较大时会产生性能问题。
由于 RSA 盲署名算法在运行时只对一真个数据进行 RSA 加密，使得在求交数据量级差距较大时，可以把数据量较小的一端作为 Client 端，这样可以得到非常大的性能上风。其余，RSA 算法的流程适宜并行处理，方便利用并行打算来提升性能。
RSA 盲署名协议能够在恶意对手模型下，为隐私凑集求交供应安全保障，但由于非对称加密的次数随比对的数量量的增加呈线性增长，以是无法处理海量数据的隐私凑集求交场景。
3.5 基于不经意传输图 6 不经意传输
OT（Oblivious Transfer）是根本的密码学原语，中文译为不经意传输，茫然传输。OT 协议最早于 1981 年由 Michael O. Rabin 提出，协议由发送方和吸收方两方参与，吸收方要求获取信息，发送方发送信息给吸收方。在这个过程中，发送方对吸收方的要求信息一无所知，同时吸收方也无法获取要求的信息之外的额外信息。OT 协议紧张利用有限的非对称加密技能，达到安全传输大量数据的功能
2014 年，Pinkas 等人提出了基于 OT 扩展协议的高效隐私凑集求交方案 [8]，该方案利用 OT 扩展，传输数据使得通信双发得到一个伪随机函数，并利用此伪随机函数对双方持有的数据进行加密比对。方案紧张分为三个阶段来实行，哈希阶段，隐秘传输阶段和求交阶段。在哈希阶段，通信 Alice 和 Bob 把各自持有的数据通过哈希运算均匀分布在一个给定大小的地址空间内，并利用随机数添补空余的哈希位置。在隐秘传输阶段，Bob 根据自己持有数据的比特信息作为选择位，利用 OT 扩展安全地获取 Alice 持有同样比专程位上的伪随机天生数据。末了在求交阶段，Bob 解密伪随机数据，并和自己持有的而数据进行比较。
2016 年，Kolesnikov 利用批量 OT 扩展传输和布谷鸟哈希实现了更高效的隐私凑集求交方案 [9]，基于 OT 的隐私凑集求交成为性能上最仅仅朴素哈希求交技能的隐私凑集求交方案。2019 年，Pinkas 等人提出了基于稀疏扩展的隐私凑集求交方案 [10]，方案首先把秘密信息分成三份，这样在未获取到哀求交的数据之前，可以提前随机天生两份秘密信息，以便在离线阶段进行 OT 扩展传输，提前获取伪随机天生函数。在在线阶段，为了避免传输大量的秘密信息，方案利用了多项式技能，把要传输的数据融入多项式，仅通报多项式的参数来代替传输大量数据。根据该方案的测试结果，在要比拟的数据量弘大，或者带宽受限定场景下，此方案相较于目前最优的基于 OT 的隐私凑集求交方案，供应了更好的性能上风。
虽然基于不经意传输的隐私凑集求交技能仍旧是利用非对称加密技能作为实在现事理，但不经意传输利用有限次非对称加密，来完成任意数量的安全数据传输。基于不经意传输的隐私凑集求交方案，是目前研究最为生动的隐私凑集求交方案。
4 隐私凑集求交前景展望隐私凑集求交作为安全多方打算的关键技能，自出身以来，得到了企业，个人和机构的高度的关注，目前仍在快速发展中。近些年来，频繁出台的隐私和信息保护的法律法规，匆匆使了我国在隐私打算领域干系的研究和落地的高速发展。目前最为盛行的隐私凑集求交方案是基于不经意传输的隐私凑集求交方案，对该方案的研究是基于安全性和性能平衡后的一种考量，研究的思路紧张在减少非对称加密次数和通信双方传输的数据量。
虽然隐私凑集求交技能在最近这些年得到了长足的发展，但仍面临了诸多寻衅，个中包含最盛行的基于不经意传输协议的隐私凑集求交方案是限定对手模型是半老实模型的条件下的安全求交协议。隐私凑集求交技能作为根本运用技能，其性能仍有提升需求。目前的各种技能方案，短缺标准的对抗手段来证明其确实在实际运用中保护了数据安全。以及短缺基于隐私凑集求交的各种标杆性运用。
隐私打算在金融，政务，运营商，营销商，科研机构等对自身数据极为敏感，且对 IT 智能化有强烈需求的行业和领域，有着重要的地位。对付隐私凑集求交技能在实际行业运用上的实践，须要关注的紧张为题有：
安全性。隐私打算为提升系统安全性而生，作为隐私打算底层关键性技能之一的隐私凑集求交，须要在安全性方面供应令业界信服的能力和证明办法。这决定了隐私凑集求交的核心技能，须要供应可信服的论文和理论依据，且常日为大众认可的开源代码。威信认证。隐私打算对安全性哀求极为敏感，除了在算法方面有可信理论依据之外，还须要对应的威信机构认证。这包括安全性认证的威信机构，仿照毁坏性攻击防御能力的威信机构等。主动防御能力。在基于智能剖析或知足客户设定的阈值的条件下，如果在打算过程中，运用及时识别出通信的参与方可能包含恶意攻击，应能够及时停滞打算并记录剖断攻击的干系数据。可阐明性。可阐明性是更好的主动不雅观测打算过程和掩护的能力。包含打算过程的可视化，通信数据抓取，事宜审计能力等方案。精良的性能。作为安全通信的底层技能，隐私凑集求交须要供应相对精良的性能，以便应对海量数据处理以及实时数据剖析的需求。这哀求隐私凑集求交算法的性能，应尽可能去逼近朴素哈希求交算法的性能。隐私凑集求交目前在海内已经有商业化运用落地，但仍短缺标志性的成功商业运用作为标杆，使得隐私打算的商业化进程在需求和质疑中缓步前行。在当前的市场背景下，如何保障今后的技能创新和运用能够在符合法律法规的条件下，安全高效地进行数据交互，将会是未来数据密集型系统的一个主要的支撑能力。对付持有大量敏感数据的传统企业来说，也急需一种可靠的技能，既能够利用数据创造代价，又能够保障持有者的数据的隐私安全。
参考文献[1] M. Raab and A. Steger. “Balls into bins” - a simple and tight analysis. In Randomization and Approximation Techniques in Computer Science (RANDOM’98), volume 1518 of LNCS, pages 159–170. Springer, 1998.
[2] A. C. Yao. How to generate and exchange secrets. In Foundations of Computer Science (FOCS’86), pages 162–167. IEEE, 1986.
[3] M. Bellare, V. Hoang, and P. Rogaway. Foundations of garbled circuits. In Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS’12, pages 784–796, 2012.
[5] Chen H, Laine K, Rindal P. Fast private set intersection from homomorphic encryption[C] //Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 1243-1255.
[6] 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.
[7] E. De Cristofaro, G. Tsudik, Practical private set intersection protocols with linear complexity, in: International Conference on Financial Cryptography and Data Security, Springer, 2010: pp. 143–159.
[8] B. Pinkas, T. Schneider, and M. Zohner. Faster private set intersection based on OT extension. In USENIX Security Sympo sium, pages 797–812. USENIX, 2014.
[9] V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu. Efficient batched obliviousPRF with applications to private set intersection. In ACM CCS 2016, pages 818–829,Vienna, Austria, October 24–28, 2016. ACM Press. 7
[10] B. Pinkas, M. Rosulek, N. Trieu, and A. Yanai. SpOT-light: Lightweight private setintersection from sparse OT extension. In CRYPTO 2019, Part III, LNCS 11694,pages 401–431, Santa Barbara, CA, USA, August 18–22, 2019. Springer, Heidelberg,Germany. 7
[11] 申立艳，陈小军，时金桥，胡兰兰。隐私保护凑集交集打算技能研究综述 [J]. 打算机研究与发展，2017,54 (10):2153-2169.
[12] 黄翠婷，张帆，孙小超，等。隐私凑集求交技能的理论与金融实践综述 [J]. 信息通信技能与政策，2021 (6):50-56. DOI:10.12267/j.issn.2096-5931.2021.06.006.
