無陷門格基簽密方案

路秀華 溫巧燕 王勵成 杜 蛟

?

無陷門格基簽密方案

路秀華*①②溫巧燕②王勵成③杜 蛟④

①(廊坊師范學院數學與信息科學學院 廊坊 065000)②(北京郵電大學網絡與交換技術國家重點實驗室 北京 100876)③(北京郵電大學信息安全中心 北京 100876)④(河南師范大學數學與信息科學學院 新鄉 453007)

現有的格基簽密方案以陷門產生算法和原像取樣算法為核心算法。但是，這兩個算法都很復雜，運算量較大，嚴重影響格基簽密方案的執行效率。該文運用無陷門格基簽名及其簽名壓縮技術，結合基于帶錯學習問題的加密方法，提出第1個基于格理論的、不依賴于陷門產生算法和原像取樣算法的簽密方案。方案在帶錯學習問題和小整數解問題的難解性假設下，達到了自適應選擇密文攻擊下的不可區分性和自適應選擇消息攻擊下的不可偽造性。方案在抗量子攻擊的同時，保證了較高的執行效率。

基于格的密碼學；簽密；無陷門格基簽名；帶錯學習問題；小整數解問題

1 引言

簽密是由文獻[1]提出的基本密碼學原語，可以同時實現信息的機密性和認證性，為信息的安全傳輸，提供最基本的安全保障。在大整數因子分解問題和離散對數問題等傳統數論問題的難解性假設下，已有大量的簽密方案被提出。但是伴隨著文獻[5]提出分解大整數和解決離散對數問題的量子多項式時間算法，以及量子計算機這些年來的飛速發展，我們不得不去探尋能夠抵抗量子算法攻擊的密碼體制。

基于格的密碼學是新興的抗量子密碼，由于其獨特的理論優勢，近二十年來發展迅速。格基密碼目前可以實現絕大部分的密碼學功能，比如認證密鑰交換方案[6]，可撤銷的加密方案[7]等。至于簽密方案，格上的實現已有文獻[8-11]，這些方案都以格中的陷門產生算法和原像取樣算法為基礎，算法的計算復雜度較大。文獻[12]在2012年提出了格中無陷門簽名方案的構造方法，文獻[13]在2014年對其進行了改進，縮短了簽名的長度。本文在文獻[13]的基礎上，構建了一個不需要陷門產生算法和原像取樣算法的格基簽密方案，并以帶錯學習問題和小整數解問題的難解性假設為基礎，結合文獻[14]的轉化方法，證明了方案的自適應選擇密文攻擊下的不可區分性和自適應選擇消息攻擊下的不可偽造性。最后，給出了方案的效率分析，驗證了所構造方案的高效性。

2 簽密的形式化定義

一個簽密方案由3個算法組成：密鑰生成算法，簽密算法，解簽密算法。

3 簽密的安全模型

一個簽密方案必須同時實現信息的機密性和認證性，因此方案的安全性包含兩個方面：(1)自適應選擇密文攻擊下的不可區分性(INDistinguishability against adaptive Chosen Ciphertext Attacks, IND- CCA2); (2)自適應選擇消息攻擊下的不可偽造性(Existential UnForgeability against adaptive Chosen Message Attacks, EUF-CMA)。

3.1 IND-CCA2安全性

簽密方案的IND-CCA2安全性由下面的游戲來描述，游戲由挑戰者和敵手交互完成。

定義1 一個簽密方案是IND-CCA2安全的，如果每個多項式有界的敵手在上述游戲中的優勢都是可忽略的。特別地，如果在上述游戲中不允許敵手進行解簽密查詢，則簽密方案具有選擇明文攻擊下的不可區分性(INDistinguishability against Chosen Plaintext Attacks, IND-CPA)。

3.2 EUF-CMA安全性

定義2 簽密方案是EUF-CMA安全的，如果每個多項式有界的敵手在上述游戲中的優勢都是可忽略的。

4 無陷門格基簽密方案1

(1) 系統設置：

(2)密鑰生成算法：

4.1方案1的正確性

4.2方案1的IND-CPA安全性

定理1 方案1 以LWE問題的難解性為基礎，達到了IND-CPA安全性。

證明 我們給出一個游戲序列。

G0是IND-CPA安全性定義中的游戲。

G1在G0的基礎上，將挑戰者生成的挑戰密文中的改為對稱加密算法密文空間中一個均勻隨機選取的。

G2在G1的基礎上，將挑戰者生成的挑戰密文中的改為中的隨機值。

G3在G2的基礎上，將挑戰者生成的挑戰密文中的改為中的隨機值。

在G3的挑戰密文中，,,都是各自取值空間中的隨機值，此時挑戰密文中已經不再含有關于明文的任何信息，因此敵手猜對的優勢為零。

由G3和G0的計算不可區分性，在G0中，敵手猜對的優勢是可以忽略的，所以方案1是IND- CPA安全的。

證畢

5 無陷門格基簽密方案2

為了使無陷門格基簽密方案達到IND-CCA2安全性，我們采用文獻[14]的轉化方法，在方案1的基礎上構建了無陷門格基簽密方案2。由方案1的IND-CPA安全性和文獻[14]的結論，方案2是IND- CCA2安全的。方案2描述如下：

(1)系統設置

(2)密鑰生成算法：

5.1 方案2的正確性

5.2方案2的IND-CCA2安全性

定理2 方案2以判定性LWE問題的難解性為基礎，達到了IND-CCA2安全性。

(1)服從均勻分布。

證畢

5.3方案2的EUF-CMA安全性

定理3 方案2以SIS問題的難解性為基礎，達到了EUF-CMA安全性。

