第 2 章基础知识

学习目标

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

本章将介绍阅读本书所需的基础知识。我们首先介绍现代密码学的核心——可证明安全。可证明安全的三个关键组成部分是定义、假设、证明。我们将通过一个公钥加密方案的例子带领读者了解可证明安全的理念。然后，我们介绍本书使用的符号和术语，并定义一些密码学基础原语。

现代密码学与可证明安全

从历史角度来看，密码学更像是一门艺术而非科学。早期的密码方案设计往往依赖设计者的直觉经验，其优劣评判标准主要取决于方案的复杂程度和构思巧妙性。安全性分析则采用"攻击-修补"的被动模式：通过穷举可能的攻击方式来检验方案，发现漏洞后再进行针对性修补。这种模式下，那些遭遇过重大攻击的方案自然会被认定为不安全，但反过来，要证明某个方案确实安全可靠，却始终缺乏系统性的判定标准。

Katz和Lindell在Introduction to Modern Cryptography一书 [Katz & Lindell, 2007]中将现代密码学的与传统密码学的主要不同总结为形式化的定义、精确的假设和严格的安全性证明。下面我们更详细地解释这三个原则。

形式化的定义

一个常见的误区是：人们对于想实现的安全性有直观的认识，因此不需要花费时间做形式化的定义。下面，我们将以加密为例阐释定义的重要性。安全定义分为两个部分：安全保证和威胁模型。安全保证定义了方案应该满足什么样的安全属性，或者从敌手的角度来说，什么构成了成功的攻击；威胁模型定义了敌手拥有的能力，即敌手可以看到哪些信息、执行哪些操作。

对于一个加密方案来说，应该有怎样的安全保证呢？

你的第一反应可能是：敌手不能从密文中恢复出明文。这是一个直观的想法。然而，如果某个加密方案泄漏了50\%的明文，而另外50\%无法破译，那么按照这个定义它是安全的，但是这样的方案显然与实际的安全需求相悖。

我们把这个漏洞补上：敌手应该不能从密文中恢复出明文的任何一个字符。这比刚才的定义考虑得更全面。但是，以员工薪资的加密数据库为例，按照这个定义，敌手不能从密文中恢复出任何字符，但是他也许可以判断加密的薪资是否大于20万。那么这样的加密方案依然会泄露员工信息。

正确的定义是：敌手不能从密文中获得关于明文的任何信息。注意，该定义的关键在于它没有要求有关明文的信息是“有意义”的内容，而且仅要求不泄露任何信息。这一点很重要，它保证了安全的加密方案适用于所有需要保密性的潜在场景。

确定了安全保证之后，还需要明确威胁模型，也就是敌手拥有的能力。需要特别强调的是，威胁模型只规定了敌手的能力，而不对其采用的策略施加任何限制。这是因为：我们永远无法预判敌手可能采用的所有攻击手段。历史多次证明，预设敌手的攻击策略，注定会设计出失败的方案。

对于加密方案，有以下几种合理的威胁模型。我们按照敌手能力增强的顺序依次介绍：

仅密文攻击(ciphertext-only attack)：这是最基本的攻击，敌手只能看到（多个）密文。
已知明文攻击(known-plaintext attack)：敌手能够看到某个密钥生成的一个或多个明文/密文对。
选择明文攻击(chosen-plaintext attack)：敌手能够看到某个密钥生成的明文/密文对，且敌手可以选择加密的明文。
选择密文攻击(chosen-ciphertext attack)：敌手除了能选择加密的明文，还可以获得他选定的密文解密后的消息。敌手的目标仍然是获得使用相同密钥生成的其他密文所对应的明文信息，但是他不允许直接获得这些密文的解密。

尽管这些威胁模型中敌手的能力是增强的，但这并不代表哪一种威胁模型更好。我们应该根据实际场景来选择合适的威胁模型。

前两种模型比较直观：在网络通信中，我们通常假设敌手可以监听网络流量；对于已知明文攻击，一个简单的例子是，当两方开始通信时，他们的第一条消息可能总是“你好”。后两种模型乍一看似乎比较奇怪，敌手竟然可以选择加密的明文甚至解密指定的密文！不过，他们在现实世界中也有实际例子。在第二次世界大战期间，英国知道德国人发现水雷时会对这些位置进行加密并发送回总部；因此他们在特定地点布设水雷，然后这些加密消息被Bletchley Park的密码分析员用来破解德国的加密方案，这就是选择明文攻击。选择密文攻击的例子是，当敌手冒充客户端向服务器发送加密消息时，服务器会尝试解密，因而敌手可以从服务器的反应中推断出一些信息。例如，发送的密文是否被解密为格式正确的明文。

好，我们已经讨论了加密方案应该有的安全保证和威胁模型。为了精确地描述它们，密码学中我们通过游戏(Game)来准确地定义安全性。在一个游戏中，有两个角色——Challenger（注：Challenger在这里的意思是参与这个游戏的人。若翻译成挑战者则不太贴切，因此不作翻译。）和敌手(Adversary)，他们按照游戏的规定进行一系列交互，最后，我们用敌手获胜的概率来定义安全性。

