楊亞濤 張亞澤 李子臣 張峰娟 劉博雅

1(北京電子科技學(xué)院通信工程系 北京 100070) 2(北京印刷學(xué)院教務(wù)處 北京 102600) 3(西安電子科技大學(xué)通信工程學(xué)院 西安 710071) (yy2008@163．com)

2017-06-14；

2017-08-01

國家自然科學(xué)基金項目(61370188)；“十三五”國家密碼發(fā)展基金項目(MMJJ20170110)；中央高?；究蒲袠I(yè)務(wù)費專項資金項目(328201523) This work was supported by the National Natural Science Foundation of China (61370188), the State Cryptography Development Fund of the Thirteen Five-Year Plan (MMJJ20170110), and the Fundamental Research Funds for the Central Universities (328201523).

RAKA:一種新的基于Ring-LWE的認(rèn)證密鑰協(xié)商協(xié)議

楊亞濤1,3張亞澤1,3李子臣2張峰娟1,3劉博雅1

1(北京電子科技學(xué)院通信工程系 北京 100070)2(北京印刷學(xué)院教務(wù)處 北京 102600)3(西安電子科技大學(xué)通信工程學(xué)院 西安 710071) (yy2008@163．com)

后量子時代，基于格理論的公鑰密碼被認(rèn)為是最有前途的抵抗量子計算機攻擊的公鑰密碼體制.然而，相對于格上公鑰加密體制和數(shù)字簽名方案的快速發(fā)展，基于格上困難問題的密鑰協(xié)商協(xié)議成果卻較少.因此，現(xiàn)階段如何構(gòu)建格上安全的密鑰協(xié)商協(xié)議是密碼學(xué)領(lǐng)域具有挑戰(zhàn)性的問題之一.針對上述問題，基于環(huán)上帶錯誤學(xué)習(xí)問題困難假設(shè)，采用調(diào)和技術(shù)構(gòu)造了一種新的認(rèn)證密鑰協(xié)商協(xié)議RAKA(authenticated key agreement protocol based on reconciliation technique)，該方案采用格上陷門函數(shù)技術(shù)提供了單向認(rèn)證功能，并且在Ring-LWE假設(shè)下證明是安全的.與現(xiàn)有的基于LWE的密鑰協(xié)商協(xié)議相比，該方案的共享會話密鑰減小為2nlogq，效率更高；同時，由于該方案的安全性是基于格上困難問題，因此可以抵抗量子攻擊.

格理論；認(rèn)證密鑰協(xié)商；調(diào)和技術(shù)；環(huán)上錯誤學(xué)習(xí)問題；抗量子攻擊

密鑰協(xié)商協(xié)議[1-2](key agreement protocol, KA)是密碼學(xué)的基本原語，允許通信雙方在不安全的信道上協(xié)商出共同的會話密鑰，并借助該會話密鑰及相應(yīng)的密碼算法進行保密通信，是保證網(wǎng)絡(luò)通信安全的重要密碼學(xué)組件.Diffie-Hellman提出了第1個密鑰協(xié)商協(xié)議[3]，該協(xié)議也拉開了公鑰密碼學(xué)的序幕.自從Diffie-Hellman(DH)密鑰協(xié)商協(xié)議提出以來，由于它構(gòu)造結(jié)構(gòu)簡單并且實用，不少密碼學(xué)者設(shè)計了很多基于DH的密鑰協(xié)商協(xié)議.認(rèn)證密鑰協(xié)商協(xié)議(authenticated key agreement, AKA)是在密鑰協(xié)商的基礎(chǔ)上擁有了通信雙方的認(rèn)證功能，目前AKA協(xié)議已經(jīng)被廣泛應(yīng)用于電子商務(wù)系統(tǒng)和電子政務(wù)系統(tǒng)等安全需求較高的系統(tǒng)中，因此對AKA協(xié)議的研究和設(shè)計具有很大的理論意義和實用價值.

