基于低密度生成矩陣碼的簽密方案

劉明燁　韓益亮　楊曉元

摘要：

基于編碼的密碼系統(tǒng)具備抵抗量子計(jì)算的天然優(yōu)勢，是后量子密碼時(shí)代的重要研究內(nèi)容。針對傳統(tǒng)的基于Goppa碼構(gòu)造的密碼方案存在密文擴(kuò)展率大和密鑰量大的問題，利用低密度生成矩陣 （LDGM） 碼和哈希函數(shù)構(gòu)造了一個(gè)可證明安全的簽密方案。LDGM碼的生成矩陣是稀疏的，能有效減小數(shù)據(jù)量，哈希函數(shù)計(jì)算效率很高。方案滿足隨機(jī)預(yù)言機(jī)下的適應(yīng)性選擇密文攻擊下的不可區(qū)分性（INDCCA2）和選擇消息攻擊下存在性不可偽造（EUFCMA）安全。在保證數(shù)據(jù)機(jī)密性和完整性的同時(shí)，與傳統(tǒng)的先簽名后加密的方法相比，輸出密文總量減少了25%；與“一石二鳥”和SCS簽密方案相比，計(jì)算效率有較大提高。

關(guān)鍵詞：

簽密；后量子密碼； 基于編碼的密碼系統(tǒng)；低密度奇偶檢驗(yàn)碼；可證明安全

中圖分類號：

TP309

文獻(xiàn)標(biāo)志碼：A

Abstract：

Codebased cryptography has natural advantage to resist the attack from quantum computers. Considering the long ciphertext length and the large key size of the traditional Goppacodesbased cryptography， LowDensity GeneratorMatrix （LDGM） code and hash function were used to construct a provably secure signcryption scheme. The generator matrix of LDGM code is sparse， so it can effectively reduce the amount of data， and the hash function is of high computation efficiency. It satisfies INDCCA2 （INDistinguishability under Adaptive Chosen Ciphertext Attacks） and EUFCMA （Existential UnForgeability under Chosen Message Attacks） security under random oracle model. As it guarantees data confidentiality and integrality， the ciphertext is reduced by 25% compared with the traditional case of “sign then encrypt”； compared with the “two birds one stone” and the SCS signcryptions， its computational efficiency gets significant improvement.

英文關(guān)鍵詞Key words：

signcryption； post quantum cryptography； codebased cryptography； LowDensity GeneratorMatrix （LDGM） code； provably secure

0引言

現(xiàn)在廣泛使用的密碼方案，如RSA（RivestShamirAdleman）、Elgamal、橢圓曲線數(shù)字簽名算法（Elliptic Curve Digital Signature Algorithm， ECDSA），容易受到量子計(jì)算機(jī)的攻擊威脅，使用其他密碼系統(tǒng)代替現(xiàn)有的公鑰密碼系統(tǒng)已經(jīng)非常迫切。在眾多的抗量子密碼體制中，基于編碼的公鑰密碼體制被認(rèn)為是最有希望的方案之一。

McEliece公鑰密碼[1]是第一個(gè)基于編碼的公鑰密碼體制，其安全性依賴于編碼學(xué)當(dāng)中的一般譯碼問題，這是一個(gè)NPC（Nondeterministic Polynomial Completeness）問題。與RSA方案相比，該密碼體制能抵抗量子計(jì)算機(jī)攻擊而且加解密速度快；但該方案也有很明顯的弱點(diǎn)，一是它的公鑰量太大，二是其信息率較低，大約只有50%[2]。

針對原始McEliece體制的弱點(diǎn)，為了推動基于編碼密碼體制的應(yīng)用，密碼學(xué)家在減少M(fèi)cEliece密碼的公鑰量方面作了很多嘗試。一個(gè)可行的辦法是使用其他的編碼代替原始方案中的Goppa碼，其中低密度奇偶檢驗(yàn)（LowDensity ParityCheck，LDPC）碼受到了較多的關(guān)注[3-5]。

隨著量子計(jì)算機(jī)的快速發(fā)展，廣泛使用的數(shù)字簽名算法（Digital Signature Algorithm， DSA）簽名和RSA簽名也變得不安全，目前替代方案較少，例如基于哈希函數(shù)的簽名。基于編碼的簽名是另一個(gè)能代替DSA簽名和RSA簽名的抗量子簽名方案，目前高效的基于編碼的簽名方案較少，所以具有較大的研究空間。