为了与下文中的例子相一致，这里给出公钥加密方案在选择明文攻击下（注：在实际应用中，选择明文攻击是较为常用的威胁模型。）的不可区分游戏(INDistinguishability under Chosen-Plaintext Attack, IND-CPA)。公钥加密与对称加密的不同之处在于：公钥加密方案的消息接收方首先生成一对公私钥 $(\mathsf{pk}, \mathsf{sk})$ 并将 $\mathsf{pk}$ 公开，任何人都可以使用 $\mathsf{pk}$ 加密消息，但是只有拥有 $\mathsf{sk}$ 才可以将消息解密。更形式化地说，一个公钥加密方案 $\Pi$ 包含3个算法 $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$，其中 $(\mathsf{pk}, \mathsf{sk}) \leftarrow \mathsf{Gen}(1^\kappa)$生成一对公私钥（注：这里的 $\kappa$ 是安全参数，在「基本术语和符号」一节会详细介绍。读者可以暂时把 $\kappa$ 理解成描述协议安全性的参数。$1^\kappa$ 是安全参数的一元表示，即 $\kappa$ 个1，这是为了确保 $\mathsf{Gen}$ 的运行时间是 $O(\kappa)$.）；$c \leftarrow \mathsf{Enc}_{\mathsf{pk}}(m)$ 输入公钥 $\mathsf{pk}$ 和消息 $m$，输出密文 $c$；$m / \bot \leftarrow \mathsf{Dec}_{\mathsf{sk}}(c)$ 输入私钥 $\mathsf{sk}$ 和密文 $c$，输出消息 $m$ 或特殊符号 $\bot$ 表示解密失败。并且，算法满足 $\mathsf{Dec}_{\mathsf{sk}}(\mathsf{Enc}_{\mathsf{pk}}(m)) = m$.

公钥加密方案在选择明文攻击下的不可区分游戏定义如下：

形式化的定义

公钥加密方案IND-CPA游戏 $\mathsf{PubK}^\mathsf{CPA}_{\mathcal{A}, \Pi}(\kappa)$：

Challenger运行 $\mathsf{Gen}(1^\kappa)$ 得到 $(\mathsf{pk}, \mathsf{sk})$，并将 $\mathsf{pk}$ 发给敌手 $\mathcal{A}$.
敌手 $\mathcal{A}$ 发送相同长度的 $m_0, m_1$ 给Challenger.
Challenger均匀随机地选择一个比特 $b \leftarrow_{\$} \{0, 1\}$，计算 $c \leftarrow \mathsf{Enc}_{\mathsf{pk}}(m_b)$，然后把密文 $c$ 发给 $\mathcal{A}$.
$\mathcal{A}$ 输出比特 $b'$. 如果 $b' = b$，游戏的输出为1，表示 $\mathcal{A}$ 成功；否则，输出0.

注意，由于是公钥加密方案，敌手 $\mathcal{A}$ 拥有公钥 $\mathsf{pk}$，因此他可以对任何消息自己进行加密，而无需为其提供加密消息的接口 $\mathsf{Enc}_{\mathsf{pk}}(\cdot)$.

现在，我们可以给出公钥加密方案在选择明文攻击下具有不可区分性的形式化定义。

定义

公钥加密方案 $\Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ 如果对任意概率多项式时间的敌手 $\mathcal{A}$，都存在一个可忽略函数 $\mathsf{negl}$（注：可忽略函数的定义在「基本术语和符号」一节会详细介绍，直观地说，可忽略函数趋近于0的速度比任何正多项式的倒数都更快。），使得

\Pr[\mathsf{PubK}^\mathsf{CPA}_{\mathcal{A}, \Pi}(\kappa) = 1] \leq \frac{1}{2} + \mathsf{negl}(\kappa)

那么，我们说公钥加密方案 $\Pi$ 在选择明文攻击下具有不可区分性(IND-CPA secure)。

该定义说明：如果没有（概率多项式时间的）敌手能够以不同于 $1/2$ 的概率判断出 $m_0, m_1$ 中哪一个消息被加密，那么公钥加密方案 $\Pi$ 是安全的（$1/2$ 表示敌手仅靠随机猜测猜对的概率）。

精确的假设

大多数现代密码方案都不是无条件安全的，他们的安全性证明必须依赖于一些未经证明的假设（注：绝大多数密码方案需要假设 $P \neq NP$.）。对此，读者可能会产生疑问：既然假设是不可避免的，那何必基于某假设来证明安全性？为什么不直接假设方案本身是安全的？这种思路看似直接，实则存在问题。首先，一个被研究多年未被攻破的假设要比新的、任意的假设更可靠；其次，我们喜欢关于一个“干净”的数学问题的难度的假设，而不是一个复杂方案满足了复杂安全性定义的假设，简单的假设更利于理解和研究。

密码学中有许多被广泛采用的假设，例如大整数分解的困难性假设、离散对数假设、DDH(Decisional Diffie–Hellman)假设等。这里，我们给出DDH假设的精确定义，作为一个例子。

考虑一个阶为 $q$ 的循环群 $\mathbb{G}$，它的生成元为 $g$. 给定 $g^x, g^y$，其中 $x, y \leftarrow_{\$} \mathbb{Z}_q$ 是均匀随机选择的，DDH假设说的是，$g^{xy}$ 与 $\mathbb{G}$ 中的一个均匀随机元素在计算上是不可区分的。

定义

如果对任意概率多项式时间的敌手 $\mathcal{A}$，都存在一个可忽略函数 $\mathsf{negl}$，使得

\left| \Pr[\mathcal{A}(\mathbb{G}, q, g, g^x, g^y, g^z) = 1] - \Pr[\mathcal{A}(\mathbb{G}, q, g, g^x, g^y, g^{xy}) = 1] \right| \leq \mathsf{negl}(\kappa)

