7.2 隐私求交 PSI：百万级数据的耗时量级
7.2 隐私求交 PSI：百万级数据的耗时量级
本节摘要：隐私求交（PSI）让两方算出交集却不暴露交集之外的元素，是 MPC 家族最先规模化的应用。本节讲清朴素哈希求交与加密求交（DH 或 OT 路线）的安全差异，给出百万级对百万级集合"百兆带宽分钟级"的耗时估算与决定因素。
定位：本节解决什么
广告主想知道"我的用户和平台的用户重合多少"，银行想知道"我的黑名单和同业的黑名单重叠多大"——需求朴素、商业价值直接。PSI（Private Set Intersection）的功能一句话：双方各持一个集合，协议结束后双方（或约定的一方）只知道交集，交集之外的任何元素信息为零。它对 MPC 意义特殊：计算量极小（没有繁重算术）、单次价值清晰（重合名单本身就值钱）、技术闭环短（不需要持续交互训练），因此成为绝大多数团队的 MPC 第一课，也是隐私计算商业化最早跑通的产品形态。
核心概念：两代实现的安全差距
第一代：哈希求交。 双方把元素用同一哈希函数（如加盐的 SHA256）散列后交换比对，明文不出域。它防得住"平台直接拖库"，防不住针对性攻击：哈希值可被彩虹表反推——手机号只有十一个数字，攻击者把全量号码段哈希一遍建立字典，交换过来的哈希值瞬间裸奔。结论：哈希求交只适用于元素取值空间大到字典攻击不划算的场景（比如长随机标识符），手机号、身份证号这类低熵数据直接判不合规。第二代：加密求交，两条主流路线。DH 路线基于交换律：各自用私钥做指数运算后再交换，比对双重加密值——攻击者没有任一方私钥，字典攻击失效。OT 路线（如 KKRT 为代表的 OT 扩展方案）用海量的不经意传输让每方在自己不知情的情况下完成比对，配合布谷鸟哈希分桶，通信效率在多数参数下更高。两代的安全差距要写进合同附件，不是实现细节。
图：PSI 两代实现的流程对照
动手演练：正确版与错误版对照
import hashlib, os def psi_hash_demo(): """错误示范：低熵数据的朴素哈希求交可被字典攻击。""" salt = os.urandom(16) # 公共盐不改变结论 phone = b"13800000001" tag = hashlib.sha256(salt + phone).hexdigest() # 攻击者遍历号段同样加盐计算 一轮即可命中 tag —— 盐挡不住枚举 return tag[:16] def psi_dh_concept(): """DH 路线概念演示：双重加密后比对 字典攻击失效。""" p = 2**127 - 1 # 大素数域（真实协议用标准群） a, b = int.from_bytes(os.urandom(16), 'big'), int.from_bytes(os.urandom(16), 'big') def H(x): # 元素先映射到域上 return int.from_bytes(hashlib.sha256(x).digest(), 'big') % p m = H(b"13800000001") alice_sends = pow(m, a, p) # 甲发 H 求幂 a bob_sends = pow(m, b, p) # 乙发 H 求幂 b tag_a = pow(bob_sends, a, p) # 甲再加密乙的值 tag_b = pow(alice_sends, b, p) # 乙再加密甲的值 return tag_a == tag_b # 交换律保证相等且双方只知自己的指数 print(psi_hash_demo()) print(psi_dh_concept()) # True
会话输出一段哈希与 True。注意概念演示省略了真实的群参数、零知识范围证明与批量优化，直接表现"为什么双重指数让字典失效"：攻击者要建字典得先猜中某方的私钥。
工程实践要点
三件采购与评审时的实事。量级要按参数算：卖方宣称"秒级百万求交"要追问带宽条件、实现路线（哈希还是加密）、是否恶意安全——同一句话在不同参数下差两个数量级。结果单向还是双向：只让一方拿到交集能进一步压缩泄露面，协议安排不同，价格谈判地位也不同。求交只是第一步：交集拿到之后的用法（联合统计、联合建模、标记比对）才是业务价值所在，提前设计好求交后的 MPC 链路，避免"求完交就没事干"的半截工程。
⚠️ 常见坑：拿哈希求交的产品去应付涉及手机号的合规场景。这不是性能取舍而是合规硬伤——监管检查里"低熵数据哈希交换"与明文交换同罪。看到"加密求交"四个字也要追问是哪条路线、参数多少。
本节要点：PSI 的安全分水岭在低熵数据的字典攻击；加密求交两条路线都在百万级做到分钟级；量级承诺必须绑定带宽与安全档位。下一节进入第一个行业纵深：金融。
采购评审的追问清单
PSI 是隐私计算采购的重灾区——演示效果惊人、上线效果缩水的案例集中在这里。评审时把六个追问问到底。一问实现路线：哈希求交还是加密求交，DH 还是 OT，参数多少比特。二问量级条件：宣传数字对应的集合规模、带宽、并行度，换成你的真实参数还剩多少。三问安全档位：半诚实还是恶意，恶意档的校验开销有没有计入报价。四问结果方向：交集给双方还是单方，多出来的泄露面换来了什么折扣。五问数据停留：比对过程中的中间数据在哪台机器上存了多久、日志里记了什么。六问扩展链路：求交之后的联合统计怎么衔接，还是交完就断。
六问的本质是把"隐私计算能力"还原成可验证的工程事实。凡是答不上参数、避谈量级条件、混淆哈希与加密的供应商，无论演示多流畅都应扣分——这三类回避恰好对应三类最常见的交付缩水。
PSI 的工程延伸：求交之后的下半场
求交拿到交集只是上半场，下半场的工程选择同样影响成败。延伸一：交集附属值处理。 现实需求往往不止要交集中的 ID，还要 ID 挂着的数值（消费额、评分）做联合统计——这就是"带负载的 PSI"（PSI with payload），安全语义要多防一层：负载只能在交集内、且按约定粒度可用。实现上常把负载用 ID 派生的密钥加密随集合一起过协议，求交成功即自然解密，链路顺滑。延伸二：增量求交。 名单每天滚动更新，全量重求既贵又慢——增量 PSI 只处理新增与删除的差集，协议状态管理复杂度上升，但长期成本降一个量级，高频合作场景的必选项。延伸三：多方求交。 两方求交的多方推广，通信量随参与方增长，工程上常退化为"星型两两求交再加安全聚合"的折中，拓扑选择回到 6.1 节的暗线。
下半场的三个延伸指向同一个结论：PSI 的产品化难度在协议外——状态管理、增量同步、负载权限，全是系统工程题。这也是为什么协议论文几十篇、能扛生产的 PSI 产品屈指可数：把十分钟的手工演示变成一年的无人值守服务，中间隔着的正是这些"下半场问题"。