2013年，Baldi提出了一個(gè)基于LDGM碼的簽名方案[6]，在這之前，基于編碼的簽名方案主要是CFS簽名[7]及其相應(yīng)的延伸方案。該方案具有易于實(shí)現(xiàn)和公鑰量低的優(yōu)點(diǎn)，克服了CFS簽名方案的兩個(gè)弱點(diǎn)：一是難于實(shí)現(xiàn)，即對于任意一個(gè)哈希值，把它作為一個(gè)伴隨式不一定能譯出相應(yīng)的錯誤向量作為數(shù)字簽名；二是簽名的公鑰量太大。

然而，Baldi提出的這個(gè)簽名方案并不是可證明安全的。本文對基于LDGM碼簽名方案的密鑰進(jìn)行改造，并結(jié)合簽密理論，提出了一個(gè)可證明安全的基于LDGM碼的簽密方案。安全性分析表明，方案滿足隨機(jī)預(yù)言模型下的適應(yīng)性選擇密文攻擊下的不可區(qū)分性（INDistinguishability under Adaptive Chosen Ciphertext Attacks， INDCCA2）安全和選擇消息攻擊下存在性不可偽造（Existential UnForgeability under Chosen Message Attacks， EUFCMA）安全，并且密文量和公鑰量比傳統(tǒng)的“先加密后簽名”有較大的下降。

因此，敵手偽造簽名的概率受到挑戰(zhàn)者求解伴隨式譯碼問題的限制，這意味著只要相應(yīng)的伴隨式譯碼問題是難以求解的，簽名是不可偽造的，即滿足EUFCMA安全。

4效率分析

本方案使用低密度生成矩陣碼（LDGM）進(jìn)行簽名，能同時(shí)保證消息的機(jī)密性和完整性，比傳統(tǒng)的先簽名后加密的方法效率更高。簽密方案的設(shè)計(jì)主要在于其中的簽名部分，本方案的簽名部分使用的是LDGM碼，與使用Goppa碼的CFS簽名相比，可以直接譯碼，不需要多次嘗試即可譯出相應(yīng)的錯誤向量作為簽名；而且密鑰量得到了很大的降低，簽密在保證機(jī)密性和可認(rèn)證性方面使用的是相同的一個(gè)密鑰對，可以減少先簽名后加密帶來的密鑰量增加。

1）簽名計(jì)算復(fù)雜度。

簽名的基本思路是將明文的哈希值當(dāng)作一個(gè)伴隨式（校驗(yàn)子），對其進(jìn)行譯碼，找出相對應(yīng)的錯誤向量，將其作為簽名。由于CFS簽名方案使用的是Goppa碼，因此平均需要進(jìn)行t！次譯碼嘗試，才能找到可譯碼的伴隨式，而本簽名方案使用基于LDGM碼的簽名算法，對任意的伴隨式都可以直接譯出相對應(yīng)的錯誤向量，因此，僅需進(jìn)行1次譯碼操作。

2）數(shù)據(jù)量。

在CFS簽名方案中，為了使偽造攻擊的計(jì)算復(fù)雜度達(dá)到O（280），需要使用的Goppa碼碼長為n=221，校驗(yàn)位r=21×10=210，于是每位用戶的公鑰量為1152KB[6]；而在本方案中，為了達(dá)到相同的安全級別，每位用戶所需要的公鑰的公鑰量為117KB[6]。因此，本方案的數(shù)據(jù)量大大減少。

目前在基于編碼的密碼體系中，為了同時(shí)保證消息機(jī)密性和完整性，所使用的是先簽名后加密的方法，即先使用CFS簽名再使用McEliece加密。表1是就數(shù)據(jù)量進(jìn)行比較的結(jié)果。

上述方案中，哈希運(yùn)算的計(jì)算量很小，運(yùn)算量主要集中在模指數(shù)運(yùn)算、對稱加解密和矩陣乘法運(yùn)算上。在計(jì)算機(jī)上，矩陣運(yùn)算速度要遠(yuǎn)遠(yuǎn)高于模冪運(yùn)算。若選取（524，1024）的矩陣，冪為16、模為1024b的模指數(shù)，矩陣乘法運(yùn)算量約為模指數(shù)的1/47。因此，本方案比“一石二鳥”和SCS方案[13]計(jì)算效率更高。

5結(jié)語

基于編碼的公鑰密鑰具有抗量子攻擊的特性， 量子計(jì)算機(jī)的快速發(fā)展使它備受關(guān)注。本文的基于LDGM碼的簽密方案是在隨機(jī)預(yù)言機(jī)模型下構(gòu)造的，計(jì)算機(jī)復(fù)雜度和數(shù)據(jù)量有大幅度的降低。但是，設(shè)計(jì)出標(biāo)準(zhǔn)模型下可證明安全的方案是運(yùn)用方案的必要條件。并且，基于編碼的密碼體制將信道編碼和加密緊密結(jié)合在一起，與通信技術(shù)有本質(zhì)的聯(lián)系，如何在標(biāo)準(zhǔn)模型下設(shè)計(jì)可證明安全的簽密方案，并應(yīng)用到移動智能設(shè)備上是值得研究的課題。

