Ciphertext-Policy ABE for $\mathsf{NC}^1$ Circuits with Constant-Size Ciphertexts from Succinct LWE

这篇论文提出了一种基于格（Lattice-based）的密文策略属性基加密（CP-ABE）方案，专门针对 NC1 电路访问策略，并实现了常数大小的密文。该方案基于 Wee (CRYPTO 2024) 提出的**简洁 LWE（Succinct LWE）**假设，在标准模型下实现了选择安全性。

以下是该论文的详细技术总结：

1. 研究背景与问题 (Problem)

• 背景：属性基加密（ABE）允许对加密数据进行细粒度的访问控制。CP-ABE 中，密文关联访问策略，密钥关联属性。
• 现有挑战：
  • 现有的 CP-ABE 方案大多基于双线性群，但面临量子攻击风险。基于 LWE（Learning With Errors）的方案虽然抗量子，但在参数效率上存在瓶颈。
  • 传统的 CP-ABE 方案中，密文大小通常与访问策略（电路）的规模（如深度 $d$ 或大小 $s$）或输入长度 $\ell$ 相关，导致密文膨胀。
  • 虽然已有工作（如 [AY20], [DKW21], [Wee25]）尝试优化参数，但往往依赖非标准假设，或者在公钥、密钥或密文大小上未能同时达到最优。
• 核心目标：构建一个基于 LWE 假设的 CP-ABE 方案，支持 NC1 电路访问策略，且密文大小为常数（即独立于电路深度 $d$、大小 $s$ 和输入长度 $\ell$），同时保持公钥和密钥大小的合理性。

2. 方法论 (Methodology)

该方案的核心思想是结合 DKW21 方案（基于线性秘密共享方案 LSSS 的 CP-ABE）与 **Wee25 的矩阵承诺（Matrix Commitment）**技术，并利用 $\ell$-Succinct LWE 假设。

2.1 核心组件

1. $\ell$-Succinct LWE 假设：

   • 这是方案安全性的基础。它断言给定矩阵 $B, W$ 和陷门 $T$（满足 $[I_\ell \otimes B | W] \cdot T = I_\ell \otimes G$），区分 $(B, s^\top B + e, W, T)$ 与 $(B, c, W, T)$ 是困难的。
   • 该假设允许在公参数中包含一个“简洁”的陷门结构，用于生成针对特定矩阵的陷门，而无需泄露原始 LWE 样本的秘密。

2. 矩阵承诺 (Matrix Commitment)：

   • 借鉴 [Wee25]，使用矩阵承诺将 LSSS 矩阵 $M$ 相关的多个矩阵（对应不同属性）压缩为一个常数大小的承诺矩阵 $C$。
   • 承诺关系：$C \cdot V = U - B \cdot Z$，其中 $U$ 是待承诺的矩阵集合，$V$ 是验证矩阵，$Z$ 是打开矩阵。

3. 构造流程：

   • 公钥 (pk)：包含简洁 LWE 的公参数 $(B, W, T)$，以及随机矩阵 $A, \{B_i\}, \{Q_u\}$ 和向量 $y$。
   • 密钥生成 (Keygen)：
     • 用户拥有属性集 $U$。
     • 利用公参数中的陷门 $T$ 和矩阵承诺的验证矩阵 $V$，生成秘密密钥。
     • 关键技巧：对于未授权属性集，挑战者可以利用 $T$ 构造针对特定线性组合矩阵的新陷门，从而在不使用原始主陷门 $td_B$ 的情况下生成合法密钥，避免泄露 LWE 样本信息。
   • 加密 (Enc)：
     • 输入消息 $msg$ 和 LSSS 策略 $(M, \rho)$。
     • 计算承诺矩阵 $C$，该矩阵编码了策略 $M$ 与公钥矩阵的线性组合。
     • 密文由三部分组成：$c_1 = s^\top B + e_1$，$c_2 = s^\top (A + C) + e_2$，$c_3 = s^\top y + msg \cdot \lceil q/2 \rceil + e_3$。
     • 关键点：密文大小仅取决于安全参数，与策略复杂度无关。
   • 解密 (Dec)：
     • 利用 LSSS 的重构系数 $\{w_i\}$。
     • 利用密钥中的 $k_u$ 和承诺的打开矩阵 $Z$，通过线性组合恢复出 $s^\top y$，进而从 $c_3$ 中解码出消息。
     • 解密过程利用了 $C \cdot V = U - B \cdot Z$ 的关系，将 $c_2$ 中的承诺部分还原为策略相关的线性项。

