不经意传输（Oblivious Transfer）：密码学隐私原语的基石

概述

不经意传输（Oblivious Transfer，简称 OT）是密码学中最基础且最重要的原语之一。它解决了一个看似矛盾的问题：如何让接收方从发送方的多个消息中选择一条进行获取，同时让发送方不知道接收方选择了哪条消息，也让接收方无法得知其他消息的内容？

这一"既选择又保密"的特性使其成为隐私集合求交（PSI）、安全多方计算（MPC）和许多现代隐私保护协议的核心构建模块。

历史背景

OT 的概念最早由 Michael O. Rabin 在 1981 年提出，最初的版本称为 "1-out-of-2 随机不经意传输"（1/2-Rabin OT）。1991 年，Shafi Goldwasser 和 Silvio Micali 将其推广为更具实用价值的 "1-out-of-2 选择不经意传输"（1/2-SIG OT），并建立了完整的安全模型。

此后，研究者提出了多种变体：

• n-out-of-n OT：接收方获取所有消息
• n-out-of-2n OT：扩展场景
• 弱 OT：仅保证部分安全性
• 可证明安全 OT：基于硬数学问题构造

数学定义与形式化

基本 1/2-OT 协议

考虑两个参与方：发送方 S 持有两条消息 $(m_0, m_1)$，接收方 R 希望获取其中一条 $m_b$（其中 $b \in \{0, 1\}$ 是接收方的选择位），但不希望泄露 $b$，也不希望获得另一条消息 $m_{1-b}$。

协议执行后应满足：

• 正确性：接收方能正确获取 $m_b$
• 发送方隐私：发送方无法知道接收方选择了哪个 $b$
• 接收方隐私：接收方只能获得一条消息，无法获知另一条

公钥加密视角

OT 可以通过公钥加密体制高效实现。基于 ElGamal 加密构造的 1/2-OT 协议如下：

发送方 S 持有 $(m_0, m_1)$，选择随机数 $r_0, r_1$ 和生成元 $g$：

k_0 = g^{r_0} mod p    # 选择 0 的公钥分量
k_1 = g^{r_1} mod p    # 选择 1 的公钥分量

接收方 R 选择 $b \in \{0, 1\}$，计算：

c_b = g^s · k_b mod p   # 其中 s 是随机数
c_{1-b} = g^t           # 随机值

发送方用私钥解密：

m_0 = D(k_0, c_b) if b=0 else random
m_1 = D(k_1, c_{1-b}) if b=1 else random

这个构造保证了发送方无法区分接收方选择了哪个消息，而接收方只能解密对应自己选择的消息。

安全模型

OT 的安全性通常在游戏化模型中定义：

• 半诚实模型（Semi-honest）：参与方按照协议执行，但试图从协议执行过程中推导额外信息
• 恶意模型（Malicious）：参与方可能偏离协议，发送恶意消息

从基本 OT 到实用构造

OT 扩展（OT Extension）

基本的 OT 协议通信开销较大，难以直接用于大规模场景。Ishai-Kushilevitz-Ostrovsky-Sahai (IKOS) 扩展 提出了一种高效构造：

1. 离线阶段：用公钥加密构造少量基础 OT
2. 在线阶段：通过混淆电路（Garbled Circuit）扩展出大量 OT
3. 验证阶段：使用随机预言机（Random Oracle）确保安全性

这种扩展使得：

• 基础 OT：O(λ) 次密码学运算（λ 是安全参数）
• 扩展 OT：O(1) 次密码学运算 + O(n) 次对称密码运算

基于同态加密的 OT

基于 Paillier 或 BFV 同态加密也可以构造 OT：

发送方：加密消息 m_0, m_1 → c_0, c_1
接收方：加密选择位 b → E(b)
计算：c = c_0^{1-b} · c_1^b mod n  # 同态乘法

这种方法的优势是支持多轮 OT 和组合使用，但计算开销较高。

基于格的 OT

后量子时代，研究者提出了基于 Learning With Errors (LWE) 问题的 OT 构造：

• Regev 加密：基于 LWE 的公钥加密
• OT 构造：利用 LWE 的解密噪声特性

核心应用场景

1. 隐私集合求交（PSI）

