目录

3.1 计算安全性 Computational Security

3.1.1 The Concrete Approach 具体方法

3.1.2 The Asymptotic Approach 渐进方法以及渐进安全

Example 3.2

Example 3.3

多项式有界和多项式函数

多项式时间运行 的含义

DEFINITION 3.4 可忽略函数

PROPOSITION 3.6 可忽略函数的性质

渐进安全性的精确定义

放宽限制的必要性 Necessity of the Relaxations

3.1 计算安全性 Computational Security

完善保密性要求关于加密信息的信息绝对不会被泄露，即使是泄露给具有无限计算能力的窃听者。然而，出于实际目的，如果一个加密方案以很小的概率泄露信息给计算能力有限的窃听者，那么它仍然被认为是安全的。

计算安全性相比于完善保密性放松了两个限制：

1. 安全只针对在可行时间内运行的高效敌手。这意味着，如果给定足够的时间（或足够的计算资源），攻击者可能会违反安全性。然而，如果我们能够使破坏方案所需的资源比任何现实攻击者可用的资源更大，那么对于所有实际目的来说，该方案都是牢不可破的。
2. 敌手可以有非常小的概率成功，即在不可区分实验中敌手猜中明文的概率比1/2稍大些。如果我们能使这个概率足够小，我们就不必担心它了。

3.1.1 The Concrete Approach 具体方法

A scheme is (t, ε)-secure if any adversary running for time at most t succeeds in breaking the scheme with probability at most ε.

对于一个方案，如果任何运行时间不超过t的对手，以不超过ε的概率成功地打破了该方案，那么该方案是（t，ε）安全的。

3.1.2 The Asymptotic Approach 渐进方法以及渐进安全

使用具体安全方法存在一些技术和理论上的困难。这些问题必须在实践中加以处理，但当抽象地描述方案时，使用渐近的方法是很方便的。这种方法基于复杂性理论，引入了一个整数安全参数（用n表示），它参数化了加密方案和所有相关方(即通信方和攻击方)。当诚实的各方使用一个方案时（例如，当他们生成一个密钥时），他们会为安全参数选择一些值；为了进行讨论，我们可以查看与密钥长度对应的安全参数。我们还将对手的运行时间以及它的成功概率视为安全参数的函数，而不是固定的具体值

我们将“有效的对手”等同于以n中的时间多项式运行的概率算法。这意味着存在一些多项式p，当安全参数为n时，对手最多运行的时间为p (n)。为了提高现实世界的效率，我们还要求通信方在多项式时间内运行

我们令PPT表示概率多项式时间probabilistic polynomial-time

渐进安全性的定义：

如果任何PPT敌手破解该加密方案的概率是可以忽略不计的，那么该方案就是安全的。

Example 3.2

假设我们有一个渐近安全的方案。敌手运行n^3分钟能够成功破解加密方案的概率为(2^40)/(2^n)

• n = 40:一个运行40^3分钟(约6周)的对手可以破解该方案
• n = 50:一个运行50^3分钟(约3个月)的对手可以以约1/1000的概率破解该方案
• n = 500:一个运行了200多年的对手可以以约2^ -500的概率破解该方案

如上面的示例所示，我们可以将安全参数视为一种机制，它允许诚实的各方将方案的安全性“调优”到某个期望的级别。当然，增加安全参数n还会增加运行方案所需的时间以及密钥的长度，因此诚实的各方将希望将安全参数设置得尽可能小，以抵御他们所关心的各种攻击类别。将安全参数视为密钥长度，这对应于穷举搜索攻击所需的时间在密钥长度上呈指数级增长的事实。

Example 3.3

假设有一个加密方案，通信方需要(10^6)*(n^2)个CPU周期，而敌手需要(10^8)*(n^4)个CPU周期以2^(-n/2)的成功概率破解这个加密方案

• 假设通信方和敌手都使用2GHz的计算机，并且n=80，则通信方运行(10^6)*6400个CPU周期，大约为3.2秒；而敌手破解这个加密方案则需要(10^8)*(80^4)个CPU周期，大约为3个星期，而成功破解的概率为2^(-40)。
• 假设通信方和敌手都是用8GHz的计算机，并且n=160，则通信方运行时间仍然为3.2秒；而敌手破解这个加密方案需要大约为13个星期，而成功的概率为2^(-80)

通信方和敌手都使用更快计算机的效果是使敌手的工作更加困难

多项式有界和多项式函数

对于一个从自然数到非负实数的一个函数f，如果存在一个常数c，使得对于所有n，f (n) < n^c均成立，那么我们就说这个函数f是多项式有界(polynomially bounded)，或者简称为多项式的(polynomial)

多项式时间运行 的含义

A是一个算法。如果存在一个多项式p，对于每个输入x∈{0,1)^∗，A (x)的计算最多在p(|x|)次数内终止（这里的|x|表示字符串x的长度），则称算法A在多项式时间内运行

使用多项式的一个技术优势是它们服从一定的闭包性质。特别地，如果p1，p2是两个多项式，

那么函数p (n) = p1(p2(n))也是多项式。

DEFINITION 3.4 可忽略函数

从自然数到非负实数的一个函数f，如果对于每个多项式p都有一个N，当n>N时有f (n) < 1/p(n)，那么我们就称这个函数f是可忽略的(negligible)。

还有一种等价描述，即对于所有常数c存在一个N，当n > N时，f(n)恒小于n^(−c)

我们通常用negl表示可忽略的函数

PROPOSITION 3.6 可忽略函数的性质

假设negl1 和 negl2为两个可忽略的函数，则：

• negl3(n) = negl1(n) + negl2(n)，则negl3也是可忽略的函数
• 对于任何一个多项式 p ，若negl4(n) = p(n) * negl1(n)，则negl4也是可忽略的函数

上述第二条性质意味着，如果某一事件在某一实验中只以可忽略的概率发生，那么即使该实验多项式重复多次，该事件发生的概率也可以忽略不计。

渐进安全性的精确定义

如果对于每个PPT敌手，对所有正多项式p，存在一个正整数N；当 n>N 时，敌手A成功破解的概率小于1/p(n)，则方案是安全的。注意，对于n≤N值时的安全性没有任何保证。

放宽限制的必要性 Necessity of the Relaxations

计算安全性引入了两种对于完善保密性的松弛：

• 保密只保证对有效的对手有效；
• 保密可能以很小的可能性“失败”

这两种松弛对于实现实际的加密方案都是必不可少的。我们会非正式地讨论为什么会这样。假设我们有一个加密方案，其中密钥空间K的大小小于消息空间M的大小，即|K| < |M|。如前一章所示，这意味着该方案不满足完善保密性。无论如何构造加密方案，都会受到两种攻击：

穷举攻击Brute-force attacks：给定一个密文c，对手可以使用所有密钥k∈k解密c。这给出了c可能对应的所有消息的列表。由于|K| < |M|，此列表不能包含所有M，因此此攻击会泄露有关已加密消息的一些信息。此外，假设对手进行已知明文攻击，并得知密文c1,c2, . . . , cl分别对应消息 m1,m2, . . . , ml。对手可以再次尝试用所有可能的密钥逐个解密这些密文，直到找到一个密钥k，使得Deck(ci) =mi对于所有的i均成立。之后，给定一个密文c是一个未知消息m的加密，几乎肯定是Deck (c) = m。经过O(|K|)时间，敌手成功的概率约为1

随机猜测：考虑当敌手获取了密文c1, ..., cl分别对应的明文m1, ..., ml，敌手不再是尝试所有可能的密钥，而是在密钥空间中随机的抽取密钥 k 进行尝试，则有 1/|K| 的概率成功破解。

然而，通过设置|K|足够大，我们可以希望实现有意义的保密（攻击者运行时间远小于|K|，所以攻击者没有足够的时间进行穷举攻击）。当然，这不排除还有极小的1/|K|的概率攻击成功，但这个时候宁愿相信敌手被雷电击中，也不会相信敌手以这样的概率破解