后量子時代，由于基于大整數(shù)分解和離散對數(shù)問題的傳統(tǒng)公鑰密碼體制容易受到量子計算機攻擊，因此尋找抗量子攻擊的AKA協(xié)議非常具有研究價值.后量子密鑰協(xié)商協(xié)議已經(jīng)被美國國家標(biāo)準(zhǔn)技術(shù)研究院(National Institute of Standards and Technology， NIST)作為一項重大科研項目.格理論(Lattice)是設(shè)計后量子安全公鑰密碼方案的重要理論，基于格理論設(shè)計的密碼方案具有抗量子計算機攻擊、計算效率高、可證明安全等優(yōu)勢.因此，基于格理論的公鑰密碼方案是后量子時代最具潛力替代傳統(tǒng)基于數(shù)論難題的密碼方案.2009年Regev提出錯誤學(xué)習(xí)(learning with errors， LWE)困難問題，并指出求解平均困難問題LWE的難度可以規(guī)約到求解格上最壞情況下困難問題[4].自從Regev提出LWE困難問題以來，由于該困難問題的困難性和良好的代數(shù)結(jié)構(gòu)，在密碼方案的構(gòu)造方面已經(jīng)得到了廣泛應(yīng)用.基于格的公鑰加密方案[5]、數(shù)字簽名方案[6-7]已經(jīng)得到了很好的發(fā)展，格理論也有可能成為設(shè)計后量子安全密碼方案的依據(jù).

相比基于格的加密、數(shù)字簽名方案，基于格的認(rèn)證密鑰協(xié)商協(xié)議(lattice-based AKA, LBAKA)發(fā)展起步較晚.目前，設(shè)計后量子安全的AKA主要存在2方面思路：1)直接基于錯誤學(xué)習(xí)問題LWE和小整數(shù)解問題(small integer solution, SIS)的不同形式來直接構(gòu)造認(rèn)證密鑰協(xié)商協(xié)議.2)基于密鑰封裝(key encapsulation mechanism, KEM)與調(diào)和技術(shù)來構(gòu)造密鑰協(xié)商協(xié)議.自從2012年丁津泰首次提出一種基于LWE的密鑰協(xié)商協(xié)議[8]以來，基于LWE,RLWE的密鑰協(xié)商協(xié)議得到了發(fā)展，成果頗多.2014年丁津泰等人根據(jù)矩陣乘法滿足結(jié)合律，使用LWE困難問題構(gòu)造了密鑰協(xié)商協(xié)議，并擴展到Ring-LWE上[9].在EURPCRYPT 2015上，張江等人首次提出了基于理想格上兩輪認(rèn)證密鑰協(xié)商協(xié)議[10]，該協(xié)議是基于Ring-LWE困難問題構(gòu)造的，并且證明了該方案在加強的BR模型下是安全的.同年，楊孝鵬等人[11]基于Ring-DLWE困難問題提出了認(rèn)證密鑰協(xié)商協(xié)議，并證明方案是CK模型中可證明安全的.

本文利用調(diào)和技術(shù)(reconciliation technique，RT)基于Ring-LWE困難問題設(shè)計了一輪的單向認(rèn)證密鑰協(xié)商算法.

1 預(yù)備知識

LWE問題就是從上述方程組中求出s.

定義2. 環(huán)上帶誤差的學(xué)習(xí)問題(RLWE).定義

2) RLWE搜索問題(RLWE search).給定概率分布bi=ai,s+ei，以不可忽略的概率輸出

定義3. 調(diào)和技術(shù)(reconciliation technique).調(diào)和技術(shù)是Peikert在文獻[12]中首次提出的，該方法思路來源于Ding等人提出的調(diào)和方法，Peikert在此基礎(chǔ)上進行了改進，提出了新的調(diào)和技術(shù).

1) 當(dāng)p=2，q是偶數(shù)時:

