TGKA：基于可聚合广播的安全可追溯组密钥协商协议

TGKA： Secure and Traceable Group Key Agreement Protocol Based on Aggregatable Broadcast

摘要

组密钥协商协议用于解决多个参与方在不安全的通信网络中的组消息传递安全问题。然而现有方案存在通信效率低、计算开销大、群组规模难以扩大、安全性不足等问题。针对组密钥协商中的这些问题，设计了一种可聚合共享棘轮树算法，并基于此提出了一个基于可聚合广播的安全可追溯组密钥协商协议（Traceable Group Key Agreement，TGKA）。TGKA协议将基于签名的可聚合广播方案与密钥封装的思想结合，通过棘轮树将用户划分为多个子组，在子组之间进行密钥协商，从而减小其在计算与通信上的开销，实现了动态组的高效密钥更新。实验结果表明，在确保了组密钥协商协议安全性的同时，TGKA协议能够降低群组发送者与接收者的通信复杂度，在数十至数百用户的中型组中具备一定的可行性。

Abstract

Group key agreement protocols are designed to address the security issues of group message transmission among multiple participants in an insecure communication network. However, existing solutions often suffer from low communication efficiency, high computational overhead, difficulty in scaling group sizes, and insufficient security issues. To address these problems in group key agreement, a novel aggregatable shared ratchet tree algorithm is designed. Based on this, a secure and traceable group key agreement(TGKA) protocol is proposed. The TGKA protocol combines a signature-based aggregatable broadcast scheme with the concept of key encapsulation. The protocol reduces computational and communication overhead by using a ratcheting tree to divide users into multiple subgroups and perform key agreements within these subgroups, achieving efficient key updates for dynamic groups. The experimental results indicate that while ensuring the security of the group key agreement protocol, the TGKA protocol can reduce the communication complexity for both group senders and receivers. This demonstrates a certain level of feasibility in medium-sized groups with tens to hundreds of users.

Graphical abstract

关键词

组密钥协商 / 前向安全与后向安全 / 可追溯性 / 棘轮树

Key words

group key agreement / forward safety and backward safety / traceability / ratchet tree

0　 引 言

现如今，社会愈加依赖于即时通讯，信息的交流与传播都需要互联网或者其他数字通信网络来实现，无论是企业内部的团队协作、跨部门的沟通，还是与客户、合作伙伴之间的联系，群组通信已经成为推动工作和业务发展的重要手段之一。群组通信为沟通带来便捷的同时，也带来了个人隐私和敏感信息泄露的风险。因此，群组通信的安全性与隐私性也逐步受到关注。

密码学作为一种有效的技术手段，可以帮助解决数字通信技术中的一些安全和隐私问题。一个安全的组密钥协商协议能够在不受信任的基础设施上为群组用户建立安全的消息传递通道，从而确保群组内部的安全通信^[1]。最简单的群组安全通信方案是将两方安全通信扩展到多方安全通信，即所有群组用户建立成对的通信通道。Signal组协议^[2]和Whatsapp中的Sender Key协议^[3]等采取的简单扩展方式虽然能够通过定期更新密钥来保证前后向安全性，但其通信开销会随着组规模的扩大而增加，导致系统效率降低，因此方案的可扩展性较差。

为了更好地解决群组通信协议中存在的问题，有学者提出了基于树的群密钥协商协议方案^[4-5]，包括二叉树结构^[6-7]与三叉树结构^[8]，这些方案通过树结构能够将群组用户的通信开销从O(n)降低到O(\mathrm{l}\mathrm{o}\mathrm{g}n)。近几年出现了更多采用树结构的复杂协议，这类协议以密钥树为主体结构，采用将消息广播加密的形式完成组密钥的协商。Cohn-Gordon等^[9]提出了专门为现代安全群组消息应用设计的名为异步棘轮树(Asynchronous Ratcheting Trees,ART)的协议，该协议提供了密钥保密性、认证、前向保密性、后向安全性和非交互性，但没有定义动态群组成员身份的机制。Bhargavan等^[10]开发了一种名为TreeKEM的系统，克服了ART的局限性，支持用户的并发更新，但在某些情况下会削弱后向安全性，并且无法追溯到因密钥泄漏而受损的用户。而Alwen等^[1，11]认为ART、TreeKEM的核心算法都是一种新型密码原语的变体，他们将这种新原语命名为异步连续组密钥协商(Continuous Group Key Agreement,CGKA)，并提出了服务器辅助的连续组密钥协议(Server-Aided Continuous Group Key Agreement,SAIK)。CGKA和SAIK分别在密钥生成算法和服务器辅助上对TreeKEM协议做了修改，但仍然未解决密钥泄露的追溯问题。

Weidner等^[12]提出了一种去中心化安全组消息传递协议(Decentralized Continuous Group Key Agreement,DCGKA)，该协议没有使用CGKA协议方案中的树结构，而是对原有的协议进行了去中心化的处理，解决了CGKA和SAIK等方案中密钥泄露的追溯问题；Yang等^[13]提出了基于ECDH和短签名的组密钥协议，并在此基础上添加了短签名实现了认证属性。虽然DCGKA和基于ECDH和短签名的组密钥协议满足了更多的安全属性，但它们的通信开销与计算复杂度为O(n)，仍存在群组规模难以扩展、效率低的问题。

为了实现低通信开销、低计算开销的安全可追溯组密钥协商协议，本文结合TreeKEM协议在密钥更新上的组内广播的思想，将基于签名的可聚合广播方案应用到棘轮树结构中，设计了一种可聚合共享棘轮树算法，并提出了一个新的组密钥协商协议。本文主要的研究工作如下：

1) 提出了一个新的基于可聚合广播的安全可追溯组密钥协商协议(Traceable Group Key Agreement,TGKA)，将原用于静态组条件约束下的公钥广播方案扩展到了在动态组，在保证通信中消息密钥隐私性的同时确保长期通信中的前向安全与后向安全。

2) 设计了一种可聚合共享棘轮树算法，利用密钥封装思想进行组内密钥交换，减小密钥更新的广播通信开销，并将其复杂度降低到O(\mathrm{l}\mathrm{o}\mathrm{g}n)，同时保证了密钥泄露后的可追溯性。

3) 从安全性、计算效率和通信开销等多方面与已有方案进行了对比，在保证了各项安全特性的基础上有较好的实验结果。

1　 预备知识

1.1　基于签名的可聚合广播

基于签名的可聚合广播方案^[14]（Aggregatable Signature-Based Broadcast,ASBB）是公钥体系下的一种广播加密方案，可以同时作为签名方案和广播方案使用。该方案包括六个多项式概率时间算法：\mathrm{P}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{G}\mathrm{e}\mathrm{n}、\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}、\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}、\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}、\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}和\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}。

1) \pi \leftarrow \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda })：在输入安全参数\lambda时，生成一个元组\mathrm{\Upsilon }=(p,\mathbb{G},{\mathbb{G}}_T,e)，其中，\mathbb{G},{\mathbb{G}}_T拥有相同的素数阶p，g是\mathbb{G}的生成元，e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T是一个有效的非退化双线性映射，H:{\{\mathrm{0,1}\}}^{\mathrm{*}}\to \mathbb{G}是一个哈希函数，输出公共参数\pi =(\mathrm{\Upsilon },g,H)。

