A Study On Code-based Digital Signatures

Cryptology is an important technology to protect the security of cyberspace.The security of classical cryptographic algorithms,e.g.,RSA and ECDSA,is based on the traditional hard problems such as the factoring large integers and the solving discrete logarithm.With the rapid development of quantum computing theory and practice,the security of cryptographic algorithms based on traditional hard problems is uncertain.It has become a consensus in academia and industry to study quantum-resistant cryptographic algorithms.Code-based hard problems,including the syndrome decoding problem and the generic decoding problem,are wellrecognized quantum-resistant NP-complete problems.As a result,designing secure and efficient cryptographic algorithms by code-based hard problems is an important part of quantum-resistant cryptography.After a long-term research,code-based encryption algorithms and key exchange protocols have made positive progress,but the Code-Based Digital Signatures Schemes(CBDS)still have the shortcomings such as the large signature and public key sizes,the low efficiency,and the weak security.In this paper,several novel Code-Based Identification Schemes(CBID)are designed to improve the shortcomings of CBDS by the way of “Identification Protocol ? Fiat-Shamir Paradigm ? Digital Signature”.The results are as follows:1.Designs two new CBID schemes,including,HGDMR and RGDMR,and proposes two CBDS schemes based on the generic decoding problem by Fiat-Shamir Paradigm.For the 128-bit security,both two CBDS schemes enjoy the shorter signature size.When compared with CBDS based on rank metric Stern(PQCRYPTO 2011),CBDS based on RGDMR features the comparable computation cost,and the signature size(around 46 KB)is about 25% improvement.2.To further reduce signature size,proposes a rank metric variant of AGS,called RAGS,and proposes CBDS based on the generic decoding problem by FiatShamir Paradigm.For the 128-bit security,when compared with CBDS based on rank metric Stern(PQCRYPTO 2011),CBDS based on RAGS features the comparable computation cost,and the signature size(around 34 KB)is about 44% improvement.3.Improves the Durandal scheme(EUROCRYPT 2019)and proposes a more secure and efficient Durandal(?) scheme with the smaller signature and public key sizes.The security of Durandalis based on the more robust rank syndrome decoding problem,instead of the rank support learning problem(slow growth in complexity).For the 128-bit security,Durandal(?) enjoys about 92%,33%,30%,69%,and 21% improvements for key generation,signature generation,verification,public key(5 KB),and signature(3 KB),respectively.This paper improves the performance and security of the CBDS schemes;enriches the design of code-based cryptographic algorithms;provides the theory and technique for the protection of cyberspace security in the quantum era.