TCS Homework 12

12.1

题目

问题 1. 设 $G$ 是一个拉伸为 $\ell$ 的伪随机生成器，满足 $\ell(n) \geq 2n$（即对于输入长度 $n$，输出长度至少为 $2n$）。

(a) 定义 $G'$ 为 $G'(s) = G(s0^{|s|})$。$G'$ 是否一定是一个伪随机生成器？

(b) 定义 $G''$ 为 $G''(s) = G(s_1 \cdots s_{n/2})$，其中 $s = s_1 s_2 \cdots s_n$（假设 $n$ 为偶数）。$G''$ 是否一定是一个伪随机生成器？

解答

伪随机生成器（PRG）的标准定义要求：

1. 拉伸条件：输出长度严格大于输入长度，即 $\ell(n) > n$。
2. 计算不可区分性：对于所有概率多项式时间（PPT）区分器 $D$，区分器无法以不可忽略的优势区分生成器的输出与均匀随机字符串。

给定 $G$ 是 PRG 且满足 $\ell(n) \geq 2n$，分析 $G'$ 和 $G''$。

(a) $G'(s) = G(s0^{|s|})$ 是否一定是伪随机生成器？

答案：否，$G'$ 不一定是伪随机生成器。

解释：

• $G'$ 的输入为 $s$（长度 $n$），计算 $s0^{|s|} = s0^n$（长度 $2n$），然后应用 $G$ 得到输出 $G(s0^n)$。
• $G$ 是 PRG，因此当输入长度为 $2n$ 时，输出长度为 $\ell(2n) \geq 4n$。
• 问题在于 $G'$ 的输入到 $G$ 的种子 $s0^n$ 不是均匀随机的：后 $n$ 位固定为 0，只有前 $n$ 位随机。因此，输入种子的熵仅为 $n$ 位（而非 $2n$ 位）。
• 尽管 $G$ 本身是 PRG，但当应用于一个非均匀分布（特别是后一半固定为 0）时，输出可能失去伪随机性。

反例构造：

• 定义 $G: \{0,1\}^m \to \{0,1\}^{\ell(m)}$ 如下（其中 $\ell(m) = 2m$ 为简单起见）：
  • 如果输入 $x$ 的后 $m/2$ 位全为 0，则输出 $x$ 的前 $m/2$ 位重复多次，使得输出长度为 $2m$（例如，输出 $(x_1 \cdots x_{m/2})^4$）。
  • 否则，输出 $H(x)$，其中 $H$ 是一个安全的 PRG（例如，基于密码学假设的标准 PRG）。
• 验证 $G$ 是 PRG：
  • 当输入 $x$ 均匀随机时，后 $m/2$ 位全为 0 的概率为 $2^{-m/2}$（可忽略）。
  • 以概率 $1 - 2^{-m/2}$，输出为 $H(x)$，与均匀随机不可区分。
  • 以概率 $2^{-m/2}$，输出为重复模式，但此事件概率可忽略，因此整体计算不可区分性成立。
• 现在考虑 $G'(s) = G(s0^n)$（输入长度 $n$，输出长度 $\ell(2n) = 4n$）：
  • 输入 $s0^n$ 的后 $n$ 位全为 0，因此 $G(s0^n) = (s_1 \cdots s_n)^4$（即 $s$ 重复四次）。
• 区分器 $D$ 攻击 $G'$：
  • 输入 $y$（长度 $4n$），检查 $y$ 是否每 $n$ 位块相同（即 $y[1..n] = y[n+1..2n] = y[2n+1..3n] = y[3n+1..4n]$）。
  • 如果是，输出“伪随机”；否则输出“随机”。
