基于Evasive格假设的最优广播加密与CP-ABE

论文概述

本文解读 EuroCrypt 2022（CCF A）上的一篇论文：Optimal Broadcast Encryption and CP-ABE from Evasive Lattice Assumptions（[Wee22-EuroCrypt]）。

该论文基于 Evasive 格假设，在格上构造了一个 CP-ABE（密文策略属性基加密）方案，并通过引入 Tensor LWE 解决了多密钥场景下的安全性问题。

一个简单的 CP-ABE 方案

作者首先构造了一个简洁的 CP-ABE 方案：

$$\begin{aligned} \mathsf{mpk} &= \mathbf{B}_1 \leftarrow \mathbb{Z}_q^{n \times m}, \quad \mathbf{A} \leftarrow \mathbb{Z}_q^{n \times \ell m}, \quad \mathbf{u}^\top \leftarrow D_{\mathbb{Z},\chi}^m \\ \mathsf{ct}_f &= (\mathbf{s}\mathbf{A}_f \mathbf{u}^\top + \mu \cdot \mathbf{g} + \mathsf{noise}, \quad \mathbf{s}\mathbf{B}_1 + \mathsf{noise}), \quad \mathbf{s} \leftarrow \mathbb{Z}_q^n \\ \mathsf{sk}_{\mathbf{x}} &= \mathbf{B}_1^{-1}(\mathbf{A} - \mathbf{x} \otimes \mathbf{G}) \end{aligned}$$

其中 $\mathbf{A}_f$ 是由策略 $f$ 和公开矩阵 $\mathbf{A}$ 派生的结构化矩阵，$\mathbf{G}$ 是 gadget 矩阵。

为什么只有 One-Key 安全性？

这个方案的核心问题在于：密钥缺乏足够的熵。

如果敌手同时拥有两个不同属性 $\mathbf{x}$ 对应的密钥 $\mathsf{sk}_{\mathbf{x}}$，安全性就会被打破。文中给出的攻击示例：

• $\mathbf{x}_1 = 0^\ell$（全零向量）
• $\mathbf{x}_2 = 1^\ell$（全一向量）

拥有这两个密钥后，敌手可以提取出足够的信息来破坏方案安全性。

张量积的引入：增强密钥熵

为了解决上述问题，作者使用张量积向密钥中嵌入了一个随机向量 $\mathbf{r}$：

$$\mathsf{sk}_{\mathbf{x}} = \mathbf{B}_1^{-1}((\mathbf{A} - \mathbf{x} \otimes \mathbf{G}) \otimes \mathbf{r}^\top), \quad \mathbf{r}^\top$$

相应地，密文也需要调整以支持解密：

$$\mathsf{ct}_f = (\mathbf{s}(\mathbf{A}_f \mathbf{u}^\top \otimes \mathbf{I}) + \mu \cdot \mathbf{g} + \mathsf{noise}, \quad \mathbf{s}\mathbf{B}_1 + \mathsf{noise})$$

解密原理

解密时，左乘密文中的 $\mathbf{s}\mathbf{B}_1 + \mathsf{noise}$ 与密钥中的 $\mathbf{B}_1^{-1}(\cdots)$ 结合，可以还原出：

$$\mathbf{s}((\mathbf{A} - \mathbf{x} \otimes \mathbf{G}) \otimes \mathbf{r}^\top) + \mathsf{noise}$$

安全性分析与 Tensor LWE 假设

敌手的视角

敌手拥有以下信息：

$$\begin{aligned} \mathsf{ct}_f &= (\mathbf{s}(\mathbf{A}_f \mathbf{u}^\top \otimes \mathbf{I}) + \mu \cdot \mathbf{g} + \mathsf{noise}, \quad \mathbf{s}\mathbf{B}_1 + \mathsf{noise}) \\ \{\mathsf{sk}_{\mathbf{x}_i}\} &= \{\mathbf{B}_1^{-1}((\mathbf{A} - \mathbf{x}_i \otimes \mathbf{G}) \otimes \mathbf{r}_i^\top), \quad \mathbf{r}_i^\top\} \end{aligned}$$