其中，群参数 $\mathbb{G}, q, g$ 是由群的生成算法 $\mathcal{G}(1^\kappa)$ 生成的，$x, y, z \leftarrow_{\$} \mathbb{Z}_q$ 是均匀随机选择的。那么，我们说DDH问题在群 $\mathbb{G}$ 中是困难的。

这里，$\mathbb{G}, q, g$ 是群的参数，敌手 $\mathcal{A}$ 得到的输入是 $(g^x, g^y, g^z)$ 或者 $(g^x, g^y, g^{xy})$. 在这两种情况下，$\mathcal{A}$ 输出1的概率几乎相等，也就是说 $\mathcal{A}$ 在接收到 $(g^x, g^y, g^z)$ 或者 $(g^x, g^y, g^{xy})$ 时不会有不同的表现，这代表 $\mathcal{A}$ 无法区分 $(g^x, g^y, g^z)$ 和 $(g^x, g^y, g^{xy})$. 像 $(g^x, g^y, g^{xy})$ 这样形式的三元组被称为DDH三元组；$(g^x, g^y, g^z)$ 被称为随机三元组。

严格的安全性证明

基于既定的安全定义和数学假设，我们可以构建严格的安全性证明。这种证明本质上是一种“归约”，即，假设存在一个能够攻破该密码方案的敌手 $\mathcal{A}$，那么就可以基于 $\mathcal{A}$ 构造出一个能够攻破底层假设的敌手 $\mathcal{B}$. 由此可得：除非所依赖的底层假设本身不成立，否则该加密方案必然满足既定的安全定义。注意，这里我们不假定敌手 $\mathcal{A}$ 的攻击策略，无论其采用什么策略，只要 $\mathcal{A}$ 能攻破该密码方案，那么就可以构造敌手 $\mathcal{B}$ 攻破底层假设。历史多次证明，假定敌手的攻击策略必然会导致有缺陷的密码方案。

下面，我们以一个公钥加密方案——ElGamal为例，我们将严格地证明它在DDH假设下满足IND-CPA安全性。

ElGamal加密方案。考虑一个阶为 $q$ 的循环群 $\mathbb{G}$，它的生成元为 $g$. ElGamal加密方案包含三个算法 $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$. 生成算法 $\mathsf{Gen}$ 随机选择 $\mathsf{sk} \leftarrow_{\$} \mathbb{Z}_q$，然后计算 $\mathsf{pk} = g^\mathsf{sk}$，输出 $(\mathsf{pk}, \mathsf{sk})$. 加密算法 $\mathsf{Enc}$ 的输入是公钥 $\mathsf{pk}$ 和消息 $m \in \mathbb{G}$，输出密文 $c = (c_1, c_2) = (g^r, m \cdot \mathsf{pk}^r)$，其中 $r \leftarrow_{\$} \mathbb{Z}_q$ 是均匀随机选择的。解密算法 $\mathsf{Dec}$ 的输入是私钥 $\mathsf{sk}$ 和密文 $c = (c_1, c_2)$，输出 $\hat{m} = c_2 / c_1^\mathsf{sk}$（这里的除号$/$表示乘以某个群元素的逆元）。

严格的安全性证明 · 公式

我们首先检查一下正确性，即 $\mathsf{Dec}_{\mathsf{sk}}(\mathsf{Enc}_{\mathsf{pk}}(m)) = m$. 设 $c = (c_1, c_2) = (g^r, m \cdot \mathsf{pk}^r)$ 是正确生成的密文。我们有

\hat{m} = \frac{c_2}{c_1^\mathsf{sk}} = \frac{m \cdot \mathsf{pk}^r}{(g^r)^\mathsf{sk}} = \frac{m \cdot \mathsf{pk}^r}{(g^\mathsf{sk})^r} = \frac{m \cdot \mathsf{pk}^r}{\mathsf{pk}^r} = m

接着，我们来直观感受一下为什么ElGamal加密方案在DDH假设下是IND-CPA安全的。DDH假设说的是，DDH三元组 $(g^x, g^y, g^{xy})$ 与随机三元组 $(g^x, g^y, g^z)$ 在计算上是不可区分的。可以看到，$(\mathsf{pk} = g^\mathsf{sk}, c_1 = g^r, \mathsf{pk}^r)$ 恰恰构成了DDH三元组，因此 $\mathsf{pk}^r$ 与随机群元素是不可区分的，那么 $m \cdot \mathsf{pk}^r$ 也与随机群元素不可区分。反过来，我们从归约的角度来讲，如果存在敌手能够攻破IND-CPA游戏，也就是说他可以区分 $\mathsf{Enc}_{\mathsf{pk}}(m_0)$ 和 $\mathsf{Enc}_{\mathsf{pk}}(m_1)$. 我们假设Challenger加密的是 $m_0$，那么敌手 $\mathcal{A}$ 得到的是 $(c_1, c_2) = (g^r, m_0 \cdot \mathsf{pk}^r)$. 如果敌手能从 $(c_1, c_2)$ 中获得信息，那就说明在他看来 $m_0 \cdot \mathsf{pk}^r$ 和随机群元素并不是不可区分的（随机群元素不可能包含任何信息）。至此，我们要构造的归约就呼之欲出了。

定理

假设DDH问题在群 $\mathbb{G}$ 中是困难的，那么ElGamal加密方案是IND-CPA安全的。

严格的安全性证明

将ElGamal加密方案记作 $\Pi$. 我们只需证明：假设存在敌手 $\mathcal{A}$ 可以攻破ElGamal加密方案的IND-CPA安全性，即

\Pr[\mathsf{PubK}^\mathsf{CPA}_{\mathcal{A}, \Pi}(\kappa) = 1] = \frac{1}{2} + \epsilon(\kappa)