任取x∈，定義x=x+∈，xp

·2×vmod 2,

則對于所有的元素v∈q，I0和I1給出了一個劃分，即當(dāng)v∈I0或v∈I1，有v2=0；對于另一種劃

下面定義調(diào)和函數(shù)rec:q×2→2,

rec(ω)

其中,E，如果v,ω∈q非常接近，那么給定ω和v2，我們可以恢復(fù)出v2，利用上述原理可以得到結(jié)論：

對于偶數(shù)q，如果對于v∈q，e∈E，ω=v+e(modq)，則rec(ω)=v2.

2) 對于奇數(shù)q，定義隨機化函數(shù)dbl:q→2q，如果v∈q是隨機均勻的則2=rec(ω)是隨機均勻的.

上述結(jié)論是對于q為偶數(shù)時，但是在RLWE的實際應(yīng)用中考慮到方案的安全性，q往往被設(shè)定為充分大的素數(shù).

2 方案描述

考慮多項式環(huán)R=[x]f(x)，其中f(x)=xn+1，其中n為2的冪次方，令Rq=RqR，則Rq中的元素可以表示為

f(x)=a0+a1x+…+an-1xn-1.

① 從高斯分布D中選取矩陣R∈q;

RAKA方案流程如圖1所示:

Fig. 1 Flow process of RAKA圖1 RAKA方案流程

圖1詳細(xì)流程說明如下：

3) Alice收到(cB,pB)后，首先利用陷門TA和cB使用表2中算法2恢復(fù)s2和e2，驗證Bob的身份[13]，如果驗證不通過，則終止；如果通過，則計算共享密鑰k1=rec(pBsA)，同樣Bob計算共享密鑰k2=rec(pAsB).

算法2. 陷門函數(shù)求逆算法InvertO(R,A,b).

輸出：向量s和e.

① 校驗矩陣A∈n×mq；陷門R∈m×kn；

② 可逆標(biāo)簽矩陣H∈n×nq；

③ 向量bt=gA(s,e)=stA+et，e∈m，s∈nq.

3 方案的正確性

4 安全性證明

定理1. 如果Ring-LWE假設(shè)成立，則RAKA協(xié)議在被動PPT敵手攻擊下是安全的.

證明. 下面我們將通過一系列的Games來證明方案的安全性.令kB=pAsB，kA=pBsA，首先Game0中的敵手得到的是真實的kB，是敵手和協(xié)議之間真實的交互，而Game4中敵手得到的是一個隨機均勻地kB.下面我們證明，在Ring-LWE假設(shè)成立下，Game0到Game4對于PPT敵手是計算不可區(qū)分的.

Game0. 該游戲是在挑戰(zhàn)者和被動敵手A之間執(zhí)行的，敵手獲得m,pA,pB,kA,kB,則敵手輸出猜測值b′.

Game2. Game2與Game1大致相同，除了pB和kB的設(shè)置，挑戰(zhàn)者將pB設(shè)置為隨機值bB，將kB設(shè)置為隨機值u.

Game3. Game3與Game2大致相同，挑戰(zhàn)者在Game2的基礎(chǔ)上，令pA=msA+eAmodq，即相比于Game2中，pA不是隨機值.

Game4. 挑戰(zhàn)者在Game3的基礎(chǔ)上將pB=msB+eBmodq.

證畢.

引理1. 如果Ring-LWE假設(shè)成立，則Game0和Game1在被動PPT敵手攻擊下是計算不可區(qū)分的.

如果bA是Ring-LWE的一個樣本值，則A得到的與Game0中完全一樣，如果bA是一個隨機均勻選取的隨機值，那么A得到的與Game1中完全一樣.這就意味著，如果A可以以不可忽略的概率區(qū)分Game0和Game1，那么B就可以以同樣的概率來區(qū)分Ring-LWE樣本和隨機值.

證畢.