2) (\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k})\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}(\pi )：选择一个随机数r\in {\mathbb{Z}}_p^{\mathrm{*}}，X\in \mathbb{G}\backslash \left\{\mathrm{1}\right\}。计算R=g^{-r}，A=e\left(X,g\right)，公钥\mathrm{p}\mathrm{k}=(R,A)，私钥\mathrm{s}\mathrm{k}=(r,X)，输出公钥/私钥对(\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k})。

3) \sigma \leftarrow \mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k},s)：在输入密钥对(\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k})和任意字符串s\in {\left\{\mathrm{0,1}\right\}}^{\mathrm{*}}时，输出对应签名：\sigma =XH{(s)}^r。

4) \mathrm{0}/\mathrm{1}\leftarrow \mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{p}\mathrm{k},s,\sigma )：在输入公钥\mathrm{p}\mathrm{k}，字符串s和签名\sigma时，验证等式为：

e(\sigma ,g)e(H(s),R)=A(1)

如果(1)式成立，则表示该签名是有效的，输出1；否则将输出0，并拒绝签名。

5) c\leftarrow \mathrm{E}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{p}\mathrm{k},m)：在输入公钥\mathrm{p}\mathrm{k}和明文m\in G_T时，随机选择t\in {\mathbb{Z}}_p^{\mathrm{*}}，输出密文c=(c_{\mathrm{1}},c_{\mathrm{2}},c_{\mathrm{3}})，其中c_{\mathrm{1}}=g^t，c_{\mathrm{2}}=R^t，c_{\mathrm{3}}=m{A}^t。

6) m\leftarrow \mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{p}\mathrm{k},s,\sigma ,c)：在输入公钥\mathrm{p}\mathrm{k}、任何有效字符串s、有效签名\sigma和密文c时，输出明文：

m=\frac{c_{\mathrm{3}}}{e(\sigma ,c_{\mathrm{1}})e(H(s),c_{\mathrm{2}})}(2)

基于签名的可聚合广播方案具有同态性和聚合性，即对于由同一个公共参数\pi生成的两个公私钥对(\mathrm{p}{\mathrm{k}}_{\mathrm{1}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}})和(\mathrm{p}{\mathrm{k}}_{\mathrm{2}},\mathrm{s}{\mathrm{k}}_{\mathrm{2}})，其公钥\mathrm{p}{\mathrm{k}}_{\mathrm{1}}、\mathrm{p}{\mathrm{k}}_{\mathrm{2}}对同一个字符串s进行签名可以得到对应签名{\sigma }_{\mathrm{1}}、{\sigma }_{\mathrm{2}},存在对于任意消息明文m满足：

c\leftarrow \mathrm{E}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{p}{\mathrm{k}}_{\mathrm{1}}\otimes \mathrm{p}{\mathrm{k}}_{\mathrm{2}},m)(3)

\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{p}{\mathrm{k}}_{\mathrm{1}}\otimes \mathrm{p}{\mathrm{k}}_{\mathrm{2}},s,{\sigma }_{\mathrm{1}}\odot {\sigma }_{\mathrm{2}},c)=m(4)

其中，\otimes代表公钥\mathrm{p}{\mathrm{k}}_{\mathrm{1}}、\mathrm{p}{\mathrm{k}}_{\mathrm{2}}之间的同态相乘运算，即(R_{\mathrm{1}},A_{\mathrm{1}})\otimes (R_{\mathrm{2}},A_{\mathrm{2}})=(R_{\mathrm{1}}{R}_{\mathrm{2}},A_{\mathrm{1}}{A}_{\mathrm{2}})。\odot代表签名{\sigma }_{\mathrm{1}}、{\sigma }_{\mathrm{2}}之间的同态相乘运算，即{\sigma }_{\mathrm{1}}\odot {\sigma }_{\mathrm{2}}={\sigma }_{\mathrm{1}}{\sigma }_{\mathrm{2}}。文献[14]证明了该方案在计算Diffie-Hellman（CDH）和决策Diffie-Hellman（DBDH）假设下满足EUF-CMA-Ind-CPA安全，即其签名在选择消息攻击下满足不可伪造性（EUF-CMA），其加密在选择明文攻击下满足不可区分性（Ind-CPA）。

1.2　棘轮树

棘轮树（Ratchet Tree,RT）是一种特殊的数据结构，通常在端到端加密通信协议中使用，特别是在需要支持多方组安全通信的场景下，使用棘轮树的组密钥交换构成了现代安全组消息传递协议的核心。图1所示为TreeKEM协议中的棘轮树结构，包含四个用户u_A、u_B、u_C和u_D。

RT树本质上是一个二叉树，每一个叶子节点代表一个用户，每个节点都包含与用户关联的密钥信息。中间节点包含由其子节点计算而来的中间密钥信息，例如图1的中间节点（H(B)和H(D)）由一个确定的孩子节点（A、B、C、D）通过哈希函数生成，最终计算所得的根节点密钥H(H(D))作为群组共享密钥信息。因此，除根节点外，所有节点都有一个关联的公共密钥加密密钥对，且每个用户知道其直接路径（即从叶节点到根的路径）上的所有密钥。棘轮树结构通常被设计用于提供长期通信的前向保密和后向保密，即使某个时刻的密钥被泄露，也不会影响到之前或之后通信的安全性。

1.3　密钥封装机制

基于非对称加密方法的密钥封装机制（Key Encapsulation Mechanism,KEM）是一种密钥交换方式，适用于在不安全信道下的私钥传输场景，将密钥封装后传输以保护密钥的隐私性。密钥封装机制包含两个主要部分：密钥封装和数据加密。密钥封装\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{a}\mathrm{p}\mathrm{s}负责生成一个随机的会话密钥k和一个封装体c（即密钥的加密形式），而数据加密\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{\text{'}}使用这个会话密钥来加密实际的消息或数据m，其形式如图2所示。这种先封装后加密的分离方法提高了整个加密过程的灵活性和安全性。

类似于公钥加密算法，密钥封装也包括三个算法：\mathrm{G}\mathrm{e}\mathrm{n}、\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{a}\mathrm{p}\mathrm{s}和\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{p}\mathrm{s}。密钥生成算法\mathrm{G}\mathrm{e}\mathrm{n}用于生成一对公钥和私钥。为了区别公钥加密算法，发送方运行封装算法\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{a}\mathrm{p}\mathrm{s}，它只接受一个公钥作为输入（不含待加密的消息），并输出一个密文c和一个密钥k。接收方运行对应的解密算法\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{p}\mathrm{s}，使用私钥从密文c中恢复出k。其形式化表示为：

1) \left(\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k}\right)\leftarrow \mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^n)：在输入安全参数{\mathrm{1}}^n时，输出一个公钥/私钥对(\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k})。假定\mathrm{p}\mathrm{k}和\mathrm{s}\mathrm{k}的长度都为n，且n可以从\mathrm{p}\mathrm{k}中确定。