其中，$\epsilon(\kappa)$ 不是可忽略函数。那么，可以基于 $\mathcal{A}$ 构造攻破DDH假设的敌手（算法） $\mathcal{B}$.

算法 $\mathcal{B}$ 的构造如下：

严格的安全性证明

算法 $\mathcal{B}$：

算法的输入是 $(\mathbb{G}, q, g, h_1, h_2, h_3)$.

设置 $\mathsf{pk} = h_1$，将 $\mathsf{pk}$ 发给 $\mathcal{A}$，然后得到 $\mathcal{A}$ 发送的两条消息 $m_0, m_1 \in \mathbb{G}$.
选择均匀随机比特 $b'$，设置 $c_1 = h_2, \; c_2 = m_{b'} \cdot h_3$.
将密文 $(c_1, c_2)$ 发给 $\mathcal{A}$ 并获得 $\mathcal{A}$ 的输出 $b$. 若 $b' = b$，输出1；否则，输出0.

严格的安全性证明

下面我们来分析 $\mathcal{B}$ 输出1的概率，考虑 $(h_1, h_2, h_3)$ 是随机三元组和DDH三元组两种情况。

情况1：$(h_1, h_2, h_3)$ 是随机三元组。即 $(h_1, h_2, h_3) = (g^x, g^y, g^z)$. 此时，$(c_1, c_2) = (h_2, m_b \cdot h_3)$ 是完全随机的，不可能包含 $m_b$ 的信息。因此，$\mathcal{A}$ 的输出 $b = b'$ 的概率（即 $\mathcal{B}$ 输出1的概率）等于 $\frac{1}{2}$.

情况2：$(h_1, h_2, h_3)$ 是DDH三元组。即 $(h_1, h_2, h_3) = (g^x, g^y, g^{xy})$. 此时，$\mathcal{A}$ 收到的 $\mathsf{pk} = h_1 = g^x$，$(c_1, c_2) = (g^y, m_b \cdot g^{xy})$. $\mathcal{A}$ 看到的所有消息与游戏 $\mathsf{PubK}^\mathsf{CPA}_{\mathcal{A}, \Pi}(\kappa)$ 中是完全一样的。所以此时$\mathcal{A}$ 的输出 $b = b'$ 的概率（即 $\mathcal{B}$ 输出1的概率）等于 $\Pr[\mathsf{PubK}^\mathsf{CPA}_{\mathcal{A}, \Pi}(\kappa) = 1]$.

综上所述，我们有

\begin{aligned}& \left| \Pr[\mathcal{B}(\mathbb{G}, q, g, g^x, g^y, g^z) = 1] - \Pr[\mathcal{B}(\mathbb{G}, q, g, g^x, g^y, g^{xy}) = 1] \right| \\ = & \left| \frac{1}{2} - \Pr[\mathsf{PubK}^\mathsf{CPA}_{\mathcal{A}, \Pi}(\kappa) = 1] \right| \\ = & \left| \frac{1}{2} - (\frac{1}{2} + \epsilon(\kappa)) \right| \\ = & \epsilon(\kappa)\end{aligned}

它不是可忽略函数。因此 $\mathcal{B}$ 攻破了DDH假设。证毕。

希望读者能从这个例子中领会到可证明安全的理念。在本书后面的章节中，基于归约的证明技术将多次出现。

基本术语和符号

我们假设读者有高等数学、概率论与数理统计、离散数学、算法复杂度的基础知识，对于其中的基本概念，本书不再重复介绍。本书将安全多方计算(secure Multi-Party Computation)缩写为MPC，将概率多项式时间(Probablistic Polynomial Time)缩写为PPT. 我们用 $[n]$ 表示集合 $\{1, 2, …, n\}$，用 $\leftarrow_{\$} $ 表示均匀随机选取。$|X|$ 表示集合 $X$ 的大小。

可忽略函数。可忽略函数 $\mathsf{negl}(\cdot)$ 是一个比任何正多项式的倒数趋近于0的速度更快的函数，即：对任意的正多项式 $\mathsf{poly}(\cdot)$ ，存在整数 $N > 0$ ，使得对所有 $x > N$ ，都有 $\mathsf{negl}(x) < \frac{1}{ \mathsf{poly}(x) } $.

安全参数。安全参数是密码学协议中影响参与方运行时间以及敌手成功概率的一个参数，它定义了协议的安全性等级，通常用字母 $\kappa$ 或 $\lambda$ 或 $n$ 表示。在参与方运行一个协议之前，他们会选定安全参数的值（例如，可以将对称加密方案的密钥长度视作安全参数）。协议中，参与方的运行时间通常是关于安全参数的多项式；如果一个敌手的运行时间是关于安全参数的多项式，我们认为他是高效的敌手（这体现了安全参数影响参与方和敌手的运行时间）。如果敌手攻破协议的概率是关于安全参数的一个可忽略函数，那么这个协议是安全的（这体现了安全参数影响敌手的成功概率）。

基本术语和符号 · 公式

统计距离。设 $X_1$ 和 $X_2$ 是定义在同一概率空间上的两个随机变量，并且它们具有相同的取值范围 $D$. 我们称

\delta(X_1, X_2) = \frac{1}{2} \sum_{d \in D} \left| \Pr[X_1 = d] - \Pr[X_2 = d] \right|

为 $X_1$ 和 $X_2$ 的统计距离（注：注意，如果范围 $D$ 是可数无穷的，那么只有在和收敛的情况下，这个定义才有意义。不过这个条件显然是成立的，因为级数 $\frac{1}{2} \sum\limits_{d \in D} \left| \Pr[X_1 = d] - \Pr[X_2 = d] \right|$ 是单调递增且上界为1的。）（又称总变差距离）。直观地说，两个随机变量的统计距离描述了它们在每个可能的取值上的概率之差的总和。

不可区分性。设 $X_1$ 和 $X_2$ 是关于安全参数 $\kappa$ 的两个概率分布，或者等价地说，$X_1$ 和 $X_2$ 是以安全参数 $\kappa$ 作为输入的两个算法。如果对于任意的敌手 $\mathcal{A}$ ，都存在可忽略函数 $\mathsf{negl}(\cdot)$，使得

基本术语和符号 · 公式

\left| \Pr[ \mathcal{A}( X_1(\kappa) )=1 ] - \Pr[ \mathcal{A}( X_2(\kappa) )=1 ] \right| \leq \mathsf{negl}(\kappa)

那么我们称 $X_1$ 和 $X_2$ 是不可区分的，记作 $X_1 \approx X_2$. 如果考虑的是PPT的敌手，那么此定义描述的是计算不可区分性，记作 $X_1 \stackrel{\text{comp}}{\approx} X_2$；如果考虑的是拥有无限计算能力的敌手，那么此定义描述的是统计不可区分性，记作 $X_1 \stackrel{\text{stat}}{\approx} X_2$，此时，式（式 2.1）的上界是 $X_1$ 和 $X_2$ 的统计距离；如果对所有的 $\kappa$，都有统计距离 $\delta(X_1(\kappa), X_2(\kappa)) = 0$，那么 $X_1$ 和 $X_2$ 是完美不可区分的，记作 $X_1 \stackrel{\text{perf}}{=} X_2$.

计算安全性表示协议面对PPT敌手时的安全性；信息论安全性表示协议面对拥有无限计算能力的敌手时的安全性。

基础原语

在这一小节，我们将介绍这本书用到的一些密码学基础原语，这些基础原语将会在后续章节的安全多方计算协议中被经常使用。

门限秘密分享

秘密分享是一种非常重要的密码学基础原语，这里我们主要讨论 $(t, n)$-门限秘密分享(threshold secret sharing)，即一个秘密 $s$ 被分成 $n$ 个秘密份额之后，其中任意 $t$ 个秘密份额不会泄露任何关于秘密 $s$ 的信息，而拥有任意 $t + 1$ 个秘密份额便能恢复出秘密 $s$. 我们给出 $(t, n)$-门限秘密分享的定义 [Bei & Cho, 1992]。

定义

设$\mathcal{D}$是秘密所在的域，$\mathcal{D}_{1}$ 是秘密份额所在的域。$(t, n)$-门限秘密分享方案包含以下两个算法 $(\mathsf{Share}, \mathsf{Rec})$：

$(s_1, …, s_n) \leftarrow \mathsf{Share}(s)$：这是分享算法，它以秘密 $s \in \mathcal{D}$ 作为输入，最后输出 $n$ 个秘密份额 $s_1, …, s_n \in \mathcal{D}_{1}$.
$s=\mathsf{Rec}(s_{i_1}, …, s_{i_k})$：这是恢复算法，它以任意 $k \geq t + 1$ 个秘密份额 $s_{i_1}, …, s_{i_k} \in \mathcal{D}_{1}$ 作为输入，最终输出秘密 $s \in \mathcal{D}$.

$(t,n)$-门限秘密分享方案需要满足如下的性质：

正确性：令 $(s_1,\dots,s_n)\leftarrow \mathsf{Share}(s)$，只要获得至少 $t + 1$ 个秘密份额便能恢复出秘密 $s$，即
$\Pr[\forall k\geq t + 1, \mathsf{Rec}(s_{i_1},\dots,s_{i_k})=s]=1\enspace.$
（完美）隐私性：任意不超过 $t$ 个秘密份额都不会泄露任何有关于秘密 $s$ 的信息。即，对任意集合 $U \subset [n]$，如果 $|U| \leq t$，那么 $\{s_j\}_{j \in U}$ 的分布与 $s$ 无关。

哈希函数与随机谕示机

哈希函数(hash functions)可以将较大的域映射到较小的范围。密码学的哈希函数 $H$ 还有以下性质：

抗原像性(preimage-resistance)：给定哈希的输出值 $y$，找到它的原像在计算上是不可行的。即，给定哈希输出值 $y$ 且不知道对应的输入值，找到 $x'$ 使得 $H(x') = y$ 在计算上不可行。
抗第二原像性(2nd-preimage resistance)：给定输入 $x$，找到另一输入使得它们的输出相同，在计算上是不可行的。即，给定 $x$，找到第二原像 $x' \neq x$ 使得 $H(x) = H(x')$ 在计算上不可行。
抗碰撞性(collision resistance)：找到两个不同的输入使它们的哈希输出相同，在计算上是不可行的。即，找到 $x \neq x'$ 使得 $H(x) = H(x')$ 在计算上不可行。

随机谕示机(Random Oracle, RO) [Bel & Rog, 1993]是一个理想化模型，它将哈希函数的输出理想化为完全随机。在随机谕示机模型下，所有参与方都被允许使用一个公开函数 $H: \{0,1\}^* \to \{0,1\}^\kappa$，其中 $\kappa$ 为安全参数。当参与方调用函数 $H$ 并以 $x \in \{0, 1\}^*$ 作为输入时，函数 $H$ 会查询它的所有历史调用记录，如果 $H(x)$ 从来没有被调用过，那么 $H$ 会挑选一个随机数 $r_x \leftarrow_{\$} \{0, 1\}^\kappa$，记录 $\langle x, r_x \rangle$ 并返回 $r_x$ 作为函数输出；如果 $H(x)$ 曾经被调用过，那么$H$便会返回曾经记录下的 $r_x$ 作为输出。

随机谕示机模型是一个输出纯随机的理想函数。在实际应用中，人们往往使用哈希函数来实例化随机谕示机模型，然而，现实中的哈希函数（例如SHA256）的输出并不是纯随机的。因此，有可能构造出的密码协议在随机谕示机模型下可证明安全，但是当随机谕示机模型被实例化为哈希函数时又不安全 [Can et al., 1998]。尽管随机谕示机模型在实例化时可能存在缺陷，人们仍然广泛接受它并将它作为一个重要的启发式模型。

伪随机数生成器

伪随机数生成器(PseudoRandom Generator, PRG)是一个高效的确定性算法。它的输入是一个较短的均匀随机串（称为种子seed），输出一个更长的“看起来随机的”（伪随机的）串。换句话说，伪随机数生成器通过少量的真随机数生成了大量的伪随机数，而生成的伪随机数和真随机数在计算上是不可区分的。

伪随机数生成器的形式化定义如下：

定义

令 $\mathcal{G}$ 是一个确定性多项式时间算法，对于任意的 $\kappa$ 和任意的输入 $s \in \{0, 1\}^\kappa$，它的输出 $\mathcal{G}(s)$ 是长度为 $\ell(\kappa)$ 的串。如果以下两个条件成立：

（扩展性。）对于每个 $\kappa$ 都有 $\ell(\kappa) > \kappa$.
（伪随机性。）对于任意PPT的算法 $\mathcal{A}$，存在可忽略函数 $\mathsf{negl}$ 满足
$| \Pr[\mathcal{A}(\mathcal{G}(s)) = 1] - \Pr[\mathcal{A}(r)] = 1 | \leq \mathsf{negl}(\kappa)$ 其中 $s \leftarrow_{\$} \{0, 1\}^\kappa, r \leftarrow_{\$} \{0, 1\}^{\ell(\kappa)}$.

那么，我们称 $\mathcal{G}$ 是一个伪随机数生成器。

对称加密

在对称加密方案(symmetric encryption schemes)中，加密密钥与解密密钥是相同的。常用的对称加密算法有DES、AES等。在上文「形式化的定义」一节，我们已经初步讨论其安全性定义，并给出了公钥加密方案的IND-CPA安全性定义。现在，我们给出对称加密方案的形式化定义：

定义

我们假设 $\mathcal{K}$ 是密钥所在的空间，$\mathcal{M}$ 是明文所在的空间，$\mathcal{E}$ 是密文所在的空间。对称加密方案包含以下三个算法 $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$：

$\mathsf{k}\leftarrow \mathsf{Gen}(1^\kappa)$：这是密钥生成算法，它以安全参数 $\kappa$ 作为输入，输出密钥 $\mathsf{k} \in \mathcal{K}$.
$c \leftarrow \mathsf{Enc}_{\mathsf{k}}(m)$：这是加密算法，它以密钥 $\mathsf{k} \in \mathcal{K}$ 和明文 $m \in \mathcal{M}$ 作为输入，输出密文 $c \in \mathcal{E}$.
$m \leftarrow \mathsf{Dec}_{\mathsf{k}}(c)$：这是解密算法，它以密钥 $\mathsf{k}\in\mathcal{K}$ 和密文 $c \in \mathcal{E}$ 作为输入，输出明文 $m \in \mathcal{M} \cup \{ \bot \}$，其中 $\bot$ 表示解密错误。

对于任意的密钥 $k \leftarrow \mathsf{Gen}(1^\kappa)$ 和明文 $m \in \mathcal{M}$，必须满足 $\mathsf{Dec}_{\mathsf{k}}(\mathsf{Enc}_{\mathsf{k}}(m)) = m$.

定义

对称加密的选择明文攻击安全性(IND-CPA secure)：一个对称加密方案 $\Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ 如果对于任意的PPT敌手 $\mathcal{A}$，有

\Pr\left[ \begin{array}{l} \mathsf{k} \leftarrow \mathsf{Gen}(1^\kappa); (m_0, m_1) \leftarrow \mathcal{A}^{\mathsf{Enc}_{\mathsf{k}}(\cdot)}(1^\kappa); \\ b \leftarrow \{0, 1\}; c \leftarrow \mathsf{Enc}_{\mathsf{k}}(m_b); b' \leftarrow \mathcal{A}^{\mathsf{Enc}_{\mathsf{k}}(\cdot)}(1^\kappa, c, m_0, m_1) \end{array} : \begin{array}{l} b = b' \end{array} \right] \leq \frac{1}{2} + \mathsf{negl}(\kappa) \enspace,

其中 $\mathsf{Enc}_{\mathsf{k}}(\cdot)$ 是一个接口，当输入为 $m$ 时，它会返回 $c \leftarrow \mathsf{Enc}_{\mathsf{k}}(m)$ 作为输出，$\mathcal{A}^{\mathsf{Enc}_{\mathsf{k}}(\cdot)}$ 表示敌手 $\mathcal{A}$ 可以任意地调用这个接口。

那么，我们称加密方案 $\Pi$ 具有选择明文攻击安全性(IND-CPA secure)。

（信息论一次性）消息认证码

