跳转到内容
Jason's Study

Rabin 遗忘传输 — 发送方永远不知道你收到了什么

是什么

遗忘传输（Oblivious Transfer，OT）是这样一个操作：发送方把一条消息发给接收方，消息以 1/2 的概率被接收，但发送方完全不知道接收方有没有收到。

日常类比：你把一封信投进一个神奇邮箱——硬币翻转，正面朝上对方收到，反面则信消失——但你对结果永远一无所知。

这份 1981 年的哈佛技术报告（手写稿，2005 年才扫描公开）由 Michael O. Rabin 写成，首次把这个”遗忘”语义形式化，并给出第一个基于 RSA 的具体协议。四十年后，OT 被证明是安全多方计算（MPC）的完备原语——只要有 OT，就能安全地计算任意函数。Garbled Circuits、PSI、VOLE……几乎所有现代密码协议都建在 OT 之上。

OT 之所以叫”遗忘”，是因为传输过程对发送方来说就像遗忘了结果一样——发送方的内存里永远没有”谁收到了”这条信息。这个性质在隐私计算场景里极其珍贵：它把隐私从”约定不泄露”变成了”协议层面无法知道”。

为什么重要

不理解 OT，下面这些事都没法解释：

  • 为什么两个公司能在不泄露各自客户名单的情况下，知道有多少共同客户（PSI / 隐私集合求交）
  • 为什么 Garbled Circuit（Yao 混乱电路）能让两方安全地运行任意程序，而双方都看不到对方的输入
  • 为什么 OT 扩展（IKNP 2003）能用少量”真 OT”生成海量廉价 OT，让 MPC 在实践中跑得足够快
  • 为什么 Kilian 1988 能用 OT 证明”安全计算的完备性”——OT 是密码协议界的”图灵完备”

核心要点

1. Rabin OT 协议机制

RSA 一句话背景：RSA 是一种基于”把两个大素数 p、q 乘在一起容易，但逆向把乘积 N 拆回 p 和 q 极难”这个事实的加密方法。这个”分解困难性”贯穿整个协议。

发送方生成 RSA 公钥 (N = pq, e)，把消息 m 加密为 mᵉ mod N，与 (N, e) 一起发出。接收方随机挑一个 x，发给发送方 x² mod N。发送方随机找一个平方根 y（x² mod N 恰好有四个平方根，发送方知道 p、q 所以能算出所有四个），发回去。如果接收方拿到的 y 和自己选的 x 不同（即 y ≠ ±x mod N），接收方就能用数论技巧推出 p 和 q，进而解密 m；否则什么都得不到。发送方对 y 是否”有用”毫不知情。

类比：发给对方一把钥匙，这把钥匙有一半概率能开锁，但你永远不知道门开没开。

2. “遗忘”的安全含义

协议满足两个方向的隐私：

  • 接收方：若拿到了 m，发送方无从得知（发送方只看到 x² mod N，无法判断 y 是否和 x 碰撞）。
  • 发送方：若接收方没拿到，发送方无需担心消息被推断——接收方只看到一个无关平方根。

类比：彩票开奖，发行方不知道谁中了，中奖者只知道自己中了，两边都不知道对方的私信息。

3. Rabin OT 与 1-out-of-2 OT 的关系

Rabin OT 定义”以 1/2 概率传一条消息”；1-out-of-2 OT（1oo2-OT）定义”发送方有两条消息，接收方选一条取走，各自对另一条一无所知”。Claude Crépeau 在 1988 年证明两者可以相互转化，是等价原语。现代实践几乎都用 1oo2-OT，因为接收方选择哪条消息的语义更直接。

实践案例

案例 1：Garbled Circuit 里的输入传输

Alice 用 Yao 的 Garbled Circuit 让 Bob 计算 f(a, b)，其中 b 是 Bob 的私有输入。Alice 为每条输入线路准备两把”线路密钥”（k₀, k₁）。Bob 需要取走 k_b 但不让 Alice 知道 b。

Alice 持有：     Bob 持有：
k₀（0 的密钥）   选择位 b（0 或 1，私密）
k₁（1 的密钥）


─── 执行 1-out-of-2 OT ────────────────────────
   Alice 不知道 b 是什么
   Bob  只拿到 k_b，不知道 k_{1-b}
   ✓ 正确性：Bob 拿到了正确密钥
   ✓ 接收方隐私：Alice 不知 b
   ✓ 发送方隐私：Bob 不知另一把密钥

对每个输入位执行一次 OT，就完成了整条电路的私密输入传递。这是 Garbled Circuit 协议的唯一需要交互的步骤——线路加密的部分可以由 Alice 离线完成。

案例 2：IKNP OT 扩展——用少量贵 OT 生成海量便宜 OT

PSI 需要对百万级元素集合做 OT，直接跑 RSA 协议代价太高。IKNP 2003 的思路：

  1. 基础 OT：用公钥密码跑 κ 次（如 128 次）真正的 1oo2-OT，得到 κ 个随机密钥对。
  2. OT 扩展：用这 κ 个密钥对作为种子，用伪随机生成器”伸长”成 n 组 OT 输出（n >> κ）。
  3. 双方各自做矩阵转置和 XOR 操作，完成 n 次 OT——通信量几乎只有对称加密的开销。
真实 OT（公钥，128 次）→ PRNG 扩展 → 百万次 "软件 OT"
代价: O(κ²) 公钥操作 + O(n·κ) 对称操作，远比 O(n) 公钥操作便宜

案例 3：隐私集合求交（PSI）基本框架

两家公司各有用户集合 A（Alice）和 B（Bob），希望知道 A∩B 的大小，但不暴露各自完整名单。

