第 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 分辨者，存在一个可忽略函数 \(negl(n)\)，满足：\(|\Pr[D(r) = 1] - \Pr[D(G(s)) = 1]| \leq negl(n)\)，其中 r 是在 \(\{0, 1\}^{l(n)}\) 中的真随机，s 是 \(\{0, 1\}^{n}\) 中的真随机；
那么这个 G 就可以被叫做伪随机数生成器。
PRG 的安全¶
如果系统 \(\Pi\) 是使用一个 PRG 拿 \(G(k) \oplus m\) 方法加密的，那么即使有窃听者，它的加密也是不可区分的。
如果加密是可区分的，我们就可以用分辨者破解这个系统。
变长的输出¶
如果对于长度 l，某个 PRG 满足：
- 某个短输出总是长输出的前缀；
- 即使把输出截短也满足 PRG；
那么这个变长输出 PRG 就是 \(G(s, 1^l)\) 的。用它可以加密不同长度的消息。
多重加密¶
定义一个实验 \(PrivK^{mult}(n)\)：
- 对手：给挑战者两个长度相同的明文 \(m_0\) 和 \(m_1\)。k 是长度。
- 挑战者：在 0 和 1 中选择一个，作为 \(b\)，发送 \(C = E_k[{m_b}^1], E_k[{m_b}^2], \cdots, E_k[{m_b}^t]\)。
- 对手：猜 \(b\) 的取值 \(b'\)。
\(PrivK^{mult} = 1\) 如果 \(b = b'\)（猜对），否则 \(PrivK^{mult} = 0\)。
\(\Pr[{PrivK^{mult}}_{A, \Pi} = 1] \leq \frac{1}{2} + negl(n)\)。
没有一种确定性加密方案对多重消息加密是安全的。
用流密钥加密多重消息¶
同步模式¶
使用输出流的不同部分加密每条新消息。
但是因为发送方和接收方需要知道哪个位置用于加密每条消息，所以经常出现同步问题。
~~伊布模式~~异步模式¶
现在有一个随机的初始向量（Initial Vector，IV）。
加密结果 \(Enc_k(m) = \langle IV, G(k, IV) \oplus m \rangle\)，IV 对于每个消息都是随机选取的。
它对于多重消息加密是安全的。
异步模式的安全性¶
- IV 发出去的时候是未加密的，可以被攻击者拿到。
- 不过 \(G(\cdot, IV)\) 可以看作是一个 PRG。
- 在同一个随机选择的种子下给出多个 IV 和输出时，组合输出是伪随机的。
- 假设流密码在实践中具有上述增强的伪随机性属性，并以这种方式使用。
CPA 攻击和 CPA 安全¶
现在攻击者可以自己选择消息并获得相应的密文。
定义一个实验 \(PrivK^{cpa}(n)\)：
- k 以 \(Gen(1^n)\) 生成。
- 对手可以使用 \(Enc_k(\cdot)\) 无限次。
- 对手：发送长度为 k 的等长明文 \(m_0, m_1\) 给挑战者。
- 挑战者：在 0 和 1 中选择一个，作为 \(b\)，发送 \(C = E_k(m_b)\)。
- 对手：依然可以使用 \(Enc_k(\cdot)\)。猜 \(b\) 的取值 \(b'\)。
\(PrivK^{cpa} = 1\) 如果 \(b = b'\)（猜对），否则 \(PrivK^{cpa} = 0\)。
如果 \(\Pr[{PrivK^{cpa}}_{A, \Pi} = 1] \leq \frac{1}{2} + negl(n)\)，那么就是 CPA 安全的。很明显确定性算法都不是 CPA 安全的。
（给定一个 CPA 安全的定长加密方案，我们可以通过分别加密消息的不同部分来加密任意长度的消息。）