Computer Science ›› 2017, Vol. 44 ›› Issue (3): 168-174.doi: 10.11896/j.issn.1002-137X.2017.03.037

Previous Articles     Next Articles

Improved Veron’s Identification with Lightweight Structure and Digital Signature Scheme

YE Jun-yao, ZHENG Dong and REN Fang   

  • Online:2018-11-13 Published:2018-11-13

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

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

No related articles found!
Full text



No Suggested Reading articles found!