3.Private-Key Encryption

在前一章中，我们看到了完全保密的一些基本限制。在本章中，我们通过引入较弱（但充分）的计算保密概念来开始我们对现代密码学的研究。然后，我们将展示如何使用这个定义来绕过之前显示的不可能的结果，以实现完全保密，特别是如何使用一个短密钥（比如128位长）来加密许多长消息（比如总共千兆字节）。

在此过程中，我们将研究伪随机性的基本概念，它捕捉到了一些东西可以“看起来”完全随机的概念，即使它不是。这个强大的概念是许多现代密码学的基础，并具有超出该领域的应用和含义。

3.1 计算安全

第二章中我们介绍了完美保密的概念。虽然完美保密是值得追求的目标，但它也是不必要的强要求。完美保密要求加密消息绝对不泄露任何信息，即使是对于具有无限计算能力的窃听者。然而，在实际情况下，如果加密方案向拥有有限计算能力的窃听者泄露一些微小概率的信息，仍然可以被认为是安全的。例如，一个方案向投入最快的超级计算机（或计算机集群）200年计算能力的窃听者泄露概率不超过$2^{60}$的信息，对于实际应用来说已经足够安全。计算安全定义考虑了攻击者的计算限制，并允许存在一定的概率违反安全性，与信息论性质的概念（如完美保密）相反。计算安全现在是评估加密方案安全性的事实标准。

我们强调，尽管我们放弃了获得完美机密性的想法，但这并不意味着我们放弃了到目前为止一直采用的严格数学方法。定义和证明仍然是必不可少的；唯一的区别在于，我们现在考虑了一个更弱但仍然有意义的安全概念。正如前面讨论的那样，计算安全定义相对于信息理论安全概念包含了两个放松条件：

1. 安全性仅对有效的、运行一些可行时间的攻击者有保障。这意味着在足够的时间（或足够的计算资源）内，攻击者可能能够违反安全性。然而，如果我们可以使破解方案所需的资源大于任何实际攻击者可用的资源，那么在所有实际用途上，方案都是不可破解的。
2. 攻击者有可能以极小的概率成功（即安全性可能会失败）。如果我们可以使这个概率足够小，那么我们就不必担心它了。

（正如我们将看到的，这两个放宽条件都是必要的，以克服上一章所展示的完美机密性的限制。）为了得到一个有意义的理论，我们需要精确地定义上述放松条件的含义。==有两种一般的方法可以做到这一点：具体方法和渐近方法==。下面将对它们进行描述。

3.1.1 具体方法

计算安全的具体方法通过明确限定某个特定时间或者计算资源下，（随机化）攻击者的最大成功概率，来量化加密方案的安全性。因此，具体的安全性定义采用如下形式：

$$\text{如果任意一个在时间上限为t的攻击者都不能以成功概率高于}\epsilon \text{的概率破解加密方案，那么这个方案就是：(t,}\epsilon \text{)-安全的。}$$

（当然，上述内容只是一个一般的模板，为了使其有意义，我们需要明确“破解”该方案的确切含义。）例如，我们可能有一个方案，保证在最多使用最快的超级计算机200年的时间内，没有攻击者能够以高于$2^{60}$的概率成功破解该方案。或者，为了方便，我们可以用CPU周期来度量运行时间，并构造这样一个方案，使得没有攻击者使用不超过280个周期就能以高于$2^{60}$的概率破解该方案。

更加深入地了解现代密码系统中典型的大量时间和小概率的值，对于理解具体方法的应用也非常重要。

例3.1

现代私钥加密方案通常被认为在以下意义上提供几乎最优的安全性：当密钥长度为n时，密钥空间的大小为$2^n$，攻击者在运行时间t（例如CPU周期）内成功破解该方案的概率最多为$ct/2^n$，其中c是一个固定的常数。（这仅仅对应于对密钥空间进行暴力搜索。）

为了简单起见，假设c=1，那么长度为n=64的密钥对于使用标准台式计算机的攻击者提供了足够的安全性。事实上，在一个每秒执行$4\times {10}^9$个周期的4 GHz处理器上，每个核心执行$4\times {10}^9$个周期，264个CPU周期需要$264/(4\times {10}^9\times 16)$秒，约为9年。（上述数字仅供说明，实际上c不等于1，而且包括访问内存所需的时间等其它因素可能会显着影响暴力攻击的性能。）

然而，没有理由假设攻击者仅限于使用台式计算机，强大的攻击者能够进行数倍于此的计算速度。今天，最小推荐的密钥长度是n=128。$2^{64}$和$2^{128}$之间的差异是$2^{64}$的倍数。为了了解它有多大，请注意，根据物理学家的估计，宇宙大爆炸在$2^{58}$秒后左右。

如果攻击者在一年内成功恢复加密消息的概率最多为$2^{-60}$次方，那么在这段时间内，发件人和收件人都被闪电击中的可能性比攻击者恢复消息的可能性更高！每秒发生一次概率为$2^{-60}$的事件预计大约每100亿年发生一次。

具体方法在实践中非常重要，因为具体的保证才是加密方案的用户最终关心的。然而，精确的具体保证很难提供。此外，在解释具体安全性声明时必须小心。例如，一个声称在5年内没有攻击者能够以高于ε的概率破解某个给定方案的声明引出了一些问题：这是基于什么样的计算能力（例如台式电脑，超级计算机，数百台计算机的网络）得出的结论？这是否考虑了预期的未来计算能力的提高（根据摩尔定律，每18个月大约增加一倍）？这个估计是否假定使用“现成的”算法，或者专门为攻击优化的专用硬件？此外，这样的保证对于运行2年的攻击者的成功概率（除了它不能超过ε之外）说得很少，对于运行10年的攻击者的成功概率则根本没有提到。

3.1.2 渐进方法

如上所述，使用具体安全性方法存在一些技术和理论上的困难。在实践中必须处理这些问题，但在抽象地描述方案时（就像本书所做的那样），使用渐近方法更为方便。这种方法根植于复杂性理论，引入一个整数值的安全参数（表示为n），该参数对加密方案以及所有涉及的各方（即诚实的各方和攻击者）进行参数化。当诚实方使用方案（例如生成密钥）时，他们选择一些安全参数的值；为了本讨论的目的，可以将安全参数视为与密钥长度相对应。我们还将攻击者的运行时间以及其成功概率视为安全参数的函数，而不是固定的具体值。然后：

1. 我们将“有效攻击者”与在n次多项式时间内运行的随机（即概率性）算法等同起来。这意味着存在某个多项式p，使得当安全参数为n时，攻击者的运行时间不超过p(n)。我们还要求——为了实现现实世界的效率——诚实方在多项式时间内运行，尽管我们强调攻击者可能比诚实方更强大（并且运行时间更长）。

2. 我们将“成功概率很小”的概念等同于成功概率小于任何n的倒数的多项式。这样的概率被称为可忽略的。（见定义3.4）

让ppt表示“概率多项式时间”。因此，渐近安全性的定义具有以下一般形式：如果任何ppt攻击者在最多可忽略的概率内破解方案，则该方案是安全的。

这种安全性概念是渐近的，因为它取决于方案在足够大的n值下的行为。以下示例说明了这一点。

Example 3.2

我们假设有一个渐近安全的加密方案，并且假设攻击者可以在 $n^3$ 分钟内以概率 $240/2^n$ 破解该方案。下面我们来解释一下为什么这些数值对应的含义是什么。

我们知道，渐近安全性是一个关于安全参数 $n$ 的概念。在这里，我们可以将 $n$ 看作是密钥长度的一种度量，因为安全参数会影响加密方案的安全性。同时，攻击者的运行时间和成功概率也都是关于安全参数 $n$ 的函数。

在这个例子中，攻击者的运行时间是 $n^3$ 分钟（多项式时间），而成功破解方案的概率是 $240/2^n$。这个概率是一个随着 $n$ 的增加而迅速减小的函数，因为 $2^n$ 增长得非常快，而 $240$ 是一个固定的常数。

