第 5 章茫然传输和茫然传输扩展

学习目标

掌握本章核心定义、协议步骤与安全结论。
能复述协议输入/输出与理想功能，并指出图中关键步骤。
理解半诚实/恶意设定下的证明思路（模拟器与归约）。

上一章，我们详细介绍了安全多方计算的形式化模型——通用可组合框架。接下来，我们将在通用可组合框架下给出协议的安全性定义和安全证明。我们首先从茫然传输协议(Oblivious Transfer, OT)开始。OT本身是一个非常重要的密码学原语，在过去几十年里受到了研究者的深入研究，至今仍是一个重要的研究方向。我们首先介绍关于OT的一些已知结论。然后，我们介绍两个基础的OT构造，它们分别可以抵御半诚实敌手和恶意敌手；这两个构造比较简单，读者可以通过它们的安全性证明来进一步理解通用可组合安全框架。最后，我们介绍IKNP提出的茫然传输扩展协议 [IKNP, 2003]。

关于OT的一些结论

我们先简单回顾一下OT的定义（见「茫然传输」一节）。OT有两个参与方：发送方和接收方，发送方的输入是 $x_0, x_1$，接收方的输入是 $b$. 协议结束后，接收方得到 $x_b$，发送方和接收方都不能得到任何额外信息。

本节介绍一些关于OT的已知结论。我们首先证明：不存在信息论安全的两方OT协议。接着，我们将介绍OT的一些变种，并给出一些相关的结论。

不存在信息论安全的两方OT协议

我们分两步证明这个结论：首先，我们通过两方OT协议构造一个两方AND协议；然后，我们证明不存在信息论安全的两方AND协议。因此，不存在信息论安全的两方OT协议。

定理

不存在信息论安全的两方OT协议。

不存在信息论安全的两方OT协议 · 证明

首先，我们通过两方OT协议构造一个两方AND协议。

在两方OT协议中，发送方 $P_s$ 的输入为 $x_0, x_1$，接收方 $P_r$ 的输入为 $b \in \{0, 1\} $. 接收方 $P_r$ 得到的输出为 $x_b$，发送方不得到输出。注意到，当 $x_0, x_1 \in \{0, 1\} $ 时，有 $x_b = ( 1 \oplus b ) x_0 \oplus b x_1 $.

在两方AND协议中，设两个参与方的输入分别为 $a$ 和 $b$，他们希望计算 $a \wedge b $，而不泄漏其他信息。我们可以用如下的方式构造两方AND协议：两个参与方执行OT协议，令发送方 $P_s$ 的输入为 $( x_0 = 0, x_1 = a ) $，接收方的输入为 $b$. 根据 $x_b = ( 1 \oplus b ) x_0 \oplus b x_1 $，协议的输出为 $ab$. 当发送方被攻陷时，根据OT协议中接收方的隐私性，发送方不知道 $b$ 的值。当接收方被攻陷时，如果接收方的输入 $b=0 $，根据OT协议中发送方的隐私性，那么接收方不知道 $x_1$ 即 $a$ 的值。因此这是一个安全的两方AND协议。

引理 1

下面，我们证明不存在信息论安全的两方AND协议。

不存在信息论安全的两方AND协议。

引理 1 · 证明

我们先证明较为简单的情形，即不存在两方AND协议满足完美隐私性和完美正确性。然后我们可以把证明过程推广到隐私性和正确性有可忽略的失败概率的情形。

假设存在两方AND协议 $\Pi_\mathsf{2AND}$ 满足完美隐私性和完美正确性。设 $\Pi_\mathsf{2AND}$ 有 $s$ 轮通信，其中 $s \geq 1$. 将参与方计作 $P_0$ 和 $P_1$，他们的输入计作 $b_0$ 和 $b_1$. $\Pi_\mathsf{2AND}$ 需要满足完美的正确性，即协议总是输出 $y = b_0 \wedge b_1 $；$\Pi_\mathsf{2AND}$ 还需要满足完美的隐私性，也就是说，当 $P_i$ 被攻陷时，他的视图 $\text{view}_{i}$ 只依赖于 $b_i$ 和 $y$，而与另一方的输入无关。

我们用 $\mathcal{T}(c, d)$ 表示当 $b_0 = c, b_1 = d$ 时，$\Pi_\mathsf{2AND}$ 执行过程中可能产生的消息集合。即，如果存在随机数 $r_0, r_1 \in \{0, 1\}^*$，使得消息集合 $\mathcal{T} = ( m_{01}, m_{11}, …, m_{0s}, m_{1s}, y )$ 是参与方 $P_0$ 和 $P_1$ 以 $c$ 和 $d$ 以及随机数 $r_0$ 和 $r_1$ 作为输入执行 $\Pi_\mathsf{2AND}$ 所产生的消息集合，那么 $\mathcal{T} \in \mathcal{T}(c, d)$. 接下来我们证明三个断言。

断言

$\mathcal{T}(0, 0) = \mathcal{T}(0, 1) $.

引理 1 · 证明

由于我们考虑的是信息论安全，敌手具有无限的计算能力，他可以遍历随机空间来计算 $\mathcal{T}(0, 0)$ 和 $\mathcal{T}(0, 1)$. 假设存在 $\mathcal{T}'$ 满足 $\mathcal{T}' \in \mathcal{T}(0, 0) $ 且 $\mathcal{T}' \notin \mathcal{T}(0, 1) $. 那么当两个参与方以 $b_0 = 0, b_1 = 0 $ 执行协议时，$P_0$ 就有可能看到消息集合 $\mathcal{T}'$. 如果 $P_0$ 是被攻陷的，他就可以判断 $\mathcal{T}'$ 不是 $\mathcal{T}(0, 1)$ 中的元素，从而断定 $b_1 = 0$. 这就违背了 $\Pi_\mathsf{2AND}$ 的完美隐私性。故该断言成立。

断言

$\mathcal{T}(0, 0) = \mathcal{T}(1, 0) $.

引理 1 · 证明

这与断言 5.1完全同理。

断言

$\mathcal{T}(0, 1) \cap \mathcal{T}(1, 0) \subset \mathcal{T}(1, 1) $.

引理 1 · 证明

这个断言的证明基于 $\mathcal{T}$ 的定义。令 $\mathcal{T} = ( m_{01}, m_{11}, …, m_{0s}, m_{1s}, y )$. 如果 $\mathcal{T} \in \mathcal{T}(0, 1) \cap \mathcal{T}(1, 0)$，首先，根据 $\mathcal{T} \in \mathcal{T}(0, 1)$ 可知，存在随机数 $r_1$ 使得 $P_1$ 以 $b_1 = 1$ 和 $r_1$ 作为输入运行协议且收到的消息是 $\{m_{0i}\}_{i \in [s]}$ 时，会得到 $\mathcal{T}$；又由 $\mathcal{T} \in \mathcal{T}(1, 0)$ 可知，存在随机数 $r_0$ 使得 $P_0$ 以 $b_0 = 1$ 和 $r_0$ 作为输入运行协议且收到的消息是 $\{m_{1i}\}_{i \in [s]}$ 时，会得到 $\mathcal{T}$. 那么，当 $P_0$ 和 $P_1$ 以 $b_0 = 1, b_1 = 1$ 以及 $r_0, r_1$ 作为输入运行协议时，也会得到 $\mathcal{T}$，即 $\mathcal{T} \in \mathcal{T}(1, 1)$. 因此 $\mathcal{T}(0, 1) \cap \mathcal{T}(1, 0) \subset \mathcal{T}(1, 1) $.

引理 1 · 证明

基于前两个断言，我们有

\mathcal{T}(0, 1) \cap \mathcal{T}(1, 0) = \mathcal{T}(0, 0)

而根据断言 5.3，$\mathcal{T}(0, 1) \cap \mathcal{T}(1, 0) \subset \mathcal{T}(1, 1)$，因此 $\mathcal{T}(0, 0) \subset \mathcal{T}(1, 1)$. 而当输入为 $b_0 = 0, b_1 = 0$ 时，输出 $y = 0$，当输入为 $b_0 = 1, b_1 = 1$ 时，输出 $y = 1$. 因此 $\mathcal{T}(0, 0)$ 不可能包含于 $\mathcal{T}(1, 1)$. 矛盾。故不存在两方AND协议满足完美隐私性和完美正确性。

如果 $\Pi_\mathsf{2AND}$ 的隐私性和正确性有可忽略的失败概率，那么在断言 5.1和断言 5.2中，$\mathcal{T}(0, 0)$ 和 $\mathcal{T}(0, 1)$ 以及 $\mathcal{T}(0, 0)$ 和 $\mathcal{T}(1, 0)$ 都有可忽略的统计距离。断言 5.3仍然成立。依然可以推出矛盾。因此，不存在信息论安全的两方AND协议。

不存在信息论安全的两方OT协议 · 证明

综上，我们可以通过两方OT协议构造两方AND协议。而引理 1证明了不存在信息论安全的两方AND协议。因此，定理得证。

注意，这里我们证明的是，不存在对发送方和接收方均满足信息论安全的OT协议。但是，构造一个当接收方被攻陷时满足信息论安全，当发送方被攻陷时满足计算安全的OT协议，或者当发送方被攻陷时满足信息论安全，当接收方被攻陷时满足计算安全的OT协议，都是已经被实现的。

OT变种

本节，我们介绍几个有名的OT变种，以及它们之间的关系。

Rabin OT [Rabin, 1981]. 在Rabin的OT变种中，发送方 $P_s$ 只有一个隐私输入 $x$, 接收方有1/2概率接收到 $x$，有1/2概率接收到 $\bot$. 发送方不知道接收方的输出。

随机OT(random OT)。 在随机OT中，发送方和接收方都没有任何输入。协议会给发送方输出 $(x_0, x_1)$ 并给接收方输出 $(b, x_b)$，其中 $x_0, x_1$ 是随机均匀选取的消息，$b$ 是随机均匀选取的比特。

OT变种的等价性。值得注意的是，OT（「茫然传输」一节所定义的常见形式）、Rabin OT和随机OT都是等价的。我们下面简要说明这一点。

我们首先说明OT和随机OT是等价的，即通过OT可以构造随机OT，通过随机OT也可以构造OT. 前者非常简单。发送方均匀随机选取 $x_0, x_1$，接收方均匀随机选取 $b \leftarrow_{\$} \{0, 1\} $，然后以它们作为输入执行OT协议，接收方得到 $x_b$. 最后，发送方的输出是 $(x_0, x_1)$，接收方的输出是 $(b, x_b)$. 容易证明这是一个安全的随机OT协议。

