连续群组密钥协商（CGKA）协议的效率分析与挑战

# 连续群组密钥协商（CGKA）协议的效率分析与挑战 ## 1. CKE 证明思路与新技术 ### 1.1 CKE 证明主要思路 若针对 n 个用户的 CKE 密文长度为 o(n)，意味着最多能将 o(n) 个有效的 e - 密文“嵌入”到 C 中。假设这些密文为 \(c_1, \ldots, c_t\)，对应的公钥为 \(pk_1, \ldots, pk_t\)，其中 \(t \in o(n)\)。这表明最多需要 t 个有效的陷门（相对于预言机 O）来解密 C，即与 \((pk_1, \ldots, pk_t)\) 对应的陷门。由于 C 应能被每个用户解密，每个用户所需的“有效”陷门集应是这 t 个陷门的子集。因为 \(t = o(n)\)，所以存在一个用户，其有效陷门是其他所有用户有效陷门的子集。由于所有用户的 CKE 秘密密钥是独立生成且无关联的，多次运行 CKE 密钥生成算法，应该能够为至少一个用户恢复所有所需的陷门。 ### 1.2 新技术 - **预言机采样限制**：证明中涉及预言机采样步骤，与以往选择与一组查询/答案对一致的预言机不同，这里需要确保采样的预言机不包含特定的查询/响应 对。这种使某些查询/响应 对成为禁区的技术及其证明的含义，可能在证明其他不可能结果中找到应用。 - **随机预言机非均匀攻击定理应用**：利用关于对随机预言机的非均匀攻击的定理，论证长度为 o(n) 的 CKE 密文无法嵌入 n 个密文。 ## 2. 不存在单一最优 CGKA 协议 ### 2.1 协议选择导致的通信成本差异 CGKA 协议以在线方式进行，用户在执行操作时需做出选择，这可能导致不必要的通信。对于每个使用 PKE 进行黑盒操作的 CGKA 协议 Π，存在某种 CGKA 操作序列 Seq 的分布和另一个 CGKA 协议 Π′，使得在执行 Seq 时，Π 的通信成本远高于 Π′。 ### 2.2 示例说明 假设一个 CGKA 组处于任意状态，用户 A 添加 k 个用户并使其离线，然后 α 个用户（包括用户 A）执行状态刷新。 - **策略一**：一些协议可能通过状态刷新为 k 个添加的用户创建并通信额外的冗余秘密。如果这些 k 个用户之后上线并执行自己的状态刷新，那么这些额外秘密的通信就是不必要的，采用另一种策略的协议通信成本会低得多。 - **策略二**：另一些协议可能仅依赖用户 A 通信的秘密。如果 α - 1 个用户中的用户 j 在状态刷新中仅通信少量信息（o(k)），之后离线，而其他 α - 1 个用户执行顺序状态刷新轮次，根据证明，每一轮次将有 Ω(k) 的通信成本。因为 k 个添加的用户主要与除用户 j 之外的 α - 1 个用户共享秘密，所以这些用户执行状态刷新时，必须重新向 k 个添加的用户通信秘密。但如果用户 j 的状态刷新密文很大（Ω(k)），采用第一种策略的协议通信成本可能会低得多，因为 k 个添加的用户仍与用户 j 共享足够的秘密，其他 α - 1 个用户执行状态刷新时无需向添加的用户通信太多新信息。 ## 3. 实践中的经验教训 ### 3.1 最坏情况通信开销的原因 如果满足以下条件，CGKA 协议的执行会在组成员之间导致不切实际的通信开销： - CGKA 协议仅由 PKE 构建。 - CGKA 协议实现最弱可接受的安全概念。 - 协议执行的组成员发起某些非平凡的操作序列。 ### 3.2 避免开销的方法 - **寻找替代构建块**：尝试找到除 PKE 之外合适的实用构建块来规避下限，但最终需要规避 CKE 下限，这是一个具有挑战性的问题。 - **降低安全要求**：不建议降低 CGKA 的安全要求。 - **识别并禁止问题操作序列**：识别所有有问题的操作序列并禁止其执行。 ### 3.3 具体场景分析 #### 3.3.1 两个管理员的 CGKA 许多实际的 SGM 系统可能对用户施加成员策略，只有少数“管理员”可以添加和移除组内成员，其他用户只能更新状态和发送消息。对于只有一个管理员的情况，CGKA 可归结为经典的组播加密，即使满足某些安全属性，也能轻松实现 \(O(\log n)\) 的通信复杂度。但在有两个可以相互替换的管理员且只需要满足属性 1 的情况下，从一个管理员到两个管理员的转变，在最坏情况下，每次操作的通信复杂度会从 \(O(\log n)\) 增加到 Ω(n)。 #### 3.3.2 MLS 提议 - 提交框架 最新的