基于低密度生成矩阵码的签密方案

刘明烨　韩益亮　杨晓元

摘要：

基于編码的密码系统具备抵抗量子计算的天然优势，是后量子密码时代的重要研究内容。针对传统的基于Goppa码构造的密码方案存在密文扩展率大和密钥量大的问题，利用低密度生成矩阵 （LDGM） 码和哈希函数构造了一个可证明安全的签密方案。LDGM码的生成矩阵是稀疏的，能有效减小数据量，哈希函数计算效率很高。方案满足随机预言机下的适应性选择密文攻击下的不可区分性（INDCCA2）和选择消息攻击下存在性不可伪造（EUFCMA）安全。在保证数据机密性和完整性的同时，与传统的先签名后加密的方法相比，输出密文总量减少了25%；与“一石二鸟”和SCS签密方案相比，计算效率有较大提高。

关键词：

签密；后量子密码； 基于编码的密码系统；低密度奇偶检验码；可证明安全

中图分类号：

TP309

文献标志码：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.

英文关键词Key words：

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

0引言

现在广泛使用的密码方案，如RSA（RivestShamirAdleman）、Elgamal、椭圆曲线数字签名算法（Elliptic Curve Digital Signature Algorithm， ECDSA），容易受到量子计算机的攻击威胁，使用其他密码系统代替现有的公钥密码系统已经非常迫切。在众多的抗量子密码体制中，基于编码的公钥密码体制被认为是最有希望的方案之一。

McEliece公钥密码[1]是第一个基于编码的公钥密码体制，其安全性依赖于编码学当中的一般译码问题，这是一个NPC（Nondeterministic Polynomial Completeness）问题。与RSA方案相比，该密码体制能抵抗量子计算机攻击而且加解密速度快；但该方案也有很明显的弱点，一是它的公钥量太大，二是其信息率较低，大约只有50%[2]。

针对原始McEliece体制的弱点，为了推动基于编码密码体制的应用，密码学家在减少McEliece密码的公钥量方面作了很多尝试。一个可行的办法是使用其他的编码代替原始方案中的Goppa码，其中低密度奇偶检验（LowDensity ParityCheck，LDPC）码受到了较多的关注[3-5]。

随着量子计算机的快速发展，广泛使用的数字签名算法（Digital Signature Algorithm， DSA）签名和RSA签名也变得不安全，目前替代方案较少，例如基于哈希函数的签名。基于编码的签名是另一个能代替DSA签名和RSA签名的抗量子签名方案，目前高效的基于编码的签名方案较少，所以具有较大的研究空间。

2013年，Baldi提出了一个基于LDGM码的签名方案[6]，在这之前，基于编码的签名方案主要是CFS签名[7]及其相应的延伸方案。该方案具有易于实现和公钥量低的优点，克服了CFS签名方案的两个弱点：一是难于实现，即对于任意一个哈希值，把它作为一个伴随式不一定能译出相应的错误向量作为数字签名；二是签名的公钥量太大。

然而，Baldi提出的这个签名方案并不是可证明安全的。本文对基于LDGM码签名方案的密钥进行改造，并结合签密理论，提出了一个可证明安全的基于LDGM码的签密方案。安全性分析表明，方案满足随机预言模型下的适应性选择密文攻击下的不可区分性（INDistinguishability under Adaptive Chosen Ciphertext Attacks， INDCCA2）安全和选择消息攻击下存在性不可伪造（Existential UnForgeability under Chosen Message Attacks， EUFCMA）安全，并且密文量和公钥量比传统的“先加密后签名”有较大的下降。

因此，敌手伪造签名的概率受到挑战者求解伴随式译码问题的限制，这意味着只要相应的伴随式译码问题是难以求解的，签名是不可伪造的，即满足EUFCMA安全。

4效率分析

本方案使用低密度生成矩阵码（LDGM）进行签名，能同时保证消息的机密性和完整性，比传统的先签名后加密的方法效率更高。签密方案的设计主要在于其中的签名部分，本方案的签名部分使用的是LDGM码，与使用Goppa码的CFS签名相比，可以直接译码，不需要多次尝试即可译出相应的错误向量作为签名；而且密钥量得到了很大的降低，签密在保证机密性和可认证性方面使用的是相同的一个密钥对，可以减少先签名后加密带来的密钥量增加。

1）签名计算复杂度。

签名的基本思路是将明文的哈希值当作一个伴随式（校验子），对其进行译码，找出相对应的错误向量，将其作为签名。由于CFS签名方案使用的是Goppa码，因此平均需要进行t！次译码尝试，才能找到可译码的伴随式，而本签名方案使用基于LDGM码的签名算法，对任意的伴随式都可以直接译出相对应的错误向量，因此，仅需进行1次译码操作。

2）数据量。

在CFS签名方案中，为了使伪造攻击的计算复杂度达到O（280），需要使用的Goppa码码长为n=221，校验位r=21×10=210，于是每位用户的公钥量为1152KB[6]；而在本方案中，为了达到相同的安全级别，每位用户所需要的公钥的公钥量为117KB[6]。因此，本方案的数据量大大减少。

目前在基于编码的密码体系中，为了同时保证消息机密性和完整性，所使用的是先签名后加密的方法，即先使用CFS签名再使用McEliece加密。表1是就数据量进行比较的结果。

上述方案中，哈希运算的计算量很小，运算量主要集中在模指数运算、对称加解密和矩阵乘法运算上。在计算机上，矩阵运算速度要远远高于模幂运算。若选取（524，1024）的矩阵，幂为16、模为1024b的模指数，矩阵乘法运算量约为模指数的1/47。因此，本方案比“一石二鸟”和SCS方案[13]计算效率更高。

5结语

基于编码的公钥密钥具有抗量子攻击的特性， 量子计算机的快速发展使它备受关注。本文的基于LDGM码的签密方案是在随机预言机模型下构造的，计算机复杂度和数据量有大幅度的降低。但是，设计出标准模型下可证明安全的方案是运用方案的必要条件。并且，基于编码的密码体制将信道编码和加密紧密结合在一起，与通信技术有本质的联系，如何在标准模型下设计可证明安全的签密方案，并应用到移动智能设备上是值得研究的课题。

参考文献：

[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]

張颖，岳殿武.基于代数几何码的公钥密码体制[J].通信学报，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.