Research And Application Of Lattice-based Public Key Cryptography

Quantum computing has posed a great treat to the security of traditional public-key cryptosystems based on large integer factorization or discrete logarithm problems, the design of cryptosystem based on new hard problems is more important than ever. Based on the study of lattice-based cryptosystems, homomorphic encryption and lattice reduction algorithm, the main contributions are as follows:Firstly, two modified schemes based on the properties of NTRU can’t provide perfect decryption are analyzed, compensating algorithm can be attributed to the original decryption algorithm, and it can’t solve the problem. The plaintext can be recovered from Li’s method by several calculations. Through the analysis of the properties of the encrypted random polynomial, a improved scheme is proposed. This scheme not only can prevent the defects of the two modified schemes, solve the decryption failure of NTRU, but also guarantee the same security as NTRU.Secondly, through the analysis of NTRU, its homomorphism characters, which include additive and mixed homomorphism, are pointed out and proved. Using these characters, a two-party secure computing protocol is proposed. Its security is based on NTRU, and it is faster than the traditional protocols which based on RSA and ECC. The main innovation is that it can prevent the two communicating people cheating the other one, so it is much better than the semi-honest model. Then it is improved to a secure multi-computation protocol.Finally, the actualities of the attacks on backpack system, RSA and NTRU by using lattice ruduction are analysised and summarized. A method of lattice construction for special RSA system is presented, and the feasibility of message recovery by using lattice reduction is proved. Combined with the construction of CS lattice, a special lattice which contains the random encrypted polynomial is improved, and also the correctness is proved.