隐私保护集合求交技术(PSI)教学文档

隐私保护集合求交技术(PSI)教学文档 1. PSI技术概述 隐私保护集合交集(Private Set Intersection, PSI)计算属于安全多方计算领域的特定应用问题，允许持有各自集合的两方或多方共同计算集合的交集，同时不会泄露交集以外的任何信息。 1.1 核心特性 隐私保护 ：确保只有交集结果被披露，不泄露交集外的任何元素 安全性 ：基于密码学或可信硬件技术实现 高效性 ：针对不同应用场景有优化方案 2. PSI应用场景 2.1 计算广告效果 计算广告转换率（浏览广告用户与完成交易用户的交集） 保护广告主和商家的用户隐私信息 2.2 联系人发现 新服务注册时查找已有联系人 保护用户联系人信息不被服务提供商获取 2.3 其他应用 基因组数据分析 敏感数据共享 隐私保护的数据协作分析 3. 传统PSI协议分类与比较 3.1 协议分类 朴素哈希方法 ：每个元素执行一次对称加密操作 基于公钥的协议 ：每个元素执行两次公钥操作 基于电路的方法 ：复杂度与电路中与门数量成正比 基于OT的协议 ：使用不经意传输扩展技术 基于布隆过滤器的协议 ：复杂度与布隆过滤器大小成正比 3.2 性能比较 | 协议类型 | 计算复杂度 | 通信复杂度 | |---------|-----------|------------| | 朴素哈希 | O(t) sym | O(t) | | 基于公钥 | O(t) pk | O(t) | | 基于电路 | O(mβ) sym | O(mβ) | | 基于OT | O(t) sym | O(tv) | | 布隆过滤器 | O(ts) sym | O(maxb) | 注：t = NX + NY，m = max(NX, NY)，β ≈ λ + 2 log n - 1 4. 高性能PSI协议 4.1 基于密码学的最快协议 EC-ROM/DE-ROM协议 ：目前最快的基于密码学的公开安全PSI协议 特点：可处理千万级数据集，恶意模型下安全 4.2 基于SGX的PSI协议（MesaTEE PSI） 4.2.1 MesaTEE平台特性 全球首个通用安全计算平台(USC) 三项核心技术： 混合内存安全技术 机密计算技术(Intel SGX) 可信计算技术(TPM) 性能优势：比传统方案快百倍以上 编程模式：与传统编程一致，易于开发 4.2.2 MesaTEE PSI协议流程 初始化阶段 ： 参与方与PSI服务器通讯 服务器为各方生成随机salt 远程认证确保服务器可信 数据处理阶段 ： 服务器发送salt给参与方 参与方对数据加盐哈希 排序哈希结果以抵抗侧信道攻击 PSI计算阶段 ： 参与方发送处理后的数据给服务器 服务器进行流式求交 使用bit vector表示结果 结果返回阶段 ： 服务器发送不同vector给各参与方 参与方解析获得最终交集 4.2.3 安全增强措施 SGX硬件级隔离保护 随机salt防止哈希反推 排序打破原始顺序关系 bit vector缓解侧信道攻击 不同传输密钥增强安全性 5. 技术对比与优势 5.1 传统PSI的局限性 参与方固定，难以动态增减 运算模式固定，难以扩展 参与方需互相通信，性能损耗大 semi-honest模型缺乏完整性保证 多方自适应能力不足 5.2 MesaTEE PSI优势 性能优势 ： 比最快的传统PSI(EC-ROM/DE-ROM)快60倍 支持分布式并行流式处理 数据量越大优势越明显 安全优势 ： SGX硬件级安全保护 内存安全保证 侧信道攻击防护 完整性保护 灵活性优势 ： 支持2方、3方及任意多方求交 参与方可动态增减 运算模式可扩展 6. 性能测试结果 6.1 测试环境 网络：LAN环境，10Gbps 硬件：Intel Xeon E3-1280 v6 @ 3.90GHz SGX内存：128MB 单线程运算 6.2 结果分析 传统PSI限制： 多数方案仅能处理百万级数据 RR、SM32、SM64等方案无法处理大数据集 EC-ROM/DE-ROM： 可处理千万级数据集 但仍比MesaTEE PSI慢60倍以上 MesaTEE PSI： 支持超大规模数据集 多方求交性能几乎不变 分布式并行处理可进一步提升性能 7. 参考文献 Chen, H., et al. Fast private set intersection from homomorphic encryption. 2017 Cristofaro, E. D., et al. Practical private set intersection protocols with linear complexity. 2010 Dong, C., et al. When private set intersection meets big data. 2013 Kamara, S., et al. Scaling private set intersection to billion-element sets. 2014 Kolesnikov, V., et al. Efficient batched oblivious prf with applications to private set intersection. 2016 Meadows, C. A more efficient cryptographic matchmaking protocol. 1986 Pinkas, B., et al. Scalable private set intersection based on ot extension. 2018 Rindal, P., et al. Improved private set intersection against malicious adversaries. 2017 Rindal, P., et al. Malicious-secure private set intersection via dual execution. 2017 8. 总结与展望 PSI技术在隐私保护需求日益增长的背景下具有重要价值。传统基于密码学的PSI协议在安全性和性能方面存在诸多限制，而基于SGX的MesaTEE PSI通过硬件级安全保护和优化设计，实现了性能的显著提升和安全性的增强。 未来发展方向： 更大规模数据集的优化处理 更复杂的集合运算支持 与其他隐私计算技术的融合 标准化和易用性提升 新型硬件加速技术的应用