1. 先从直觉说起OT到底解决了什么实际问题我第一次接触不经意传输这个词是在一个隐私计算项目的评审会上。当时同事问了一个非常尖锐的问题接收方真的能把选择藏住吗发送方真的无法知道对方拿了哪条消息我第一反应是这不就是数据包加密吗但真正把协议翻完、亲手实现了一遍之后才发现这个工具远比表面看起来精妙——它不是在藏数据而是在藏选择本身。不经意传输Oblivious Transfer简称OT描述的是一个双人交互场景发送方手里有两条消息接收方想拿其中一条但接收方不希望发送方知道自己选的是哪一条发送方则希望接收方只能拿到选中的那一条剩下的那条无论如何都拿不到。注意这两个要求是同时成立的缺一不可。很多人一开始会混淆以为OT只是接收方匿名选择忽略了发送方保证消息不被多拿的另一半这就会在后续理解安全计算协议时踩坑。从定义上讲最常见的1-out-of-2不经意传输记作OT(2,1)是这样的发送方输入两条等长消息 m0 和 m1。接收方输入一个选择比特 b ∈ {0, 1}。协议结束后接收方得到 mb但对 m1-b 一无所知。发送方不能从协议交互中判断出 b 到底是 0 还是 1。如果发送方和接收方中有人不按协议流程走恶意行为协议的安全性会退化这就要引入恶意模型下的额外处理后面专门讲。除了1-out-of-2之外还有1-out-of-n版本接收方从 n 条消息中选一条发送方不知道选了哪条。这个变体常用于秘密信息检索、隐私查询之类的场景。实际工程中1-out-of-2OT是最基础的原语很多n选一协议也都是先拆成多个1选2来实现。你会问这样一朵双人交互舞到底有什么用它不是一个可以直接面向普通用户的App但它几乎是所有安全多方计算协议的基础砖块。从姚期智的混淆电路到隐私求交PSI、安全聚合、门限签名几乎都离不开OT。可以说如果密码学工具箱里只能留三样东西我会留对称加密、哈希函数和OT。我自己的体会是理解OT的最好方式不是先硬啃论文里的符号而是先接受一个事实双方在协议结束的时候对同一批数据的知识状态是不对称的。这种不对称知识恰好是安全计算协议里最难构造、也最有用的一种资源。哈希和加密可以带给你不可读但OT带给你的是选择性可见。2. 安全计算里的关键角色从姚氏混淆电路到OT扩展很多人第一次看到OT是在理解姚氏混淆电路Garbled Circuit的时候。姚氏协议把计算任务表示成一个电路发送方对每条电路输入线生成一对随机标签用来代替真实的0/1值。接收方要计算电路就必须逐条获取自己输入线上对应的标签但不能让发送方知道他的输入到底是什么。换句话说这正好就是一个OT调用发送方提供两个标签接收方根据自己的输入比特取走其中一个。所以OT在这里不是可有可无的优化而是协议能跑起来的必要条件。更准确地说混淆电路本身已经通过加密和打乱保证了计算过程的不可读但如何把接收方的输入安全地传进电路这件事必须靠OT。没有了OT接收方就只能把自己的输入明文交给发送方安全计算的意义就荡然无存。随着协议规模的扩大按每条输入线调用一次OT会很笨重。比如隐私求交场景里双方要对几百万个元素做集合比较如果每个元素都调用一次公钥密码学OT计算量会直接爆炸。于是OT扩展OT Extension走上前台。它的核心思想是先通过少量基础OT比如128次交换一些随机种子再用对称密码学伪随机生成器、哈希函数把这些种子放大成上千上万次独立OT调用。因为对称密码运算比公钥运算快几个数量级OT扩展让OT从实验室玩具变成了可以上生产环境的工具。在这个意义上OT和安全计算的关系就像水泥和混凝土的关系。你可能不会直接看到水泥但整栋楼的地基全靠它撑着。理解了OT再去看MPC、PSI、PIR这些高端协议会发现很多设计动机都源于如何更高效、更安全地调用OT。3. 手工拆解一个经典OT协议基于RSA的1-out-of-2实现理论说再多不如把协议流程摊开来看。我下面要拆解的是一个非常经典的基于RSA的OT构造结构清晰适合入门也是很多教学材料里的标准范例。它虽然在实际项目中效率不高RSA运算比较贵但非常有助于理解不经意性到底来自哪里。3.1 完整流程假设发送方Alice持有两条消息 m0,m1接收方Bob的选择比特是 b。双方事先协商好一个RSA模数 N p q 以及公钥指数 e其中 gcd(e, φ(N)) 1。实际使用中Alice可以直接生成一对RSA密钥并把公钥 (N,e) 发给Bob私钥 d 自己保留。协议分五步Bob选择两个随机数 k 和一个随机元素 g ∈ ℤ_N^*。这里的 g 是一个可逆元素即满足 gcd(g, N) 1。Bob根据选择比特计算一个值 v如果 b 0则 v k^e mod N如果 b 1则 v g · k^e mod N。Bob把 v 发送给Alice。Alice收到 v 后分别计算 k0 v^d mod N 和 k1 (v / g)^d mod N。Alice用 k0, k1 作为加密密钥例如取哈希后用作AES密钥分别加密 m0,m1并把两份密文 c0,c1 发送给Bob。Bob利用自己手里的 k 解密对应那份密文如果 b 0则 k k0Bob能解开 c0如果 b 1则 k k1Bob能解开 c1。注意这里并不是直接拿 k 去解密而是把 k 哈希成对称密钥然后解AES密文。实际操作里第5步加密方式建议用H(k0) xor m0搭配一次一密或者用AES(keyH(k0))这样可以避免泄露消息结构。3.2 为什么是不经意的从Bob角度想他只把 v 发给了Alice。Alice即使拿到 v也无法判断 v 到底是 k^e 还是 g·k^e因为在模 N 下这两者看起来都是均匀随机数。除非Alice能分解 N 或者拿到私钥 d 反推 k否则她没有办法区分 b。这保证了接收方的选择隐私。从Alice角度想Bob只掌握了原始随机数 k而 k 只能解出 k0 和 k1 中的一个。原因在于如果 b0那么 Bob 知道的是 k但不知道 g 的 e 次方对应的随机关系因此无法推出 k1 (v/g)^d (k^e / g)^d如果 b1同理推不出 k0。直观上Bob在协议开始前只知道一个随机种子而Alice用两种不同方式隐藏了两把钥匙Bob手里的单个种子只能打开其中一把锁。发送方隐私由此成立。3.3 需要注意的坑这个协议虽然直观但直接照搬上生产会很危险RSA参数必须够大。一般建议至少2048位模数不然攻击者可以直接分解 N。g 必须是模 N 的可逆元素否则 gcd(g,N) ≠ 1 时Alice可以利用最大公约数泄漏的因子来破解。随机数质量不过关是致命的。Bob选择 k 时必须使用密码学安全随机数生成器CSPRNG不能用普通rand()。这个协议不是恶意安全的。如果Alice是恶意的她可以故意发一个不合理的 N 或者构造密文让Bob无法正常完成计算如果Bob是恶意的他也可以发送特殊构造的 v 来探测信息。恶意模型下需要额外加零知识证明成本会高很多。效率问题。每次OT至少涉及一次RSA指数运算公钥运算比对称加密慢好几个量级所以这个构造只适合用来讲原理不适合大规模工程落地。我建议读者自己用Python或Go写一版这个协议跑一遍加解密流程再看一遍密文能不能正确解开。你会发现理论上是安全的和代码里能跑通、参数选对之间还有很长的路这也是我强烈建议大家动手的原因。4. OT扩展从纸面协议到工程可用的放大器直接调用公钥密码学OT每跑一次都伴随大整数模幂运算在百万级数据量的场景里完全扛不住。OT扩展的出现把这个问题变成了先花一部分公钥成本再用对称密码学放大。4.1 一个直观类比可以把基础OT想象成播种机它先在双方之间播下少量相关性种子然后用一个伪随机生成器PRG把这些种子长成一大片随机性森林。关键在于这些长出来的随机性不是彼此独立的而是带有一种特殊的关联接收方知道每一列随机性中哪一条对应了他的选择发送方则完全不知道选择分布。通过精心构造的转换这种关联可以被“洗”成许多独立且安全的OT实例。4.2 IKNP协议的核心思路目前业界最常用的OT扩展框架是IKNPIshai、Kilian、Nissim、Petrank2003。我大概描述一下它的样子方便你建立直觉设安全参数为 κ一般取128或256。先执行 κ 次基础OT。发送方为每条基础OT提供两个 κ 比特随机字符串接收方根据自己的随机比特串 r[1..κ] 选择其中一个。这一阶段结束后发送方和接收方共享了一组相关性随机串。然后双方利用这些相关随机串作为种子运行一个伪随机生成器把每个种子扩展成很长的伪随机串。对每一个目标OT实例发送方根据自己的两列随机串计算出两条消息接收方通过自己手里那列随机串恢复出它选择的那一条。为了保证不同实例之间的随机性互不相关最后通常要过一个哈希函数比如 SHA-256 或者固定键的AES做混合避免相关性被攻击者利用。有了IKNP一次基础OT的花费可以摊到几千、几万个OT上。实际工程里基础OT数量只和统计安全参数相关和你要生成的OT总数无关这是扩展方案能保持高效的根本原因。4.3 效率数据参考以libOTe库为例在我用过的桌面级CPU上做百万次OT扩展耗时大约在几十毫秒到几百毫秒之间远低于直接调用公钥运算的秒级耗时。当然这个数字和网络延迟、并行度、哈希实现都有关系但数量级上的优势是明确的。4.4 工程里的坑OT扩展的坑往往出在参数和实现细节上种子必须充分混合。有的实现为了省时间直接用PRG输出作为最终随机串却没有做相关性消除容易被侧信道或统计攻击。正确做法是使用相关性鲁棒哈希。并发下的随机性竞争。如果多个线程共用同一个伪随机生成器且没有加锁或隔离扩展出来的OT会带有相关性。基OT不能复用。如果不同会话共享同一组基础OT种子接收方在选择位向量上可能会被追踪整个隐私保护失效。我个人的建议是除非你要写论文否则不要从零实现IKNP。直接用成熟实现比如libOTe、emp-toolkit里的ot组件然后把精力放在上层协议的正确性上。真正让你项目翻车的往往不是OT本身而是调用OT周围的协议逻辑。5. 安全模型和选型从半诚实到恶意安全的现实抉择很多人看完OT协议后会有一个疑问这些协议看起来都能保护隐私那直接把两个库拼起来不就行了吗实际上安全计算协议的安全性是有模型的不同模型对应不同威胁假设工程实现和协议设计的复杂程度天差地别。5.1 半诚实模型与恶意模型半诚实模型Semi-honest model假设双方都按照协议步骤执行只是会试图从收到的消息中获取额外信息。这个模型适合双方互不信任、但还没有到互相使坏程度的情况比如数据联合统计。它的优点是协议简单、性能好。恶意模型Malicious model则假设参与方可以任意偏离协议发送方可以篡改消息接收方可以构造恶意输入。要在这个模型下保持安全通常需要加约束证明、零知识证明或一致性检查让偏离协议的行为能被发现。代价是通信量和计算量显著上升。举例来说在基于RSA的OT里如果Bob是恶意的他可以故意不选择一个 k而是构造 v 来探测Alice的私钥信息。即使探测不到私钥也可能通过多次会话统计出额外信息。要对付这种行为就得要求Bob额外证明我知道某个 k 满足 v k^e 或 v g · k^e而这个证明本身又要引入更多密码学原语。5.2 真实项目里怎么选如果项目是原型验证、内部数据联合半诚实模型足够。如果要面对公开网络、敌意用户就得上恶意安全或者至少可验证的安全模型。OT层面通常会对基础OT做恶意保护比如用带零知识证明的OT再用OT扩展放大这样恶意安全的成本被控制在基础部分扩展部分还是高效的。实际操作中我会按照下面这个顺序做选型先明确数据规模、双方身份、网络环境。再决定安全模型是半诚实还是恶意。然后选适合的OT库和底层曲线/群结构。最后做端到端的安全审计尤其是随机数生成、输入校验、密钥派生这些环节。5.3 常见坑位清单把开源实现当安全保证。开源库也可能有bug而且很多库默认的参数选择未必适配你的场景比如生成元 g 选择不当、统计安全参数设得太低。忽略输入长度差异。OT协议通常要求两条消息长度相同如果 m0 和 m1 长度不一致接收方单凭密文长度就能判断发送方哪条消息更长这会破坏发送方隐私。重用密文/密钥。有些简化版实现会把同一个加密密钥用于多个OT实例导致接收方可以通过交叉对比推断额外信息。网络超时和中断处理。OT协议通常是交互式的如果一方在中间收到半截消息就继续处理容易产生不一致状态。高可用实现里必须加入消息认证和会话标识。性能测试只看OT本身忽略网络往返。OT扩展虽然计算量小但如果每次OT调用都单独走一次网络RT吞吐量会被RTT拖垮。工程上通常会把批量OT合并到一个往返里再切分成多个逻辑OT。踩过这些坑之后我的经验总结就一句话OT是地基不是万能砖。它保证了选择性可见这个核心性质但上层协议里的数据格式、状态管理和输入校验同样决定了整个系统是否安全。你越是把它当作一个普普通通的函数来调用越要在四周加上足够多的护栏。如果你真的想深入这块我建议看三样东西一是Yehuda Lindell的《Secure Computation》讲义里面对OT和安全计算的关系讲得非常清楚二是IKNP那篇OT扩展的原始论文虽然是2003年的但到今天仍然不过时三是libOTe的源码里面编码了很多实现技巧很多细节是论文里不会写的。把这几个啃下来你再看上层MPC协议会觉得很多设计忽然串起来了。