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（1-out-of-2 OT）¶

2. 1 真实协议流程¶

设 $\mathbb{G}$ 为阶为 $q$ 的循环群，生成元为 $g$，发送方消息 $x_0,x_1\in\mathbb{G}$，接收方选择位 $b\in\{0,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)$ 发送给发送方
发送方加密两条消息：取 $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)$ 发送给接收方
接收方恢复所选消息：$x_b = c_b / v^{\text{sk}}$

安全直觉

接收方隐私：发送方看到的 $\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}$

问答题【24-25春夏期末】

What is the security definition of the oblivious transfer protocol? Given a secure (1,2)-OT, (i.e. 1-out-of-2 oblivious transfer protocol,) could you construct a (1,4)-OT protocol? And show why the proposed a (1,4)-OT protocol is secure.

参考答案（LLM生成）

理想功能 $\mathcal{F}_{\text{OT}}$：发送方输入 $(m_0,m_1)$，接收方输入选择比特 $b$，接收方获得 $m_b$，发送方无输出，半诚实安全要求：

接收方隐私：发送方无法区分 $b=0$ 和 $b=1$。
发送方隐私：接收方除 $m_b$ 外，得不到 $m_{1-b}$ 的任何信息。

下面构造 1-out-of-4 OT.发送方有消息 $\{m_{00},m_{01},m_{10},m_{11}\}$，接收方有选择 $(s_1,s_2)\in\{0,1\}^2$。

发送方随机生成四个对称密钥 $k_1^0,k_1^1,k_2^0,k_2^1$，计算双重密文：
$c_{ab} = E_{k_1^a}(E_{k_2^b}(m_{ab}))$，将全部四个密文发给接收方。
执行两次 (1,2)-OT：
- OT₁：发送方输入 $(k_1^0,k_1^1)$，接收方输入 $s_1$，得到 $k_1^{s_1}$
- OT₂：发送方输入 $(k_2^0,k_2^1)$，接收方输入 $s_2$，得到 $k_2^{s_2}$
接收方用 $k_1^{s_1},k_2^{s_2}$ 解密 $c_{s_1 s_2}$ 得 $m_{s_1 s_2}$，其余密文无法解密。

接收方隐私：发送方仅参与两次独立的 (1,2)-OT，由基础 OT 的接收方隐私保证其无法区分选择比特，从而不知 $(s_1,s_2)$。
发送方隐私：对于 $(a,b)\neq(s_1,s_2)$，接收方至少缺失一个密钥，由加密的 IND-CPA 安全性和 OT 保证缺失密钥不可知，故其他三个消息信息论隐藏。模拟器可用随机密文和仅目标位置的正确消息构建不可区分的视图。

2. 2 理想功能模型¶

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

解释

发送方提交输入，理想功能同步模拟器：发送方 $P_s$ 向理想功能 $\mathcal{F}_{OT}$ 发送 $(\text{INPUT}, \text{sid}, x_0, x_1)$，$\mathcal{F}_{OT}$ 收到输入后，向模拟器 $\mathcal{S}$ 发送通知 $(\text{INPUT}, \text{sid}, P_s)$，告知发送方已完成输入提交。
接收方提交选择，理想功能同步模拟器：接收方 $P_r$ 向理想功能 $\mathcal{F}_{OT}$ 发送 $(\text{INPUT}, \text{sid}, b)$，$\mathcal{F}_{OT}$ 收到选择后，向模拟器 $\mathcal{S}$ 发送通知 $(\text{INPUT}, \text{sid}, P_r)$，告知接收方已完成选择提交。
模拟器触发输出，接收方获得目标消息：模拟器 $\mathcal{S}$ 向 $\mathcal{F}_{OT}$ 发送输出指令 $(\text{OUTPUT}, \text{sid}, P_r)$，$\mathcal{F}_{OT}$ 校验会话标识匹配后，向接收方 $P_r$ 返回 $(\text{OUTPUT}, \text{sid}, x_b)$，接收方得到选中的消息 $x_b$。

情况 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$ 被攻陷

真实协议中，$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¶

3. 1 真实协议流程¶

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

解释

