Processing math: 6%
  • 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

基于身份的群组密钥分发方案

王后珍, 秦婉颖, 刘芹, 余纯武, 沈志东

王后珍, 秦婉颖, 刘芹, 余纯武, 沈志东. 基于身份的群组密钥分发方案[J]. 计算机研究与发展, 2023, 60(10): 2203-2217. DOI: 10.7544/issn1000-1239.202330457
引用本文: 王后珍, 秦婉颖, 刘芹, 余纯武, 沈志东. 基于身份的群组密钥分发方案[J]. 计算机研究与发展, 2023, 60(10): 2203-2217. DOI: 10.7544/issn1000-1239.202330457
Wang Houzhen, Qin Wanying, Liu Qin, Yu Chunwu, Shen Zhidong. Identity Based Group Key Distribution Scheme[J]. Journal of Computer Research and Development, 2023, 60(10): 2203-2217. DOI: 10.7544/issn1000-1239.202330457
Citation: Wang Houzhen, Qin Wanying, Liu Qin, Yu Chunwu, Shen Zhidong. Identity Based Group Key Distribution Scheme[J]. Journal of Computer Research and Development, 2023, 60(10): 2203-2217. DOI: 10.7544/issn1000-1239.202330457
王后珍, 秦婉颖, 刘芹, 余纯武, 沈志东. 基于身份的群组密钥分发方案[J]. 计算机研究与发展, 2023, 60(10): 2203-2217. CSTR: 32373.14.issn1000-1239.202330457
引用本文: 王后珍, 秦婉颖, 刘芹, 余纯武, 沈志东. 基于身份的群组密钥分发方案[J]. 计算机研究与发展, 2023, 60(10): 2203-2217. CSTR: 32373.14.issn1000-1239.202330457
Wang Houzhen, Qin Wanying, Liu Qin, Yu Chunwu, Shen Zhidong. Identity Based Group Key Distribution Scheme[J]. Journal of Computer Research and Development, 2023, 60(10): 2203-2217. CSTR: 32373.14.issn1000-1239.202330457
Citation: Wang Houzhen, Qin Wanying, Liu Qin, Yu Chunwu, Shen Zhidong. Identity Based Group Key Distribution Scheme[J]. Journal of Computer Research and Development, 2023, 60(10): 2203-2217. CSTR: 32373.14.issn1000-1239.202330457

基于身份的群组密钥分发方案