2) \left(c,k\right)\leftarrow \mathrm{E}\mathrm{n}\mathrm{c}\mathrm{a}\mathrm{p}{\mathrm{s}}_{\mathrm{p}\mathrm{k}}({\mathrm{1}}^n)：在输入公钥\mathrm{p}\mathrm{k}和安全参数{\mathrm{1}}^n时，输出密文c和密钥k，其中k\in {\left\{\mathrm{0,1}\right\}}^{\mathrm{𝓁}\left(n\right)}，\mathrm{𝓁}\left(n\right)为密钥k的长度。

3) k\leftarrow \mathrm{D}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{p}{\mathrm{s}}_{\mathrm{s}\mathrm{k}}(c)：在输入私钥\mathrm{s}\mathrm{k}、密文c，输出密钥k或一个表示失败的特殊符号“⊥”。

1.4　安全模型

在本小节中，给出了证明本文协议的安全性时需要用到的安全游戏。本文的安全游戏基于对多阶段的定义进行构造，允许会话具有不同密钥的多个阶段，并且攻击者可以测试任何阶段。

本文通过挑战者C和概率多项式时间的攻击者\mathrm{𝒜}之间的安全游戏来定义方案的安全模型，其中由挑战者C执行TGKA协议的各个阶段并持有密钥信息，而攻击者\mathrm{𝒜}通过询问可以与挑战者进行交互。攻击者\mathrm{𝒜}可以通过检查用户存在状态并选择一个当前用户u作为阶段执行者，也就是代理，调用协议任何阶段的对应算法（成员添加、成员删除或密钥更新）并向挑战者C发起询问。攻击者\mathrm{𝒜}最终选择某一个群组（会话）的某一个阶段进行测试，判断其收到了真实密钥还是随机密钥。如果判断是正确的，那么攻击者\mathrm{𝒜}就赢得了游戏。因此，在这个模型中安全的协议具有对手不能区分真实密钥与随机密钥的属性。

1) 初始化阶段

令U=(u,v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_{n-\mathrm{1}})表示有n个群组成员的用户集合，u代表被询问目标。对于一次询问任务，s表示当前想要询问的群组（会话），t表示群组此时所处的阶段状态（在初始化阶段为0），\mathrm{o}\mathrm{p}表示一项阶段操作（成员添加、成员删除或密钥更新）。\tau (s,t)表示在群组会话s的阶段t下的公钥树，{\tau }_i(v_i,s,t)表示成员v_i在群组会话s的阶段t下的签名树。游戏开始之时，挑战者C运行初始化阶段算法，生成跟踪执行所需的所有变量，包括公钥树、所有初始用户签名树集合并生成相应的安全参数\lambda和公共参数\pi，全部发送给攻击者\mathrm{𝒜}。

2) 询问阶段

攻击者\mathrm{𝒜}向挑战者C进行多项式有界次适应性询问，这些查询包括允许攻击者与诚实参与者进行交互的\mathrm{C}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{e}、\mathrm{A}\mathrm{S}\mathrm{e}\mathrm{n}\mathrm{d}和\mathrm{A}\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{v}，模拟协议中使用的密钥的损坏的\mathrm{R}\mathrm{e}\mathrm{v}\mathrm{S}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{K}\mathrm{e}\mathrm{y}和\mathrm{R}\mathrm{e}\mathrm{v}\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{m}，以及\mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}。具体描述如下：

\mathrm{C}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{e}(u,v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_{n-\mathrm{1}})：对于攻击者给定的参与者v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_{n-\mathrm{1}}，挑战者执行群组创建阶段算法生成一个新的群组（群组阶段为1），并为全部参与者与代理u生成密钥对并计算得到公钥树\tau (s,\mathrm{1})和所有初始用户签名树集合{\tau }_i(v_i,s,\mathrm{1})。

\mathrm{A}\mathrm{S}\mathrm{e}\mathrm{n}\mathrm{d}\left(u,s,\mathrm{o}\mathrm{p}\right)：对于攻击者给定的操作指令\mathrm{o}\mathrm{p}和会话阶段s，u发送一个执行\mathrm{o}\mathrm{p}的命令来促使群组进入下一状态。该询问模拟代理用户u向协议发送一条请求信息，u必须是一个有效的代理且群组已经创建成功，返回请求是否被接受。

\mathrm{A}\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{v}\left(u,s,\mathrm{o}\mathrm{p}\right)：对于攻击者给定的操作指令\mathrm{o}\mathrm{p}和群组会话s，挑战者接收到请求并执行一次\mathrm{o}\mathrm{p}任务促使群组进入下一状态。该询问模拟协议对用户操作请求的响应。

\mathrm{R}\mathrm{e}\mathrm{v}\mathrm{S}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{K}\mathrm{e}\mathrm{y}\left(u,s,t\right)：对于给定的群组会话s和会话阶段t，返回当前状态下的组密钥\mathrm{g}\mathrm{k}。该询问模拟组密钥的泄露。

\mathrm{R}\mathrm{e}\mathrm{v}\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{m}\left(u,s,t\right)：对于给定的群组会话s和会话阶段t，返回在该阶段下用户u在密文空间下选择的随机密钥。

\mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}\left(u,s,t\right)：攻击者在群组运行到t阶段时进行一次\mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}询问。挑战者掷随机硬币\rho \in \left\{\mathrm{0,1}\right\}，如果\rho =\mathrm{0}，返回当前阶段中用户u计算得到的真实组密钥\mathrm{g}{\mathrm{k}}_{\mathrm{0}}；如果\rho =\mathrm{1}，返回密钥空间中随机选择的密钥\mathrm{g}{\mathrm{k}}_{\mathrm{1}}。

3) 挑战阶段

游戏结束时，攻击者\mathrm{𝒜}对\rho进行猜测，如果能够猜测出的\rho \mathrm{\text{'}}=\rho，则代表攻击者胜利。对于多项式时间内的攻击者\mathrm{𝒜}，赢得TGKA游戏的优势为

\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{𝒜}}^{\mathrm{T}\mathrm{G}\mathrm{K}\mathrm{A}}=\mathrm{P}\mathrm{r}[\rho \mathrm{\text{'}}=\rho ]-\frac{\mathrm{1}}{\mathrm{2}}(5)

换句话说，如果任何概率多项式时间对手以可忽略的优势赢得安全游戏的概率不高于1/2，那么基于可聚合广播的安全可追溯组密钥协商协议是安全的。

2　 本文方案

本文利用基于签名的可聚合广播方案中公钥方案的同态性与聚合性，设计了可聚合共享棘轮树算法用于组内共享和交换密钥信息，并通过调用可聚合共享棘轮树算法设计了一个强安全群组通信密钥协商协议，用于多用户之间创建动态群组并共享同一个组密钥。

2.1　可聚合共享棘轮树算法

棘轮树包括公钥树和签名树。棘轮树共有六个相关算法，分别是：创建棘轮树（\mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{C}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{e}）、树更新（\mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{U}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}）、添加用户节点（\mathrm{A}\mathrm{d}\mathrm{d}\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}）、删除用户节点（\mathrm{R}\mathrm{e}\mathrm{m}\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}）、组密钥发送（\mathrm{S}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{K}\mathrm{e}\mathrm{y}）与组密钥接收（\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{K}\mathrm{e}\mathrm{y}）。当用户创建一个新的群组，首先初始化群组用户信息与有关状态变量，并根据用户密钥信息构建群组公钥树与用户签名树。每进行一次群成员的变动或密钥的更新操作，都会更新当前群组状态，调用公钥树与签名树的相应算法更新树结构，促使群组进入下一个状态。棘轮树的算法如下：

1) \tau \leftarrow \mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{C}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{e}(G,K)

