后量子前向安全的可组合认证密钥交换方案

陈 明

(宜春学院数学与计算机科学学院 江西宜春 336000)

认证密钥交换(authenticated key exchange, AKE)协议用于在开放网络环境下，网络通信实体之间确认彼此身份、协商共享会话密钥，为通信提供机密性、认证性和完整性保障.自Diffie和Hellman提出密钥交换(简称为DHKE[1])概念以来，AKE协议得到广泛的研究和应用，是保障网络通信安全的基础协议之一.

AKE协议的一个重要安全属性是会话密钥的前向安全性(forward secrecy, FS)，是指参与会话的用户长期私钥泄露不影响之前已经建立的会话密钥的安全性.随着量子计算技术的发展，FS被赋予了新的含义，即向后量子时代过渡的时期，AKE协议被要求能抵抗未来量子计算机的攻击.后量子的网络通信安全受到越来越多政府、研究机构和学者的关注.2016年美国国家标准与技术研究所(National Institute of Standards and Technology, NIST)开启了下一代密钥交换和数字签名的后量子标准征集工作[2].我国、日本及欧洲也相继开展相关研究项目.

近20年来，基于格(lattice)上困难问题构建密码系统的研究[3-8]取得进展，为后量子密码研究和应用奠定了基础.在Asiacrypt2009会议上，Katz等人[9]提出了首个基于格问题的口令认证密钥交换协议.随后，文献[10-24]分别提出多种基于格上困难问题的密钥交换方案.总体来看，提出的方案分为2种类型:一类采用密钥封装机制(key encapsulation mech-anism, KEM)传输会话密钥材料;另一类则基于格上LWE(ring-learning with errors, Ring-LWE)问题[4,7-8]构造了类似DHKE的密钥交换机制(记为DHKE-like[10,18,20]).需要指出的是，由于缺乏后量子的公钥基础设施(public key infrastructure, PKI)支持，基于格的密钥交换协议在当下还不能作为后量子密钥交换的完整解决方案.一种过渡时期的解决办法是将后量子的(无认证)密钥交换与现有的公钥密码系统整合，利用现有公钥密码技术实现实体的相互认证，典型的方案有Bos等人[18]将基于Ring-LWE问题的DHKE-like机制与TLS[25]握手协议进行整合，实现会话密钥的后量子前向安全性.但是，TLS协议需要多轮信息交换，不适合某些特殊的应用场景，如多方认证、传感器网络、自组织网络和专用网络等.

为了适应更加广泛的网络应用环境，考虑过渡时期对AKE方案的可扩展性需求，本文提出“签密[26](signcryption, SC)+DHKE-like”的可组合AKE架构.

签密的概念由Zheng[26]在1997年的美密会议上提出，能在一个密码学的逻辑步骤中同时实现消息的机密性和认证性，在网络通信领域有着广阔的应用前景，得到了广泛研究.

本文的主要工作是：本文提出以DHKE-like为基础的一轮(2-pass)AKE方案，主要工作包括3个方面:

1) 提出“SC+DHKE-like”架构的通用可组合AKE方案(记为GC-AKE).具体来说，采用具有IND-CCA安全(indistinguishability against chosen ciphertext attacks)和SEUF-CMA[27]安全(strong existentially unforgeable under adaptive chosen mess-ages attacks)的SC机制对DHKE-like中的临时公钥参数进行加密和签名，实现实体认证和会话密钥协商.但是，一个关键问题是，理想格上DHKE-like机制的临时公钥大小为几十Kb，其签密的计算以及通信开销较大.为了降低开销，本文设计了临时公钥特征提取和恢复函数进行特征提取、公钥隐藏和恢复，将认证过程中签密消息的长度从几十Kb降低为nb(本文取n=1 024).

2) 基于现有AKE的安全模型，定义了wAKE-PFS安全模型，重点模拟AKE协议的完美前向安全性(perfect FS, PFS).在wAKE-PFS模型下，本文GC-AKE协议的安全性被规约到敌手求解DDH-like问题(见本文3.1节定义8)，以及攻破SC机制的IND-CCA和SEUF-CMA安全性.

3) 考虑到(后量子)过渡时期的实际应用需求，提出一种基于身份的签密(identity-based signcryp-tion, IBSC)机制，以Boneh等人[28]提出的短签名方案BBS为基础扩展而来，在选择身份安全模型下实现了IND-CCA和SEUF-CMA安全性.将IBSC机制与理想格上的DHKE-like组合，可实现用户的相互认证，以及抵抗量子计算机的完美前向安全性.

1 相关工作

后量子密钥交换的前期研究工作主要集中于构造无认证的密钥交换方案，或者KEM机制，作为一个独立的密码套件与其他加密原语(如数字签名)进行组合(类似TLS[25]和SIGMA方案[29])，实现实体的认证和密钥交换.比较典型的方案包括：Ding等人[10]提出了格上DHKE-like密钥交换方案；Peikert[16]基于Ring-LWE问题提出了带密钥调节机制的KEM方案；Bos等人[18]采用Peikert的密钥调节机制构造了BCNS-DHKE-like协议及其在一般格上的变形(Frodo[19])；Alkim等人[20]将BCNS-DHKE-like协议进行简化，提出了NewHope方案，将Ring-LWE实例中误差采样的离散高斯分布替换为中心二项分布，以提高采样效率；随后，Alkim等人将NewHope方案变形，提出更加简化的NewHope-Simple KEM[21]方案，并且采用了密文压缩技术以降低通信开销.

在基于格的AKE方面，Fujioka等人[13-14]、Zhang等人[17]、Ding等人[11-12]分别提出一轮隐式认证和密钥交换方案，融合对方实体的长期和临时公钥与自身的长期和临时私钥，以某种方式融入到会话密钥的计算中，实体的相互认证有赖于会话双方计算一致的会话密钥.具体来说，Fujioka等人[13]提出一种通用的AKE构造方法，采用一种称之为“twisted PRF”的技术(类似于NAXOS trick[30])，2个伪随机函数(pseudo-random function, PRF)分别输入实体的长期私钥和临时私钥，相互交织，输出高安全性的密钥材料，实现抵抗长期私钥泄露的伪装攻击和临时私钥泄露攻击.然而，Fujioka方案实例[14]计算过程复杂，通信开销较大，总体的性能较差.Zhang等人[17]基于Ring-LWE问题构造了类似HMQV[31]协议的隐式认证与密钥交换方案.Zhang等人[17]的方案采用了Ding等人[10]提出的DHKE-like密钥交换机制，在会话双方之间协商得到2个近似相等的多项式，通过密钥调节机制，从2个多项式中提取一致的会话密钥材料.但是，在基于Ring-LWE问题的DHKE-like密钥交换中重用公钥被认为存在私钥泄露风险[32-33].为了弥补这一缺陷，Ding等人[12]提出公钥可重用AKE方案，利用一个随机谕言机(一个密码Hash函数)对临时公钥进行结构调整.Yang等人[23]提出一种强安全性的通用AKE方案，采用OT-IND-CCA[23]安全(one-time IND-CCA)的KEM设计了一种OTKEM机制传递密钥材料，使用强不可伪造签名算法实现实体认证，并提出一种基于Ring-LWE问题的OTKEM实例.然而，Yang等人[23]提出的OTKEM实例计算和通信代价太高，难以实际应用.李子臣等人[24]将NewHope-Simple KEM[21]方案变形为公钥加密机制，以此为基础构造了基于Ring-LWE问题的AKE方案.但是，李子臣等人提出的AKE方案不能抵抗密钥重用攻击，具体分析见本文5.2.1节.

此外，Wang等人[15]提出格上的基于身份AKE协议(ID-AKE)，采用ABB-IBE[34]加密传输会话密钥材料.该方案构造简单，安全性低，不具有前向安全性.赵秀凤等人[22]提出一种基于BCNS-DHKE-like机制的ID-AKE方案(记为Zhao-AKE).但是，Zhao-AKE方案存在较为严重的安全缺陷，具体在本文5.2.2节分析.由于基于格的IBC系统普遍存在密钥尺寸较大的问题，使得格上基于身份的KEM密文尺寸大，限制了其在AKE领域的应用.就目前的文献来看，尚没有高效、安全的基于格的ID-AKE协议发表.

本文提出一种可组合的AKE方案，重点关注在过渡时期的后量子前向安全性.本文方案采用“SC+DHKE-like”组合，可实现跨密码体制的AKE协议，适应多种应用需求.例如针对过渡时期的网络通信安全需求，本文4.2节提出的GC-AKE实例采用基于椭圆曲线密码(elliptic curve cryptography, ECC)的IBSC与基于Ring-LWE问题的DHKE-like机制组合，实现了跨密码体制的ID-AKE协议.尽管本文方案以BCNS-DHKE-like协议为基础，但是可采用具有DDH-like性质的其他DHKE-like协议(如DHKE[1]和NewHope[20]协议)直接替换.此外，通过将SC机制扩展为多接收者的签密方案，还可以将本文的GC-AKE方案扩展到多方认证的应用环境.对比相关的通用AKE方案，例如文献[14,23]，本文方案在实现较强安全性的同时，具有结构简单、可组合的优势，同时在计算、存储和通信开销方面具有一定优势.

2 背景知识

2.1 数学概念与定义

本节简要描述本文所使用的数学概念和符号，以及困难数学问题.

2.1.1 双线性映射理论

本节简要阐述与本文相关的双线性对理论及假设，详细内容请参考文献[28,35].

双线性映射:给定素数阶为p的循环群G1，G2和GT，g1和g2分别是G1和G2的生成元，且存在同构函数ψ:G2→G1，使得ψ(g2)=g1成立，定义双线性映射e:G1×G2→GT满足3个性质.

2) 非退化性.e(g1,g2)≠1.

3) 可计算性.给定任意的u∈G1,v∈G2，能有效计算e(u,v).

为了叙述简洁，本文省略了“modp”运算.

2.1.2 环的定义及困难问题

R=Z[X](Xn+1)是一个分圆多项式环，其中，n为2的整数幂，环的元素是系数为整数的多项式.

令Rq=RqR，Rq的成员用它的所有系数组成的向量表示，每个系数是Zq中的成员，q为整数模量.

令‖·‖和‖·‖分别表示向量(或多项式)的欧拉范数和无穷范数，令a←UR表示从R中抽取均匀随机的元素a，令χ表示R上的概率分布，e←χ表示从χ中随机抽取元素e.

BCNS-DHKE-like方案以Rq上Ring-LWE问题为基础，下面描述其判定性问题和假设，详细内容请查阅文献[8,18].

定义1.判定Ring-LWE问题.给定参数(n，q，R，Rq，χ)，对随机选择的s←χ，定义谕言机OD,s按2个步骤执行：1)随机选取a←URq和e←χ；2)返回(a,as+e)∈Rq×Rq.

判定Ring-LWE问题是区分OD,s的输出与Rq×Rq上的随机均匀样本.特定地，定义区分算法A，则A的优势为

定义1中，s从错误分布χ中选取，而不是Rq的均匀分布，Lyubashevsky等人[8]证明了s的选取不影响判定Ring-LWE问题的困难性(文献[8]的引理2.24).

2.2 AKE协议安全模型

本文安全模型以Cremers等人[36]的eCK-PFS模型为基础，融合了王霏和陈明[37]对eCK-PFS模型的扩展.下面对相关概念进行简要阐述，详细内容见文献[36-37]和本文3.3.2节.

会话(session)是协议实例的一次运行，由一个七元组Ts=(sactor,speer,srole,ssent,srecv,sstat,scomp)唯一标识.Ts记录会话s的运行参数，sactor和speer记录实体身份；srole是会话拥有者的角色；ssent和srecv记录发送和接收的消息；sstat记录临时参数；scomp记录会话状态，scomp=T表示会话已完成，scomp=表示会话未完成.

敌手(adversary)被模拟为一个概率多项式时间图灵机，允许执行如下询问.

1)Send(s,M)询问.模拟敌手发送消息M到会话s.

2)Corrupt(ID)询问.询问用户ID的长期私钥.

3)Ephemeral-key(s)询问.询问会话s的临时秘密.

4)Session-key(s)询问.询问会话s的会话密钥.

5)Test(s*)询问.模拟器随机选择ζ∈{0,1}，如果ζ=0,输出s*的会话密钥，否则输出随机的SK←{0,1}λ.其中，λ为安全参数.

下面定义原始会话、匹配会话和会话新鲜性.

定义4.eCK-PFSfresh[36].如果已完成的会话s满足6个条件，那么s满足eCK-PFSfresh.

1)sactor，speer是诚实的参与者；

2) 未执行过Session-key(s)询问；

3) 如果存在s*↔s，则未执行Session-key(s*)询问；

4) 不允许同时执行Ephemeral-key(s)询问和Corrupt(sactor)询问；

5) 对于所有满足s′→s的s′，不允许同时执行Corrupt(speer)询问和Ephemeral-key(s′)询问；

6) 如果不存在s′满足s′→s，那么在s完成之前，不允许执行Corrupt(speer)询问.

此外，本文定义一类较弱的安全模型，命名为wAKE-PFS，不模拟协议的抗临时秘密泄露攻击(maximal exposure attacks, MEX[13])，即不允许敌手询问会话的临时秘密(Ephemeral-key(s)询问).

定义6.wAKE-PFSfresh.如果已完成的会话s满足5个条件，那么s满足wAKE-PFSfresh.

1)sactor，speer是诚实的参与者；

2) 未执行过Session-key(s)询问；

3) 如果存在s*↔s，则未执行Session-key(s*)询问；

4) 如果不存在s*↔s，但是存在s′→s，则在s完成之前，不允许执行Corrupt(speer)询问.

5) 如果不存在s′满足s′→s，则不允许执行Corrupt(speer)询问.

除了MEX安全性，wAKE-PFS模型能模拟AKE协议的其它安全属性，包括KCI和PFS.

2.3 签密及其安全模型

签密由系统建立、密钥生成、签密和解签密4个算法组成.本文以IBSC为例，定义为：

系统建立.输入安全参数λ，PKG(private-key generator)产生系统的公开参数和主密钥.

密钥生成.输入用户身份ID，密钥生成中心产生用户密钥SK并通过安全信道返回给用户.IBC系统中，用户私钥实质是PKG对用户ID的签名.

签密.输入发送者私钥SKs、接收者身份IDr和待签密消息m，输出密文c←SCIBSC(m,SKs,IDr).

解签密.输入发送者公钥IDs、接收者私钥SKr和密文c，输出明文m←UnSCIBSC(c,SKr,IDs)或者“⊥”(表示密文无效).

签密应同时满足IND-CCA和EUF-CMA安全性，分别归纳为IND-CCA和EUF-CMA的2类安全游戏.本文AKE方案要求IBSC具有强的不可伪造性，以选择身份安全模型为例，定义为：

初始化.C创建系统公开参数和N个用户身份{ID1,ID2,…,IDN}，随机选择l∈{1,2,…,N}.

询问1.敌手A自适应地提交多项式时间有界的询问，挑战者C模拟IBSC的相应算法对A的询问进行应答.

1) 密钥询问.A提交用户身份IDi，如果IDi=IDl，则终止模拟，否则C输出IDi的长期私钥.

2) 签密询问.A输入(m,IDs,IDr)，C输出签密密文c.

3) 解签密询问.A输入(c,IDs,IDr)，如果验证签密密文有效，则输出明文m，否则返回⊥.

3 基于DHKE-like的AKE方案

本节提出一种以DHKE-like为基础的GC-AKE方案，下面首先简要阐述Bos等人[18]的DHKE-like方案，然后提出本文GC-AKE方案模型.

3.1 DHKE-like密钥交换方案

BCNS-DHKE-like[18]方案在密钥交换双方交换2个近似相等的多项式环成员，采用Peikert[16]定义的密钥调节机制从2个多项式中提取相同的密钥材料.

首先简要介绍Peikert[16]定义的密钥调节机制.

定义MR(modular rounding)函数⎣·⎤q,2和CR(cross-rounding)函数〈·〉q,2为：

⎣·⎤q,2：Zq→Z2,x⎣x⎤q,2=2xq+1mod 2，
〈·〉q,2：Zq→Z2,x〈x〉q,2=4xqmod 2.

MR函数和CR函数的输入可扩展为多项式，对多项式的每一个系数分别执行⎣·⎤q,2和〈·〉q,2运算.例如令f=fn-1Xn-1+…+f1X+f0∈Rq，则〈f〉q,2=(〈fn-1〉q,2,…,〈f1〉q,2,〈f0〉q,2)∈R2.

当q为奇数时，为了避免MRCR函数输出偏倚，需要将模数扩大为2q，定义dbl函数为

dbl: Zq→Z2q,x

定义集合.

令E=[-q4,q4)，对与v∈Zq逼近的w∈Zq，令v′=dbl(v)∈Z调节函数定义为

基于Peikert[16]定义的密钥调节机制，Bos等人[18]实现的BCNS-DHKE-like方案如图1所示：

Fig. 1 Unauthenticated Diffie-Hellman-like key exchange图1 无认证的Diffie-Hellman-like密钥交换方案

定义8.DDH-like problem[18].给定参数(n，q，R，Rq，χ)和1个DHKE-like实例(a,b,b′,c,κ)，区分κ是DHKE-like的有效解还是{0,1}n上的随机样本.特定地，对于多项式时间敌手A，定义A赢得DDH-like挑战的优势为

