安全求交集(PSI)在隐私计算中的发展和应用
安全求交集(PSI)定义
- 定义：Private Set Intersection (安全求交集)，指 Alice 拥有集合 X，Bob 拥有集合 Y，通过 PSI 计算后，Alice 只能学习到 X ∩ Y，而无法获知 Bob 集合中不属于交集的元素，且该过程具有可证明的安全性。
- 需求：除了 PSI 协议本身，还需要考虑如何隐藏非交集元素、高效计算交集元素以及协议的实用性。
PSI 功能和分类
- 两方半诚实 PSI：
- 仅用于计算交集，交集被公开，非交集元素被隐藏。
- 仅适用于两方 (Alice 和 Bob)。
- 仅提供半诚实安全，即攻击者严格遵循协议，但好奇对方秘密信息。
- 挑战：
- 隐藏非交集元素：需要密码学安全的隐藏机制，通过添加噪声防止攻击者推断出非匹配元素。
- 计算交集元素：需要某种方式披露两个元素相等的事实。
- 效率：协议需适用于大规模应用。
- 方法：
- 基于 Diffie-Hellman 密钥交换的 PSI：
- 基本思想：利用“双重加密”的交换性质。
- 隐藏：加密隐藏元素。
- 比较：交换性质确保元素相等时能被披露。
- 效率：线性于通信成本，仍是主流实现方式，许多对密码原语进行了增强。
- 基于 Oblivious Pseudo-Random Functions (OPRF) 的 PSI：
- 发送方计算其集合在“秘密”函数上的结果并发送给接收方。
- 接收方通过交互计算其集合在“秘密”函数上的结果，并与接收到的结果比较。
- 隐藏：秘密函数确保发送方无法知道接收方数据，接收方无法知道秘密函数。
- 比较：函数后的数据可比较。
- 效率：大部分操作是高效的密码学操作，PKI 操作很少。
PSI 最新进展
- 优化离线阶段：
- 使用最新的 OT (Oblivious Transfer)。
- 用 VOLE 替换 OT。
- 用新的原语替换 Cuckoo hashing。
- 引入 Probe-and-Xor-of-Strings (PaXos)。
- 引入 Oblivious Key-Value Store (OKVS)。
- 支持交集上的安全计算：
- 亿级计算：高带宽+高算力，分钟级别完成。
PSI 和其他隐私计算技术结合
- PSI + 差分隐私 (DP)：
- 动机：向交集添加噪声，使其统计上“正确”，但任何单个元素“DP 难”地确定是否属于双方。
- 应用：联合营销。
- 方法：
- FHE-PSI + DP：效率低。
- DH-PSI + DP：改进性能，减少 DP 填充长度。
- PSI + 可信执行环境 (TEE)：
- MesaTEE：开源的 TEE 上 PSI 解决方案。
- 机制：TEE 创建盐，各方用盐哈希数据，PSI 在 TEE 上完成，结果发送回各方。
- 优点：高效灵活，信任根在 TEE，而非密码方案。
其他特殊需求
- 多方 PSI：
- 常规多方 PSI：需要 N 方交集，挑战是任何两方交集不能被披露，方法包括 PHE+多项式表示、OPPRF。
- 特殊多方 PSI：某些两方交集可能需要计算并披露给特定方，需要定制解决方案。
- 计算模型：
- 单向模型：仅一方学习交集，如客户端提交联系人列表。
- 互惠模型：双方都学习交集，如银行间查找共同用户。
- 外包 PSI：两客户端通过不可信第三方执行 PSI，适用于资源受限设备。
- 安全模型：
- 半诚实安全 PSI：简单高效，但安全假设过强，仅考虑被动攻击者。
- 恶意安全 PSI：安全性更高，考虑恶意攻击者，但计算和通信开销更大。
- 非对称 PSI：一方元素数量远大于另一方，如客户端-服务器场景，方法包括 ECC-OPRF-PSI、FHE PSI。
- 其他需求：如大小隐藏、定制化业务场景。
总结
PSI 作为隐私计算中的关键技术，通过多种方法（如 DH、OPRF）实现安全交集计算，并不断优化以提高效率和安全性。结合差分隐私和可信执行环境等技术，PSI 在保护数据隐私的同时，支持更广泛的应用场景，如联合营销、多方数据协作等。未来发展方向包括优化协议性能、支持更复杂的计算模型和安全模型，以及应对非对称数据分布等挑战。