① 输入用户集合G=(\mathrm{I}{\mathrm{D}}_{\mathrm{0}},\mathrm{I}{\mathrm{D}}_{\mathrm{1}},\mathrm{I}{\mathrm{D}}_{\mathrm{2}},\dots ,\mathrm{I}{\mathrm{D}}_{n-\mathrm{1}})，密钥集合K=(k_{n-\mathrm{1}},k_n,k_{n+\mathrm{1}},\dots ,k_{\mathrm{2}n-\mathrm{2}})，其中每个\mathrm{I}{\mathrm{D}}_i对应的用户密钥为k_{i+n-\mathrm{1}}。

② 根据用户数量创建棘轮树\tau，每个叶子节点的密钥信息包括(\mathrm{I}{\mathrm{D}}_i,k_{i+n-\mathrm{1}})。

③ 遍历计算其他树节点。从叶子节点k_{n-\mathrm{1}}开始向上计算中间节点，每个中间节点的密钥信息由对应子节点计算，如果k_i为用户公钥，则中间节点采用公钥同态乘法，即k_{i/\mathrm{2}}=k_i\otimes k_{i+\mathrm{1}}，直至计算出根节点；如果k_i为用户签名，则中间节点采用签名同态乘法，即k_{i/\mathrm{2}}=k_i\odot k_{i+\mathrm{1}}，直至计算出根节点。

④ 输出棘轮树\tau。

2) \tau \mathrm{\text{'}}\leftarrow \mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{U}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}(\tau ,\mathrm{I}{\mathrm{D}}_i,k\mathrm{\text{'}})

① 输入棘轮树\tau和待更新密钥信息(\mathrm{I}{\mathrm{D}}_i,k\mathrm{\text{'}})。

② 修改\mathrm{I}{\mathrm{D}}_i的对应密钥k_{i+n-\mathrm{1}}为k\mathrm{\text{'}}。

③ 遍历计算其他树节点。从叶子节点k_{n-\mathrm{1}}开始向上计算中间节点，每个中间节点的密钥信息由对应子节点计算，如果k_i为用户公钥，则中间节点采用公钥同态乘法，即k_{i/\mathrm{2}}=k_i\otimes k_{i+\mathrm{1}}，直至计算出根节点；如果k_i为用户签名，则中间节点采用签名同态乘法，即k_{i/\mathrm{2}}=k_i\odot k_{i+\mathrm{1}}，直至计算出根节点。

③ 输出棘轮树\tau \mathrm{\text{'}}。

3) \tau \mathrm{\text{'}}\leftarrow \mathrm{A}\mathrm{d}\mathrm{d}\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}(\tau ,\mathrm{I}{\mathrm{D}}_i,k\mathrm{\text{'}})

① 输入棘轮树\tau和新用户信息(\mathrm{I}{\mathrm{D}}_i,k\mathrm{\text{'}})。

② 检查\mathrm{I}{\mathrm{D}}_i是否存在于G中，如果已经存在则无法添加。

③ 检查空叶子节点。如果树中存在空节点，则将密钥信息存放在第一个空节点中；如果不存在空节点则创建一个新节点。

④ 更新树\tau \mathrm{\text{'}}\leftarrow \mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{U}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}(\tau ,\mathrm{I}{\mathrm{D}}_i,k\mathrm{\text{'}})。

⑤ 输出棘轮树\tau \mathrm{\text{'}}。

4) \tau \mathrm{\text{'}}\leftarrow \mathrm{R}\mathrm{e}\mathrm{m}\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}(\tau ,\mathrm{I}{\mathrm{D}}_i,k_{i+n-\mathrm{1}})

① 输入棘轮树\tau和删除用户信息(\mathrm{I}{\mathrm{D}}_i,k_{i+n-\mathrm{1}})。

② 检查\mathrm{I}{\mathrm{D}}_i是否存在于G中，如果不存在则删除失败。

③ 由删除并更新节点向根节点计算修改路径上树节点。将该叶子节点中的密钥信息删除并设置为1，更新树\tau \mathrm{\text{'}}\leftarrow \mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{U}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}(\tau ,\mathrm{I}{\mathrm{D}}_i,\mathrm{1})。

④ 输出棘轮树\tau \mathrm{\text{'}}。

5) \mathrm{K}\mathrm{M}\leftarrow \mathrm{S}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{K}\mathrm{e}\mathrm{y}(\mathrm{I}{\mathrm{D}}_k,\mathrm{g}\mathrm{k})

① 输入用户\mathrm{I}{\mathrm{D}}_k，组密钥\mathrm{g}\mathrm{k}。

② 选择\mathrm{I}{\mathrm{D}}_k叶子节点到根节点的路径上所有节点的兄弟节点，获取其对应的公钥或子组公钥。

③ 用这些节点所包含的公钥\mathrm{p}{\mathrm{k}}_{k-\mathrm{1}}（或聚合后的有效公钥\mathrm{g}\mathrm{p}{\mathrm{k}}_i）加密组密钥\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{p}{\mathrm{k}}_{k-\mathrm{1}},\mathrm{g}\mathrm{k})（或\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{g}\mathrm{p}{\mathrm{k}}_i,\mathrm{g}\mathrm{k})），输出封装后的\mathrm{l}\mathrm{o}\mathrm{g}n个密钥\mathrm{K}\mathrm{M}并发送到对应子组如图3所示。

6) \mathrm{g}\mathrm{k}=\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{K}\mathrm{e}\mathrm{y}(\mathrm{I}{\mathrm{D}}_k,\mathrm{K}\mathrm{M})

① 输入用户\mathrm{I}{\mathrm{D}}_k，封装密钥\mathrm{K}\mathrm{M}。

② 获得对应封装后密钥的用户用签名树中对应节点签名（或子组节点中的聚合签名值）对密钥进行解封计算\mathrm{g}\mathrm{k}=\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{p}{\mathrm{k}}_{k-\mathrm{1}},\mathrm{I}{\mathrm{D}}_k,{\sigma }_{k-\mathrm{1}},\mathrm{K}\mathrm{M})（或\mathrm{g}\mathrm{k}=\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{g}\mathrm{p}{\mathrm{k}}_i,\mathrm{I}{\mathrm{D}}_k,{\sigma }_i,\mathrm{K}\mathrm{M})）获得更新后的组密钥\mathrm{g}\mathrm{k}。

③ 输出组密钥\mathrm{g}\mathrm{k}。

2.2　安全可追溯组密钥协商协议

协议共包含群组通信中的六项操作,分别是：初始化（Initialization）、群组创建（Group creation）、成员添加（Member addition）、成员移除（Member removal）、密钥更新（Key update）和消息处理（Message processing）。除初始化操作以外，每项操作完成后，组内全部用户需要共享一个组密钥用于此状态阶段下的组消息传递。在本文方案中，全体用户的密钥信息被分别存储在两种不同的棘轮树中，即公钥树与签名树。其中公钥树由所有群组当前用户的公钥计算生成，而签名树针对单个用户，由组内当前所有用户对其\mathrm{I}\mathrm{D}生成的签名序列计算生成，作为该用户的私有签名树。每个群组拥有唯一的公钥树，群组成员能够通过访问公钥树完成对组密钥的封装与转发，而群组中每个用户都拥有一个唯一的私有签名树，与公钥树对应，用于对封装密钥信息的解封。

1) 初始化

① 初始化公钥生成参数。输入安全参数\lambda，生成公共参数\pi \leftarrow \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda })。

② 初始化群组相关的状态变量。初始化用户序列标识符\mathrm{I}\mathrm{D}形成用户列表，记录用户当前状态，初始化变量\tau用于跟踪基于群组所生成公钥树的变化，初始化{\tau }_i序列用于跟踪用户基于群组所生成的签名树在每轮更新中的变化。

2) 群组创建

① 输入用户集合G=(\mathrm{I}{\mathrm{D}}_{\mathrm{0}},\mathrm{I}{\mathrm{D}}_{\mathrm{1}},\mathrm{I}{\mathrm{D}}_{\mathrm{2}},\dots ,\mathrm{I}{\mathrm{D}}_{n-\mathrm{1}})。

② 获取密钥对。采用基于签名的可聚合广播方案生成封装密钥，为群组集合G中每个用户\mathrm{I}{\mathrm{D}}_i创建共n个密钥对：(\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i)\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}(\pi )。

③ 计算签名。每个用户\mathrm{I}{\mathrm{D}}_i\in G对其他用户\mathrm{I}{\mathrm{D}}_j\in G进行签名：{\sigma }_i(\mathrm{I}{\mathrm{D}}_j)\leftarrow \mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i,\mathrm{I}{\mathrm{D}}_j)。

其中用户\mathrm{I}{\mathrm{D}}_i用私钥\mathrm{s}{\mathrm{k}}_i对\mathrm{I}{\mathrm{D}}_i的签名{\sigma }_i(\mathrm{I}{\mathrm{D}}_i)由用户自己私有存储，将密钥信息\mathrm{p}{\mathrm{k}}_i和其他签名{\sigma }_i=({\sigma }_i(\mathrm{I}{\mathrm{D}}_{\mathrm{1}}),\dots ,{\sigma }_i(\mathrm{I}{\mathrm{D}}_{i-\mathrm{1}}),{\sigma }_i(\mathrm{I}{\mathrm{D}}_{i+\mathrm{1}}),\dots ,{\sigma }_i(\mathrm{I}{\mathrm{D}}_{n-\mathrm{1}}))向其他用户进行广播。

④ 创建公钥树与签名树。输入集合G和每个用户广播的公钥\mathrm{p}\mathrm{k}=(\mathrm{p}{\mathrm{k}}_{\mathrm{0}},\mathrm{p}{\mathrm{k}}_{\mathrm{1}},\dots ,\mathrm{p}{\mathrm{k}}_{n-\mathrm{1}})与每个用户的签名信息\sigma =({\sigma }_{\mathrm{0}},{\sigma }_{\mathrm{1}},\dots ,{\sigma }_{n-\mathrm{1}})，分别调用创建棘轮树算法得到公钥树\tau \leftarrow \mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{C}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{e}(G,\mathrm{p}\mathrm{k})和n个用户签名树{\tau }_i\leftarrow \mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{C}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{e}(G,{\sigma }_i)。

⑤ 组密钥发送与接收。群创建者生成对称组密钥\mathrm{g}{\mathrm{k}}_{\mathrm{0}}作为初始组密钥并通过棘轮树发送到子组中\mathrm{K}\mathrm{M}\leftarrow \mathrm{S}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{K}\mathrm{e}\mathrm{y}(\mathrm{I}{\mathrm{D}}_i,\mathrm{g}{\mathrm{k}}_{\mathrm{0}})，由子组用户单独解密获得\mathrm{g}{\mathrm{k}}_{\mathrm{0}}=\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{K}\mathrm{e}\mathrm{y}(\mathrm{I}{\mathrm{D}}_j,\mathrm{K}\mathrm{M})。

⑥ 输出公钥树\tau、所有{\tau }_i。

3) 成员添加

① 输入新用户\mathrm{I}{\mathrm{D}}_k，公钥树\tau。

② 检查\mathrm{I}{\mathrm{D}}_k是否已经存在G中，如果已经存在，则添加失败。

③ 获取新的密钥对(\mathrm{p}{\mathrm{k}}_k,\mathrm{s}{\mathrm{k}}_k)\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}(\pi )。