定理1.给定参数(n，q，R，Rq，χ)，如果判定Ring-LWE问题是难解的，那么DDH-like问题也是困难的.特定地，对于多项式时间敌手A，赢得DDH-like挑战的优势为

其中，B1和B2为判定Ring-LWE问题的敌手.

定义8和定理1来源于文献[18]的定义3和定理1，文献[18]对定理1进行了安全性规约，本文不再赘述.

3.2 基于DHKE-like的认证密钥交换方案

本文提出的GC-AKE方案包含系统建立、用户密钥生成和密钥交换3个阶段.

1) 系统建立.输入安全参数λ，认证权威运行Setup算法，产生系统参数para={n,q,Rq,χ,a,H}.其中，a←URq，H：{0,1}*→{0,1}λ为密钥导出函数.

2) 用户密钥生成.给定用户的标识为ID，令用户的公私钥为(pkID,skID).这里不具体指定用户密钥生成的方式，可基于PKI系统或者IBC系统等.

3) 密钥交换.如果Alice与Bob期望建立安全会话，按如下步骤进行认证与密钥交换，如图2所示.令Alice,Bob的身份和密钥分别为(IDA,pkA,skA),(IDB,pkB,skB).

Fig. 2 Generic authenticated key exchange protocol图2 通用的AKE协议

③ Alice计算θB←UnSC(cB,skA,pkB)，κA←rec(2bBtA,θB)，SKAB=H(IDA,IDB,μA,θB,κA).

在理想信道下，如果签密方案满足正确性，且BCNS-DHKE-like密钥交换有效，那么诚实的Alice和Bob能以极大的概率(不小于1-2-217)输出一致的会话密钥，SKAB=SKBA.也就是说，如果密文c是签密算法的有效输出c←SC(μ,ski,pkj)，则接收者必然输出有效的μ←UnSC(c,skj,pki)，进而认证双方能建立有效的DHKE-like实例(a,bA,bB,μA,θB,κA,κB)，使得κA=κB.可见，本文GC-AKE方案满足正确性.

本文GC-AKE方案以无认证DHKE-like方案为基础，组合签密方案，实现实体的认证和密钥协商.DHKE-like方案每次选择新鲜的临时公(私)钥，与用户长期私钥无关，实现了会话密钥的新鲜性和前向安全性；签密方案对发送者和接收者的身份进行了绑定，只有拥有相应私钥的用户才能完成密钥交换，协商一致的会话密钥，融合了显式认证(签名)和隐式认证(加密).本文方案具有可组合的特点，根据不同安全需求，可采用任何满足安全性要求的签密方案和DHKE-like方案进行组合，实现认证密钥交换.例如本文4.2节提出的GC-AKE实例采用基于ECC的IBSC与基于Ring-LWE问题的DHKE-like机制组合，既能满足现实的应用需求，还能实现抵抗量子计算攻击的前向安全性.

3.3 GC-AKE方案的安全性分析

本节首先分析F(*)函数的安全性，然后采用wAKE-PFS模型对GC-AKE方案进行安全性规约.

3.3.1F(*)函数的安全性分析

从3方面分析F(bA)函数的安全性.

2) 分析敌手完整恢复bA的概率.同上，由于bA的每个系数的符号位等于“0”的概率近似为12，则敌手完整恢复bA的概率为max(2-1 024,εSC).其中，εSC为敌手攻破SC方案IND-CCA安全的概率.

3.3.2 GC-AKE方案安全性规约

本文采用wAKE-PFS模型对GC-AKE方案进行安全性规约.与eCK-PFS模型不同，wAKE-PFS模型不允许敌手询问会话的内部状态(临时秘密参数).

根据wAKE-PFSfresh定义，本文主要考虑6种攻击场景S1～S6，如表1所示.令s表示Test会话，s分为发起者会话(I)和响应者会话(R)这2类，每一类会话分别存在3种情形：1)存在s*↔s(则至少存在一个原始会话s*→s)；2)不存在s*↔s，但存在s′→s；3)s*↔s和s′→s都不存在.表1中，MS表示匹配会话，OS表示原始会话；Yes表示存在s*↔s或s′→s，No则表示不存在；allowed表示允许敌手执行Corrupt询问，allowed*表示在s完成之前不允许敌手执行Corrupt询问，disallowed表示不允许敌手执行Corrupt询问.

表1中，所有场景均允许敌手询问会话拥有者的私钥(Corrupt(sactor)询问)，表明所有场景均可模拟密钥泄露伪装攻击(KCI)；S1和S4场景允许敌手在任意时刻询问挑战会话双方的私钥，由于s存在匹配会话，限制了敌手在挑战会话中主动注入临时秘密的能力，而场景S2和S5允许敌手在s完成之后询问对端实体的私钥(Corrupt(speer))，能模拟协议的完美前向安全性(PFS).

“BR+wPFS”模型不区分匹配会话与原始会话，不能模拟S2，S5；S2，S5分别包含在S3，S6中；这是wPFS与PFS安全性的主要区别.

定理2.给定参数(n，q，R，Rq，χ)，如果DDH-like假设成立，并且SC方案满足IND-CCA和SEUF-CMA安全性，那么本文提出的GC-AKE协议满足wAKE-PFS安全.

证明. 首先考虑定义7的第1个条件，2个诚实的用户完全如实地按照协议执行，如果他们完成了一次匹配的会话，根据匹配会话条件，如果SC方案有效，接收方能正确恢复bA和θB，进而，密钥交换双方能输出相同的会话密钥SKAB=SKBA，且Pr(SKAB=SKBA)≥1-2-217.

其次，对于定义7的第2个条件，根据安全游戏，本文将GC-AKE协议的安全性规约为求解DDH-like问题和攻破SC方案的IND-CCA和SEUF-CMA安全性.

表1所概括的6种场景分别对应一个安全游戏.考虑到模拟过程冗长且差别不大，本文选取场景S1，S3和S5进行详细叙述.场景S1模拟AKE协议的弱前向安全性(wPFS)，S5模拟AKE的完美前向安全性(PFS)，S3重点模拟AKE协议的KCI安全性.

游戏过程模拟为敌手A与挑战者C之间的一系列游戏.C激活一个模拟器产生系统公开参数，创建N个独立的用户P={ID1,ID2,…,IDN}，发送给敌手A，接受敌手的询问并做出相应的应答.令π表示本文GC-AKE协议，Sj表示游戏GameSi.j(i∈{1,2,3,4,5,6},j∈{0,1,2,3,…})中敌手猜测成功的事件，那么GameSi.j中敌手赢得游戏的优势定义为：εj=|2Pr(Sj)-1|.令N，qI，qR分别表示游戏中创建的用户数、发起者会话数和响应者会话数的上界.注意，模拟过程中，C将所有签名验证不成功的询问作为无效询问.

下面首先叙述S1的模拟过程，由一系列游戏GameS1.j组成.

GameS1.0：GameS1.0模拟真实的攻击场景，A自适应地提交询问，C按照协议π和安全模型的定义对A的询问做出应答，那么A赢得游戏的优势为：ε0=|2Pr(S0)-1|.

GameS1.1：在GameS1.0的基础上，GameS1.1考虑一些小概率的碰撞事件，比如在不同的会话中发生临时参数碰撞或者Hash碰撞等，当出现此类事件则模拟失败.令E1表示上述小概率事件，根据差分引理(文献[36]引理1)：

|Pr(S0)-Pr(S1)|≤Pr(E1)，
ε0=|2Pr(S0)-1|=2|Pr(S0)-Pr(S1)+
Pr(S1)-12|≤2(|Pr(S0)-Pr(S1)|+
|Pr(S1)-12|)≤ε1+2Pr(E1).

那么，GameS1.1中A成功的优势为：ε1≥ε0-negl(λ).其中，negl(λ)为一个可忽略的函数，表示E1发生的概率.

GameS1.3：在GameS1.2的基础上，GameS1.3模拟对DDH-like问题的挑战.给定一个DDH-like问题实例(a,b*,b″,θ″,κ*)，模拟过程描述为：

1)C按照真实协议的系统建立算法生成系统公开参数para={n,q,Rq,χ,a,H}发送给A.

2)C按照协议的密钥生成算法生成用户密钥(pkID,skID)，将(ID,pkID,skID)插入初始为空的列表LID.

3)A提交Send(s，IDj)询问激活发起者会话s.令sactor=IDi，如果s=s*，C计算(b′*,μ*)←F(b*)，c*←SC(μ*,skIDi,pkIDj)，将(b′*,c*)返回给A(事件E3)；否则，C按照协议步骤计算响应消息(bi,ci)返回给A.最后更新Ts.

5)A提交Send(s，M)询问.如果s是一个已激活的发起者会话，且scomp≠T，且如果s=s*，则置scomp=T；否则C按照协议计算得到sstat=(bi,bj,μi,ci,θj,κi,SKij)，更新Ts并置scomp=T；否则忽略.

6)A提交Corrupt(ID)询问.如果ID∈P，则查询LID返回用户ID的私钥，否则返回⊥.

7)A提交Reveal(s)询问，如果s=s*∨s↔s*，算法终止(破坏wAKE-PFSfresh)；否则，如果s不存在或scomp≠T则返回⊥；否则C查询sstat，返回相应的SKij.

9) 最后，A输出其猜测ζ′∈(0,1)，则C直接输出ζ′作为对DDH-like挑战的应答(事件E5).

GameS1.3与GameS1.2在事件E3～E5不同.事件E3描述用给定的DDH-like挑战实例(a,b*,b″,θ″)替换挑战会话s*及其匹配会话s″的输出.假定(a,b*,b″,θ″)独立于A的视角，则敌手不能区分GameS1.3和GameS1.2.事件E4和事件E5都是C的内部事件，对A透明.假设在DDH-like挑战中，ζ=0表示κ*是DDH-like实例(a,b*,b″,θ″)的有效的解，则ζ=1表示κ*是{0,1}n上的随机值.Test(s)询问中，SK*根据κ*计算得到，如果ζ=0，则SK*是挑战会话s*的正确会话密钥；如果ζ=1，则SK*与随机的SK*←U{0,1}λ不可区分，则GameS1.3和GameS1.2的Test(s)询问输出同分布.因此，敌手不能根据E4和E5区分GameS1.3和GameS1.2.则GameS1.3中敌手成功的优势：ε3≥ε2-negl(λ).

根据系列游戏结果，A赢得GameS1的优势为：ε≤ε1+negl(λ)≤qIqRε2+negl(λ)≤2qIqRεddhl+negl(λ).

场景S1的模拟到此结束，下面叙述场景S3的模拟过程.

GameS3.0：与GameS1.0相同，GameS3.0模拟真实的攻击场景，A赢得游戏的优势为：ε0=|2Pr(S0)-1|.

GameS3.1：与GameS1.1相同，在GameS3.0的基础上，GameS3.1考虑一些小概率的碰撞事件，则A成功的优势为：ε1≥ε0-negl(λ).

GameS3.3：在GameS3.2的基础上，GameS3.3考虑对SC算法的SEUF-CMA攻击.C创建模拟环境，构造谕言机OSC模拟SC算法的签密和解签密运算，运行子算法B，游戏模拟如下.

B维护初始为空的列表LSC=(IDi,IDj,ν,c).

步骤1)、2)与GameS1.3相同.

5)A提交Send(s，M)询问.如果s是一个已激活的发起者会话，且scomp≠T，令sactor=IDi，M=(bj,cj).如果cj∉LSC是与IDj相关的可验证有效的签密密文，IDj=ID*是密文cj的签名者身份，那么B输出cj作为对SEUF-CMA挑战的应答，然后终止模拟(事件E3)；否则，B询问谕言机OSC，解密cj得θj，按照协议计算得到sstat=(bi,bj,μi,ci,θj,κi,SKij)，更新Ts并置scomp=T；否则忽略.