通过随机OT构造OT的方法如下。发送方和接收方首先执行随机OT协议，发送方获得 $(x_0, x_1)$，接收方获得 $(b, x_b)$. 我们将发送方在OT协议中的输入记作 $(m_0, m_1)$，接收方在OT协议中的输入记作 $c$. 现在接收方需要获得 $m_c$. 这里的 $x_0, x_1$ 都是均匀随机的，可以作为一次一密的密钥，我们的思路是用 $x_b$ 加密 $m_c$，用 $x_{b \oplus 1}$ 加密 $m_{c \oplus 1}$ 发送给接收方。

然而发送方 $P_s$ 不知道 $b$ 与 $c$ 的关系：如果 $b = c$，那么应该用 $x_0$ 加密 $m_0$，用 $x_1$ 加密 $m_1$；如果 $b = c \oplus 1$，那么应该用 $x_1$ 加密 $m_0$，用 $x_0$ 加密 $m_1$. 为此，接收方 $P_r$ 发送 $d = b \oplus c $ 给 $P_s$（告知 $b$ 与 $c$ 是否相等）。根据 $d$ 的值，$P_s$ 接下来计算 $(y_0, y_1) = (x_d \oplus m_0, x_{d \oplus 1} \oplus m_1)$ 并发送给 $P_r$. 最后，接收方 $P_r$ 输出 $m'_c = y_c \oplus x_b$.

我们简单分析一下这个协议的正确性和隐私性。首先，正确性：$m'_c = y_c \oplus x_b = ( x_{d \oplus c} \oplus m_c ) \oplus x_b = ( x_b \oplus m_c ) \oplus x_b = m_c$. 而 $x_{b \oplus 1}$ 作为一次一密的密钥加密了 $m_{c \oplus 1}$，保护了发送方的隐私；$b$ 作为一次一密的密钥加密了选择比特 $c$，保护了接收方的隐私。

所以，我们通过随机OT构造了OT协议。故随机OT和OT是等价的。

关于Rabin OT，Crépeau [Crepeau, 1987]证明了它与OT也是等价的。因此，OT、Rabin OT、随机OT都是等价的。

1-out-of-$N$-OT. 在这种OT中，$P_s$ 有 $N$ 个隐私输入 $x_0, …, x_{N-1}$，$P_r$ 有一个隐私索引 $b \in \{ 0, …, N-1 \}$. $P_r$ 的输出是 $x_b$. 发送方 $P_s$ 不知道 $b$，接收方 $P_r$ 不知道 $x_b$ 以外的其他隐私输入。

$k$-out-of-$N$-OT. 在这种OT中，$P_s$ 有 $N$ 个隐私输入 $x_0, …, x_{N-1}$，$P_r$ 有 $k$ 个隐私索引 $i_0, …, i_{k-1} \in \{ 0, …, N-1 \} $. $P_r$ 的输出是 $x_{i_0}, …, x_{i_k}$. 发送方 $P_s$ 不知道隐私索引 $i_0, …, i_{k-1}$，接收方 $P_r$ 不知道 $x_{i_0}, …, x_{i_k}$ 以外的其他隐私输入。

Naor和Pinkas [Nao & Pin, 1999]证明了：可以通过1-out-of-2-OT构造1-out-of-$N$-OT和$k$-out-of-$N$-OT. 例如GMW协议中（见「GMW协议」一节），需要调用1-out-of-4-OT来计算乘法门。有了这个结论，我们就可以聚焦于构造1-out-of-2-OT了。

一些其他结论

本节，我们列出关于OT的一些其他重要结论以及相关文章，可以作为读者拓展阅读的材料。

OT是完备的，即基于OT可以安全地计算任何函数 [Kilian, 1988; Ish et al., 2008]。
OT是对称的，即基于OT可以构造 $\text{OT}'$，其中 $\text{OT}'$ 的发送方是OT的接收方，$\text{OT}'$ 的接收方是OT的发送方 [Wol & Wul, 2006]。
不能以黑盒的方式基于公钥加密(Public Key Encryption, PKE)构造OT [GKMRV, 2000].
OT可以基于增强陷门置换(enhanced trapdoor permutation) [Even et al., 1985; Gol et al., 1987]、DDH假设、RSA假设 [Even et al., 1985]、格密码 [Pei et al., 2008]构造。

基于DDH假设的OT协议（半诚实安全）

本小节，我们介绍一个在半诚实敌手模型下，基于DDH假设的OT协议。（注：本节参考了书 [Boneh, 2023]，Section 23.5.7.）

协议描述

这个协议的基本思想很简单。接收方 $P_r$ 生成两个公钥 $\mathsf{pk}_{0}, \mathsf{pk}_{1}$，且 $P_r$ 知道 $\mathsf{pk}_{b}$ 对应的私钥，不知道 $\mathsf{pk}_{1-b}$ 对应的私钥（具体的做法是，$P_r$ 生成一个公私钥对 $\langle \mathsf{pk}_{b}, \mathsf{sk}_{b} \rangle$，然后在群上随机选择一个元素作为 $\mathsf{pk}_{1-b}$）。然后，接收方 $P_r$ 将 $\mathsf{pk}_{0}, \mathsf{pk}_{1}$ 发给发送方 $P_s$. 随后 $P_s$ 用 $\mathsf{pk}_{0}, \mathsf{pk}_{1}$ 通过ElGamal加密算法分别加密 $x_0, x_1$，并将密文发送给 $P_r$. 因为接收方只知道一个私钥，因此只能解密一个密文。而发送方只能看到两个公钥，无法知道接收方拥有的是哪一个私钥。

该协议的完整描述如图 5.1所示。

基于DDH假设的OT协议

设 $\mathbb{G}$ 是一个阶为 $q$ 的群（$q$ 为素数），生成元是 $g$. 设发送方 $P_s$ 的输入 $x_0, x_1$ 是群 $\mathbb{G}$ 中的元素（或者可以编码成群 $\mathbb{G}$ 中的元素）。

输入：发送方 $P_s$ 的输入是 $x_0, x_1 \in \mathbb{G}$；接收方 $P_r$ 的输入是$b \in \{0, 1\}$.
协议：
- 接收方 $P_r$ 计算
  $\mathsf{sk} \leftarrow_{\$} \mathbb{Z}_q, \mathsf{pk}_{b} = g^\mathsf{sk}, \mathsf{pk}_{1-b} \leftarrow_{\$} \mathbb{G}$ 并将 $(\mathsf{pk}_{0}, \mathsf{pk}_{1})$ 发给 $P_s$.
- 当从 $P_r$ 收到 $(\mathsf{pk}_{0}, \mathsf{pk}_{1})$ 后，发送方 $P_s$ 计算
  $r \leftarrow_{\$} \mathbb{Z}_q, v = g^r, c_0 = x_0 \cdot \mathsf{pk}_{0}^r, c_1 = x_1 \cdot \mathsf{pk}_{1}^r$ 并将 $(v, c_0, c_1)$ 发给 $P_r$.
- 当从 $P_s$ 收到 $(v, c_0, c_1)$ 后，接收方 $P_r$ 输出 $c_b / v^\mathsf{sk}$.

安全性的直观说明

安全性的直观说明 · 公式

我们首先在半诚实敌手模型下给出一个安全性的直观说明。

正确性。在半诚实敌手模型下，参与方均遵循协议。我们有

\frac{c_b}{v^\mathsf{sk}} = \frac{c_b}{(g^r)^\mathsf{sk}} = \frac{c_b}{(g^\mathsf{sk})^r} = \frac{c_b}{\mathsf{pk}_{b}^r} = \frac{x_b \cdot \mathsf{pk}_{b}^r}{\mathsf{pk}_{b}^r} = x_b

因此，接收方 $P_r$ 的输出是 $x_b$.

隐私性。首先，我们说明 $P_s$ 无法得到关于 $P_r$ 的输入 $b$ 的任何信息。在协议中，$(\mathsf{pk}_{0}, \mathsf{pk}_{1})$ 是两个随机的群元素，它的分布与 $b$ 的值无关。因此，$P_s$ 无法得到关于 $P_r$ 的输入 $b$ 的任何信息。

然后，我们说明 $P_r$ 可以得到 $x_b$，但是不能得到关于 $x_{1-b}$ 的任何信息。这需要假设DDH问题在群 $\mathbb{G}$ 上是困难的。在协议中，$P_r$ 知道的信息包括自己的输入 $b$，私钥 $\mathsf{sk}$，公钥 $\mathsf{pk}_{0}, \mathsf{pk}_{1}$，协议的输出 $x_b$，以及从 $P_s$ 收到的 $(v, c_0, c_1)$. 其中，$v$ 是随机群元素，不会泄漏任何关于 $x_{1-b}$ 的信息；$c_b = x_b v^\mathsf{sk}$ 可以由 $P_r$ 的已知信息推算出来，也不会泄漏 $x_{1-b}$. 因此我们只需要论证 $c_{1-b}$ 没有泄漏信息。基于DDH假设，三元组 $(g^r, \mathsf{pk}_{1-b}, \mathsf{pk}_{1-b}^r)$ 与 $(g^r, \mathsf{pk}_{1-b}, e)$ 是计算上不可区分的，其中 $e \in \mathbb{G}$ 是一个随机群元素。由于 $c_{1-b} = x_{1-b} \mathsf{pk}_{1-b}^r $，区分 $(v=g^r, \mathsf{pk}_{1-b}, c_{1-b})$ 和 $(v=g^r, \mathsf{pk}_{1-b}, e)$ 等价于区分 $(v=g^r, \mathsf{pk}_{1-b}, c_{1-b}/x_{1-b})$ 和 $(v=g^r, \mathsf{pk}_{1-b}, e/x_{1-b})$. 前者是DDH三元组，而 $e/x_{1-b}$ 仍是随机群元素，所以在计算上它们是不可区分的。因此，$P_r$ 不能得到关于 $x_{1-b}$ 的任何信息。

安全性证明

现在，我们给出形式化的安全性证明。我们先给出理想功能 $\mathcal{F}_{\mathsf{OT}}$ 的定义，如图 5.5所示。

理想功能 $\mathcal{F}_{\mathsf{OT}}$

该理想功能 $\mathcal{F}_{\mathsf{OT}}$ 与发送方 $P_s$，接收方 $P_r$ 以及敌手 $\mathcal{S}$ 交互。

当收到来自发送方 $P_s$ 的消息 $(\operatorname{Input}, \mathsf{sid}, x_0, x_1)$ 时，该理想功能 $\mathcal{F}_{\mathsf{OT}}$ 做如下操作：
- 记录 $(\operatorname{Input}, \mathsf{sid}, x_0, x_1)$，并发送 $(\operatorname{Input}, \mathsf{sid}, P_s)$ 给敌手 $\mathcal{S}$.
当收到来自接收方 $P_r$ 的消息 $(\operatorname{Input}, \mathsf{sid}, b)$ 时，该理想功能 $\mathcal{F}_{\mathsf{OT}}$做如下操作：
- 记录 $(\operatorname{Input}, \mathsf{sid}, b)$，并发送 $(\operatorname{Input},\mathsf{sid},P_r)$ 给敌手 $\mathcal{S}$.
当收到来自 $\mathcal{S}$ 的 $(\operatorname{Output}, \mathsf{sid}, P_r)$ 时，如果 $(\operatorname{Input}, \mathsf{sid}, x_0, x_1)$ 和 $(\operatorname{Input}, \mathsf{sid}, b)$ 均已经被记录，该理想功能 $\mathcal{F}_{\mathsf{OT}}$ 做如下操作：
- 发送 $(\operatorname{Output}, \mathsf{sid}, x_b)$ 给接收方 $P_r$.

茫然传输的理想功能$\mathcal{F}_{\mathsf{OT}}$

定理

假设DDH问题在群 $\mathbb{G}$ 上是困难的。图 5.1展示的协议 $\Pi$ 对于静态半诚实敌手UC-安全实现了理想功能 $\mathcal{F}_{\mathsf{OT}}$（图 5.5）。

安全性证明

要证明该定理，我们需要构造模拟器 $\mathcal{S}$，使得对所有PPT的环境 $\mathcal{Z}$，都有

\operatorname{exec}_{\Pi,\mathcal{A},\mathcal{Z}} \approx \operatorname{exec}_{\mathcal{F}_{\mathsf{OT}},\mathcal{S},\mathcal{Z}}

其中 $\mathcal{A}$ 是平凡敌手，只执行 $\mathcal{Z}$ 的指令（基于定理 4.1平凡敌手的完备性）。

模拟器 $\mathcal{S}$. 首先，模拟器 $\mathcal{S}$ 在内部运行 $\mathcal{A}$，转发 $\mathcal{Z}$ 与 $\mathcal{A}$ 之间的消息。根据参与方被攻陷的不同情况，模拟器 $\mathcal{S}$ 的行为会对应地有所不同。在两方均被攻陷或两方均诚实的情况下，$\mathcal{S}$ 就不需要做什么了。因此，我们重点考虑一个参与方被攻陷的情况。

情况1：发送方 $P_s$ 被攻陷。在这种情况下，$\mathcal{S}$ 的工作方式如下。

当 $\mathcal{Z}$ 发送输入 $(\operatorname{Input}, \mathsf{sid}, x_0, x_1)$ 给 $P_s$ 时，它会被直接转发给 $\mathcal{F}_{\mathsf{OT}}$，同时，$\mathcal{S}$ 也会收到 $(\operatorname{Input}, \mathsf{sid}, x_0, x_1)$. 此后，$\mathcal{S}$ 模拟 $P_s$ 遵循协议运行，并将 $P_s$ 的内部状态报告给 $\mathcal{Z}$.
在某个时刻，$\mathcal{Z}$ 会给 $P_r$ 发送输入$(\operatorname{Input}, \mathsf{sid}, b)$，这会让真实世界的 $P_s$ 收到消息 $(\mathsf{pk}_{0}, \mathsf{pk}_{1})$. 在理想世界中，此时 $\mathcal{S}$ 会从 $\mathcal{F}_{\mathsf{OT}}$ 收到 $(\operatorname{Input}, \mathsf{sid}, P_r)$ （告知 $\mathcal{S}$ “$P_r$已提供输入”）。$\mathcal{S}$ 并不能知道 $P_r$ 的输入 $b$，但是 $\mathcal{S}$ 需要“编造”出消息 $(\mathsf{pk}_{0}, \mathsf{pk}_{1})$. 此时，$\mathcal{S}$ 随机选取 $\mathsf{pk}_{0} \leftarrow_{\$} \mathbb{G}, \mathsf{pk}_{1} \leftarrow_{\$} \mathbb{G}$，并把 $(\mathsf{pk}_{0}, \mathsf{pk}_{1})$ 报告给 $\mathcal{Z}$.
当 $P_s$ 向 $P_r$ 发送 $(v, c_0, c_1)$ 后，$\mathcal{S}$ 向 $\mathcal{F}_{\mathsf{OT}}$ 发送 $(\operatorname{Output}, \mathsf{sid}, P_r)$.

以上就是 $P_s$ 被攻陷时 $\mathcal{S}$ 的工作方式。下面，我们需要论证理想世界和真实世界的不可区分性。

不可区分性。我们观察到，理想世界与真实世界唯一的不同，就是 $(\mathsf{pk}_{0}, \mathsf{pk}_{1})$ 的生成方式。然而，无论 $P_r$ 的输入 $b$ 是0还是1，$(\mathsf{pk}_{0}, \mathsf{pk}_{1})$ 都是两个群上的随机元素。因此，理想世界和真实世界是完美不可区分的。

情况2：接收方 $P_r$ 被攻陷。在这种情况下，$\mathcal{S}$ 的工作方式如下。

当 $\mathcal{Z}$ 发送输入 $(\operatorname{Input}, \mathsf{sid}, b)$ 给 $P_r$ 时，它会被直接转发给 $\mathcal{F}_{\mathsf{OT}}$，同时，$\mathcal{S}$ 也将收到 $(\operatorname{Input}, \mathsf{sid}, b)$. 此后，$\mathcal{S}$ 模拟 $P_r$ 遵循协议运行，即计算 $\mathsf{sk} \leftarrow_{\$} \mathbb{Z}_q, \; \mathsf{pk}_{b} = g^\mathsf{sk}, \; \mathsf{pk}_{1-b} \leftarrow_{\$} \mathbb{G} $，将 $(\mathsf{pk}_{0}, \mathsf{pk}_{1})$ 发给 $P_s$. $\mathcal{S}$ 将 $P_r$ 的内部状态报告给 $\mathcal{Z}$.
在某个时刻，$\mathcal{Z}$ 会给 $P_s$ 发送输入 $(\operatorname{Input}, \mathsf{sid}, x_0, x_1)$，如果 $P_r$ 已经发送了第一条消息 $(\mathsf{pk}_{0}, \mathsf{pk}_{1})$ 给 $P_s$ ，那么这会让真实世界的 $P_r$ 收到消息 $(v, c_0, c_1)$. 在理想世界中，这对应于 $\mathcal{S}$ 从 $\mathcal{F}_{\mathsf{OT}}$ 收到 $(\operatorname{Input}, \mathsf{sid}, P_s)$ （告知 $\mathcal{S}$ “$P_s$已提供输入”）。$\mathcal{S}$ 并不能知道 $P_s$ 的输入 $x_0, x_1$，但是 $\mathcal{S}$ 需要“编造”出消息 $(v, c_0, c_1)$. 此时，$\mathcal{S}$ 发送 $(\operatorname{Output}, \mathsf{sid}, P_r)$ 给 $\mathcal{F}_{\mathsf{OT}}$ 使被攻陷的接收方 $P_r$ 得到其在理想世界中的输出$x_b$. 然后，$\mathcal{S}$ 计算 $v \leftarrow_{\$} \mathbb{G}, c_b = x_b v^\mathsf{sk}, c_{1-b} \leftarrow_{\$} \mathbb{G}$，并将 $(v, c_0, c_1)$ 报告给 $\mathcal{Z}$.

以上就是 $P_r$ 被攻陷时 $\mathcal{S}$ 的工作方式。下面，我们需要论证理想世界和真实世界的不可区分性。

不可区分性。观察到，理想世界与真实世界唯一的不同，就是 $(v, c_0, c_1)$ 的生成方式。然而，不论在理想世界还是真实世界中，$v$ 都是随机群元素，$c_b$ 都被 $P_r$ 已知的信息决定。在真实世界中，$c_{1-b} = x_{1-b} \cdot \mathsf{pk}_{1-b}^r$，在理想世界中，$c_{1-b}$ 是随机群元素，正如我们在第安全性的直观说明小节中的论证，基于DDH假设，它们计算上是不可区分的。因此，理想世界和真实世界是计算上不可区分的。

思考题：之前我们提到，不能以黑盒的方式基于公钥加密(PKE)构造 OT. 但是这里我们似乎只使用了ElGamal公钥加密方案就构造了OT协议。这是否矛盾了呢？

答案：上面的构造中暗含了一个假设：接收方可以在不知道私钥的情况下选取一个公钥。而公钥加密并不保证这个假设成立。因此不矛盾。

三方OT协议（恶意安全）

上一节介绍的协议是对半诚实敌手安全的OT协议，这个协议在面对恶意敌手时显然是不安全的。如果接收方 $P_r$ 是恶意的，他可以生成两个公私钥对，然后将这两个公钥发给 $P_s$. 这样，$P_r$ 就可以解密两个密文，打破发送方的隐私性。

一个抵抗该攻击的简单的想法是：在协议的第一步，发送方 $P_s$ 随机选取 $d \leftarrow_{\$} \mathbb{G} $ 并发送给 $P_r$，接收方的公钥生成方式改为 $\mathsf{sk} \leftarrow_{\$} \mathbb{Z}_q, \; \mathsf{pk}_{b} = g^\mathsf{sk}, \; \mathsf{pk}_{1-b} \leftarrow d / \mathsf{pk}_{b} $. 当 $P_s$ 收到 $\mathsf{pk}_{0}, \mathsf{pk}_{1}$ 后，检查条件 $\mathsf{pk}_{0} \cdot \mathsf{pk}_{1} = d $ 是否满足，若不满足则中止协议。这样，$P_r$ 不可能同时知道 $\mathsf{pk}_{0}$ 和 $\mathsf{pk}_{1}$ 对应的私钥，因为这等价于求解 $d$ 的离散对数。

然而，仅仅作上述修改还不足以构造出一个恶意安全的OT协议：“敌手不知道公钥对应的私钥”并不能证明“敌手不知道关于消息的任何信息”。本节，我们将给出一个三方OT协议，并证明：在只有一个参与方被攻陷的情况下，该协议是恶意安全的。（注：本节参考了书 [Boneh, 2023]，Section 23.5.8.）

协议描述

在该协议中，发送方 $P_s$ 的输入是 $x_0, x_1$，接收方 $P_r$ 的输入是 $b \in \{ 0, 1 \}$，还有一个额外的“协助者” $P_h$，他没有任何输入。协议结束时，接收方 $P_r$ 获得 $x_b$，而发送方 $P_s$ 和“协助者” $P_h$ 不获得输出。

我们使用抗碰撞哈希函数 $H: \mathcal{M} \times \mathcal{R} \rightarrow \mathcal{C}$ 作为非交互承诺方案。其中，$\mathcal{M}$ 是消息空间，$\mathcal{R}$ 是（足够大的）随机元素的空间，$\mathcal{C}$ 是输出的空间（也就是承诺的空间）。我们假设哈希函数 $H$ 具有输入隐藏性，其定义如下：对于任意选定的 $x_0, x_1 \in \mathcal{M}$ 和随机选择的 $r \leftarrow_{\$} \mathcal{R}$，分布 $\{ H(x_0, r) \}$ 和 $\{ H(x_1, r) \}$ 是计算上不可区分的（不可区分性的定义见第基本术语和符号节）。基于抗碰撞性和输入隐藏性，可以证明承诺方案 $\mathsf{Com}(x) = H(x, r), \; r \leftarrow_{\$} \mathcal{R}$ 具有隐藏性和绑定性（承诺的定义见第承诺节）。

该协议的完整描述如图 5.2所示。

三方OT协议

准备步骤：抗碰撞哈希函数 $H: \mathcal{M} \times \mathcal{R} \rightarrow \mathcal{C}$.
输入：$P_s$ 的输入是 $x_0, x_1 \in \mathcal{M}$；$P_r$ 的输入是 $b \in \{0, 1\}$.
协议：
- $P_h$ 计算
  $p_0, p_1 \leftarrow_{\$} \mathcal{M}, r_0, r_1 \leftarrow_{\$} \mathcal{R}, \beta \leftarrow_{\$} \{0, 1\}, c_{\beta \oplus 1} = H(p_{\beta \oplus 1}, r_{\beta \oplus 1})$ 并把 $(\beta, p_\beta, r_\beta, c_{\beta \oplus 1})$ 发给 $P_r$，把 $(p_0, r_0, p_1, r_1)$ 发给 $P_s$.
- 当 $P_r$ 从 $P_h$ 处收到 $(\beta, p_\beta, r_\beta, c_{\beta \oplus 1})$ 后，计算
  $\tau = b \oplus \beta, c_\beta = H(p_\beta, r_\beta)$ 并把 $(\tau, c_0, c_1)$ 发给 $P_s$.
- 当 $P_s$ 从 $P_h$ 处收到 $(p_0, r_0, p_1, r_1)$，从 $P_r$ 处收到 $(\tau, c_0, c_1)$ 后，首先检查
  $c_0 \stackrel{?}{=} H(p_0, r_0), c_1 \stackrel{?}{=} H(p_1, r_1)$ 如果检查不通过，则中止协议（同时通知 $P_r$ 中止协议）。
  否则，$P_s$ 计算
  $e_0 = x_0 \oplus p_\tau, e_1 = x_1 \oplus p_{\tau \oplus 1}$ 并把 $(e_0, e_1)$ 发给 $P_r$.
- 当 $P_r$ 从 $P_s$ 处收到 $(e_0, e_1)$ 后，输出 $e_b \oplus p_\beta$.

协议的直观描述。直观上来说，该协议的思想如下：

协助者生成两个均匀随机的消息 $p_0, p_1$，作为“一次一密”的密钥来加密发送方的消息。然后，协助者生成对 $p_0, p_1$ 的承诺，将两个承诺的打开都发给发送方；对于接收方，协助者向他发送 $p_\beta$ 的打开和 $p_{\beta \oplus 1}$ 的承诺，这里 $\beta$ 是协助者均匀随机选择的比特。
接着，接收方将 $\beta$ 作为“一次一密”的密钥加密他的选择比特 $b$ 得到 $\tau$，然后将 $\tau$ 和对 $p_0$ 和 $p_1$ 的两个承诺发给发送方。
发送方首先检查：从协助者处收到的承诺的打开与从接收方处收到的承诺是否一致。这一步防止了恶意的协助者给发送方和接收方发送不一致的信息。如果检查通过，发送方用 $p_\tau$ 加密 $x_0$ 得到 $e_0$，用 $p_{\tau \oplus 1}$ 加密 $x_1$ 得到 $e_1$，并将 $e_0, e_1$ 发给接收方。
最后，接收方用 $p_\beta$ 解密 $e_b$ 得到 $x_b$.

安全性的直观说明

在给出形式化的安全性证明之前，我们先从直观上分析该协议的正确性、隐私性和输入独立性。输入独立性指的是：所有参与方的输入必须是独立于其他参与方的输入的（半诚实情况下敌手不能更改协议输入，故无需分析输入独立性）。协议假设最多只有一个参与方被攻陷，因此我们分别对“协助者被攻陷”、“接收方被攻陷”和“发送方被攻陷”三种情况进行分析。

协助者被攻陷：由于哈希函数 $H$ 的抗碰撞性，当被攻陷的协助者给发送方和接收方发送不一致的消息时，协议会中止。而如果协助者发送了一致的消息，接收方就能得到正确的消息 $x_b$. 因此正确性成立。由于发送方和接收方之间的通信是通过安全信道进行的，协助者无法得到任何关于 $x_0, x_1$ 和 $b$ 的信息。因此隐私性成立。因为协助者没有输入，输入独立性平凡地成立。

接收方被攻陷：当被攻陷的接收方将 $\tau$ 发给发送方时，它的选择比特 $b$ 就由关系 $b = \tau \oplus \beta$ 所决定了，其中 $\beta$ 是诚实的协助者选择的比特。此时，接收方没有收到任何与发送方的输入 $x_0, x_1$ 有关的消息，因此输入独立性成立。接下来分析当接收方从发送方处收到 $e_0, e_1$ 时的情况。此时，接收方可以由 $e_b$ 解密得到 $x_b$. 根据承诺方案的隐藏性，接收方不能从 $c_{\beta \oplus 1}$ 中得到任何关于 $p_{\beta \oplus 1}$ 的信息。而 $p_{\beta \oplus 1}$ 作为“一次一密”的密钥加密了 $x_{b \oplus 1}$ 得到 $e_{b \oplus 1}$，因此 $e_{b \oplus 1}$ 没有泄漏任何关于 $x_{b \oplus 1}$ 的信息，隐私性成立。最后，由于诚实的协助者和发送方没有输出，正确性平凡地成立。

发送方被攻陷：当发送方将 $e_0, e_1$ 发给接收方时，他的输入 $x_0, x_1$ 由关系 $x_0 = e_0 \oplus p_\tau$ 和 $x_1 = e_1 \oplus p_{\tau \oplus 1}$ 决定。此时，接收方的输入比特 $b$ 被 $\beta$ 完美地保护了，因此发送方不知道关于 $b$ 的任何信息，输入独立性成立。在之后的协议执行过程中，发送方没有获得任何与 $b$ 有关的消息，因此隐私性也成立。最后，接收方可以正确地解密 $e_b$ 得到 $x_b$，因此正确性成立。

安全性证明

由于这里加入了一个角色——协助者，并且考虑的是恶意安全，我们需要对理想功能 $\mathcal{F}_{\mathsf{OT}}$ 稍作修改：当协助者执行协议时，发送一个通知消息给 $\mathcal{S}$；$\mathcal{S}$ 可以向 $\mathcal{F}_{\mathsf{OT}}$ 发送一个中止指令，使其结束运行，不产生输出。修改后的理想功能 $\mathcal{F}_{\mathsf{OT}}$ 如图 5.6所示。

理想功能 $\mathcal{F}_{\mathsf{OT}}$

该理想功能 $\mathcal{F}_{\mathsf{OT}}$ 与发送方 $P_s$，接收方 $P_r$，协助者 $P_h$ 以及敌手 $\mathcal{S}$ 交互。

当收到来自协助者 $P_h$ 的消息 $(\operatorname{Prepare}, \mathsf{sid})$ 时，该理想功能 $\mathcal{F}_{\mathsf{OT}}$ 做如下操作：
- 记录 $(\operatorname{Prepare}, \mathsf{sid})$，并发送 $(\operatorname{Prepare}, \mathsf{sid}, P_h)$ 给敌手 $\mathcal{S}$.
当收到来自发送方 $P_s$ 的消息 $(\operatorname{Input}, \mathsf{sid}, x_0, x_1)$ 时，该理想功能 $\mathcal{F}_{\mathsf{OT}}$ 做如下操作：
- 记录 $(\operatorname{Input}, \mathsf{sid}, x_0, x_1)$，并发送 $(\operatorname{Input}, \mathsf{sid}, P_s)$ 给敌手 $\mathcal{S}$.
当收到来自接收方 $P_r$ 的消息 $(\operatorname{Input}, \mathsf{sid}, b)$ 时，该理想功能 $\mathcal{F}_{\mathsf{OT}}$ 做如下操作：
- 记录 $(\operatorname{Input}, \mathsf{sid}, b)$，并发送 $(\operatorname{Input}, \mathsf{sid}, P_r)$ 给敌手 $\mathcal{S}$.
当收到来自 $\mathcal{S}$ 的 $(\operatorname{Abort}, \mathsf{sid})$ 时，中止。
当收到来自 $\mathcal{S}$ 的 $(\operatorname{Output}, \mathsf{sid}, P_r)$ 时，如果 $(\operatorname{Prepare}, \mathsf{sid})$、$(\operatorname{Input}, \mathsf{sid}, x_0, x_1)$ 和 $(\operatorname{Input}, \mathsf{sid}, b)$ 均已经被记录，该理想功能 $\mathcal{F}_{\mathsf{OT}}$ 做如下操作：
- 发送 $(\operatorname{Output}, \mathsf{sid}, x_b)$ 给接收方 $P_r$.

茫然传输的理想功能$\mathcal{F}_{\mathsf{OT}}$

定理