1. Alice 选 PRF 密钥 k
2. 用 OT：Alice 有 F(k, a₁)…F(k, aₙ)，Bob 选择 b∈B，拿到对应 F(k, b)
   ——Bob 只知道自己元素对应的 PRF 值
3. Alice 公开 { F(k, a) | a∈A }
4. Bob 比对：哪些 F(k, b) 在 Alice 的集合里，哪些就是交集元素
5. 全程 Alice 不知道 Bob 选了什么，Bob 不知道 Alice 完整集合

踩过的坑

  1. Rabin OT ≠ 1oo2-OT，不能直接当接口互换：两者语义不同——Rabin OT 里接收方以 1/2 概率不确定地得到消息，而 1oo2-OT 里接收方确定性地得到选定的那条。直接把 Rabin OT 套进期望 1oo2-OT 的协议会导致安全洞或正确性错误；需要用 Crépeau 转化。

  2. 原始协议不满足 UC 安全，组合会出问题：Rabin 1981 给出的是基础语义安全，不是通用可组合（UC）框架下的安全。在并发执行或和其他协议组合的场景，需要用 Commitment Scheme 或 Cut-and-Choose 加强，否则 session 间的关联攻击可能攻破安全性。

  3. RSA 假设不抗量子计算：OT 的 RSA 实现在量子计算机面前不安全（Shor 算法可分解 N）。后量子 OT 需要改用格密码（如 LWE）或椭圆曲线 OT，目前工程主流是 SoftSpokenOT 等实现。

  4. 引用这篇论文要小心出处：它原本是 1981 年哈佛手写报告，曾几乎失传；2005 年才上传 IACR ePrint（2005/187）。引用时应注明”Harvard University Technical Report TR-81, 1981”，不要仅写 ePrint 2005 年，会被误认为是 2005 年的新作。

适用 vs 不适用场景

适用：

  • 两方或多方安全计算中需要传递私有输入（Garbled Circuit 的标准构件）
  • 隐私集合求交（PSI）、隐私信息检索（PIR）等隐私保护协议的底层原语
  • 需要”发送方对结果盲”的场景：彩票、拍卖投标、秘密共享密钥协商
  • 通过 OT 扩展（IKNP/SoftSpoken）批量生成大规模 OT，支持现代实用 MPC

不适用：

  • 不需要隐私保护、双方都知道结果的普通消息传输（用 TLS 就够了）
  • 量子安全场景（需要基于格的 OT 替代，RSA 版本不抗量子）
  • 在未做 UC 加固的情况下并发组合多个协议（会出现安全漏洞）
  • 接收方必须”确定性拿到某条消息”的场景（Rabin OT 有 1/2 失败概率，需转换为 1oo2-OT）

历史小故事（可跳过）

  • 1981 年：Michael O. Rabin 在哈佛大学 Aiken 计算实验室用手稿写成这篇技术报告（TR-81）。没有经过正式学术期刊审稿，副本有限，流传靠复印。
  • 1985 年：Even、Goldreich、Lempel 提出 1-out-of-2 OT，为 MPC 提供了更直接的接口，并基于 RSA 给出了严格构造。
  • 1988 年：Claude Crépeau 证明 Rabin OT 与 1oo2-OT 等价；同年 Joe Kilian 证明 OT 对安全计算具有完备性——OT 是密码世界的”万能基础积木”。
  • 2003 年：Ishai、Kilian、Nissim、Petrank 发表 IKNP OT 扩展，让实用 MPC 成为可能：用 128 次公钥 OT 生成数百万次 OT。
  • 2005 年：Tal Rabin 与 Mohammad Sadeq Dousti 将 1981 年手稿扫描排版，上传至 IACR ePrint（2005/187），这篇几乎失传的奠基论文才重新进入公众视野。

学到什么

  1. “发送方对结果盲” 是一个非常强的隐私原语，它让”隐私输入传输”这件事有了形式化基础——Garbled Circuit 等协议都靠它活着。
  2. 完备性定理是密码协议里的”图灵完备”：一个原语能构造所有安全计算，意味着把 OT 实现好就够了，上层协议的正确性和安全性可以在 OT 之上归约。
  3. 等价转化（Rabin OT ↔ 1oo2-OT）告诉我们：形式定义不同的原语可以在安全归约意义下等价，选择哪种定义更多是工程便利性而非本质差异。
  4. 论文可以在正式出版四十年后仍影响工业界：OT 从 1981 年手稿到 2020 年代的 PSI/MPC 工具库，证明奠基性工作的生命周期远超任何框架或语言。

延伸阅读

关联

  • ot-1989 —— 基于 Rabin OT 演进出的具体 OT 构造，1oo2-OT 的重要参考实现
  • chillotti-tfhe-2016 —— 全同态加密方案 TFHE，与 OT 同属密码学安全计算家族
  • aes —— 对称加密原语，OT 扩展（IKNP）的内层高效组件
  • hotstuff-2019 —— BFT 共识协议，MPC 在区块链场景中的上层协议之一
  • gray-1978-notes —— Jim Gray 1978 数据库事务笔记，与 OT 同属”不泄露中间状态”的设计哲学

反向链接

  • chillotti-tfhe-2016 —— Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds
  • freedman-psi-2004 —— Freedman-Nissim-Pinkas PSI 2004 — 两个人怎么找共同好友而不暴露各自通讯录
  • gray-1978-notes —— Gray 1978 — 数据库操作系统讲义，事务/2PL/2PC/恢复一次讲完
  • hotstuff-2019 —— HotStuff — 让换领导也只花线性消息的 BFT 共识