• 分析：
  • $\Pr[D(G'(s)) = 1] = 1$（因为输出总是重复模式）。
  • $\Pr[D(r) = 1]$（其中 $r$ 均匀随机）为 $r$ 每 $n$ 位块相同的概率，即 $2^{-3n}$（可忽略）。
  • 优势 $\left| \Pr[D(G'(s)) = 1] - \Pr[D(r) = 1] \right| = |1 - \text{negl}(n)| \approx 1$，不是可忽略函数。
• 因此，$G'$ 不是 PRG。

此反例显示，存在 $G$ 是 PRG，但 $G'$ 不是 PRG。

(b) $G''(s) = G(s_1 \cdots s_{n/2})$ 是否一定是伪随机生成器？

答案：否，$G''$ 不一定是伪随机生成器。

解释：

• $G''$ 的输入为 $s$（长度 $n$），但仅使用前一半 $s_1 \cdots s_{n/2}$（长度 $n/2$）作为 $G$ 的输入，输出 $G(s_1 \cdots s_{n/2})$。
• $G$ 是 PRG，因此当输入长度为 $n/2$ 时，输出长度为 $\ell(n/2) \geq 2 \times (n/2) = n$。
• 问题在于拉伸条件：$\ell(n/2)$ 可能等于 $n$（例如，如果 $\ell(m) = 2m$，则 $\ell(n/2) = n$），此时输出长度等于输入长度 $n$，违反 PRG 的拉伸要求（输出必须严格长于输入）。
• 即使计算不可区分性可能成立（因为输出分布等同于 $G$ 在输入长度 $n/2$ 时的输出），拉伸不足本身已导致 $G''$ 不符合 PRG 定义。

反例构造：

• 取 $\ell(m) = 2m$（满足 $\ell(m) \geq 2m$）。
• 定义 $G: \{0,1\}^m \to \{0,1\}^{2m}$ 为 $G(z) = z \| H(z)$，其中 $H$ 是一个安全的 PRG。则 $G$ 是 PRG，因为输出包含真随机部分。
• 现在 $G''(s) = G(s_1 \cdots s_{n/2}) = s_1 \cdots s_{n/2} \| H(s_1 \cdots s_{n/2})$（长度 $n$）。
• 输入长度 $n$，输出长度 $n$，拉伸为 $n/n = 1 \not> n$，不满足拉伸条件。
• 此外，统计距离大：输出分布的支持集大小最多 $2^{n/2}$（因为输入到 $G$ 只有 $n/2$ 位），而输出空间大小为 $2^n$，统计距离至少 $1 - 2^{n/2} / 2^n = 1 - 2^{-n/2}$（不是可忽略函数），因此存在区分器（无界）有显著优势。

此反例显示，当 $\ell(n/2) = n$ 时，$G''$ 不满足 PRG 的拉伸要求。即使在某些 $G$ 下计算安全，但由于“necessarily”要求对所有 $G$ 成立，而存在反例，因此 $G''$ 不一定是 PRG。

12.2

题目

一个密钥函数族 $F_k$ 被称为伪随机置换（PRP），如果满足以下条件：

• 给定密钥 $k$，函数 $F_k(\cdot)$ 和其逆函数 $F_k^{-1}(\cdot)$ 是高效可计算的；
• 对于任意多项式时间的敌手 $\mathcal{A}$：

$\left| \Pr\left( \mathcal{A}^{F_k(\cdot), F_k^{-1}(\cdot)} (1^n) = 1 \right) - \Pr\left( \mathcal{A}^{f_n(\cdot), f_n^{-1}(\cdot)} (1^n) = 1 \right) \right| \leq \text{negl}(n),$

其中 $f_n$ 是一个随机置换。

考虑以下加密方案：

1. 均匀采样密钥 $k$。
2. 对于明文 $x \in \{0, 1\}^{n/2}$（假设 $n$ 为偶数），加密算法 $\text{Enc}_k$ 采样随机数 $r \in \{0, 1\}^{n/2}$，并输出 $F_k(r \| x)$。

假设 $F_k$ 是一个 PRP：

(a) 展示解密算法 $\text{Dec}_k$ 如何工作。
(b) 证明该加密方案在 CPA（选择明文攻击）下是安全的。

解答

(a) 解密算法 $\text{Dec}_k$ 的工作方式

给定密文 $c$（长度为 $n$，因为 $F_k$ 的输出长度是 $n$)，解密算法 $\text{Dec}_k$ 执行以下步骤：

1. 计算逆置换：使用密钥 $k$ 计算 $m = F_k^{-1}(c)$。这里 $m$ 是一个长度为 $n$ 的字符串。
2. 解析明文：将 $m$ 分为两部分：
   • 前 $n/2$ 位是随机数 $r$（在加密过程中生成），
   • 后 $n/2$ 位是原始明文 $x$。
     即 $m = r \| x$。
3. 输出明文：输出后 $n/2$ 位作为明文 $x$。

形式化定义：

$\text{Dec}_k(c) = \text{后 } n/2 \text{ 位} \text{ 的 } F_k^{-1}(c).$

正确性验证：

• 加密时，$\text{Enc}_k(x) = F_k(r \| x)$。
• 解密时，$F_k^{-1}(c) = F_k^{-1}(F_k(r \| x)) = r \| x$。
• 提取后 $n/2$ 位直接得到 $x$，故解密正确恢复明文。

(b) 证明加密方案是 CPA 安全的：

目标是证明该方案满足 IND-CPA 安全性（选择明文攻击下的密文不可区分性）。假设 $F_k$ 是 PRP，如果存在一个多项式时间敌手 $\mathcal{A}$ 能以不可忽略的优势攻破该加密方案的 CPA 安全，则可以构造一个敌手 $\mathcal{D}$ 来攻破 PRP 的安全性，从而导出矛盾。

敌手 $\mathcal{D}$ 的构造（用于攻击 PRP）：
敌手 $\mathcal{D}$ 拥有访问预言机 $\mathcal{O}(\cdot)$ 和 $\mathcal{O}^{-1}(\cdot)$ 的能力，这些预言机要么是 $F_k(\cdot)$ 和 $F_k^{-1}(\cdot)$（真实 PRP），要么是随机置换 $f_n(\cdot)$ 和 $f_n^{-1}(\cdot)$。$\mathcal{D}$ 模拟加密方案的环境给 $\mathcal{A}$，具体步骤如下：

• 步骤 1：模拟加密预言机。
  • 当 $\mathcal{A}$ 查询加密预言机（输入明文 $x \in \{0,1\}^{n/2}$）：
    • $\mathcal{D}$ 采样随机数 $r \leftarrow \{0,1\}^{n/2}$。
    • 查询自己的预言机 $\mathcal{O}$ 得到 $c = \mathcal{O}(r \| x)$。
    • 将 $c$ 返回给 $\mathcal{A}$ 作为密文。
      补充说明： 这完美模拟了 $\operatorname{Enc}_k(\cdot)$，因为真实方案中 $\operatorname{Enc}_k(x) = F_k(r \| x)$。
• 步骤 2：处理挑战阶段。
  • $\mathcal{A}$ 输出两个等长的明文 $x_0, x_1 \in \{0,1\}^{n/2}$。
  • $\mathcal{D}$ 采样随机比特 $b \leftarrow \{0,1\}$ 和随机数 $r \leftarrow \{0,1\}^{n/2}$。
  • 查询预言机 $\mathcal{O}$ 得到挑战密文 $c^* = \mathcal{O}(r \| x_b)$。
  • 将 $c^*$ 发送给 $\mathcal{A}$。
• 步骤 3：处理 $\mathcal{A}$ 的输出。
  • $\mathcal{A}$ 继续访问加密预言机（但不能查询 $c^*$ 的解密），并最终输出一个猜测比特 $b'$.
  • 如果 $b' = b$，则 $\mathcal{D}$ 输出 1（猜测预言机是真实 PRP）；否则输出 0（猜测预言机是随机置换）。

分析 $\mathcal{D}$ 的优势：

• 情况 1：预言机是真实 PRP（即 $\mathcal{O} = F_k$）。
  此时，$\mathcal{D}$ 完美模拟了加密方案的 CPA 游戏。如果 $\mathcal{A}$ 以不可忽略的优势攻破 CPA 安全，则：

  $\Pr\left[\mathcal{D}^{F_k(\cdot),F_k^{-1}(\cdot)}(1^n) = 1\right] = \Pr[\mathcal{A} \text{ 成功}] \geq \frac{1}{2} + \frac{1}{\operatorname{poly}(n)}.$

  其中 $\frac{1}{\operatorname{poly}(n)}$ 是不可忽略的函数（因为 $\mathcal{A}$ 是成功的 CPA 敌手）。
• 情况 2：预言机是随机置换（即 $\mathcal{O} = f_n$）。
  此时，$\mathcal{D}$ 使用随机置换 $f_n$ 模拟加密。设 $\mathcal{A}$ 向加密预言机查询的总次数为 $q(n)$（多项式次），挑战密文为 $c^* = f_n(r \| x_b)$：
  • 如果 $\mathcal{A}$ 在查询中曾输入过点 $r \| x_b$ 到预言机，则它可完美计算 $c^*$ 并猜中 $b$（成功概率为 1）。
  • 否则，由于 $f_n$ 是随机置换，且 $r$ 在挑战阶段是新鲜随机的（未被查询过），$\mathcal{A}$ 无法获得 $x_b$ 的任何信息（密文 $c^*$ 在 $x_0$ 和 $x_1$ 上分布相同），因此成功概率最多为 $\frac{1}{2}$。
  • 敌手 $\mathcal{A}$ 查询到点 $r \| x_b$ 的概率至多为 $\frac{q(n)}{2^{n/2}}$（因为 $r$ 是 $n/2$ 位随机数，空间大小为 $2^{n/2}$)。
    因此：

  $\Pr\left[\mathcal{D}^{f_n(\cdot),f_n^{-1}(\cdot)}(1^n) = 1\right] \leq \Pr[\mathcal{A} \text{ 查询 } r \| x_b] \cdot 1 + \Pr[\mathcal{A} \text{ 未查询 } r \| x_b] \cdot \frac{1}{2} \leq \frac{q(n)}{2^{n/2}} + \frac{1}{2}.$

  由于 $q(n)$ 是多项式而 $2^{n/2}$ 是指数函数，$\frac{q(n)}{2^{n/2}}$ 是可忽略函数 $\operatorname{negl}(n)$，故：

  $\Pr\left[\mathcal{D}^{f_n(\cdot),f_n^{-1}(\cdot)}(1^n) = 1\right] \leq \frac{1}{2} + \operatorname{negl}(n).$

• 比较两种情况：
  $\mathcal{D}$ 作为 PRP 敌手的优势为：

  $\left| \Pr\left[\mathcal{D}^{F_k(\cdot),F_k^{-1}(\cdot)}(1^n) = 1\right] - \Pr\left[\mathcal{D}^{f_n(\cdot),f_n^{-1}(\cdot)}(1^n) = 1\right] \right| \geq \left( \frac{1}{2} + \frac{1}{\operatorname{poly}(n)} \right) - \left( \frac{1}{2} + \operatorname{negl}(n) \right) = \frac{1}{\operatorname{poly}(n)} - \operatorname{negl}(n).$

  该优势是不可忽略的（因为 $\frac{1}{\operatorname{poly}(n)}$ 主导 $\operatorname{negl}(n)$），但这与 $F_k$ 是 PRP 的假设矛盾（PRP 要求优势可忽略）。

结论： 不存在多项式时间敌手 $\mathcal{A}$ 能以不可忽略的优势攻破该加密方案的 CPA 安全。因此，该方案是 CPA 安全的。