简化不可区分混淆构造的小记

### 简化不可区分混淆构造的小记 #### 1. 引言 不可区分混淆（iO）是密码学界的核心目标，其主要目的是让功能等价的电路难以区分。它有众多应用，如功能加密、可搜索加密或非交互式密钥交换协议等。iO 可通过多线性映射、多输入功能加密或紧凑功能加密等方式实现，如今也存在基于成熟假设的安全方案。 功能加密（FE）能对加密数据进行有针对性的访问。使用公共参数（mpk），可将指定域中的输入 inp 加密为密文 CT；使用 FE 的秘密密钥（msk），能为以多项式规模电路 C 表示的任何函数 f 颁发功能密钥 skf。当用 skf 解密 CT 时，可恢复出 C(inp)。其主要安全概念是不可区分性，即对于两个不同消息 m0 和 m1，只要 C(m0) = C(m1)，任何计算受限的对手在拥有 skf、mpk 和 CT 的情况下，都难以区分 CT 加密的是 m0 还是 m1。 乍一看，不可区分混淆与功能加密并无关联。其接口规范如下：考虑两个功能等价的电路 C0 和 C1，它们都实现同一函数 f。不可区分混淆器 iO 随机选取其中一个（如 Cb）作为输入，输出 C，使得任何计算受限的对手都难以区分 C 是由 C0 还是 C1 得到的。我们将针对非常受限的 P 子类的 iO 混淆器称为“耗尽”混淆器。 #### 2. 研究成果 - **与现有 iO 方案的对比**：本研究从高层角度遵循了[25]提出的方法，即使用混淆器计算功能密文，并颁发功能密钥来解密 iO 的输出。但存在重大差异，[25]使用通用的指数高效混淆器（XiO）构建紧凑功能加密（cFE）方案，然后通过一系列复杂变换构建 iO。而本研究专注于为非常受限的电路类构建不可区分混淆器，不使用 XiO，而是直接构建，假设存在加密复杂度为 NC1 的 FE、通用电路（Uc）、评估复杂度为 NC1 的可刺破伪随机函数（pPRF）和仿射行列式程序（ADP）。 - **主要思路**：为 Uc 生成功能密钥，然后使用 ADP 为形式为“C ||inp”的消息生成功能密文。根据 FE 的正确性，有 FE.Dec(FE.KGen(msk, Uc), FE.Enc(mpk, C ||inp)) = C(inp)。ADP 硬编码了 FE 方案的主公共密钥和（可刺破）PRF 密钥，将生成功能密文，由评估 Uc 的功能密钥进行解密。混淆器的内部工作原理如下： ```plaintext iO.Setup(C ) := [ADP.Setup(mpk, C , k), FE.KGen(msk, Uc)] iO.Eval(inp) := FE.Dec(skUc, ADP.Eval(FE.Enc(mpk, C ||inp; pPRF(k, inp)))) ``` - **不可区分性证明的直觉**：对于上述混淆器的证明，通过对所有输入进行混合（类似于[25]）。考虑两个功能等价的 C0 和 C1，利用 ADP 的不可区分性，将 pPRF 的密钥替换为在混合游戏输入中被刺破的密钥；再利用 pPRF 的安全性，将当前挑战点生成 FE 密文所用的随机性替换为真正的随机硬币；接着利用功能加密对当前输入的不可区分性，将编码 C0||inp∗ 的密文替换为编码 C1||inp∗ 的密文；最后再换回来。显然，混合的数量在输入长度上是指数级的。 #### 3. 如何使用 ADP 混淆特定类别的电路 仿射行列式程序（ADP）旨在实现更高效和直接的混淆器。原始构造是启发式的，在一般情况下已被简单的反例攻破。本研究描述了如何使用增强分支程序实例化不同类型的 ADP，从而对底层图结构进行拓扑变换。更重要的是，讨论了证明特定类电路安全性所需的约束条件。 对于长度为 n 的二进制输入，ADP 是一组 n + 1 个元素在 F2 中的方阵，第一个矩阵 T0 称为“基”矩阵。它们一起可对可表示为 NC1 电路的函数 f 进行编码和评估。评估过程是计算基矩阵与输入相关矩阵子集之和的行列式： ```plaintext f(m) = det [T0 + ∑(i=1 to n) inpi · Ti] ``` 其中 inpi 是输入 inp 的第 i 位，运算在 F2 上进行。 构建 ADP 矩阵时，应考虑 NC1 中的函数，因为其分支程序具有多项式规模。分支程序由起始节点、两个终端节点（0 和 1）和一组可变大小的规则节点组成。起始节点有两条潜在的出边，无入边；终端节点有零条或多条入边，无出边；规则节点至少有一条入边和两条出边。每个非终端节点与输入位 inpi 相关联，根据 inpi 的值选择相应的出边。如果固定输入（如 ⃗0），可从分支程序的邻接矩阵得到 ADP 基矩阵的核心，记为 G0。 接下来，可得到“差异”矩阵。例如，为评估输入 1||0...||0，从该输入对应的邻接矩阵中减去基矩阵 G0，得到“差异”矩阵 G1 = G1||0...||0 - G0||0...||0（一般情况下，Gi 表示第 i 位设为 1 时的差异矩阵）。经过简单的后处理步骤后，应用随机化阶段，将在 Fm×m2 上采样的左右可逆矩阵 L 和 R 分别乘以 n + 1 个矩阵。 #### 4. ADP 在方案中的使用 本方案的思路是使用 ADP 生成 FE 密文。为此，FE 的加密过程本身必须在 NC1 中，FE.Enc 使用的随机硬币通过 pPRF 生成，pPRF 本身也必须在 NC1 中。 由于每个 ADP 输出单个位，我们使用 ℓ 个这样的电路，其中 ℓ 是 FE 密文的长度。这个功能密文将支持对 t 位长度函数的解密。 在 ADP 的不可区分性证明中，一个主要问题是 pPRF 在正常密钥和被刺破密钥下的评估电路结构不同。为解决这个问题，我们人为地将 pPRF 的输入域扩展一位，在以 0 开头的输入处刺破密钥，同时始终在以 1 开头的输入上进行评估，以保证能在整个原始域上评估 pPRF。在证明中，我们将切换到在点“1||inp∗”处刺破密钥，同时保持分支程序的拓扑结构不变，这是 ADP 作为“耗尽”混淆器不可区分性证明的关键。 为证明 iO 混淆器的安全性，我们使用嵌套的混合方法。遍历整个输入空间，对于每个挑战输入，从编码第一个电路 C0 切换到表示 C1。对于每个挑战 inp∗，首先利用 ADP 混淆器的不可区分性将密钥切换为在当前输入处被刺破的密钥；然后利用 pPRF 的安全性将计算挑战密文 c 所用的随机性项替换为真正的随机硬币；一旦使用了新鲜的随机硬币，就利用 FE 的安全性切换到编码 C1 的设置；最后进行反向混合，撤销与 pPRF 密钥相关的更改并减小限制 ρ。 需要注意的是，k、C0、C1 或 ρ 等值非常敏感，泄露它们会导致简单的区分器。IND - ADP 不可区分性的一个目标是间接保护这些变量，称为非输入可变变量（nimv）。可以将电路视为接受两个输入：i 和 nimv