多实例随机性提取技术解析

### 多实例随机性提取技术解析 #### 1. 背景与基础概念 在加密领域，每个用户拥有无界数量的密文在标准模型中是不可行的。这是因为模拟器在不知道消息的情况下，需要模拟除密钥之外的所有内容。对于敌手存储的密文，模拟器要查询底层消息并生成密钥，使这些密文能解密为给定消息。由于不可压缩性，密钥长度至少要和消息数量一样大。因此，我们转而考虑每个用户有界密文的情况。 对于有状态加密方案，将支持每个用户一个密文的方案升级为支持多个密文很简单，只需让密钥成为一次性密钥列表。在对称密钥设置中，可利用 $k$ -wise 独立哈希函数使其无状态。而在公钥设置中，实现无状态构造则需要更多工作，目前没有简单的通用构造方法，我们会展示如何修改现有构造以实现每个用户多个密文。 在深入探讨多实例随机性提取之前，我们先了解一些基础概念和符号表示： - **符号表示**：对于 $n \in N$，$[n]$ 表示有序集 $\{1, 2, \ldots, n\}$。大写粗体字母表示矩阵 $M$，小写粗体字母表示向量 $v$。$M_{i,j}$ 表示矩阵 $M$ 的第 $i$ 行第 $j$ 列元素，$v_i$ 表示向量 $v$ 的第 $i$ 个元素。 - **引理 1（Johnson 界）**：设 $C \subseteq \Sigma^n$ 且 $|\Sigma| = q$ 是任意 $q$ 元纠错码，相对距离 $p_0 = 1 - (1 + \rho) \frac{1}{q}$（$\rho > 0$），即对于任意两个不同值 $x, y \in C$，$x$ 和 $y$ 之间的汉明距离至少为 $p_0 \cdot n$。那么对于任意 $\delta > \sqrt{\rho(q - 1)}$，存在 $L \leq \frac{(q - 1)^2}{\delta^2 - \rho(q - 1)}$，使得该码是 $(p_1 = (1 - (1 + \delta) \frac{1}{q}), L)$ - 列表可解码的，即对于任意 $y \in \Sigma^n_q$，与 $y$ 的汉明距离在 $p_1n$ 以内的码字最多有 $L$ 个。 - **引理 2（区分意味着预测）**：对于任意随机函数 $D : \{0, 1\}^n \times \{0, 1\}^m \to \{0, 1\}$，存在随机函数 $P : \{0, 1\}^n \to \{0, 1\}^m$，使得对于任意联合分布的随机变量 $(A, B)$ 在 $\{0, 1\}^n \times \{0, 1\}^m$ 上，如果 $Pr[D(A, B) = 1] - Pr[D(A, U_m) = 1] \geq \epsilon$，则 $Pr[P(A) = B] \geq \frac{1}{2^m}(1 + \epsilon)$。 - **平均最小熵**：对于两个联合分布的随机变量 $(X, Y)$，$X$ 在 $Y$ 条件下的平均最小熵定义为 $H_{\infty}(X|Y) = -\log E_{y \leftarrow Y}[\max_x Pr[X = x|Y = y]]$。 - **引理 3**：对于随机变量 $X, Y$，其中 $Y$ 取值于大小为 $T$ 的集合，有 $H_{\infty}(X|Y) \geq H_{\infty}(X, Y) - \log T \geq H_{\infty}(X) - \log T$。 - **提取器**：函数 $Extract : \{0, 1\}^n \times \{0, 1\}^d \to \{0, 1\}^m$ 是 $(k, \epsilon)$ 强平均最小熵提取器，如果对于所有联合分布的随机变量 $(X, Y)$，其中 $X$ 取值于 $\{0, 1\}^n$ 且 $H_{\infty}(X|Y) \geq k$，则 $(U_d, Extract(X; U_d), Y)$ 与 $(s, U_m, Y)$ $\epsilon$ - 接近，其中 $U_d$ 和 $U_m$ 分别是长度为 $d$ 和 $m$ 的均匀随机字符串。 #### 2. 多实例随机性提取的定义 一个函数 $Ext : \{0, 1\}^n \times \{0, 1\}^d \to \{0, 1\}^m$ 是 $(t, \alpha, \beta, \epsilon)$ - 多实例提取器，如果满足以下条件： 设 $X = (X_1, \ldots, X_t)$ 是由块 $X_i \in \{0, 1\}^n$ 组成的随机变量，且 $H_{\infty}(X) \geq \alpha \cdot tn$。那么存在与 $X$ 联合分布的随机变量 $I_X$，$I_X$ 取值于 $[t]$ 的子集 $I$，且 $|I| \geq \beta \cdot t$，使得： $(S_1, \ldots, S_t, Ext(X_1; S_1), \ldots, Ext(X_t; S_t)) \approx_{\epsilon} (S_1, \ldots, S_t, Z_1, \ldots, Z_t)$ 其中 $S_i \in \{0, 1\}^d$ 是均匀随机且独立的种子，对于 $i \in I_X$，$Z_i \in \{0, 1\}^m$ 是独立均匀随机采样的，而对于 $i \notin I_X$，$Z_i = Ext(X_i; S_i)$。 简单来说，如果使用“多实例提取”提取器，用独立种子从 $t$ 个相关块（联合熵率为 $\alpha$）中分别提取，那么看到所有提取输出与用均匀值替换精心选择的 $\beta$ 部分是不可区分的。 #### 3. 提示提取器 提示提取器是多实例随机性提取中的重要概念，一个函数 $Ext : \{0, 1\}^n \times \{0, 1\}^d \to \{0, 1\}^m$ 是 $(δ, L, h, Q)$ - 提示提取器需满足以下两个条件： - **列表可解码性**：若将 $ECC(x) = (Ext(x; s))_{s \in \{0, 1\}^d}$ 视为字母表 $\Sigma = \{0, 1\}^m$ 上的 $(2^d, n)$ 纠错码，那么该码是 $(p = 1 - (1 + δ)2^{-m}, L)$ - 列表可解码的，即对于任意 $y \in \Sigma^{2^d}$，与 $y$ 的汉明距离在 $p \cdot 2^d$ 以内的码字最多有 $L$ 个。 - **成对独立提示**：存在函数 $hint : \{0, 1\}^n \times \{0, 1\}^{\tau} \to \{0, 1\}^h$ 以及 $rec_0$ 和 $rec_1$，使得： - 对于所有 $x \in \{0, 1\}^n$，$r \in \{0, 1\}^{\tau}$，若定义 $\sigma = hint(x; r)$，$\{s_1, \ldots, s_Q\} = rec_0(r)$，$\{y_1, \ldots, y_Q\} = rec_1(\sigma, r)$，则对于所有 $i \in [Q]$，有 $Ext(x; s_i) = y_i$。 - 在均匀随机的 $r \leftarrow \{0, 1\}^{\tau}$ 下，$Q$ 个种子 $\{s_1, \ldots, s_Q\} = rec_0(r)$ 各自在 $\{0, 1\}^d$ 上均匀分布且成对独立。 下面介绍两种提示提取器的构造： - **构造 1：Hadamard** 定义 $Ext : \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}^m$ 为 $Ext(x; s) = \langle x, s \rangle$，这里将 $x$ 和 $s$ 视为 $\hat{n} := \frac{n}{m}$ 维的 $F_{2^m}$ 元素，所有运算都在 $F_{2^m}$ 上进行。种子长度 $d = n$ 比特，输出长度为 $m$ 比特。 对于任意 $h, δ > 0$，当 $Q \geq 2^{h - m}$ 且 $L \leq \frac{2^{2m}}{\delta^2}$ 时，上述 $Ext$ 是 $(δ, L, h, Q)$ - 提示提取器。 - **构造 2：Hadamard ◦ Reed - Muller** 定义 $Ext(f;