第 7 章：流加密和 CPA 安全¶

流加密¶

伪随机数生成器¶

流加密得使用一个伪随机数生成器（Pseudo Random (Number) Generator，PR(N)G）： $G : {0, 1}^{s} \to {0, 1}^{n}$ ，即把一个随机数种子拓展到很大一坨“看起来是”随机的 01 序列。

分辨者¶

一个对于两个分布的分辨者（Distinguisher），需要（可以）对给定的序列判断它是从哪个分布生成的。

伪随机生成¶

如果某个算法 $G$ 有长度为 n 的输入和长度为 $l (n)$ 的输出，并且：

对于所有 n， $l (n) > n$ ；
并且对于所有 PPT 分辨者，存在一个可忽略函数 $n e g l (n)$ ，满足： $| Pr [D (r) = 1] - Pr [D (G (s)) = 1] | \leq n e g l (n)$ ，其中 r 是在 ${0, 1}^{l (n)}$ 中的真随机，s 是 ${0, 1}^{n}$ 中的真随机；

那么这个 G 就可以被叫做伪随机数生成器。

PRG 的安全¶

如果系统 $Π$ 是使用一个 PRG 拿 $G (k) \oplus m$ 方法加密的，那么即使有窃听者，它的加密也是不可区分的。

如果加密是可区分的，我们就可以用分辨者破解这个系统。

变长的输出¶

如果对于长度 l，某个 PRG 满足：

某个短输出总是长输出的前缀；
即使把输出截短也满足 PRG；

那么这个变长输出 PRG 就是 $G (s, 1^{l})$ 的。用它可以加密不同长度的消息。

多重加密¶

定义一个实验 $P r i v K^{m u l t} (n)$ ：

对手：给挑战者两个长度相同的明文 $m_{0}$ 和 $m_{1}$ 。k 是长度。
挑战者：在 0 和 1 中选择一个，作为 $b$ ，发送 $C = E_{k} [{m_{b}}^{1}], E_{k} [{m_{b}}^{2}], \dots, E_{k} [{m_{b}}^{t}]$ 。
对手：猜 $b$ 的取值 $b^{'}$ 。

$P r i v K^{m u l t} = 1$ 如果 $b = b^{'}$ （猜对），否则 $P r i v K^{m u l t} = 0$ 。

$Pr [{P r i v K^{m u l t}}_{A, Π} = 1] \leq \frac{1}{2} + n e g l (n)$ 。

没有一种确定性加密方案对多重消息加密是安全的。

用流密钥加密多重消息¶

同步模式¶

使用输出流的不同部分加密每条新消息。

但是因为发送方和接收方需要知道哪个位置用于加密每条消息，所以经常出现同步问题。

伊布模式异步模式¶

现在有一个随机的初始向量（Initial Vector，IV）。

加密结果 $E n c_{k} (m) = ⟨ I V, G (k, I V) \oplus m ⟩$ ，IV 对于每个消息都是随机选取的。

它对于多重消息加密是安全的。

异步模式的安全性¶

IV 发出去的时候是未加密的，可以被攻击者拿到。
不过 $G (\cdot, I V)$ 可以看作是一个 PRG。
在同一个随机选择的种子下给出多个 IV 和输出时，组合输出是伪随机的。
假设流密码在实践中具有上述增强的伪随机性属性，并以这种方式使用。

CPA 攻击和 CPA 安全¶

现在攻击者可以自己选择消息并获得相应的密文。

定义一个实验 $P r i v K^{c p a} (n)$ ：

k 以 $G e n (1^{n})$ 生成。
对手可以使用 $E n c_{k} (\cdot)$ 无限次。
对手：发送长度为 k 的等长明文 $m_{0}, m_{1}$ 给挑战者。
挑战者：在 0 和 1 中选择一个，作为 $b$ ，发送 $C = E_{k} (m_{b})$ 。
对手：依然可以使用 $E n c_{k} (\cdot)$ 。猜 $b$ 的取值 $b^{'}$ 。

$P r i v K^{c p a} = 1$ 如果 $b = b^{'}$ （猜对），否则 $P r i v K^{c p a} = 0$ 。

如果 $Pr [{P r i v K^{c p a}}_{A, Π} = 1] \leq \frac{1}{2} + n e g l (n)$ ，那么就是 CPA 安全的。很明显确定性算法都不是 CPA 安全的。

（给定一个 CPA 安全的定长加密方案，我们可以通过分别加密消息的不同部分来加密任意长度的消息。）