doi：10.3969/j.issn.1671-1122.2021.06.010
基于密钥封装机制的RLWE型认证密钥
交换协议
王超1,2，韩益亮1,2，段晓巍1,2，李鱼1,2
（1.武警工程大学密码工程学院，西安 710086；2.武警部队密码与信息安全保密重点实验室，西安 710086）
摘 要：当前，基于格理论构造密钥交换协议已成为密钥交换领域的研究前沿，设计安全性更强、密钥和密文规模以及通信开销更小的高效密钥交换协议，是格基密
钥交换领域的重难点问题。文章基于紧凑型RLWE公钥加密方案与NewHope-Simple
中的密文压缩和NTT转换技术，结合FO转换机制，提出一种主动安全的KEM方案，
采用隐性认证和身份标识认证的方式，构造出一种在标准eCK模型下可证明安全的认
证密钥交换协议。与NewHope-Simple协议相比，协议安全性由被动安全提升为主动
安全；与现有的基于密钥封装机制的密钥交换协议相比，该协议中的密钥封装机制有
效降低了密文尺寸和通信开销。通过分析可得，文章所提协议是一个紧凑高效、主动
安全的基于密钥封装机制的抗量子认证密钥交换协议。
关键词：RLWE；FO转换；加密机制；认证密钥交换；标准eCK模型
中图分类号：TP309 文献标志码： A 文章编号：1671-1122（2021）06-0080-09
中文引用格式：王超，韩益亮，段晓巍，等.基于密钥封装机制的RLWE型认证密钥交换协议[J].信息网络安全，2021，21（6）：80-88.
英文引用格式：WANG Chao, HAN Yiliang, DUAN Xiaowei, et al. RLWE-type Authentication Key Exchange Protocol Bad on Key Encapsulation Mechanism[J]. Netinfo Security, 2021, 21(6): 80-88.
RLWE-type Authentication Key Exchange Protocol Bad on Key
Encapsulation Mechanism
WANG Chao1,2, HAN Yiliang1,2, DUAN Xiaowei1,2, LI Yu1,2
(1. College of Cryptographic Engineering, Engineering University of PAP, Xi’an 710086, China;2. Key Laboratory of
PAP for Cryptology and Information Security, Xi’an 710086, China)
会议纪要内容Abstract: At prent, constructing key exchange protocol bad on lattice theory has become the rearch frontier in the field of key exchange. Designing efficient key exchange
protocol with stronger curity, smaller size of key and ciphertext and communication overhead
is an important and difficult problem in the field of lattice key exchange.Bad on the compact
收稿日期：2020-12-01
基金项目：国家自然科学基金[61572521]；陕西省自然科学基础研究计划[2021-JM252]；武警工程大学科研创新团队科学基金[KYTD201805]作者简介：王超（1997—），男，山东，硕士研究生，主要
研究方向为抗量子密码；韩益亮（1977—），男，甘肃，教授，博士，主要研究方向为信息安全、抗量子密码；段晓巍（1997—），男，山东，硕士研究生，主要研究方向为抗量子密码；李鱼（1995—），男，重庆，博士研究生，主要研究方向为抗量子密码。
通信作者：
RLWE public key encryption scheme and the ciphertext compression and NTT conversion technology in NewHope-Simple, and combined with FO conversion mechanism, an active cure KEM scheme is propod. Using the implicit authentication and identity authentication methods, an authenticated key exchange protocol which can prove cure under the standard eCK model is constructed. In terms of protocol curity, the propod protocol improves from passive curity to active curity compared with NewHope-Simple protocol. In terms of ciphertext size and communication overhead, compared with the existing key exchange protocols bad on key encapsulation mechanism, the key encapsulation mechanism in this protocol effectively reduces the
ciphertext size and communication overhead through analysis, which is a compact, efficient and active cure anti-quantum authentication key exchange protocol bad on key encapsulation mechanism.
Key words: RLWE; FO conversion; encryption mechanism; authentication key exchange; standard eCK model
0 引言
祝认证密钥交换（Authenticated Key Exchange，AKE）协议使通信双方或多方在不安全的信道上协商得到共享会话密钥，并向通信参与者提供彼此的身份认证，以保证在后期的数据加密中实现数据的保密性和完整性。
SHOR[1]提出量子攻击计算，随着量子攻击计算的发展，基于大整数分解和离散对数问题构造的密钥交换协议面临多项式时间内被攻破的威胁。1997年，AJT AI[2]等人首次提出基于格的加密技术，格密码学者们经过十几年的探讨和发掘，提出了大量的实用抗量子密钥交换方案。自2016年NIST（National Institute of Standards and Technology）启动后量子安全密码算法标准化[3]流程以来，基于格构造的密码算法[4]展现出了良好的性能优势和实用前景，不仅可以有效抵抗量子算法攻击，而且相比基于编码和多项式构造的密码算法[5]，其在算法上简单、高效可并行化，具有更强的可实施性和
应用性。
格上本身的困难问题，如最短向量问题（Short V ector Problem，SVP）、最近向量问题（Clost V ector Problem，CVP）等构造出的密码方案虽然具有很强的安全性，但实现效率较低。2005年，REGEV[6]基于格理论提出错误学习问题（Learning with Errors，LWE），其困难性可归约到一般格上CVP的最坏情形，基于LWE问题设计的加密[4]、签名[7]、密钥交换[8]、全同态加密[9]等在后量子密码算法中具有很强的竞争力。2010年，LYUBASHEVSKY[10]等人提出基于环上的错误学习问题（Ring Learning with Errors，RLWE），其困难性可归约到理想格上的SVP的最坏情形。RLWE 独特的环结构结合NTT转换[11]，使基于RLWE的密码方案在算法性能、密钥尺寸上具有很大的优势。
近年来，基于L WE、RL WE、ML WE[12]问题构造密钥交换协议的研究上，出现了许多新型、高效的密钥交换方案。2012年，DING[13]等人首次提出了错误协调机制，基于SL WE和该机制构造了密钥交换协议，并将其扩展到RL WE上。2014年，PEIKERT[14]提出一种新的错误协调机制并构造了一种被动安全的密钥封装协议，且给出了提升为主动安全密钥交换协议的框架，这种新的错误协调机制将密文长度减少50%。2015年，BOS[15]等人基于RL WE问题和错误协调机制，结合传统的签名方案将KE方案转换为AKE方案并集成到TSL 协议中。2016年，ALKIM[16]等人提出基于RL WE的后量子密钥交换方案NewHope。同年，ALKIM[17]等人基于NewHope方案提出了一种使用加密机制的密钥交换协议NewHope-Simple，降低计算复杂度的同时产生很小的通信量代价，但是该协议在RO模型中仅能达到
IND-CP A安全。2018年，BOS[11]等人基于ML WE提出了CRYST ALS-kyber方案，利用FO（Fujisaki-Okamoto）转换构造了IND-CCA安全的KEM（Key Encapsulation Mechanism）方案，并构造了密钥交换协议。2019年，
李子臣[18]等人基于RL WE提出IND-CCA安全的密钥封装机制，并构造了认证密钥交换协议。同年，杨亚涛[19]等人在eCK模型下基于RL WE提出了支持身份隐私保护的认证密钥交换协议。2020年，HÖVELMANNS[20]等人在量子随机预言模型下提出将任何被动安全的公钥加密（Public key Encryption，PKE）转化为认证密钥交换协议的通用结构FO-AKE，将NIST提交的方案实例化，并给出正确性和安全性证明。
本文对NewHope-Simple中的密钥封装机制进行改进，提出一种新型的主动安全KEM方案和AKE协议。首先基于紧凑型RLWE公钥加密方案与NewHope-Simple中的密文压缩和NTT转换技术，提出一种IND-CP A安全的高效公钥加密方案；然后利用FO转换机制将其转换为IND-CCA安全的新型KEM方案；最后基于新型KEM方案，结合协议双方分别拥有长期、临时密钥对的隐性认证和身份标识认证两
种方式，构造出主动安全的双方认证密钥交换协议。本文协议与相同参数设置下的NewHope-Simple方案相比，安全性由被动安全提升为主动安全，可满足未知密钥共享安全性和弱的完美前向安全性，是一种紧凑高效、主动安全的抗量子双方认证密钥交换协议。
1 相关知识
1.1 RLWE问题cad2012
定义１［１０］ ＲＬＷＥ分布整系数多项式环为R=Z(x)/x n+1，其中n∈Z为2的幂次方，设R q=Z q(x)/x n+1为模素整数q的多项式商环。在R q上随机均匀选取多项式a和秘密值s，在χq上随机均匀选取噪声多项式e，χq为R q上某种公开的特定分布。令b=as+e，则称(a, b)∈R q×R q为RLWE分布。
定义２［１０］ ＲＬＷＥ判定问题 给定样本(a,b)，如何区分(a,b)采样自RLWE分布A s, χ还是R q×R q上的随机均匀分布的问题称为RLWE判定问题。
1.2 密文压缩技术
定义３［１１］ 压缩函数压缩函数Compress q(x,d )= 「2d/
q·x」 mod+2d=y，函数的输入为x∈Z q，输出为y∈{0,…, 2d-1}。其中，d< 「log2q」 。
定义４［１１］ 解压函数 解压函数Decompress q( y,d ) = 「q/2d y」 =x'，函数的输入为y∈{0,…, 2d-1}，输出为x'∈Z q。其中，d< 「log2q」 ，x与x'满足|x'-x mod±q|≤ B q= 「q/2d」 。
1.3 NTT算法
NTT算法原理如公式（1）、公式（2）所示。
NTT=
(g g g X
)=ˆˆ
1023
∑
i=0
i
i（1）其中，g g
ˆi j
=
1023
∑
i=0
γβ
j ij。
NTT=
−1(g g g X
ˆ)=1023∑
i=0
i
i（2）
其中，g n g
i j
=−−−
1γβ
i ij
1023
∑
i=0
ˆ，g R∈q，β是g的本原n次根，γβ
=。
设R q=Z q(x)/x n+1，其中n为2的幂次方，q为素数且满足q ≡ 1mod 2n，则对任意a,b,c∈R q，c=ab，有c= NTT-1(NTT(a)· NTT(b))。
1.4 FO-IND-CCA-KEM算法的形式化定义
通过FO转换技术将IND-CP A安全的公钥加密方案转换为IND-CCA安全的密钥封装机制由以下4个算法组成。
1）初始算法Setup()：输入安全参数K，输出公共参数pp。
2）密钥生成算法KeyGen()：IND-CCA-KEM的密钥生成算法和原始PKE方案相同，即输入pp，输出公钥pk和私钥sk。
3）密钥封装算法Encaps( pk)：输入pk，选择随机数σ←(0,1)L、u←(0,1)L，H和G为定长输出的散列函数，令σ为PKE加密算法中的明文、H(σ||ω)为PKE加密算法中的随机数，根据PKE加密算法、散列函数和一次性填充加密可计算c =PKE.Enc( pp, pk,σ,H(σ ||ω))、k =G(σ,ω)、c'=G(σ)⊕ω，最终输出验证密文(c,c')和会话密钥K=H(k,(c,c'))。雪梨汁
4）密钥解封算法Decaps( pk,sk,(c,c'))：根据sk和
密文c 利用PKE 解密算法，计算出σ'←PKE .Dec (sk ,c )，进而得到ω'=G (σ' )⊕c'、k'=G (σ',ω' )。对(σ',ω)进行重加密操作，验证c 是否等于PKE .Enc ( pp , pk ,σ', H (σ' ||ω'))。若相等，则输出K =H (k',(c ,c'))；否则，输出一个随机密钥K = H (x ,(c ,c'))。其中，x 为随机秘密种子。
2 带身份标识的双方认证密钥交换协议
2.1 协议参数选取
为使公钥加密方案至少达到128位的抗量子安全性，本文采用与NewHope-Simple 相同的参数设置，设n =1024，q =12289 < 214；明文空间M ={0,1}L ，长度L = 1024；中心二项分布为ψk n ，本文选取k =16；β=49，多项式系数有效位为14位；压缩和解压函数的压缩参数d u =d v =3。
2.2 IND-CPA 安全的公钥加密方案
基于紧凑型RL WE 公钥加密方案[4]结合NewHope-Simple 中的密文压缩技术和NTT 转换技术，本文提出一种IND-CP A 安全的新型公钥加密方案，具体流程如下：
1）密钥生成算法PKE KeyGen .()，如算法1所示。算法１ PKE KeyGen .()
ed ← $
{0,1;
}l
a
Par SHAKE ed ˆ←−(128());s e ,;
← $ψ16n s
s b a s e ˆˆˆ←←⋅+NTT(),NTT();ˆoutput pk b ed sk s :(,),;==
ˆˆ首先选取长度为l 的秘密种子ed ，输入到扩展输出函数Par ()[17]，输出一个NTT 域中的多项式a ˆ；然后从中心二项分布中选取秘密值s 和噪声多项式e ，通
过NTT 算法计算得到s
ˆ←NTT(s )、b ˆ←a ˆ·s ˆ+NTT(e )；最后输出公私钥(pk = (b
ˆ, ed ), sk =s ˆ)。2）加密算法PKE .Enc ( pk =(b ˆ, ed ), m ,r )，如算法2所示。
算法２ PKE Enc pk b
ed m r .((,),,)=ˆed ← $
{0,1;
}l
a
Par SHAKE ed ˆ←−(128());r Sam r r r
r ←=∈←{0,1,(),NTT();}l
′′ψ16n
ˆm e e ←← {0,1,,;
}L
′′′$ψ16n
c Compress u a
r e d 1==⋅+q u (NTT(),);ˆˆ′c Compress v
b r e m q d 2==⋅++⋅ q v (NTT ()/2,);−1ˆˆ′′Return
c c c =(,);
12首先选取ed ，输入到函数Par ()[17]，输出一个a ˆ；然后选取长度为l 的比特串r ，通过Sam ()[12]函数生成
一个服从中心二项分布的多项式r'∈ψ16
n
，并将其转换为NTT 域上的多项式r ˆ←NTT(r' )；进一步从中心二项分布
上选取噪声多项式e e ′′′,← $ψ16n
，从M 中选取明文m ，
便利店英文最终输出密文c = (c 1,c 2)。
3）解密算法PKE .Dec (sk =s
ˆ,c =(c 1,c 2))。利用解压函数对密文进行解压，可得u'=Decompress q (c 1,d u )，v'= Decompress q (c 2,d v )，然后通过解密算法解密出明文m'，如算法3所示。
算法３ PKE Dec sk s c c c .(,(,))
==ˆ12u Decompress c d ′=q u (,);1v Decompress c d ′=q v (,);
2m Compress v u s
′′′=−⋅q (NTT (),1);−1ˆ2.3 IND-CCA 安全的NNS.KEM 方案
已知散列函数G :{0,1}*→{0,1}L , H :{0,1}*→{0,1}l ，利用FO 转换将2.2节的IND-CP A 安全的公钥加密方案转换为IND-CCA 安全的NNS.KEM 方案，具体流程如下：
1）密钥生成算法NNS .KeyGen ()。NNS.KEM 方案的密钥生成算法与公钥加密方案的密钥生成算法一致，具体流程见2.2节。
2）密钥封装算法NNS .Encaps ( pk =b ˆ)，如算法4所示。
算法４ NNS Encaps pk b
.()=ˆωσ←←M M ,;
K G ′=(,);
σω(,).(,,(,));();c c CPA Enc pk b H c G 123===+ˆσσωσωc c c c =(,,);123K H K c =(,);′return c K (,);
首先从M 中均匀随机选取两个随机值ω←M 、σ← M ，令σ为明文、H (σ,ω)为随机数，根据算法2，计算
出验证密文(c 1,c 2)=PKE .Enc (pk =b ˆ,σ, H (σ,ω))；然后，根
据散列函数G 、H 和一次填充加密算法，计算子密钥值K'=G (σ,ω)和密文c 3=G (σ)+ω；再将3个密文值级联得到密文c =(c 1,c 2,c 3)并计算得出K =H (K',c )；最终输出密文c 和协商密钥K 。
3）密钥解封算法NNS .Decaps (sk =(s ˆ,b ˆ, ed , x ),c = (c 1,c 2,c 3))，如算法5所示。
算法５ NNS Decaps sk s b
ed x c c c c .((,,,),(,,))==ˆˆ123σ′=CPA Dec s c c .(,(,));ˆ12ωσ′′=
−c G 3();K G ′′′′=(,);
σω(,).(,,(,));c c CPA Enc pk b H 12′′==
半夜猫叫
ˆσσω′′′if (,,),c c c c return 123′′′=K H K c =(,);
′′el ,return K H x c =(,);
首先利用算法3，解密出σ' = PKE .Dec (s ˆ, (c 1,c 2))，进而得到ω'=c 3⊕G (σ' )、K''=G (σ',ω' )；然后根据算法2对σ'和ω'进行重加密操作，并验证重加密后的密文(c 1',c 2',c 3' )是否与原始密文(c 1,c 2,c 3)相等。若相等，则输出正确的协商密钥K = H (K'',c )；否则，输出一个随机会话密钥K =H (x ,c )。
2.4 带身份标识的双方认证密钥交换协议
舞蹈教学计划通信参与者A 和B 各自利用密钥生成算法生成长期公私钥( p k A ,
s k A )、( p k B , s k B )，临时公私钥( p k a , s k a )、( p k b , sk b )，并公布自己的公钥信息和身份标识信息( p k A , p k a , ID A )、( p k B ,
p k b , I D B )，利用本文提出的密钥封装机制NNS.KEM 构造了一个基于RL WE 问题的带身份标识的双方认证密钥交换协议。协议的具体构造过程如图1所示。与书有关的名言
A
B
(,).()
pk sk NNS KeyGen A A ←(,).()pk sk NNS KeyGen a a ←(,).()c K NNS Encaps pk B B B ←(,).()c K NNS Encaps pk b b b ←K NNS Decaps sk c A A A ′←.(,)K NNS Decaps sk c a a a ′←.(,)SK H K K K K ID ID =(,,,,,)
B b A a A B ′′c c
B b ,c c
A a ,(,).()pk sk NNS KeyGen
B B ←(,).()pk sk NNS KeyGen b b ←K NNS Decaps sk c B B B ′←.(,)K NNS Decaps sk c b b b ′←.(,)(,).()c K NNS Encaps pk A A A ←(,).()c K NNS Encaps pk a a a ←SK H K K K K ID ID =(,,,,,)
A a
B b A B ′′图1 带身份标识的双方认证密钥交换协议
3 正确性证明
设δ为解密失败概率，δ=Pr[||er +e''+l v - -sl u ||∞≥ 「q /4」 ]，则本文公钥加密方案的解密正确概率为1-δ。其中，
δ<2-60，取l u ∈R d 、l v ∈R d 。下面将对本文公钥加密方案解密出正确明文的概率进行分析。
Compress q (v'-NTT -1(u's
ˆ),1)=Compress q (Decompress q (c 2,d v )-NTT -1(Decompress q (c 1, d u )s ˆ),1)=Compress q (NTT -1(b ˆr ˆ)+e''+m 「q /2」 +l v -
NTT -1(a
ˆr ˆ s ˆ+NTT(e' )s ˆ+l u s ˆ),1)=Compress q (asr +er +e''+m 「q /2」 +l v -ars -'-sl u ,1)=m'
令ω=er +e''+l v -'-sl u 、||ω||∞< 「q /4」 ，则有v'-NTT -1(u' s ˆ) = ω+m 「q /2」 ，由算法3可得
||v'-NTT -1(u's
ˆ)-m' 「q /2」 ||∞=|ω+m 「q /2」 -m' 「q /2」 ||∞≤ 「q /4」
（3）
已知||ω||∞< 「q /4」 ，因此，根据三角不等式可得|| 「q /2」 · (m -m')||∞<2 「q /4」 ；已知q 为奇数，所以有m'=m ，由此可得本文公钥加密方案的解密正确率为1-δ。H 和G 为随机预言模型下的散列函数，根据文献[21]可得，由FO 转换产生的NNS.KEM 方案的解密正确率为1-δ。因此，根据IND-CCA 安全的NNS.KEM 方案构造的认证密钥交换协议，通信双方可以协商出正确的会话密钥。
4 安全性分析
4.1 KEM 方案安全性证明
首先证明本文构造的新型公钥加密方案为IND-CP A 安全。定义3个游戏G 0、G 1、G 2，其中，G 0为真实IND-CP A 攻击游戏，G 1、G 2是G 0基础上的衍生游戏。
在G 0中，定义一个挑战者和一个敌手N ，N 拥有加密查询能力，当N 结束加密查询训练时，随机选取两个明文(m 0,m 1)发送给挑战者，挑战者随机选取随机值t ←{0,1}，加密m t 得到挑战密文c 0并发送给N ，N 通过加密查询训练（没有查询m t 的权限）输出一个猜测
值t'，定义N 赢得游戏的优势为Adv PKE
CP A
(N )=|Pr [t =t' in the game G 0]-1/2|。
在G 1中，从R q 中随机均匀选取一个随机值代替
真实公钥b
ˆ←a ˆ·s ˆ+NTT(e )，基于RLWE 判定问题的困难性，对于N 来说G 1与G 0在计算上是不可区分的，且
