Skip to content

Chapter 5 茫然传输和茫然传输扩展

1 两方信息论安全 OT 不存在

茫然传输理想功能 \(F_{OT}\)

发送方 \(P_s\) 输入两条消息 \((x_0,x_1)\)，接收方 \(P_r\) 输入选择位 \(b\in\{0,1\}\)，\(P_r\) 只得到 \(x_b\)，\(P_s\) 得到 \(\bot\)：

  • 接收方隐私：发送方不应知道接收方选择了哪一条，即不知道 \(b\)
  • 发送方隐私：接收方除 \(x_b\) 外，不应学到 \(x_{1-b}\)
  • 完备性地位：OT 是两方安全计算的完备原语，很多 2PC / MPC 协议都把 OT 当作基础模块

若 \(x_0,x_1\in\{0,1\}\)，则：

\[ x_b = (1\oplus b)x_0 \oplus b x_1. \]

使用两方 OT 构造两方 AND 协议

令发送方输入 \((x_0,x_1)=(0,a)\)，接收方输入选择位 \(b\)，则接收方得到 \(x_b = ab\)，因而 OT 可以直接实现两方 AND。

如果存在信息论安全的两方 OT，那么就存在信息论安全的两方 AND 协议。但两方 AND 本身不可能信息论安全，因此两方 OT 也不可能信息论安全。

两方 AND 不可能性的证明思路

设双方输入为 \(b_0,b_1\in\{0,1\}\)，目标输出为 \(y=b_0\land b_1\)：

令 \(\mathcal{T}(c,d)\) 表示在输入 \((b_0,b_1)=(c,d)\) 时，协议可能产生的全部消息集合与输出的集合，即

\[ \mathcal{T}=(m_{01},m_{11},\dots,m_{0s},m_{1s},y) \]

那么有以下四个关键断言：

  • \(\mathcal{T}(0,0)=\mathcal{T}(0,1)\)：否则存在只出现在 \(\mathcal{T}(0,0)\) 的消息集合，\(P_0\) 可据此区分 \(b_1\)，破坏隐私
  • \(\mathcal{T}(0,0)=\mathcal{T}(1,0)\)：对称地，若两者不同，则 \(P_1\) 可据此区分 \(b_0\)，破坏隐私
  • \(\mathcal{T}(0,1)\cap \mathcal{T}(1,0)\subseteq \mathcal{T}(1,1)\)：若 \(\mathcal{T}\) 同时能由输入 \((0,1)\) 和 \((1,0)\) 产生，则把对应随机性拼接，可推出它也能由 \((1,1)\) 产生
  • \(\mathcal{T}(0,0)\cap \mathcal{T}(1,1)=\varnothing\)：当输入为 \((0,0)\) 时必须输出 \(0\)，当输入为 \((1,1)\) 时必须输出 \(1\)

由 1、2、3 可得 \(\mathcal{T}(0,0) = \mathcal{T}(0,1) = \mathcal{T}(1,0) \subseteq \mathcal{T}(1,1)\)，这与 4 的 \(T(0,0)\cap T(1,1)=\varnothing\) 矛盾！

两方场景下，若不引入额外假设，就无法同时满足正确性和信息论隐私，因此现实中的两方 OT 通常必须依赖计算假设（如 DDH）或额外参与方 / 硬件 / 预处理。

从 OT 中来，到 OT 中去
  • OT 可以用于安全地计算任何函数，构造发送方和接收方角色互换的 OT，构造 N 选 k OT（k-out-of-N-OT）
  • 基于增强陷门置换（enhanced trapdoor permutation）、DDH 假设、RSA 假设、格密码学（lattice-based cryptography）等方法可以构造 OT 协议
  • 注：不能以黑盒的方式基于公钥加密 (Public Key Encryption, PKE) 构造 OT

2 基于 DDH 的半诚实安全 OT

设 \(\mathbb{G}\) 为阶为 \(q\) 的循环群，生成元为 \(g\)，发送方消息 \(x_0,x_1\in\mathbb{G}\)，接收方选择位 \(b\in\{0,1\}\)：

  1. 接收方准备公钥：取 \(\text{sk}\xleftarrow{}_{\$}\mathbb{Z}_q\)，令 \(\text{pk}_b=g^{\text{sk}}\)，\(\text{pk}_{1-b}\xleftarrow{}_{\$}\mathbb{G}\)，将 \((\text{pk}_0,\text{pk}_1)\) 发送给发送方
  2. 发送方加密两条消息：取 \(r\xleftarrow{}_{\$}\mathbb{Z}_q\)，令 \(v=g^r\)，计算 \(c_0=x_0\cdot \text{pk}_0^r\)，\(c_1=x_1\cdot \text{pk}_1^r\)，将 \((v,c_0,c_1)\) 发送给接收方
  3. 接收方恢复所选消息：\(x_b = c_b / v^{\text{sk}}\)
