BS Chap 3: Stream ciphers

type

status

date

slug

summary

Stream ciphers

🤯

流密码（Stream Cipher）是一种加密算法，它通过将明文数据流（通常是位流或字节流）与伪随机生成的密钥流逐位或逐字节地进行异或（XOR）运算来生成密文。与分组密码（Block Cipher）不同，流密码不需要将数据分成固定大小的块，而是按位或按字节对数据流进行加密。

Stream ciphers = （E，D）:

和 OTP 类似，流密码使用对称加密，不同的是流密码使用伪随机生成器（Pseudo-random generators，PRG）来进行加密，而 OTP 中使用一个真随机数进行加密。

既然 OTP 和流密码类似，我们肯定要问的一个问题是——流密码和 OTP 相比，优势是什么？

在流密码中，密钥是 PRG 的种子()，而不是一个长度为的串；它的长度可以比明文更短，而在 OTP 中密钥的长度和明文等长。因此，流密码中只需一个较短的密钥，通过 PRG 生成伪随机数，就可以生成一个较长的密钥流。

值得注意的是，在上一章的 Shannon’s Theorem 部分，我们已经证明了如果一个 Shannon cipher 密钥空间的长度比明文空间的长度小，那么这个 cipher 一定不满足完美安全。因此流密码一定是达不到完美安全的，但当 PRG 满足某些条件的情况下，我们可以证明流密码能达到语义安全。

PRG

很直观地想，如果我们不能有效区分PRG 的输出和真随机串的区别，我们也没法有效区分流密码和 OTP。一个 PRG 的输出如果与真随机数不可区分，那我们简单想想它应该符合哪些性质：

每一位的分布大致相等：每一位中0和1的分布都应该近似相等，且0和1出现的几率大致是五五开。

不应被有效预测：比如说一个 PRG 的输出可以通过很多概率性检验，但是这个 PRG 的输出有一些特殊的性质，比如它一定会输出回文串，这种性质也可以让我们快速区分 PRG 的输出和一个真随机数，所以它不应有这种 predictable。

设 PRG ，接下来我们给出 secure PRG 的 Attack Game 定义。

以下定义 game :

Challenger 计算

Challenger 计算

Challenger 将发给 Adversary

Adversary 输出比特

设事件：

：Adversary 在中输出

敌手区分PRG 的输出与真随机数的优势为：

上面的两个 Game 是说在一个 Game 里一定会向 Adv 发 PRG 的输出，而在另一个 Game 里则一定会发一个真随机数，就是 Adv 算对的概率减去算错的概率，或者说是 Adv 成功区分上的随机分布与 输出的分布的概率。如果 PRG 是安全的，那么我们认为对于任意的 efficient 敌手，都是关于安全参数的可忽略量。

还有一个 bit-guessing 版本的 Game，Challenger 抛一个硬币来决定到底给 Adv 发 PRG 的输出还是发一个真随机数：

GAME（bit-guessing）：

Challenger 计算

Challenger 计算

Challenger 计算，将发给 Adversary

Adversary 输出比特

将这个游戏中敌手算对的优势记作：

注意到：

所以有：

就是说对于同一个 Adv，如果 Adv 玩的是 bit-guessing 游戏，优势会变为原始游戏的 1/2 。这里的话感觉就是差了一个条件概率，就是 Adv 其实不知道自己是在和还是在和交互，这里还要猜一次，所以优势是原始游戏的的 1/2 。

然后回到流密码（E，D）：

这里明文m和密文c的长度需要小于等于。如果长度小于，假设说长度是，那么就取的前个比特，然后和m或者c进行异或。

🤯

对于有些 PRG 来说，直接算前个比特，比算出完整的G(s)再做截断要来得高效。

安全规约

接下来我们要将 stream cipher 的语义安全规约到 PRG 的安全性上，具体地有：

设是敌手在 bit-guessing 版的 Semantic Secure Attack Game 中获胜的优势。

Stream cipher’s SS Attack Game*（bit-guessing version）：

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

Challenger 计算

Challenger 计算，将算出来的发给 Adversary

Adversary 输出比特

设上述 Stream cipher’s SS Attack Game* 为 Game 0.

设事件：敌手在 Game 0 中输出。

即.

我们玩一个新的游戏 Game 1，Game 1 将设置为真随机数：

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

Challenger 计算

Challenger 计算，将算出来的发给 Adversary

Adversary 输出比特

设事件：敌手在 Game 1 中输出。

由于在 Game 1 中是一个真随机数，即和敌手得到的挑战是独立的，即实际上和也是独立的，所以敌手在 Game 1 中真的只能盲猜：

所以有：

然后我们可以构造一个攻击 PRG security 的敌手，和 PRG Challenger 玩游戏会得到一个；随后作为 SS Challenger 和敌手玩游戏，抛个硬币，向发挑战。最后当输出时，输出。

设事件

：敌手在 Game 0 中输出

：敌手在 Game 1 中输出

由于 Game 0 中是 PRG 的输出，而在 Game 1 中是真随机数，我们对比一下 PRG Attack Game的定义，会发现有：

所以：

这个证明的直观理解就在于，如果真的有优势猜出到底是的密文还是的密文，那就说明和不独立，那么就不会是一个真随机数。所以借助攻击 SS 的敌手就可以区分是 PRG 的输出还是一个真随机数。

流密码的错误打开方式

上一部分我们说用 secure 的 PRG 就可以构造出语义安全的流密码，语义安全辣当然很强啦，但是如果我们的用法有问题，反而会导致整个 scheme 变得不安全。下面给出流密码的两种错误打开方式，以此说明正确使用流密码的重要性（？）

Two-Time Pad

让我们来举一个例子，假设 Alice 想给 Bob 发两个 message，分别是和，如果我们用同一个密钥去加密两个明文：

那么假设 Alice 和 Bob 中间有一个窃听者 Eva， Eva 就可以计算：

那 Eva 就有了关于和的信息。

上面这种做法被戏称为 Two-Time Pad，即用同一个流密码加密两个及以上的 message，这个做法是非常不安全的！！

The One-Time Pad is Malleable

还是 Alice 想给 Bob 发消息，比如说发一个，随后用流密码计算，然后把发给 Bob。那么窃听者 Eva 在截获之后，就可以伪造一个密文 :

其中是 Eva 自由选取的一个值。

而 Bob 收到后，没有办法判断这个密文有没有被半路篡改过，即在流密码中，integrity（完整性）无法得到保障。Eva 不知道 Bob 的 secret key，但也可以成功篡改密文。

Composing PRGs

这个部分的重点有两点：

如何用已有的 PRG 组合出新的 PRG

证明组合得到的 PRG 的安全性不低于已有的 PRG

对于第一点，我们除了要知道如何组合 PRG 之外，还要知道为什么要组合出新的 PRG。原因是我们可以通过组合 PRG，获得比已有 PRG 的输出范围更广的新 PRG。

接下来我们介绍组合 PRG 的两种构造。

A Parallel Construction

如何构造：

假设是一个定义在上的 PRG，我们可以构造这样一个定义在上的 PRG ：

我们说是的 -wise parallel composition，其中被称为 repetition paramater，是一个 poly-bounded 的值。

定理1：

假设是一个secure PRG，那么的 -wise parallel composition 也是一个 secure PRG，并且有：

如何理解：

定理1在直观上也很好理解：假设的攻击者能有效区分和随机数，那的攻击者就把得到的挑战逐个发给，让判断是不是一个随机数。

如果判断所有都是随机数，那么就认为挑战是一个随机数。如果判断存在某个不是随机数，那么就认为挑战是由 PRG 生成出来的数。我们可以把向发送，并让判断是不是随机数，视为一次独立事件，显然的 PRG 优势就是的倍。

除了上面这个理解之外，我想应该还有第二种理解方式：

假设的攻击者能有效区分和随机数，那么的攻击者就把得到的挑战嵌到发给的挑战中。具体做法为选择一个，并选择个随机数，其中，然后构造一个挑战：

如果判断是 PRG 生成的数，那么就知道了也是 PRG 生成的数；反之如果判断是真随机数，那么就判断是一个随机数。并且由于的选择有种，所以的 PRG 优势是的。

安全证明：

在这里我们使用一种被称为 Hybrid Game 的证明技巧，使用个 Game 去证明定理1。其中第0个 Hybrid Game 和的攻击者玩的 PRG secure Attack Game 1 （挑战是 PRG 生成的数）一致，而第个 Hybrid Game 和 PRG secure Attack Game 0 （挑战是随机数）一致。

随后我们构造一个的攻击者，通过和交互、构造得到的挑战，来判断他得到的挑战是否为 PRG 生成的数，即的输出与的输出一致。构造方式和上面所说的第二个理解非常像，区别之处在于我们把之后的分量都设置为 PRG 生成的数，这是为了从第 0 个 Hybrid Game 到第个 Hybrid Game 的每一个中间 Hybird Game 都不可区分。

所以对于嵌入的每个位置（），我们按以下方式构造得到的挑战：的前个分量是随机数，后个分量是由 PRG 生成的数，而第个分量即为的攻击者得到的挑战：

然后我们构造 Hybrid Game：

Hybrid Game 0 :

Hybrid Game :

设是在 Hybrid Game 中输出 1 的概率；事件是为 PRG 生成的数，输出1；事件是为一个随机数，输出1。

当把挑战嵌入位置时，如果为 PRG 生成的数，实际上等价于在玩 Hybrid Game ；而如果为一个随机数，等价于在玩 Hybrid Game 。

又因为 mock 了的输出，所以有：

所以根据全概率公式：

所以有：

整理一下就得到了定理1！！

所以如果是一个 secure PRG，那么就是一个可忽略量，如果 是一个 poly-bounded value，那么也会是一个可忽略量，所以我们构造的也是一个 secure PRG。

The Blum-Micali Method

如何构造：

假设是一个定义在上的 PRG，我们可以构造这样一个定义在上的 PRG ：

我们说是的 -wise sequential composition，其中是一个 poly-bounded 的任意值。

定理2：

假设是一个secure PRG，那么的 -wise sequential composition 也是一个 secure PRG，并且有：

如何理解：

如何理解 sequential 的构造？其实和 parallel 的构造非常类似：假设的攻击者能有效区分和随机数，那的攻击者就取得到的挑战逐个发给，让判断是不是一个随机数。

或者从另一个方向上，我们假设的攻击者能有效区分的输出和随机数，那么的攻击者就把得到的挑战嵌到发给的挑战中。具体做法为选择一个，并选择个随机数，其中，，然后构造一个挑战：

安全证明：

安全证明部分思路与技巧和定理1的部分一样，不同之处在于嵌入挑战的方式发生了一点变化：

然后我们构造 Hybrid Game：

Hybrid Game 0 :

Hybrid Game :

剩下的部分和定理1一致，在此略过不证。

Unpredictability for A PRG

在介绍 PRG 的概念时，我们曾经讲到：

一个 PRG 的输出如果与真随机数不可区分，那我们简单想想它应该符合哪些性质：
每一位的分布大致相等：每一位中0和1的分布都应该近似相等，且0和1出现的几率大致是五五开。
不应被有效预测：比如说一个 PRG 的输出可以通过很多概率性检验，但是这个 PRG 的输出有一些特殊的性质，比如它一定会输出回文串，这种性质也可以让我们快速区分 PRG 的输出和一个真随机数，所以它不应有这种 predictable。

我们可以设计一个概率性检验去描述上面两种性质：对于一个定义在上的 PRG ，Challenger 随机挑选种子，用生成伪随机数，并让攻击者选择一个 index ，将的前位发给，最后让去预测的第位。

如果成功预测的第位的概率与 1/2 只相差可忽略量，那么我们就说具有 unpredictability。下面我们用 attack game 去描述。

Unpredictable PRG Attack Game

攻击者任意挑选 index ，并将发给 Challenger

Challenger 计算：，并将发给

计算：

的预测优势为：

如果对于任意 efficient 攻击者，都是可忽略量，那么就说满足 unpredictable。

安全规约

定理3:

设是一个定义在上的 PRG。如果是一个 secure PRG，那么满足 unpredictable。并且有：

如何理解：

用 unpredictability 的攻击者去构造 secure PRG 的攻击者是比较容易的：只需要将自己收到的挑战的前位发给，然后让去预测的第位。如果预测的第位和的第位一样，那么就认为是生成的伪随机数；反之则认为是一个真随机数。

定理4:

设是一个定义在上的 PRG。如果满足 unpredictable，那么是一个 secure PRG。并且有：

如何理解：

如果要证明定理4，构造思路上和定理3相反，我们要用 secure PRG 的攻击者去构造一个 predictor ：任意挑选，然后让 Challenger 发一个长度为的挑战；随后生成一个长度为的随机串，将两个串拼接为，并将作为 secure PRG attack game 的挑战发给。如果认为是生成的伪随机数，说明的分布和上的随机均匀分布可区分，那么就输出；否则输出。

并且由于的选择有种，所以的 PRG 优势是的。

Computational Indistinguishability and Statical Distance

Computational Indistinguishability

在secure PRG 的 Attack Game 定义中，其实我们已经接触了关于计算不可区分性的概念，因为这个 Attack Game 直观来说就是让 efficient 攻击者区分上的随机分布与输出的分布。

Attack Game 定义：

更广义一些，假设和是定义在有限集合上的两个分布，对于攻击者，我们还是用 Attack Game 去定义区分和的优势：

Challenger 计算

Challenger 将发给 Adversary

攻击者输出比特

设事件：

：在中输出

那么区分和的优势为：

如果是个可忽略量，那么我们就认为分布和 在计算上不可区分。

上面的 Attack Game 还可以改写成 bit-guessing 版本：

Game：

Challenger 计算

Challenger 将发给 Adversary

攻击者输出比特

在这个游戏中获胜的优势为：

此外，对于任意，我们定义：

Statistical Distance

定义：

设和是定义在有限集合上的两个分布，则它们的统计距离为：

这里可以把理解为分布中取到的概率，所以描述的就是两个分布取到每个元素的概率差距之和。至于为什么前面要乘一个 1/2，~~g老师告诉我是为了取平均距离~~。

定理5:

设和是定义在有限集合上的两个分布，对于每个攻击者，有：

定理5告诉我们，攻击者区分和的优势不会大于和本身的统计距离。或者我们换个方向来理解，两个分布的统计距离是某个最强攻击者区分这两个分布的优势。

总结

这一章主要讲了：

Secure PRG 的安全定义，以及如何把流密码的安全性规约到 secure PRG。

如何用两种不同的方法，由 secure PRG 构造出输出范围更大的 secure PRG。

如何使用 Hybrid Game 去规约，以及 Hybrid Game 的构造思路。

Unpredictability 和 secure PRG 的相互规约。

计算不可区分与统计距离的概念。