基于Evasive LWE和Tensor LWE的常数输入ABE方案

论文概述

本文解读 Crypto 2023（CCF A）上的一篇论文：Constant Input Attribute Based (and Predicate) Encryption from Evasive and Tensor LWE（[ARYY23-Crypto]）。

该论文基于 Evasive LWE 和 Tensor LWE 困难假设，构造了一个多输入属性基加密（Multi-Input ABE）方案。这是格密码学领域的一项重要进展，为在格上构建功能更丰富的加密方案提供了新的思路。

核心构造思路

基本框架

作者首先采用了 [Wee22-EuroCrypt] 的方法，利用张量积向密钥中嵌入随机数：

$$sk_y = B^{-1}((A_2 - y \otimes G) \otimes r^\top), \quad r^\top$$

解密时，左乘密文中的 $sB + \text{noise}$ 即可得到：

$$s((A_2 - y \otimes G) \otimes r^\top) + \text{noise}$$

与函数输入向量 $x$ 相关的项被直接嵌入密文：

$$s((A_1 - x \otimes G) \otimes r^\top) + \text{noise}$$

解密时可以计算出：

$$s(([A_1 \| A_2] - [x\|y] \otimes G) \otimes r^\top) + \text{noise}$$

利用 BGG+14 编码即可得到 $s(A_f \otimes r^\top) + \text{noise}$（满足 $f(x, y) = 0$）。密钥中再提供一个类似于 $A_f^{-1}(G)$ 的项，即可实现解密。

安全性证明的挑战

上述构造在安全证明时遇到了问题：

• $A_f^{-1}(P)$ 中的 $A_f$ 是高度结构化的矩阵
• Evasive LWE 中的 $B$ 是均匀随机矩阵

两者之间存在本质差异，无法直接归约。

解决方案

作者再次借鉴 [Wee22-EuroCrypt] 的密文构造，将密文中的 $s(Gu^\top \otimes I) + \text{noise}$ 替换为 $s(A_f u^\top \otimes I) + \text{noise}$。由于是 KPABE，密文与 $f$ 无关，实际上是让：

$$sk_f = B^{-1}(A_f u^\top \otimes I)$$

再结合密文中的 $sB + \text{noise}$ 还原出 $s(A_f u^\top \otimes I) + \text{noise}$。

随机性保障的调整

上述调整会导致 $s((A_1 - x \otimes G) \otimes I) + \text{noise}$ 和 $s(A_f u^\top \otimes I) + \text{noise}$ 的随机性无法得到保障，因为其形式与 Tensor LWE 不符（缺少与 $r$ 的张量积）。

针对第一个问题，作者的做法是：

• 将 $s((A_1 - x \otimes G) \otimes I) + \text{noise}$ 替换为 $s((A_1 - x \otimes G) \otimes I) + \text{noise} + s_0(A_0 \otimes I)$
• $A_0$ 为固定矩阵
• 在密文中添加 $s_0(A_0 \otimes r^\top) + \text{noise}$
• 敌手只能计算出与 $r$ 做张量积的项 $s((A_1 - x \otimes G) \otimes r^\top) + \text{noise}$

针对第二个问题，不能使用同样的方法（敌手可做多次密钥查询，相同固定矩阵无意义），因此：

• 将 $s(A_f u^\top \otimes I) + \text{noise}$ 替换为 $s(A_f u^\top \otimes I) + s_1(D \otimes t^\top) + \text{noise}$
• 为适配 Tensor LWE，进一步替换为 $s(A_f u^\top \otimes I) + s_1(D \otimes t^\top \otimes I) + \text{noise}$

由此得到最终方案。

Tensor LWE 到 LWE 的归约

论文还证明了当所有向量 $x$ 为 0 时，Tensor LWE 可以归约到标准 LWE。该变种 Tensor LWE 定义如下：

Assumption 1 (Tensor LWE with $x = 0$)

设 $n, m, q, \ell, Q \in \mathbb{N}$ 为格参数，$\gamma, \chi > 0$ 为高斯参数：

$$A, \{s(I_n \otimes r_i^\top)A + e_i, r_i\}_{i \in [Q]} \approx_c A, \{\$, r_i\}_{i \in [Q]}$$

其中 $A \leftarrow \mathbb{Z}q^{n \times \ell m}$，$s \leftarrow \mathbb{Z}_q^{mn}$，$e_i \leftarrow D{\mathbb{Z},\chi}$，$ri \leftarrow D{\mathbb{Z},\gamma}$，$$$ 表示均匀分布。

归约证明思路

归约的关键在于将 $s$ 主动拆解为多个张量积之和，利用张量积性质化简，从而转换为含有 LWE 样本的形式：

$$\begin{aligned} s(I_n \otimes r_i^\top)A + e_i &= \left(\sum_{j=1}^{m} s_j \otimes \epsilon_j\right)(I_n \otimes r_i^\top)A + e_i \\ &= \sum_{j=1}^{m} s_j \cdot r_i[j] \cdot A + e_i \\ &= \sum_{j=1}^{m} r_i[j] \cdot (s_j \cdot A + e_j') + e_i \\ &\approx \sum_{j=1}^{m} r_i[j] \cdot \$ + e_i \\ &= \$ \end{aligned}$$

其中 $\epsilon_j$ 表示 $\mathbb{Z}_q^m$ 上的第 $j$ 个标准单位向量。证明过程依次利用了：

1. 张量积性质 — 将外积展开为内积形式
2. LWE 归约 — 将内部项替换为 LWE 样本
3. Noise Flooding — 通过噪声淹没消除残余项

个人思考

这篇论文的技巧性很强，尤其是对 Tensor LWE 的运用。几个值得关注的点：

1. 张量积作为工具：通过张量积在密钥和密文中嵌入结构化信息，是一种优雅的代数技巧
2. 安全证明中的”补丁”策略：通过引入额外的噪声项和固定矩阵来弥补归约中的间隙
3. Tensor LWE 的独立价值：其到 LWE 的归约证明本身就是一个有意义的结果

这些技术为未来在格上构造更复杂的密码学原语（如功能加密、谓词加密等）提供了新的工具箱。

参考文献

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