Research On Encryption Algorithm And Digital Signature Algorithm From Coding Theory

With the research progress of information technology and quantum computing,the computation ability of computing facilities are in high-speed development.Meanwhile,the R&D and manufacturing progress of quantum computer is constantly advancing.Although the existing quantum technology can not support scientists to build true quantum computer.We can estimate the applicable quantum computer,in the high probability,will be applied in our society with the maturity of existing technology and the development of new technology.However,while the quantum computer bring people the massive improvement of computation ability,it also bring some brand new security issues in the existing cryptosystems.Most public-key encryption(PKE)algorithms and digital signature(DS)algorithms used in our society today(e.g.RSA,ElGamal)are based on the difficulty of the number-theoretic problems like factoring problem or the discrete logarithm problem which are generally considered secure at present.However,the traditional numbertheoretic cryptosystems are facing new security challenge with advances in quantum computing.In 1994,Shor presented a quantum attack algorithm that could be used to solve both factorization and discrete logarithm problems in polynomial time with quantum computers.Therefore,constructing new public key cryptography algorithm whose security relies on the hard problems that will remain secure against quantum attacks is a topic of ongoing focus.The hard problems in coding theory,such as general decoding(GD)problem,general syndrome decoding(GSD)problem,have been proved to be NP-complete(NPC).These kinds of NPC problems are generally regarded to be secure under quantum attacks.Hence,code-based PKE algorithms and DS algorithms is one of the potential post-quantum cryptosystem solution.However,the code-based cryptosystem has not been as popular as other number theory-based cryptosystems in today's application environment.The main reason of it is because the size of the public key in code-based cryptosystems is considerably larger.Especially for code-based DS algorithms,most of them suffer from the limitation of a lengthy signing time.To improve these limitations of code-based cryptosystem,this paper has mainly completed the following three aspects of work.· Code-based digital signature algorithms with additional properties: In this part of our work,we propose a novel blind signature algorithm and a ring signature algorithm.The former has the high speed signing phase and the latter has the simple structure.To avoid the lengthy signing time,our blind signature algorithm use a fast syndrome based(FSB)hash function to generate a decodable 2-regular word syndrome.Hence,the signing phase of our algorithm could produce a valid signature with only once decoding process.In the other hand,our ring signature algorithm avoid the N +1 times hash computations in the signing and verify phase and thus makes these phases relatively fast.· Digital signature algorithms which are transformed by the code-based identi-fication protocols: In this part of work,we propose three 5-pass zero-knowledge (ZK)identification protocols,namely: RZK protocol,GZK protocol and CCVA protocol respectively.Then we convert the RZK protocol,GZK protocol and CCVA protocol into a ring signature scheme,a group signature scheme and a blind signature respectively following the idea from the Fait-Shamir's paradigm.This kind of identification based DS algorithm has an advantage: the signing phase doesn't include decoding algorithm so that it has the fast signing speed.In the other hand,the public key in our identification based DS algorithms are relatively small because of using qary parity-check matrix in the algorithm.· An IND-CCA2 secure public key encryption algorithm from rank metric codes:In this part of work,we propose a PKE algorithm from Lau and Tan's PKE algo-rithm(LT scheme),which is using rank metric codes in the algorithm.Our PKE algorithm inheriting the underlying small public key from LT scheme.While improving the security from IND-CPA into IND-CCA2,our PKE algorithm avoid the ciphertext expanding.