后妥协安全成本的研究与分析

### 后妥协安全成本的研究与分析 在当今的网络安全领域，连续组密钥协议（CGKA）在保障群组通信安全方面扮演着重要角色。然而，这些协议在实现后妥协安全（PCS）时，其通信成本是一个关键问题。本文将围绕这一问题展开，深入探讨相关的界限、证明以及克服下界的方法，并介绍一些相关的工作和预备知识。 #### 1. 界限分析 在研究中，我们主要关注实现后妥协安全的CGKA协议的通信成本下界，并引入了一种新的协议CoCoALight。我们以用户为实现后妥协安全所需创建的密文数量来衡量协议成本，同时也会考虑各方恢复所需的轮数。 ##### 1.1 界限设定 - **模型设定**：我们考虑用户不知道在任何给定通信轮次中谁被破坏或谁会更新，且由对手安排每轮谁进行更新的情况。同时，我们引入了“随机破坏”模型（RC）和“无随机破坏”模型（¬RC）。在RC模型中，用户被破坏时其整个秘密状态和本地随机性都会泄露给对手；而在¬RC模型中，仅秘密状态会泄露。大多数协议在较强的RC模型中被证明是安全的，而下界在¬RC模型中更强。 - **下界**：用户在其状态保证恢复之前所需进行的更新次数k起着关键作用。我们的安全游戏由用户数量n和k参数化。对手安排每轮谁更新，并且要求在任何时候，只要过去被破坏的每个方自上次破坏以来至少被要求更新k次，组密钥就是安全的。我们的下界大约是$n^{1 + 1/k} \cdot k / \log(k)$。这意味着如果我们希望每个用户的发送者通信成本为小对数级，就需要允许对数级的恢复轮数。特别是，如果坚持恒定的轮数，每个用户的平均成本将为$n^{1/k}$量级。 - **上界**：我们引入的CoCoALight协议是CoCoA的改进和推广，它能在$k \in [4, 2 \lceil \log(n) \rceil + 1]$轮内实现PCS。该协议的成本为$k \cdot n^{1 + 2/(k - 1)}$，与下界在$ \log(k) / n^{1/(k - 1)}$因子内匹配。对于$k$为$\log(n)$量级的情况，我们的协议仅比最优值差一个$\log(\log(n))$因子。 以下是不同协议的上界和下界对比表格： | 类型 | 方案 | 通信成本 | 轮数 | 随机破坏 | 参考 | | --- | --- | --- | --- | --- | --- | | 上界 | TreeKEM及相关 | $n^2$ | 2 | RC | [10] | | 上界 | Bienstock, Dodis, Rösler | $n^2$ | 2 | ¬RC | [12] | | 上界 | CoCoA在$k - 1\sqrt{n}$ - 元树上 | $n k^2 k - 1\sqrt{n}$ | k | RC | 相关章节 | | 上界 | CoCoA在2 - 元树上 | $n \log(n)^2$ | $\log(n)$ | RC | [2] | | 上界 | CoCoALight在$(k - 1)/2\sqrt{n}$ - 元树上 | $n k (k - 1)/2\sqrt{n}$ | k | RC | 相关章节 | | 下界 | 无限制 | $n^2$ | 2 | ¬RC | [12] | | 下界 | NDW, NNE, PCU∗ | $n \log(n) / \log(\log(n))$ | $\log(n)$ | ¬RC | Cor. 5 | | 下界 | NDW, NNE, PCU∗ | $\varepsilon \cdot n \cdot (1 + \varepsilon)k - 1\sqrt{\alpha_{\varepsilon}n} \cdot k / \log(k)$ | k | ¬RC | Cor. 5 | #### 1.2 证明思路 - **下界证明**：为了证明下界，我们首先表明，如果协议能在k轮内从c次破坏中恢复，那么存在某个用户的成本为$c^{1/k}$。特别是当$c = \Theta(n)$时，成本为$\Theta(n^{1/k})$。我们通过分析集合系统的大小变化来直观理解这一点。然后，我们将证明对于$c = \Theta(n)$次破坏，对手可以通过安排更新，使得$1 / \log(k)$比例的用户在每轮被迫接近最大成本，从而加起来达到$n^{1 + 1/(k - 1)} \cdot k / \log(k)$。具体的对手安排方式是，在每轮之前，对手调查每个用户如果在下一轮被要求更新的成本，然后选择$1 / \log(k)$比例的用户，这些用户要么成本非常小，要么成本大致相同。 - **上界证明**：我们通过遵循[22]设定的框架来证明协议的安全性，该框架将CGKA协议的自适应安全性降低到图上的游戏。首先定义一个安全谓词，它捕获了应保证安全性的设置（即每个被破坏的用户自上次破坏以来执行了k次更新）。然后，我们通过为执行中的每个组密钥关联一个恢复图，证明满足安全谓词的密钥不会因用户破坏而泄露。协议的安全性由此通过该框架得出，与先前的工作类似。 #### 1.3 克服下界的方法 证明重要协议的下界有多个目的，一方面可以告诉我们何时落入下界模型的构造无法进一步改进；另一方面，也可以提示我们在哪里寻找克服这些下界的构造。 - **更强大的构建块**：我们考虑的符号模型允许基本的伪随机函数（PRF）或公钥加密原语，但不排除使用更复杂工具的协议克服我们的下界。例如，多方非交互式密钥协商（mNIKE）可以让每个用户创建一个广播消息，之后任何用户子集都可