辅助方准备随机掩码：辅助方随机选取掩码 $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})$，使发送方能验证承诺而接收方仅知一半掩码。
接收方绑定自己的选择：接收方用 $\tau=b\oplus \beta$ 掩盖真实选择 $b$，计算己侧承诺 $c_\beta=H(p_\beta,r_\beta)$，将 $(\tau,c_0,c_1)$ 发送给发送方，从而绑定选择且不泄露 $b$。
发送方验证并发送掩码密文：检查 $c_0=H(p_0,r_0)$，$c_1=H(p_1,r_1)$，若通过，则以 $\tau$ 为偏移加密得到 $e_0 = x_0 \oplus p_\tau$，$e_1 = x_1 \oplus p_{\tau\oplus 1}$，发送给接收方。
接收方恢复目标消息：$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$，正确性成立。

3. 2 理想功能模型¶

解释

辅助方触发协议准备：辅助方 $P_h$ 向理想功能 $\mathcal{F}_{OT}$ 发送准备消息 $(\text{PREPARE}, \text{sid})$ 启动协议实例，$\mathcal{F}_{OT}$ 同步向模拟器 $\mathcal{S}$ 发送准备事件通知 $(\text{PREPARE}, \text{sid}, P_h)$。
发送方提交消息输入：发送方 $P_s$ 向 $\mathcal{F}_{OT}$ 提交两条待传输消息输入 $(\text{INPUT}, \text{sid}, x_0, x_1)$，$\mathcal{F}_{OT}$ 同步向模拟器 $\mathcal{S}$ 发送发送方输入事件 $(\text{INPUT}, \text{sid}, P_s)$。
接收方提交选择输入：接收方 $P_r$ 向 $\mathcal{F}_{OT}$ 提交选择比特输入 $(\text{INPUT}, \text{sid}, b)$，$\mathcal{F}_{OT}$ 同步向模拟器 $\mathcal{S}$ 发送接收方输入事件 $(\text{INPUT}, \text{sid}, P_r)$。
模拟器控制协议走向：模拟器 $\mathcal{S}$ 可向 $\mathcal{F}_{OT}$ 发送 $(\text{ABORT}, \text{sid})$ 终止协议，也可发送输出指令 $(\text{OUTPUT}, \text{sid}, P_r)$，触发理想功能向接收方交付结果。
接收方获得目标消息：$\mathcal{F}_{OT}$ 收到输出指令后，向接收方 $P_r$ 返回 $(\text{OUTPUT}, \text{sid}, x_b)$，接收方得到自己选中的消息 $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。

4. 1 真实协议流程¶

解释

接收方原始随机矩阵 $T$：接收方 $P_r$ 生成的完全随机 $0-1$ 矩阵，每一行 $t_j$ 是随机 $k$ 比特串，每一列记为 $t^i$。
接收方翻转后的矩阵 $T'$：由接收方的选择向量 $r=(r_1,\dots,r_m)$ 对 $T$ 按行翻转得到 $T' = T \oplus (r \cdot \mathbf{1}^T)$。对第 $j$ 行有 $t'_j = t_j \oplus r_j \cdot 1^k$，对第 $i$ 列有 $t'^i = t^i \oplus r$。
发送方通过基础 OT 得到的矩阵 $Q$：共 $k$ 列，对应 $k$ 次 1-out-of-2 基础 OT。接收方 $P_r$ 第 $i$ 次 OT 输入 $t^i$ 和 $t'^i$，发送方 $P_s$ 第 $i$ 次 OT 输入选择位 $s_i$（全局秘密向量 $s$ 的第 $i$ 位），输出得到 $q^i$（矩阵 $Q$ 的第 $i$ 列）。
满足关系式 $q^i = \begin{cases} t^i & s_i=0 \\ t'^i = t^i \oplus r & s_i=1 \end{cases}$，即第 $i$ 列有 $q^i = t^i \oplus (s_i \cdot r)$，第 $j$ 行有 $q_j = t_j \oplus (r_j \cdot s)$。

4. 2 理想功能模型¶

解释

接收方准备矩阵：选 $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)$
发送方选择列选择位：$s\xleftarrow{}_{\$}\{0,1\}^k$
执行 $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$
发送方掩码真实消息：对每个 $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)$
接收方恢复所选消息：$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}$

5 思考题¶

1. 为什么说 OT 是两方安全计算的完备原语？

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

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

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

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

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