假设参与方之间存在点对点安全信道；假设哈希函数 $H$ 是抗碰撞的，且满足上文所述的输入隐藏性；假设最多只有一个参与方被攻陷。图 5.2展示的协议 $\Pi$ 对于静态恶意敌手UC-安全实现了理想功能 $\mathcal{F}_{\mathsf{OT}}$（图 5.6）。

真实世界。首先，让我们回顾一下真实世界的细节。环境 $\mathcal{Z}$ 在最开始决定哪些参与方是被攻陷的，之后，它向诚实方提供输入并从诚实方接收输出。（在这个协议中，只有 $P_s$ 和 $P_r$ 可以接收输入，只有 $P_r$ 可以产生输出。）通信网络由 $\mathcal{Z}$ 控制（通过平凡敌手 $\mathcal{A}$ 向 $\mathcal{C}$-控制线发送指令），因此它可以决定何时将协议消息发送给诚实方。注意，我们可以认为被攻陷方并不真实存在，它们发送给诚实方的任何消息实际上是由 $\mathcal{Z}$ 发送的（通过 $\mathcal{A}$ 间接地实现），而任何诚实方发送给被攻陷方的消息实际上是发送给 $\mathcal{Z}$ 的（通过 $\mathcal{A}$ 间接地实现）。尽管如此，为了描述的明确性，在下面的证明中我们仍然会说“从被攻陷方发送给诚实方的消息”和“从诚实方发送给被攻陷方的消息”。

理想世界。理想世界中，有一个模拟器 $\mathcal{S}$. 与真实世界一样，$\mathcal{Z}$ 在最开始决定哪些方是被攻陷的，之后，它向诚实方提供输入并从诚实方接收输出。诚实方的输入直接转发给理想功能，被攻陷方的输入由 $\mathcal{S}$ 提供给理想功能。当理想功能收到了所有参与方的输入之后，$\mathcal{S}$ 可以选择何时让理想功能生成输出：诚实方的输出直接转发给 $\mathcal{Z}$，而被攻陷方的输出则交给 $\mathcal{S}$.

证明的总体方法。为了证明协议 $\Pi$ 的安全性，我们需要设计 $\mathcal{S}$，使得所有PPT的良好的 $\mathcal{Z}$ 都无法区分真实世界和理想世界。直观地说，这意味着 $\mathcal{S}$ 在理想世界中与 $\mathcal{Z}$ 的交互应该能使 $\mathcal{Z}$ “认为”它仍然在真实世界中。为此，$\mathcal{S}$ 需要与 $\mathcal{Z}$ 交换消息（通过 $\mathcal{S}$-控制线），这些消息看起来就像真实世界中的通信网络上的消息。因此，即使在理想世界中，我们也可以说“从被攻陷方发送给诚实方的消息”（其内容实际上是由 $\mathcal{Z}$ 发送给 $\mathcal{S}$ 的）以及“从诚实方发送给被攻陷方的消息”（其内容实际上是由 $\mathcal{S}$ 生成并发送给 $\mathcal{Z}$ 的）。对于“诚实方之间发送的消息”，其内容实际上从未生成：$\mathcal{S}$ 只需要与 $\mathcal{Z}$ 交换消息，所以 $\mathcal{S}$ 无需模拟诚实方之间的消息。

每当真实世界中的诚实方向真实世界中的被攻陷方发送协议消息时，$\mathcal{S}$ 必须以某种方式“编造”出一个协议消息发送给该被攻陷方（实际上发送给 $\mathcal{Z}$）。此外，根据真实世界的被攻陷方发送给真实世界的诚实方的消息，$\mathcal{S}$ 必须从这些消息中提取出被攻陷方的有效输入，并将其提交给理想功能。注意，$\mathcal{S}$ 需要在不知道诚实方的输入输出的情况下完成这些模拟（但它最终可以知道被攻陷方的输出）。并且，这些模拟必须使得 $\mathcal{Z}$ 无法高效地区分理想世界和真实世界（ $\mathcal{Z}$ 知道所有诚实方的输入和输出）。

基于上述讨论我们可以发现，恶意敌手模型和半诚实敌手模型的一个重要技术区别是：在恶意敌手模型中，模拟器必须从被攻陷方的协议消息中“提取”有效输入；而在半诚实模型中，模拟器可以直接得到这些输入。

下面，我们给出形式化的证明。

安全性证明

根据平凡敌手的完备性，我们需要构造模拟器 $\mathcal{S}$，使得对所有PPT的环境 $\mathcal{Z}$，都有

\operatorname{exec}_{\Pi,\mathcal{A},\mathcal{Z}} \approx \operatorname{exec}_{\mathcal{F}_{\mathsf{OT}},\mathcal{S},\mathcal{Z}}

其中 $\mathcal{A}$ 是平凡敌手，只执行 $\mathcal{Z}$ 的指令。

模拟器 $\mathcal{S}$. 首先，模拟器 $\mathcal{S}$ 在内部运行 $\mathcal{A}$，转发 $\mathcal{Z}$ 与 $\mathcal{A}$ 之间的消息。根据参与方被攻陷的不同情况，模拟器 $\mathcal{S}$ 的行为会对应地有所不同。在三方均诚实的情况下，$\mathcal{S}$ 就不需要做什么了。因此，我们重点考虑一个参与方被攻陷的情况。

情况1：协助者 $P_h$ 被攻陷。在这种情况下，$\mathcal{S}$ 的工作方式如下。

当 $\mathcal{S}$ 获得了 $P_h$ 发给 $P_r$ 的消息 $(\beta, p_\beta, r_\beta, c_{\beta \oplus 1})$ 以及 $P_h$ 发给 $P_s$ 的消息 $(p_0, r_0, p_1, r_1)$ （ $\mathcal{S}$ 可以收到所有“被攻陷方发给诚实方的消息”）时，$\mathcal{S}$ 在理想世界中代表 $P_h$ 将 $(\operatorname{Prepare}, \mathsf{sid})$ 发给 $\mathcal{F}_{\mathsf{OT}}$.
在某个时刻，$\mathcal{Z}$ 会给 $P_r$ 发送输入 $(\operatorname{Input}, \mathsf{sid}, b)$，这会让 $\mathcal{S}$ 从 $\mathcal{F}_{\mathsf{OT}}$ 收到 $(\operatorname{Input}, \mathsf{sid}, P_r)$（告知$\mathcal{S}$“ $P_r$ 已提供输入”）。此时，$\mathcal{S}$ 已经获得了 $P_h$ 发给 $P_r$ 的消息 $(\beta, p_\beta, r_\beta, c_{\beta \oplus 1})$ 以及 $P_h$ 发给 $P_s$ 的消息 $(p_0, r_0, p_1, r_1)$ 。$\mathcal{S}$ 检查这两条消息是一致的：即，发给 $P_r$ 的 $p_\beta, r_\beta$ 与发给 $P_s$ 的值是一致的，以及 $c_{\beta \oplus 1}$ 确实是发给 $P_s$ 的 $p_{\beta \oplus 1}, r_{\beta \oplus 1}$ 的哈希。如果检查不通过，$\mathcal{S}$ 将发送 $(\operatorname{Abort}, \mathsf{sid})$ 给 $\mathcal{F}_{\mathsf{OT}}$ （模拟 $P_s$ 中止协议），也就是 $\mathcal{S}$ 将不会让 $\mathcal{F}_{\mathsf{OT}}$ 为 $P_r$ 生成输出。
如果检查通过，$\mathcal{S}$ 将模拟 $P_s$ 不中止协议。在之后的某个时刻，$\mathcal{Z}$ 会给 $P_s$ 发送输入 $(\operatorname{Input}, \mathsf{sid}, x_0, x_1)$，这会让 $\mathcal{S}$ 从 $\mathcal{F}_{\mathsf{OT}}$ 收到 $(\operatorname{Input}, \mathsf{sid}, P_s)$ （告知 $\mathcal{S}$ “ $P_s$ 已提供输入”）。此时，$\mathcal{S}$ 发送 $(\operatorname{Output}, \mathsf{sid}, P_r)$ 给 $\mathcal{F}_{\mathsf{OT}}$，让 $\mathcal{F}_{\mathsf{OT}}$ 为 $P_r$ 生成输出。

以上就是 $P_h$ 被攻陷时 $\mathcal{S}$ 的工作方式。下面，我们需要论证理想世界和真实世界的不可区分性。

不可区分性。令Game 0是真实世界的执行，我们定义Game 1如下：Game 1与Game 0相同，除了当 $P_h$ 向 $P_s$ 和 $P_r$ 发送了不一致的信息时，$P_s$ 会中止协议。（在真实世界中，此时 $P_s$ 不可能中止协议，因为他不知道 $P_h$ 发给 $P_r$ 的消息；但我们这里可以这样定义Game 1，它本质上是一个思想实验）。可以观察到，除非 $P_s$ 和 $P_r$ 收到了不同的 $(p_\beta, r_\beta)$ 但有相同的哈希，Game 0与Game 1将完全相同。因此，环境 $\mathcal{Z}$ 能区分Game 0和Game 1的概率就是找到哈希碰撞的概率，而基于抗碰撞哈希的假设，这个概率是可忽略的。

最后，我们观察到Game 1的执行与理想世界的执行是完全一样的。因此，理想世界和真实世界不可区分。

情况2：接收方 $P_r$ 被攻陷。在这种情况下，$\mathcal{S}$ 的工作方式如下。

在某个时刻，$\mathcal{Z}$ 会给 $P_h$ 发送 $(\operatorname{Prepare}, \mathsf{sid})$ ，这条消息会让真实世界中 $P_r$ 从 $P_h$ 处收到 $(\beta, p_\beta, r_\beta, c_{\beta \oplus 1})$. 此时，$\mathcal{S}$ 从 $\mathcal{F}_{\mathsf{OT}}$ 收到 $(\operatorname{Prepare}, \mathsf{sid}, P_h)$，$\mathcal{S}$ 需要“编造”出一条模拟的消息发给 $P_r$. $\mathcal{S}$ 均匀随机选取
$\beta \leftarrow_{\$} \{0, 1\}, p_0, p_1 \leftarrow_{\$} \mathcal{M}, r_0, r_1 \leftarrow_{\$} \mathcal{R}$
并计算
$\[c_0 = H(p_0, r_0), c_1 = H(p_1, r_1)\]$
然后将 $($\beta$, p_$\beta$, r_$\beta$, c_{$\beta$ $\oplus$ 1})$发给 $P_r$，正如真实世界中 $P_h$ 所做的那样。
之后的某个时刻，当 $\mathcal{S}$ 获得 $P_r$ 发给 $P_s$ 的消息 $(\tau, \hat{c}_0, \hat{c}_1)$时，首先，$\mathcal{S}$ 检查 $\hat{c}_0 \stackrel{?}{=} c_0$ 和 $\hat{c}_1 \stackrel{?}{=} c_1$，这里的 $c_0, c_1$ 是 $\mathcal{S}$ 在上一步通过式（式 5.1）所计算出来的。

