共计 9170 个字符，预计需要花费 23 分钟才能阅读完成。
作者：京东科技 孙晓军
摘要
隐衷汇合求交（PSI）是平安多方计算（MPC）中的一种密码学技术，它容许参加计算的单方，在不获取对方额定信息（除交加外的其它信息）的根底上，计算出单方数据的交加。隐衷汇合求交在数据共享，广告转化率，联系人发现等畛域有着宽泛的利用空间。本文对隐衷汇合求交的各项实现技术做了介绍和比照，对隐衷汇合求交的原理进行了剖析，并进一步论述了隐衷汇合求交目前面临的挑战和发展前景。
【关键词】：隐衷汇合求交，平安多方计算，不经意传输
1 引言
隐衷汇合求交（PSI）是平安多方计算（MPC）中的一种密码学技术，它容许参加计算的单方，在不获取对方额定信息（除交加外的其它信息）的根底上，计算出单方数据的交加。随着大数据，人工智能，云计算等技术的衰亡，企业和集体对隐衷数据的爱护越来越器重。隐衷汇合求交，作为平安多方计算中的关键技术，在近年来的实践钻研也失去了长足的倒退。
在数字经济的泛滥平安威逼中，数据泄露已成为寰球范畴高发的安全事件之一，且这个趋势仍在继续。
- 2018 年，Facebook 因向第三方公司歹意泄露其用户信息被判罚数十亿美元
- 2019 年，字节跳动因收集未成年人信息被罚款总计约 1 亿美元
- 2020 年，中国电信 2 亿用户信息被贩卖，相干人员被判刑并处以罚款
- 2021 年，亚马逊因违反数据隐衷法规被处罚 8.88 亿美元
在这些数据安全问题中，有人为起因的成心泄露，也有技术缺点导致的数据泄露。数据隐衷问题，间接影响着企业的利益和信用，甚至因而导致企业倒闭。
随着中国在信息化和数字化的继续倒退，大量具备敏感性和私密性的集体和企业信息在互联网上流传。如何平安地利用这些信息为企业和集体提供便捷的服务，同时又能保障信息不在传输过程中被泄露，对数字经济的衰弱倒退，有着十分重要的作用和意义。
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 应用雷同的哈希函数 H
- Alice 生成随机盐值 Salt 并发送给 Bob
- Bob 应用 salt 对所有 Y 进行哈希计算 hyi = H(yi, salt)
- Alice 应用 Salt 对所有 X 进行哈希计算 hxi = H (xi, salt), 并发送 hxi 给 Bob
- Bob 计算 {hx1, hx2, …, hxm}∩{hy1, hy2, …, hyn} 的后果为 Alice 和 Bob 数据的交加
奢侈哈希求交法，是目前 PSI 协定中，性能最优的协定。因为协定自身不具备平安求交能力，个别只能利用在特定问题下的非敏感数据的求交场景。
3.2 姚氏混同电路
姚氏混同电路（Yao’s Garbled Circuits）[2] 协定由 1986 年由图灵奖获得者姚期智院士提出，用来解决驰名的姚氏百万富翁问题。混同电路应用布尔电路（与，或，非等）构建电路表，保障计算的过程中，单方的数据不被泄露。最终依据混同电路的计算结果，以及混同电路表，能够计算单方数据的计算结果。
![图 2 残缺的姚氏电路 [2]](https://img-blog.csdnimg.cn/i…)
图 2 残缺的姚氏电路 [2]
一个典型的姚氏混同电路的计算过程分为混同电路生成阶段，电路执行阶段和电路评估阶段。
- 混同阶段，Alice 生成一个布尔混同电路表，应用混同电路表为每个布尔值生成密钥。Alice 对混同电路的计算结果，应用布尔电路中对应的密钥进行加密，打乱程序后和本人持有的数据 X 对应的密钥信息发送给 Bob。
- 执行阶段，Bob 依据本人持有的数据 Y，通过 OT 协定获取混同电路表对应的密钥信息。Bob 应用本人持有的数据对应的密钥和 Alice 给的密钥对 Alice 发送过去的混同电路的计算结果进行解密，其中，只有 Alice 和 Bob 持有的数据对应的混同电路的数据，可能被失常解密。
- 评估阶段，Bob 发送解密后的值给 Alice，Alice 对照混同电路计算结果，得出最终的计算结果。
图 3 用于相等比拟的混同电路设计
混同电路的设计不仅能够利用在隐衷汇合求交的数据相等的比拟场景，也能够利用于平安的数据大小比拟，含糊查问等场景。基于混同电路的计划相较于热门的基于不经意传输的计划在性能上处于劣势，且同样基于半诚恳的对手模型，使得此计划目前在理论利用中应用较少。
3.3 基于同态加密
![图 4 基于全同态加密的隐衷汇合求交协定 [5]](https://img-blog.csdnimg.cn/i…)
图 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} 发送给 Bob
- Bob 对数据集进行解密，收集所有解密后果为 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]](https://img-blog.csdnimg.cn/i…)
图 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.1. Bob 发送所有 yi 给 Alice
4.2. Alice 应用私钥计算 yi’ = RSA(yi)
4.3. Alice 发送所有 yi’ 和 tj 给 Bob
4.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 oblivious
PRF 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 set
intersection 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.
内容起源：京东云开发者社区 [https://www.jdcloud.com/]
