改进的具有轻量级结构的Veron身份认证及数字签名方案

doi:10.11896/j.issn.1002-137X.2017.03.037

摘要/Abstract

摘要： 目前大部分的公钥密码方案都基于大整数分解或离散对数难题,这些困难问题在量子计算机中都可以在多项式时间内求解,而基于纠错码的密码方案可以抵抗量子计算机的攻击,所以很有必要研究基于纠错码的身份认证及数字签名方案。Veron身份认证方案总体性能不错,但公钥太大,大约有150k比特。在Veron方案的基础上,采用双循环矩阵来进一步减小Veron方案中的密钥大小,即通过双循环矩阵把私钥嵌入到公钥中。这样做的好处有3点:1)所基于的安全性是已被证明为安全的循环码；2)改进以后,公钥只有1041比特,而私钥也只有1041比特；3)每轮数据的传输量比较少。然后分析所构造方案的安全性,将其归结到GSD困难问题上。最后,采用FS方法将改进后的身份认证方案转换为数字签名方案,并对该方案进行正确性证明和安全性证明。循环结构的使用使得改进方案实现起来比较容易并且效率较高。这些特点使得所提方案在轻量级结构的场合具有广阔的应用前景,比如手持终端、云存储环境下的数字签名等场合。

关键词: 后量子密码,循环码,数字签名,身份认证,纠错码

Abstract: At present,most of the public key cryptography schemes are based on hard problems such as large integer factorization or discrete logarithm.All these hard problems can be solved by a quantum computer in polynomial time.Cryptographic schemes based on error-correcting codes can resist the attacks by a quantum computer,so it is necessary to design identification schemes or signature schemes based on error-correcting codes.Veron’s identification scheme is very nice in general,but it’s public key is too long.Based on Veron’s scheme,we used double circulant matrix to further reduce the size of public key in Veron’s scheme.The secret key is embedded into the public key directly,which has the three following advantages.The security relies on a problem which is related to well-known and well-studied codes,namely the double circulant codes.The size of the public key is very low,only 1041 bits in a typical set-up,and the private key is also 1041bits.The transmission rate of each round is very low.Then we analyzed the security of the improved scheme.Its security can be reduced to GSD hard problem.At last,we used FS paradigm to transform the improved identification scheme into signature scheme,and then proved the correctness and security of the scheme.In the improved scheme,the use of cyclic structure makes it relatively easy to implement and have high efficiency.These chara-cteristics make our variant highly attractive for lightweight implementations,especially in handheld terminal or cloud storage environment.

Key words: Post-quantum cryptography,Cyclic codes,Digital signature,Identification,Error correcting codes

叶君耀,郑东,任方. 改进的具有轻量级结构的Veron身份认证及数字签名方案[J]. 计算机科学, 2017, 44(3): 168-174. https://doi.org/10.11896/j.issn.1002-137X.2017.03.037

YE Jun-yao, ZHENG Dong and REN Fang. Improved Veron’s Identification with Lightweight Structure and Digital Signature Scheme[J]. Computer Science, 2017, 44(3): 168-174. https://doi.org/10.11896/j.issn.1002-137X.2017.03.037

参考文献