如果检查不通过，$\mathcal{S}$ 将发送 $(\operatorname{Abort}, \mathsf{sid})$ 给 $\mathcal{F}_{\mathsf{OT}}$（模拟 $P_s$ 中止协议）。

否则，$\mathcal{S}$ 通过计算 $b = \tau \oplus \beta$ 来“提取” $P_r$ 的输入 $b$，并在理想世界中代表 $P_r$ 将 $(\operatorname{Input}, \mathsf{sid}, b)$ 发给 $\mathcal{F}_{\mathsf{OT}}$.
假设协议没有中止，之后的某个时刻，$$\mathcal{Z}$$会给 $P_s$发送输入 $($\operatorname{Input}$, $\mathsf{sid}$, x_0, x_1)$，这条消息会让真实世界的 $P_r$从 $P_s$处收到 $(e_0, e_1)$.

在理想世界中，$\mathcal{S}$ 会从 $\mathcal{F}_{\mathsf{OT}}$ 收到 $(\operatorname{Input}, \mathsf{sid}, P_s)$（告知 $\mathcal{S}$ “ $P_s$ 已提供输入”）。$\mathcal{S}$ 需要“编造”一条消息发给 $P_r$. 注意，在这个时候 $\mathcal{F}_{\mathsf{OT}}$ 已经收到了 $P_s$ 的输入 $x_0, x_1$，而 $\mathcal{S}$ 并不知道这个输入。但是，$\mathcal{S}$ 可以发送 $(\operatorname{Output}, \mathsf{sid}, P_r)$ 给 $\mathcal{F}_{\mathsf{OT}}$ 使其生成 $P_r$ 的输出 $(\operatorname{Output}, \mathsf{sid}, x_b)$，这条消息会直接发给 $\mathcal{S}$. 当得到 $x_b$ 后，$\mathcal{S}$ 计算
$e_b = x_b \oplus p_\beta, e_{b \oplus 1} \leftarrow_{\$} \mathcal{M}$
并将 $(e_0, e_1)$ 作为模拟的消息发给 $P_r$.

以上就是 $P_r$ 被攻陷时 $\mathcal{S}$ 的工作方式。下面，我们来论证理想世界和真实世界的不可区分性。

不可区分性。令Game 0是真实世界的执行。那么，$P_s$ 和 $P_h$ 将通过式（式 5.1）的方式计算 $c_0, c_1$，并且

$P_h$ 会将 $c_{\beta \oplus 1}$ 发给 $P_r$；
当 $P_s$ 从 $P_r$ 处收到 $(\tau, \hat{c}_0, \hat{c}_1)$ 时，他会检查 $\hat{c}_0 = c_0$ 和 $\hat{c}_1 = c_1$.

现在，定义Game 1如下：Game 1与Game 0相同，除了 $P_s$ 和 $P_h$ 计算 $c_0, c_1$ 的方式变为

c_\beta = H(p_\beta, r_\beta), c_{\beta \oplus 1} = H(p, r_{\beta \oplus 1})

其中 $p \leftarrow_{\$} \mathcal{M}$ 是均匀随机选择的消息。也就是说，对于 $c_{\beta \oplus 1}$，将 $p_{\beta \oplus 1}$ 替换为随机的 $p$. 注意，在这个游戏(Game)中，$P_s$ 仍然按照协议规定使用 $p_0, p_1$ 来计算 $e_0, e_1$，即 $e_0 \leftarrow x_0 \oplus p_\tau, \; e_1 \leftarrow x_1 \oplus p_{\tau \oplus 1}$（在真实世界中，$P_s$ 不可能这么做，因为他不知道 $\beta$；但我们这里可以这样定义Game 1，它是一个思想实验）。于是，我们可以发现 $\mathcal{Z}$ 能区分Game 0和Game 1的概率就是区分 $H(p_{\beta \oplus 1}, r_{\beta \oplus 1})$ 和 $H(p, r_{\beta \oplus 1})$ 的概率。基于哈希函数的输入隐藏性假设，这个概率是可忽略的。

注意到 $p_{\beta \oplus 1}$ 在Game 1中唯一用到的地方就是作为“一次一密”的密钥加密 $x_{b \oplus 1}$ 得到 $e_{b \oplus 1}$，其中 $b = \tau \oplus \beta$. 因此，定义Game 2如下：Game 2与Game 1相同，除了 $P_s$ 在最后一步直接均匀随机选取

e_{b \oplus 1} \leftarrow_{\$} \mathcal{M}

作为最后一步发给 $P_r$ 的消息（在Game 1中 $e_{b \oplus 1} = x_{b \oplus 1} \oplus p_{\beta \oplus 1}$）。

由于在Game 1中将 $c_{\beta \oplus 1}$ 修改为了 $c_{\beta \oplus 1} \leftarrow H(p, r_{\beta \oplus 1})$，故 $P_r$ 不可能从 $c_{\beta \oplus 1}$ 中获得任何关于 $p_{\beta \oplus 1}$ 的信息。那么根据“一次一密”的完美隐私性，Game 1与Game 2对于 $\mathcal{Z}$ 完美不可区分。最后，Game 2与理想世界的执行是完全相同的。因此，理想世界和真实世界不可区分。

情况3：发送方 $P_s$ 被攻陷。在这种情况下，$\mathcal{S}$ 的工作方式如下。

在某个时刻，$\mathcal{Z}$ 会给 $P_h$ 发送 $(\operatorname{Prepare}, \mathsf{sid})$ ，这条消息会让真实世界中 $P_s$ 从 $P_h$ 处收到 $(p_0, r_0, p_1, r_1)$. 在理想世界中，这对应于 $\mathcal{S}$ 从 $\mathcal{F}_{\mathsf{OT}}$ 收到 $(\operatorname{Prepare}, \mathsf{sid}, P_h)$. $\mathcal{S}$ 选取
$p_0, p_1 \leftarrow_{\$} \mathcal{M}, r_0, r_1 \leftarrow_{\$} \mathcal{R}$
并将 $(p_0, r_0, p_1, r_1)$ 发给 $P_s$，正如真实世界中 $P_h$ 所做的那样。
之后的某个时刻，$\mathcal{Z}$ 会给 $P_r$ 发送输入 $(\operatorname{Input}, \mathsf{sid}, b)$，这条消息会让真实世界中的 $P_s$ 从 $P_r$ 处收到 $(\tau, c_0, c_1)$.

在理想世界中，$\mathcal{S}$ 会从 $\mathcal{F}_{\mathsf{OT}}$ 收到 $(\operatorname{Input}, \mathsf{sid}, P_r)$ (告知 $\mathcal{S}$ “ $P_r$ ”已提供输入)。此时，$\mathcal{S}$ 计算
$c_0 = H(p_0, r_0), c_1 = H(p_1, r_1), \tau \leftarrow_{\$} \{0, 1\}$
并模拟 $P_r$ 将 $(\tau, c_0, c_1)$ 发给 $P_s$. 也就是说，$\mathcal{S}$ 诚实地计算 $c_0, c_1$，但 $\tau$ 是随机选取的。
之后的某个时刻，当 $P_r$ 从 $P_s$ 处收到 $(e_0, e_1)$ 时，$\mathcal{S}$ 计算
$x_0 = e_0 \oplus p_\tau, x_1 = e_1 \oplus p_{\tau \oplus 1}$
来“提取” $P_s$ 的输入 $x_0, x_1$，并在理想世界中代表 $P_s$ 将 $(\operatorname{Input}, \mathsf{sid}, x_0, x_1)$ 发给 $\mathcal{F}_{\mathsf{OT}}$. 此时，$\mathcal{F}_{\mathsf{OT}}$ 获得了来自 $P_s$ 和 $P_r$ 的输入，于是 $\mathcal{S}$ 发送 $(\operatorname{Output}, \mathsf{sid}, P_r)$ 给 $\mathcal{F}_{\mathsf{OT}}$ 使其生成 $P_r$ 的输出，这个输出将直接转发给 $\mathcal{Z}$.

以上就是 $P_s$ 被攻陷时 $\mathcal{S}$ 的工作方式。下面，我们来论证理想世界和真实世界的不可区分性。

不可区分性。首先，根据 $x_0, x_1$ 的提取方式可知，在理想世界和真实世界中，$P_r$ 的输出都是 $x_b$. 然后，理想世界和真实世界唯一的不同，是 $\tau$ 的生成方式。在理想世界中，$\tau \leftarrow_{\$} \{0, 1\}$；在真实世界中，$\tau = b \oplus \beta$，而 $\beta \leftarrow_{\$} \{0, 1\}$ 是 $P_h$ 均匀随机选取的。因此，理想世界和真实世界中 $\tau$ 的分布完全相同，它们完美不可区分。

IKNP OT扩展协议

上面我们分别介绍了半诚实安全和恶意安全的OT协议，在一个MPC协议中，往往需要大量的OT协议。由于两方OT无法基于单向函数(one way function)实现 [Imp & Rud, 1988]，而必须使用开销较大的公钥密码部件，因此，通常的做法是，首先选用合适的基OT（base OT）协议（例如文献 [Pei et al., 2008; Cho & Orl, 2015; Hau & Los, 2017; BDDMNB]的协议），然后使用OT扩展技术高效地实现多个OT. 下面，我们将介绍Ishai, Kilian, Nissim和Petrank [IKNP, 2003]（IKNP）提出的OT扩展协议。

OT扩展的思想与混合加密(hybrid encryption)类似。当我们希望用公钥加密算法加密一条很长的消息时，直接对其加密是很低效的；然而，我们可以用公钥加密算法加密一个对称加密算法的密钥 $\mathsf{k}$，然后用对称加密算法使用密钥 $\mathsf{k}$ 加密消息。这样的方法只需黑盒使用对称加密，就可以大大扩展公钥加密的效率。类似地，在OT扩展中，我们希望：将参与双方少量的（$k$ 个）OT，通过高效的对称密码组件，扩展到大量的（$m$ 个）OT.

