一種新型基于環上帶誤差學習問題的認證密鑰交換方案

楊孝鵬 馬文平 張成麗

?

一種新型基于環上帶誤差學習問題的認證密鑰交換方案

楊孝鵬*馬文平 張成麗

(西安電子科技大學綜合業務網及關鍵技術國家重點實驗室 西安 710071)

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

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

1 引言

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

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

2 預備知識

2.1符號說明

2.2格上亞高斯變量

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

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

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

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

2.3代數整數環上格的抽樣

2.4困難問題

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

引理3[4]設，向量，分布與分布統計距離至多為。

2.5 安全模型

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

2.6調和技術

調和函數定義請參見文獻[11]。

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

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

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

3 方案

3.1方案描述

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

3.2正確性

3.3參數選取

3.4效率比較

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

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

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

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

4 安全分析

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

1,1這個游戲和1,0基本相同，下述情況除外：抽取，計算，選取，計算，選取，計算，依據協議規范地計算，并發送給。

1,2這個游戲和1,1基本相同，下述情況除外：選取，計算，選取，設置，依據協議規范地計算和。

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

1,2中替換為1,3中的隨機值。設和是兩個Ring-LWE挑戰組。構造求解Ring-LWE問題的區分器,設置,,，選取，計算，設置，依據協議規范計算。另外，選取，設置，發送給。若是困難問題，則

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

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

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

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

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

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

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

5 結束語

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

參考文獻

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

完善的知識產權管理體系對“三農”產業的發展和保護具有重要意義，能夠推動企業不斷發展升級，從而產生經濟效益。通過對知識產權的實際運用，使企業能夠充分發揮自身的創新潛力，為企業的健康可持續發展奠定堅實基礎。

[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網絡優先出版

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

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

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

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