正确性

因为 \(c_b = x_b\cdot \text{pk}_b^r = x_b\cdot g^{r\cdot \text{sk}} = x_b\cdot v^{\text{sk}}\)，所以接收方可正确恢复 \(x_b\)

安全直觉
  • 接收方隐私：发送方看到的 \(\text{pk}_0,\text{pk}_1\) 都是群中的随机元素，它无法区分哪一个公钥对应已知私钥，因而无法判断接收方选的是 \(0\) 还是 \(1\)
  • 发送方隐私：对未选择的一侧 \(\text{pk}_{1-b}\)，三元组 \((g^r,\text{pk}_{1-b},\text{pk}_{1-b}^r)\) 在 DDH 假设下与随机三元组不可区分，因此 \(c_{1-b}=x_{1-b}\cdot \text{pk}_{1-b}^r\)，看起来就像被一个随机群元素一次性掩盖，从而隐藏了 \(x_{1-b}\)

若 DDH 问题在群 \(\mathbb{G}\) 上困难，则上述协议对静态半诚实敌手 UC-安全实现 理想功能 \(F_{OT}\)

情况 1：发送方 \(P_s\) 被攻陷

  • 环境输入：\(\mathcal{Z}\) 给被攻陷的 \(P_s\) 输入 \(x_0, x_1\)，给诚实的 \(P_r\) 输入 \(b\)
  • 理想 OT 执行：\(P_s\) 和 \(P_r\) 分别将输入发送给 \(\mathcal{F}_{OT}\)，\(\mathcal{F}_{OT}\) 计算后给 \(P_r\) 输出 \(x_b\)，\(P_r\) 再将结果发给环境
  • 模拟器模拟视图：模拟器 \(S\) 直接从群 \(\mathbb{G}^2\) 中随机选取两个元素作为 \(pk_0, pk_1\)，将构造好的 \(P_s\) 状态（包含随机公钥对）发给环境 \(\mathcal{Z}\)

不论在理想世界和真实世界中，无论 \(P_r\) 的输入 \(b\) 是 \(0\) 还是 \(1\)，\((pk_0, pk_1)\) 都是两个群上的随机元素。环境 \(\mathcal{Z}\) 无法区分现实视图和理想视图，被攻陷的 \(P_s\) 无法从交互中获取任何关于 \(b\) 的信息，接收方的隐私得到保护。

情况 2：接收方 \(P_r\) 被攻陷

核心依赖DDH假设（判定Diffie-Hellman问题困难），我们来拆解：

真实协议中，\(c_{1-b} = x_{1-b} \cdot pk_{1-b}^r\)。其中 \(pk_{1-b}\) 是 \(P_r\) 生成的随机群元素，\(r\) 是 \(P_s\) 选取的随机数。

\((v, pk_{1-b}, pk_{1-b}^r) = (g^r, pk_{1-b}, pk_{1-b}^r)\) 是标准的 DDH 三元组，根据 DDH 假设，\(pk_{1-b}^r\) 与群上的随机元素是计算不可区分的，因此 \(c_{1-b}\) 也与群上的随机元素计算不可区分。

理想世界中，模拟器直接选取群上的随机元素作为 \(c_{1-b}\)，因此真实与理想的 \(c_{1-b}\) 是计算不可区分的。

结合 \(v\) 和 \(c_b\) 分布完全一致，整个视图 \((v, c_0, c_1)\) 对环境 \(\mathcal{Z}\) 来说是不可区分的，敌手无法从协议交互中推导任何关于 \(x_{1-b}\) 的信息，发送方的隐私得到了保护，协议满足半诚实安全。

恶意接收方攻击

若接收方不按协议生成公钥，而是恶意构造两个自己都知道私钥的公钥 \(\text{pk}_0,\text{pk}_1\)，则它在收到 \((v,c_0,c_1)\) 后可同时解出 \(x_0\) 和 \(x_1\)，从而彻底破坏发送方隐私。

半诚实证明默认接收方只会对其中一个公钥知道离散对数，一旦敌手偏离协议，这个关键结构就会失效。

可以引入协助者（Helper \(P_h\)），利用抗碰撞哈希（CRH）作为承诺，确保即使一方恶意，协议依然安全。

3 三方恶意安全 OT

为阻止接收方双私钥作弊，引入一个半诚实且不串通的辅助方 \(P_h\)。

协议流程详解

  1. 辅助方准备随机掩码：取 \(p_0,p_1\xleftarrow{}_{\$}\mathcal{M}\)，\(r_0,r_1\xleftarrow{}_{\$}\mathcal{R}\)，\(\beta\xleftarrow{}_{\$}\{0,1\}\)，计算 \(c_{\beta\oplus 1}=H(p_{\beta\oplus 1},r_{\beta\oplus 1})\)，向发送方发送 \((p_0,r_0,p_1,r_1)\)，向接收方发送 \((\beta,p_\beta,r_\beta,c_{\beta\oplus 1})\)

  2. 接收方绑定自己的选择：计算 \(\tau=b\oplus \beta\)，令 \(c_\beta=H(p_\beta,r_\beta)\)，将 \((\tau,c_0,c_1)\) 发送给发送方

  3. 发送方验证并发送掩码密文：检查 \(c_0=H(p_0,r_0)\)，\(c_1=H(p_1,r_1)\)，若通过，则发送 \(e_0 = x_0 \oplus p_\tau\)，\(e_1 = x_1 \oplus p_{\tau\oplus 1}\)

  4. 接收方恢复目标消息：\(x_b=e_b\oplus p_\beta\)

安全直觉

  • 协助者被攻陷：哈希抗碰撞性保证承诺一致性；否则协议中止。若一致，接收方得到 \(x_b\)，正确性成立。协助者无输入且不见安全信道内容，隐私性与输入独立性成立。
  • 接收方被攻陷：\(\tau = b \oplus \beta\)，\(b\) 由诚实协助者的 \(\beta\) 保护。承诺隐藏性保证 \(c_{\beta\oplus1}\) 不泄露 \(p_{\beta\oplus1}\)。\(e_{b\oplus1}\) 为一次一密加密，隐私性与正确性成立。
  • 发送方被攻陷：\(x_0 = e_0 \oplus p_\tau\)，\(x_1 = e_1 \oplus p_{\tau\oplus1}\)。发送方不获知 \(b\)，输入独立性与隐私性成立。接收方可由 \(e_b \oplus p_\beta\) 恢复 \(x_b\)，正确性成立。

情况 1：协助者 \(P_h\) 被攻陷

  • Game 0（真实世界）：\(P_h\) 可发送不一致消息，\(P_s\) 仅能通过哈希承诺验证消息一致性，匹配则继续协议。
  • Game 1（理想实验）：只要 \(P_h\) 发送的消息实际不一致，就强制 \(P_s\) 中止协议。

两个游戏仅在 \(P_h\) 找到哈希碰撞（不同输入对应同一哈希）时才会分叉；基于哈希函数的抗碰撞性，这种情况发生的概率可忽略，因此真实世界与理想世界视图计算不可区分，敌手无法在不被发现的情况下作弊或窃取隐私，协议满足恶意安全。

情况 2：接收方 \(P_r\) 被攻陷

  • Game 0（真实世界）：协议按真实流程执行，\(P_r\) 仅能拿到自己选择的掩码 \(p_\beta\)，未选消息的哈希承诺 \(c_{\beta\oplus1}=H(p_{\beta\oplus1},r_{\beta\oplus1})\) 和一次一密密文 \(e_{b\oplus1}=x_{b\oplus1}\oplus p_{\beta\oplus1}\) 无法被破解。
  • Game 1：修改哈希承诺，用随机值 \(p\) 代替真实掩码 \(p_{\beta\oplus1}\) 生成 \(c_{\beta\oplus1}\)。
  • Game 2（理想世界）：直接将未选消息的密文 \(e_{b\oplus1}\) 设为随机元素。

基于哈希的输入隐藏性，\(P_r\) 无法区分真实承诺与随机承诺，Game 0 与 Game 1 不可区分；基于一次一密的完美隐私性，真实密文与随机值不可区分，Game 1 与 Game 2 等价。因此真实世界与理想世界不可区分，被攻陷的 \(P_r\) 无法获取额外信息，协议满足发送方隐私安全。

情况 3：发送方 \(P_s\) 被攻陷

  • 真实世界：接收方发送 \(\tau = b \oplus \beta\)，其中 \(\beta\) 是协助者生成的均匀随机比特，最终输出为 \(x_b\)。
  • 理想世界：模拟器直接生成均匀随机的 \(\tau\)（不依赖 \(b\)），输出同样为 \(x_b\)。

由于 \(b \oplus \beta\) 与均匀随机比特同分布，真实与理想世界的视图完美不可区分，被攻陷的发送方无法从 \(\tau\) 中获取 \(b\) 的任何信息，接收方隐私得到保护。

4 OT 扩展：IKNP 协议

为什么需要 OT 扩展？

基于 DDH 的 OT 虽然简单，但每次都要做公钥运算，代价高，实际协议常常需要成千上万次 OT*。IKNP 的核心目标是用少量贵的基 OT，扩展出大量便宜的 OT。

