PSI与OT：联邦学习数据对齐的密码学地基与工程实践

联邦学习这两年讨论热度一直不减但真跑到企业里做联调的时候你会发现最花时间的往往不是模型怎么聚合、梯度怎么加密而是第一步——把两边数据先对齐。这边叫“张三”那边叫“zhang.san”到底是不是同一个人各自的用户ID在不出域的前提下怎么找交集这就是隐私集合求交PSI要解决的事。而作为PSI最重要地基的不经意传输OT才是真正决定这套方案能不能跑起来、跑得动百万级数据的核心。这篇文章就把PSI和OT掰开揉碎讲清楚从密码学原理到工程落地的坑一次说透。正在搭联邦学习平台、做跨机构数据合作的算法工程师以及想给团队选型隐私计算方案的技术负责人都适合读一读。1. 为什么联邦学习的起点是“数据对齐”而不是“模型聚合”1.1 数据不出域的“找共同用户”联邦学习整个框架看上去很美好模型在本地训练参数加密上传服务器只聚合梯度。但真到项目里第一个拦路虎往往是“联邦学习的各方到底在哪些样本上对齐”。拿两家医院联建一个疾病预测模型来说。A院有患者的影像特征B院有患者的检验指标两边医院的患者ID体系完全不同不能直接拿原始ID去比因为这样等于把各自的用户清单全量暴露给对方。你要做的其实是在双方都不泄露非交集用户的前提下找到“两边都有的那些患者ID”然后只在这部分共同用户上做联邦建模。这个过程就是隐私集合求交。它解决的是数据准备阶段的样本对齐问题而不是模型训练本身。很多人一上来就研究横向联邦的梯度聚合、纵向联邦的特征对齐但其实样本交集都没算干净后面的建模全是空中楼阁。1.2 为什么不能直接哈希一下再比有同学会问我把ID做个SHA256哈希给对方比对不就行了理论上可以但实际上非常危险。原因在于ID空间的枚举性——手机号、身份证号、邮箱这些标识符的取值空间有限而且有固定的编码规则。攻击者只要把常见格式的ID全部哈希一遍再和你传过来的哈希值做比对就能反推出你的原始ID。这种攻击方式叫枚举攻击在隐私计算领域是教科书级别的反面案例。有人会想那把哈希加个盐总可以了吧但你加盐的目的是什么如果双方用同一个盐对方照样可以通过枚举反推如果双方用不同盐哈希值根本对不上。所以单纯“哈希比对”这条路从根上就是死的。这也解释了为什么实际工程里需要PSI这样的密码学协议。它保证的是协议结束时双方只知道交集不知道对方集合里非交集部分的任何信息。这才是“隐私集合求交”这六个字里“隐私”二字的真正含义。2. 隐私集合求交的真正地基不经意传输OT2.1 怎么理解OT一台“看不见选择的自动售货机”不经意传输Oblivious TransferOT是密码学里的一个基础原语它的概念比PSI更底层。简单说发送方手里有若干个消息接收方想选其中一个但发送方不知道接收方选的是哪个同时接收方也只能拿到自己选的那个拿不到其他消息。打个比方传统售货机你按了“可乐”的按钮机器知道你选了可乐也看到你拿走了可乐。但OT要做到的是你按下按钮机器吐出饮料但机器不知道你按的是哪个按钮而你手里也只有一瓶饮料拿不到其他货道的东西。这个“双方都蒙在鼓里”的性质听起来很神奇但确实是可构造的。这种性质在密码学协议里几乎是万能积木。比如你要实现“让双方共同计算一个函数但彼此不泄露输入”很多时候都要靠OT来搭。PSI就是其中一个典型应用——很多高效PSI协议本质上就是把集合求交问题规约到一系列OT实例上再通过OT协议安全地完成比较。2.2 OT扩展把小种子变成一百万个OT如果直接基于公钥加密来做OT每一对OT都需要一次指数运算百万级样本根本跑不动。这里的关键技术叫OT扩展OT Extension它的核心思想非常巧妙先用少量公钥运算生成一小批“种子OT”这批OT只需要跑几十个或几百个然后用对称密码学比如AES、哈希函数把这些种子OT“拉伸”成几百万个OT实例。你可以把OT扩展理解成“用一小把真随机种子通过伪随机生成器产出一大串随机数”。密码学上保证如果种子是安全的、只有双方各自掌握一部分那么扩展出来的海量OT依然满足OT的安全性质。实测下来OT扩展的效率比朴素OT方案快好几个数量级。现在工业界主流的PSI库比如libOTe、emp-toolkit里的PSI实现底座基本都是OT扩展。这也是为什么现代PSI能把百万级ID的交集计算压到几十秒级别——如果没有OT扩展单纯靠公钥运算这个时间会膨胀到不可接受。所以我说OT是PSI的地基一点都不夸张。3. 从OT到PSI三条主流技术路线对比3.1 基于OT扩展的PSI工程上最实用的那一款基于OT的PSI协议代表工作是KKRT16以及后来的BaRK-OT等方案是目前开源社区和商业产品里最流行的一类。它的思路可以这样理解把每一个集合元素通过哈希映射到一个“桶”里然后用OT协议对这些桶做比较——双方在同一个桶内执行OT如果OT的结果匹配就说明双方在这个桶里有相同元素。这套流程里OT负责的是“安全比较”每次比较过程中接收方只知道自己拿到的比较结果发送方完全不知道对方在比哪个桶、比对结果是什么。多个桶并行跑下来交集自然就出来了。再加上桶的大小通过参数控制可以在通信量和计算量之间做权衡。我在实际项目里用libOTe跑过百万级ID的PSI配置合理的机器上单线程大约一分钟上下多线程优化后能进到十几秒。这个量级在横向联邦的用户ID对齐场景中完全够用。要注意的是这类协议对网络RTT比较敏感跨机房调用时要提前评估。3.2 DH-PSI原理最容易讲清楚的老方案Diffie-Hellman PSIDH-PSI是早期最经典的PSI方案也是很多技术人员第一次接触PSI时看到的那个协议。它的原理基于DH交换的数学性质双方各自生成随机私钥a和b然后把自己的ID分别做两次盲化A方计算 H(x)^aB方计算 H(y)^b。双方交换盲化结果后A方再对B方的结果做自己的指数运算得到 H(y)^(ba)B方对A方结果做自己的指数运算得到 H(x)^(ab)。根据DH交换的数学规律当且仅当 x y 时H(y)^(ba) H(x)^(ab)。通过比对双方二次盲化后的值就能找出交集而整个过程中原始ID没有泄露。这个方案的优点是逻辑直白、代码实现难度低。缺点是每个元素都要做多次椭圆曲线点乘运算计算开销远高于基于OT扩展的方案。百万级样本跑DH-PSI通常需要几分钟甚至更久。所以我一般建议如果你是在教学演示、中小规模场景或刚起步的原型系统里DH-PSI是很合适的但要上生产环境优先考虑OT路线。3.3 同态加密PSI精度高但吃算力还有一类基于同态加密的PSI比如用Paillier或者BFV方案。思路是A方把自己的ID列表用同态加密算法加密后发给B方B方在同态密文上执行集合包含判断等运算因为同态加密允许直接对密文做加减乘除所以B方在看不到明文的情况下也能算出“哪些ID同时在双方集合里”的加密结果最后返回给A方解密。这种方案的好处是扩展性好能和联邦学习中的安全聚合流程无缝衔接甚至可以直接把同态加密得到的加密交集结果用于后续训练。坏处也很明显同态加密的计算量巨大尤其是全同态方案对机器内存和CPU的要求非常高。百万级样本如果硬上全同态耗时和资源消耗会非常感人。所以同态加密PSI更适合对隐私保护级别要求极高、数据规模可控的场景而不是通用的大规模联邦学习基础设施。3.4 怎么选一张表看明白如果要在方案选型时快速拍板我习惯看下面这张表方案类型计算开销通信开销实现难度适用规模典型代表基于OT扩展低中中百万级以上KKRT16、libOTeDH-PSI高低低十万级以下emp-toolkit同态加密PSI极高高高十万级以下Paillier、BFV结论很直接在联邦学习的生产环境里优先考虑基于OT扩展的PSI原型演示和中小规模合作DH-PSI更容易快速落地只有在特殊合规要求下才选同态加密路线。4. 联邦学习实战PSI在横向与纵向场景中的用法4.1 横向联邦先对齐用户再训练模型横向联邦的场景是“不同机构拥有不同用户的相同特征”。最典型的就是两家银行各自拥有自己客户的交易流水想联合建模识别欺诈但双方客户不完全重合。这时候第一步就是用PSI找出共同的客户ID然后再在这个交集上做联合建模。这里有一个容易被忽视的实操细节PSI的输出结果本质上是一组双方都知道的ID集合但它是按原始顺序输出的。如果后续你直接把这个交集ID当成训练集划分依据可能会带来潜在风险——比如一方可以观察模型在哪些ID上表现好反推另一方是否拥有某些特征。稳妥的做法是在PSI完成之后双方约定一个随机打散策略对交集ID做重排然后再划分训练集和测试集。这个打散步骤虽然简单但在合规评审时经常被重点关注。4.2 纵向联邦样本对齐和标签补全纵向联邦是“不同机构拥有相同用户的不同特征”。比如一方是电商平台有用户的购买行为特征另一方是金融机构有用户的历史信用标签。建模前需要把同一批用户在两边拉齐。这时PSI的作用是保证只有共同用户进入后续的特征拼接流程避免出现“A方的特征配上B方空白标签”这种脏数据。纵向联邦里PSI还经常被扩展成“带标签对齐”的版本。比如A方除了ID还想确认某个ID的标签是否有效B方则需要确认A方的标签对应的样本是否在B方的特征范围里。这种场景需要对PSI做一点功能延伸比如PSI-Cardinality只算交集基数不泄露交集元素或PSI-Sum连交集某些属性的和也算出来但不泄露明细。联邦学习平台如果要把纵向场景做成标准化产品迟早都要支持这些变种。4.3 性能调优百万级ID是怎么压到秒级的跑过真实PSI任务的同学应该都有体会小规模数据没问题一到百万级就开始焦虑内存和耗时。这里分享几个实测下来的调优思路。第一分桶并行。基于OT扩展的PSI协议天然支持把数据分成多个桶并行处理桶间互不影响可以开多线程来跑。我一般会把百万级ID按哈希值分成64个桶然后用16到32个线程并行吞吐量能翻好几倍。第二控制桶大小和哈希函数的参数。有的协议实现里桶越大则哈希碰撞概率越低但单桶计算量越大。这个要根据样本量做一次小规模基准测试找到平衡点。第三网络带宽对PSI影响很大。OT扩展的通信量虽然比公钥方案小很多但百万级ID跑下来也要传输几百MB到几GB的数据。跨机房跑PSI时最好提前测一下带宽和RTT必要时压缩数据或调整分桶策略。实测下来在局域网环境跑百万级PSI大概几十秒公网环境则会显著变慢甚至翻几倍。5. 联邦学习流水线上的另一个话题灾难性遗忘与PSI的位置5.1 灾难性遗忘到底是个什么问题最近“灾难性遗忘”和“联邦学习”放在一起讨论的频率很高。它说的是当一个模型连续学习多个任务时学习新任务可能会导致模型在旧任务上的表现急剧下降。这个现象在传统的集中式训练里就存在在联邦学习里则因为数据分布更复杂、各参与方数据不重叠表现得更明显。但要注意灾难性遗忘发生在模型训练和更新阶段而PSI发生在数据准备阶段。两者在联邦学习流水线上的位置不同但都属于“能不能把联邦学习工程化落地”的关键问题。你在设计一个联邦学习系统时PSI负责的是“喂给模型的数据对不对”灾难性遗忘负责的是“模型在持续学习时记不记得住”。一个完整的联邦学习平台这两个问题都得解决。圈内人常提到杨强教授那本《联邦学习》的PDF里面有相当篇幅专门介绍隐私保护技术栈PSI就是其中数据准备阶段的重要组件。建议做联邦学习的同学把那本书里关于隐私计算的部分配合这篇内容一起看能更快建立全局观。5.2 PSI在联邦学习隐私技术栈里的位置如果把联邦学习平台的隐私保护能力分成三层最底层是密码学原语层包含OT、同态加密、秘密共享中间层是隐私计算协议层包含PSI、安全多方计算MPC、联邦特征工程最上层才是联邦学习框架层负责调度、聚合和模型管理。很多团队做联邦学习平台时会先花大力气做框架调度最后才补PSI。但实际上PSI这类中间层能力是承上启下的——框架层调度得再好底层隐私协议不扎实样本对齐出问题整个平台就用不起来。我见过不止一个项目前期框架功能看着很全一联调才发现PSI模块跑不动百万级数据只能回炉重做。这个教训值得后来的团队引以为戒。6. 工程落地的常见坑与排查实录6.1 常见问题速查表拿实际运行中踩过的坑整理成一张表供大家遇到问题时快速定位现象可能原因排查建议PSI结果为空双方ID格式不统一比如一个带空格一个不带先检查预处理是否完全一致用时比预期慢几倍网络RTT过高或分了过多小桶先测带宽和延迟调整分桶数量内存溢出数据量超过预期桶内元素过多增大桶数或改成流式处理哈希碰撞导致错误交集用了较弱的哈希函数或参数设置不当改用SHA256检查桶参数配置日志打印了原始ID开发时忘了脱敏彻底检查日志输出开启脱敏开关6.2 实操心得日志、脱敏与盐值管理这里分享几个我反复跟团队强调的细节。日志脱敏是第一优先级。很多PSI库调试时候会在日志里输出元素哈希或者中间结果稍不注意原始ID就会打出来。生产环境中日志是必须经过脱敏管道处理的至少要把原始ID替换成对应哈希值。我见过因为日志泄露导致整个合规评审被卡住的真实案例这个坑成本极高。盐值管理要纳入密钥管理体系。PSI协议里如果用到随机盐或者盲化因子它就不是普通配置项而是密码学密钥。很多人开发时习惯把盐值硬编码在配置文件里这在生产环境是绝对不允许的。正确的做法是接入公司的密钥管理系统KMS按项目隔离定期轮换。最后一点是ID标准化。PSI最怕的不是密码学问题而是双方数据格式不统一。手机号有的带86前缀有的不带邮箱有的全大写有的全小写身份证号有15位和18位版本。这些都要在PSI之前做好标准化否则再好的协议都会被底层数据格式问题毁掉。所以项目启动时建议先让双方团队各出一批样本做一次“格式对账”再进入正式的PSI联调。我个人在实际操作中最大的体会是PSI和OT这类隐私计算协议安全性和正确性都建立在大量细节之上。你可以在性能上做取舍但绝不能对数据预处理、参数配置、日志脱敏这些工程问题掉以轻心。后面如果想继续扩展可以研究PSI-Cardinality和PSI-Sum这两个变体它们在联邦广告归因和联合统计场景里非常有用和现有联邦学习框架也能无缝衔接。先把基础PSI跑扎实再往这些方向走会顺手很多。