例如，当 $n=40$ 时，$2^n=2^{40}$ 大约等于 ${10}^{12}$，因此破解方案的概率约为 $240/{10}^{12}$，这个概率非常小，但对于一个运行时间为 $403$ 分钟的攻击者来说，它已经足够大了，以至于攻击者可以以概率 $1$ 破解方案。同样地，当 $n=50$ 时，$2^n=2^{50}$ 大约等于 ${10}^{15}$，因此破解方案的概率约为 $240/{10}^{15}$，这个概率仍然非常小，但对于一个运行时间为 $503$ 分钟的攻击者来说，它已经足够大了，以至于攻击者可以以概率约为 $1/1000$ 破解方案。但是，当 $n$ 变得更大时，破解方案的概率将迅速减小。例如，当 $n=500$ 时，$2^n$ 大约等于 ${10}^{150}$，因此破解方案的概率约为 $240/{10}^{150}$，这个概率非常非常小，以至于一个运行时间为 $200$ 年的攻击者也只有约 $2^{-500}$ 的概率才能破解方案。这个概率可以被认为是安全的，因为它非常接近于 $0$。

正如前面的例子所示，我们可以将安全参数视为一种机制，使诚实方能够将方案的安全性“调整”到所需的水平。（增加安全参数也会增加运行方案所需的时间以及密钥长度，因此诚实方将希望尽可能地将安全参数设置得小，同时又能够抵御他们所关心的攻击类型。）将安全参数视为密钥长度，这对应于穷举搜索攻击所需的时间随着密钥长度的增加而呈指数增长的事实。通过增加安全参数来“增加安全性”的能力具有重要的实际影响，因为它使得诚实方能够抵御计算能力的增加。下面的例子给出了这种影响在实践中可能会如何发挥的一些感性认识。

Example 3.3

让我们看看更快的计算机可用性可能对实际安全性产生的影响。假设我们有一个密码方案，其中诚实方运行 ${10}^6\cdot n^2$ 个周期，并且如果攻击者运行 ${10}^8\cdot n^4$ 个周期，则可以最多以概率 $2^{-\frac{n}{2}}$ 成功“破解”方案。（这些数字旨在使计算更容易，并且不是指任何现有的密码方案。）

假设所有方使用2 GHz的计算机，诚实方设置 $n=80$。然后，诚实方运行 ${10}^6\cdot 6400$ 个周期，或者说运行时间为3.2秒。攻击者运行 ${10}^8\cdot {80}^4$ 个周期，或大约3周的时间，只有以概率 $2^{-40}$ 的成功概率才能破解该方案。

假设出现了8 GHz的计算机，且所有方都进行了升级。诚实方可以将 $n$ 增加到160（需要生成新的密钥），并保持运行时间为3.2秒（即 ${10}^6\cdot {160}^2$ 个周期，速度为 $8\cdot {10}^9$ 次/秒）。与此相比，攻击者现在需要运行超过800万秒，或者超过13周的时间，才能以概率 $2^{-80}$ 成功破解该方案。更快的计算机的影响是使攻击者的攻击变得更加困难。

即使使用渐近方法，也要记住在最终部署密码系统时需要提供具体的安全保证。（毕竟，必须选择某个 $n$ 值，并且了解所提供的安全级别很重要。）然而，正如上面的例子所示，通常可以将渐近安全性声明转换为任何所需的 $n$ 值的具体安全性界限。

渐近方法详细介绍

我们现在更正式地讨论“多项式时间算法”和“可忽略成功概率”的概念。

• 多项式时间算法

一个将自然数映射到非负实数的函数 $f$ 被称为多项式有界（或简称为多项式），如果存在常数 $c$ 使得对于所有 $n$，$f(n)<c\times n^k$，其中 $k$ 是一个固定的正整数。

一个算法 $A$ 被称为多项式时间算法，如果存在一个多项式 $p$，对于每个输入 $x\in \{0,1{\}}^{\ast }$，$A(x)$ 的计算可以在 $p(|x|)$ 步内终止。这里，$|x|$ 表示字符串 $x$ 的长度。我们认为运行时间在安全参数 $n$ 的多项式内的算法是高效的。

• 可忽略成功概率

一个将自然数映射到非负实数的函数 $\epsilon$ 被称为可忽略的，如果对于任何多项式 $p$，存在一个整数 $n_0$，使得对于所有 $n\ge n_0$，都有 $\epsilon (n)<1/p(n)$。

如果一个对手 $A$ 尝试以非可忽略的成功概率破解密码方案，那么对于某个常数 $c$，存在一个整数 $n_0$ 和一个多项式 $p$，使得对于所有 $n\ge n_0$，$A$ 成功破解该方案的概率至少为 $c/p(n)$。如果对手的成功概率不可忽略，则它必须下降得比任何多项式的倒数更慢。

可忽略成功概率的概念之所以重要，是因为它使我们能够量化地描述对手的成功概率，并定义安全性。我们可以说，如果没有运行时间在多项式内且成功概率不可忽略的对手能够破解密码方案，则密码方案是安全的。或者，我们可以说，如果任何多项式时间对手的成功概率是可忽略的，则该方案是安全的。

定义 3.4 一个将自然数映射到非负实数的函数 $f$ 被称为可忽略函数，如果对于任何多项式 $p$，存在一个整数 $N$，使得对于所有 $n>N$，都有 $f(n)<p(\frac{1}{n})$。

上述定义也可以等价地表述为：对于每个多项式 $p$ 和所有足够大的 $n$，都有 $f(n)<p(\frac{1}{n})$。换句话说，对于所有常数 $c$，存在一个整数 $N$，使得对于所有 $n>N$，都有 $f(n)<n^{-c}$。我们通常用 $negl$ 来表示任意可忽略函数。

Example 3.5

函数 $2^{-n}$，$2^{-\sqrt{n}}$ 和 $n^{-\log n}$ 都是可忽略函数。然而，它们以非常不同的速度趋近于零。例如，我们可以查看每个函数小于 $1/n^5$ 的最小 $n$ 值：

1. 解方程 $2^{-n}<n^{-5}$，得到 $n>5\log n$。满足这个不等式的最小整数值 $n>1$ 是 $n=23$。
2. 解方程 $2^{-\sqrt{n}}<n^{-5}$，得到 $n>25{\log }_{2}n$。满足这个不等式的最小整数值 $n>1$ 是 $n\approx 3500$。
3. 解方程 $n^{-\log n}<n^{-5}$，得到 $\log n>5$。满足这个不等式的最小整数值 $n$ 是 $n=33$。

通过上面的计算，你可能会认为 $n^{-\log n}$ 比 $2^{-\sqrt{n}}$ 小。然而，这是不正确的；对于所有 $n>65536$，都有 $2^{-\sqrt{n}}<n^{-\log n}$。尽管如此，这表明对于数百或数千的 $n$ 值，对手的成功概率为 $n^{-\log n}$ 比 $2^{-\sqrt{n}}$ 更好。使用可忽略成功概率的技术优势在于它们遵循某些封闭性质。以下是一个简单的练习。

PROPOSITION 3.6

设 $neg{l}_1$ 和 $neg{l}_2$ 是可忽略函数。则：

1. 函数 $neg{l}_3(n)=neg{l}_1(n)+neg{l}_2(n)$ 是可忽略函数。
2. 对于任何多项式 $p$，函数 $neg{l}_4(n)=p(n)\cdot neg{l}_1(n)$ 是可忽略函数。

上述命题的第二部分意味着，如果某个事件在某个实验中只以可忽略概率发生，那么即使该实验被多项式地重复多次，该事件发生的概率仍然是可忽略的。（这依赖于并集界，参见命题 A.7。）

例如，投掷 $n$ 枚公平硬币都正面朝上的概率是 $2^{-n}$，这是可忽略的。这意味着，即使我们多项式地重复 $n$ 枚硬币的实验多次，这些实验中仍有至少一个结果全部是正面的概率仍然是可忽略的。

上述命题的第二部分的一个推论是，如果一个函数 $g$ 不是可忽略的，则对于任何多项式 $p$，函数 $f(n)\stackrel{\mathrm{def}}{=}g(n)/p(n)$ 也不是可忽略的。

对渐进安全的总结