④ 计算签名。新用户\mathrm{I}{\mathrm{D}}_k对当前集合G进行签名得到签名合集{\sigma }_k=({\sigma }_k(\mathrm{I}{\mathrm{D}}_{\mathrm{0}}),\dots ,{\sigma }_k(\mathrm{I}{\mathrm{D}}_n))并将签名值广播到其他用户。

⑤ 调用棘轮树添加用户节点算法分别更新共享公钥树\tau \mathrm{\text{'}}\leftarrow \mathrm{A}\mathrm{d}\mathrm{d}\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}(\tau ,\mathrm{I}{\mathrm{D}}_k,\mathrm{p}{\mathrm{k}}_k)和用户签名树{\tau }_i\mathrm{\text{'}}\leftarrow \mathrm{A}\mathrm{d}\mathrm{d}\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}({\tau }_i,\mathrm{I}{\mathrm{D}}_k,{\sigma }_k(\mathrm{I}{\mathrm{D}}_i))。

⑥ 用户\mathrm{I}{\mathrm{D}}_k生成对称密钥\mathrm{g}{\mathrm{k}}_{l+\mathrm{1}}作为新的组密钥并发送到子组中\mathrm{K}\mathrm{M}\leftarrow \mathrm{S}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{K}\mathrm{e}\mathrm{y}(\mathrm{I}{\mathrm{D}}_k,\mathrm{g}{\mathrm{k}}_{l+\mathrm{1}})，由子组用户单独解密获得\mathrm{g}{\mathrm{k}}_{l+\mathrm{1}}=\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{K}\mathrm{e}\mathrm{y}(\mathrm{I}{\mathrm{D}}_i,\mathrm{K}\mathrm{M})。

