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

### 从LPN、DLIN和PRG实现不可区分混淆 在密码学领域，实现强大的功能加密（FE）和不可区分混淆（iO）是重要的研究目标。本文将围绕预处理随机编码（PRE）展开，介绍其构建过程、面临的挑战以及解决方案。 #### 预处理随机编码（PRE）概述 PRE包含三个主要算法： - **PRE.PreProc(p, x) →(PI, SI)**：预处理算法将输入 $x \in \{0, 1\}^n$ 和随机带 $r$ 转换为在 $\mathbb{Z}_p$ 上的预处理输入 $(PI, SI)$。预处理时间需满足次线性时间简洁性，即 $T_{PreProc} = m^{1 - \epsilon}poly(\lambda)$，且不依赖于后续要编码的电路（仅依赖其大小的上界）。 - **PRE.Encode(C, PI, SI) = π**：编码算法接受大小为 $mpoly(\lambda)$ 的电路 $C$ 和预处理输入 $(PI, SI)$，生成二进制随机编码 $\pi$。$PRE.Encode_C$ 可通过 $\mathbb{Z}_p$ 上的多项式映射计算，在 $PI$ 上为常数度，在 $SI$ 上为2度。 - **PRE.Decode(π) = y**：解码算法从 $\pi$ 中解码出输出 $y = C(x)$。 PRE还保证了不可区分安全性，即只要 $C(x_0) = C(x_1)$，从 $(C, x_0)$ 或 $(C, x_1)$ 生成的 $(PI, \pi)$ 是不可区分的。利用PRE，可轻松构建所需的强大FE： - **FE.SK**：$PHFE.SK_h$，其中 $h(PI, SI) = PRE.Encode_C(PI, SI) = \pi$ - **FE.CT**：$PHFE.CT(PI, SI)$，其中 $(PI, SI) \leftarrow PRE.PreProc(p, x)$ 由于预处理时间为次线性，且PHFE加密时间与预处理输入长度成正比（也是次线性），因此FE加密具有次线性时间简洁性。 #### 构建PRE的挑战 构建NC1电路的PRE面临两个主要挑战： 1. 编码在私有预处理输入 $SI$ 上的度仅为2。 2. 预处理具有次线性时间简洁性。 为解决这些问题，我们从一个已知的具有常数局部性和次线性随机性的NC1随机编码方案开始，并对其进行修改，使其具有度为 $(O(1), 2)$ 的编码。该方案可通过将常数局部性的RE与NC0中的PRG结合得到，编码算法为 $\pi = Encode'_C(x; r' = PRG(r))$，其中随机带长度 $|r| = m^{1 - \tau}poly(\lambda)$。 #### PRE的高层方法 为了将编码在私有预处理输入上的度降低到2，我们借鉴了构建结构化种子PRG的一些思想： - **设置PI**：将公共输入 $PI$ 设置为使用特殊用途同态加密方案对 $x' = x, r$ 进行加密的结果，即 $PI = HEEnc(x')$。 - **设置SI**：$SI$ 包含同态加密的秘密密钥和一些关于加密的“预处理信息”，且 $PI$ 和 $SI$ 需由大小相对于电路 $C$ 为次线性的电路计算得到。 - **编码过程**：编码算法 $Encode$ 首先对 $PI$ 进行同态评估 $Encode'$ 以获得输出加密 $HEEnc(\pi)$，然后使用 $SI$ 对 $HEEnc(\pi)$ 进行解密得到 $\pi$。同态评估 $Encode'$ 在 $PI$ 上的度为 $d$，解密在 $SI$ 上的度为2，因此 $Encode$ 具有度为 $(O(1), 2)$。 #### 通过Fp上的LPN实例化 一种同态加密方案基于Fp上的LPN： $PI = HEEnc(x') = (A, b = sA + e + x' \mod p)$ 其中维度 $dim$ 与 $\lambda$ 多项式相关且相对较小。我们采样 $A \leftarrow \mathbb{Z}_{dim \times |x'|}^p$，$s \leftarrow \mathbb{Z}_{1 \times dim}^p$，误差 $e$ 的每个坐标非零的概率为 $dim^{-\delta}$。 为了进行解密，我们观察到对于每个局部性为 $d$ 的多项式 $h$，有 $h(b - As) = h(x' + e)$。如果在 $SI$ 中包含 $s$