对渐进安全的总结。任何安全定义由两部分组成：对该方案的“攻破”的定义，和对敌手能力的详细说明。敌手的能力和很多问题(比如，在加密情况下，假设是唯密文攻击，还是选择明文攻击)相关。但是，考虑到敌手的计算能力，从现在开始，将敌手建模成有效的和概率多项式时间的(意味着只有“可行的”攻击策略被考虑)。定义往往被公式化，以至于以可忽略的概率发生攻破不被认为是重要的。因此，任何安全定义的一般框架如下：

如果每个概率多项式时间的敌手A执行某个特定类型的攻击，在这次攻击(成功也被很好地定义过)中，A成功的概率是可忽略的，那么这个方案是安全的。

这样的定义是渐进的，因为对于小的n值，敌手成功的概率很高是有可能的。为了说明更多细节，在上面的陈述中，将使用到上面陈述的对“可忽略”的完全定义：

如果每个概率多项式时间的敌 手A执行某个特 定类型的攻击，对于每个多项式$p(\cdot )$​,存在一个整数N,对于n>N,敌手在这次攻击中成功的概论小于 $1/p(n)$,则这个方案是安全的。

注意， 对n ≤ N时，没有保证。

3.2 定义计算安全的加密

鉴于前一节的背景，我们准备提出一个针对私钥加密的计算安全性定义。首先，我们重新定义私钥加密的语法；这将与第二章介绍的语法基本相同，只是我们现在明确考虑安全参数n。我们还进行了其他两个更改：我们允许解密算法输出错误（例如，如果它接收到无效的密文），并将消息空间设为所有（有限长度）二进制字符串的集合{0，1}∗

定义3.7： 私钥加密方案由三个概率多项式时间算法 $(Gen,Enc,Dec)$ 组成，满足以下条件：

1. 密钥生成算法 $Gen$ 以 $1^n$（即以一进制写成的安全参数）作为输入，并输出密钥 $k$；我们将其写为 $k\leftarrow Gen(1^n)$（强调 $Gen$ 是一个随机化算法）。我们可以假设没有失去一般性，$Gen(1^n)$ 输出的任何密钥 $k$ 都满足 $|k|\ge n$。
2. 加密算法 $Enc$ 以密钥 $k$ 和明文消息 $m\in \{0,1{\}}^{\ast }$ 作为输入，并输出密文 $c$。由于 $Enc$ 可能是随机化的，因此我们将其写为 $c\leftarrow En{c}_k(m)$。
3. 解密算法 $Dec$ 以密钥 $k$ 和密文 $c$ 作为输入，并输出消息 $m\in \{0,1{\}}^{\ast }$ 或错误。我们用符号 $\perp$ 表示通用错误。

对于每个 $n$、$Gen(1^n)$ 输出的每个密钥 $k$ 和每个 $m\in \{0,1{\}}^{\ast }$，都要求 $De{c}_k(En{c}_k(m))=m$。

如果 $(Gen,Enc,Dec)$ 是这样的，即对于 $Gen(1^n)$ 输出的密钥 $k$，算法 $En{c}_k$ 仅对消息 $m\in \{0,1{\}}^{\ell (n)}$ 定义，则我们称 $(Gen,Enc,Dec)$ 是针对长度为 $\ell (n)$ 的消息的固定长度私钥加密方案。

几乎总是，$Gen(1^n)$ 简单地输出一个均匀的 $n$ 位字符串作为密钥。在这种情况下，我们省略 $Gen$ 并将私钥加密方案定义为一对算法 $(Enc,Dec)$。在本书中，我们假设 $Dec$ 在整个过程中都是确定性的，因此写作 $m:=De{c}_k(c)$。

上述定义考虑了无状态方案，其中每次 $Enc$ 的调用都与所有先前的调用无关（$Dec$ 同理）。本章后面，我们将讨论有状态方案，其中各方可能维护本地状态，在每次调用 $Enc$ 和/或 $Dec$ 后更新该状态。除非另有明确说明，我们假设加密方案是无状态的（如上述定义）。

3.2.1 安全的基本定义（EAV安全）

我们首先介绍私钥加密的最基本的计算安全概念：对单个密文攻击的安全性，其中攻击者仅观察单个密文，或等价地，当给定密钥用于加密单个消息时的安全性。我们稍后将考虑更强的安全定义。

EAV安全是指私钥加密方案在单个密文攻击下的计算安全性。在这种攻击场景中，攻击者只能观察单个密文，而不能对多个密文进行比较或选择。EAV安全是私钥加密方案最基本的安全定义之一，它确保攻击者无法从密文中获取任何关于明文的部分信息。

为了定义EAV安全，我们需要考虑两个方面：威胁模型和安全目标。

在威胁模型方面，我们假设存在一个窃听攻击者，它能够观察单个密文，并在多项式时间内运行。这个威胁模型是非常基本的，但它足以涵盖大多数实际情况下的攻击。

在安全目标方面，我们希望私钥加密方案能够保护明文的机密性，即攻击者无法从密文中获取任何关于明文的部分信息。由于攻击者只能观察单个密文，因此我们无法通过比较多个密文来定义安全性。相反，我们需要定义一个等价的安全目标，即不可区分性。

不可区分性是指对于所有多项式时间的攻击者和所有消息，私钥加密方案在给定加密密钥下，攻击者无法在多项式时间内以比随机猜测更好的概率区分加密是由哪个明文生成的。这个安全目标是EAV安全的最基本形式，它确保攻击者无法从单个密文中获取明文的任何信息。

需要注意的是，虽然EAV安全是私钥加密方案的最基本安全定义之一，但它并不足以涵盖所有实际应用场景。在实际应用中，攻击者可能具有更多的能力，例如能够选择明文或观察多个密文。在这些更强的攻击场景下，我们需要使用更强的安全定义来确保私钥加密方案的安全性。

定义的动机。如我们已经讨论过的那样，任何安全定义都由两个不同的组成部分组成：威胁模型（即对攻击者的权力假设）和安全目标（通常通过描述构成方案“破解”的方式来指定）。我们开始我们的定义性处理，考虑最简单的威胁模型，即存在一个窃听攻击者，它观察单个消息的加密。这恰好是我们在上一章中考虑的威胁模型。唯一的区别在于，正如前一节所解释的，我们现在只对受限于多项式时间运行的计算受限攻击者感兴趣。

虽然我们已经对攻击者的能力作了两个假设（即它窃听一个密文，并且它在多项式时间内运行），但我们对攻击者在试图解密它观察到的密文时的策略没有任何假设。这对于获得有意义的安全概念至关重要：定义确保保护免受任何计算受限的窃听者的攻击，无论它使用的算法如何。

正确地定义加密的安全目标并不是轻松的事情，但我们已经在第1.4.1节和上一章中详细讨论了这个问题。因此，我们只是回顾一下定义的背后思想是，攻击者应该无法从密文中获取任何关于明文的部分信息。语义安全的定义（参见第3.2.2节）正是将这个概念明确化的，并且是首个提出计算安全加密定义的定义。语义安全是复杂且难以处理的。幸运的是，有一个等价的定义称为不可区分性，它要简单得多。

不可区分性的定义是基于完美保密的另一种定义，即定义2.6给出的定义。（这进一步证明了不可区分性定义是一个好定义。）回想一下，定义2.6考虑了一个实验$Priv{K}_{A,\Pi }^{eav}$，在其中一个攻击者$A$输出两个消息$m_0$和$m_1$，然后给出一个使用随机生成的密钥加密这些消息之一的加密。定义指出，如果没有攻击者$A$可以确定哪个消息$m_0$，$m_1$被加密的概率与$1/2$不同，那么方案Π是安全的（如果攻击者只是随机猜测，则$A$正确的概率为$1/2$）。

在这里，我们几乎保持$Priv{K}_{A,\Pi }^{eav}$实验完全相同（除了一些技术上的差异），但在定义本身中引入了两个重要的修改：

1. 现在只考虑在多项式时间内运行的攻击者，而定义2.6考虑了甚至具有无限运行时间的攻击者。
2. 我们现在承认攻击者可能以比$1/2$微不足道地更好的概率确定加密的消息。