加密方案为消息传输提供了隐私性(privacy)，但不保证完整性(integrity)。换句话说，加密方案虽然使敌手无法获得关于明文的任何信息，但不能阻止敌手在信道中注入消息或修改被传输的消息。消息认证码(Message Authentication Codes, MACs)提供了这层保障。在本书中，我们主要关注信息论一次性消息认证码(information-theoretic one-time MACs)。直观来说，消息认证码方案使用密钥为消息生成一个标签，而不知道密钥的敌手无法为消息生成合法的标签。消息认证码的定义与信息论一次性消息认证码的安全性定义如下。

定义

我们假设 $\mathcal{K}$ 是密钥所在的空间，$\mathcal{M}$ 是消息所在的空间，$\mathcal{T}$ 是标签所在的空间。消息认证码方案包含以下三个算法 $(\mathsf{Gen}, \mathsf{Mac}, \mathsf{Ver})$：

$\mathsf{k}\leftarrow \mathsf{Gen}(1^\kappa)$：这是密钥生成算法，它以安全参数 $\kappa$ 作为输入，输出密钥 $\mathsf{k} \in \mathcal{K}$.
$t \leftarrow \mathsf{Mac}_{\mathsf{k}}(m)$：这是标签生成算法，它以密钥 $\mathsf{k} \in \mathcal{K}$ 和消息 $m \in \mathcal{M}$ 作为输入，输出标签 $t \in \mathcal{T}$.
$0/1 \leftarrow \mathsf{Ver}_{\mathsf{k}}(m, t)$：这是验证算法，它以密钥 $\mathsf{k} \in \mathcal{K}$、消息 $m \in \mathcal{M}$ 和标签 $t \in \mathcal{T}$ 作为输入，输出 $0/1$ 表示不合法或合法.

对于任意的密钥 $k \leftarrow \mathsf{Gen}(1^\kappa)$ 和消息 $m \in \mathcal{M}$，必须满足 $\mathsf{Ver}_{\mathsf{k}}(m, \mathsf{Mac}_{\mathsf{k}}(m)) = 1$.

定义

信息论一次性消息认证码安全性：一个消息认证码方案 $\Pi = (\mathsf{Gen}, \mathsf{Mac}, \mathsf{Ver})$ 如果对于任意（拥有无限计算能力）的敌手 $\mathcal{A}$，有