3. 主要贡献 (Key Contributions)

1. 常数大小密文：

   • 提出了首个基于 LWE 假设（具体为 Succinct LWE）的 CP-ABE 方案，其密文大小为 $O(1)$，独立于电路深度 $d$、大小 $s$ 和输入长度 $\ell$。
   • 公钥大小为 $O(s)$（电路大小），但作者指出公钥中大部分元素是均匀随机的，可通过伪随机生成器（PRG）压缩，从而在理论上实现 $O(1)$ 的公钥大小。
   • 密钥大小为 $O(\ell)$（属性数量），但在用户属性较少时可进一步缩减。

2. 最优广播加密 (Optimal Broadcast Encryption)：

   • 作为 CP-ABE 的特例，该方案可转化为针对 $N$ 个用户的广播加密方案。
   • 参数达到最优：密文大小 $|ct| = \text{poly}(\lambda)$（独立于 $\log N$），密钥大小 $|sk| = \text{poly}(\lambda, \log N)$。
   • 通过 PRG 压缩公钥后，总通信开销达到理论下界。

3. 新的安全证明技术：

   • 在安全性证明中，利用 Succinct LWE 中的陷门 $T$，构造了针对矩阵 $[I_{\ell'} \otimes B | W']$ 的陷门（其中 $W'$ 统计上接近均匀分布）。
   • 这使得挑战者能够在不泄露 LWE 样本秘密的情况下，为未授权属性集生成密钥，从而在混合游戏（Hybrid Games）中完成安全归约。

4. 结果与参数 (Results & Parameters)

• 安全性：在标准模型下，基于 poly($\lambda$)-Succinct LWE 假设，实现了选择安全性（Selective Security），且能抵抗无界合谋攻击。
• 参数规模（隐藏了 $\text{poly}(\lambda)$ 因子）：
  • **公钥大小 ($|pk|$)**：$O(s)$（若使用 PRG 压缩则为 $O(1)$）。
  • **密钥大小 ($|sk|$)**：$O(\ell)$（实际取决于用户拥有的属性数量，若为$O(1)$则密钥也为$O(1)$）。
  • **密文大小 ($|ct|$)**：$O(1)$。
• 广播加密参数：
  • $|pk| = N \cdot \text{poly}(\lambda, \log N)$ （可压缩为 $\text{poly}(\lambda)$）。
  • $|sk| = \text{poly}(\lambda, \log N)$。
  • $|ct| = \text{poly}(\lambda)$。

5. 意义与对比 (Significance & Comparison)

• 与 [Wee25] 的对比：
  • 优势：本方案的密文、公钥和密钥大小均独立于电路深度 $d$；广播加密的密文大小独立于用户数 $N$ 的对数 $\log N$；加密过程仅需执行一次矩阵承诺，而非像 [Wee25] 那样对电路进行递归承诺。
  • 劣势：支持的访问策略类较窄（仅限 NC1 电路，而 [Wee25] 支持所有电路）；密钥大小略大（依赖于属性数量 $\ell$）。
• 学术价值：
  • 证明了在抗量子假设下，可以实现真正高效的 CP-ABE，打破了密文大小必须随策略复杂度增长的瓶颈。
  • 为构建高效的后量子广播加密系统提供了新的理论基石。
  • 展示了 Succinct LWE 假设在构造紧凑密码原语中的强大能力。

总结

该论文通过巧妙结合矩阵承诺技术和 Succinct LWE 假设，成功构建了一个具有常数大小密文的 CP-ABE 方案。这一突破不仅优化了基于格的加密方案参数，还直接导出了参数最优的广播加密方案，在抗量子密码学领域具有重要的理论意义和应用前景。