[1] ZHAO S R.New Discrete Logarithm Problems over FiniteFields[D].Jinan:Shandong University,2014:14-20,5-50.(in Chinese) 赵书让.有限域上新的离散对数问题[D].济南:山东大学,2014:14-20,5-50.
[2] SHOR P.Polynomial-Time Algorithms For Prime Factorization and Discrete Logarithms on A Quantum Computer[J].Siam Review,1997,41(5):1484-1509.
[3] GERSHENFELD N,CHUANG I.Quantum Computing withMolecules[J].Scientific American,1998,282(6):86-93.
[4] MCELIECE R.A public key cryptosystem based on algebraiccoding theory[J].DSN Progress Report,1978,2(44):114-116.
[5] PATARIN J.Hidden Fields Equations (HFE) and Isomor-phisms of Polynomials (IP):Two New Families of Asymmetric Algorithms[M]∥Advances in Cryptology — EUROCRYPT ’96.Springer Berlin Heidelberg,1996:33-48.
[6] STERN J.A New Identification Scheme Based On Syndrome Decoding[C]∥Crypto’93.1993:13-21.
[7] VERON P.Improved Identification Schemes Based On Error-Correcting Codes[J].Applicable Algebra in Engineering,Communication and Computing,1997,8(1):57-69.
[8] 杨波.现代密码学[M].北京:清华大学出版社,2015:198-199
[9] FIAT A,SHAMIR A.How to Prove Yourself:Practical Solutions to Identification and Signature Problems[C]∥Odlyzko AM(ed) Advances in Cryptology-CRYPTO’86.LNCS,Sprin-ger,Berlin,1987:186-194.
[10] YI H,LI W.Fast Three-Input Multipliers over Small Composite Fields for Multivariate Public Key Cryptography[J].International Journal of Security & Its Applications,2015,9(9):165-178.
[11] GABORIT P.Shorter Seys For The McEliece Cryptosystem[J].Proceedings of WCC,2005,30(6):124-133.
[12] WANG X M.Digital Signature scheme based on error-correcting codes[J].Electronics Letters,1990,26(13):898-899.
[13] ALABBADI M,WICKER S B.Security of Xinmei Digital Signature Scheme[J].Electronics,1992,8(9):890-891.
[14] ALABBADI M,WICKER S B.Digital Signature Scheme Based on Error-Correcting Codes[C]∥IEEE International Symposium on Information Theory.IEEE,1993:9-19.
[15] HARN L,WANG D C.Cryptoanalysis and Modification of Di-gital Signature Scheme Based on Error-Correcting Codes[J].Electronics Letters,1992,8(2):157-159.
[16] KABATIANSKII V,KROUK E,SMEETS B J M.A DigitalSignature Scheme Based on Random Error-Correcting Codes[M]∥Crylography and Coding.Springer Berlin Heidelberg,1997:161-167.
[17] CAYREL P L,OTMANI A,VERGNAUD D.On Kabatianskii-Krouk-Smeets Signatures[M]∥Carlet S C,Sunar B,eds.Arithmetic of Finite Fields.Springer,Heidelberg, 2007:237-251.
[18] COURTOIS N,FINIASZ M,SENDRIER N.How to achieve a McEliece-based digital signature schem[M]∥Advances in cryptology-ASIACRYPT 2001.LNCS,vol 2248,Springer,Berlin,2001:157-174.
[19] DALLOT L.Towards a Concrete Security Proof of Courtois,Finiasz and Sendrier Signature Scheme[M]∥ Research in Cryptology.LNCS 4945,Springer,2007:65-77.
[20] FAUGRE J C,GAUTHIER V,OTMANI A,et al.A distinguisher for high rate mceliece cryptosystems:Report 2010/331[R/OL].http://eprint.iacr.org.
[21] PREETHA M P,VASANT S,R ANGAN C P.On Provably Secure Code based Signature and Signcryption Scheme:Report 2012/585[R].2012.
[22] SIDI M,PIERRE-LOUIS C,RACHID E.Code-Based Identification and Signature Schemes in Software[M]∥ Security Engineering and Intelligence Informatics.Germany,LNCS 8128.2014:122-136.
[23] PIERRE-LOUIS C,VERON P,ALAOUI S.A Zero-Knowledge Identification Scheme Based on The Q-ary Syndrome Decoding Problem[C]∥2013 Eighth Asia Joint Conference on Selected Areas in Cryptography 2011.Berlin:Springer,2013:171-186.
[24] RONG H,MOROZOV K,TAKAGI T.On Zero-KnowledgeIdentification Based on Q-ary Syndrome Decoding[C]∥ 2013 Eighth Asia Joint Conference on Information Security (Asia JCIS).IEEE,2013:12-18.
[25] GABORIT P.Method of authentication using a decoding of an error correcting code on the basis of a public matrix:US,US8817972 [P].2014.
[26] GADAT B,VAN N,RIES L.Method Of Decoding A Correcting Code,For Example A Turbo-code,By Analysis Of The Extended Spectrum Of The Words Of The Code:US,US20140351667[P].2014.
[27] El YOUSFI A.Code-based Identification and Signature Schemes[D].Technische Universitat Darmastadt.2013.
[28] BERLEKAMP E R,MCELIECE R J, TILBORG H C A V.On The Inherent Intractability Of Certain Coding Problems[J].IEEE Transactions on Information Theory,1978,4(3):384-386.
[29] 岳殿武.信息论与编码简明教程[M].清华大学出版社,2015:166-178.
[30] GABORIT P,ZEMOR G.Asymptotic improvement of the Gilbert Varshamov bound for linear codes[J].IEEE Transactions on Information Theory,208,4(9):3865-3872.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed