格上的前向安全组加密：原理与实现

### 格上的前向安全组加密：原理与实现 #### 1. 引言 在当今数字化时代，信息安全至关重要，尤其是在涉及群体信息交互的场景中。组加密（GE）作为一种基本的匿名原语，类似于组签名，它能够隐藏一组认证用户中的有效解密者，同时在开放权威机构（OA）的控制下对任何不当行为保持问责。自Kiayias、Tsiounis和Yung（KTY）开创组加密的先河以来，它在众多实际场景中得到了广泛应用，比如阻止嵌入恶意软件的加密电子邮件、构建遗忘检索存储系统以及设计分层组签名等。 然而，密钥暴露是安全密码系统面临的最致命威胁之一。一旦发生密钥暴露，系统的预期安全性将被彻底破坏。为了减轻这种潜在损害，人们研究了许多技术，包括秘密共享、门限密码学和主动密码学等。其中，前向安全机制提供了一种高效且实用的策略，适用于交互式和非交互式场景。其核心思想是将密码系统的生命周期划分为多个连续的离散时间段，然后通过单向密钥更新函数，利用当前密钥和时间段递归地演化后续密钥。这样，用户可以定期刷新密钥，并且攻击者无法仅通过暴露的信息了解先前的密钥。 在组签名和组加密中，密钥暴露的破坏性更为严重。在组签名中，持有暴露密钥的人可以冒充整个组生成有效签名，使得难以判断签名的真实性。在组加密中，攻击者可以使用暴露的密钥解密所有针对该用户的密文，破坏消息的保密性。如果OA的密钥被泄露，组加密所期望的匿名性也将丧失。因此，本文首次考虑了组加密中的前向安全性，并基于格假设提供了具体的实现方案。 #### 2. 研究贡献 - **形式化模型与安全定义**：通过在KTY模型中引入适当的程序和预言机，为前向安全组加密提供了形式化模型和安全定义。 - **格上的具体实现**：在标准模型下，基于格假设提供了具体的实现方案，即使在密钥暴露的环境中，也能确保消息的保密性和匿名性。 #### 3. 相关工作 隐私保护密码学在过去几十年中一直是一个非常活跃的研究领域。组加密作为一种基本的匿名技术，近年来受到了广泛关注。许多学者提出了不同的组加密方案，如Kiayias等人提出的模块化设计方案、Cathalo等人将交互式方案改进为非交互式方案、Aimani等人提出的更实用的方案、Libert等人提出的具有公共可追溯性的变体以及Izabach`ene等人构建的无隐蔽信道的可追溯组加密方案。然而，这些方案大多基于数论假设，在量子攻击下是脆弱的。直到Libert等人提出了第一个基于格的方案，这种情况才有所改变。但所有这些方案都没有考虑密钥暴露的问题，本文的研究弥补了这一不足。 #### 4. 预备知识 ##### 4.1 符号说明 - 对于正整数$n$，用$[n]$表示集合$\{1, ..., n\}$，用$[0, n]$表示集合$\{0, 1, ..., n\}$。 - 所有向量用小写粗体字母表示，矩阵用大写粗体字母表示。 - 对于向量$b \in R^n$和矩阵$B \in R^{n×m}$，用$\|b\|$和$\|B\| = \max_{i\leq m}\|b_i\|$分别表示它们的欧几里得$l_2$范数。 - 用$\tilde{B}$表示矩阵$B$的Gram - Schmidt正交化（如果$B$是满列秩的）。 - 如果集合$S$是有限的，用$U(S)$表示$S$上的均匀分布，用$x \leftarrow D$表示根据分布$D$进行采样。 ##### 4.2 格 使用符号$\Lambda_q^{\perp}(A) := \{e \in Z^m | A \cdot e = 0_n \mod q\}$和$\Lambda_q^u(A) := \{e \in Z^m | A \cdot e = u \mod q\}$表示格。用$D_{L,\sigma,c}$表示支持集为$L$、中心为$c \in R^m$、参数为$\sigma > 0$的离散高斯分布，其中$D_{L,\sigma,c}(x) = \frac{\rho_{\sigma,c}(x)}{\rho_{\sigma,c}(L)}$，$\rho_{\sigma,c}(x) = \exp(-\pi\|x - c\|^2/\sigma^2)$是$R^m$上的相关高斯函数。当$c = 0$时，简记为$D_{L,\sigma}$。 为了构建基于格的方案，需要一些格技术，包括陷门生成、高斯采样和固定维度的格基委托。 - **引理1**：存在一个概率多项式时间（PPT）算法TrapGen，输入整数元组$(n, m, q)$（$q \geq 2$且$m \geq \Omega(n \log q)$），输出矩阵$A \in Z_q^{n×m}$和相关基$T_A$，满足$\|\tilde{T}_A\| \leq O(\sqrt{n \log q})$，且$A$与$U(Z_q^{n×m})$的统计距离可忽略不计。 - **引理2**：给定整数$m > n$，$q \geq 2$，向量$u \in Z_q^n$和$c \in R^m$，设$T_A$是矩阵$A \in Z_q^{n×m}$的短范数基，$\sigma \geq \|\tilde{T}_A\|\omega(\sqrt{\log m})$，则： - 从$D_{\Lambda_q^u(A),\sigma}$中采样的向量$b$满足$\|b\| \leq \sqrt{m}\sigma$的概率极大。 - 存在PPT算法SampleGausssian(·)和SamplePre(·)，分别从$D_{\Lambda^{\perp}_q(A),\sigma,c}$和$D_{\Lambda_q^u(A),\sigma}$中采样向量。 - 存在PPT算法RandBasis(·)，输入格$\Lambda^{\perp}_q(A)$的基$S$和高斯参数$\sigma \geq \|\tilde{S}\| \cdot \omega(\sqrt{\log n})$，输出一个新的基$S'$，满足$\|\tilde{S}'\| \leq \sigma\sqrt{m}$，且输出分布与在相同参数约束下另一个基$T$的RandBasis(T, σ)的输出分布统计接近。 - **引理3**：给定整数$m > n$，$q > 2$，高斯参数$\sigma > 0$和$Z_q$上的可逆分布$D_{m×m}$，设$A \in Z_q^{n×m}$和相关陷门$T_A \in Z_q^{m×m}$，则： - 给定$\Lambda^{\perp}_q(A)$的规范基，存在PPT算法SampleR，输出的矩阵$R$的分布与$D_{m×m}$统计接近。 - 给定参数$\sigma_{\ell} \geq \|\tilde{T}_A\| \cdot (\sigma_R\sqrt{m} \omega(\log^{1/2} m))^{\ell} \cdot \omega(\log m)$和矩阵$R_1, ..., R_{\ell} \in D_{m×m}$，设$R_{|\ell} = R_{\ell} \cdot R_{\ell - 1} \cdots R_1$，存在PPT格基委托算法BasisDel(·)，输入$A$、$T_A$、$\sigma_{\ell}$、$R_{|\ell}$，输出$\Lambda^{\perp}_q(AR_{|\ell}^{-1})$的基$T'$，其分布与相同格的任何基$T$的RandBasis(T, $\sigma_{\ell}$)的输出分布统计接近。 - 存在PPT模拟算法SampleRwithBasis(·)，输入任何矩阵$B \in Z_q^{n×m}$，输出矩阵$R \in Z_q^{m×m}$，其分布与$D_{m×m}$统计接近，且生成的$\Lambda^{\perp}_q(BR^{-1})$的基$T'$满足$\|\tilde{T}'\| \leq \sigma_R/\omega(\sqrt{\log m})$。 ##### 4.3 计算问题 方案的安全性依赖于以下两个计算格问题的难度： - **SIS问题**：给定正整数$n$、$m$、$q$和实数$\beta > 0$，SIS$_{n,m,q,\beta}$问题要求对于任何$A \leftarrow U(Z_q^{n×m})$，找到一个非零向量$x \in Z^m$，其范数有界为$\beta$，使得$A \cdot x = 0$。对于适当选择的参数，标准最坏情况格问题SIVP$_{\gamma}$可以归约为平均情况问题SIS$_{n,m,q,\beta}$。 - **LWE问题**：给定正整数$n$、$m$、$q$，秘密$s \in Z_q^n$和$Z$上的离散概率分布$\chi$，设$A_{s,\chi}$是$(a, a^T \cdot s + e) \in Z_q^n × Z_q$的概率分布，其中$a \leftarrow U(Z_q^n)$，$e \leftarrow \chi$。LWEn,q,χ问题（决策版本）要求区分$m$个来自$A_{s,\chi}$的样本和$m$个来自$U(Z_q^n × Z_q)$的样本。对于素数幂$q$，给定有界离散分布$\chi$，存在从SIVP$\tilde{O}(nq/B)$问题到LWEn,q,χ问题的有效归约。 ##### 4.4 支持高效协议的签名 Libert等人提出了一种安全的签名方案，该方案支持高