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. 隐私集合求交的真正地基：不经意传输（OT）

2.1 怎么理解OT：一台“看不见选择的自动售货机”

不经意传输（Oblivious Transfer，OT）是密码学里的一个基础原语，它的概念比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 PSI（DH-PSI）是早期最经典的PSI方案，也是很多技术人员第一次接触PSI时看到的那个协议。它的原理基于DH交换的数学性质：双方各自生成随机私钥a和b，然后把自己的ID分别做两次盲化：A方计算 H(x)^a，B方计算 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扩展的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 常见问题速查表

拿实际运行中踩过的坑整理成一张表，供大家遇到问题时快速定位：

6.2 实操心得：日志、脱敏与盐值管理

这里分享几个我反复跟团队强调的细节。

日志脱敏是第一优先级。很多PSI库调试时候会在日志里输出元素哈希或者中间结果，稍不注意原始ID就会打出来。生产环境中日志是必须经过脱敏管道处理的，至少要把原始ID替换成对应哈希值。我见过因为日志泄露导致整个合规评审被卡住的真实案例，这个坑成本极高。

盐值管理要纳入密钥管理体系。PSI协议里如果用到随机盐或者盲化因子，它就不是普通配置项，而是密码学密钥。很多人开发时习惯把盐值硬编码在配置文件里，这在生产环境是绝对不允许的。正确的做法是接入公司的密钥管理系统（KMS），按项目隔离，定期轮换。

最后一点是ID标准化。PSI最怕的不是密码学问题，而是双方数据格式不统一。手机号有的带86前缀有的不带，邮箱有的全大写有的全小写，身份证号有15位和18位版本。这些都要在PSI之前做好标准化，否则再好的协议都会被底层数据格式问题毁掉。所以项目启动时，建议先让双方团队各出一批样本，做一次“格式对账”，再进入正式的PSI联调。

我个人在实际操作中最大的体会是：PSI和OT这类隐私计算协议，安全性和正确性都建立在大量细节之上。你可以在性能上做取舍，但绝不能对数据预处理、参数配置、日志脱敏这些工程问题掉以轻心。后面如果想继续扩展，可以研究PSI-Cardinality和PSI-Sum这两个变体，它们在联邦广告归因和联合统计场景里非常有用，和现有联邦学习框架也能无缝衔接。先把基础PSI跑扎实，再往这些方向走，会顺手很多。