⑦ 输出公钥树\tau \mathrm{\text{'}}。

4) 成员移除

① 输入移除用户\mathrm{I}{\mathrm{D}}_k。

② 检查\mathrm{I}{\mathrm{D}}_k是否存在G中，如果不存在，则移除失败。

③ 调用棘轮树删除用户节点算法分别更新共享公钥树\tau \mathrm{\text{'}}\leftarrowRemUser(\tau ,\mathrm{I}{\mathrm{D}}_k,\mathrm{p}{\mathrm{k}}_k)和用户签名树{\tau }_i\mathrm{\text{'}}\leftarrowRemUser({\tau }_i,\mathrm{I}{\mathrm{D}}_k,{\sigma }_k(\mathrm{I}{\mathrm{D}}_i))。

④ \mathrm{I}{\mathrm{D}}_k生成对称密钥\mathrm{g}{\mathrm{k}}_{l+\mathrm{1}}作为新的共享组密钥并发送到子组中\mathrm{K}\mathrm{M}\leftarrow \mathrm{S}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{K}\mathrm{e}\mathrm{y}(\mathrm{I}{\mathrm{D}}_k,\mathrm{g}{\mathrm{k}}_{l+\mathrm{1}})，由子组用户单独解密获得\mathrm{g}{\mathrm{k}}_{l+\mathrm{1}}=\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{K}\mathrm{e}\mathrm{y}(\mathrm{I}{\mathrm{D}}_i,\mathrm{K}\mathrm{M})。

⑤ 输出公钥树\tau \mathrm{\text{'}}。

5) 密钥更新

① 输入更新用户\mathrm{I}{\mathrm{D}}_k。

② 检查\mathrm{I}{\mathrm{D}}_k是否存在G中，如果不存在，则移除失败。

③ 获取新密钥对(\mathrm{p}{\mathrm{k}}_k,\mathrm{s}{\mathrm{k}}_k)\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}(\pi )。

④ 调用棘轮树的更新树算法，分别更新共享公钥树\tau \mathrm{\text{'}}\leftarrow \mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{U}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}(\tau ,\mathrm{I}{\mathrm{D}}_k,\mathrm{p}{\mathrm{k}}_k)和用户签名树{\tau }_i\mathrm{\text{'}}\leftarrow \mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{U}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}({\tau }_i,\mathrm{I}{\mathrm{D}}_k,{\sigma }_k(\mathrm{I}{\mathrm{D}}_i))。

⑤ \mathrm{I}{\mathrm{D}}_k生成对称密钥\mathrm{g}{\mathrm{k}}_{l+\mathrm{1}}作为新的共享组密钥并发送到子组中\mathrm{K}\mathrm{M}\leftarrow \mathrm{S}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{K}\mathrm{e}\mathrm{y}(\mathrm{I}{\mathrm{D}}_k,\mathrm{g}{\mathrm{k}}_{l+\mathrm{1}})，由子组用户单独解密获得\mathrm{g}{\mathrm{k}}_{l+\mathrm{1}}=\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{K}\mathrm{e}\mathrm{y}(\mathrm{I}{\mathrm{D}}_i,\mathrm{K}\mathrm{M})。

⑥ 输出公钥树\tau \mathrm{\text{'}}。

6) 消息处理

① 发送消息。在用户发送的消息m用组密钥\mathrm{g}{\mathrm{k}}_l加密得密文c后发送到各个子组。

② 接收消息。在用户接收到的密文c用共享组密钥\mathrm{g}{\mathrm{k}}_l解密得到明文m。

3　 安全分析

3.1　正确性分析

在基于可聚合广播的安全可追溯组密钥协商协议中，当更新用户想要向其他子组发送新的组密钥时，需要用公钥树中子组公钥对新的组密钥进行封装。如图3所示当用户节点的位置确定，根据用户节点到根节点的路径，大小为n的群组会被划分为\mathrm{l}\mathrm{o}\mathrm{g}(n)个大小不同的子组，每个子组对应的子树的根节点代表着其包含所有用户的公钥聚合值。公钥树和签名树在相同的操作下，树与树的节点一一对应，例如，对于接收到密钥封装的用户\mathrm{I}{\mathrm{D}}_j，\mathrm{g}\mathrm{p}{\mathrm{k}}_i代表子组所有用户的公钥聚合值，\mathrm{g}\mathrm{s}{\mathrm{k}}_i代表子组所有用户对\mathrm{I}{\mathrm{D}}_j的签名聚合值，根据加解密原理可知：

\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{g}\mathrm{p}{\mathrm{k}}_i,\mathrm{I}{\mathrm{D}}_j,\mathrm{g}\mathrm{s}{\mathrm{k}}_i,\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{g}\mathrm{p}{\mathrm{k}}_i,\mathrm{g}\mathrm{k}))=\mathrm{g}\mathrm{k}(6)

因而每个子组用户都能够通过对树的读取并进行解封得到相同的组密钥值，完成一轮组密钥的更新与密钥协商。

3.2　形式化安全性证明

本文的证明使用了标准的游戏跳跃技术。从最初的安全游戏开始，考虑“跳到”类似的游戏，限制每跳对手的成功概率，直到达到一个对手显然不能以绝对的概率超过1/2获胜的游戏。由于所有游戏的概率都是相互关联的，因此能够限制对手的原始成功概率。假设协议最多可以建立n_s个群组，每个群组最多有n_t个阶段，最多有n_p个群组成员。定义\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{K}\mathrm{D}\mathrm{F}}为攻破KDF函数单向性的优势，\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}\mathrm{S}\mathrm{B}\mathrm{B}}为ASBB方案的优势，有以下定理成立：

定理1 如果ASBB方案在计算Diffie-Hellman（CDH）和决策Diffie-Hellman（DBDH）假设下其签名满足EUF-CMA安全且加密满足Ind-CPA安全，密钥派生函数KDF满足单向性，那么对于TGKA协议的安全游戏，任何多项式时间的攻击者成功概率的优势为

\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{𝒜}}^{\mathrm{T}\mathrm{G}\mathrm{K}\mathrm{A}}\le \frac{\mathrm{1}}{\mathrm{2}}+\frac{n_s{n}_p}{p}+n_s{n}_t\mathrm{l}\mathrm{o}\mathrm{g}(n_p)\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}\mathrm{S}\mathrm{B}\mathrm{B}}+n_s(n_t+\mathrm{1})\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{K}\mathrm{D}\mathrm{F}}(7)

证 假设攻击者\mathrm{𝒜}是一个具备多项式时间内计算能力的敌手，挑战者C负责执行协议并响应\mathrm{𝒜}的询问。根据安全游戏的定义，只有当攻击者\mathrm{𝒜}对某个会话s的某个阶段t发出了一个\mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}(u,s,t)查询，攻击者\mathrm{𝒜}能够以超过1/2且不可忽略的优势猜测出正确的\rho \mathrm{\text{'}}=\rho，则\mathrm{𝒜}赢得游戏。

Game 0表示原始安全实验中的游戏。令\mathrm{A}\mathrm{d}{\mathrm{v}}_i表示在Game i中所有攻击者\mathrm{𝒜}的优势的最大值。本文的目标是界定\mathrm{A}\mathrm{d}{\mathrm{v}}_i，即对于安全实验的任何攻击者的优势。

Game 0定义为原始协议，因此攻击者的优势为：

\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{0}}+\frac{\mathrm{1}}{\mathrm{2}}

Game 1和Game 0基本相同，唯一的区别在于挑战者在为群组用户生成公私钥对时，如果用户私钥\mathrm{s}\mathrm{k}发生碰撞，则挑战者将中止安全游戏。由于协议最多可以建立n_s个群组且每个群组最多有n_p个群组成员，于是可以得到：

\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{0}}\le \frac{n_s{n}_p}{p}+\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{1}}

Game 2和Game 1基本相同，唯一的区别在于挑战者C将替换所有会话中所有的组密钥。由于在为每一次组密钥更新时，采用密钥派生函数为每一次组密钥更新生成新密钥，在询问过程中，挑战者将用随机密文替换由KDF函数计算所得密文。如果攻击者\mathrm{𝒜}可以区分Game 1和Game 2，那么就可以利用攻击者\mathrm{𝒜}的能力构造出一个攻击者\mathrm{ℬ}攻击KDF函数的单向性，而协议最多可以建立n_s个群组且每个群组最多执行n_t+\mathrm{1}次组密钥生成，于是可以得到：

