楊孝鵬 馬文平 張成麗

?

一種新型基于環(huán)上帶誤差學(xué)習(xí)問(wèn)題的認(rèn)證密鑰交換方案

楊孝鵬*馬文平 張成麗

(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 西安 710071)

利用格上判定帶誤差學(xué)習(xí)問(wèn)題(Ring-DLWE)困難假設(shè)，該文基于Peikert的調(diào)和技術(shù)構(gòu)造認(rèn)證密鑰交換方案。在標(biāo)準(zhǔn)模型下，該方案是CK模型中可證明安全的，并達(dá)到弱前向安全性(wPFS)。與現(xiàn)有的基于LWE的密鑰交換方案相比，該方案使用平衡的密鑰提取函數(shù)，因而保護(hù)共享會(huì)話密鑰，同時(shí)因其基于格中困難問(wèn)題，所以能抵抗量子攻擊。

密碼學(xué)；格；認(rèn)證密鑰交換；CK模型；環(huán)上判定帶誤差學(xué)習(xí)問(wèn)題(Ring-DLWE)

1 引言

認(rèn)證密鑰交換是密碼學(xué)中的基本原型。它不僅允許通信雙方協(xié)商出共享密鑰而且為雙方提供認(rèn)證。每個(gè)通信方擁有一對(duì)靜態(tài)公私鑰，其中靜態(tài)公鑰由可信第三方頒發(fā)。在協(xié)議執(zhí)行過(guò)程中，每個(gè)通信方首先生成自己的短暫公私鑰，再計(jì)算會(huì)話狀態(tài)，最后利用密鑰提取函數(shù)計(jì)算共享密鑰。

近年來(lái)，基于格的密碼體制因其具有較高的漸進(jìn)效率、可并行計(jì)算、抗量子攻擊等優(yōu)點(diǎn)，迅速成為密碼學(xué)研究新熱點(diǎn)，并取得了一系列成果。其中，基于帶誤差學(xué)習(xí)(Learning With Errors, LWE)問(wèn)題的困難性在建立秘密共享方案方面應(yīng)用廣泛。文獻(xiàn)[6]基于LWE提出了認(rèn)證密鑰交換協(xié)議，并證明協(xié)議是強(qiáng)安全的。文獻(xiàn)[7]指出文獻(xiàn)[6]的協(xié)議難以抵抗不知道任何秘密信息的外部攻擊者實(shí)施的假冒攻擊。文獻(xiàn)[8]提出基于LWE的秘密共享方案。該方案借助符號(hào)函數(shù)來(lái)降噪，但符號(hào)函數(shù)泄露了密鑰的一些信息。文獻(xiàn)[9]提出基于LWE的認(rèn)證密鑰交換方案，并構(gòu)造了特征函數(shù)和符號(hào)函數(shù)。為了使符號(hào)函數(shù)輸出分布與均勻分布不可區(qū)分，要求模數(shù)很大。針對(duì)現(xiàn)有文獻(xiàn)的不足，該文基于環(huán)上帶誤差學(xué)習(xí)問(wèn)題(RLWE)問(wèn)題[10]提出新的認(rèn)證密鑰交換方案，使用較小的模數(shù)，并利用平衡密鑰提取器，所以不會(huì)泄露共享密鑰的信息，而且所有計(jì)算可以采用分圓域上快速傅里葉變換(FFT)[10]加速。

2 預(yù)備知識(shí)

2.1符號(hào)說(shuō)明

2.2格上亞高斯變量

定義1[10]對(duì)于,，若滿足，則稱(chēng)上隨機(jī)變量是標(biāo)準(zhǔn)偏差為的-亞高斯變量。由馬爾科夫不等式得：，有

事實(shí)1[10]若是-亞高斯變量，標(biāo)準(zhǔn)偏差為,是-亞高斯變量，標(biāo)準(zhǔn)偏差為。與相互獨(dú)立，則是-亞高斯變量，標(biāo)準(zhǔn)偏差為。

引理1[10]設(shè)是-亞高斯變量，標(biāo)準(zhǔn)偏差為。，則對(duì)于，用的每個(gè)解碼基表示時(shí)，系數(shù)均是-亞高斯變量，標(biāo)準(zhǔn)偏差為。

引理2[10]設(shè)，其中,。則是-亞高斯變量，標(biāo)準(zhǔn)偏差為，且以至少的概率成立。

2.3代數(shù)整數(shù)環(huán)上格的抽樣

2.4困難問(wèn)題

定義2[4,10]對(duì)于,上的分布，隨機(jī)均勻選取,是服從的噪聲。計(jì)算。記的分布為。以不可忽略的概率區(qū)分與上的均勻分布問(wèn)題就是判定Ring-LWE問(wèn)題，記作。

引理3[4]設(shè)，向量，分布與分布統(tǒng)計(jì)距離至多為。

2.5 安全模型

安全模型定義請(qǐng)參見(jiàn)文獻(xiàn)[13]。

2.6調(diào)和技術(shù)

