第 8 章：PRF、CPA 和 CCA 安全¶

密钥函数¶

$F : {0, 1}^{k} \times {0, 1}^{*} \to {0, 1}^{*}$

那么有多少种 F 呢？如果长度为 n，那么可以有 $(2^{n})^{2^{n}}$ 种。

让 $R_{k}$ 是随机的一个 $F_{k}$ 。所以如果 $a \neq b$ ， $R_{k} (a)$ 的值对于 $R_{k} (b)$ 没有意义。

看起来 $R_{k}$ 很强。如果要拿它作加密函数的话，得让 $c := ⟨ r, R_{k} (r) \oplus m ⟩$ ，其中 r 不能重复。

伪随机函数 PRF¶

对于函数 F，如果同时满足：

$F : {0, 1}^{n} \times {0, 1}^{n} \to {0, 1}^{n}$ ；
对于所有 PPT 分辨者 D， $| Pr [D^{F_{k} (\cdot)} (1^{n}) = 1] - Pr [D^{f (\cdot)} (1^{n}) = 1] | \leq n e g l (n)$ ，其中 f 是从 $F_{n}$ 中随机取到的某个函数；

那么 F 是个 PRF。

使用 PRF 加密¶

$E n c_{k} (m) : c := ⟨ r, F_{k} (r) \oplus m ⟩, r \leftarrow {0, 1}^{n}$ ；
$D e c_{k} (c) : c = ⟨ r, s ⟩, m := F_{k} (r) \oplus s$ 。

安全性证明¶

现在有一个很厉害的对手 A，可以打掉上面使用 PRF 加密的 CPA 安全的系统 $Π$ 。现在构造一个分辨器 D：

$c := ⟨ r, g (r) \oplus m ⟩$ ；D 有访问 g 的权限。

那么如果 A 猜对就输出 1，否则输出 0。

当给 D 一个随机函数 f： $Pr [D^{f (\cdot)} (1^{n}) = 1] = Pr [{P r i v K^{c p a}}_{A, Λ} = 1] \leq 1 / 2 + q (n) / 2^{n}$ ，A 最多访问 q(n) 次加密操作。 $Λ$ 是上面使用 PRF 加密的系统。

当给 D PRF $F_{k}$ ： $Pr [D^{F_{k} (\cdot)} (1^{n}) = 1] = Pr [{P r i v K^{c p a}}_{A, Π} = 1]$ 。

所以 $Pr [{P r i v K^{c p a}}_{A, Π} = 1] > 1 / 2 + n e g l (n)$ 当且仅当 $| Pr [D^{F_{k} (\cdot)} (1^{n}) = 1] - Pr [D^{f (\cdot)} (1^{n}) = 1] | > n e g l (n)$ 。

伪随机序列 PRP¶

块加密¶

$F : {0, 1}^{n} \times {0, 1}^{l} \to {0, 1}^{l}$ ，密钥长度为 n，块大小为 l。F 是一个双射。

混淆与扩散¶

混淆：打乱明文、密文、密钥之间的依赖关系。

扩散：明文或密钥哪怕只变 1 个 bit 都能影响密文的所有比特，破坏明文统计特性（雪崩效应）。

置换排列网络¶

这是混淆扩散范式的一种变体。

S 盒
主密钥会生成子密钥，子密钥和中间结果作异或。

每一轮有三个步骤：

消息与子密钥异或。
消息被分割，并通过 S 盒。
消息混合排列（位重新排序）。

注意 S 盒必须是可逆的，否则没法解密；并且需要达成雪崩效应：S 盒 1 比特变至少引起 2 比特的变化。

费斯妥网络 Feistel Network¶

S 盒不用可逆，因为加密和解密算出来的密钥是相同的。

CCA 不可区分实验¶

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

$k \leftarrow G e n (1^{n})$
对手有访问 $E n c_{k} (\cdot)$ 和 $D e c_{k} (\cdot)$ 的权限。
对手：输出等长明文 $m_{0}, m_{1}$ 。
挑战者：在 0 和 1 中选择一个 $b$ ，发送 $c \leftarrow E n c_{k} (m_{b})$ 。
对手仍然有有访问 $E n c_{k} (\cdot)$ 和 $D e c_{k} (\cdot)$ 的权限，除了不能访问 $D e c_{k} (c)$ 。
对手：猜 $b$ 的取值 $b^{'}$ 。

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