基于格的前向安全组加密方案解析

### 基于格的前向安全组加密方案解析 #### 1. 方案概述 前向安全组加密（FSGE）方案旨在实现对密钥暴露和量子计算攻击的防护，同时为组用户和开放权限机构（OA）提供独立的密钥演化机制。该方案通过将ABB加密修改为基于格的BTE，并结合适当的构建块，实现了消息保密性和匿名性。 #### 2. 安全性与正确性 - **安全性**：方案的安全性基于SIS和LWE难题假设，通过经典归约方法可证明其匿名性和消息保密性。 - **正确性**：方案的正确性源于对特定时间周期生成的ABB HIBE密文的正确解密，尽管可能存在一些解密错误，但在一定条件下，解密过程能以压倒性概率返回正确消息。 #### 3. 方案设计 - **时间周期与密钥演化**：将给定的生命周期 $T = 2^d - 1$ 划分为 $T$ 个离散时间周期 $[0, T - 1]$，构建一个具有 $2^d - 1$ 个节点的完整二叉树，每个节点 $w_t$ 对应一个时间周期 $t$。初始密钥 $sk_0$ 可以递归地演化为 $sk_t$，其表示为一个节点密钥栈。 - **密钥更新机制**：用户和OA分别有独立的密钥更新算法，确保前向安全性。 - **加密过程**：加密消息 $m$ 时，生成密文 $\Psi$，并通过交互式零知识证明确保密文的有效性。 - **解密过程**：用户使用 $sk_i,t$ 解密消息，OA使用 $sk_{OA},t$ 揭示密文的预期用户身份。 #### 4. 具体算法流程 - **SETUPinit(1λ)**：设置公共参数，包括安全参数、时间周期、矩阵采样等。 ```plaintext 给定安全参数 λ，设 N = 2^s 为最大预期组大小，T = 2^d 为时间周期大小。 设整数 n = O(λ)，素数 q = Õ(n^(2d + ℓ + 3.5))，设置 k = ⌈log q⌉，m = 2nk，构建离散分布 χ 有界于 B = √nω(log n)。 选择参数 σ = Ω(√n log q log n)，构建离散高斯分布 D_Z,σ 上界为 β = σ · ω(log n)。 选择强不可伪造的一次性签名 OTS = (Gen, Sig, Ver)，其验证密钥位于 Z_√n_p 且二进制长度为 ℓ，素数 p = O(n^0.5)。 采样 4d + 2ℓ 个可逆的 Z_n×m_q 矩阵 {R_i,j}，用于用户和OA的密钥更新。 获取用于零知识论证系统的公共参数 parCOM。 选择随机矩阵 F ← Z_2n×nmk_q，用于哈希用户公钥。 选择矩阵 U_rec ← U(Z_n×m_q) 和 U_oa ← U(Z_n×s_q)，分别用于接收者和OA的加密。 输出公共参数 pp。 ``` - **SETUPGM(pp)**：生成GM的公钥和私钥。 ```plaintext 运行 TrapGen(n, q) 生成随机矩阵 G 和短基 SG 作为陷门。 采样随机矩阵 G_0, G_1, D_0, D_1 和向量 u。 创建GM的公钥 pk_GM 和私钥 sk_GM。 ``` - **SETUPOA(pp)**：生成OA的公钥和私钥。 ```plaintext 使用 TrapGen(n, q) 生成随机矩阵 P 和短陷门 S_0。 形成OA的密钥对 (pk_OA, sk_OA) 和初始秘密栈密钥 sk_{OA},0。 ``` - **UKGEN(pp)**：用户生成自己的密钥对。 ```plaintext 用户 U_i 运行 TrapGen(n, q) 生成随机矩阵 A_i 和相关短陷门 T_i。 形成密钥对 (p_k_i, s_k_i) 和初始 ```