調(diào)和函數(shù)定義請(qǐng)參見(jiàn)文獻(xiàn)[11]。

引理4[11]對(duì)于偶數(shù)模，若是隨機(jī)均勻的，則是隨機(jī)均勻的。

引理5[11]對(duì)于偶數(shù)模，若,,，則。

引理6[11]對(duì)于奇數(shù)模，若是隨機(jī)均勻的，，給定條件下，的分布是一致分布。

3 方案

3.1方案描述

圖1 基于Ring-LWE的認(rèn)證密鑰交換方案

3.2正確性

3.3參數(shù)選取

3.4效率比較

方案效率由計(jì)算復(fù)雜度和通信復(fù)雜度組成。計(jì)算復(fù)雜度主要考慮向量乘法和抽樣。通信復(fù)雜度考慮發(fā)送比特總數(shù)。表1對(duì)現(xiàn)有的基于Ring-LWE的密鑰交換方案做比較(密鑰為bit)。

表1 基于Ring-LWE的密鑰交換方案的性能比較(密鑰為bit)

表1 基于Ring-LWE的密鑰交換方案的性能比較(密鑰為bit)

方案認(rèn)證q的尺寸困難假設(shè)安全模型計(jì)算復(fù)雜度ROM發(fā)送比特總數(shù) 文獻(xiàn)[8]×n4×× 文獻(xiàn)[9]√BR√ 本文√CK×

4 安全分析

1,0這個(gè)游戲是敵手和協(xié)議之間的真實(shí)交互。按照模型規(guī)定的能力向模擬器發(fā)出詢(xún)問(wèn)，并得到相應(yīng)的回答。特別地，當(dāng)向一個(gè)未完成的會(huì)話發(fā)出詢(xún)問(wèn)時(shí)，選取。若，則返回一個(gè)隨機(jī)密鑰給。否則，返回的真實(shí)密鑰給。

1,1這個(gè)游戲和1,0基本相同，下述情況除外：抽取，計(jì)算，選取，計(jì)算，選取，計(jì)算，依據(jù)協(xié)議規(guī)范地計(jì)算，并發(fā)送給。

1,2這個(gè)游戲和1,1基本相同，下述情況除外：選取，計(jì)算，選取，設(shè)置，依據(jù)協(xié)議規(guī)范地計(jì)算和。

1,3這個(gè)游戲和1,2基本相同，下述情況除外：選取,，計(jì)算，選取，計(jì)算，選取，并設(shè)置，發(fā)送給。

1,2中替換為1,3中的隨機(jī)值。設(shè)和是兩個(gè)Ring-LWE挑戰(zhàn)組。構(gòu)造求解Ring-LWE問(wèn)題的區(qū)分器,設(shè)置,,，選取，計(jì)算，設(shè)置，依據(jù)協(xié)議規(guī)范計(jì)算。另外，選取，設(shè)置，發(fā)送給。若是困難問(wèn)題，則

1,4這個(gè)游戲和1,3基本相同，下述情況除外：選取，設(shè)置作為共享密鑰。在1,4中，是均勻隨機(jī)的。給定條件下，的輸出分布統(tǒng)計(jì)接近均勻分布。1,3與1,4計(jì)算不可區(qū)分，且有

2,0這個(gè)游戲與情形1中游戲相同。

2,1這個(gè)游戲和2,0基本相同，下述情況除外：抽取，計(jì)算，抽取，計(jì)算，選取，計(jì)算，選取，計(jì)算，并發(fā)送給。類(lèi)似分析與的不可區(qū)分性，可以得到

2,2這個(gè)游戲和2,1基本相同，下述情況除外：用替換中的。類(lèi)似分析與的不可區(qū)分性，可以得到

2,3這個(gè)游戲和2,2基本相同，下述情況除外：抽取，計(jì)算，選取，計(jì)算，依據(jù)協(xié)議規(guī)范地計(jì)算。類(lèi)似分析與的不可區(qū)分性，可以得到

2,4這個(gè)游戲和2,3基本相同，下述情況除外：抽取，計(jì)算，計(jì)算，計(jì)算，依據(jù)協(xié)議規(guī)范地計(jì)算。由引理3可知不能區(qū)分2,4與2,3。則有

2,5這個(gè)游戲和2,4基本相同，下述情況除外：選取，依據(jù)協(xié)議規(guī)范地計(jì)算。因?yàn)樵陔S機(jī)均勻條件下，的分布是一致分布。由引理5可知猜測(cè)成功的優(yōu)勢(shì)可忽略，則有

5 結(jié)束語(yǔ)

本文利用Ring-DLWE困難假設(shè)，基于調(diào)和技術(shù)構(gòu)造出一種新型認(rèn)證密鑰交換方案。相對(duì)于現(xiàn)有的基于LWE的認(rèn)證密鑰交換方案來(lái)說(shuō)，本文使用較小的模數(shù)，并利用平衡函數(shù)提取共享密鑰。下一步工作可以考慮基于LWE構(gòu)造強(qiáng)安全的認(rèn)證密鑰交換方案。

