BS Chap 2: Encryption

type

status

date

slug

summary

前置数学知识

在 GCAC 中，关于数学细节其实是放在这一章的中后部讲的，有点搞笑的是书里面说 :”We stress that the reader may safely skip this section without suffering a significant loss in understanding.”

所以的话我们在这里也只涉及一些重要概念的理解，而先不去看它们的具体证明细节。

在这一章里面最重要的两个数学概念分别是 efficient 和 negligible（可忽略量），其中 efficient 的概念又可以分成关于 efficient encryption/decryption algorithm 的概念和 efficient adversary 的概念。

Negligible function

首先介绍什么是 negligible function。negligible 是一个渐进的定义，直观地，我们可以理解成当 negligible function 的输入足够大时，的函数值将小于任意多项式的倒数。或者也可以理解为当的输入足够大时，无论乘上一个多大的多项式，它们的乘积还是会小于1 。

那么如果有一个函数，如果是一个 negligible function 的话，我们可以知道对于任意多项式，在输入足够大时，就会有，也就是说比更“大”。我们将称为超多项式的（super-poly）。

Efficient

对于一个 efficient algorithm，我们认为它在多项式输入长度下，执行时间（running time）与某一个多项式函数之差是一个关于输入长度的 negligible function。说人话就是我们可以大概理解为，一个 efficient algorithm 可以在关于输入长度的多项式时间内被执行完毕。

然后我们怎么去理解 efficient adversary 呢？在密码学的世界里面我们将它 modeled 为一个交互机器（interactive machine），一个 efficient adversary 就是一个 efficient 的 interactive machine。和上面的定义类似，我们认为这个 machine 的执行时间与某一个多项式函数之差是一个关于输入长度的 negligible function。

Shannon ciphers and perfect security

Shannon cipher

Shannon cipher 是这样的一个算法对：，它定义在上。其中是密钥的集合，是明文（plaintext）的集合，是密文（ciphertext）的集合。

有。

Shannon cipher 的正确性是指对于所有密钥所有 plaintext 都可以被正确解密：

我们常见的 One-Time-Pad（OTP）和变长 OTP 都是 Shannon cipher。

Perfect Security

给定一个上面所描述的 Shannon cipher，如果它满足以下条件，则我们说它满足完美安全（Perfect Security）：

也就是说不管密钥怎么选，每个明文被加密为同一密文的概率都是一样的。

这个条件还有一个等价条件，即对于每一个明文和密文，都存在一个常数使得：

这个也比较好理解，因为我们从密钥出发去看，这里实际上是一个古典概型。设对,由完美安全的定义我们知道，由于是一个定值，所以存在一个常数使得：

所以说如果密钥满足均匀分布，那么对于每一个密文，都相等，那么就有相等，即每一个密文都服从同一分布。

推论1：满足完美安全，则对于 上的任意 predicate 和任意，都有

直观一点地说，如果我们拿到了两个不同明文所对应的密文，然后想通过对密文的 predicate 看看的长度是否等长，或者说想看看是不是一奇一偶，那都是做不到的。因为从概率上我们就没办法找出这两个密文的一些“特殊性质”，也可以说没办法发现一些“额外信息”。

推论2：满足完美安全，则随机变量和相互独立

要理解这个推论，首先我们要理解随机变量和相互独立，这点还是比较显然的，因为无论怎么选，明文都可以任选，反之亦然。

然后这里的数学证明我懒得写出来了（？），我们直接看一下这个推论的含义。这个推论就更能体现完美安全的优势了，因为当我们拿到一个密文，由于随机变量和相互独立，除了盲猜之外我们没有更好的方法来到它对应的明文。

OTP 是一个常见的满足完美安全的例子。

Shannon’s Theorem

Shannon’s Theorem 是说，一个定义在上的 Shannon cipher ，如果它满足完美安全，那么。

对于这个定理的证明我们可以使用反证法，假设有，目标是要推出存在，使得

注意到和之间的大小关系，我们能很快想到对于同一个密文，密钥实际上是“不够用的”。也就是说假如我们设集合是密文用某个解密出的明文集，因为，实际上一定会有。

现在我们可以设，显然会有：

因此满足，QED。

因为 Shannon’s Theorem 的存在，我们很遗憾（？）地发现，其实也没有比 OTP 更好的完美安全 cipher 了，至少 OTP 密钥和明文等长，而且异或运算还快。但在现实生活中我们可能并不需要用到完美安全这种“关于密文的任何信息都不泄漏”的定义，这个定义有点太强了，我们可以适当允许一些在特定场景下不敏感的信息的泄漏，比如说允许泄漏密文的长度。于是就有了下个部分的语义安全（Semantic Security）。

Computational ciphers and semantic security

Computational cipher

和 Shannon cipher 类似，一个 computational cipher 是定义在上的算法对：。

但和Shannon cipher 不同的是，computational cipher 允许加密函数是一个概率性（Probabilistic）算法，也就是说对于固定的输入和，可以有多种输出（此时的输出不再是确定性的，但还是一个函数，我们只是通过加入一些随机性去达到这个性质）：

Computational cipher 同样允许解密函数是一个概率性算法，但我们一般都不会这么干，一般来说解密函数是一个确定性算法，但可以输出一个的特殊值，类似我们在编程时扔出一个 error。

Computational cipher 的正确性要求是指，对于任意:

就是说无论密文是用什么随机种子生成出来的，解密结果一定还是对应的明文。

Semantic security

形式定义：

给定一个上面所描述的 computational cipher，如果它满足以下条件，则我们说它满足语义安全:

对于所有在上的 efficient predicate ，所有

其中是在中服从均匀分布的一个随机变量。

由完美安全部分的推论2可以看出，如果一个 Shannon cipher 满足完美安全，那么它必定满足语义安全。

不难看出语义安全的定义比完美安全的定义更弱一些。完美安全是要求对于一个密文，明文空间中每个元素都等可能地是对应的明文，要求的是概率分布要相同；而语义安全没有对分布作出明确的限制，只是说没有一个 efficient predicate 能算出 和分布的区别，但不代表这两者之间本身没有区别，它们的区别甚至有可能很大。

或者再把要求放低一点点，我们可以认为对于一个满足语义安全的 cipher，任意 efficient predicate 只能算出和之间可忽略的区别：

其中是一个可忽略量（negligible）。

用 Attack Game 描述安全定义（Why and How）:

首先介绍一下 Attack Game 大概长什么样子：一个 game 里面有两个参与方，一方我们叫 Challenger，另一方叫 Adversary，通过它们的“交互”来描述一个安全定义。

为什么要定义这样的一个 game？我们的思路是为 Challenger 设定不同的行为，每一个不同的行为都可以定义为一个新的 game；Adversary 在这些不同的 game 里面 follow the same protocol，然后我们观察 Adversary 在 games 里输出的不同，来衡量 Adversary 在现实中攻击的能力或者说是优势。

举个实例，我们现在用 Attack Game 描述语义安全，以下定义 game :

Adversary 计算出两个等长的，将发给 Challenger

Challenger 随机抽一个，将算出来的发给 Adversary

Adversary 输出比特

我们观察一下和的区别，其实就是 Challenger 选择加密还是的区别。在这两个 game 中 Adversary 的行为是没有变化的。

将 Adversary 简记为，接下来我们定义以下两个事件：

在中输出

我们将攻击 cipher 的语义安全优势（advantage）定义为：

为什么我们要这样定义的语义安全优势呢？其实还是从语义安全的定义出发，个人理解其实就是 predicate 的一个实例，这样来看其实的语义安全优势定义和的语义安全定义是对应的。

如果对于所有 efficient 的 Adversary ，都有以下条件成立，那么我们说满足语义安全：

Message recover attack

在这个部分，我们首先给出 Message recover attack 的定义，然后通过规约，证明如果一个 cipher 满足语义安全，那么它也满足抗密钥提取攻击安全（secure against message recovery）。

Message recovery：

设有一个定义在上的 cipher ，给定一个攻击者，我们用以下的 game 去定义的 message recovery：

Challenger 计算，将算出来的密文发给攻击者

输出一个

设事件：。当事件发生时，我们说赢得了这次的游戏。

以下定义的 message recovery 优势：

也就是说的 message recovery 优势是它成功输出密文的概率减去它盲猜一个然后刚好猜中的概率。

如果对于任意的efficient adversary 都是一个可忽略量，那么我们说满足抗密钥提取攻击。

安全证明与规约：

什么是问题的规约？

当我们说问题A可规约到问题B时，意思就是如果存在一个高效解决问题B的方法，这个算法也能用来解决问题A。举个例子，比如问题A是求一个数的平方，问题B是求两个数的乘积，显然我们可以用问题B的算法来解决问题A，即用某一个数与自己的乘积求出这个数的平方；那么我们就说求一个数的平方可规约到求两个数的乘积。

在这里有个值得想一下的问题，就是我们得想明白如果问题A可规约到问题B，那么A和B到底哪个问题更难呢？应该是B更难一些，因为如果B可解，那么A肯定也可解，但是反之不一定，所以B不会是一个比A更简单的问题。

规约在安全证明中有什么用？

对于一个 cipher，如果要证明它在某个安全模型下满足某种安全定义，我们的想法就是去“抱大腿”“拜个山头”。意思就是我们可以将安全性规约到某个“大哥”上，躲在大哥背后当个小弟，如果大哥被攻击了，那么小弟就会被重拳出击。但重点是大哥之所以是大哥，就是因为人家很强嘛，人家就不大可能被成功攻击，所以我们可以狐假虎威地躲在大哥背后，说自己也很强很安全（？）。

🤯

之所以选择躲在大哥背后当小弟（将安全性规约到难题），而不是当大哥的大哥（将难题规约到安全性），是因为后者的要求太高，小弟通常都做不到。

但我们还是要知道，上面说的是如果大哥倒了那么小弟就会倒，但并不是只有大哥倒了小弟才会倒。很多时候大哥在前方无人可敌大杀特杀，背后的小弟还是有可能直接被人一闷棍敲晕。

那看起来好像找个大哥也没啥用，但如果连大哥都找不到，那~~铁定是个没用的小弟~~。

一般来说我们找的“大哥”会是某个公认的难题，比如我们将破解 RSA 规约到大整数分解问题上，或者也可以是某个更强的安全定义，或是某个已被证明的安全方案之类的。

抗密文提取攻击的规约：

首先我们要思考一个问题：到底是做到抗密文提取攻击难呢，还是做到语义安全难呢？很直接地去想，假如我们有一个算法能直接提取出某个明文对应的密文，那在语义安全的 game 里面我们压根不用猜啊，直接就能算出来 Challenger 加密的到底是还是。所以做到抗密文提取攻击安全并不比做到语义安全简单。

所以，我们想将攻击语义安全规约到攻击密文提取安全上。大概的思路是假定存在一个攻击密文提取安全的攻击者，然后我们构造一个攻击语义安全的，让通过的“帮助”来完成对语义安全的攻击。由此将完成规约。

具体来说怎么做呢？我们回顾一下的 message recovery advantage：

：

对于攻击语义安全的，的优势是：

在中输出

接下来我们要设计和如何交互，才能让赢得和 Challenger 的博弈。要用以下方式和 Challenge 玩游戏：

计算出两个等长的，将发给 Challenger

Challenger 随机抽一个，将算出来的发给

作为 Challenger，和玩 message recovery 的 attack game

把拿到的发给
输出一个

如果，那么就输出1；否则输出0

从挑战密文开始分析，如果是的密文，那么是在玩 game ，在中输出1当且仅当输出的。但由于不是的密文，也就是说其实压根没有关于的信息，输出的和就是独立的，能猜中的概率是:

那如果是的密文，那么是在玩 game ，在中输出1当且仅当输出的。这时候就非常开心，因为 Challenger 发了的密文，然后也成功算出了，所以就可以十分确信地说：

所以，我们证出了：

或者从规约的角度来看，我们可以写成：

所以，如果满足语义安全，那么对于任意的 efficient 攻击者，都是一个可忽略量；因此对于所有 efficient 攻击者，也是一个可忽略量。

即：如果满足语义安全，那么也满足抗密钥提取攻击安全。

重点总结

语义安全的 attack game 定义

message recovery 的 attack game 定义

规约的概念

如何将攻击语义安全规约到攻击密文提取安全