RAKA:一種新的基于Ring-LWE的認證密鑰協商協議

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

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

2017-06-14；

2017-08-01

國家自然科學基金項目(61370188)；“十三五”國家密碼發展基金項目(MMJJ20170110)；中央高?；究蒲袠I務費專項資金項目(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的認證密鑰協商協議

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

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

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

格理論；認證密鑰協商；調和技術；環上錯誤學習問題；抗量子攻擊

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

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

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

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

1 預備知識

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

定義2. 環上帶誤差的學習問題(RLWE).定義

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

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

1) 當p=2，q是偶數時:

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

·2×vmod 2,

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

下面定義調和函數rec:q×2→2,

rec(ω)

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

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

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

上述結論是對于q為偶數時，但是在RLWE的實際應用中考慮到方案的安全性，q往往被設定為充分大的素數.

2 方案描述

考慮多項式環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詳細流程說明如下：

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

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

輸出：向量s和e.

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

② 可逆標簽矩陣H∈n×nq；

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

3 方案的正確性

4 安全性證明

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

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

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

Game2. Game2與Game1大致相同，除了pB和kB的設置，挑戰者將pB設置為隨機值bB，將kB設置為隨機值u.

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

Game4. 挑戰者在Game3的基礎上將pB=msB+eBmodq.

證畢.

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

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

證畢.

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

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

證畢.

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

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

證畢.

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

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

證畢.

5 效率分析

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

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

6 總 結

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

[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)

(楊孝鵬, 馬文平, 張成麗. 一種新型基于環上帶錯誤學習問題的認證密鑰交換方案[J]. 電子與信息學報, 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.