6)A提交Corrupt(ID)询问.如果ID=ID*，则算法终止(破坏wAKE-PFSfresh)；否则，如果ID∈P，B向C提交密钥询问返回用户ID私钥，否则返回⊥.

7)A提交Reveal(s)询问，如果s=s*∨s↔s*，算法终止(破坏wAKE-PFSfresh)；否则，如果s不存在或scomp≠T则返回⊥；否则B查询sstat，返回对应的会话密钥SKij.

9) 最后，A输出其猜测ζ′∈(0,1).

如果事件E3发生，算法终止，A输出随机的ζ′∈(0,1)，则Pr(S3|E3)=12.如果事件E3不发生，则因此有：可得A成功的优势为：

GameS3.4：在GameS3.3的基础上，GameS3.4考虑对SC算法的IND-CCA攻击.C创建模拟环境，运行子算法F，游戏模拟如下.

F维护初始为空的列表LSC=(IDi,IDj,ν,c).

步骤1)、2)与GameS1.3相同.

6)A提交Corrupt(ID)询问.如果ID=ID*，则算法终止；否则，如果ID∈P，F向C提交密钥询问，将得到的用户私钥返回给A，否则返回⊥.

7)A提交Reveal(s)询问，如果s=s*∨s↔s*，算法终止；否则，如果s不存在或scomp≠T则返回⊥；否则查询sstat，如果存在SKij，则返回SKij；否则返回随机的SKij←U{0,1}λ(事件E7).

9) 最后，A输出其猜测ζ′∈(0,1)，则C输出ζ′作为对IND-CCA挑战的应答.

根据系列游戏结果，A赢得游戏GameS3的优势为：ε≤2NqIεF(1-εB)+negl(λ).

场景S3的模拟到此结束，下面叙述场景S5的模拟过程.

GameS5.0：与GameS1.0相同，GameS5.0模拟真实的攻击场景，A赢得游戏的优势为：ε0=|2Pr(S0)-1|.

GameS5.1：与GameS1.1类似地，在GameS5.0的基础上，GameS5.1考虑小概率碰撞事件，A成功的优势为：ε1≥ε0-negl(λ).

GameS5.3：与GameS3.3类似，在GameS5.2的基础上，GameS5.3考虑对SC算法的SEUF-CMA攻击.C创建模拟环境，运行子算法B，游戏模拟如下.

B维护初始为空的列表LSC=(IDi,IDj,ν,c).

步骤1)、2)、3)与GameS3.3相同.

步骤4)和5)与GameS3.3基本相同.不同之处在于事件E3的触发条件：如果cj∉LSC是与IDj相关的可验证有效的签密密文，IDj=ID*是密文cj的签名者身份，且敌手尚未执行Corrupt(ID*)询问，那么B输出cj作为对SEUF-CMA挑战的应答.

步骤7)、8)、9)与GameS3.3相同.

根据系列游戏结果，A赢得游戏GameS5的优势为：ε≤2NqRεddhl(1-εB)+negl(λ).

证毕.

4 一种GC-AKE架构的ID-AKE方案

本节提出一种基于GC-AKE架构的ID-AKE方案，采用基于身份的签密(IBSC)方案.根据GC-AKE架构的要求，IBSC方案应同时满足IND-CCA和SEUF-CMA安全性.

4.1 强安全的基于身份签密

本文的IBSC方案来源于Boneh和Boyen[28]提出的BBS签名，王霏等人[37]将BBS签名扩展为基于身份的签名，本文进一步将其扩展为IBSC方案.下面简要描述BBS方案及其扩展.

4.1.1 BBS签名

BBS签名基于双线性映射理论，相关背景知识和符号定义见本文2.1节.

定理3[28].如果群G1,G2,GT上的(q,t′,ε′)-SDH假设成立，则BBS签名实现了(t,qs,ε)-SEUF-CMA安全.其中，qs

文献[28]对其进行了证明，这里不再赘述.

4.1.2 IBSC方案

IBSC方案描述如下.

签密(SCIBSC).输入待签密消息m∈{0,1}n，发送者身份IDs及密钥SKs=(xs,ys,zs)，接收者身份及公钥参数(IDr,R3r)，步骤计算为：

解签密(UnSCIBSC)：输入密文c=(W,τ,ω,σ,t)，发送者身份及公钥(IDs,R1s,R2s)，接收者身份IDr及密钥SKr=(xr,yr,zr)，步骤计算为：

需要说明的是，本文IBSC方案沿用文献[28]的符号定义，采用标准离散群的数学描述，具有更好的通用性.在具体实现中，为了降低开销，BBS签名可采用定义在y2=x3+2x±1上的椭圆曲线和超奇异椭圆曲线构建ECC系统.在本文第5节的分析中，也采用了基于ECC的方案.

4.1.3 IBSC方案安全性分析

初始化.输入安全参数λ，挑战者C生成系统公开参数param={G1,G2,GT,g1,g2,e,α,P0,H1,H2,H3,H4,H5}.其中，H1,H2,H3,H4,H5模拟为随机谕言机.C维护初始为空的L1=(ID,R,h1)，L2=(η,m,h2)，L3=(U,h3)，L4=(η,h4)，L5=(W,τ,ω,m,h5)和LID=(ID,R1ID,R2ID,R3ID,r1ID,r2ID,r3ID,xID,yID,wID)分别记录H1,H2,H3,H4,H5询问和用户密钥.

询问1.A自适应地执行多项式时间有界的询问，C模拟IBSC方案的相应算法做出应答.注意：询问中随机选择的参数出现碰撞则重新选择.

4)H3询问.输入Ui，C查询L3，如果存在(Ui,h3i)，则输出h3i；否则，随机选择并输出h3i∈{0,1}n，将(Ui,h3i)插入L3.