敌手可以计算出：

$$\{\mathbf{s}((\mathbf{A} - \mathbf{x}_i \otimes \mathbf{G}) \otimes \mathbf{r}_i^\top) + \mathsf{noise}\}$$

如果这一项是伪随机的，敌手就无法从中获取 $\mathbf{s}$ 的信息，也就无法恢复明文 $\mu$。

Tensor LWE 假设

这一步的逻辑与标准 LWE 类似，但形式不同，无法直接归约到已有的 LWE 变体。因此作者提出了 Tensor LWE 假设：

Assumption (Tensor LWE)

设 $n, m, q, \ell, Q \in \mathbb{N}$ 为格参数，$\gamma, \chi > 0$ 为高斯参数。$\forall \mathbf{x}_i \in {0,1}^\ell, i \in [Q]$，有：

$$\mathbf{A}, \{\mathbf{s}((\mathbf{A} - \mathbf{x}_i \otimes \mathbf{G}) \otimes \mathbf{r}_i^\top) + \mathbf{e}_i, \mathbf{r}_i^\top\}_{i \in [Q]} \approx_c \mathbf{A}, \{\$, \mathbf{r}_i^\top\}_{i \in [Q]}$$

其中 $\mathbf{A} \leftarrow \mathbb{Z}q^{n \times \ell m}$，$\mathbf{s} \leftarrow \mathbb{Z}_q^{mn}$，$\mathbf{e}_i \leftarrow D{\mathbb{Z},\chi}^{\ell m}$，$\mathbf{r}i^\top \leftarrow D{\mathbb{Z},\gamma}^m$，$$$ 表示均匀分布。

Tensor LWE 与 BGG+14 编码的关系

从形式上看，Tensor LWE 中包含形如 $\mathbf{s}(\mathbf{A} - \mathbf{x} \otimes \mathbf{G})$ 的项，这与 BGG+14 编码有着密切联系。

归约到 LWE

Tensor LWE 本身是一个新的困难假设，但其部分变体可以归约到标准 LWE：

1. 变体一（[Wee22-EuroCrypt]）：将 $\mathbf{x}_i \otimes \mathbf{G}$ 替换为 $\mathbf{x}_i \otimes \mathbf{I}_m$，可归约到 LWE
2. 变体二（[ARYY23-Crypto]）：当所有 $\mathbf{x}_i = \mathbf{0}$ 时，同样可归约到 LWE

这些归约证明为 Tensor LWE 假设的可信度提供了理论支撑。

与 [ARYY23-Crypto] 的关系

本文提出的 Tensor LWE 假设和 one-key CP-ABE 方案，为后续 [ARYY23-Crypto] 的工作奠定了基础。后者在本文的基础上：

• 进一步扩展到多输入 ABE 场景
• 证明了 Tensor LWE 的更多归约性质
• 构造了更丰富的密码学原语

个人思考

这篇论文的亮点在于：

1. 张量积作为密钥熵的来源：通过张量积将随机性嵌入结构化密钥，是一种巧妙的代数技巧
2. 新假设的提出：Tensor LWE 虽然是新假设，但其形式与 LWE 的紧密联系增强了可信度
3. 从 one-key 到 multi-key 的路径：展示了如何通过增加密钥熵来提升安全性

对于格密码研究者而言，Tensor LWE 是一个值得关注的新困难假设，它在后续的 ABE、广播加密等方案中展现了广泛的应用潜力。

参考文献

• [Wee22-EuroCrypt] Hoeteck Wee, “Optimal Broadcast Encryption and CP-ABE from Evasive Lattice Assumptions”, Eurocrypt 2022
• [ARYY23-Crypto] Shweta Agrawal et al., “Constant Input Attribute Based (and Predicate) Encryption from Evasive and Tensor LWE”, Crypto 2023
• [BGG+14] Boneh et al., “Key Homomorphic PRFs and Their Applications”, Crypto 2014