符号表示。 OT扩展的目标是实现 $m$ 个长度为 $\ell$ 比特的OT，记作 $\mathsf{OT}^m_\ell$，它实现了如图 5.7所示的理想功能：

$\mathsf{OT}^m_\ell$ 的理想功能 $\mathcal{F}_{\mathsf{OT}^m_\ell}$

输入： $P_s$ 的输入是 $m$ 对长度为 $\ell$ 比特的消息 $(x_{j, 0}, x_{j, 1}), 1 \leq j \leq m$. $P_r$ 的输入是 $m$ 个选择比特 $\boldsymbol{r} = (r_1, …, r_m)$.

输出： $P_r$ 输出 $x_{j, r_j}, 1 \leq j \leq m$. $P_s$ 没有输出。

$\mathsf{OT}^m_\ell$ 的理想功能 $\mathcal{F}_{\mathsf{OT}^m_\ell}$

参与双方 $P_s$ 和 $P_r$ 本身可以执行 $k$ 个OT ($k < m$)。我们不妨假设这 $k$ 个OT传输的是长度为 $m$ 的消息（注：如果OT传输的消息长度小于 $m$，可以采用如下方法。将需要发送的消息记为 $(x_0, x_1), \; |x_0| = |x_1| = m$. 首先以两条均匀随机的消息 $(k_0, k_1)$ 为输入调用OT，它们是伪随机数生成器（见「伪随机数生成器」一节）的种子（密钥），然后发送方将 $(PRG(k_0) \oplus x_0, PRG(k_1) \oplus x_1)$ 发给接收方，其中 $PRG$ 是伪随机数生成器。接收方拥有一个密钥，只能解密一条消息。换句话说，通过伪随机数生成器，OT是可以延展的。），即我们希望基于 $\mathsf{OT}^k_m$ 构造 $\mathsf{OT}^m_\ell$.

在下面的叙述中，我们将用大写字母表示矩阵，用加粗的小写字母表示向量。对于矩阵 $\boldsymbol{M}$，我们用 $\boldsymbol{m}_{j}$ 表示它的第 $j$ 行，用 $\boldsymbol{m}^i$ 表示它的第 $i$ 列，用 $\boldsymbol{m}_{j}[i]$ 表示它第 $j$ 行的第 $i$ 个元素。符号 $b \cdot \boldsymbol{v}$ 表示比特 $b$ 与向量 $\boldsymbol{v}$ 相乘，当 $b=0$ 时，它的值为 $\boldsymbol{0}$；当 $b=1$ 时，它的值为 $\boldsymbol{v}$.

协议描述

IKNP协议是在随机谕示机模型下（见「哈希函数与随机谕示机」一节）实现的。协议的初始设置是一个随机谕示机 $H: [m] \times \{0, 1\}^k \rightarrow \{0, 1\}^\ell$. 协议的参与双方可以访问 $\mathsf{OT}^k_m$ 的理想功能 $\mathcal{F}_{\mathsf{OT}^k_m}$. $k$ 是基OT的数量，实际上是协议的一个安全参数。发送方 $P_s$ 的输入是 $m$ 对长度为 $\ell$ 比特的消息 $(x_{j, 0}, x_{j, 1}), 1 \leq j \leq m$. 接收方 $P_r$ 的输入是 $m$ 个选择比特 $\boldsymbol{r} = (r_1, …, r_m)$.

图 5.3展示了协议的运行过程。首先，接收方 $P_r$ 生成一个 $m \times k$ 比特的均匀随机矩阵 $\boldsymbol{T}$. $P_r$ 将矩阵 $\boldsymbol{T}$ 的每一列 $\boldsymbol{t}^i$ 与选择比特 $\boldsymbol{r}$ 进行异或计算，得到新矩阵 $\boldsymbol{T}'$，即 $\boldsymbol{T}'$ 的每一列 $\boldsymbol{t}'^i = \boldsymbol{r} \oplus \boldsymbol{t}^i$. 发送方 $P_s$ 均匀随机地生成一个长度为 $k$ 比特的向量 $\boldsymbol{s} \leftarrow_{\$} \{0, 1\}^k$.

接着，双方调用 $k$ 个OT的理想功能 $\mathcal{F}_{\mathsf{OT}^k_m}$. 注意，此时 $P_r$ 扮演了发送方的角色，它将 $\boldsymbol{T}$ 和 $\boldsymbol{T}'$ 的每一列作为 $\mathsf{OT}^k_m$ 的输入，即输入为 $(\boldsymbol{t}^i, \boldsymbol{t}'^i), 1 \leq i \leq k$. $P_s$ 扮演了接收方的角色，他的输入是上一步中生成的随机向量 $\boldsymbol{s}$. $P_s$ 将 $\mathcal{F}_{\mathsf{OT}^k_m}$ 的输出按列组成 $m \times k$ 比特的矩阵 $\boldsymbol{Q}$.

我们仔细观察矩阵 $\boldsymbol{Q}$. 因为OT是按列执行的，对于其每一列 $\boldsymbol{q}^i$，如果 $s_i = 0$，那么 $\boldsymbol{q}^i = \boldsymbol{t}^i$；如果 $s_i = 1$，那么 $\boldsymbol{q}^i = \boldsymbol{t}'^i = \boldsymbol{r} \oplus \boldsymbol{t}^i$，即 $\boldsymbol{q}^i = (s_i \cdot \boldsymbol{r}) \oplus \boldsymbol{t}^i$.

协议描述 · 公式

再观察矩阵 $\boldsymbol{Q}$ 的行。对于每一行 $\boldsymbol{q}_{j}$，如果这一行对应的 $r_j = 0$，那么 $\boldsymbol{t}_{j} = \boldsymbol{t}'_j$，此时无论 $\boldsymbol{s}$ 为何值，都有 $\boldsymbol{q}_{j} = \boldsymbol{t}_{j}$；如果 $r_j = 1$，那么有

\boldsymbol{q}_{j}[i] = \begin{cases} \boldsymbol{t}_{j}[i], & s_i = 0 \\ r_j \oplus \boldsymbol{t}_{j}[i] , & s_i = 1 \end{cases}

式（式 5.2）可以写作 $\boldsymbol{q}_{j} = (r_j \cdot \boldsymbol{s}) \oplus \boldsymbol{t}_{j}$. 当 $r_j = 0$ 时，$\boldsymbol{q}_{j} = \boldsymbol{t}_{j}$ 也满足 $\boldsymbol{q}_{j} = (r_j \cdot \boldsymbol{s}) \oplus \boldsymbol{t}_{j}$. 综上，矩阵 $\boldsymbol{Q}$ 的每一行满足 $\boldsymbol{q}_{j} = (r_j \cdot \boldsymbol{s}) \oplus \boldsymbol{t}_{j}, 1 \leq j \leq m$.

协议描述 · 插图

于是，我们得到了 $\boldsymbol{q}_{j}, \boldsymbol{t}_{j}, \boldsymbol{s}$ 和 $r_j$ 之间的关系。让我们纵览全局。原始OT按列执行，因而有 $\boldsymbol{q}^i = (s_i \cdot \boldsymbol{r}) \oplus \boldsymbol{t}^i$；而矩阵的行也满足 $\boldsymbol{q}_{j} = (r_j \cdot \boldsymbol{s}) \oplus \boldsymbol{t}_{j}, 1 \leq j \leq m$. 这充分体现了OT的对称性！原始OT的选择比特是 $s_i$，输入消息是 $\boldsymbol{t}^i$ 和 $\boldsymbol{r} \oplus \boldsymbol{t}^i$，输出消息是 $\boldsymbol{q}^i$；我们也可以把 $r_j$ 看成选择比特，那么输入消息就是 $\boldsymbol{q}_{j}$ 和 $\boldsymbol{q}_{j} \oplus \boldsymbol{s}$，输出消息是 $\boldsymbol{t}_{j}$（当 $r_j=0$ 时，$\boldsymbol{t}_{j} = \boldsymbol{q}_{j}$；当 $r_j=1$ 时，$\boldsymbol{t}_{j} = \boldsymbol{q}_{j} \oplus \boldsymbol{s}$），同时，发送方和接收方的身份也进行了对调。于是，我们便把 $k$ 个OT扩展为了 $m$ 个OT！

最后，发送方 $P_s$ 通过随机谕示机对消息进行加密，对 $1 \leq j \leq m$，其计算 $y_{j, 0} = x_{j, 0} \oplus H(j, \boldsymbol{q}_{j}), \; y_{j, 1} = x_{j, 1} \oplus H(j, \boldsymbol{q}_{j} \oplus \boldsymbol{s})$，并将 $(y_{j, 0}, y_{j, 1})$ 发给接收方 $P_r$. 接收方 $P_r$ 输出 $z_j = y_{j, r_j} \oplus H(j, \boldsymbol{t}_{j}), 1 \leq j \leq m$. 图 5.4是IKNP协议形式化的描述。

IKNP OT扩展协议

公共参数：安全参数 $k$.

设置：随机谕示机 $H: [m] \times \{0, 1\}^k \rightarrow \{0, 1\}^\ell$；$\mathsf{OT}^k_m$ 的理想功能 $\mathcal{F}_{\mathsf{OT}^k_m}$.

$P_s$ 的输入：$m$ 对长度为 $\ell$ 比特的消息 $(x_{j, 0}, x_{j, 1}), 1 \leq j \leq m$.

$P_r$ 的输入：$m$ 个选择比特 $\boldsymbol{r} = (r_1, …, r_m)$.

$P_s$ 选择均匀随机向量 $\boldsymbol{s} \leftarrow_{\$} \{0, 1\}^k$，$P_r$ 选择 $m \times k$ 的均匀随机矩阵 $\boldsymbol{T}$.
调用 $\mathcal{F}_{\mathsf{OT}^k_m}$，$P_s$ 作为接收方，其输入是 $\boldsymbol{s}$；$P_r$ 作为发送方，其输入是 $\boldsymbol{t}^i, \boldsymbol{r} \oplus \boldsymbol{t}^i, 1 \leq i \leq k$.
将 $P_s$ 收到的 $m \times k$ 矩阵记为 $\boldsymbol{Q}$（注意，矩阵 $\boldsymbol{Q}$ 满足 $\boldsymbol{q}^i = (s_i \cdot \boldsymbol{r}) \oplus \boldsymbol{t}^i, \boldsymbol{q}_{j} = (r_j \cdot \boldsymbol{s}) \oplus \boldsymbol{t}_{j}$）。对 $1 \leq j \leq m$，$P_s$ 计算 $y_{j, 0} = x_{j, 0} \oplus H(j, \boldsymbol{q}_{j}), y_{j, 1} = x_{j, 1} \oplus H(j, \boldsymbol{q}_{j} \oplus \boldsymbol{s})$，并发送 $(y_{j, 0}, y_{j, 1})$.
$P_r$ 输出 $z_j = y_{j, r_j} \oplus H(j, \boldsymbol{t}_{j}), 1 \leq j \leq m$.