引理2. 如果Ring-LWE假設(shè)成立，則Game1和Game2在被動PPT敵手攻擊下是計算不可區(qū)分的.

證明. 如果存在敵手A可以區(qū)分Game1和Game2，那么我們可以構(gòu)造出一個PPT敵手B可以區(qū)分Ring-LWE樣本與隨機均勻值.針對Game1與Game2的區(qū)別，敵手B可以從Ring-LWE挑戰(zhàn)者得到m,bB，bA，u，敵手B令pA=bA，pB=bB，kB=u，發(fā)送(m,pA,pB,kB)給敵手A.注意到，如果u和bB都是Ring-LWE的樣本值，那么A得到的與Game1中完全相同.如果u和bB都是隨機值，那么A得到的就與Game2中完全相同.因此，如果敵手A可以以不可忽略的概率區(qū)分Game1和Game2，那么敵手B也可以以相同的概率來區(qū)分Ring-LWE樣本和隨機值，從而攻破Ring-LWE困難問題.

證畢.

引理3. 如果Ring-LWE假設(shè)成立，那么Game2和Game3在被動PPT敵手攻擊下是計算不可區(qū)分的.

證明. 引理3的證明可以參照引理1證明過程，需要注意的是在Game2和Game3中kB=u為隨機值.

證畢.

引理4. 如果Ring-LWE假設(shè)成立，那么Game3和Game4在被動PPT敵手攻擊下是計算不可區(qū)分的.

證明. 引理3的證明可以參照引理2證明過程，需要注意的是在Game3和Game4中kB也設(shè)定為隨機值u.

證畢.

5 效率分析

本文主要從方案中共享密鑰的大小和協(xié)商輪數(shù)考慮方案的效率.表1是本文方案與文獻[8-9]的效率對比.

Table 1 Comparison Between Some Key Agreement Schemes Based on Ring-LWE表1 基于Ring-LWE密鑰協(xié)商方案的性能比較

6 總 結(jié)

本文基于RLWE困難問題設(shè)計了一輪單向認(rèn)證密鑰協(xié)商協(xié)議，方案中使用調(diào)和技術(shù)來提供雙方共享密鑰.本文所設(shè)計方案的密鑰尺寸減小為2nlogq，并且協(xié)商輪數(shù)也減少，但是方案實現(xiàn)的是單項認(rèn)證.因此，下一步工作要進一步研究在此基礎(chǔ)上如何實現(xiàn)雙向認(rèn)證的密鑰協(xié)商協(xié)議.

[1] Dodis Y, Mironov I, Stephens-Davidowitz N. Message transmission with reverse firewalls-secure communication on corrupted machines[G] //LNCS 9814: Advances in Cryptology (CRYPTO 2016). Berlin: Springer, 2016: 341-372

[2] Benzvi A, Blackburn S R, Tsaban B. A practical cryptanalysis of the algebraic eraser[G] //LNCS 9814: Advances in Cryptology (CRYPTO 2016). Berlin: Springer, 2016: 179-189

[3] Diffie W, Hellman M. New directions in cryptography[J]. IEEE Trans on Information Theory, 1976, 22(6): 644-654

[4] Regev O. On Lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM, 2009, 56(6): 1-37

[5] Clear M, Mcgoldrick C. Multi-identity and multi-key leveled FHE from learning with errors[G] //LNCS 9216: Advances in Cryptology (CRYPTO 2015). Berlin: Springer, 2015: 630-656

[6] Ling San, Nguyen K, Wang Huaxiong. Group signatures from Lattices: Simpler, tighter, shorter, ring-based[G] //LNCS 9020: Proc of the 2015 Advances in Public Key Cryptography (PKC2015). Berlin: Springer, 2015: 427-449

[7] Gorbunov S, Vaikuntanathan V, Wee H. Predicate encryption for circuits from LWE[G] //LNCS 9216: Advances in Cryptology (CRYPTO 2015). Berlin: Springer, 2015: 503-523