\Pr\left[ \begin{array}{l} \mathsf{k} \leftarrow \mathsf{Gen}(1^\kappa); m' \leftarrow \mathcal{A}(1^\kappa); \\ t' \leftarrow \mathsf{Mac}_{\mathsf{k}}(m'); (m, t) \leftarrow \mathcal{A}(1^\kappa, m', t') \end{array} : \begin{array}{l} \mathsf{Ver}_{\mathsf{k}}(m, t) = 1 \wedge m \neq m' \end{array} \right] \leq \mathsf{negl}(\kappa) \enspace,

那么，我们称消息认证码方案 $\Pi$ 是信息论安全一次性消息认证码。

（信息论一次性）消息认证码 · 公式

一种信息论一次性消息认证码的构造如下。令消息空间 $\mathcal{M} = \mathbb{Z}_p$，标签空间 $\mathcal{T} = \mathbb{Z}_p$. 密钥 $(a, b)$ 是 $\mathbb{Z}_p$ 上的一对随机元素，即密钥空间 $\mathcal{K} = \mathbb{Z}_p \times \mathbb{Z}_p$. 标签生成算法定义如下：

\mathsf{Mac}_{a, b}(m) = a \cdot m + b \; (\bmod \; p)

对于消息标签对 $(m, t)$，验证算法检查 $a \cdot m + b \; (\bmod \; p) \stackrel{?}{=} t$，若验证通过则输出1，否则输出0.

承诺

承诺方案(commitments)中有两个参与方：承诺者和接收者。承诺者可以利用承诺方案来对他所持有的消息 $m$ 生成承诺 $c$，并将这个承诺 $c$ 发送给接收方。接收方在收到承诺 $c$ 之后并不能获得有关 $m$ 的任意信息，这就是承诺方案的隐藏性。之后，承诺者可以发送 $m$ 和打开信息 $d$ 给接收方，接收方根据 $d$ 来验证 $c$ 是不是对 $m$ 的承诺。承诺方无法把之前所发送的承诺 $c$ 打开为另一个消息 $m' \neq m$，这就是承诺方案的绑定性。

直观上，承诺方案就类似于把秘密放入了一个不透明的信封，其他人看不见信封中的内容。承诺者可以在之后将信封打开，展示之前放入的秘密。我们给出承诺方案的定义：

定义

我们假设 $\mathcal{K}$ 是承诺密钥所在的空间，$\mathcal{M}$ 是消息所在的空间，$\mathcal{C}$ 是承诺所在的空间，$\mathcal{D}$ 是打开信息所在的空间。承诺方案包含以下三个算法 $(\mathsf{Gen}, \mathsf{Com}, \mathsf{Ver})$：

$\mathsf{ck} \leftarrow \mathsf{Gen}(1^\kappa)$：这是承诺密钥生成算法，它以安全参数 $\kappa$ 作为输入，最终输出承诺密钥 $\mathsf{ck} \in \mathcal{K}$.
$(c, d) \leftarrow \mathsf{Com}_{\mathsf{ck}}(m)$：这是承诺算法，它以承诺密钥 $\mathsf{ck} \in \mathcal{K}$，消息 $m \in \mathcal{M}$ 作为输入，最终输出承诺 $c\in \mathcal{C}$ 和打开消息 $d \in \mathcal{D}$.
$b=\mathsf{Ver}_{\mathsf{ck}}(c, m, d)$：这是承诺验证算法，它以承诺密钥 $\mathsf{ck} \in \mathcal{K}$，承诺 $c \in \mathcal{C}$，消息 $m \in \mathcal{M}$ 和打开消息 $d \in \mathcal{D}$ 作为输入，最终输出一个比特 $b \in \{0, 1\}$ 来表示通过验证 $(b = 1)$ 或者未能通过验证 $(b = 0)$.

承诺方案需要满足如下性质：

正确性：对于任意的消息 $m\in\mathcal{M}$，我们有
$\Pr[\mathsf{ck} \leftarrow \mathsf{Gen}(1^\kappa); (c, d) \leftarrow \mathsf{Com}_{\mathsf{ck}}(m): \mathsf{Ver}_{\mathsf{ck}}(c, m, d) = 1] = 1 \enspace.$
（计算上的）隐藏性：对于任意PPT的敌手 $\mathcal{A}$，我们有
$\Pr\left[ \begin{array}{l} \mathsf{ck} \leftarrow \mathsf{Gen}(1^\kappa); (m_0, m_1) \leftarrow \mathcal{A}(\mathsf{ck}); \\ b \leftarrow \{0, 1\}; (c, d) \leftarrow \mathsf{Com}_{\mathsf{ck}}(m_b); b' \leftarrow \mathcal{A}(c, \mathsf{ck}, m_0, m_1) \end{array} : \begin{array}{l} b = b' \end{array} \right] \leq \frac{1}{2} + \mathsf{negl}(\kappa) \enspace.$
（计算上的）绑定性：对于任意PPT的敌手 $\mathcal{A}$，我们有
$\Pr\left[ \begin{array}{l} \mathsf{ck} \leftarrow \mathsf{Gen}(1^\kappa); \\ (c, m_0, m_1, d_0, d_1) \leftarrow \mathcal{A}(\mathsf{ck}) \end{array} : \begin{array}{l} \mathsf{Ver}_{\mathsf{ck}}(c, m_0, d_0) = \mathsf{Ver}_{\mathsf{ck}}(c, m_1, d_1) = 1 \\ \wedge \; m_0 \neq m_1 \end{array} \right] \leq \mathsf{negl}(\kappa) \enspace.$

在现实场景下，常用的承诺方案有基于哈希的承诺、Pedersen承诺等。基于哈希的承诺无需承诺密钥，承诺定义为 $c = H(m || r)$，其中 $H$ 是抗碰撞的哈希函数，$m$ 是承诺的消息，$r$ 是随机数。当需要打开承诺时，承诺者公布 $m, r$（即方案的打开消息为 $d = r$）。验证算法验证 $c \stackrel{?}{=} H(m || r)$. Pedersen承诺的承诺密钥 $\mathsf{ck} = h \in \mathbb{G}$ 是一个群元素，其离散对数是未知的。假设群 $\mathbb{G}$ 的生成元为 $g$，Pedersen承诺定义为 $c = g^m h^r$，其中 $m$ 是承诺的消息，$r$ 是随机数。当需要打开承诺时，承诺者公布 $m, r$（即方案的打开消息为 $d = r$）。验证算法验证 $c \stackrel{?}{=} g^m h^r$.

茫然传输

茫然传输(Oblivious Transfer, OT)（注：也被翻译为“不经意传输”，我们认为“茫然传输”更贴切。）是一个两方协议，包含两个参与方：发送方和接收方。发送方持有两个消息 $x_0$ 和 $x_1$，接收方持有一个选择比特 $b\in\{0,1\}$，在协议的最后，接收方可以获得消息 $x_b$. 茫然传输协议有如下的隐私性保障：（1）接收方无法得知发送方所持有的另一条消息 $x_{1-b}$；（2）发送方无法得知接收方所持有的选择比特 $b$.

在密码学中，我们常常使用理想功能(ideal functionality)来定义原语。一个理想功能刻画了协议所希望实现的效果，它类似于一个可信第三方的角色：它接受所有参与方的输入，执行正确的计算，并将输出私密地发给参与方。一个功能描述了协议所期望达到的正确性和隐私性。

我们把茫然传输的理想功能记作 $\mathcal{F}_{\mathsf{OT}}$，其具体定义如图 2.1所示。由图 2.1可知，$\mathcal{F}_{\mathsf{OT}}$ 保障了接收方无法获取 $x_{1-b}$，同时 $\mathcal{F}_{\mathsf{OT}}$ 也保障了发送方不知道接收方收到了哪条消息，因而 $\mathcal{F}_{\mathsf{OT}}$ 很好地展现了茫然传输的安全性。

本章思考题

一个可证明安全的协议是否在现实中一定是安全的？如果不是，为什么？
请思考密码学的安全定义中的游戏和平时我们娱乐消遣玩的游戏有什么共同之处？
随机谕示机模型与现实中哈希函数的主要差异是什么？
如果 $P = NP$，是否存在伪随机数生成器，为什么？

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

学习笔记

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

本章笔记

第 2 章 基础知识

目录

第 2 章 基础知识

现代密码学与可证明安全

形式化的定义

精确的假设

严格的安全性证明

基本术语和符号

基础原语

门限秘密分享

哈希函数与随机谕示机

伪随机数生成器

对称加密

（信息论一次性）消息认证码

承诺

茫然传输

本章思考题

学习笔记

第 2 章基础知识

第 2 章基础知识