5)H4询问.输入ηi，C查询L4，如果存在(ηi,h4i)，则输出h4i；否则随机选择输出h4i∈{0,1}n，将(ηi,h4i)插入L4.

7) 密钥询问.输入IDi，如果IDi=ID*，则C终止模拟；否则如果LID中存在(IDi,*,*,*,*,*,*,xi,yi,zi)则返回(xi,yi,zi)给A，否则返回⊥.

询问2.A可以继续提交询问，询问过程与第1阶段相同，但是不能提交c*=(W*,τ*,ω*,*,*)的解签密询问.

证毕.

证明. 我们将IBSC方案的不可伪造性规约到BBS方案的SEUF-CMA安全性.规约过程分为初始化、询问和伪造3个阶段，包含2类模拟器C0和C1，以及敌手A.规约形式采用嵌套的游戏模拟方式，外层模拟以C0为模拟器，A为敌手，内层模拟(BBS挑战游戏，参考文献[28])以C1为模拟器，C0为敌手，C0可以向C1提交BBS签名询问，最后向C1提交伪造的BBS签名.模拟之前，C0选择i∈{1,2,…,N}，令IDi=ID*表示创建的第i个用户身份.

初始化.输入安全参数λ，挑战者C1产生BBS挑战游戏的公开参数(G1,G2,GT,g1,g2,e,u*,v*,α)发送给模拟器C0，C0产生IBSC游戏公开参数param={G1,G2,GT,g1,g2,e,α,P0,H1,H2,H3,H4,H5}.与定理4的证明过程相同，H1,H2,H3,H4,H5模拟为随机谕言机，C0维护初始为空的L1，L2，L3，L4，L5和LID分别记录H1,H2,H3,H4,H5询问和用户密钥.此外，C0维护初始为空的LSC=(Wi,τi,ωi,hi,σi,ti)记录签密询问的结果.

询问.A自适应地提交多项式时间的下列询问.

步骤2)～7)与定理4证明过程相同.

8) 签密询问.输入(IDs,IDr,mi)，如果IDs=ID*，C0按照SCIBSC算法第1)步计算得到(Wi,τi,ωi)，提交H5询问得到h5i，然后向C1提交h5i的BBS签名询问得到签名(σi,ti)，将ci=(Wi,τi,ωi,σi,ti)返回给A；否则，C0按照SCIBSC算法计算输出ci=(Wi,τi,ωi,σi,ti).其中，H1,H2,H3,H4,H5运算替换为对应的谕言机询问.最后，C0将(Wi,τi,ωi,h5i,σi,ti)插入LSC.

9) 解签密询问.与定理4相同.

显然，如果c*=(W*,τ*,ω*,σ*,t*)是IBSC的有效的伪造密文，那么(h*5,σ*,t*)必然是BBS的有效的伪造签名.即，如果A挑战成功，则C0必然挑战成功.

证毕.

4.2 基于IBSC的ID-AKE方案

本文ID-AKE方案基于3.2节提出的GC-AKE方案和4.1节提出的IBSC算法，描述如下.

系统建立.输入安全参数λ，PKG产生系统参数para={n,q,Rq,χ,a,H,G1,G2,GT,g1,g2,e,α,P0,H1,H2,H3,H4,H5}.系统参数包含了基于格的和基于双线性映射的2套参数.

密钥交换.如果Alice与Bob期望建立安全会话，其密钥交换过程与图2基本相同.为了进一步增强安全性(主要考虑抵抗临时秘密泄露攻击(ESR))，将会话密钥的计算方式替换为

但是这种增强的方式在基于格的密码系统中并不直接适用.因为在基于格的环境下，不具有与离散群相同的CDH假设，则基于格的ESR安全性需要进一步讨论.

5 对比分析

5.1 相关AKE方案对比分析

本文选择FSXY方案[14]、BCNS方案[18]、YCL方案[23]和DBS方案[12]作为对照方案进行对比分析，如表2所示.其中，FSXY方案和YCL方案为通用AKE在格密码系统下的实例；BCNS方案将DHKE-like密钥交换与TLS握手协议整合，实现经典密码系统下的实体认证以及后量子的会话密钥前向安全；DBS方案则采用类似HMQV协议的密钥交换方案，侧重实现隐式认证.本文方案则遵循BCNS方案的思路，将DHKE-like密钥交换与现有经典公钥密码系统相结合，重点关注会话密钥的后量子前向安全性.此外，本文方案也融合了通用AKE的思想，以适应后量子密码技术的发展，以及提供AKE方案的可扩展性.例如，BCNS-DHKE-like密钥交换方案可直接使用其他具有类似DDH属性的DHKE-like密钥交换方案替代，比如NewHope[20]协议.

此外，李子臣等人[24]和赵秀凤等人[22]也分别提出了基于Ring-LWE问题的AKE方案.但是，本文分析发现，这2种方案都存在较为严重的安全缺陷，具体的分析见本文5.2节.

Table 2 Comparison of Several AKE protocols

可以看出，FSXY方案和YCL方案在计算、存储和通信方面的开销都明显较大.特别是通信开销(表2第6列)，表2中仅列出了直接的密钥交换开销和公钥传输的开销，由于基于格的证书系统尚未建立，公钥证书的开销则未列入，其他如密钥调节参数由于相对较小(1 024 b)也未列入.具体来看，FSXY方案共发送9个Rq上的成员(其中2个Rq上的成员为用户长期公钥)，YCL方案则多达2μ+m+5个Rq上的成员.以n=1 024，logq=32为例，1个Rq上的成员约为4 KB，则FSXY方案的通信开销大于36 KB. BCNS方案、DBS方案和本文方案的总体开销差别不大.BCNS方案的计算性能虽然较优，但是TLS握手协议需要多轮信息交互，其总体性能并不占优.此外，FSXY方案、YCL方案和DBS方案未指明用户公钥的授信机制，假定采用PKI体制，与公钥证书相关的开销并未在表2中列出.本文方案实例基于IBC系统，对用户公钥的授权验证包含在IBSC算法中，在通信部分增加约160 B传输开销(假定用户身份标识为20 B).

