Research And Design Of Lattice-based Cryptographic Schemes

Public-key cryptosystems is the main techniques for e-commerce and e-government security. The most common cryptosystems used at present are those systems based on Integer Factoring Problem (IFP) and Discrete Logarithm Problem (DLP) etc, such as RSA cryptosystem etc. In these public-key cryptosystems, most algorithms involve complicated operations, which are less efficient. In addition, there are polynomial quantum algorithms and sub-exponent algorithms that can solve IFP and DLP. More efficient and more secure cryptosystems are needed. In 1996, Ajtai revealed the intriguing possibility of basing cryptography on worst-case complexity assumptions related to lattices. It turned out to be a breakthrough in cryptographic constructions.An n-dimension lattice is a discrete additive subgroup of Rn. Lattice-based cryptographic constructions are based on the presumed hardness of lattice problems, the most basic of which is the shortest vector problem (SVP). Current research and experiment can help us conjecture that there is no polynomial time algorithm that approximates lattice problems to within polynomial factors. The fact that attempts to solve lattice problems by quantum algorithms have met with little success justifies the use of lattice-based cryptography for post-quantum. Lattice-based cryptographic constructions not only hold a great promise for post-quantum cryptography, but also they enjoy very strong security proofs based on worst-case hardness, relatively efficient implementations, as well as great simplicity because of the lattice structure and linearity. So the constructions based on lattice can be expected more efficient than others. In this thesis, we make research on certain cryptographic constructions based on lattice to learn their construction method. At the same time, we design some schemes based on lattice.To construct new lattice-based cryptographic schemes, we first study on basic lattice definitions and properties. We study discrete Gaussian distribution which is applied in lattice research widely. We applied the algorithm SampleD put forward by Gentry into our constructions. The research on the q modular lattice is the basis of our constructions. As the underlying worst-case lattice assumptions are somewhat more subtle, it is difficult to construct schemes directly on them. Most lattice-based cryptosystems are based on average-case hard problems, such as LWE, SIS and ISIS. The hardness of these average hard problems are proved equivalent to the hardness of the worst hard lattice problems. We mainly research a few schemes based on them, including the first cryptosystem based on LWE proposed by Regev, identity-based encryption constructed by Gentry etc., the lossy trapdoor functions based CCA2-secure encryption schemes. The SIS and ISIS based schemes originated from the preimage samplable trapdoor functions defined by Gentry. Gentry etc. constructed signature schemes on the functions collection. Our constructions based on SIS and ISIS are stemmed from the collection. Our research and results are listed as follows.(1) Public-key encryption schemes based on LWE. Regev first proved the equivalence between the hardness of average-case LWE problem and worst-case GapSVP. Based on LWE, Regev presented a single-bit encryption scheme. Through the research on the scheme, we learn how to design public-key cryptosystems based on LWE. We proposed a multi-bit encryption dual LWE encryption scheme based on Peikert's multi-bit LWE encryption and Gentry's single-bit dual LWE encryption. Based on a collection of preimage samplable functions and dual LWE encryption, Gentry presented a single-bit IBE scheme. We turned it into a multi-bit IBE scheme. Boneh etc. suggested a general approach which can be used to construct a CCA-secure public-key encryption scheme based on any identity-based encryption (IBE) scheme. With the Boneh's approach, we construct a new lattice-based CCA-secure public-key encryption from the multi-bit IBE scheme. All of the above schemes are constructed on the decisional version of LWE problem. In 2009 Peikert showed that the search version of LWE, for any sufficiently large modulus, is at least as hard as approximating GapSVP in the worst case, via a classical reduction. He put forward a collection of trapdoor functions based on the search version of LWE and constructed a CCA-secure encryption scheme. These results provide new basis for lattice-based cryptographic constructions.(2) Public-key encryption schemes based on SIS and ISIS. The schemes based on SIS and ISIS are mainly based on preimage samplabe functions. Gentry constructed one digital signature scheme on these functions. But there isn't public-key encryption scheme based on them. We use witness-recovering decryption method proposed by Peikert to construct CPA-secure public key encryption scheme based on preimage samplable functions. These functions are proved to be satisfied with three properties that injective functions should hold. Inspired by Rosen's correlated products method which can be used to build public encryption schemes on a collection of injective functions which are secure under correlated products, we construct CCA 1 and CCA2 secure schemes.(3) Lattice-based proxy signature. To construct LWE-based hierarchical identity-based encryption schemes, Rosen presented a technique called basis delegation that allows one to use a short basis of a given lattice to derive a new short basis of a related lattice with higher dimension in a secure way. The basis delegation technique is the generalization of Gentry's preimage samplable functions. At the heart of our basis delegation technique is an idea called generalized preimage sampling. Since short bases for lattices essentially function like cryptographic trapdoors, basis delegation turns out to be a very powerful primitive and can be used in lattice-based cryptographic constructions. I construct a basic lattice-based proxy signature scheme and multiple-grade proxy signature scheme. Both of them are based on Gentry's preimage samplable functions based signature scheme. The basis delegation technique is used to generate proxy signing keys in our proxy signature scheme and multiple-grade proxy signature scheme.My research and constructions enrich the current research on the lattice-based public-key cryptosystems. Later we will design new schemes based on the presumed hardness of lattice problems. As the security of these schemes are all the result of theory proof, how to evaluate the security of the schemes in practice and how to choose parameters in schemes are still open. These factors are of great importance to the real practice of lattice-based schemes. To put these lattice-based schemes into practice early, improving practicability and efficiency of current schemes is the main research object.