共计 4781 个字符，预计需要花费 12 分钟才能阅读完成。
- 前言隐衷汇合求交（Private Set Intersection，即 PSI）是一个特定的平安多方计算（Multi-Party Computation, 即 MPC）问题，其问题能够简略了解为：Alice 输出汇合
Bob 输出汇合
单方执行 PSI 协定能够失去 Alice 和 Bob 两者的交加，同时不在交加范畴内的局部是受爱护的，即 Alice 和 Bob 无奈学习出交加以外的任何信息。隐衷汇合求交 (PSI) 协定有很多分类办法，依照底层依赖的明码技术分类次要包含：基于公钥明码的 PSI 计划，包含：基于密钥替换（DH: Diffie-Hellman）的 PSI 计划和 RSA 盲签名的 PSI 计划；基于不经意传输（OT: Oblivous Transfer）的 PSI 计划；基于通用 MPC 的 PSI 计划，例如基于混同电路（GC: Garbled Circuit）的 PSI 计划；基于同态加密（Homomorphic Encryption）的 PSI 计划；依照单方待求交汇合大小是否相等进行分类，可分为：均衡的 PSI（Balanced PSI）：两方汇合大小靠近，即
非均衡的 PSI（Unbalanced PSI）：两方汇合大小相差加大，即
本文先介绍非均衡隐衷汇合求交 (Unbalanced PSI) 的需要和利用场景，而后介绍相干的背景常识，最初介绍两种专门的 Unbalanced PSI 协定。非均衡隐衷汇合求交需要和利用场景
图 1 Unbalanced PSI 示意大多数的 PSI 协定思考的是两方数据汇合大小根本相等的状况，在一些场景下求交单方的数据集大小差别较大，具体是指一方汇合很小，一方汇合很大的求交状况，即
这种场景的隐衷汇合求交称为：非均衡隐衷汇合求交 (Unbalanced PSI)。寻找联系人当一个用户注册应用一种新的服务（如微信、Whatsapp 等）的时候，从用户的现有联系人中寻找有哪些曾经注册了同类的服务是一种在大多数状况下十分必要的操作。通过将用户的联系人发送给服务提供商能够无效地实现这项性能，然而与此同时用户的联系人信息，一种在大多数状况下被认为是隐衷的信息，也被裸露给服务提供商了。因而在这种场景下，将用户的联系人信息作为一方的输出，将服务提供商的所有用户信息作为另一方的输出来进行 PSI 协定能够实现发现联系人的性能，而且能够避免交加以外的信息泄露给任何一方。口令安全检查通过与曾经泄露的口令数据集比照，能够断定用户口令的安全性。用户如果间接将口令传输给服务器的话，用户口令的隐衷不会失去满足。为爱护用户口令隐衷，零碎应用隐衷求交技术来保障既帮忙检测口令是否平安，同时又不泄露用户口令隐衷。例如：Google 开发的 Password Checkup，微软的 Password Monitor。联邦学习样本对齐在联邦学习发动训练之前，必须基于单方的数据进行 PSI，应用单方共有的用户信息（例如用户 ID）找出交加，从而对应两方数据的特色和标签，在对齐的数据集上进行模型训练才有意义。下面几种典型利用中，两方的数据量差别比拟大，例如，10w vs 10 亿的隐衷汇合求交。通用的 balanced PSI 协定在两方汇合大小差别大的状况下，两方的计算量基本相同，跟大数据集的汇合大小成线性关系，数据集小的一方也要依照大数据集的规模配置计算和通信资源，对于数据集小的一方计算资源需要和耗费太大。一些研究成果对于 Unbalanced PSI 这种比拟常见而有理论利用价值的场景做优化，并且获得了较好的后果。
图 2 DH PSI 协定流程以基于密钥替换 (DH: Diffie-Hellman) 的 PSI 计划为例，介绍在两方数据集差别很大时的计算。如图 2 中 DH-PSI 的流程，包含 4 个步骤：alice 对
计算
次幂指数
发送到 bobbob 对
计算
次幂指数
发送到 alicebob 对
计算
次幂指数
发送给 alicealice 对
计算
次幂指数
能够看到 alice 数据集远小于 bob 数据集的状况下，alice 和 bob 的计算量都是
alice 要依照 bob 的数据集规模配置计算资源，对 alice 要求太高。2. 背景常识 2.1 不经意伪随机函数 (OPRF) 伪随机函数 (PseudoRandom Function PRF) 是密码学中的根底函数，与伪随机生成器 (PseudoRandom Generator PRG)、伪随机置换 (PseudoRandom Permuation PRP) 等根底组件之间也能够互相转换。伪随机函数的定义能够参见下图，依据密钥
和输出
失去后果
在不晓得密钥
的假如下
和随机数差别能够疏忽。
图 3 PRF 定义最典型的 PRF 利用是在传输层平安协定 (Transport Layer Security TLS) 中，TLS 握手 (handshake) 阶段通过协商失去预主密钥 (PreMaster Key)，预主密钥通过 PRF 计算失去主密钥 (Master Key)，主密钥再应用 PRF 失去通信加密和认证密钥。
图 4 OPRF 协定框架不经意伪随机函数 (Oblivious PseudoRandom Function OPRF) 是客户端和服务端之间计算伪随机函数 (PRF) 的两方协定。服务端提供伪随机函数 (PRF) 的密钥
客户端提供输出
协定完结后客户端失去
不经意伪随机函数 (OPRF) 有很多构造方法，如：RSA、DH 和不经意传输 (Oblivious Transfer)。2.1.1 基于 OPRF 的 PSI 框架文献 [HL08] 提出了基于 OPRF 实现 PSI 协定，能够形象为如下图所示的协定流程。
图 5 基于 OPRF 结构 PSI 协定的通用框架图 3 协定中 bob 产生密钥
并对数据集
计算
alice 和 bob 执行上节提到的不经意伪随机函数，失去数据集
的 OPRF 后果
通过比拟两方汇合的 PRF 值，失去交加后果。2.1.2 OPRF 相干规范 IETF 草案《应用素数阶群的 OPRF》给出了基于素数阶群结构 OPRF 的办法，定义了函数名称、参数、数据格式和规范向量。
图 6 基于素数阶群 DH 结构 OPRFIETF 草案《应用素数阶群的 OPRF》协定过程如下：客户端随机抉择
将输出
映射到群
中的元素
计算
发送给服务端。服务端接管到
后，计算
发送给客户端。客户端接管到
后，计算
失去
计算
IETF 草案《应用素数阶群的 OPRF》将下面三个步骤中的计算局部定义为三个函数（Blind，Evaluate 和 Finalize），并给出了具体的函数名称、参数和规范向量。IETF 草案《应用素数阶群的 OPRF》给出了候选的素数阶群，包含：ristretto255, SHA-512decaf448, SHAKE-256P-256, SHA-256P-384, SHA-384ristretto 是将非素数阶的 ecc 群转换为素数阶群的一种办法，ristretto255 是将 curve25519 (阶是 8 乘以一个素数) 的点群转换为素数阶群的实现。除了 ristretto255 外，其余阶为大素数或具备大素数阶子群的椭圆曲线也能够作为候选，例如比特币应用的 secp256k1 曲线或商密 SM2 定义的曲线也可作为候选。文献 [CMGD+21] 及其开源实现 APSI 建已应用 FourQ 曲线。2.2 全同态加密 (Full Homomorphic Encryption FHE) 全同态加密 (Full Homomorphic Encryption FHE) 是一种弱小的明码原语，能够对加密的数据执行任意 (算术或二进制) 电路运算，电路运算后的后果还是加密的，能够应用解密密钥进行解密。然而全同态加密个别计算开销比拟大，罕用的全同态加密计划是分级全同态加密计划 (leveled Full Homomorphic Encryption FHE)，即加密计划的参数抉择只容许执行无限的乘法深度。全同态加密 (Full Homomorphic Encryption FHE) 可用于设计隐衷汇合求交协定和隐匿查问协定，在通信量和计算上都有加到的劣势。疾速非均衡隐衷求交协定文献 [RA18] 中给出了半诚恳模型下的疾速非均衡隐衷汇合求交协定，并给出了实现参考和性能。[RA18] 的 PSI 协定能够看做图 5 OPRF 结构 PSI 协定的一种具体实现办法，其中 OPRF 协定采纳 2.3 节中形容的 OPRF 协定。协定过程中 bob 产生密钥
并对数据集
计算
alice 和 bob 执行上节提到的不经意伪随机函数，失去数据集
的 OPRF 后果
图 7 [RA18] Unbalanced PSI 协定流程该协定分为离线和在线阶段：离线阶段 bob 端对数据集
计算
发送给 alice，alice 对接管到的数据进行缓存。bob 端的计算量次要是
次幂运算。在线阶段 alice 和 bob 对数据集
执行不经意伪随机函数，alice 端失去
。比拟两个汇合失去交接后果。alice 端的计算量次要是
次幂运算，bob 端的计算量次要是
次幂运算。
总体计算量方面，[RA18] Unbalanced PSI 比 dh-psi 缩小一半。[RA18] Unbalanced PSI 在线阶段只和小数据集的大小
相干。思考到
在线阶段执行很快。能够看到下面的协定更适宜 Unbalanced PSI 的情景。0** 4 基于 FHE 的 Unbalanced PSI 协定文献 [CLR17] 给出了应用全同态 (Level Full Homorphic Encryption) 结构 PSI 的办法，并给出了优化办法。[CHLR18] 中提出在预处理阶段应用不经意随机函数 (OPRF) 对原始数据进行平安增强。[CMGD+21] 给出了具体的参数优化办法，缩小了在线阶段计算和通信量，并给出了和 [RA18] 的性能比照。
图 8 FHE PSI 协定流程 FHE PSI 协定流程：数据预处理阶段 alice 和 bob 在线执行 OPRF 协定，alice 失去数据集
的 OPRF 后果
在线求交阶段 alice 计算
局部幂指数的 FHE 密文，发送给 bob;bob 计算失去
所有须要幂指数，计算插值多项式的密文后果
发送给 alice；alice 对插值多项式的密文后果
解密，如果解密为 0，则
FHE 的 Unbalanced PSI 和 [RA18] 中的 Unbalanced PSI 相比，劣势在于不须要传输大数据集的相干数据，在执行完不经意伪随机函数 (OPRF) 后，通过减少一轮查问交互，即 FHE 的查问密文和返回，失去交加。参考文献
[HL08] Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries
[CT10] Practical Private Set Intersection Protocols with Linear Computational and Bandwidth Complexity
[CKT10] Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model
[KLSAP17] Private Set Intersection for Unequal Set Sizes with Mobile Applications
[RA18] Faster Unbalanced Private Set Intersection
[CLR17] Fast Private Set Intersection from Homomorphic Encryption
[CHLR18] Labeled PSI from Fully Homomorphic Encryption with Malicious Security
[CMGD+21] Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication
[draft-irtf-cfrg-voprf-09] Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups
