第 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 := \langle r, R_k(r) \oplus m \rangle\)，其中 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 negl(n)\)，其中 f 是从 \(F_n\) 中随机取到的某个函数；
那么 F 是个 PRF。
使用 PRF 加密¶
- \(Enc_k(m): c := \langle r, F_k(r) \oplus m \rangle, r \leftarrow \{0, 1\}^n\)；
- \(Dec_k(c): c = \langle r, s \rangle, m := F_k(r) \oplus s\)。
安全性证明¶
现在有一个很厉害的对手 A，可以打掉上面使用 PRF 加密的 CPA 安全的系统 \(\Pi\)。现在构造一个分辨器 D：
- \(c := \langle r, g(r) \oplus m \rangle\)；D 有访问 g 的权限。
那么如果 A 猜对就输出 1，否则输出 0。
当给 D 一个随机函数 f：\(\Pr[D^{f(\cdot)}(1^n) = 1] = \Pr[{PrivK^{cpa}}_{A, \Lambda} = 1] \leq 1 / 2 + q(n) / 2^n\)，A 最多访问 q(n) 次加密操作。\(\Lambda\) 是上面使用 PRF 加密的系统。
当给 D PRF \(F_k\)：\(\Pr[D^{F_k(\cdot)}(1^n) = 1] = \Pr[{PrivK^{cpa}}_{A, \Pi} = 1]\)。
所以 \(\Pr[{PrivK^{cpa}}_{A, \Pi} = 1] > 1/2 + negl(n)\) 当且仅当 \(|\Pr[D^{F_k(\cdot)}(1^n) = 1] - \Pr[D^{f(\cdot)}(1^n) = 1] | > negl(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 不可区分实验¶
定义一个实验 \(PrivK^{cca}(n)\)：
- \(k \leftarrow Gen(1^n)\)
- 对手有访问 \(Enc_k(\cdot)\) 和 \(Dec_k(\cdot)\) 的权限。
- 对手：输出等长明文 \(m_0, m_1\)。
- 挑战者：在 0 和 1 中选择一个 \(b\)，发送 \(c \leftarrow Enc_k(m_b)\)。
- 对手仍然有有访问 \(Enc_k(\cdot)\) 和 \(Dec_k(\cdot)\) 的权限，除了不能访问 \(Dec_k(c)\)。
- 对手：猜 \(b\) 的取值 \(b'\)。
\(PrivK^{cca} = 1\) 如果 \(b = b'\)（猜对），否则 \(PrivK^{cca} = 0\)。