Research On Lattice-based Public Key Cryptography And Compressed Sensing

In the quantum age, the traditional cryptography system is no longer safe in front of quantum computers. To deal with the threat of quantum computers and ensure the information security , the design of the cryptography against quantum attack is the goal that people pursue.At present, there is no effective algorithm to solve the lattice problem, so it is a hot research topic in the field of post quantum cryptography.As one of the most important tools to resist quantum information,lattice cryptography has become the first choice for information security.The provable security, good application prospect and linear structure of the lattice problem make lattice cryptography become a hot spot in the research of information security. This paper focuses on the research of lattice-based public key encryption system and authenticated key exchange protocols. Meanwhile , the lattice-based compressed sensing is being discussed. In the course of the study, obtain the following results.(1) Construct a lattice-based authenticated key exchange (AKE)on the learning with error problem and prove its security in the BR model. Compared with other AKEs, the proposed lattice-based AKE is the first one without cryptography basic technology based on LWE problem, which has the advantages of little computation resource, higher efficiency, stronger practicability and can resist quantum attack. Based on the learning with error problem , proposes a bilateral learning with error problem (Bi-LWE) and prove its hardness . In addition, also propose the decisional Bi-L WE problem, computational Bi-L WE problem and decisional assumption and computational assumption.(2) Based on the small integer solution ( SIS ) problem, a simple AKE protocol is proposed, and its security is analyzed. In addition, based on the SIS problem, proposed two lattice-based AKE protocols with Hash and propose their securities under the CK model and eCK model respectively. Compared with other AKEs , the computation of the proposed lattice-based AKEs is smaller and their securities are higher.(3) Construct a provably secure public key encryption scheme on SIS problem and prove its CPA security. Compared with other PKEs, the proposed lattice-based PKE has the faster encryption and decryption speed, higher efficiency, stronger practicability and can resist quantum attack. As a result, it broads the research ideas of lattice cryptography.(4) Construct a generalized compressed sensing model with perturbed noise folding, study its RIP and correlation. In addition, give its numerical experiment which indicates its correctness and feasibility.The new CS model provides a new idea for the classical compressed sensing model and broadens CS research scope and field.