IKNP 协议示意图

协议流程详解
  1. 接收方准备矩阵：选 \(T\xleftarrow{}_{\$}\{0,1\}^{m\times k}\)，定义 \(T'=T\oplus (r\cdot \mathbf{1}^T)\)，即第 \(j\) 行满足 \(t'_j=t_j\oplus (r_j\cdot \mathbf{1}^T)\)
  2. 发送方选择列选择位：\(s\xleftarrow{}_{\$}\{0,1\}^k\)
  3. 执行 \(k\) 个基 OT：每一列 \(i\in[k]\)，接收方提供一对消息 \((t_i,\ r\oplus t_i)\)，发送方以选择位 \(s_i\) 通过基 OT 得到 \(q_i\)，汇总得到矩阵 \(Q\)，其行向量满足 \(q_j = (r_j\cdot s)\oplus t_j\)
  4. 发送方掩码真实消息：对每个 \(j\in[m]\)，发送 \(y_{j,0}=x_{j,0}\oplus H(j,q_j)\)，\(y_{j,1}=x_{j,1}\oplus H(j,q_j\oplus s)\)
  5. 接收方恢复所选消息：\(z_j = y_{j,r_j}\oplus H(j,t_j)\)， 因为 \(q_j \oplus (r_j\cdot s)=t_j\)

半诚实安全直觉

  • 发送方隐私：对每个 \(j\)，接收方只知道 \(q_j\) 与 \(q_j\oplus s\) 中的一个，另一个在 \(\{0,1\}^k\) 上均匀随机，在随机谕示机模型下，接收方若想命中那一项，对应查询成功概率可忽略。
  • 接收方隐私：发送方只看到矩阵 \(Q\)，由于 \(T\) 是均匀随机的，且\(Q=(r\cdot s)\oplus T\)，所以 \(Q\) 对发送方来说仍是均匀随机矩阵，不泄露 \(r\)。

恶意情形下的安全性直观说明

  • 恶意发送方： 任意发送的 \((y_{j,0},y_{j,1})\) 都等价于某组输入 \((x_{j,0},x_{j,1})\) 的重新编码，因此从理想世界角度通常可解释为输入替换，安全。
  • 恶意接收方：若接收方恶意伪造 \(T,T'\)，使某一列只在很少位置不同，就可能通过哈希查询恢复 \(s_i\)，进而同时得到 \(q_j\) 与 \(q_j\oplus s\)，最终解出两条消息

因此恶意安全 OT 扩展必须额外加入一致性检查、committing OT / cut-and-choose OT 或专门的恶意安全编译。

情况 1：发送方 \(P_s\) 被攻陷（恶意）

  • 矩阵 \(Q\) 满足 \(q_j = (r_j \cdot s) \oplus t_j\)，协议正确性成立
  • 由 \(\mathcal{S}\) 提取 \((x_{j,0}, x_{j,1})\) 的方式，\(P_r\) 在理想/真实世界输出一致
  • 敌手视角下 \(Q\) 在理想/真实世界均为均匀随机矩阵
情况 2：接收方 \(P_r\) 被攻陷（半诚实）

\(P_r\) 被攻陷时（半诚实），区分优势不超过 \((t + 1) \cdot 2^{-k}\):

  • 当 \(s \neq 0\) 时，理想/真实世界的 \((y_{j,0}, y_{j,1})\) 分布相同
  • 坏事件 \(B\): \(s = 0\) 或敌手请求 \(H(j, t_j \oplus s)\)
  • 由于 \(t_j \oplus s\) 在 \(2^k\) 空间均匀，\(\Pr[B] \leq (t + 1) \cdot 2^{-k}\)

本章小结

  • 理论边界：两方信息论安全 OT 不存在
  • 计算型构造：可用 DDH 构造简单高效的半诚实 OT
  • 恶意安全：可引入辅助方，或使用更强的编译技术防止接收方作弊
  • 工程关键：IKNP 用少量基 OT 扩展出大量廉价 OT，是现代 MPC 的核心基础设施
1. 为什么说 OT 是两方安全计算的完备原语？

因为一旦有了 OT，就能构造 AND、布尔电路求值、GMW、Yao 等通用两方计算协议。

2. IKNP 为什么通常写在随机谕示机模型下？

因为其安全性分析要依赖哈希查询“命中隐藏点”的概率可忽略，这在随机谕示机下最自然。

3. 基础 IKNP 为什么对恶意发送方看起来反而没那么危险？

因为发送方随便发什么密文对，往往都能等价解释为它提交了另一组输入；而恶意接收方则可能真的突破“只能拿一条消息”的约束。