證畢

5.4方案2的效率分析

表1與文獻[10]的效率對比

6 結束語

陷門產生算法和原像取樣算法的計算復雜度是影響格基密碼實用性的重要因素。本文提出的格基簽密方案，使用了無陷門簽名技術和基于LWE問題的加密方法，避免了陷門產生算法和原像取樣算法的使用，提高了方案的運算效率，高效地保證了量子計算機環境下信息傳輸的機密性和認證性。在本文方案的基礎上研究代理簽密，多接收者簽密，聚合簽密等具有特殊應用需求的高效簽密方案的設計，將是下一步的研究內容。

[1] ZHENG Y. Digital signcryption or how to achieve cost (signature+encryption)<

[2] MALONE-LEE J and MAO W. Two birds one stone: signcryption using rsa[C]. Proceedings of the 2003 RSA conference on The Cryptographers’ track, San Francisco, USA, 2003: 211-226.

[3] LI Fagen and TAKAGI T. Secure identity-based signcryption in the standard model[J]., 2013, 57(11/12): 2685-2694.

[4] LU Y and LI J. Efficient certificate-based signcryption secure against public key replacement attacks and insider attacks[J]., 2014, Article ID 295419.

[5] Shor P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]., 1997, 26(5): 1484-1509.

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

YANG Xiaopeng, MA Wenping, and ZHANG Chengli. New authenticated key exchange scheme based on ring learning with errors problem[J].&, 2015, 37(8): 1984-1988.

[7] 張彥華, 胡予濮, 江明明, 等. 格上可撤銷的基于身份的適應性安全的加密方案[J]. 電子與信息學報, 2015, 37(2): 423-428.

ZHANG Yanhua, HU Yupu, JIANG Mingming,. A lattice-based revocable adaptive-id secure encryption scheme [J].&, 2015, 37(2): 423-428.

[8] WANG Fenghe, HU Yupu, and WANG Chunxiao. Post- quantum secure hybrid signcryption from lattice assumption[J].&, 2012, 6(1): 23-28.

[9] LI Fagen, BIN MUHAVA F T, KHAN M K,. Lattice-based signcryption[J]., 2013, 25(14): 2112-2122.

[10] YAN Jianhua, WANG Licheng, YANG Yixian,. Efficient lattice-based signcryption in standard model[J]., 2013, Article ID 702539.

[11] LU Xiuhua, WEN Qiaoyan, JIN Zhengping,. A lattice- based signcryption scheme without random oracles[J]., 2014, 8(4): 667-675.

[12] LYUBASHEVSKY V. Lattice signatures without trapdoors [C]. EUROCRYPT 2012, Cambridge, USA, 2012: 738-755.

[13] BAI Shi and GALBRAITH S D. An improved compression technique for signatures based on learning with errors[C]. CT-RSA 2014, San Francisco, USA, 2014: 28-47.

[14] FUJISAKI E and OKAMOTO T. Secure integration of asymmetric and symmetric encryption schemes[J]., 2013, 26(1): 80-101.

[15] BELLARE M and NEVEN G. Multi-signatures in the plain public-key model and a general forking lemma[C]. Proceedings of the 13th ACM Conference on Computer and Communications Security, Alexandria, USA, 2006: 390-399.

A Lattice-based Signcryption Scheme Without Trapdoors

LU Xiuhua①②WEN Qiaoyan②WANG Licheng③DU Jiao④

①(Faculty of Mathematics and Information Science, Langfang Teachers University, Langfang 065000, China)②(State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China)③(Information Security Center, Beijing University of Posts and Telecommunications, Beijing 100876, China)④(College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China)

The existing lattice-based signcryption schemes are based on trapdoor generation algorithm and preimage sample algorithm. However, both algorithms are complex, require a lot of time to run, and affect the efficiency of latticed-based signcryption schemes deeply. To solve this problem, the first lattice-based signcryption scheme without trapdoor generation algorithm and preimage sample algorithm is proposed, with the help of the technique of lattice signatures without trapdoors and the associated signature compression technique, as well as the encryption method based on the learning with errors assumption. The scheme achieves indistinguishability against adaptive chosen ciphertext attacks under the learning with errors assumption. It also achieves existential unforgeability against adaptive chosen message attacks under the small integer solution assumption. The proposed scheme is not only quantum resistant, but also efficient.

Lattice-based cryptography; Signcryption; Lattice signatures without trapdoors; Learning with errors problem; Small integer solution problem

TP309

A

1009-5896(2016)09-2287-07

10.11999/JEIT151044

2015-09-14；

2016-06-27；

2016-08-09

國家自然科學基金(61300181, 61502044, 61402015, U1404601, 11471104)，中央高校基本科研業務費專項資金 (2015RC23)，河北省教育廳青年基金(QN2015084)，廊坊市科技局項目(2015011063)，廊坊師范學院博士基金(LSLB201408)

The National Natural Science Foundation of China (61300181, 61502044, 61402015, U1404601, 11471104), The Fundamental Research Funds for the Central Universities (2015RC23), Hebei Province Education Funds for Youth Project (QN2015084), Langfang Municipal Science and Technology Support Program (2015011063), Langfang Teachers University Doctor Funds (LSLB201408)

路秀華 luxiuhua2014@sina.cn

路秀華： 女，1979年生，副教授，博士生，研究方向為基于格的公鑰密碼學.

溫巧燕： 女，1959年生，教授，研究方向為密碼學和信息安全.

王勵成： 男，1971年生，副教授，研究方向為密碼學和網絡安全.

杜 蛟： 男，1978年生，講師，博士，研究方向為密碼學與應用數學.