01The Problem of Private Set Intersection
PSI 全称为 Private Set Intersection，直观的翻译名字为“隐衷求交”。从场景来看，隐衷求交：有许多个参与方，每个参与方持有各自的隐衷数据心愿通过协定求到所有数据的交加然而不透露除交加外的任何信息
目前罕用的 PSI 算法有：ECDH [1]KKRT [2]PSTY [3]1.1. ECDH 如果咱们假如哈希函数
这里
是计算平安参数，通常咱们能够取 128，基于 DH 的 PSI 协定如下所示。
1.2. KKRT 联合 Cuckoo hash 以及 batched OPRF，能够结构出一个比拟高效的基于 OT 的 PSI 协定（因为 batched OPRF 的构建基于 OT，因而咱们能够认为 KKRT16 的 PSI 协定是基于 OT 构建的）。协定具体内容如下图所示，咱们将右边参与方叫做 Alice，左边参与方叫做 Bob。
02PSI 的利用场景
咱们能够看到，（如果咱们只思考两方的场景下）PSI 场景中参与方咱们记为 P0 以及 P1P0 持有数据：data0 = (X, A1, A2, A3, ….)P1 持有：data1 = (Y, B1, B2, B3, ….)这里 X、Y 示意想要“撞库”应用的匹配字段（相似于 UID），而 Ai、Bi 指的是可能存在的其余数据信息。咱们假如在所有两方 PSI 场景下想要比对的数据用下图形式示意。咱们假如 data0 和 data 1 中只有一条数据是匹配的，即 y1 和 x2。
留神在 PSI 中咱们肯定须要保障平安的是：X 与 Y 的非交加元素 Case 1: 指定参与方获取交加 UID 通常来说，在 PSI 中咱们指定能够指定某个参与方（例如 P0）获取到 UID 的 PSI 后果。在上面这种场景下，P0 得悉了交加的 UIDP1 什么都没有失去
（简直）所有的已知 PSI 协定都能够实现上述性能。例如 KKRT、ECDH PSI 等等。Case 2: 指定参与方获取交加 UID 以及 Payload 通常来说，在 PSI 中咱们指定能够指定某个参与方（例如 P0）获取到 UID 以及 Payload 的 PSI 后果。在上面这种场景下，P0 得悉了交加的 UID + 交加元素在 P1 处的 PayloadP1 什么都没有失去
这种状况咱们须要一些 tricky 的形式来计算，通过 case1 首先使 P0 获取到“x2”这条交加的 UID 数据；运行一个 Symmetric PIR 协定，或者 1-out-of-n OT 协定获取到 payload 的交加信息。当然，也有一些更加高效的算法，这里不再赘述。
Case 3: 交加 UID 公开在这个 case 中，单方均获取到最终交加的 UID 信息。
所有的已知 PSI 协定都能够实现上述性能。
Case 4: 交加 UID 公开，指定方获取到 Payload
所有的已知 PSI 协定都能够实现上述性能。只须要在 case3 的根底上让 P1 将 payload 发送给 P0 即可。
Case 5: 单方数量级差距大（性能晋升）传统的 PSI 协定个别假如了单方数据集大小相似的状况，因而在 unbalanced 场景中咱们须要特定设计的 PSI 协定来实现协定减速。须要留神的是在 unbalanced 的场景下其实并不影响咱们解决 case 1 – case 4 的所有利用场景，这里咱们只以 case 3 的场景作为例子。
Case 6: 获取到交加 UID 或者 Payload 的统计值在法律法规、用户隐衷要求较高的场景中，咱们须要对交加信息进行爱护。因而在上面这种场景下，P0 得悉了 单方交加 UID 的某个统计值 P1 得悉了 单方交加 UID 的某个统计值
如果咱们想要同时对 Payload 进行计算，会就义较大的性能，能够达到的成果是：P0 得悉了单方 交加 UID 的某个统计值 或者 Payload 的某个统计值 P1 得悉了单方 交加 UID 的某个统计值 或者 Payload 的某个统计值
=== 注：本文探讨的计划仅限于半诚恳平安模型，歹意平安须要另行探讨。
参考文献
[1] Agrawal, Rakesh et al.“Information sharing across private databases.”SIGMOD ’03 (2003).
[2] Kolesnikov, Vladimir et al.“Efficient Batched Oblivious PRF with Applications to Private Set Intersection.”Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (2016): n. pag.
[3] Pinkas, Benny et al.“Efficient Circuit-based PSI with Linear Communication.”IACR Cryptol. ePrint Arch. 2019 (2019): 241.