\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{1}}\le n_s(n_t+\mathrm{1})\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{K}\mathrm{D}\mathrm{F}}+\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{2}}

Game 3和Game 2的不同之处在于：挑战者C将替换会话中所有基于ASBB方案中的封装密钥。具体而言，在询问阶段，每经过一次\mathrm{A}\mathrm{S}\mathrm{e}\mathrm{n}\mathrm{d}\left(u,s,\mathrm{o}\mathrm{p}\right)和\mathrm{A}\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{v}\left(u,s,\mathrm{o}\mathrm{p}\right)查询，群组状态发生一次变动，组密钥重新协商后由挑战者C执行协议的对应操作（添加用户、删除用户或密钥更新）将封装密文发送到对应子组并解密。如果攻击者\mathrm{𝒜}可以区分Game 2和Game 3，那么就可以利用攻击者的能力构造出一个攻击者\mathrm{ℬ}{\text{'}}攻击ASBB方案的密文不可区分性。由于协议最多可以建立n_s个群组且最多执行n_t次阶段状态改变，每一次状态改变挑战者都依据树结构执行\mathrm{l}\mathrm{o}\mathrm{g}(n_p)次密钥封装，于是可以得到：

\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{2}}\le n_s{n}_t\mathrm{l}\mathrm{o}\mathrm{g}(n_p)\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}\mathrm{S}\mathrm{B}\mathrm{B}}+\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{3}}

Game 4和Game 3基本相同，唯一的区别在于挑战者开始猜测攻击者选择\mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}查询的阶段（u',s',t'），如果攻击者发出的\mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}(u,s,t)中（u,s,t）≠（u',s',t'），那么挑战者中止游戏且攻击者失败。因为挑战者的猜测和攻击者选择\mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}阶段相对独立，所以有：

\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{3}}\le n_s{n}_t{n}_p\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{4}}

在Game 4中，有关于本文协议的所有密钥信息全部替换成了随机信息，因此攻击者在Game 4中没有任何优势，于是可以得到：

\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{4}}=\mathrm{0}

结合Game 0到Game 4，定理1可以得证。

3.3　其他安全性分析

1) 前向与后向安全。本文提出的方案能够同时保证前向安全与后向安全。在安全游戏中，由于攻击者会在每个阶段选择一名代理执行者执行协议操作。一旦攻击者破坏了某个用户并获取了其密钥信息，他就能够解密该时刻状态下的组密钥，进而解密该阶段的信息。然而，密钥信息在每个阶段都会更新，且每个阶段的状态只与该轮操作有关，与上一阶段的操作无关。因此，攻击者无法通过当前阶段的信息推断出上一阶段棘轮树的状态，保证了协议的前向安全。

当出现密钥泄露或用户妥协的情况，此时协议执行组密钥更新，重新获取组密钥并在组内进行更新，攻击者所获取的密钥信息与新生成的密钥信息无关，因此无法破解下一阶段的密文，从而保证了协议的后向安全。因此本文方案中状态之间的密钥独立性能够同时保证前向安全与后向安全。

2) 密钥可追溯性。对于一个连续组密钥协商协议，组密钥的泄露会造成当前阶段用户之间交换的信息被攻击者获取，为了找到密钥泄露方并判断是否存在恶意用户或恶意窃听者，本文方案在共享组密钥发生泄露，能够根据其附带密钥信息追溯到密钥泄露用户实现密钥泄露的追踪。

在本文的方案中，所有用户用于解封组密钥的私钥完全不同，并且与身份信息相关联。当发生组密钥泄露事件，组密钥的封装信息和解封信息一同泄露，根据密钥封装信息中子组公钥能够锁定接收者所在子组，缩小追溯范围。而根据密钥解封信息中密钥所包含的签名信息，可以比对得到泄露密钥的用户，从而进一步判断密钥泄露的成因，从而满足协议要求的可追溯性。

4　 实验与评估

使用基于Intel(R) Xeon(R) Gold 5218 CPU@ 2.30 GHz、Ubuntu 18.04系统实现本文方案，使用PBC库Type A椭圆曲线实现基于签名的可聚合广播方案中双线性密码运算，哈希函数和对称加密使用256位安全级别，分别对方案的安全性、计算效率与通信开销进行了实验分析与比较。

4.1　安全性对比分析

为了更清晰地了解本文方案与其他方案的区别和联系，将本文方案与该领域现行的方案以及近几年提出的方案进行了安全特性的对比分析，具体结果如表1所示。

由表1可知，在保证协议密钥隐私性的前提下，不同方案在前向安全性、后向安全性和密钥可追溯性上有不同的取舍。Signal方案和Sender Keys方案^[3]为了保证其能够在App中应用都使用了较为简单的协议，舍去了部分安全特性；而MLS协议中使用的TreeKEM方案，包括近几年对其的改进方案，例如CGKA方案^[3]和SAIK方案^[11]均无法保证密钥可追溯性。只有ART方案^[9]、DCGKA方案^[12]、GKA-SS方案^[13]和本文方案完整覆盖了组密钥协商协议需要具备的主要安全属性。

4.2　计算效率分析

为了保证在同一安全标准下进行有效对比，本文主要选择了Sender Keys方案^[3]、ART方案^[9]、DCGKA方案^[12]、GKA-SS方案^[13]与本文方案对计算开销进行了对比分析。其中ART方案、DCGKA方案、GKA-SS方案和本文方案达到了相同的安全标准，而Sender Keys方案应用于Whatsapp中，可以通过定期更新密钥来为用户提供后向安全而满足安全属性，各个方案在完成一次组密钥协商的计算开销对比如表2所示。

在连续组密钥协商方案中，每完成一次密钥协商需要密钥更新方（即发送方），将新生成的组密钥通过协议中的某种方式发送给群组内每一个其他用户，即接收者。由表2可知，Sender Keys和DCGKA方案都需要与群组每一个用户进行交互，因此发送方需要进行n次计算，但DCGKA方案中的接收者只需要1次计算；GKA-SS方案在DCGKA方案的基础上添加了短签名，因此接收者同样需要1次计算。本文方案与ART方案都采用了棘轮树对用户进行处理，但不同点在于ART方案采用棘轮树中叶子节点进行X3DH密钥交换，因此发送方和接收者都需要\mathrm{l}\mathrm{o}\mathrm{g}n次密钥交换来完成密钥协商，但本文方案通过子树对用户进行子组划分，因此接收者只需要一次计算便能够完成密钥协商。

由于双线性映射的计算时间T_{\mathrm{p}\mathrm{e}}要高于幂指数运算的时间T_{\mathrm{e}\mathrm{x}\mathrm{p}}，单个接收者的计算开销，DCGKA方案要低于本文方案。但如图4所示，对于完成一次密钥协商的总计算开销，Sender Keys、DCGKA和GKA-SS方案的发送方计算开销都随着组规模的扩大呈线性增长，因此总计算开销远高于ART方案与本文方案。而相较于ART方案，在发送方的计算量同步增长的同时，本文方案能够保证接收者的计算量保持基本持平。综合考量发送方和接收者各自的计算开销，本文方案有着明显的优势。