基金项目: 国家自然科学基金项目 (62272348, 62272385, 62272389, U19B2021, U20B2064);先进密码技术与系统安全四川省重点实验室开放基金 (SKLACSS-202203);国家重点研发计划项目 (2022YFB4500800);中央高校基本科研业务费专项资金 (2042022kf002);湖北省重点研发计划 (2022BAA041)
详细信息
    作者简介:

    王后珍: 1981 年生.博士,副教授. CCF 会员.主要研究方向为公钥密码学、抗量子密码.

    秦婉颖: 2000 年生.硕士研究生.主要研究方向为公钥密码学.

    刘芹: 1978 年生.博士,副教授. CCF 会员. 主要研究方向为数据隐私保护、物联网安全、嵌入式系统安全.

    余纯武: 1974 年生. 博士,副教授. 主要研究方向为图象处理、信息隐藏、算法设计与分析、生物计算机模拟.

    沈志东: 1975 年生. 博士,副教授,CCF会员. 主要研究方向为可信计算、分布式系统与网络安全、大数据分析与可视化技术

    通讯作者:

    刘芹(qinliu@whu.edu.cn

  • 中图分类号: TP309

Identity Based Group Key Distribution Scheme

Funds: The work was supported by the National Natural Science Foundation of China (62272348, 62272385, 62272389, U19B2021, U20B2064), the Open Fund of Advanced Cryptography and System Security Key Laboratory of Sichuan Province (SKLACSS-202203), the National Key Research and Development Program of China (2022YFB4500800), the Fundamental Research Funds for the Central Universities (2042022kf002), and the Key Research and Development Projects in Hubei Province (2022BAA041).
More Information
    Author Bio:

    Wang Houzhen: born in 1981. PhD, associate professor. Member of CCF. His main research interests include public key cryptography and post-quantum cryptography

    Qin Wanying: born in 2000. Master candidate. Her main research interest includes public key cryptography

    Liu Qin: born in 1978. PhD, associate professor. Member of CCF. Her main research interests include data privacy preservation, IoT security, and embedded system security

    Yu Chunwu: born in 1974. PhD, associate professor. His main research interests include image processing, information hiding, algorithm design and analysis, and biological computer simulation

    Shen Zhidong: born in 1975. PhD, associate professor. Member of CCF. His main research interests include trusted computing, distributed systems and network security, and big data analysis and visualization techniques

  • 摘要:

    随着人们越来越倾向于使用即时通讯软件进行交流,保障群聊中消息的安全性成为一个亟需解决的问题. 因此,基于国密SM9算法提出了一种基于身份的群组密钥分发方案,并进行了严格的安全性证明;提出的方案相较于Guo等人、Meng等人提出的方案在便捷性和兼容性上更具优势,同时,相较于Wu等人在欧密会上提出的非对称群组密钥协商协议也有群组密钥管理和兼容性方面的优势. 此外,还给出了所提方案在即时通讯群聊及点对点通信场景下的应用示范,进一步证明了所提方案在通信开销和密钥管理方面要优于目前典型即时聊天软件中的安全群聊实现方法.

    Abstract:

    As people are increasingly inclined to use instant messaging software for communication, ensuring the security of messages in group chats has become an urgent issue. Therefore, we propose an identity-based group key distribution scheme based on the national cryptographic algorithm SM9 and provide rigorous security proofs. The proposed scheme has advantages over the ones introduced by Guo et al. and Meng et al. in terms of convenience and compatibility. Additionally, our scheme outperforms the asymmetric group key agreement protocol proposed by Wu et al. at the Eurocrypt in terms of group key management and compatibility. Furthermore, we provide application demonstrations of the proposed scheme in both instant messaging group chats and peer-to-peer communication scenarios, further proving that the proposed scheme outperforms current typical secure group chat implementation methods in terms of communication overhead and key management in instant messaging software.

  • 游戏博弈作为现实世界的一种高度抽象,具有良定义、易检验算法性能等特点,成为目前智能决策研究的热点. 近些年,一系列人工智能方法在游戏中均取得了很好的效果,甚至战胜人类,彰显出人工智能在现实应用中极大的潜力,具有重大的意义. 而且,不断有新的算法在各类游戏博弈中取得重要进展. 如在围棋中,以AlphaGo[1]和AlphaZero[2]为代表的人工智能战胜了李世石、柯洁等人类顶尖高手;Libratus[3]和Pluribus[4]战胜德州扑克(Texas Hold’em)职业冠军;Suphx[5]在天凤麻将平台超越职业选手段位;AlphaStar[6],OpenAI-Five[7]分别在星际争霸中与DOTA2中战胜人类世界冠军等.

    目前针对棋牌类游戏存在多种求解方式,例如:1)基于强化学习(reinforcement learning)的方法[1-2, 6-8]采用试错的方式学习智能体在自身观测状态下的最优策略,通过深度神经网络拟合状态动作值函数或状态动作概率分布的方法,根据获取到的经验更新相应神经网络,得到更好的策略;2)基于反事实遗憾最小化(counterfactual regret minimization,CFR)的方法[3-4, 9-10]采用类似在线学习的方式,在每一轮迭代中计算每种自身观测状态下所有动作的反事实遗憾,根据遗憾匹配(regret matching)等遗憾最小化方法生成新一轮策略,尝试降低新策略的遗憾,最终输出每一轮的平均策略;3)通过在线优化的方法,如一阶方法(first order method)[11],将中小规模二人零和博弈问题建模为一个凸优化问题进行求解.

    国内扑克游戏,如掼蛋、斗地主等,作为一类非完美信息博弈,相较于目前已有较好算法的德州扑克等游戏博弈有较大差异. 国内扑克游戏具有信息集状态多、动作空间复杂、状态动作难以约简等特点[8],因此大部分现有方法难以应用. 例如用于求解德州扑克的蒙特卡洛反事实遗憾最小化[10,12](Monte Carlo counterfactual regret minimization,MCCFR)算法虽然能缓解在求解德州扑克问题时由于博弈树大小而引发的难以迭代遍历问题[13],但是斗地主或掼蛋这样无法简单进行状态动作空间约简的扑克游戏,其博弈树规模仍过于庞大,无法简单适用;经典的强化学习方法如DQN[14-15],A3C[16-17]等则由于较大的动作空间导致这些算法的网络结构难以较好地拟合扑克类的值函数[8],从而无法在掼蛋、斗地主等国内扑克类游戏中取得较好的效果.

    深度蒙特卡洛[8](deep Monte Carlo,DMC)方法是目前针对国内扑克游戏设计人工智能算法所面临问题的主要解决途径之一. DMC方法采用蒙特卡洛采样评估状态动作值函数,其考虑到斗地主等扑克游戏动作不易约简且动作之间由于出牌相似而具有相似关系的特点,通过将动作进行编码与状态一同作为神经网络的输入,借此解决动作空间大且不易约简的问题. 同时DMC方法采用TorchBeast[18]训练框架,通过大量采样来降低训练方差,在斗地主游戏中取得了较好的效果. 但是单纯的DMC方法在面对以掼蛋为代表的更大规模扑克博弈时,依然面临一些问题:1)DMC方法需要大量的训练时间. 采用DMC方法的DouZero系统,在对抗专家策略的监督学习方法时,在斗地主环境中需要10天时间才能达到50%的对抗胜率. 因此对于更复杂的扑克博弈如掼蛋,其信息集数量、信息集大小、动作空间、每局历史信息长度均远超斗地主,需要更多的训练时间. 2)DMC方法实际执行策略过程中总是选择第1个状态动作值最大的动作,因此在实际对局过程中更容易被对手利用. 同时由于DMC训练过程中的高方差原因,较小的值扰动也可能造成较大的策略差异,从而造成策略质量较大的变化.

    为了有效解决训练时间问题,考虑到在常见的扑克博弈中,存在大量的已有知识或领域知识,因此如果能够将现有的先验知识融入算法的训练过程,将大大提升算法的训练效率. 为此文献[19]提出一种暖启动(warm start)方法,该方法针对反事实遗憾最小化算法进行暖启动,通过已有策略,赋予在每个信息集中的动作一个合适的反事实遗憾值,从而实现对于策略求解的加速计算. 然而,暖启动方法需要获取整个博弈信息,从而进行期望值与遗憾值的计算,因此对于大规模扑克博弈需要进行大幅度的状态与动作的约简,而这对于斗地主、掼蛋等国内主流扑克博弈难以实现,相关方法较难直接应用.

    因此本文提出了一种软深度蒙特卡洛(soft deep Monte Carlo,SDMC)方法,对以掼蛋为代表的国内扑克类博弈进行求解. 首先针对DMC方法需要大量训练时间的问题,提出通过软启动(soft warm start)方式,结合已有策略知识,在训练过程中进行已有策略决策与SDMC策略模型决策的混合决策,辅助进行策略训练,提升策略收敛速度;然后在实际对战过程中依据策略模型状态动作值预测,通过软动作采样(soft action sample,SAS),缓解DMC方法仅选择最大值动作时,由于策略固定而易被对手利用等问题,增强策略鲁棒性. 最后,本文在掼蛋博弈中进行实验验证. 本文提出的SDMC方法在第2届“中国人工智能博弈算法大赛”取得冠军,在与DMC方法和第1届冠军等其他参赛算法进行对比实验证明了本文所提出的方法在掼蛋扑克博弈中的有效性.

    本节首先介绍现有扑克类博弈的求解方法,并分析各个方法的优缺点;其次着重介绍在斗地主中的最新方法,从而更好地介绍本文提出的SDMC方法.

    DMC方法是由Zha 等人[8]提出,是应用在斗地主环境下DouZero AI系统中的核心算法. DMC方法考虑到斗地主等扑克游戏动作不易约简且动作之间存在相似关系的特点,通过将动作进行编码与状态一同作为神经网络的输入,解决现有其他方法在大规模具有相似动作的空间下不适用的问题. 具体来讲,DMC方法尝试训练神经网络V,使其输出值与实际的值函数尽可能地相近:

    θ=argminθ||Q(τit,ai)Vθ(τit,ai)||, (1)

    其中θ为神经网络V的参数,且

    Q(τit,ai)=EτP(τ|π,τit,ai)[R(τ)] (2)

    为在当前动作观测历史τit下,选择动作ai后,依据当前策略π所能获得的期望奖励值.

    在训练过程中,DMC方法采用ϵ-贪心的策略选择方法,即给定神经网络和参数Vθ,训练过程中选择的策略

    πϵ(τit,ai)=(1ϵ)I(ai==a)+ϵ|A|, (3)

    其中|A|为当前可选动作数量,a=argmaxaV(τit,a)I()为指示函数(indicating function)且仅在参数为真时结果为1,否则为0,argmax函数选择值最大的第1个动作.

    在实际博弈过程中,DMC方法直接选择值函数最大的动作,即在AOH选择τit,可选动作集合A下,策略为

    π(τit,ai)=I(ai==argmaxaV(τit,a)). (4)

    扑克类游戏作为一种天然的非完美信息博弈,已经具有悠久的研究历史.

    针对竞争型的扑克类游戏,如德州扑克,通常采取求解纳什均衡的方式. 其中为代表的CFR[9]采用自博弈的方式进行训练. 在训练的每一轮中,个体与上一轮训练出的策略进行对抗,并依靠遍历整棵博弈树的方式计算策略的遗憾,通过最小化遗憾的方式最终求解博弈的纳什均衡. 但受制于CFR的遍历过程,随着博弈规模的增加,遍历整棵博弈树需要极大的时间与空间,因此MCCFR[10]方法采取采样的方式更新博弈策略的遗憾,降低算法需求. 虽然CFR类的方法在以德州扑克为代表的博弈中取得惊人的效果,但是其方法限制了其在大规模环境下的应用,往往需要结合博弈约简(abstraction)[20]方法,降低博弈树规模. 因此难以处理如掼蛋、斗地主等非完美信息博弈.

    而对合作型的扑克类游戏如Hanabi,则有着更为多样的求解范式. 不同于竞争型博弈下致力于求解纳什均衡而将其看作一个优化问题,合作型博弈也可以建模为一类学习问题[21]. 其中贝叶斯动作编码器(Bayesian action decoder,BAD)[22-23]方法在Hanabi中取得了最为理想的成果. BAD方法使用深度强化学习的方式在公共信念中探索合适的策略,但此类方法仅面向纯合作类场景选取确定性动作,无法简单适用到如掼蛋这样具有竞争合作的混合场景中.

    针对掼蛋、斗地主等牌类博弈面对状态、动作空间复杂不易求解等问题,You等人[24]提出通过一种组合Q网络(combinatorial Q-network)的方式,将决策过程分为组牌和出牌2个步骤. 但组牌过程耗时巨大,不利于在大规模环境下的训练.DeltaDou方法[25]通过贝叶斯推断的方式推理对手的卡牌,之后采用类似于AlphaZero的方式进行蒙特卡洛树搜索,从而对策略进行训练,但仍需约20天的训练时间才能在斗地主中达到专家水平.

    掼蛋扑克博弈问题由于具有无法观测对手手牌内容、独立决策的特性,经常被建模为一个部分可观测的马尔可夫决策过程(partially observable Markov decision process,POMDP). 在部分可观测马尔可夫决策过程中,智能体i表示智能体的编号索引,状态s表示当前实际状态. 在每一个时间点t,每一个智能体i都会观测到一个观测状态oi=Z(S,i),这里函数Z是一个观测函数. 在每次智能体观测到观测状态oi时,智能体i都可以选择一个动作 {\boldsymbol{a}} . 因此,智能体 i 的策略 {\pi }_{i} 可以看做一个动作观测历史(action-observation history,AOH) {\tau }_{t}=\{{o}_{0}^{i},{a}_{0}^{i},{o}_{1}^{i},{a}_{1}^{i},…o_{t-1}^i,a_{t-1}^i,{o}_{t}^{i}\} 的函数. 每当所有智能体执行一个动作后,当前状态 {s}_{t} 会根据环境转移函数转换到新的状态 {s}_{t+1}\sim \mathcal{P}\left({s}_{t+1}|{s}_{t},{{\boldsymbol{a}}}\right) ,其中 \boldsymbol{a}=({a}^{0},{a}^{1},… ) 为所有智能体的联合动作,每个智能体 i 会收到环境的奖励 {r}_{t}^{\;i}={\mathcal{R}}^{i}({s}_{t},\boldsymbol{a}) . 因此当前状态下的轨迹可用 {\tau }_{t}=\left\{{s}_{0},{\boldsymbol{a}}_{0},s_1,{\boldsymbol{a}}_1,… ,s_{t-1},{\boldsymbol{a}}_{t-1},{s}_{t}\right\} 表示. 在POMDP中,智能体 i 目标在于最大化自身奖励 {J}_{\pi }={E}_{\tau \sim P\left(\tau \right|\pi )}\left[R\left(\tau \right)\right] ,其中函数 R\left(\tau \right)=\displaystyle\sum_{t}{{\gamma }^{t}r}_{t} 为智能体收到的折扣累计奖赏, \gamma 为累计折扣因子.

    掼蛋扑克博弈,具有序贯决策特性,即每个AOH下最多有1个智能体进行决策,状态转移函数可约简为 {s}_{t+1}=\mathcal{P}\left({s}_{t+1}|{s}_{t},{a}^{i}\right) ,其中 {a}^{i} 为当前智能体决策. 由于扑克博弈的关键信息通常由2部分组成:手牌、已打出牌等当前状态信息与所有参与博弈的智能体的历史动作信息,且可以通过当前观测状态与历史动作信息对牌局进行复盘,故掼蛋博弈的AOH可由 {\tau }_{t}^{\;i}=\left\langle{Z\left({s}_{t},i\right),{H}_{t}}\right\rangle 进行表示,其中 {h}_{t}^{i}\in {H}_{t} 为智能体 i 在包含时刻 t 前的动作历史 \left\{{a}_{0}^{i},{a}_{1}^{i},\dots ,{a}_{t}^{i}\right\} . 掼蛋扑克博弈不同于普通的POMDP,其奖励值往往仅存在于终止状态集合 {S}_{\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}} ,因此对于非终止状态 {s}_{t} ,所有智能体获取到的奖励为0,即 \forall i,{s}_{t}\notin {S}_{\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}},{\mathcal{R}}^{i}\left({s}_{t},\boldsymbol{a}\right)=0 ,因此累计折扣因子通常可以设置为1.

    本节将介绍SDMC方法,SDMC方法包含软启动与软动作采样2个过程,解决现有方法在以掼蛋为例的扑克博弈中的问题. 同时,为了更好地进行深度学习训练,本文亦创新性地提出了一种针对深度学习的掼蛋扑克博弈编码方法.

    DMC方法将动作观测历史与可选择动作进行结合,作为神经网络输入,通过蒙特卡洛采样方式对值函数进行拟合,采样策略根据神经网络预测值采用 \epsilon -贪心的策略.

    由于DMC方法采用随机网络进行初始化,再通过自博弈的方式不断自我对战产生样本,并进行更新. 因此在训练初期DMC自博弈产生的博弈轨迹样本的值更多是面对对手使用随机策略时的动作值,由此产生出的策略往往并不具有实用价值,只是训练迭代过程中的中间策略,为后续更强策略的训练提供基础.

    为了加快策略的训练过程并尽量降低因加速训练过程而产生的影响,本文提出了软启动DMC方法,通过软启动的方式进行训练,借助已有策略,尽量加速训练过程.

    具体的,对于已有策略 {\pi }_{\mathrm{E}} ,软启动DMC尝试融合借鉴预训练方法. 常见的预训练通过训练一个神经网络模型 {V}_{\theta } ,使得其输出预测值与已有策略值函数尽可能相近,即

    \begin{array}{c}{\theta }^{\;*}=\underset{\theta }{\mathrm{arg}\;{\mathrm{min}}}\left| \left|{Q}_{\mathrm{E}}\left({\tau }_{t}^{\;i},{a}^{i}\right)-{V}_{\theta }\left({\tau }_{t}^{\;i},{a}^{i}\right)\right| \right|,\end{array} (5)

    其中 {Q}_{\mathrm{E}}\left({\tau }_{t}^{\;i},{a}^{i}\right) 为已有策略的值函数.

    但是已有策略的值函数由于掼蛋扑克博弈规模过大通常难以直接获取,因此可以通过蒙特卡洛采样的方式进行自博弈模拟评估:

    \begin{array}{c}{Q}_{\mathrm{E}}\left({\tau }_{t}^{\;i},{a}^{i}\right)={E}_{\tau \sim P\left(\tau |{\pi }_{\mathrm{E}},{\tau }_{t}^{\;i},{a}^{i}\right)}\left[R\left(\tau \right)\right]. \end{array} (6)

    但由于已有策略具有先验知识,有较多的动作并不会主动选择,故直接自博弈评估时可能存在较多的动作没有给出评估值,从而出现如过估计[26]等问题. 而通过在已有策略 {\pi }_{\mathrm{E}} 中加入 \epsilon -贪心的方式可以部分缓解该问题,但仍面临若 \epsilon 设置较大,则自博弈的评估并非已有策略值;而若 \epsilon 设置较小,则由于探索样本比例较低,需要大量的训练才可进行较好的拟合,出现与最初降低训练时间需求的初衷相违背的问题.

    考虑到由于已有策略并非一定最优,经过初始化过后仍需采取自博弈的方式进行训练,因此软启动考虑在训练过程中融入已有策略而非如文献[19]直接去拟合已有策略方式,如图1(a)所示. 这样既融入了已有策略对当前模型训练进行加速,同时又避免了普通的暖启动方法所面临的过估计等问题.

    图  1  SDMC的整体流程
    Figure  1.  Overview of SDMC

    具体来讲,软启动结合已有策略与当前模型生成策略的自博弈评估值 {\widetilde{Q}}_{\mathrm{E}}\left({\tau }_{t}^{\;i},{a}^{i}\right) 代替式(5)中的已有策略评估值 {Q}_{\mathrm{E}}\left({\tau }_{t}^{\;i},{a}^{i}\right) ,即

    \begin{array}{c}{\theta }^{\;*}=\underset{\theta }{\mathrm{arg}\;{\mathrm{min}}}\left| \left|{\widetilde{Q}}_{\mathrm{E}}\left({\tau }_{t}^{\;i},{a}^{i}\right)-{V}_{\theta }\left({\tau }_{t}^{\;i},{a}^{i}\right)\right| \right|. \end{array} (7)

    其中软启动所采用的评估值由策略 {\widetilde{\pi }}_{\mathrm{E}} 生成, {\widetilde{\pi }}_{\mathrm{E}} 结合了式(4)中当前模型生成的策略 \pi 与已有策略 {\pi }_{\mathrm{E}} :

    \begin{array}{c}{\widetilde{\pi }}_{\mathrm{E}}\left({\tau }_{t}^{\;i},{a}^{i}\right)=\dfrac{\epsilon }{\left|A\right|}+\left(1-\omega -\epsilon \right)\pi \left({\tau }_{t}^{\;i},{a}^{i}\right)+\omega {\pi }_{\mathrm{E}}\left({\tau }_{t}^{\;i},{a}^{i}\right),\end{array} (8)

    为混合了2种决策模型的 \epsilon -贪心策略,其中权重 \omega 为软启动参数,可随着训练的进行而衰减.

    具体算法流程如算法1所示.

    算法1. 软启动蒙特卡洛.

    初始化:初始化经验缓存 {\left\{{B}_{i}\right\}}_{i=1}^{n} 与经验缓存 {\left\{{D}_{i}\right\}}_{i=1}^{n}    为空,其中 n 为智能体数量;随机初始化SDMC   神经网络 {\left\{{V}_{i}\right\}}_{i=1}^{n} 的参数 {\theta }_{i} .

    ① for episode=1 to max_episodes

    ②  for t=0 to T

    ③    i\leftarrow 当前行动智能体编号;

    ④   智能体 i 观测到动作观测历史 {\tau }_{t}^{\;i}

    ⑤   由式(8)计算软启动策略 {\widetilde{\pi }}_{\mathrm{E}}^{i}

    ⑥   选取动作 {a}^{i}\sim{\widetilde{\pi }}_{\mathrm{E}}^{i}

    ⑦   存储样本 \left\{{\tau }_{t}^{\;i},{a}^{i}\right\} 至经验缓存 {B}_{i}

    ⑧  end for

    ⑨  获得环境奖励 \boldsymbol{r}=({r}_{1},{r}_{2},\dots ,{r}_{n})

    ⑩  for i=1 to n

    ⑪   for \left\{{\tau }_{t}^{\;i},{a}^{i}\right\} in {B}_{i}

    ⑫     存储样本 \left\{{\tau }_{t}^{\;i},{a}^{i},{r}_{i}\right\} 至经验缓存 {D}_{i}

    ⑬    end for

    ⑭    清空经验缓存 {B}_{i}

    ⑮    while {D}_{i}.length > batch\_size

    ⑯     从 {D}_{i} 采样并更新神经网络 {V}_{i}

    ⑰    end while

    ⑱  end for

    ⑲ end for

    ⑳ 输出:神经网络模型 {\left\{{V}_{i}\right\}}_{i=1}^{n} .

    对于掼蛋这类大规模扑克博弈,可以通过TorchBeast[18]框架进行并行训练. 具体对于算法1来说,每一个actor执行算法1中 ①~⑭步,并在每次循环开始之前与learner同步模型;learner执行⑮~⑰步.

    传统DMC方法在使用模型决策时,一般选择最大值的动作,即对于动作观测历史 {\tau }_{t}^{\;i} 和可选动作集合 A ,由式(4)选择动作. 但由于仅选择最大值的动作容易受到微小扰动的干扰,如训练方差等,导致策略大幅度变化,因此评估值较为接近的动作都有可能是最好的动作,且在实际使用过程中完全确定性的策略较易被对手猜测出自身手牌等信息,因此采用带有软动作采样(soft action sample,SAS)的动作选择方式,流程如图1(b)所示,在保证所选动作在当前模型的评估下评估值变化不大的前提下,通过舍弃可选动作集合中值较低的动作,保留评估值与最大值接近的备选动作,构造备选动作集合 \hat{A} ,并在备选动作集合 \hat{A} 中对每一个动作的值进行softmax处理,按比例分配被选择的概率:

    \begin{array}{c}P\left({a}^{i}|{\tau }_{t}^{\;i},\theta \right)={\mathrm{e}}^{{V}_{\theta }\left({\tau }_{t}^{\;i},{a}^{i}\right)}/\displaystyle\sum\limits _{{a}'\in \hat{A}}{\mathrm{e}}^{{V}_{\theta }\left({\tau }_{t}^{\;i},{a}'\right)},\end{array} (9)

    最终根据概率分布 P\left(a|{\tau }_{t}^{\;i},\theta \right) 选择动作. 其中备选集合 \hat{A} 的选择方式可通过设定最低阈值的形式,即对于阈值 {v}_{{\tau }_{t}^{\;i}} ,备选集合 \hat{A}

    \begin{array}{c}\hat{A}=\left\{{a}^{i}|\forall {a}^{i}\in A,{V}_{\theta }\left({\tau }_{t}^{\;i},{a}^{i}\right)\ge {v}_{{\tau }_{t}^{\;i}}\right\}. \end{array} (10)

    对于阈值的选择需要保证其与最大值尽量接近,可根据当前所有动作的值的分布选择. 具体而言,可以通过设置较小的阈值权重 {\omega }'选择 {v}_{{\tau }_{t}^{\;i}}

    \begin{split} {v}_{{\tau }_{t}^{\;i}}=\; &\underset{{a}^{i}}{\mathrm{max}}{V}_{\theta }\left({\tau }_{t}^{\;i},{a}^{i}\right)- {\omega }'\left(\underset{{a}^{i}}{\mathrm{max}}{V}_{\theta }\left({\tau }_{t}^{\;i},{a}^{i}\right)-\underset{{a}^{i}}{\mathrm{min}}{V}_{\theta }\left({\tau }_{t}^{\;i},{a}^{i}\right)\right)=\\ & \left(1-{\omega }'\right)\underset{{a}^{i}}{\mathrm{max}}{V}_{\theta }\left({\tau }_{t}^{\;i},{a}^{i}\right)+{\omega }'\underset{{a}^{i}}{\mathrm{min}}{V}_{\theta }\left({\tau }_{t}^{\;i},{a}^{i}\right). \\[-1pt] \end{split} (11)

    原则上,阈值的选择应保证将所有最优动作筛选出来,并摒弃所有非最优动作. 若能精确估计所有动作的 Q 值,则权重 {\omega }'应设为0,即仅选择最优的动作. 但由于训练过程中的采样带来的方差扰动,使得最优动作的 Q 值并非准确值,故而需采用较小的权重. 随着训练过程的增加, Q 值愈发准确,可适当降低权重大小.

    软动作采样算法流程如算法2所示.

    算法2. 软动作采样.

    输入:决策模型 {V}_{\theta } ,动作观测历史 {\tau }_{t}^{\;i} ,可选动作      集合 A ,阈值权重 {\omega }'

    输出:模型最终选择动作 {a}^{i} .

    ① 由式(11)计算阈值 v

    \hat{A}\leftarrow \left\{{a}'|\forall {a}'\in A,{V}_{\theta }\left({\tau }_{t}^{\;i},{a}'\right)\ge v\right\}

    \boldsymbol{P}\leftarrow \left(0,0,\dots ,0\right) ; /*初始化每个动作的概率为0*/

    ④ for {a}' in \hat{A}

    ⑤   由式(9)计算每个动作的概率 \mathit{P}\left({a}'\right)

    ⑥ end for

    {a}^{i}\sim\boldsymbol{P} ; /*根据概率分布 \boldsymbol{P} 采样一个动作 {a}^{i} */

    ⑧ 返回结果 {a}^{i} .

    对状态信息进行编码是深度强化学习在扑克环境中进行应用的重要组成部分,本节从DouZero[8]针对斗地主的编码方法出发,根据掼蛋扑克游戏与斗地主的不同,创新性地提出一种适用于掼蛋扑克游戏的编码框架.

    对于掼蛋扑克牌局状态的编码应至少包含3部分:私有信息、当前可出牌与公共信息. 私有信息一般则为自己的手牌;当前可出牌包含所有可能出牌动作;公共信息包含出牌记录与对局信息,牌局信息指如掼蛋中的牌局等级信息、当前其余玩家手牌数量等当前对局的信息. 在此基础上可以添加额外的信息辅助深度网络进行训练.

    状态的编码均采用1位有效编码的形式. 手牌信息根据游戏使用的牌数量构建不同大小的空矩阵,若使用 n 副牌则构建 n\times (4\times 13+2) 大小的矩阵,其中 4\times 13+2 表示1副牌,4为花色索引,13为点数索引,2表示大小王,当拥有某张手牌时,对应位置的矩阵数值置为1. 对于标准掼蛋规则,由于使用2副牌,因此 n=2 ,具体卡牌编码如图2“卡牌表示”部分所示.

    图  2  掼蛋扑克信息编码示例
    Figure  2.  An example of information encoding in GuanDan poker game

    出牌动作的编码类似手牌编码方式,分别对出牌动作的类型、大小与所使用的牌进行编码. 对类型、大小的编码可解决相同出牌具有不同出牌类型与大小情况,如掼蛋中部分具有逢人配的顺子等,以及区分在编码出牌记录时无出牌记录的0填充编码与“过牌”(PASS)在编码时的区别,并提供额外的信息辅助神经网络处理,如图2所示.

    对于出牌记录的处理主要包括对出牌动作的编码与出牌动作结构的组织. 对于SDMC与DMC等方法,出牌记录信息会被输入到循环神经网络,因此可采取序列式结构对出牌进行组织,即从下家出牌到智能体自己出牌为止1轮的出牌编码进行拼接.

    本节对本文提出的SDMC方法进行实验分析,使用掼蛋扑克环境,衡量SDMC方法中软启动的加速训练效果,并分别与第1届、第2届“中国人工智能博弈算法大赛”的参赛算法对比,证明SDMC方法的有效性.

    掼蛋是国内一种广泛流传的扑克类博弈. 掼蛋博弈使用2副扑克牌,共108张牌,采取2对2的模式对抗,其中每个博弈玩家与对家为1支队伍进行对抗. 本文采用第2届“中国人工智能博弈算法大赛”中的掼蛋规则,下面简要介绍.

    1) 等级. 1局掼蛋博弈可以分为若干小局,每小局根据双方队伍等级中最高的决定当前牌局等级,并依据小局胜负情况更新双方的等级. 掼蛋对局中初始双方等级为2,之后依次为3,4,5,6,7,8,9,10,J,Q,K,A.

    2) 升级. 每小局对战结束后,仅第1个出完牌的玩家(称为上游)所在队伍可以升级,升级数依据队友出完牌的顺序决定:若队友第2个出完牌(称为二游),则升3级;第3个出完牌(称为三游),则升2级;若队友最后1个出完牌(称为下游),则只升1级.

    3) 获胜条件. 当一方队伍到达等级A,并且队伍中一人获得上游,另一人获得二游或者三游.

    4) 特殊牌. 掼蛋中和当前牌局等级相同的牌为级牌,其中红桃级牌称为逢人配,可当作任意牌与其他花色牌组合使用.

    5) 牌型. 掼蛋中牌型如下:单张、对子、三连对、三同张、二连三、三带二、顺子、同花顺、炸弹、天王炸. 其中炸弹张数多者为大,同样张数按照点数排序,同花顺大于任意不超过5张的炸弹,天王炸为2张大王和2张小王为最大牌型.

    6) 牌点大小. 掼蛋中牌点从大到小依次为:大王、小王、级牌、A、K、Q、J、10、9、8、7、6、5、4、3、2. A在搭配成三连对、二连三、顺子、同花顺时,可视作1.

    7) 进贡、还贡. 从第2小局开始,由上一轮的下游向上游进贡,挑选1张除红心级牌之外最大的牌给上游. 上游选择1张不大于10的牌给下游还贡. 如果上一局出现一方队伍获得三游和下游,则队伍2人均向对方队伍分别进贡和接受还贡. 如进贡方有2个大王,则可以不进贡.

    掼蛋由于使用2副牌,因此具有更高的求解复杂度,对算法训练效率提出了更大挑战. 仅第1轮发牌后的信息集的数量级约为1020,远超斗地主等扑克博弈(斗地主的第1轮发牌后数量级约1014,如考虑去除斗地主的花色影响约为108). 同时考虑到各个玩家拥有更多的手牌产生的指数级增长的可选动作以及等级、逢人配等因素,掼蛋实际信息集数量与大小远超斗地主等扑克博弈.

    本节主要描述了基于SDMC的掼蛋智能体实现细节,包含整体架构、状态编码方式与奖励设计3个方面.

    1) 整体架构细节

    基于SDMC的掼蛋智能体主要由2部分组成:掼蛋贡、还牌规则决策模块与出牌的SDMC决策模块. 其中所使用的掼蛋贡、还牌规则决策模块采用第1届“中国人工智能博弈算法大赛”的冠军规则. 出牌的SDMC决策模块中,式(11)中 {\omega }'=\dfrac{1}{500} .

    SDMC的网络结构与文献[8]相似,均采用LSTM网络处理历史动作,通过6层全连接网络输出动作评估值.

    2) 状态编码方式

    掼蛋编码方式采用2.3节编码框架,每一部分的编码大小如表1所示.

    表  1  掼蛋环境状态编码
    Table  1.  State Representation of GuanDan Games
    类型 含义 one-hot编码长度
    出牌动作 卡牌的矩阵表示 108
    类型的矩阵表示 10
    大小的矩阵表示 15
    私有信息 手牌的卡牌矩阵表示 108
    手牌中逢人配数量 3
    公共信息 当前等级 13
    其他玩家剩余手牌 108
    上家已出卡牌矩阵表示 108
    对家已出卡牌矩阵表示 108
    下家已出卡牌矩阵表示 108
    最近一次的出牌动作 133
    上家最近一次出牌动作 133
    对家最近一次出牌动作 133
    下家最近一次出牌动作 133
    上家剩余手牌数量 28
    对家剩余手牌数量 28
    下家剩余手牌数量 28
    最近4轮出牌的联合表示 532
    下载: 导出CSV 
    | 显示表格

    3) 奖励设计

    如3.1节介绍的,掼蛋胜负取决于队伍积分是否超过A,因此通过判断大局胜利的方式给予2队智能体奖励,可能会导致较差的小局内策略获得正奖励,因此在掼蛋环境训练过程中,当小局结束时,对双方队伍给定奖励,奖励分配方式如表2所示,1—1—2—2表示完牌顺序分别为队伍1、队伍1、队伍2、队伍2的选手.

    表  2  掼蛋环境训练中的奖励设计
    Table  2.  Reward Functions Designed in GuanDan Games
    完牌顺序 队伍1获得奖励 队伍2获得奖励
    1—1—2—2 +3 −3
    1—2—1—2 +2 −2
    1—2—2—1 +1 −1
    2—1—1—2 −1 +1
    2—1—2—1 −2 +2
    2—2—1—1 −3 +3
    下载: 导出CSV 
    | 显示表格

    设计的奖励方式基本与掼蛋晋级方式相同,但当掼蛋遇到等级A时有所不同,由于当一方队伍到达等级A时想要获胜至少要有一个队友第1个完牌并且另一个队友不能最后一个完牌,因此若以队伍1达到等级A为例,完牌顺序1—1—2—2与完牌顺序1—2—1—2相同,剩余4种完牌顺序奖励也相同. 考虑到SDMC方法会尽量选择高评估值的动作,因此不对奖励函数进行修正很大程度上并不会影响训练策略的正确性,故智能体在训练过程中并未对等级A进行特殊处理.

    本节通过与不同算法的对比验证SDMC的效果. 具体而言,分别与第1届“中国人工智能博弈算法大赛”的冠军(1st Champion)与前2届16强(1st Top 16和2nd Top 16)进行比较. 实验中选取2种算法作为2支队伍,采取2种评估指标,分别评估对战双方团队的胜利与净胜小分情况.

    我们首先验证了经过30天训练的SDMC与其他方法的最终胜率与净胜小分,每场对战均进500次,并重复验证5次,最终胜率与标准差如表3所示. 表3中的数据表示算法1对阵算法2时的胜率,如SDMC对抗2nd Top 16胜率为97.5%,算法的排名顺序按照击败(胜率>50%)其他算法的顺序进行排序.

    表  3  不同算法对抗胜率
    Table  3.  Winning Percentage of Different Algorithms Against Each Other %
    算法1 算法2
    SDMC(本文) SDMC-无SAS 1st Champion 2nd Top 16 1st Top 16
    SDMC(本文) \ 51.0\pm 1.0 92.1\pm 1.0 97.5\pm 0.7 100.0\pm 0.0
    SDMC-无SAS 49.0\pm 1.0 \ 91.8\pm 0.9 97.2\pm 0.9 100.0\pm 0.0
    1st Champion 7.9\pm 1.0 8.2\pm 0.9 \ 62.2\pm 1.0 97.3\pm 0.6
    2nd Top 16 2.5\pm 0.7 2.8\pm 0.9 37.8\pm 1.0 \ 94.9\pm 0.8
    1st Top 16 0.0\pm 0.0 0.0\pm 0.0 2.7\pm 0.6 5.1\pm 0.8 \
    注:“\”表示2种相同算法之间不对抗,没有对抗胜率.
    下载: 导出CSV 
    | 显示表格

    我们看到SDMC对战第1届比赛的冠军以及其他算法胜率均大于90%,对抗2nd Top 16和1st Top 16时胜率甚至分别大于97.5%和100%,因此可以认为SDMC的效果显著高于其他算法. 同时我们也对比了不使用SAS的SDMC(SDMC-无SAS)和使用SAS的SDMC的效果,对于测试的,使用SAS能够提升一定的SDMC的效果.

    同时对于净胜小分,我们详细列出了各种算法之间对战过程中双方小分的获得情况与净胜分,如表4所示. 可以看到SDMC在对战其他参赛方法的时候具有很高的3分得分率,即在掼蛋中有很高的双上(队伍分别以上游和二游完牌)概率,在对战1st Champion时达到44.3%,对战2nd Top 16时达到48.4%,对战1st Top 16时达到68.4%,因此对战过程中的净胜分非常高,对战1st Champion时平均每局净胜达到4955.6分. 同时观察到SDMC与SDMC-无SAS在对抗过程中无论是3分、2分、1分的占比还是净胜分均是SDMC更胜一筹,且SDMC在对战除2nd Top 16的对手时,净胜分均高于SDMC-无SAS.

    表  4  不同算法对抗时得分
    Table  4.  Score of Different Algorithms Against Each Other
    算法 对战算法 3分占比/% 2分占比/% 1分占比/% 净胜小分
    (500局)
    SDMC-无SASSDMC(本文) 23.0\pm 0.7 9.8\pm 0.3 13.7\pm 0.6 -95.6\pm 233.9
    1st Champion 12.3\pm 0.2 6.0\pm 0.4 13.9\pm 0.6 -495.6\pm 126.5
    2nd Top 16 8.5\pm 0.7 5.7\pm 0.6 12.8\pm 0.4 -5869.4\pm 96.7
    1st Top 16 2.0\pm 0.2 1.7\pm 0.2 7.5\pm 0.2 -7415.2\pm 47.1
    SDMC(本文)SDMC-无SAS 23.4\pm 0.6 11.3\pm 0.4 15.6\pm 0.8 95.6\pm 233.9
    1st Champion 12.4\pm 0.4 6.2\pm 0.4 13.8\pm 0.3 -4907.0\pm 80.0
    2nd Top 16 8.8\pm 0.4 5.7\pm 0.2 12.2\pm 0.4 -5885.4\pm 93.8
    1st Top 16 1.9\pm 0.2 1.8\pm 0.2 7.4\pm 0.3 -7387.4\pm 14.9
    SDMC(本文)1st Champion 44.3\pm 1.1 9.6\pm 0.2 13.8\pm 0.7 4955.6\pm 126.5
    SDMC-无SAS 44.2\pm 0.8 9.8\pm 0.3 13.7\pm 0.6 4907.0\pm 80.0
    2nd Top 16 23.3\pm 0.7 7.2\pm 0.3 16.3\pm 0.6 -1213.0\pm 128.4
    1st Top 16 8.7\pm 0.4 3.8\pm 0.4 14.4\pm 0.7 -5997.4\pm 140.3
    SDMC(本文)2nd Top 16 48.4\pm 0.4 12.0\pm 0.3 12.6\pm 0.3 5869.4\pm 96.7
    SDMC-无SAS 48.8\pm 0.7 12.0\pm 0.2 12.6\pm 0.4 5885.4\pm 93.8
    1st Champion 30.2\pm 0.4 9.2\pm 0.4 13.7\pm 0.4 1213.0\pm 128.4
    1st Top 16 10.1\pm 0.3 5.1\pm 0.3 15.7\pm 0.5 -5367.6\pm 63.4
    SDMC(本文)1st Top 16 68.4\pm 0.5 13.5\pm 0.6 7.0\pm 0.1 7415.2\pm 47.1
    SDMC-无SAS 68.1\pm 0.5 13.9\pm 0.5 7.0\pm 0.3 7387.4\pm 14.9
    1st Champion 50.5\pm 1.2 11.5\pm 0.4 11.0\pm 0.4 5997.4\pm 140.3
    2nd Top 16 42.6\pm 0.7 14.2\pm 0.4 12.4\pm 0.3 5367.6\pm 63.4
    下载: 导出CSV 
    | 显示表格

    最后为了验证本文提出的软启动方法的实验效果,我们比较了DMC方法、已有策略预训练的方法(基于策略启动的DMC)以及我们提出的采用软启动的SDMC方法对抗1st Top 16时的胜率与平均每小局净胜分曲线,如图3所示,其纵坐标分别为对抗的胜率与平均每小局净胜分,横坐标为训练所用的时间步. 对于每种方法,每次测试记录200局与1st Top 16的胜率与每小局净胜分结果,测试3次,图3绘制了测试的平均值与标准差. 其中基于策略启动的DMC采取与DMC和SDMC相同的神经网络架构与训练方式,不同之处在于基于策略启动的DMC每次自博弈生成轨迹是依据已有策略进行 \epsilon -贪心采样,训练基于策略启动的DMC模型. 基于策略启动的DMC所采用的已有策略与SDMC相同,均为1st Champion.

    图  3  3种方法在训练过程中对抗基准算法时的表现
    Figure  3.  Performance of three methods against baseline in training stage

    图3(a)中可以看到SDMC相较于DMC在训练初始阶段取得了较高的胜率提升速度,如在胜率达到60%时,SDMC需要约 2.7\times {10}^{8} 个时间步,而DMC则需要约 4\times {10}^{8} 个时间步,对于60%胜率,SDMC仅需DMC的68%训练开销. 同样地,在图3(b)中对于净胜小分,SDMC仅需 2.5\times {10}^{8} 个时间步即可达到净胜分大于0,而DMC需要约 3.8\times {10}^{8} 个时间步,SDMC降低了约 35\% 的时间需求.

    同时可以发现,相比于SDMC和DMC,基于策略启动的DMC训练效果不佳,原因可能正如2.1节中讨论的,仅通过已有策略生成数据在训练过程中由于掼蛋的动作空间过于庞大,因此无法很好地拟合未探索动作的值,因此存在过估计问题. 而DMC和SDMC因为存在通过神经网络去决策的步骤,当存在高评估值的动作时,由于倾向于选择高评估值动作,可以有效地对于这个动作的评估值进行验证,从而更好地评估.

    本文提出了一种针对掼蛋扑克博弈的软深度蒙特卡洛SDMC方法. SDMC方法在学习过程中不仅采用了软启动方法,结合已有策略,加速模型训练过程,同时采取软动作采样,在实际对战过程中,保证选择的策略在当前模型下的评估值变化不大的情况下对动作进行采样,降低训练过程中方差带来的影响,并增加被对手利用的难度. 在掼蛋环境下的实验表明,本文所提方法SDMC相较于现有方法有着更高的对战胜率与净胜得分. 之后,拟从软动作采样的角度出发,依据现有模型的动作评估值,结合子博弈求解方法提升在实战环境下的策略强度,致力于得到在团体对战情况下的团队最大最小均衡等博弈论角度下的最优策略,最终实现在掼蛋等扑克博弈环境下战胜人类的职业选手.

    作者贡献声明:葛振兴提出选题、研究内容,设计技术方案,撰写论文;向帅设计技术方案,采集和整理实验数据,修订论文;田品卓设计技术方案,提出指导性建议;高阳提出指导性建议,指导论文写作.

  • 图  1   群主计算相关参数所需的平均时间

    Figure  1.   Average time required for the group owner to calculate the relevant parameters

    图  2   每个普通群成员计算出群组密钥的平均时间开销

    Figure  2.   Average time cost for each ordinary group member to calculate the group key

    图  3   公司员工注册

    Figure  3.   Company employees register

    图  4   部门领导创建群聊

    Figure  4.   Department leader creates group chat

    图  5   群组密钥分发

    Figure  5.   Group key distribution

    图  6   群成员发送群聊消息

    Figure  6.   Group members send group chat messages

    图  7   群成员向服务器查询用于计算群组密钥的相关参数

    Figure  7.   Group members query the server for the relevant parameters used to calculate the group key

    图  8   群成员向服务器查询群聊记录

    Figure  8.   Group members query the server for group chat records

    图  9   Signal协议中实现群聊消息加密的流程

    Figure  9.   Process of implementing group chat message encryption in Signal protocol

    表  1   本文方案的存储开销

    Table  1   Storage Cost of Our Scheme

    身份存储开销/B
    群主 {U_0} \dfrac{ {len} }{8} + (n + 3){ {\rm{lb} }}\dfrac{p}{8} + n + 2
    普通群成员 {U_i}(i=1, 2, … , n) \dfrac{ {len} }{8} + 3{ {\rm{lb} }}\dfrac{p}{8} + 2
    下载: 导出CSV

    表  2   本文方案的通信开销

    Table  2   Communication Cost of Our Scheme

    传输的信息通信开销/B
    群主广播的参数 q
    {a_{n + 2}}, {a_{n + 1}},… ,{a_0}以及 {C_1}, {C_2},… ,{C_n}
    \dfrac{ {len} }{8} + \dfrac{ {n + 3} }{8}{\rm{lb}}(q - 1)+ n{\rm{lb} }\dfrac{p}{8} + n
    下载: 导出CSV

    表  3   6种运算各自所需的平均时间

    Table  3   Average Time Required for Each of the Six Operations

    运算运算平均所需的时间
    {G_1}上的点乘37.164 ms
    双线性对82.467 ms
    哈希函数 {H_2} 5.071 μs
    {{\mathbb{Z}}_q} 上的加法0.302 μs
    {{\mathbb{Z}}_q} 上的乘法0.348 μs
    {{\mathbb{Z}}_q} 上的幂运算1.010 μs
    下载: 导出CSV

    表  4   本文方案与其他方案的比较

    Table  4   Comparison Between Our Scheme and Other Schemes

    4个比较角度文献[17]
    的方案
    文献[18]
    的方案
    本文方案
    群组密钥分发者
    的身份
    无线传感网络的
    群组管理者
    KGC群主
    分发者与接收者之间是否需要预共享参数需要需要不需要
    接收者在群组密钥分发期间是否需要向分发者
    发送消息
    不需要需要不需要
    兼容性与目前在市场中投入使用且广泛部署的协议相差较大,兼容性
    较差
    与目前在市场中投入使用且广泛部署的协议相差较大,兼容性
    较差
    利用国密SM9算法进行构造,可兼容使用了SM9的算法或协议
    下载: 导出CSV

    表  5   本文方案与文献[13]方案的比较

    Table  5   Comparison Between Our Scheme and the Scheme Proposed in Reference [13]

    2个比较角度文献[13]的方案本文方案
    群组密
    钥管理
    密钥类型非对称密钥对称密钥
    密钥使用
    方式
    需要由某个成员向证书
    颁发机构注册群组公钥
    在本地直接使
    用群组密钥
    参数分发
    时成员在
    线要求
    要求所有成员同时在线只要求群主在线
    非群组成员
    对群组密钥
    的获取能力
    非群组成员可以冒充
    群组内成员与其他成
    员协商出群组密钥
    非群组内成员无法计
    算出正确的群组密钥
    兼容性 与目前在市场中投入使
    用且广泛部署的协议
    相差较大,兼容性较差
    利用国密SM9算法进
    行构造,可兼容使用
    了SM9的算法或协议
    下载: 导出CSV

    表  6   本文方案和Signal协议采取的方法的对比

    Table  6   Comparison Between Our Scheme and the Method Adopted by Signal Protocol

    4个比较角度Signal协议采取的
    方法
    本文方案
    每个群成员需要在本地预计算的密钥数量30
    每个群成员需预存储的参数或密钥的数量n + 1个链密钥、
    n 个签名公钥、
    1对签名密钥对
    群主:1个长期私钥和n + 1个椭圆曲线点;
    普通群成员:1个长期私钥和1个椭圆曲线点
    每个群成员在会话开始前需发送的携带参数或密钥的报文数 n 群主:1;
    普通群成员:0
    每个群成员发送n条消息时共需计算的消息密钥数 n 1
    下载: 导出CSV
  • [1]

    Diffie W, Hellman M. New directions in cryptography[J]. IEEE Transactions on Information Theory, 1976, 22(6): 644−654 doi: 10.1109/TIT.1976.1055638

    [2]

    Harn L, Hsu C F, Xia Zhe. Lightweight and flexible key distribution schemes for secure group communications[J]. Wireless Networks, 2021, 27(1): 129−136 doi: 10.1007/s11276-020-02449-2

    [3]

    Hsu C F, Harn L, Zeng Bing. UMKESS: User-oriented multi-group key establishments using secret sharing[J]. Wireless Networks, 2020, 26(1): 421−430 doi: 10.1007/s11276-018-1825-x

    [4] 张泽林,王化群. 基于区块链的工业互联网动态密钥管理[J]. 计算机研究与发展,2023,60(2):386−397

    Zhang Zelin, Wang Huaqun. Dynamic key management of industrial Internet based on blockchain[J]. Journal of Computer Research and Development, 2023, 60(2): 386−397 (in Chinese)

    [5]

    Xiong Hu, Wu Yan, Lu Zhen. A survey of group key agreement protocols with constant rounds[J]. ACM Computing Surveys, 2019, 52(3): 1−32

    [6]

    Chen C M, Deng Xiaoting, Gan Wensheng, et al. A secure blockchain-based group key agreement protocol for IoT[J]. The Journal of Supercomputing, 2021, 77(8): 9046−9068 doi: 10.1007/s11227-020-03561-y

    [7]

    Braeken A. Pairing free certified common asymmetric group key agreement protocol for data sharing among users with different access rights[J]. Wireless Personal Communications, 2021, 121(1): 307−318 doi: 10.1007/s11277-021-08636-4

    [8]

    Gan Yong, Wang Bingli, Zhuang Yuan, et al. An asymmetric group key agreement protocol based on attribute threshold for Internet of things[J]. Transactions on Emerging Telecommunications Technologies, 2021, 32(5): e4179

    [9]

    Ingemarsson I, Tang D T, Wong C K. A conference key distribution system[J]. IEEE Transactions on Theory, 1982, 28(51): 714−719

    [10]

    Naresh V S, Reddi S, Murthy N V E S. A provably secure cluster-based hybrid hierarchical group key agreement for large wireless ad hoc networks[J]. Human-centric Computing and Information Sciences, 2019, 9(1): 1−32 doi: 10.1186/s13673-018-0162-5

    [11]

    Xu Zisang, Liang Wei, Li K C, et al. A time-sensitive token-based anonymous authentication and dynamic group key agreement scheme for industry 5.0[J]. IEEE Transactions on Industrial Informatics, 2021, 18(10): 7118−7127

    [12]

    Lee T F, Ye Xiucai, Lin S H. Anonymous dynamic group authenticated key agreements using physical unclonable functions for internet of medical things[J]. IEEE Internet of Things Journal, 2022, 9(16): 15336−15348 doi: 10.1109/JIOT.2022.3149117

    [13]

    Wu Qianhong, Mu Yi, Susilo W, et al. Asymmetric group key agreement[C] //Advances in Cryptology-EUROCRYPT 2009: 28th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2009: 153−170

    [14]

    Zhang Lei, Wu Qianhong, Qin Bo, et al. Identity-based authenticated asymmetric group key agreement protocol[C] //Proc of the 16th Annual Int Conf on Computing and Combinatorics. Berlin: Springer, 2010: 510−519

    [15] 张启坤,甘勇,王锐芳,等. 簇间非对称群组密钥协商协议[J]. 计算机研究与发展,2018,55(12):2651−2663

    Zhang Qikun, Gan Yong, Wang Ruifang, et al. Inter-cluster asymmetric group key agreement[J]. Journal of Computer Research and Development, 2018, 55(12): 2651−2663 (in Chinese)

    [16]

    Li Juyuan, Qiao Zhiqi, Peng Jialiang. Asymmetric group key agreement protocol based on blockchain and attribute for industrial Internet of things[J]. IEEE Transactions on Industrial Informatics, 2022, 18(11): 8326−8335 doi: 10.1109/TII.2022.3176048

    [17]

    Guo Hua, Zheng Yandong, Li Xiong, et al. Self-healing group key distribution protocol in wireless sensor networks for secure IoT communications[J]. Future Generation Computer Systems, 2018, 89(12): 713−721

    [18]

    Meng Keju, Miao Fuyou, Yu Yue. A secure and efficient on-line/off-line group key distribution protocol[J]. Designs, Codes and Cryptography, 2019, 87(7): 1601−1620 doi: 10.1007/s10623-018-0554-6

    [19]

    Li Xinghua, Wang Yunwei, Vijayakumar P, et al. Blockchain-based mutual-healing group key distribution scheme in unmanned aerial vehicles ad-hoc network[J]. IEEE Transactions on Vehicular Technology, 2019, 68(11): 11309−11322 doi: 10.1109/TVT.2019.2943118

    [20]

    Jiao Runhai, Ouyang Hong, Lin Yukun, et al. A computation-efficient group key distribution protocol based on a new secret sharing scheme[J]. Information, 2019, 10(5): 175

    [21]

    Yıldız H, Cenk M, Onur E. PLGAKD: A PUF-based lightweight group authentication and key distribution protocol[J]. IEEE Internet of Things Journal, 2020, 8(7): 5682−5696

    [22]

    Xu Guangquan, Li Xiaotong, Jiao Litao, et al. BAGKD: A batch authentication and group key distribution protocol for vanets[J]. IEEE Communications Magazine, 2020, 58(7): 35−41 doi: 10.1109/MCOM.001.2000118

    [23]

    Shamir A. Identity-based cryptosystems and signature schemes[C] //Proc of the 4th Int Cryptology Conf. Berlin: Springer, 1985: 47−53

    [24]

    Nam J, Choo K K R, Han S, et al. Efficient and anonymous two-factor user authentication in wireless sensor networks: Achieving user anonymity with lightweight sensor computation[J]. PloS One, 2015, 10(4): e0116709 doi: 10.1371/journal.pone.0116709

    [25]

    Chang Chin-Chen, Le Hai-Duong. A provably secure, efficient, and flexible authentication scheme for ad hoc wireless sensor networks[J]. IEEE Transactions on wireless communications, 2015, 15(1): 357−366

    [26] 张启坤,王锐芳,谭毓安. 基于身份的可认证非对称群组密钥协商协议[J]. 计算机研究与发展,2014,51(8):1727−1738

    Zhang Qikun, Wang Ruifang, Tan Yu’an. Identity-based authenticated asymmetric group key agreement[J]. Journal of Computer Research and Development, 2014, 51(8): 1727−1738 (in Chinese)

    [27] GB/T 38635.2−2020《信息安全技术 SM9标识密码算法》第2部分: 算法[S]. 北京: 中国标准出版社. 2020

    GB/T 38635.1-2020. Information Security Technology SM9 Identity-based Cryptography Part 2: Algorithm[S]. Beijing: Standards Press of China, 2020(in Chinese)

    [28] 文嘉明, 王后珍, 刘金会, 等. Aitps: 基于非对称模格问题的两方协同签名方案[J]. 计算机研究与发展2023, 60(9): 2137−2151

    Wen Jiaming, Wang Houzhen, Liu Jinhui, et al. Aitps: A two-party signature from asymmetry module lattice problem[J]. Journal of Computer Research and Development 2023, 60(9): 2137−2151 (in Chinese)

    [29] GB/T 38635.1−2020 《信息安全技术 SM9标识密码算法》第1部分: 总则[S].北京: 中国标准出版社, 2020

    GB/T 38635.1-2020. Information Security Technology SM9 Identity-based Cryptography Part 1: General[S]. Beijing: Standards Press of China, 2020(in Chinese)

    [30]

    Alwen J, Coretti S, Dodis Y. The double ratchet: Security notions, proofs, and modularization for the signal protocol[C] //Advances in Cryptology–EUROCRYPT 2019: 38th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2019: 129−158

    [31]

    WhatsApp. Whatsapp encryption overview, technical white paper [R/OL]. (2023-01-24) [2023-04-15].https://scontent-sjc3−1.xx.fbcdn.net/v/t39.8562−6/328495424_498532869106467_756303412205949548_n.pdf?_nc_cat=104&ccb=1−7&_nc_sid=ad8a9d&_nc_ohc=BPmGXFrfbGsAX-A2MQ7&_nc_ht=scontent-sjc3−1.xx&oh=00_AfCYrzsCnuGB8OeWmfTUifmAcQPd1CLh2OlykXi0M_RkMg&oe=643F38BC

    [32]

    Facebook Messenger. Messenger secret conversations, technical whitepaper [R/OL]. (2017-05-18) [2023-04-15].https://about.fb.com/wp-content/uploads/2016/07/messenger-secret-conversations-technical-whitepaper.pdf

  • 期刊类型引用(1)

    1. 李继国,方淳. 基于SM9的指定验证者聚合签名方案. 网络与信息安全学报. 2024(04): 63-71 . 百度学术

    其他类型引用(0)

图(9)  /  表(6)
计量
  • 文章访问数:  292
  • HTML全文浏览量:  46
  • PDF下载量:  143
  • 被引次数: 1
出版历程
  • 收稿日期:  2023-06-04
  • 修回日期:  2023-08-17
  • 网络出版日期:  2023-10-07
  • 刊出日期:  2023-10-15

目录

/

返回文章
返回