Lattice Reduction Theory And Its Applications To Cipher Design

Lattice reduction is not only an important task of lattice research but also a powerful tool for cryptology. Many lattice problems can be solved by lattice reduction directly, and even some NP-hard lattice problems can be approximately solved by reduction. On the other hand, some cryptanalysis can be reduced to lattice reduction problems. Therefore, to design new lattice reduction algorithms has great value in lattice research as well as in practical applications.It is a common measure that employing some mathematical hard problems in crypto scheme designing. A good crypto scheme should be secure and efficient. It is well known that lattice has typical linear structure and some lattice problems have been proven to be NP-hard. A crypto scheme based on lattice hard problems can be expected to be secure as well as efficient. Because of these potential advantages, many scholars focus on constructing crypto schemes on lattice.This paper is based on the research result of study on NTRU Public Key Cryptosystem, a project supported by the foundation of National Laboratory for Modern Communications under No. 51436010203QT2201. This paper is composed of two main parts. In the first half of this paper, research focuses on basic conceptions of lattice and lattice reduction algorithms. l -reduced lattice reduction algorithm is presented for the first time. The results of this algorithm are better than one's got by standard LLL reduction algorithm. An interesting property of this algorithm is that a better reduced lattice base can be got if a lager l is chosen, while the time cost increased. Using this algorithm, the approximate shortest vector with coefficient a^1/2 can be disclosed, while the one with coefficient a^(n-1)/2 can be got by using standard LLL algorithm. The conception of SVK-lattice is proposed for the first time. Two sufficient conditions for disclosure of the shortest vector in some lattice are proven. Based on these two conditions, measures for constructing random SVK-lattices are discussed, too. In the second half of this paper, research focuses on crypto schemes based on lattice hard problems. Several public key crypto schemes are analyzed. An efficient compensating algorithm is proposed for NTRU decryption correction. Basedon Goldreich et al's study, a new hash function is presented. This hash function can be proved to be collision-free. Concretely, the following aspects are investigated deeply in this paper:(1) Basic conceptions of lattice theory, especially ones applied in cryptography, are introduced. The conception of lattice reduction and the advances in lattice reduction research are shown. / -reduction is proposed for the first time. / -reduced lattice reduction algorithm is presented, too. The different performances of / -reduced lattice reduction algorithm and standard LLL algorithm are compared by numerical experiments results.(2) SVK-lattices, in which the shortest vector is known, are proposed for the first time. Several theorems on the relationship between cyclic lattices and SVK-lattices are proposed and proved. Two sufficient conditions for disclosure of the shortest vector in some lattice are proven. Two algorithms are designed for generating random SVK-lattices.(3) Several public key crypto schemes are analyzed. Based on their common phenomena of decryption failure, the conceptions of PPKC and IPKC are introduced. The different abilities to resist some typical attacks of PPKC and IPKC are analyzed. Errors sniffing attack model, which only works on IPKC, is proposed.(4) NTRU decryption failures are analyzed. As a result, the theoretical bounds of parameters, which guaranteed NTRU decryption failure free, are presented. In order to correct NTRU decryption failures, a compensating algorithm is proposed. To our knowledge, this algorithm is better than any other ones for NTRU decryption failure correction.(5)A fault in process of proving LMAC's security is pointed out. Employing Goldreich compression function, GHash is designed. This hash function can be proven to be collision-free. The security of GHash is proven, too. Two set of parameters for secure GHash are proposed. Some applications of GHash are discussed.