在安全性方面(表2第7列)，BCNS方案仅实现了客户端对服务器的认证，采用ACCE[39]安全模型(类似于BR+wPFS)；DBS方案实现了相互认证，采用了BR+wPFS模型；FSXY方案采用了CK+模型；YCL方案则采用了eCK-PFS模型；本文提出的通用AKE采用wAKE-PFS模型(见第2节)，而第4节提出的AKE实例则实现了eCK-PFS安全性.严格来讲，FSXY方案和YCL方案的MEX安全性具有较大局限性.由于FSXY方案和YCL方案等通用AKE方案临时秘密参数较多，不能像HMQV协议那样将MEX安全性规约到一个确定的DHKE实例，部分参数泄露仍然不能保证MEX安全性.例如，FSXY方案中的(KA,KB,KT)和YCL方案中的rpgid1泄露同样不能防止会话密钥泄露，在实际应用中，不能区别对待临时的秘密参数.在本文4.2节的AKE实例中，即使所有临时的参数泄露(包括DHKE-like密钥κ)，针对非量子攻击者，也能确保会话密钥的安全性.

5.2 2种AKE方案的安全性分析

5.2.1 NLPQ-AKE方案分析

李子臣等人[24]提出一种基于Ring-LWE问题的AKE方案(记为NLPQ-AKE).NLPQ-AKE中采用的IND-CPA安全的PKE(记为NLPQ-CPA-PKE)是NewHope-Simple KEM的变形.但是，文献[21]不建议NewHope-Simple KEM方案的公钥重复使用.Bauer等人[40]分析表明，对于NewHope-Simple CPA-KEM实例，重用公钥会导致私钥泄露，对于NewHope-Simple CCA-KEM实例，在可能重用公钥的情况下，应谨慎设计CPA-KEM→CCA-KEM转换中的关键步骤.不幸的是，NLPQ-AKE方案中的NLPQ-CCA-KEM机制完全暴露了NLPQ-CPA-PKE机制的密文，不能抵抗密钥重用攻击.NLPQ-AKE方案分为2组独立(分别采用用户长期公钥和临时公钥)的密钥交换，其中采用长期公钥的NLPQ-CCA-KEM实例必然存在公钥重用，将导致用户长期私钥的泄露.根据文献[40]的测试结果，采用Alkim等人[21]推荐的系统参数，只需数千个重用公钥的密文即以较大概率恢复对应的完整私钥.

5.2.2 Zhao-AKE方案分析

赵秀凤等人[22]提出一种基于BCNS-DHKE-like机制的ID-AKE方案(记为Zhao-AKE).但是，Zhao-AKE方案存在较为严重的安全隐患.具体来说，赵秀凤等人提出一种新的基于身份密钥生成算法(详见文献[22]的3.2节)，将用户密钥(Si=IiS+Mei)的安全性建立在Ring-LWE问题的困难性上.其中，Ii=H(IDi)和M为多项式环Rq上具有小范数的元素，S是系统主密钥，ei是误差值，S和ei服从Rq上的离散高斯分布.根据Ring-LWE假设，给定均匀随机的a←URq，求解(a,as+e)∈Rq×Rq中的秘密s是困难的(其中s和e服从Rq上的离散高斯分布).由于Ii和M在Rq上并非随机均匀分布，Zhao-AKE方案的用户密钥产生算法不满足Ring-LWE假设条件，敌手可能利用Ii和M非均匀随机分布的特性，实施对系统主密钥S的猜测攻击.就目前掌握的文献资料来看，没有相关的理论能够证明非随机均匀分布的(a,as+e)满足Ring-LWE假设条件，而文献[22]并未就这一关键问题展开讨论.同理，用户密钥Si也不满足判定Ring-LWE假设.文献[22]的安全性证明中(引理10)，在Game3中用随机的Ii←URq和M1←URq替换真实的Ii和M(Game2)，并声称敌手无法区分Game2和Game3(应用判定Ring-LWE假设).显然，敌手可以通过计算Ii和M1的范数来区分，因为Game2中的Ii和M具有小的范数，而Rq上的随机成员具有小范数的概率很低，Ii和M1的分布不满足判定Ring-LWE假设条件，不适合应用这一假设，文献[22]的安全性证明不成立.基于以上分析，Zhao-AKE方案[22]不是一种安全可靠的ID-AKE方案.

6 结束语

本文以格上(无认证)DHKE-like协议为基础，采用签密机制对DHKE-like协议中的临时公钥进行签密，提出一种“SC+DHKE-like”的可组合AKE构造方案——GC-AKE.GC-AKE结构简单，具有可组合的优点，可根据不同应用场景需求，采用不同密码学原语加以组合.针对向后量子时代过渡的时期，面向AKE协议的后量子前向安全需求，本文提出采用基于ECC的IBSC结合基于理想格的DHKE-like协议实例.在wAKE-PFS模型下，本文的GC-AKE方案实现了可证明安全性，特别是实现了会话密钥的PFS安全性.PFS安全性要求使用具有强不可伪造的签名方案.因此，本文以BBS签名为基础，设计了强不可伪造的IBSC方案，并对其安全性进行了规约证明，实现了IND-CCA和SEUF-CMA安全性.但是，采用基于Ring-LWE问题的DHKE-like协议作为密码套件存在一个关键问题，即：如果加密完整的临时公钥，则加密后的密文较大，使得AKE的计算和通信开销较大.为了解决这一问题，本文提出临时公钥特征提取与隐藏函数，仅加密n位(本文取n=1 024)的特征值，显著降低了需加密传输的数据量，使得本文的AKE协议实例的计算和通信开销相对较优.进一步的优化可采用性能更优的DHKE-like协议替换BCNS-DHKE-like协议，如NewHope协议.