正如在前一节中广泛讨论的那样，上述放宽构成了计算安全的核心要素。

另一个显著的不同之处是，我们现在通过安全参数n来参数化实验。攻击者A的运行时间和成功概率都被视为n的函数。对于安全参数 $n$，我们用 $Priv{K}_{A,\mathrm{\Pi }(n)}^{eav}$ 表示运行实验，并将攻击者 $A$ 和私钥加密方案 $\mathrm{\Pi }$ 作为输入。用 $\text{Pr}[Priv{K}_{A,\mathrm{\Pi }(n)}^{eav}=1]$ 表示实验输出为 $1$ 的概率（式（3.1））。请注意，对于固定的 $A$ 和 $\mathrm{\Pi }$，式（3.1）中的表达式是 $n$ 的函数。

第二个差异是，我们现在明确要求攻击者输出长度相等的两个消息 $m_0$ 和 $m_1$。（在定义2.6中，如果消息空间 $M$ 只包含某些固定长度的消息，则该要求是隐含的，例如一次性密码加密方案的情况。）这意味着，默认情况下，我们不要求安全的加密方案隐藏明文的长度。我们将在本节末尾重新讨论这一点；请参见练习3.2和3.3。

窃听者存在情况下的不可区分性。 我们现在给出正式的定义，从上面概述的实验开始。该实验定义了一个私钥加密方案 $\mathrm{\Pi }=(\text{Gen},\text{Enc},\text{Dec})$，一个攻击者 $A$，以及一个安全参数 $n$ 的值：

攻击者不可区分性实验 ${\text{PrivK}}_{A,\mathrm{\Pi }}^{eav}(n)$：

1. 攻击者 $A$ 获得输入 $1^n$，并输出一对消息 $m_0$，$m_1$，其中 $|m_0|=|m_1|$。
2. 通过运行 $\text{Gen}(1^n)$ 生成密钥 $k$，并选择一个均匀的比特 $b\in \{0,1\}$。计算密文 $c\leftarrow {\text{Enc}}_k(m_b)$，并将其提供给 $A$。我们将 $c$ 称为挑战密文。
3. $A$ 输出比特 $b^{{}^{\prime }}$。
4. 实验的输出被定义为：如果 $b^{{}^{\prime }}=b$，则为1，否则为 0。如果 ${\text{PrivKeav}}_A^{\mathrm{\Pi }}(n)=1$，则称 $A$ 成功。

$m_0$ 和 $m_1$ 的长度没有限制，只要它们相同即可。（当然，如果 $A$ 在多项式时间内运行，则 $m_0$ 和 $m_1$ 的长度是 $n$ 的多项式。）如果 $\mathrm{\Pi }$ 是一个针对长度为 $\ell (n)$ 的消息的固定长度方案，则上述实验会通过要求 $m_0,m_1\in \{0,1{\}}^{\ell (n)}$ 来进行修改。

攻击者只能窃听的事实是暗含在攻击者仅获得（单个）密文并且没有任何与发送方或接收方的进一步交互中。 （正如我们将在后面看到的那样，允许额外的交互会使攻击者显著更强。）

不可区分性的定义指出，如果没有 PPT 攻击者 $A$ 能够在上述实验中猜测加密的哪个消息的概率显着优于随机猜测（随机猜测的正确概率为 1/2），则加密方案是安全的。

定义 3.8

私钥加密方案 $\mathrm{\Pi }=(\text{Gen},\text{Enc},\text{Dec})$在窃听者存在的情况下具有难以区分的加密，如果对于所有的概率多项式时间的攻击者 $A$，都存在一个可忽略函数 $\text{negl}$，使得对于所有的 $n$，有

$$\text{Pr}[{\text{PrivK}}_{A,\mathrm{\Pi }(n)}^{eav}=1]\le \frac{1}{2}+\text{negl}(n)$$

上述概率是在攻击者 $A$ 使用的随机数和实验中使用的随机数（用于选择密钥和比特 $b$，以及 Enc 使用的任何随机数）上取的。

显然，定义 3.8 比定义 2.6 更弱，后者等价于完美保密性。因此，任何完美保密的加密方案也具有 EAV 安全性。我们的目标是展示存在满足定义 3.8 的加密方案，可以规避完美保密性的限制，尤其是密钥长度小于消息长度的限制。（注意，如果方案可以处理任意长度的消息，则必须这样做。）也就是说，我们将展示满足定义 3.8 但无法满足定义 2.6 的方案。

等价表述：定义 3.8 要求没有 PPT 攻击者能够确定哪个消息是使用更好的概率加密的两个消息之一。同等表述是，每个 PPT 攻击者在观察到 $m_0$ 或 $m_1$ 的加密时表现相同。由于攻击者 $A$ 输出比特，因此“表现相同”意味着它在每种情况下输出 1 的概率几乎相同。为了明确这一点，定义 ${\text{PrivK}}_{A,\mathrm{\Pi }}^{eav}(n,b)$ 与上述相同，只是使用固定比特 $b\in \{0,1\}$（而不是随机选择）。令 ${\text{out}}_A({\text{PrivK}}_{A,\mathrm{\Pi }}^{eav}(n,b))$ 表示在这个实验中 $A$ 的输出比特 $b_0$。下面陈述了 $A$ 的输出分布在其是否在实验 ${\text{PrivK}}_{A,\mathrm{\Pi }}^{eav}(n,0)$ 或实验 ${\text{PrivK}}_{A,\mathrm{\Pi }}^{eav}(n,1)$ 中运行时不会受到显著影响。

定义 3.9

私钥加密方案 $\mathrm{\Pi }=(\text{Gen},\text{Enc},\text{Dec})$在窃听者存在的情况下具有难以区分的加密，如果对于所有的 PPT 攻击者 $A$，都存在一个可忽略函数 $\text{negl}$，使得

$$|\text{Pr}[{\text{out}}_A({\text{PrivK}}_{A^{,}Pi}^{eav}(n,0))=1]-\text{Pr}[{\text{out}}_A({\text{PrivK}}_{A^{,}Pi}^{eav}(n,1))=1]|\le \text{negl}(n)$$

事实上，定义 3.9 等价于定义 3.8，这里不再赘述。

关于披露明文长度

安全加密的默认概念并不要求加密方案隐藏明文长度，事实上，所有常用的加密方案都会揭示明文长度（或其近似值）。

这主要原因是，要支持任意长度的消息，同时隐藏有关明文长度的所有信息是不可能的。这是因为加密过程通常涉及将明文填充到固定块大小，这意味着明文长度通过密文长度隐含地被揭示。此外，加密过程可能会向密文中添加元数据，揭示有关明文长度或其他属性的信息。

在许多情况下，明文长度已经是公开的或不敏感的，因此揭示它不会构成安全风险。然而，在某些情况下，泄漏明文长度可能会有问题。例如，如果明文包含个人或财务数据等敏感信息，则揭示明文长度可能会为攻击者提供有价值的信息，从而使攻击变得更加有效。同样，在某些加密协议中，例如用于安全消息传递或数据传输的协议中，揭示明文长度可能会危及通信的机密性或完整性。

因此，了解明文长度的披露问题并采取措施减轻它是非常重要的。这可能包括在加密之前将所有消息填充到预定长度，或使用提供一定程度的明文长度隐藏的加密方案，例如基于格式保留加密或随机填充的加密方案。

3.2.2 *语义安全

在密码学中，语义安全性（Semantic Security）是指加密算法应该能够保证在密文泄露的情况下，仍能够保护明文的机密性。具体来说，如果一个加密算法是语义安全的，那么攻击者即使知道加密后的密文，仍然不能够推断出原始的明文或有用的信息。

语义安全性是对加密算法安全性的一种强要求，它反映了加密算法的难以破解程度。如果一个加密算法不是语义安全的，那么攻击者可能通过分析密文来获得有用的信息，从而破译加密算法。

通常，一个加密算法被认为是语义安全的，当且仅当它满足选择明文攻击（chosen-plaintext attack，CPA）的安全性。在选择明文攻击中，攻击者可以选择任意的明文对，将它们加密并获取相应的密文。通过对这些密文和明文对进行分析，攻击者可以尝试推断出加密算法的密钥。

为了满足语义安全性，加密算法通常采用随机化的方式来使每个明文对应的密文都是随机的，并且在明文和密文之间没有任何可预测的关系。这样可以使得攻击者无法通过密文推断出明文或密钥。常见的语义安全的加密算法包括对称加密算法中的AES、DES、以及公钥加密算法中的RSA、ECC等。

定义

考虑一个加密方案 $(Gen,Enc,Dec)$，其中

• $Gen$ 是密钥生成算法
• $Enc$ 是加密算法
• $Dec$ 是解密算法

对于任意的概率多项式时间（probabilistic polynomial-time）算法 $A$ 和任意的概率多项式时间可分辨器（distinguisher） $D$，我们有：

$$|Pr[D(A(pk),\text{Enc}(pk,m_0))=1]-Pr[D(A(pk),\text{Enc}(pk,m_1))=1]|\le \text{negl}(n)$$

其中，

• $n$ 是安全参数
• $\text{negl}(n)$ 是一个忽略不计的函数，表示随着安全参数 $n$ 的增长，这个值会趋向于 0
• $(pk,sk)\leftarrow Gen(1^n)$ 表示根据安全参数 $n$ 生成的公钥-私钥对
• $m_0$ 和 $m_1$ 是任意两个相同长度的明文
• $Pr[\cdot ]$ 表示概率

上述定义表明，对于语义安全的加密方案，攻击者在多项式时间内无法有效地区分两个密文对应的明文。

例子

一个典型的语义安全的加密方案是概率性非对称加密方案，例如ElGamal加密。ElGamal 加密具有以下性质，使其满足语义安全性：

1. 加密是概率性的，即对于相同的明文和公钥，加密过程会产生不同的密文。
2. 密文空间比明文空间大，即密文的数量大于明文的数量。

这些性质保证了攻击者无法通过简单地观察密文来推测明文，从而实现语义安全。

总结

语义安全是密码学中的一种重要安全性定义。在语义安全的加密方案中，攻击者不能从密文中获取关于明文的任何有意义的信息。这种安全性使得加密方案在现实应用中具有更高的安全性。

3.3构建一个EAV-安全加密方案

在定义了加密方案的安全性之后，读者可能期望我们立即转向安全加密方案的构建。然而，在此之前，我们需要介绍伪随机生成器（Pseudorandom Generators，PRGs）的概念，它是私钥加密的重要构建块。这将进一步引出关于伪随机性的讨论，它在密码学中发挥着基础性的作用，特别是在私钥加密中。

3.3.1伪随机生成器

伪随机生成器（Pseudorandom Generators，PRGs）是密码学中的一种重要工具，它们允许我们使用看起来随机的比特串来代替真正的随机比特串，从而简化了密码学协议的设计和实现。

PRGs接受一个随机的种子作为输入，并产生一个看起来随机的比特串作为输出。PRGs的输出并不是真正的随机比特串，而是伪随机的。伪随机性指的是输出看起来随机，但实际上是由一个确定性算法生成的，而不是真正的随机比特串。

一个好的PRG应该满足以下几个条件：

1. 均匀性（Uniformity）：PRG的输出应该看起来是随机的，即输出的比特串应该足够均匀地分布在所有可能的比特串中。

2. 可预测性（Predictability）：PRG的输出应该只能在已知种子的情况下被预测，而对于没有种子的情况下，它应该是不可预测的。

3. 不可区分性（Indistinguishability）：PRG的输出应该与真正的随机比特串难以区分，即攻击者不能够在多项式时间内区分PRG的输出与真正随机比特串的输出。

PRGs通常被用于生成加密密钥，例如将一个随机的种子作为输入，并使用PRG生成一个更长的随机比特串作为密钥。这样做的好处是，由于PRG的输出看起来随机，攻击者很难通过分析密文来推断出密钥的值。

PRGs在密码学中发挥着重要的作用，因为它们允许我们使用看起来随机的比特串来代替真正的随机比特串，从而简化了密码学协议的设计和实现。在私钥加密中，PRG是实现语义安全的重要工具，而在公钥加密和消息认证码中，伪随机函数（Pseudorandom Function，PRF）则是实现安全协议的重要工具。

3.3.2规约证明

规约证明（Proofs by Reduction）是密码学中一种常用的证明技术，用于证明一个安全性问题与另一个已知的安全性问题等价。规约证明是密码学中证明安全性的重要工具之一。

如果我们希望证明某个构造（例如加密方案）在计算上是安全的，除非该方案在信息论上是安全的，否则我们必须依赖未经证明的假设。我们的策略是假设某个数学问题很难，或者某个低级密码学原语是安全的，然后证明基于该问题/原语的给定构造在我们的初始假设正确的情况下是安全的。在1.4.2节中，我们已经详细解释了这种方法的优点，因此我们不在此重复这些论点。

通常情况下，证明某个密码构造 $\mathrm{\Pi }$ 是安全的，只要某个基础问题 $X$ 是困难的，我们需要通过提供一个显式的规约来证明，该规约说明如何将任何成功“破解” $\mathrm{\Pi }$ 的有效攻击者 $A$ 转化为一个有效算法 $A^{{}^{\prime }}$，该算法 $A^{{}^{\prime }}$ 可以解决 $X$。由于这一点非常重要，因此我们详细介绍此类证明的步骤（我们将在本书中看到许多具体的例子，包括下一节中的定理 3.16 的证明）。我们从假设一些问题 $X$ 不能被任何多项式时间算法解决（在某种精确定义的意义下），除非概率可以忽略不计。然后，我们想证明某个密码构造 $\mathrm{\Pi }$ 是安全的（再次在精确定义的意义下）。规约证明通过以下步骤进行（也可以参见图 3.1）：

1. 固定某个攻击 $\mathrm{\Pi }$ 的有效（即概率多项式时间）攻击者 $A$。用 $ϵ(n)$ 表示攻击者的成功概率。

2. 构造一种有效的算法 $A^{{}^{\prime }}$，该算法尝试使用攻击者 $A$ 作为子例程来解决问题 $X$。这里的重要一点是，$A^{{}^{\prime }}$ 对 $A$ 的工作方式一无所知；$A^{{}^{\prime }}$ 只知道 $A$ 期望攻击 $\mathrm{\Pi }$。因此，给定问题 $X$ 的某个输入实例 $x$，我们的算法 $A^{{}^{\prime }}$ 将为 $A$ 模拟一个 $\mathrm{\Pi }$ 实例，以便：

   (a) 就 $A$ 而言，它正在与 $\mathrm{\Pi }$ 交互。也就是说，在 $A^{{}^{\prime }}$ 作为 $A$ 的子例程运行时，$A$ 的视图应该与其与 $\mathrm{\Pi }$ 本身交互时的视图完全相同（或至少接近）。

   (b) 当 $A$ 成功“破解”由 $A^{{}^{\prime }}$ 模拟的 $\mathrm{\Pi }$ 实例时，这应该允许 $A^{{}^{\prime }}$ 解决它所给出的实例 $x$，至少具有倒数多项式概率 $1/p(n)$。也就是说，我们试图将解决 $X$ 的问题归约为破解 $\mathrm{\Pi }$ 的问题。

3. 综合以上所述，我们有 $A^{{}^{\prime }}$ 具有概率 $ϵ(n)/p(n)$ 解决 $X$。现在，如果 $ϵ(n)$ 不是可以忽略不计的，那么 $ϵ(n)/p(n)$ 也不是可以忽略不计的。此外，如果 $A$ 是有效的，则我们得到一个有效算法 $A^{{}^{\prime }}$ 以非可忽略概率解决 $X$，这与我们的初始假设相矛盾。

4. 鉴于我们关于 $X$ 的假设，我们得出结论：没有有效的攻击者 $A$ 能够以非可忽略的概率破解 $\mathrm{\Pi }$。换句话说，$\mathrm{\Pi }$ 是计算上安全的。

作为上述思路的说明，本文节选了一个例子，展示了如何使用伪随机生成器 $G$ 构造加密方案，并通过展示任何能够“破解”加密方案的攻击者都可以用来区分 $G$ 的输出和均匀字符串。在假设 $G$ 是伪随机生成器的前提下，该加密方案是安全的。