參考文獻(xiàn)：

[1]

MCELIECE R J. A publickey cryptosystem based on algebraic coding theory [J]. Coding Thv， 1978， 4244： 114-116.

MCELIECE R J. A publickey cryptosystem based on algebraic coding theory [EB/OL]. [20151024]. https：//www.cs.colorado.edu/～jrblack/class/csci7000/f03/papers/mceliece.pdf.

[2]

BALDI M. QCLDPC codebased cryptosystems [M]// BALDI M. QCLDPC Codebased Cryptography. Berlin： Springer， 2014： 91-117.

[3]

GEORGIEVA M， DE PORTZAMPARC F. Toward secure implementation of McEliece decryption [C]// MANGARD S， POSCHMANN A Y. Constructive SideChannel Analysis and Secure Design， LNCS 9064. Berlin： Springer， 2015： 141-156.

[4]

張穎，岳殿武.基于代數(shù)幾何碼的公鑰密碼體制[J].通信學(xué)報(bào)，2008，29（6）：75-81.（ZHANG Y， YUE D W. Public key cryptography based on algebraic geometric codes [J]. Journal on Communications， 2008， 29（6）： 75-81.）

[5]

BALDI M， BIANCHI M， MATURO N， et al. Improving the efficiency of the LDPC codebased McEliece cryptosystem through irregular codes [C]// Proceedings of the 2013 IEEE Symposium on Computers and Communications. Washington， DC： IEEE Computer Society， 2013： 197-202.

[6]

BALDI M， BIANCHI M， CHIARALUCE F， et al. Using LDGM codes and sparse syndromes to achieve digital signatures [C]// GABORIT P. PostQuantum Cryptography， LNCS 7932. Berlin： Springer， 2013： 1-15.

[7]

COURTOIS N T， FINIASZ M， SENDRIER N. How to achieve a McEliecebased digital signature scheme [C]// BOYD C. Advances in Cryptology—ASIACRYPT 2001， LNCS 2248. Berlin： Springer， 2001： 157-174.

[8]

BERLEKAMP E R， MCELIECE R J， VAN TILBORG H C A. On the inherent intractability of certain coding problems [J]. IEEE Transactions on Information Theory， 1978， 24（3）： 384-386.

[9]

CHENG J F， MCELIECE R J. Some highrate near capacity codecs for the Gaussian channel [C]// proceedings of the annual allerton conference on communication control and computing. university of illinois. UNIVERSITY OF ILLINOIS， 1996， 34： 494-503.

CHENG J F， MCELIECE R J. Some highrate near capacity codecs for the Gaussian channel [EB/OL]. [20151114]. http：//xueshu.baidu.com/s？wd=paperuri%3A%282738fdc6421751d8f7b9827de8cdfe23%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Bjsessionid%3DECAFAC735A595F2AB5705FB3150963F3%3Fdoi%3D10.1.1.57.6071%26rep%3Drep1%26type%3Dpdf&ie=utf8&sc_us=13201804057768292757.

CHENG J F， MCELIECE R J. Some highrate near capacity codecs for the Gaussian channel [C]// proceedings of the annual allerton conference on communication control and computing. university of illinois. UNIVERSITY OF ILLINOIS， 1996， 34： 494-503.

[10]

GARCIAFRIAS J， ZHONG W. Approaching Shannon performance by iterative decoding of linear codes with lowdensity generator matrix [J]. IEEE Communications Letters， 2003， 7（6）： 266-268.

[11]

GONZLEZLPEZ M， VAZQUEZARAUJO F J， CASTEDO L， et al. SeriallyConcatenated LowDensity Generator Matrix （SCLDGM） codes for transmission over AWGN and Rayleigh fading channels [J]. IEEE Transactions on Wireless Communications， 2007， 6（8）： 2753-2758.

[12]

MALONELEE J， MAO W. Two birds one stone： signcryption using RSA [C]// Topics in Cryptology — CTRSA 2003. Berlin： Springer， 2003： 211-226.

[13]

ZHENG Y. Digital signcryption or how to achieve cost （signature & encryption） cost （signature）+ cost （encryption） [C]// Advances in Cryptology—Crypto 97， LNCS 1294. Berlin： Springer， 1997： 165-179.