參考文獻(xiàn)

[1] Gentry C, Peikert C, and Vaikuntanathan V. Trapdoor for hard lattices and new cryptographic constructions[C]. Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, BC , Canada, 2008: 197-206.

[3] Peikert C. Public-key cryptosystems for the worst-case shortest vector problem[C]. Proceedings of the 41th Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA, 2009: 333-342.

[4] Lyubashevsky V, Peikert C, and Regev O. On ideal lattices and learning with errors over rings[C]. Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Riviera, France, 2010: 1-23.

[5] Benny A, David C, and Peikert C. Fast cryptographic primitives and circular-secure encryption based on hard learning problems[C]. Proceedings of the 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, 2009: 595-618.

[6] Fujioka A, Suzuki K, Xagawa K,. Practical and post-quantum authenticated key exchange from one-way secure key encapsulation mechanism[C]. Proceedings of the 8th ACM Symposium on Information, Computer, and Communication Security, Hangzhou, China, 2013: 83-94.

[7] 胡學(xué)先, 魏江宏, 葉茂, 等. 對(duì)一個(gè)強(qiáng)安全的認(rèn)證密鑰交換協(xié)議的分析[J]. 電子與信息學(xué)報(bào), 2013, 35(9): 2278-2282.

Hu Xue-xian, Wei Jiang-hong, Ye Mao,.. Cryptanalysis of a strongly secure authenticated key exchange protocol[J].&, 2013, 35(9): 2278-2282.

[8] Ding Jin-tai. A simple provably secure key exchange scheme based on the learning with errors problems[OL]. http://eprint.iacr.org/2012/688, 2014, 6.

[9] Zhang Jiang, Zhang Zhen-feng, Ding Jin-tai,Authenticated key exchange from ideal lattices[OL]. http://eprint.iacr.org/2014/589, 2014, 7.

完善的知識(shí)產(chǎn)權(quán)管理體系對(duì)“三農(nóng)”產(chǎn)業(yè)的發(fā)展和保護(hù)具有重要意義，能夠推動(dòng)企業(yè)不斷發(fā)展升級(jí)，從而產(chǎn)生經(jīng)濟(jì)效益。通過(guò)對(duì)知識(shí)產(chǎn)權(quán)的實(shí)際運(yùn)用，使企業(yè)能夠充分發(fā)揮自身的創(chuàng)新潛力，為企業(yè)的健康可持續(xù)發(fā)展奠定堅(jiān)實(shí)基礎(chǔ)。

[10] Lyubashevsky V, Peikert C, and Regev O. A toolkit for ring-LWE cryptography[C]. Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, 2013: 35-54.

[11] Peikert C. Lattice cryptography for the Internet[C]. Proceedings of the 6th International Workshop, Post-Quantum Cryptography, Waterloo, Canada, 2014: 197-219.

[12] Peikert C. An efficient and parallel gaussian sampler for lattices[C]. Proceedings of the 30th Annual International Cryptology Conference, Santa Barbara, CA, USA, 2010: 80-97.

[13] Canetti R and Krawczyk H. Analysis of key-exchange protocols and their use for building secure channels[C]. Proceedings of the 20th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Innsbruck, Austria, 2001: 453-474.

New Authenticated Key Exchange Scheme Based on Ring Learning with Errors Problem

Yang Xiao-peng Ma Wen-ping Zhang Cheng-li

(,710071,)

Using the hard assumption of Ring-Decision Learning With Errors (Ring-DLWE) in the lattice, a new Authenticated Key Exchange (AKE) scheme is proposed, which is based on the Peikert’s reconciliation technique. Under the standard model, the proposed scheme is provably secure in the CK model, which is additionally achieves weak Perfect Forward Secrecy (wPFS). Compared with the current Key Exchange (KE) schemes based on the LWE, the proposed scheme not only protects the shared session key with balanced key derivation function but also resists quantum attacks because of the hard assumption on lattice problem.

Cryptography; Lattice; Authenticated Key Exchange (AKE); CK model; Ring-Decision Learning With Errors (Ring-DLWE)

TP309

A

1009-5896(2015)08-1984-05

10.11999/JEIT141506

楊孝鵬 xp_yang89xidian@126.com

2014-11-27收到，2015-02-19改回，2015-06-08網(wǎng)絡(luò)優(yōu)先出版

國(guó)家自然科學(xué)基金(61072140, 61373171)，高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金(20100203110003)，高等學(xué)校創(chuàng)新引智計(jì)劃項(xiàng)目(B08038)，“十二五”國(guó)家密碼發(fā)展基金(MMJJ201401003)和華為技術(shù)有限公司合作項(xiàng)目(YB2013120005)資助課題

楊孝鵬： 男，1986年生，博士生，研究方向?yàn)楦衩艽a.

馬文平： 男，1965年生，博士，教授，博士生導(dǎo)師，研究方向?yàn)橥ㄐ爬碚?、糾錯(cuò)碼和信息安全等.

張成麗： 女，1985年生，博士生，研究方向?yàn)楦衩艽a.