[8] Ding Jintai. A simple provably secure key exchange scheme based on the learning with errors problem, 20121210: 115748[R]. New York: IACR, 2012

[9] Ding Jintai, Xie Xiang, Lin Xiaodong. A simple provably secure key exchange scheme based on the learning with errors problem, 20140729: 180116[R]. New York: IACR, 2014

[10] Zhang Jiang, Zhang Zhenfeng, Ding Jintai, et al. Authenticated key exchange from ideal Lattices[G] //LNCS 9057: Advances in Cryptology (EUROCRYPT 2015). Berlin: Springer, 2015: 719-751

[11] Yang Xiaopeng, Ma Wenping, Zhang Chengli. New authenticated key exchange scheme based on ring learning with errors problem[J]. Journal of Electronics & Informa-tion Technology, 2015, 37(8): 1984-1988 (in Chinese)

(楊孝鵬, 馬文平, 張成麗. 一種新型基于環(huán)上帶錯誤學(xué)習(xí)問題的認(rèn)證密鑰交換方案[J]. 電子與信息學(xué)報, 2015, 37(8): 1984-1988)

[12] Peikert C. Lattice cryptography for the Internet [G] //LNCS 8772: Proc of 2014 Post-Quantum Cryptography (PQCrypto 2014). Berlin: Springer, 2014: 197-219

[13] Micciancio D, Peikert C. Trapdoors for Lattices: Simpler, tighter, faster, smaller[G] //LNCS 7237: Advances in Cryptology (EUROCRYPT 2012). Berlin: Springer, 2012: 700-718

RAKA:NewAuthenticatedKeyAgreementProtocolBasedonRing-LWE

Yang Yatao1,3, Zhang Yaze1,3, Li Zichen2, Zhang Fengjuan1,3, and Liu Boya1

1(DepartmentofCommunicationEngineering,BeijingElectronicScience&TechnologyInstitute,Beijing100070)2(OfficeofEducationalAdministration,BeijingInstituteofGraphicCommunication,Beijing102600)3(SchoolofCommunicationEngineering,XidianUniversity,Xi’an710071)

During the post quantum era, public key cryptosystem based on Lattice is considered to be the most promising cryptosystem to resist quantum computer attack. Comparing to the rapid development of public key encryption and digital signature schemes based on Lattice, the key agreement protocols rarely appeared in the research papers. Therefore, how to construct the secure key agreement protocol is one of the most challenging problems. To solve this problem above, a secure key agreement protocol RAKA based on reconciliation technique and ring learning with errors (Ring-LWE) is designed. The proposed scheme is provably secure under the Ring-LWE assumption and can provide authentication by using the Lattice-based trapdoor function. Compared with current key agreement schemes based on LWE, this scheme is more efficient and the shared key size is reduced to 2nlogq. Moreover, this scheme can resist quantum attack because of the hard assumption on Lattice.

Lattice; authenticated key agreement (AKA); reconciliation technique; ring learning with errors (Ring-LWE); resist quantum attacks

his master degree from Xidian University. His main research interests include cryptosy-stems and information security.

TP309

YangYatao, born in 1978. Associate professor at Beijing Electronic Science and Technology Institute. Received his PhD degree from Beijing University of Posts and Telecommunications in 2009. His main research interests include information security, homomorphic cryptosystems, design of cryptographic protocol and algorithm.

LiZichen, born in 1965. Professor at Beijing Institute of Graphic Communica-tion. Received his PhD degree from Beijing University of Posts and Telecommunica-tions in 1999. His main research interests include cryptography, digital signature, design of cryptographic protocol and algorithm.

ZhangFengjuan, born in 1992. Received her master degree from Xidian University. Her main research interests include crypto-systems and information security.

LiuBoya, born in 1990. Received his master degree from Beijing Electronic Science and Technology Institute. His main research interests include crypto-systems and information security.