总体而言，本文阐述了在密码学中证明计算安全性的规约技术的重要性，并提供了规约证明方法的高级概述。

3.3.3

假设我们有一个可伪随机生成器 $G$，并且想要使用它来构建一个加密方案。我们可以考虑使用一个简单的方案，称为 EAV（Encrypt-Add-Verify）方案。

具体来说，假设我们有一个明文集合 $\mathcal{M}$，一个密钥集合 $\mathcal{K}$，一个加密算法 $E:\mathcal{K}\times \mathcal{M}\to \{0,1{\}}^n$，一个解密算法 $D:\mathcal{K}\times \{0,1{\}}^n\to \mathcal{M}$，以及一个伪随机生成器 $G:\{0,1{\}}^s\to \{0,1{\}}^n$。我们定义 EAV 方案如下：

加密：给定一个密钥 $k\in \mathcal{K}$ 和一个明文 $m\in \mathcal{M}$，我们生成一个随机值 $r\in \{0,1{\}}^s$，并计算 $E(k,m)=G(r)\oplus m$。我们将 $E(k,m)$ 作为密文输出，同时保留 $r$ 作为加密的辅助信息。

解密：给定一个密钥 $k\in \mathcal{K}$ 和一个密文 $c\in \{0,1{\}}^n$，我们将 $c$ 分解为 $c=G(r)\oplus m$ 的形式，其中 $r$ 是加密时生成的随机值。如果 $G(r)$ 是伪随机的，那么 $m$ 也应该是随机的，因此我们可以安全地将 $m$ 作为明文输出。

这个方案的正确性可以通过简单的代数运算得到：

$$D(k,E(k,m))=D(k,G(r)\oplus m)=G(r)\oplus (G(r)\oplus m)=m$$

因此，解密算法可以正确地恢复出明文。

我们现在考虑该方案的安全性。假设存在一个攻击者 $A$，可以通过观察多个密文来确定 $G$ 的输出是否真正是随机的。我们将展示如何使用 $A$ 来构建一个区分器，该区分器可以用来检测 $G$ 是否是伪随机的。

具体来说，我们构造一个区分器 $B$，该区分器随机选择一个比特 $b\in \{0,1\}$，并随机生成一个长度为 $n$ 的比特串 $y$。然后，$B$ 模拟 EAV 方案的加密过程，生成一个随机值 $r\in \{0,1{\}}^s$，并计算 $c=G(r)\oplus y$. 接下来，$B$ 将 $c$ 提交给 $A$，并获得 $A$ 的输出 $b^{\prime }\in \{0,1\}$。

最后，$B$ 输出 $1$ 当且仅当 $b^{\prime }=b$。我们注意到，$B$ 的成功概率为 $1/2$，而如果 $G$ 是真正的伪随机生成器，则 $B$ 的成功概率应该非常接近 $1/2$。另一方面，如果 $G$ 不是伪随机的，则 $B$ 的成功概率应该接近 $1$。

因此，我们得到了一个区分器 $B$，它可以用来检测 $G$ 是否是伪随机的。这与我们对 $G$ 的假设相矛盾，因此我们可以得出结论：如果 $G$ 是伪随机生成器，则 EAV 方案是安全的。

总结一下，我们可以使用伪随机生成器 $G$ 来构建一个简单的加密方案，该方案在假设 $G$ 是伪随机的前提下是安全的。这种方式可以用来构建许多其他的密码学方案，例如对称加密、消息认证码等等。这种构造方法的优点是简单易实现，同时能够利用已有的密码学工具来证明安全性。然而，需要注意的是，这种构造方法依赖于强大的伪随机生成器，如果生成器不足够强，则可能会导致方案不安全。因此，在实际应用中需要选择安全的伪随机生成器，并且进行充分的安全性分析。

3.3.3从伪随机生成器实现EAV安全性

一个伪随机生成器提供了一种构建安全的固定长度加密方案的自然方法，其密钥比消息短。回想一次性密码本（见2.2节），加密是通过将随机密码本与消息进行异或运算来完成的。关键的洞察是，我们可以使用伪随机密码本。然而，发送方和接收方可以共享一个均匀种子，该种子在需要时用于生成密码本（参见图3.2）；这个种子将比密码本短，因此比消息短。至于安全性，直觉是伪随机字符串“看起来随机”，任何多项式时间敌手都无法区分使用一次性密码本加密的消息和使用“伪一次性”密码本加密方案加密的消息。

加密方案。令G是一个扩展因子为$\ell$的伪随机发生器$(\text{即}|G(s)|=|\ell (|s|)|)$。回想一个加密方案被三个算法定义：一个密钥生成算法Gen,一个加密算法Enc以及一个解密算法Dec。加密过程是，密钥(作为一个种子)应用到一个伪随机发生器来获得一个长的填充，然后和明文消息作异或处理。该方案在构造方法3.15中正式地描述，如图3.2所示。

这个证明是使用反证法来证明的。我们首先假设 $G$ 是一个伪随机生成器，并且EAV方案是不安全的，即存在一个多项式时间的攻击者可以在不知道加密密钥的情况下构造出一个有效的密文和认证标签对。

接下来，我们将使用这个假设构建一个区分器 $B$，来检测 $G$ 是否真的是伪随机生成器。我们定义 $B$ 的行为如下：

• 选择一个随机的二进制字符串 $k$，长度为 $n$，作为 $G$ 的密钥。
• 根据密钥 $k$ 使用 $G$ 生成一个随机的二进制串 $r$，长度为 $n$。
• 选择两个随机的消息 $m_0$ 和 $m_1$，长度相同，并给 $B$ 一个比特 $b$。
• 如果 $b=0$，则定义 $c=G(k)\oplus m_0$，否则定义 $c=r\oplus m_1$。
• 计算 $t=S(k,c)$，其中 $S$ 是一个固定长度的MAC或数字签名算法。
• 将密文 $c$ 和认证标签 $t$ 提供给攻击者，让攻击者进行区分。

攻击者的目标是确定 $B$ 选择的是哪个消息 $m_b$，并输出 $b$。如果攻击者可以在多项式时间内区分 $m_0$ 和 $m_1$，那么我们可以说 $G$ 不是一个伪随机生成器。

现在我们分两种情况来讨论：

1. 如果攻击者使用 $G$ 生成的密码本来计算 $c$ 和 $t$，则 $c=G(k)\oplus m_0$ 或 $c=G(k)\oplus m_1$。由于 $k$ 是随机选择的，因此 $G(k)$ 本身应该是随机的。如果 $G$ 是一个伪随机生成器，则 $G(k)$ 应该看起来像是真正的随机数。因此，攻击者无法区分 $c$ 是由真正的随机数还是由 $G(k)$ 生成的伪随机数得到的。此外，认证标签 $t$ 是使用密钥 $k$ 和密文 $c$ 计算的，因此攻击者无法在不知道 $k$ 的情况下计算出正确的认证标签 $t$。因此，攻击者无法在多项式时间内对 $B$ 区分 $m_0$ 和 $m_1$，即攻击者无法成功地区分 $G$ 和真正的随机生成器。

2. 如果攻击者使用 $r$ 生成的密码本来计算 $c$ 和 $t$，则 $c=r\oplus m_1$。由于 $r$ 是随机选择的，并且 $m_0$ 和 $m_1$ 是随机选择的，因此 $c$ 也应该看起来像是真正的随机数。因此，攻击者无法区分 $c$ 是由真正的随机数还是由 $r$ 生成的伪随机数得到的。认证标签 $t$ 是使用密钥 $k$ 和密文 $c$ 计算的，但攻击者不知道 $k$。因此，攻击者无法计算出正确的认证标签 $t$。因此，攻击者也无法在多项式时间内对 $B$ 区分 $m_0$ 和 $m_1$，即攻击者无法成功地区分 $G$ 和真正的随机生成器。

因此，我们可以得出结论：如果 $G$ 是一个伪随机生成器，则 EAV 方案是安全的。如果存在一个多项式时间的攻击者能够在不知道加密密钥的情况下构造出一个有效的密文和认证标签对，那么这个攻击者也可以被用来构建一个区分器 $B$，从而与我们对 $G$ 的假设相矛盾。因此，我们可以相信在使用一个足够强的伪随机生成器时，EAV方案是安全的。

这个证明的关键点在于，我们使用反证法来证明 $G$ 是伪随机生成器时，EAV方案是安全的。我们假设存在一个攻击者可以在多项式时间内构造出有效的密文和认证标签对，然后根据这个假设构建一个区分器 $B$ 来检测 $G$ 是否真的是伪随机生成器。如果 $B$ 的输出是 $0$，那么这意味着我们已经找到了一个区分 $G$ 和真正的随机生成器的方法，这与我们对 $G$ 的假设相矛盾。因此，我们可以得出结论：如果 $G$ 是一个伪随机生成器，则 EAV 方案是安全的。

3.4更强的安全概念

到目前为止，我们一直在考虑一个相对较弱的安全定义，即对手只被动地窃听诚实当事人之间发送的单个密文。这里我们考虑更强的安全概念。

3.4.1针对多次加密的安全性

定义3.8处理了通信双方传输单个密文并被窃听者观察的情况。然而，如果通信双方可以安全地互相发送多个密文——所有这些密文都使用相同的密钥生成——即使窃听者可能观察到所有这些密文，这将非常方便。对于这样的应用程序我们需要一种加密方案，用于加密多个消息的安全性。

我们首先为此设置引入适当的安全性定义。与定义3.8的情况类似，我们首先为任何加密方案 $\mathrm{\Pi }$，对手 $A$ 和安全参数 $n$ 定义一个适当的实验：

多消息窃听实验 ${\text{PrivK}}_{\text{mult}}^{A,\mathrm{\Pi }}(n)$：

1. 对手 $A$ 被赋予输入 $1^n$，并输出两个等长的消息列表 ${\mathbf{M}}_0=(m_{0,1},\dots ,m_{0,t})$ 和 ${\mathbf{M}}_1=(m_{1,1},\dots ,m_{1,t})$，其中对于所有 $i$，$|m_{0,i}|=|m_{1,i}|$。

2. 通过运行 $\text{Gen}(1^n)$ 生成密钥 $k$，并选择一个均匀比特 $b\in \{0,1\}$。对于所有 $i$，计算密文 $c_i\leftarrow {\text{Enc}}_k(m_{b,i})$，并将列表 $\mathbf{C}=(c_1,\dots ,c_t)$ 交给 $A$。

3. 对手 $A$ 输出一个比特 $b^{\prime }$。

4. 如果 $b^{\prime }=b$，则实验的输出定义为 $1$，否则为 $0$。

与之前的安全性定义相同，但现在它指的是上述实验。

定义3.18 如果私钥加密方案 $\mathrm{\Pi }=(\text{Gen},\text{Enc},\text{Dec})$ 在窃听者存在的情况下拥有不可区分的多个加密，则对于所有概率多项式时间对手 $A$，存在可忽略函数 $\text{negl}$，使得

$$\text{Pr}[{\text{PrivK}}_{\text{mult}}^{A,\mathrm{\Pi }}(n)=1]\le \frac{1}{2}+\text{negl}(n)$$

在窃听者存在的情况下拥有不可区分的多个加密的任何方案显然也满足定义3.8，因为实验 ${\text{PrivK}}_{\text{eav}}^{A,\mathrm{\Pi }}(n)$ 对应于实验 ${\text{PrivK}}_{\text{mult}}^{A,\mathrm{\Pi }}(n)$ 的特殊情况，其中对手输出仅包含单个消息的两个列表。实际上，我们的新定义比定义3.8严格更强，如下所示。

命题3.19 存在一种私钥加密方案，在窃听者存在的情况下具有不可区分的加密，但在窃听者存在的情况下不存在不可区分的多个加密。
证明：我们不需要观察就能找到满足该命题的加密方案的例子。一次一密（one-time pad）是完全保密的，因此在窃听者存在的情况下也具有不可区分的加密。我们将证明它在定义3.18的意义下不是安全的。（我们已经在第2章中讨论过这种攻击；这里我们只是根据定义3.18分析攻击。）

概率性加密的必要性。上面的内容可能表明，使用任何加密方案都无法实现定义3.18。只要加密方案是（无状态的且）确定性的，因此使用相同的密钥多次加密相同的消息总是产生相同的结果，这就是真实情况。这一点重要到足以陈述为一个定理。

定理3.20 如果 $\mathrm{\Pi }$ 是一个加密方案，在其中 $\text{Enc}$ 是密钥和消息的确定性函数，则在窃听者存在的情况下，$\mathrm{\Pi }$ 不能具有不可区分的多个加密。
这不应被解释为定义3.18太强了。事实上，向窃听者泄露两个加密消息相同的事实可能会造成重大安全漏洞。（例如，考虑加密一系列是/否回答的场景！）

为了构建一个安全的用于加密多个消息的方案，我们必须设计一个随机化的加密方案，这样当同一消息被加密多次时，可以产生不同的密文。这可能看起来是不可能的，因为解密必须始终能够恢复消息。然而，我们很快将看到如何实现它。
虽然实现多个消息的加密的安全性很重要，但我们并不会广泛地考虑定义3.18本身，而是专注于我们在下一节中介绍的更强的定义。

3.4.2 选择明文攻击和CPA安全

选择明文攻击捕获了攻击者在加密过程中（部分）控制诚实方加密内容的能力。想象一个场景，其中两个诚实方共享一个密钥 $k$，攻击者可以影响这些方加密消息 $m_1,m_2,...$（使用 $k$），并将结果的密文发送到攻击者可以观察的信道上。在某个时间点后，攻击者观察到一个密文，对应于使用相同密钥 $k$ 加密的某个未知消息 $m$；让我们甚至假设攻击者知道 $m$ 是两个可能性 $m_0,m_1$ 中的一个。选择明文攻击安全意味着即使在这种情况下，攻击者也不能比随机猜测更好地确定哪个消息被加密了。（现在我们回到窃听者只给出一个未知消息的加密的情况。不久，我们将回到考虑多个消息的情况。）

==安全性的定义要求:即使敌手具备访问加密预言机能力，敌手也不能区分两个任意消息的加密==。这里先提出定义，然后将讨论该定义模拟真实世界的什么攻击。

现实世界中的选择明文攻击。选择明文攻击是一个现实可行的问题吗？首先，注意到选择明文攻击也包括已知明文攻击——攻击者知道加密的某些消息，即使它不能选择它们——作为一种特殊情况。此外，有几个现实世界的场景中，攻击者可能会对哪些消息被加密具有重大影响。一个简单的例子是攻击者在终端上输入，然后使用与远程服务器共享的密钥（对攻击者未知）加密攻击者输入的所有内容。在这里，攻击者完全控制了被加密的内容，当使用相同的密钥加密其他用户输入的数据时，加密方案仍应该不泄漏任何信息。

有趣的是，选择明文攻击也曾被成功地用于突破军事加密方案。例如，在第二次世界大战期间，英国在某些位置放置了地雷，知道德国人——当发现那些地雷时——会加密这些位置并将它们送回总部。Bletchley Park的密码分析员使用这些加密消息来破解德国的加密方案。还有一个例子是著名的中途岛战役。1942年5月，美国海军密码分析员拦截到一条来自日本的加密消息，他们能够部分解码。结果表明，日本计划袭击“AF”，其中“AF”是美国无法解码的密文片段。由于其他原因，美国认为中途岛是目标。不幸的是，他们试图说服华盛顿的规划者这是事实的尝试是徒劳无益的。海军密码分析员制定了以下计划：他们指示在中途岛的美军发送一条假消息，声称他们的淡水供应不足。日本人截获了这条消息，并立即向他们的上级发送了一条加密消息，称“AF缺水”。海军密码分析员现在有了证据，证实“AF”对应于中途岛，美国派出了三艘航空母舰前往该位置。结果是中途岛得救了，而日本遭受了重大损失。这场战斗是美国和日本在太平洋之间的战争的转折点。
在这里，海军密码分析员进行了选择明文攻击，因为他们能够影响日本人（虽然是迂回的方式）加密“中途岛”这个词。如果日本的加密方案对选择明文攻击是安全的，美国密码分析员的这种策略就不会奏效（历史可能会有很大不同）！

CPA-Security。在正式定义中，我们通过给攻击者 A 访问一个加密 oracle 来对选择明文攻击进行建模，将其视为加密 A 选择的消息的“黑盒”，使用未知于 A 的密钥 k 加密。也就是说，我们想象 A 有一个“oracle” $En{c}_k(\cdot )$ 的访问权限；当 A 通过提供消息 m 作为输入查询该 oracle 时，oracle 作为回复返回密文 $c\leftarrow En{c}_k(m)$。（如果 Enc 是随机的，则 oracle 每次回答查询时都会使用新的随机数。）攻击者可以与加密 oracle 适应性地交互，任意次数地查询。

考虑以下对于任何加密方案 $\mathrm{\Pi }=(Gen,Enc,Dec)$、攻击者 A 和值 n 的实验定义：
选择明文攻击下的 CPA 不可区分性实验 $Priv{K}_{A,\mathrm{\Pi }}^{cpa}(n)$：

1. 运行 $Gen(1^n)$ 生成密钥 $k$。
2. 攻击者 A 获得输入 $1^n$ 和访问 $En{c}_k(\cdot )$ 的 oracle，并输出一对相同长度的消息 $m_0,m_1$。
3. 选择均匀的比特 $b\in \{0,1\}$，计算密文 $c\leftarrow En{c}_k(m_b)$，并将其提供给 A,c称为挑战密文。
4. 攻击者 A 继续对 $En{c}_k(\cdot )$ 有 oracle 访问权限，并输出一个比特 $b^{{}^{\prime }}$。
5. 实验的输出被定义为当 $b^{{}^{\prime }}=b$ 时为 1，否则为 0。在前一种情况下，我们称 A 成功。

定义 3.21：私钥加密方案 $\mathrm{\Pi }=(Gen,Enc,Dec)$ 具有在选择明文攻击下的不可区分加密或是 CPA-安全的，如果对于所有概率多项式时间攻击者 A，都存在一个可以忽略的函数 $negl$，使得

$$Pr[Priv{K}_{A,\mathrm{\Pi }}^{cpa}(n)=1]\le \frac{1}{2}+negl(n)$$

其中概率取决于 A 使用的随机性，以及实验中使用的随机性。

现在，CPA-安全性是加密方案应满足的最低安全性要求，尽管现在越来越常见的是要求更强的安全性概念，我们将在第 5 章中讨论。

3.4.3 用于多次加密的 CPA 安全性

可以使用明文列表将 Definition 3.21 扩展到多次加密的情况，类似于 Definition 3.8 的方式。然而，这里我们使用一种略微不同的方法，具有攻击者可以自适应地选择要加密的密文对的优势。具体而言，我们现在给攻击者访问“左侧或右侧”oracle LR_k,b，对于相等长度的消息$ m_0$ 和 $m_1$，计算密文$ c ← Enc_k(m_b)$，并返回 c。换句话说，如果 b = 0，则攻击者总是接收“左侧”明文的加密，如果 b = 1，则总是接收“右侧”明文的加密。比特 b 是在实验开始时选择的均匀比特。攻击者的目标是猜测 b。

考虑任何加密方案 $\mathrm{\Pi }=(Gen,Enc,Dec)$，攻击者 A 和值 n 的实验定义：

多次加密下的 LR-oracle 实验 $Priv{K}_{A,\mathrm{\Pi }}^{LR-cpa}(n)$：

1. 运行 $Gen(1^n)$ 生成密钥 $k$。
2. 选择均匀的比特 $b\in \{0,1\}$。
3. 攻击者 A 获得输入 $1^n$ 和访问 $L{R}_{k,b}(\cdot ,\cdot )$ 的 oracle，如上所述。
4. 攻击者 A 输出比特 $b^{{}^{\prime }}$。
5. 实验的输出被定义为当 $b^{{}^{\prime }}=b$ 时为 1，否则为 0。在前一种情况下，我们称 A 成功。

定义 3.22：私钥加密方案 $\mathrm{\Pi }=(Gen,Enc,Dec)$ 具有在选择明文攻击下的不可区分多次加密或是多次 CPA-安全的，如果对于所有概率多项式时间攻击者 A，都存在一个可以忽略的函数 $negl$，使得

$$Pr[Priv{K}_{A,\mathrm{\Pi }}^{LR-cpa}(n)=1]\le \frac{1}{2}+negl(n)$$

需要注意的是，给定访问 $L{R}_k,b$ 的攻击者可以模拟访问加密 oracle：要获得消息 m 的加密，攻击者只需查询 $L{R}_{k,b}(m,m)$。根据这个观察结果，可以立即得出，如果 $\mathrm{\Pi }$ 对多次加密具有 CPA 安全性，则它也具有 CPA 安全性。此外，如果 $\mathrm{\Pi }$ 对多次加密具有 CPA 安全性，则在窃听者存在的情况下，它具有不可区分多次加密的安全性。换句话说，定义 3.22 至少与定义 3.18 和 3.21 相同强度。

实际上，多次加密的 CPA 安全性与单次加密的 CPA 安全性等价（与窃听型攻击者的情况相反，参见命题 3.19）。我们在不加证明的情况下陈述以下定理；类似的公钥设置结果在第 12.2.2 节中给出证明。

定理 3.23：任何具有 CPA 安全性的私钥加密方案也具有多次加密下的 CPA 安全性。

因此，只需证明一个方案具有 CPA 安全性（针对单次加密），我们就可以得出它也具有多次加密的 CPA 安全性。

固定长度与任意长度的消息。使用 CPA 安全性的多条消息的概念（或等效地，CPA 安全性），可以不失一般性地处理固定长度加密方案的优点。特别是，对于任何具有 CPA 安全的固定长度加密方案$\mathrm{\Pi }=(Gen,Enc,Dec)$，我们可以将其扩展到任意长度消息的情况下。

具体来说，假设我们要加密长度为 $l$ 的消息 $m=(m_1,m_2,...,m_l)$，其中 $m_i$ 是单个比特。我们可以将消息划分为块 $m_1,m_2,...,m_{l/b}$，其中每个块有 $b$ 个比特，即 $l/b$ 为块的数量。我们可以使用固定长度加密方案 $\mathrm{\Pi }$ 加密每个块，得到密文 $c_1,c_2,...,c_{l/b}$。然后，我们将这些密文连接起来以形成最终密文 $c=c_1||c_2||...||c_{l/b}$。

解密时，我们可以简单地解密每个块并将它们连接起来以重建原始消息。由于 $\mathrm{\Pi }$ 具有 CPA 安全性，因此对于给定的密文，攻击者无法确定原始消息中的任何块，因此也无法确定原始消息。

需要注意的是，在实际应用中，通常使用的是支持任意长度消息的加密方案，而不是仅支持固定长度消息的加密方案。这是因为大多数实际应用程序需要加密的消息都不是固定长度的。

3.6 操作模式和实践中的加密

在3.3.3节和3.5.2节中描述的加密方案（即构造3.17和3.28）具有许多缺点，使它们不适合实际应用。首先，构造3.17仅具有EAV安全性。此外，这两个构造仅针对固定长度消息的加密。虽然可以使用3.28构造通过在3.4.3节末尾讨论的方法加密任意长度的消息，但这将导致密文长度是明文长度的固定倍数，这相当低效。在本节中，我们将展示如何克服这些缺点。
在处理实际考虑因素时，我们还开始讨论安全加密方案的基础构建模块，即伪随机生成器和伪随机置换如何使用流密码和分块密码在现实世界中实现。我们的目标在于介绍适当的术语和语法；我们将深入讨论流密码和分块密码的设计以及这些原语的一些流行候选项，留待第7章讨论。
看大佬总结吧 (opens new window)

3.6.1 流密码

3.6.2 流密码工作模式

3.6.3 分组密码和分组密码工作模式

*3.6.4 基于随机数的加密