Research On Efficient Lattice-Based Public Key Cryptosystems

The emergence of quantum computer is a serious threat to the public keycryptosystems which are now widely used and based on the number theory. In order tocope with the challenge of quantum computer and guarantee the information security inthe future, the research of post-quantum cryptography has already become to one of thehot fields in the modern cryptography.Lattice-based cryptography is a classical representative against quantum computerattack. The lattice-based cryptographic schemes can resist the quantum computer attackand their average security is based on the worst case hardness of lattice problems.Moreover, their linear constructions will be expected to have faster encryption anddecryption speed. However, the main disadvantages of lattice-based constructions arelarge key sizes and large space complexity. So these result in the schemes being ratherinefficient and unsuitable for practical use.To cope with this inherent inefficiency, we discuss the design and analysis ofefficient lattice-based cryptography in this thesis. We show how to improve and buildefficient encryption schemes, signature schemes and identification schemes. Our maincontributions are as follows:(1) A new NTRU encryption scheme which is based on the Ring-Learning WithError problem is given. The new scheme is provably secure in the standard model. Andwe present a lattice attack method to this scheme.(2) A novel NTRU-class digital signature scheme using Gaussian samplingalgorithm and the property of the cyclic lattice is presented. The signature values of thenovel scheme will leak no information on the private key. Moreover, we discuss theefficiency and security of the novel scheme.(3) A novel ideal lattice-based zero-knowledge identification scheme is presented.According to compare the new scheme with the several old schemes which can resistquantum computer attack, our new scheme is secure and the most efficient.