楊孝鵬 馬文平 張成麗

?

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

楊孝鵬*馬文平 張成麗

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

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

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

1 引言

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

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

2 預(yù)備知識

2.1符號說明

2.2格上亞高斯變量

定義1[10]對于,，若滿足，則稱上隨機變量是標準偏差為的-亞高斯變量。由馬爾科夫不等式得：，有

事實1[10]若是-亞高斯變量，標準偏差為,是-亞高斯變量，標準偏差為。與相互獨立，則是-亞高斯變量，標準偏差為。

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

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

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

2.4困難問題

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

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

2.5 安全模型

安全模型定義請參見文獻[13]。

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

調(diào)和函數(shù)定義請參見文獻[11]。

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

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

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

3 方案

3.1方案描述

圖1 基于Ring-LWE的認證密鑰交換方案

3.2正確性

3.3參數(shù)選取

3.4效率比較

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

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

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

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

4 安全分析

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

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

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

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

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

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

2,0這個游戲與情形1中游戲相同。

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

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

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

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

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

5 結(jié)束語

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

參考文獻

[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é)先, 魏江宏, 葉茂, 等. 對一個強安全的認證密鑰交換協(xié)議的分析[J]. 電子與信息學(xué)報, 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.

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

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

楊孝鵬： 男，1986年生，博士生，研究方向為格密碼.

馬文平： 男，1965年生，博士，教授，博士生導(dǎo)師，研究方向為通信理論、糾錯碼和信息安全等.

張成麗： 女，1985年生，博士生，研究方向為格密碼.