从LPN、DLIN和PRG实现不可区分混淆

### 从LPN、DLIN和PRG实现不可区分混淆 在当今的密码学和计算领域，不可区分混淆技术正逐渐成为研究的热点。它在保护数据隐私、实现安全计算等方面有着巨大的应用潜力。本文将围绕从LPN（Learning Parity with Noise）、DLIN（Decisional Linear）和PRG（Pseudorandom Generator）实现不可区分混淆展开，深入探讨其中涉及的关键技术和概念。 #### 1. 电路转换 在实现特定功能的电路时，我们需要对RAM程序的每一步进行详细检查，并使用合适的子电路替换它们，同时保持整体运行时间不变。由于这个转换过程技术细节较多，我们仅强调其中使用的一些关键工具。 我们广泛使用了几乎线性规模的排序电路以及图灵机到电路的转换方法。例如，在某些情况下，我们需要用电路替换RAM内存查找操作。为此，我们证明了关于RAM查找程序的一个简单引理。 一个以数字 \(N \in \mathbb{N}\) 和 \(q \in \mathbb{N}\) 为索引的RAM查找程序 \(P_{lookup}^{q,N}\)，其结构如下：它接受 \(q\) 个索引 \(\{i_1, \ldots, i_q\}\) 和一个数据库 \(DB \in \{0, 1\}^N\) 作为输入，并输出 \(\{DB[i_1], \ldots, DB[i_q]\}\)。我们证明了这个程序可以通过一个电路高效实现： **引理3**：设 \(q, N \in \mathbb{N}\)。一个RAM查找程序 \(P_{RAM}^{q,N}\)（从大小为 \(N\) 的数据库中查找 \(q\) 个索引）可以由一个大小为 \(O((q + N)poly(\log_2(q \cdot N)))\) 的高效均匀可生成的布尔电路实现，其中 \(poly\) 是某个多项式。 #### 2. 预备知识 在深入研究具体技术之前，我们先介绍一些贯穿全文的符号和概念。 - **安全参数**：我们用 \(\lambda\) 表示安全参数。对于任何分布 \(X\)，\(x \leftarrow X\) 表示从分布 \(X\) 中采样一个值 \(x\) 的过程。对于一个集合 \(X\)，\(x \leftarrow X\) 表示从 \(X\) 上的均匀分布中采样 \(x\)。对于整数 \(n \in \mathbb{N}\)，\([n]\) 表示集合 \(\{1, \ldots, n\}\)。 - **多项式**：当我们提到安全参数的多项式时，指的是在非负输入上取正值的常数度多项式。我们用 \(poly(\lambda)\) 表示满足非负性要求的任意多项式。 - **Landau符号**：我们使用标准的Landau符号，同时引入 \(\tilde{O}\) 符号。对于任何函数 \(a(n, \lambda)\) 和 \(b(n, \lambda)\)，如果 \(a(n, \lambda) = O(b(n, \lambda)poly(\lambda, \log_2 n))\) 对于某个多项式 \(poly\) 成立，我们称 \(a = \tilde{O}(b)\)。 - **可忽略函数**：一个函数 \(negl : \mathbb{N} \to \mathbb{R}\) 是可忽略的，如果 \(negl(\lambda) = \lambda^{-\omega(1)}\)。如果 \(negl(\lambda) = 2^{-\lambda^{\Omega(1)}}\)，则称该函数是亚指数小的。 - **向量和矩阵**：我们用粗体字母（如 \(\mathbf{b}\) 和 \(\mathbf{u}\)）表示向量，用大写粗体字母（如 \(\mathbf{A}\) 和 \(\mathbf{M}\)）表示矩阵。对于任何 \(k \in \mathbb{N}\)，\(\mathbf{v}^{\otimes k} = \mathbf{v} \otimes \cdots \otimes \mathbf{v}\)（\(k\) 次）表示标准张量积，它包含了 \(\mathbf{v}\) 中变量的所有次数恰好为 \(k\) 的单项式。 #### 3. 多项式的多线性表示和在 \(\mathbb{Z}_p\) 上的表示 从布尔函数分析中可以得出一个直接的事实：每个 \(NC^0\) 函数 \(F : \{0, 1\}^n \to \{0, 1\}\) 都可以由一个唯一的常数度多线性多项式 \(f \in \mathbb{Z}[x = (x_1, \ldots, x_n)]\) 表示，该多项式将 \(\{0, 1\}^n\) 映射到 \(\{0, 1\}\)。 有时，我们会考虑将这样的多项式 \(f \in \mathbb{Z}[x]\) 映射到 \(\mathbb{Z}_p[x]\) 上的多项式 \(g\)，其中 \(p\) 是一个素数。这可以通过将 \(f\) 的系数模 \(p\) 约简，然后在 \(\mathbb{Z}_p\) 上计算多项式来实现。注意，对于每个 \(x \in \{0, 1\}^n\)，有 \(g(x) = f(x) \bmod p\)，因为对于这样的 \(x\)，\(f(x) \in \{0, 1\}\)。此外，给定任何 \(NC^0\) 函数 \(F\)，找到这些表示需要多项式时间。 #### 4. 计算不可区分性 计算不可区分性是密码学中的一个重要概念，它用于衡量两个集合在计算上是否难以区分。 **定义4（\(\epsilon\) - 不可区分性）**：我们称两个集合 \(X = \{X_{\lambda}\}_{\lambda \in \mathbb{N}}\) 和 \(Y = \{Y_{\lambda}\}_{\lambda \in \mathbb{N}}\) 是 \(\epsilon\) - 不可区分的，其中 \(\epsilon : \mathbb{N} \to [0, 1]\)，如果对于每个概率多项式时间敌手 \(A\)，对于每个足够大的 \(\lambda \in \mathbb{N}\)，有： \(\left| \Pr_{x \leftarrow X_{\lambda}}[A(1^{\lambda}, x) = 1] - \Pr_{y \leftarrow Y_{\lambda}}[A(1^{\lambda}, y) = 1] \right| \leq \epsilon(\lambda)\) 如果 \(\epsilon(\lambda) = negl(\lambda)\) 对于某个可忽略函数 \(negl\) 成立，我们称这两个集合是计算不可区分的；如果 \(\epsilon(\lambda) = 2^{-\lambda^c}\) 对于某个正实数 \(c\) 成立，我们称这两个集合是亚指数不可区分的。 #### 5. 假设 我们使用三个假设来构建本文中的新组件，下面介绍其中两个假设：LPN和PRG。关于DLIN的正式定义，请参考相关文献。 **定义5（\(\delta\) - LPN假设）**：设 \(\delta \in (0, 1)\)。我们称 \(\delta\) - LPN假设成立，如果以下条件成立：对于任何常数 \(\eta_p > 0\)，任何函数 \(p : \mathbb{N} \to \mathbb{N}\) 使得对于每个 \(\ell \in \mathbb{N}\)，\(p(\ell)\) 是一个 \(\ell^{\eta_p}\) 位的素数，任何常数 \(\eta_n > 0\)，我们设置 \(p = p(\ell)\)，\(n = n(\ell) = \ell^{\eta_n}\)，\(r = r(\ell) = \ell^{-\delta}\)，并且要求以下两个分布是计算不可区分的： \(\{ (A, b = s \cdot A + e) | A \leftarrow \mathbb{Z}_p^{\ell \times n}, s \leftarrow \mathbb{Z}_p^{1 \times \ell}, e \leftarrow D_r^{1 \times n}(p) \}_{\ell \in \mathbb{N}}\) \(\{ (A, u) | A \leftarrow \mathbb{Z}_p^{\ell \times n}, u \leftarrow \mathbb{Z}_p^{1 \times n} \}_{\ell \in \mathbb{N}}\) 此外，如果上述两个分布是亚指数不可区分的，我们称亚指数 \(\delta\) - LPN成立。 **定义6（伪随机生成器）**：一个拉伸为 \(m(\cdot)\) 的伪随机生成器是一个布尔函数 \(PRG : \{0, 1\}^* \to \{0, 1\}^*\)，它将 \(n\) 位输入映射到 \(m(n)\) 位输出（也称为拉伸），并且可以由一个均匀概率多项式时间机器计算。对于任何非均匀概率多项式时间敌手 \(A\)，存在一个可忽略函数 \(negl\)，使得对于所有 \(n \in \mathbb{N}\)，有： \(\left| \Pr_{r \leftarrow \{0, 1\}^n}[A(PRG(r)) = 1] - \Pr_{z \leftarrow \{0, 1\}^m}[A(z) = 1] \right| < negl(n)\) 如果 \(PRG\) 可以由一个均匀高效可生成的 \(NC^0\) 电路实现，我们称 \(PRG\) 是 \(NC^0\) 中的。如果 \(m(n) = n^{1 + \Omega(1)}\)，我们称 \(PRG\) 具有多项式拉伸。如果 \(negl(n) = O(\exp(-n^{\Omega(1)}))\)，我们称 \(PRG\) 是亚指数安全的。 #### 6. 预处理多项式编码（PPE） ##### 6.1 函数类 \(F_{PPE}\) 在正式定义PPE方案之前，我们先介绍函数类 \(F_{PPE}\)。首先，我们定义 \(n\) 个变量上的 \(d\) 次单项式模式 \(Q\)，它是一个次数至多为 \(d\) 的单项式集合。 **定义8（\(d\) - 单项式模式和单项式）**：对于整数 \(d > 0\) 和 \(n > d \in \mathbb{N}\)，我们称 \(Q\) 是 \(n\) 个变量上的 \(d\) - 单项式模式，如果 \(Q = \{Q_1, \ldots, Q_m\}\)，其中对于每个 \(i \in [m]\)，有 \(0 < |Q_i| \leq d\)，并且每个 \(Q_i\) 是 \([n]\) 的一个不同子集。对于任何输入 \(x \in \{0, 1\}^n\) 和集合 \(Q \subseteq [n]\)，定义 \(Mon_Q(x) = \prod_{i \in Q} x_i\) 为 \(x\) 中对应于集合 \(Q\) 的单项式。 因此，对于任何输入 \(x\)，\(n\) 个变量上的 \(d\) - 单项式模式 \(Q = \{Q_1, \ldots, Q_m\}\) 定义了 \(m\) 个次数至多为 \(d\) 的单项式。我们用 \(\Gamma_{d,n}\) 表示 \(n\) 个变量上的所有 \(d\) - 单项式模式的集合。 **定义9（多项式类 \(F_{PPE}\)）**：对于常数 \(d \in \mathbb{N}\)，多项式类 \(F_{PPE,d} = \{F_{PPE,d,n_{P