4.3　通信开销分析

表3列出了Sender Keys、ART、DCGKA、GKA-SS方案和本文方案在群组创建、用户增删、密钥更新和消息传递中的通信开销复杂度对比。除了在创建一个群组时，所有方案中发送者的通信开销上都为O(n)，需要将信息发送给每一个群组用户，其他操作的通信开销在不同方案中存在差异。

在Sender Keys方案中所有的操作都是在两方协议中完成，因此所有通信开销为O(n)，总通信开销较大。另外四个方案的总通信开销对比如图5所示，DCGKA方案和GKA-SS方案发送者想要完成一次密钥更新其通信开销复杂度为O(n)，而组内每个接收者通信开销为O(\mathrm{1})，总体开销呈线性增长，但GKA-SS方案由于其复杂性通信开销更多。而采用棘轮树结构能够将通信开销由O(n)减小到O(\mathrm{l}\mathrm{o}\mathrm{g}n)，相比于ART方案，本文方案不仅通过棘轮树结构降低发送者的通信开销，并且通过与广播加密的结合将接收者的通信开销减小到O(\mathrm{1})，相比于同等安全属性的其他方案具有更低的通信效率。

5　 结 语

本文将基于签名的可聚合广播方案与棘轮树结构相结合，借鉴密钥封装与解封的思想，设计了可聚合共享棘轮树算法并提出了一个基于可聚合广播的安全可追溯组密钥协商协议TGKA，弥补了以棘轮树结构为核心的方案中缺乏密钥可追溯性的问题。本文从安全性、计算开销和通信开销等多方面将所提协议方案与已有方案进行了对比实验，通过形式化安全分析证明了TGKA协议能够满足密钥隐私性、前后向安全和密钥泄露后的可追溯性，在保证了各项安全特性的基础上有较好的实验结果，在数十至数百用户的中型组中具备一定的可行性。本文协议的身份认证是一种隐式的认证，所有的签名都基于用户的身份标识符，因此能够在一定程度上进行身份认证，但并未对组密钥协商中的密钥密文和消息密文进行签名。利用可聚合共享棘轮树算法，设计一个包含身份认证、不可否认性等更多安全属性的组密钥协商协议值得更进一步的研究。

参考文献

[1] ALWEN J， CORETTI S， DODIS Y， et al. Security analysis and improvements for the IETF MLS standard for group messaging［C］//Annual International Cryptology Conference. Berlin： Springer， 2020： 248-277.10.1007/978-3-030-56784-2_9. DOI: 10.1007/978-3-030-56784-2_9 .

[2] BIENSTOCK A， FAIROZE J， GARG S， et al. A more complete analysis of the signal double ratchet algorithm［C］//Annual International Cryptology Conference. Berlin： Springer， 2022： 784-813.10.1007/978-3-031-15802-5_27. DOI: 10.1007/978-3-031-15802-5_27 .

[3] BALBÁS D， COLLINS D， GAJLAND P. WhatsUpp with sender keys？ analysis， improvements and security proofs［C］//International Conference on the Theory and Application of Cryptology and Information Security. Berlin： Springer， 2023： 307-341.10.1007/978-981-99-8733-7_10. DOI: 10.1007/978-981-99-8733-7_10 .

[4] ALWEN J， AUERBACH B， BAIG M A， et al. Grafting key trees： Efficient key management for overlapping groups［C］//Theory of Cryptography Conference. Berlin： Springer， 2021： 222-253.10.1007/978-3-030-90456-2_8. DOI: 10.1007/978-3-030-90456-2_8 .

[5] 姜奇， 蔡明鑫， 程庆丰， 等. 面向分层无人机网络的去中心群组密钥管理方案［J］. 电子与信息学报， 2023， 45（5）： 1669-1677. DOI： 10.11999/JEIT220347 .

[6] JIANG Q， CAI M X， CHENG Q F， et al. Decentralized group key management scheme in hierarchical unmanned aerial vehicle network［J］. Journal of Electronics & Information Technology， 2023， 45（5）： 1669-1677. DOI： 10.11999/JEIT220347（Ch ）.

[7] BRECHER T， BRESSON E， MANULIS M. Fully robust tree-diffie-hellman group key exchange［C］//Cryptology and Network Security. Berlin： Springer， 2009： 478-497. DOI： 10.1007/978-3-642-10433-6_33 .

[8] 韩司， 郑宝昆， 曹奇敏. 基于逻辑密钥树的无线传感网络密钥管理方案［J］. 计算机应用， 2019， 39（5）： 1378-1384. DOI： 10.11772/j.issn.1001-9081.2018102175 .

[9] HAN S， ZHENG B K， CAO Q M. Logical key hierarchy plus based key management program for wireless sensor network［J］. Journal of Computer Applications， 2019， 39（5）： 1378-1384. DOI： 10.11772/j.issn.1001-9081.2018102175（Ch ）.

[10] 陈海红， 李军义. 新的基于身份认证的群密钥协商协议［J］. 计算机工程与应用， 2017， 53（21）： 103-109. DOI： 10.3778/j.issn.1002-8331.1605-0280 .

[11] CHEN H H， LI J Y. Novel ID-based group authenticated key agreement scheme［J］. Computer Engineering and Applications， 2017， 53（21）： 103-109. DOI： 10.3778/j.issn.1002-8331.1605-0280（Ch ）.

[12] COHN-GORDON K， CREMERS C， GARRATT L， et al. On ends-to-ends encryption： Asynchronous Group messaging with strong security guarantees［C］//Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2018： 1802-1819. DOI： 10.1145/3243734.3243747 .

[13] BHARGAVAN K， BARNES R， RESCORLA E. TreeKEM： Asynchronous decentralized key management for large dynamic groups a protocol proposal for messaging layer security（MLS）［EB/OL］. ［2018-05-03］.

[14] ALWEN J， HARTMANN D， KILTZ E， et al. Server-aided continuous group key agreement［C］//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security.New York：ACM， 2022： 69-82. DOI： 10.1145/3548606.3560632 .

[15] WEIDNER M， KLEPPMANN M， HUGENROTH D， et al. Key agreement for decentralized secure group messaging with strong security guarantees［C］//Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. New York：ACM， 2021： 2024-2045. DOI： 10.1145/3460120.3484542 .

[16] YANG Z Y， WANG Z Q， QIU F， et al. A group key agreement protocol based on ECDH and short signature［J］. Journal of Information Security and Applications， 2023， 72： 103388. DOI： 10.1016/j.jisa.2022.103388 .

[17] WU Q H， MU Y， SUSILO W， et al. Asymmetric group key agreement［C］//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2009： 153-170.10.1007/978-3-642-01001-9_9. DOI: 10.1007/978-3-642-01001-9_9 .

基金资助

国家重点研发计划项目(2022YFB3103300)

中央高校基本科研业务费专项资金资助项目(2042022kf1195)

国家自然科学基金(62172303)

国家自然科学基金(62076187)

湖北省重点研发计划项目(2022BAA039)

山东省重点研发计划项目(2022CXPT055)