路秀華 溫巧燕 王勵(lì)成 杜 蛟

?

無陷門格基簽密方案

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

①(廊坊師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院 廊坊 065000)②(北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100876)③(北京郵電大學(xué)信息安全中心 北京 100876)④(河南師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院 新鄉(xiāng) 453007)

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

基于格的密碼學(xué)；簽密；無陷門格基簽名；帶錯(cuò)學(xué)習(xí)問題；小整數(shù)解問題

1 引言

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

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

2 簽密的形式化定義

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

3 簽密的安全模型

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

3.1 IND-CCA2安全性

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

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

3.2 EUF-CMA安全性

定義2 簽密方案是EUF-CMA安全的，如果每個(gè)多項(xiàng)式有界的敵手在上述游戲中的優(yōu)勢(shì)都是可忽略的。

4 無陷門格基簽密方案1

(1) 系統(tǒng)設(shè)置：

(2)密鑰生成算法：

4.1方案1的正確性

4.2方案1的IND-CPA安全性

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

證明 我們給出一個(gè)游戲序列。

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

G1在G0的基礎(chǔ)上，將挑戰(zhàn)者生成的挑戰(zhàn)密文中的改為對(duì)稱加密算法密文空間中一個(gè)均勻隨機(jī)選取的。

G2在G1的基礎(chǔ)上，將挑戰(zhàn)者生成的挑戰(zhàn)密文中的改為中的隨機(jī)值。

G3在G2的基礎(chǔ)上，將挑戰(zhàn)者生成的挑戰(zhàn)密文中的改為中的隨機(jī)值。

在G3的挑戰(zhàn)密文中，,,都是各自取值空間中的隨機(jī)值，此時(shí)挑戰(zhàn)密文中已經(jīng)不再含有關(guān)于明文的任何信息，因此敵手猜對(duì)的優(yōu)勢(shì)為零。

由G3和G0的計(jì)算不可區(qū)分性，在G0中，敵手猜對(duì)的優(yōu)勢(shì)是可以忽略的，所以方案1是IND- CPA安全的。

證畢

5 無陷門格基簽密方案2

為了使無陷門格基簽密方案達(dá)到IND-CCA2安全性，我們采用文獻(xiàn)[14]的轉(zhuǎn)化方法，在方案1的基礎(chǔ)上構(gòu)建了無陷門格基簽密方案2。由方案1的IND-CPA安全性和文獻(xiàn)[14]的結(jié)論，方案2是IND- CCA2安全的。方案2描述如下：

(1)系統(tǒng)設(shè)置

(2)密鑰生成算法：

5.1 方案2的正確性

5.2方案2的IND-CCA2安全性

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

(1)服從均勻分布。

證畢

5.3方案2的EUF-CMA安全性

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

證畢

5.4方案2的效率分析

表1與文獻(xiàn)[10]的效率對(duì)比

6 結(jié)束語

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

[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] 楊孝鵬, 馬文平, 張成麗. 一種新型基于環(huán)上帶誤差學(xué)習(xí)問題的認(rèn)證密鑰交換方案[J]. 電子與信息學(xué)報(bào), 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] 張彥華, 胡予濮, 江明明, 等. 格上可撤銷的基于身份的適應(yīng)性安全的加密方案[J]. 電子與信息學(xué)報(bào), 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

國(guó)家自然科學(xué)基金(61300181, 61502044, 61402015, U1404601, 11471104)，中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金 (2015RC23)，河北省教育廳青年基金(QN2015084)，廊坊市科技局項(xiàng)目(2015011063)，廊坊師范學(xué)院博士基金(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年生，副教授，博士生，研究方向?yàn)榛诟竦墓€密碼學(xué).

溫巧燕： 女，1959年生，教授，研究方向?yàn)槊艽a學(xué)和信息安全.

王勵(lì)成： 男，1971年生，副教授，研究方向?yàn)槊艽a學(xué)和網(wǎng)絡(luò)安全.

杜 蛟： 男，1978年生，講師，博士，研究方向?yàn)槊艽a學(xué)與應(yīng)用數(shù)學(xué).