安全性的直观说明

我们首先在半诚实安全模型下直观分析一下IKNP OT扩展协议的安全性。

发送方的隐私性。 发送方使用了 $H(j, \boldsymbol{q}_{j})$ 和 $H(j, \boldsymbol{q}_{j} \oplus \boldsymbol{s})$ 分别加密 $x_{j, 0}$ 和 $x_{j, 1}$. 接收方知道 $(\boldsymbol{q}_{j}, \boldsymbol{q}_{j} \oplus \boldsymbol{s})$ 其中的一个；由于 $\boldsymbol{s}$ 是均匀随机选取的，因此接收方不知道另一个。当然，接收方可以试图“猜测”这个消息并请求随机谕示机，但是这个消息均匀分布于 $2^k$ 的空间中，因此，当接收方只能对随机谕示机进行多项式次数的访问时，他成功的概率是可忽略的。

接收方的隐私性。 在发送方的视角中，协议中看到的信息只有矩阵 $\boldsymbol{Q}$. 由于矩阵 $\boldsymbol{T}$ 是均匀随机选取的，因此 $T$ 和 $T'$ 都是均匀随机的。无论 $\boldsymbol{s}$ 为何值，矩阵 $\boldsymbol{Q}$ 都是均匀随机的矩阵，因此不会泄露有关 $\boldsymbol{r}$ 的信息。

对于恶意敌手模型的情况，我们作一个简单的分析。协议中，发送方选择了随机向量 $\boldsymbol{s}$，并把 $(y_{j, 0}, y_{j, 1})$ 发给接收方；而无论发送方如何选择 $(y_{j, 0}, y_{j, 1})$ 的值，它们都对应于输入为 $x_{j, 0} = y_{j, 0} \oplus H(j, \boldsymbol{q}_{j}), \; x_{j, 1} = y_{j, 1} \oplus H(j, \boldsymbol{q}_{j} \oplus \boldsymbol{s})$ 时的消息，也就是等价于输入替换。因此，协议对恶意发送方是安全的。

然而，对于恶意的接收方，我们通过一个例子来表明协议确实是不安全的。接收方不遵循协议计算矩阵 $\boldsymbol{T}'$，而是让 $\boldsymbol{t}^i$ 和 $\boldsymbol{t}'^i$ 只有第 $i$ 个位置不同。不失一般性地，假设 $\boldsymbol{t}^i[i]=0, \boldsymbol{t}'^i[i]=1$. 那么此时，可以观察到，发送方得到的矩阵 $\boldsymbol{Q}$ 的第 $j$ 行 $\boldsymbol{q}_{j}$ 的第 $j$ 个位置就包含 $s_j$，而其他位置的值是接收方知道的（因为这些位置 $\boldsymbol{T}$ 和 $\boldsymbol{T}'$ 是相同的）。于是，如果接收方拥有关于消息空间的一些先验知识（例如，哪些是有意义的消息），接收方分别取 $s_j = 0$ 和 $s_j = 1$ 请求两次 $H$，就可以确定 $s_j$ 的值。当接收方恢复出向量 $\boldsymbol{s}$ 后，他可以解密两条消息，破坏发送方的隐私性。

安全性证明

现在，我们给出形式化的安全性证明。

定理

设 $t$ 是敌手请求随机谕示机 $H$ 的次数的上界。图 5.4展示的协议 $\Pi_\mathsf{IKNP}$ 对恶意的发送方和半诚实的接收方在 $\{H, \mathcal{F}_{\mathsf{OT}^k_m}\}$-混合世界中对于静态敌手UC-安全实现了理想功能 $\mathcal{F}_{\mathsf{OT}^m_\ell}$（图 5.7），其中敌手的区分优势不超过 $(t + 1) \cdot 2^{-k}$.

安全性证明

要证明该定理，我们需要构造模拟器 $\mathcal{S}$，使得对所有PPT的环境 $\mathcal{Z}$，都有

\operatorname{exec}_{\Pi_\mathsf{IKNP}, \mathcal{A}, \mathcal{Z}}^{H, \mathcal{F}_{\mathsf{OT}^k_m}} \approx \operatorname{exec}_{\mathcal{F}_{\mathsf{OT}^m_\ell}, \mathcal{S}, \mathcal{Z}}

其中 $\mathcal{A}$ 是平凡敌手。

模拟器 $\mathcal{S}$. 首先，模拟器 $\mathcal{S}$ 在内部运行 $\mathcal{A}$，转发 $\mathcal{Z}$ 与 $\mathcal{A}$ 之间的消息。并且，$\mathcal{S}$ 需要模拟 $H$ 和 $\mathcal{F}_{\mathsf{OT}^k_m}$. 我们分别考虑发送方和接收方被攻陷的情况。

情况1：发送方 $P_s$ 被攻陷。 在这种情况下，敌手是恶意的，可以不遵循协议。$\mathcal{S}$ 的工作方式如下。

在协议第2步，$\mathcal{S}$ 记录 $P_s$ 对 $\mathcal{F}_{\mathsf{OT}^k_m}$ 的输入 $\boldsymbol{s}$，并选择一个 $m \times k$ 的均匀随机矩阵 $\boldsymbol{Q}$ 作为 $\mathcal{F}_{\mathsf{OT}^k_m}$ 的输出（$\mathcal{S}$ 不知道 $P_r$ 的输入）。
在协议第3步，当 $P_s$ 发送 $(y_{j, 0}, y_{j, 1}), 1 \leq j \leq m$ 给 $P_r$ 时，$\mathcal{S}$ “提取”出 $x_{j, 0} = y_{j, 0} \oplus H(j, \boldsymbol{q}_{j}), \; x_{j, 1} = y_{j, 1} \oplus H(j, \boldsymbol{q}_{j} \oplus \boldsymbol{s}), 1 \leq j \leq m$. 并在理想世界中代表 $P_s$ 将 $(x_{j, 0}, x_{j, 1}), 1 \leq j \leq m$ 输入给 $\mathcal{F}_{\mathsf{OT}^m_\ell}$.

不可区分性。 首先，根据前面的推导，矩阵 $\boldsymbol{Q}$ 满足 $\boldsymbol{q}_{j} = (r_j \cdot \boldsymbol{s}) \oplus \boldsymbol{t}_{j}, 1 \leq j \leq m$，因而协议的正确性成立。根据 $\mathcal{S}$ 计算 $(x_{j, 0}, x_{j, 1})$ 的方式，$P_r$ 在理想世界和真实世界中的输出是一致的。其次，在敌手的视角中，无论在真实世界还是理想世界，$\boldsymbol{Q}$ 都是均匀随机的矩阵。因此，理想世界和真实世界完美不可区分。

情况2：接收方 $P_r$ 被攻陷。 在这种情况下，敌手是半诚实的，因此 $\mathcal{S}$ 知道 $P_r$ 的协议输入 $\boldsymbol{r}$. $\mathcal{S}$ 的工作方式如下。

在协议第2步，$\mathcal{S}$ 模拟 $P_r$ 遵循协议均匀随机地选择矩阵 $\boldsymbol{T}$ 并以 $\boldsymbol{t}^i, \boldsymbol{r} \oplus \boldsymbol{t}^i, 1 \leq i \leq k$ 为输入调用 $\mathcal{F}_{\mathsf{OT}^k_m}$. $\mathcal{S}$ 模拟 $P_s$ 均匀随机选择 $\boldsymbol{s}$，并诚实地计算 $\boldsymbol{Q}$.
当 $\mathcal{S}$ 在理想世界中收到协议的输出 $z_j, 1 \leq j \leq m$ 时，$\mathcal{S}$ 计算 $y_{j, r_j} = z_j \oplus H(j, \boldsymbol{q}_{j} \oplus (r_j \cdot \boldsymbol{s}) ), \; y_{j, 1-r_j} = 0^\ell \oplus H(j, \boldsymbol{q}_{j} \oplus ( (1 - r_j) \cdot \boldsymbol{s}) )$，并将 $(y_{j, 0}, y_{j, 1}), 1 \leq j \leq m$ 发给 $P_r$. （也就是说，$\mathcal{S}$ 不知道 $P_s$ 的输入：它的做法是，对于 $P_r$ 应该收到的消息，$\mathcal{S}$ 诚实地计算；对于 $P_r$ 不知道的那条消息，$\mathcal{S}$ 将其替换为 $0^\ell$）

\Pr[B] \leq (t + 1) \cdot 2^{-k}

即敌手区分理想世界和真实世界的优势不超过 $(t + 1) \cdot 2^{-k}$. 定理得证。

本章思考题

虽然无法以黑盒的方式利用一般性的公钥加密来构造OT协议，我们是否可以利用一些具有特殊性质的公钥加密算法来构造OT协议呢？
IKNP OT扩展协议的安全性证明中使用了随机谕示机（Random Oracle）？如果替换为具体的哈希函数，安全性会受到哪些影响？我们需要具有什么特性的哈希函数？
OT协议被证明是安全多方计算的完备原语。请思考一下如何利用OT构造一个安全的二方承诺协议。

学习笔记

记录协议细节、模拟器构造与图中记号对照。

本章笔记

第 5 章 茫然传输和茫然传输扩展

目录

第 5 章 茫然传输和茫然传输扩展

关于OT的一些结论

不存在信息论安全的两方OT协议

OT变种

一些其他结论

基于DDH假设的OT协议（半诚实安全）

协议描述

安全性的直观说明

安全性证明

三方OT协议（恶意安全）

协议描述

安全性的直观说明

安全性证明

IKNP OT扩展协议

协议描述

安全性的直观说明

安全性证明

本章思考题

学习笔记

第 5 章茫然传输和茫然传输扩展

第 5 章茫然传输和茫然传输扩展