支持快速转发的前向安全加密技术解析

### 支持快速转发的前向安全加密技术解析 #### 1. 支持无界轮次的方案 为了支持无界数量的轮次，并将初始化运行时间减少到 $O(1)$，可以应用一系列高度递增的 GGM 树的思想。这些树的根可以使用前向安全的伪随机数生成器（PRNG）推导得出，比如基于 PRG.Expand 的常见构造。 在树 $GGM_t$ 中，更新操作会在轮次到达子树 $T_{t - 1}$ 之前完成扩展。由于这个子树有 $2^{t - 1}$ 个更多的叶子节点，我们可以利用这段时间来初始化下一棵树 $GGM_{t + 1}$，推导其最左边的路径，并将其共路径的加密信息存储在公告板上。 #### 2. 可快速转发的可更新公钥加密（FF - UPKE） FF - UPKE 使用任何更新同态的可更新公钥加密（H - UPKE）方案，并围绕所谓的累积更新思想构建。累积更新是指聚合一系列单个更新的更新密文。我们使用更新图来决定生成哪些累积更新，以平衡发送者的开销和接收者的快速转发能力。 ##### 2.1 更新同态的可更新公钥加密（H - UPKE） H - UPKE 是可更新公钥加密的一种特殊情况，除了密钥生成算法 $(pk_1, sk_1, pp) \leftarrow KeyGen(1^{\kappa})$、消息加密算法 $c \leftarrow Encrypt(pk_i, m)$ 和消息解密算法 $m \leftarrow Decrypt(sk_i, c)$ 外，还提供以下结构： 1. **更新密文**：由加密的更新消息组成，即 $up_{i + 1} \leftarrow UpdEnc(pk_i, \delta_{i + 1})$，其中 $\delta_{i + 1} \leftarrow UpdGen(pp)$ 是基于公共参数 $pp$ 采样得到的。 2. **更新消息**：是秘密密钥空间中的元素，该空间在某个运算符 $\star$ 下构成一个群。 3. **秘密密钥更新**：根据 $sk_{i + 1} = sk_i \star \delta_{i + 1}$ 更新秘密密钥。 4. **更新加密的同态性**：存在一个算法 $Upd - Comb(up, up')$ 可以同态地组合在相同公钥 $pk_i$ 下加密的两个更新。 使用简写符号 $\Delta[j, \ell] := (\delta_{j + 1} \star \cdots \star \delta_{\ell})$，同态性确保我们可以从两个部分更新 $UpdEnc(pk_i, \Delta[j, k])$ 和 $UpdEnc(pk_i, \Delta[k, \ell])$ 计算出等同于 $UpdEnc(pk_i, \Delta[j, \ell])$ 的加密结果。 H - UPKE 方案由一组算法 $(KeyGen, Encrypt, Decrypt, UpdGen, UpdEnc, UpdDec, UpdatePK, Upd - Comb)$ 组成，其中秘密密钥空间 $SK$ 构成一个半群。这些算法的定义如下： - **密钥生成算法**：$(pk_1, sk_1, pp) \leftarrow KeyGen(1^{\kappa})$，输出初始密钥对 $sk_1$ 和 $pk_1$ 以及公共参数 $pp$。 - **加密算法**：$c \leftarrow Encrypt(pk_i, m)$。 - **解密算法**：$m \leftarrow Decrypt(sk_i, c)$。 - **更新采样算法**：$\delta_{i + 1} \leftarrow UpdGen(pp)$，生成 $\delta_{i + 1} \in SK$。 - **公钥更新算法**：$pk_{i + 1} \leftarrow UpdatePK(pk_i, \delta_{i + 1})$。 - **更新加密算法**：$up_{i}^j \leftarrow UpdEnc(pk_i, \delta_j)$，其中 $j > i$。 - **更新组合算法**：$Upd_{i}[j, \ell] \leftarrow Upd - Comb(Upd_{i}[j, k], Upd_{i}[k, \ell])$。 - **更新解密算法**：$\Delta_{i}[j, \ell] \leftarrow UpdDec(sk_i, Upd_{i}[j, \ell])$。 **正确性和安全性**： - **正确性**：通过两个独立的属性来形式化。第一个属性要求 $(Encrypt, Decrypt)$ 和 $(UpdEnc, UpdDec)$ 分别是其各自消息空间的正确加密和解密算法对。第二个属性是关于同态性，要求 $Upd - Comb$ 的输出必须正确解密为底层更新秘密的乘法结果，即 $\Delta[j, k] \star \Delta[k, \ell] = UpdDec(sk_i, Upd - Comb(UpdEnc(pk_i, \Delta[j, k]), UpdEnc(pk_i, \Delta[k, \ell])))$。 - **安全性**：要求 IND - CPA 安全，其 IND - CPA 游戏与常规 UPKE 类似，但考虑了更新机制的特殊结构。具体游戏如下： ```plaintext Game UPKE IND - CPA Initialization b ←$ {0, 1} safe ←true chall ←false n ←1 (pk, sk, pp) ←KeyGen(1κ) return pk Oracle Corrupt if chall ∧safe then return sk Oracle Update Input: r1, r2 ∈R ∪{⊥} if r1 = ⊥∨r2 = ⊥then r1 ←$ R r2 ←$ R safe ←true n ←n + 1 δ ←UpdGen(pp; r1) up ←UpdEnc(pk, δ; r2) pk ←UpdatePK(pk, δ) sk ←sk ⋆δ return (pk, up) Oracle Challenge Input: m0, m1 ∈M if ¬chall ∧|m0| = |m1| then c ←Encrypt(sk, mb) safe ←false chall ←true return c Finalization Input: b′ ∈{0, 1} return b = b′ ``` 一个 UPKE 方案被称为 IND - CPA 安全，如果任何多项式时间概率敌手 $A$ 赢得上述游戏的概率是可忽略的。 通过对标准模型的 UPKE 方案进行微小修改，可以得到基于 DDH 或 LWE 假设的 H - UPKE 方案实例。但这两种构造都有一些限制：基于 LWE 的方案支持有限数量的同态操作，最多支持聚合 $q$ 个原子更新；基于 DDH 的构造支持先验无界数量的聚合，但聚合更新的解密需要 $O(\sqrt{n})$ 的局部计算时间，其中 $n$ 是底层更新的数量。 ##### 2.2 更新图 决定生成哪些累积更新是 FF - UPKE 构造的关键部分。如果插入的累积更新太少，$LeapSK - Idx(i, j) \approx j - i$ 将失去快速转发属性；如果插入太多，$UpdatePK$ 需要从公告板读写线性数量的元素。 我们将累积更新的插入问题重新表述为一个图论问题，并将原子（非快速转发）更新纳入图中。 **定义**：设 $\alpha, \beta, \gamma : \mathbb{N} \to \mathbb{N}$。一个 $(\alpha, \beta, \gamma)$ - 更新图 $G = (N, E)$ 是一个有向无环图，具有以下属性： 1. $\forall i \in \mathbb{N} : (i, i + 1) \in E$。 2. $\forall (i, j) \in E : i < j$。 3. $\forall n \in \mathbb{N} : deg_{in}^G(n) \leq \alpha(n)$。 4. $\forall n \in \mathbb{N} : diam(G_n) \leq \beta(n)$。 5. $\forall n \in \mathbb{N} : |active_G(n)| \leq \gamma(n)$，其中 $active_G(n) := \{i \in [n - 1] | \exists j > n : (i, j) \in E\}$，$(G_n)_{n \in \mathbb{N}}$ 是前缀图序列，$G_n := ([n], E_n)$ 且 $E_n := E \cap [n]^2$。 不同参数对构造效率的影响如下： |参数|影响| |----|----| |$\beta(j)$|$LeapSK$ 所需的更新消息数量的上限| |$active_G(n) \leq \gamma(n)$|当发送者使用 $UpdatePK$ 启动第 $i$ 个轮次时，需要扩展的累积更新集合| |入度|对应轮次的“最终”更新数量| 为了使更新图对我们的构造有用，需要能够高效计算。具体来说，需要计算每个节点 $i$ 的 $E_{in}^G(i)$ 和 $active_G(i)$ 集合，以及任意节点 $i$ 和 $j$ 之间的短路径。 一个 $(\alpha, \beta, \gamma)$ - 更新图 $G = (N, E)$ 由一对确定性算法 $(G.Eval, G.Path)$ 实现，如果： - $G.Eval(n)$ 在 $O(poly(log n))$ 时间内输出 $E_{in}(n)$ 和 $active(n)$。 - $G.Path(i, j)$ 在 $O(poly(\beta(j) \cdot j))$ 时间内输出从节点 $i$ 到节点 $j$ 的路径 $e$，使得 $|e| \leq \beta(j)$。 下面是更新图相关操作的流程图： ```mermaid graph LR A[开始] --> B[计算E_in和active集合] B --> C{是否需要路径} C -- 是 --> D[计算短路径] C -- 否 --> E[结束] D --> E ``` #### 2.3 通用构造方案 基于更新同态的可更新公钥加密（H - UPKE）方案和更新图，我们可以构建一个可快速转发的可更新公钥加密（FF - UPKE）方案。 **发送方操作**： 当发送方 $j$ 选择相应的更新秘密 $\delta_{j + 1}$ 时，除了将 $pk_j$ 更新为 $pk_{j + 1}$，还会进行以下操作： 1. 生成一个新的密文 $Up[j, j + 1]$，该密文在公钥 $pk_j$ 下对 $\delta_{j + 1}$ 进行加密。 2. 对于 $active(j + 1) \cup E_{in}(j + 1)$ 中的每个 $i$，从公告板获取 $Up[i, j]$，并利用 H - UPKE 的更新同态属性计算密文 $Up[i, j + 1]$，然后将其发布到公告板上。 **接收方操作**： 如果接收方知道密钥 $sk_i$，并希望跳转到某个密钥 $sk_j$（$j > i$），则会执行以下步骤： 1. 在更新图中计算一条从 $i = i_0$ 到 $i_d = j$ 的短“跳跃路径” $i = i_0 \to i_1 \to \cdots \to i_d = j$。 2. 从公告板检索 $d$ 个密文 $\{Up[i_k, i_{k + 1}]\}$。 3. 使用 $sk_i = sk_{i_0}$ 解密 $Up_{i_0, i_1}$，得到 $\Delta[i_0, i_1]$。 4. 计算 $sk_{i_1} := sk_{i_0} \star \Delta[i_0, i_1]$。 5. 重复步骤 3 - 4 $d$ 次，最终“追上” $sk_j = sk_{i_d}$。 以下是该方案的正式描述： ```plaintext Protocol Fast - Forwardable UPKE KeyGen(1κ) BBinit[·] ←⊥ (pkH - UPKE, skH - UPKE, ppH - UPKE) ←H - UPKE.KeyGen(1κ) pk ←(1, pkH - UPKE, ppH - UPKE) BB[·, ·] ←⊥ pk ←(1, pkH - UPKE, ppH - UPKE, BB) sk ←(1, skH - UPKE) return (pk, sk, BBinit) Encrypt(pk, m) parse (·, pkH - UPKE, ·) ←pk parse (·, pkH - UPKE, ·, ·) ←pk c ←H - UPKE.Encrypt(pkH - UPKE, m) return c Decrypt(sk, c) parse (·, skH - UPKE) ←sk m ←H - UPKE.Encrypt(skH - UPKE, c) return m UpdatePK(pk, BB) parse (n, pkH - UPKE, ppH - UPKE) ←pk parse (n, pkH - UPKE, ppH - UPKE, BB) ←pk n ←n + 1 BB′[·, ·] ←⊥ // Generate the regular update δ ←H - UPKE.UpdGen(pp) pk′H - UPKE ←H - UPKE.UpdatePK(pk, δ) up(n−1,n) ←H - UPKE.UpdEnc(pk, δ) // Update all active cumulative updates (In, A) ←G.Eval(n) for all i ∈A ∪In \ {n - 1} do up(i,n−1) ←BB[i, n - 1] up(i,n) ←H - UPKE.Upd - Comb(up(i,n−1), up(n−1,n)) BB′[i, n] ←up(i,n) BB′[n - 1, n] ←up(n−1,n) pk′ ←(n, pk′H - UPKE, ppH - UPKE) return (pk′, BB′) BB′′[·, ·] ←⊥ BB′′[n - 1, n] ←up(n−1,n) pk′ ←(n, pk′H - UPKE, ppH - UPKE, BB′) return (pk′, BB′′) UpdateSK(sk, BB) parse (n, skH - UPKE) ←sk n ←n + 1 δ ←H - UPKE.UpdDec(skH - UPKE, BB[n - 1, n]) skH - UPKE ←skH - UPKE ⋆δ sk′ ←(n, skH - UPKE) return sk′ LeapSK(sk, j, BB) parse (n, skH - UPKE) ←sk if j ≤n then return ⊥ e ←G.Path(n, j) for (u, v) ∈e do δ ←H - UPKE.UpdDec(skH - UPKE, BB[u, v]) skH - UPKE ←skH - UPKE ⋆δ n ←j sk′ ←(n, sk′H - UPKE) return sk′ UpdatePK - Idx(n) I ←∅ (In, A) ←G.Eval(n + 1) for all i ∈A ∪In \ {n} do I ←I ∪{(i, n)} return I UpdateSK - Idx(n) return {(n, n + 1)} LeapSK - Idx(n, j) e ←G.Path(n, j) I ←∅ for (u, v) ∈e do I ←I ∪{(u, v)} return I ``` **单发送方变体**： 当该方案部署在单发送方环境中，如两方安全消息传递方案时，可以进行一些调整以实现不同的存储/带宽权衡。由于接收方只会使用 $(i, j) \in E$ 的元素，发送方可以选择只上传 $E_{in}(n)$ 中的元素，将正在进行的累积更新作为本地状态的一部分保留。 这种变体的优点是： 1. 存储需求为 $O(\gamma + \alpha(n))$。 2. $UpdatePK$ 不需要从公告板读取任何内容，即 $UpdatePK - Idx(n) = \emptyset$，可能减少延迟。 以下是单发送方变体的流程图： ```mermaid graph LR A[发送方选择更新秘密] --> B[更新公钥] B --> C[生成新密文] C --> D{是否需要扩展累积更新} D -- 是 --> E[计算并上传累积更新] D -- 否 --> F[结束] E --> F ``` **正确性和效率**： 该构造的正确性直接源于底层 H - UPKE 方案的正确性。更新图的各种参数直接影响方案的效率，具体如下： |操作|效率指标| |----|----| |$UpdatePK$|$|UpdatePK - Idx(n)| \leq \gamma(n + 1)$，$|BB_{up}| \leq \gamma(n + 1) + 1$，需要 $O(\gamma(n + 1))$ 次与底层方案相同的加密操作| |$UpdateSK$|$|UpdateSK - Idx(n)| = 1$，需要 $O(1)$ 次与底层方案相同的加密操作| |$LeapSK$|$|LeapSK - Idx(n, j)| \leq \beta(j)$，需要 $O(\beta(j))$ 次与底层方案相同的加密操作| 单发送方方案的私钥大小与底层 H - UPKE 方案大致相同，公钥大小约为底层方案的 $\gamma(n)$ 倍（考虑本地存储），除了 $|UpdatePK - Idx(n)| = 0$ 和 $|BB_{up}| \leq \alpha(n + 1)$ 外，效率相同。 **安全性**： 该 FF - UPKE 方案的安全性直接源于底层 H - UPKE 方案的安全性。如果底层 H - UPKE 方案是 IND - CPA 安全的，那么 FF - UPKE 方案也是 IND - CPA 安全的。 #### 3. 总结 快速转发是前向安全加密的一个引人注目的特性，在实际相关的公告板模型中，快速转发可以以很小的额外成本实现。 我们构建了一个可快速转发的流密码，该密码保持恒定的本地状态，每次更新操作的运行时间恒定。同时，我们提出了一个从更新同态的 UPKE 方案构建可快速转发的可更新公钥加密方案的通用方法，填补了前向安全公钥加密（PKE）和更高效的可更新公钥加密（UPKE）之间的差距。 虽然目前的实例化方案还不十分实用，但这种新颖的 FF - UPKE 构造可能最终会产生性能显著优于前向安全 PKE 的构造，解决实际公钥加密中在选择前向保密性和快速转发之间的困境。未来，构建高效的更新同态 UPKE 方案是一个值得探索的问题。