PSI 允许两个参与方在不泄露其他元素的情况下计算集合交集。基于 OT 的 PSI 是最经典的方案：

发送方 S：集合 A = {a_1, ..., a_n}
接收方 R：集合 B = {b_1, ..., b_m}

步骤：
1. S 将 A 编码为 n 条消息（每个 a_i 对应一条）
2. R 对 B 中每个元素执行 OT，获取对应的 A 中元素
3. 通过 OT 结果计算交集 |A ∩ B|

效率：通信量 O(n + m)，计算量 O(n) 次 OT。

2. 安全多方计算（MPC）

在 Yao 混淆电路中，每个门需要执行一次 OT。对于深层电路，OT 扩展成为 MPC 的性能瓶颈。

关键优化：使用 Beaver 三元组（Beaver Triples）预计算，减少在线阶段 OT 调用次数。

3. 区块链与隐私币

Monero、Zcash 等隐私区块链使用 OT 实现：

• 环形签名：混入真实输入与其他"假"输入
• RingCT：隐藏交易金额

4. 联邦学习与差分隐私

在联邦学习场景中，各方希望在不泄露本地数据的前提下联合训练模型。OT 可用于：

• 安全聚合（Secure Aggregation）
• 梯度混淆（Gradient Masking）
• 隐私保护模型更新

工程实现要点

性能基准

常用库

• crypto-js：JavaScript 实现，适合 Web 端
• SECFP：C++ 高性能 PSI 库，内置 OT 扩展
• CryptoPP：C++ 密码学库，支持 OT 基础构造
• pyOT：Python 实验性实现，用于研究

常见陷阱

• OT 混淆电路错误：混淆表构造不正确会导致信息泄漏
• 随机数重用：OT 中随机数必须一次性使用
• 侧信道攻击：OT 实现需防护时序和功耗分析

与国密的结合

虽然标准中未专门规定 OT，但在以下场景可以结合国密算法：

SM2 替代 ElGamal

SM2 是基于椭圆曲线的公钥密码算法，可以替代 ElGamal 用于 OT 构造：

基于 SM2 的 OT：
- 发送方：生成 SM2 密钥对 (d_S, P_S)
- 接收方：选择 b，计算 H(ID_b)
- 消息加密：C_i = SM2_Encrypt(P_S, m_i)
- 解密：D(C_b, d_S) = m_b

SM3 作为随机预言机

OT 构造中常用的哈希函数可以用 SM3 替换 SHA-256，确保国密合规。

国密 OT 的应用场景

• 政务数据共享：多个政府部门在不泄露原始数据的前提下共享信息
• 金融风控：银行间联合反洗钱，不泄露客户详情
• 医疗数据协作：医院间联合研究，保护患者隐私

安全分析

已知攻击

• 选择性失败攻击：接收方可能选择性拒绝某些消息
• 重放攻击：协议执行过程中可能重放旧消息
• 中间人攻击：未经认证的 OT 通道可能被拦截

防御措施

• 认证机制：结合数字签名（如 SM2 签名）
• 密钥协商：使用 authenticated key exchange (AKE)
• 零知识证明：证明协议执行的正确性

后量子安全

基于格的 OT 构造（如基于 RLWE）被认为是后量子安全的。NIST PQC 标准化过程中，相关构造正在成为研究热点。

总结

不经意传输（OT）作为密码学的核心原语，在隐私保护领域扮演着不可替代的角色。从 Rabin 的原始构想到现代的扩展方案，OT 不断演进以适应不同的安全需求和性能要求。

随着隐私计算、联邦学习和区块链等技术的兴起，OT 的应用场景正在不断扩大。掌握 OT 的原理和实现，对于深入理解现代密码学和隐私保护技术至关重要。

延伸阅读

• Rabin, M.O. (1981). How to exchange secrets with oblivious transfer.
• Chaum, D. (1991). Blind signatures for untraceable payments.
• Ishai, Y., et al. (2004). Extending oblivious transfers efficiently.
• Goldreich, O. (2001). Foundations of Cryptography.

参考链接：

• 隐私集合求交（PSI）详解
• 安全多方计算原理
• 国密 TLS 协议详解