Applications Of Lattice Theory In Cryptanalysis Of Public Key Schemes And Computational Algebra

Lattices are regular arrangements of points in Rm. From the mathematical point of view, lattices are discrete additive subgroups of Rm. The history of lattice re-duction dates back to the reduction theory of quadratic forms developed by La-grange、Gauss among others, and to Minkowski’s geometry of numbers. Since the celebrated LLL lattice basis reduction algorithm was proposed in1982, lattice the-ory have had extensive applications in the fields of mathematics,cryptology and theory of computer science.With respect to mathematics and cryptanalysis of public key schemes, LLL algo-rithm and other lattice basis reduction algorithms can be considered as efficient tools in these two areas (the reference provides an excellent introduction for the lattice reduction algorithms). Many mathematical problems can be reduced to easier ones which can be solved by lattice basis reduction algorithms. Such as the factorization of univariate polynomial over Q problem, integer linear programming with fixed variables problem, and so on. In the areas of assessments of the security of public key cryptosystems, lattice basis reduction algorithms can be utilized to attack kinds of public key cryptosystems, including cryptanalysis of Merkle-Hellman knapsack cryp-tosystems, weak key attacks on RSA cryptosystems, and attacks on spe-cial settings of DSA and ECDSA, and so on. Additionally, from the view of theoretical computer science, most of lattice problems are proved to be NP-hard, which can be utilized in the design of lattice based cryptosystems. Such as the Ajtai- Dwork public key algorithm which is based on uSVP problem, digital signature schemes based on SIS problem and public key encryption cryptosystems based on LWE problem, and so on. Under the quantum computer model, Shor discovered the polynomial-time algorithms to solve the integer factorization problem and discrete logarithm problem. However, practical algorithms of solving the NP-hard prob-lems have not been found till now. Therefore, cryptanalysis and design of public key cryptosystems based on hard lattice problems is one of the hot topics of post-quantum cryptosystems.In this thesis, we study the applications of lattice theory on the cryptanalysis of public key cryptosystems and computational algebra. The main contributions includes four aspects. Firstly, we propose the estimations of the lower bounds of the shortest vector length of random NTRU lattices; Secondly, we present the cryptanalysis of a homomorphic encryption scheme based on vector spaces, and our attack is practical on all the three settings of recommended parameters; Thirdly, we propose a practical attack against a fast public key cryptosystem based on Chinese Remainder Theorem. Finally, using the lattice basis reduction algorithms, we present a deterministic sub-linear in q algorithm to decide whether a sparse univariate polynomial has a root over finite fields Fq.1.Lower Bounds of Shortest Vector Lengths in Random NTRU LatticesGiven a lattice L with dimension n, how to find the shortest vector is one of the most important problems in computational lattice theory. For the upper bound of the shortest vector length, one can obtain it from the famous Minkowski’s Convex Body Theorem. More precisely, if the volume of a given ball with dimension n is bigger than2n det(L), then there must exist a non-zero lattice point. Therefore, the length of the shortest vector is shorter than (?)net(L)1/n. For a random lattice, one can expect the "average" length of the shortest vector through Gaussian Heuristic. More specifically, for a random lattice L with determinant det(L). Gaussian Heuristic expects there are about Vol(((?))/det(L) lattice points in a measurable subset ((?) of Rn with volume Vol((?)). In other words, the length of the shortest vector can be approximated by the radius of a sphere whose volume is det(L), which is about (?)n/2eπ det(L)1/n. As the first work of this thesis, we propose a general method to estimate the lower bounds of the lengths of the shortest vectors for a kind of random integral lattices. As a significant application, we consider random NTRU lattices which can be used to ana-lyze NTRU cryptosystems. Now, NTRU cryptosy stem is the standard of IEEE P1363.1, whose encryption and decryption operations are in the ring of truncated polynomials Z[X]/(XN-1).Let Sf and Sg be two sets of polynomials in Z[x] of degree at most N-1and of very small coefficients. Let q be a positive integer, select polynomials f(x)∈Sf and g(x)∈Sg. Let h(x)=∑i=0N-1hixi be the polynomial such that h(x)f(x)=g(x)(mod q,xN-1). Define the cyclic matrix Define the NTRU lattice as follows,The security of the NTRU cryptosystem is related to the difficulty of finding short vectors in the NTRU lattice. One can obtain the equivalent keys of NTRU cryp-tosystems from the short vectors of NTRU lattices.We call an NTRU lattice (Sf,Sg)-random, if f(x) is selected uniformly at random from the invertible elements (in the ring Zq[x]/(xN-1)) in Sf, and g(x) is selected uniformly from Sg.Note that, Gaussian Heuristic clearly does not hold for random NTRU lattices. According to the Gaussian Heuristic, the shortest vector length is Ω((?)Nq). However, the vector of the coefficients of f and g, is in the NTRU lattice and has length0((?)N). Since f and g have very small coeffi-cients, many researchers conjecture that the vector T is the shortest vector in the NTRU lattice in most of cases. However, no formal proof has been provided.As the first work of this thesis, we propose the estimations of the lower bounds of the shortest vector length of the random NTRU lattices. More precisely, with an overwhelming probability, the ratio between the length of the shortest vector and length of the target vector is at least a constant, independent of the rank of the lattice.2.Cryptanalysis of a Homomorphic Encryption Scheme From ISIT2008Homomorphic encryption is an interesting concept to protect privacy, which was proposed by Rivest, Adleman and Dertouzos in1978. Since its publication, this idea was used widely, such as the e-voting system, the private information retrieval protocol, and so on.Formally, a homomorphic encryption scheme can be described as follows:for two messages m1, m2, it satisfies that Dec(En(m1)(?) En(m2))=m1(?) m2. where (?) and (?) are two operations over ciphertexts and plaintexts, respectively. Usu-ally, if (?) represents modular addition over plaintexts, we call this scheme additively-homomorphic. If the homomorphic scheme only permit finite times operations on the ciphertexts, we call this scheme "bounded" homomorphic scheme, such as the homo-morphic schemes proposed by the references. If the homomorphic scheme can permit arbitrary times of operations on ciphertexts, we call this scheme "fully" ho-momorphic scheme. Recently, Gentry proposed the first "fully" homomorphic cryp-tosystem based on ideal lattice. After that, further research focused on how to construct new homomorphic encryption schemes based on other hard problems, such as approximate greatest common divisor problem and Ring-LWE problem.As the second work of this thesis, we present an equivalent key attack on a "bounded" homomorphic encryption scheme based on vector spaces, which was pro-posed by Aguilar Melchor, Castagnos and Gaboril at ISIT2008(abbreviated as MCG). The one-wayness of the MCG scheme relies on the hardness of the Computa-tional Knapsack Vector Problem (CKVP). For the settings of recommended parame-ters, the known method to recover the message is to find a short vector in a lattice with dimension at least600.We present a key-recovery attack on MCG by avoiding the CKVP directly. Firstly, we uncover a hidden linear relationship between the public keys and the private keys. Secondly, from partial public keys, construct a dimension-reduced lattice with dimen-sion much less than600, we can recover the noisy matrices by solving N CVP instances of the new lattice. Finally, we can recover the whole equivalent private keys from the noisy matrices by using simple mathematical computations. According to our exper-iments, all the three scheme instances with the recommended parameters are broken practically.3.Cryptanalysis of a Public-key Scheme Based on the Chinese Remainder TheoremDiffie and Hellman first proposed the idea of public keys encryption, by find-ing one way and threshold functions which are based on mathematical hard prob-lems. The two most popular traditional public keys schemes are RSA algorithm, which is based on the integer factorization problem, and Elgamal algorithm which is based on discrete logarithm problems over finite fields or the rational point group of elliptic curves. Since the main encryption operations of these two schemes are ex-ponential computation modulo a large integer, they are not efficient in some resource-constrained devices. Therefore, it is very important to design new public key encryp-tion schemes with high key generation, encryption and decryption speeds. Knapsack-based cryptosystems are such fast public key schemes, which only need modulo mul-tiplication and addition. Unfortunately, both the first knapsack-based cryptosystem Merkle-Hellman cryptosystem and Chor-Rivest cryptosytem were broken effi-ciently.Wang et.al designed a fast public key cryptosystem which is based on the Chi-nese Remainder Theorem. During the encryption and decryption procedures, it only needs the operations of multiplications modulo integers. Compared to RSA、Elgamal public encryption schemes, the speed is much higher. As the third work of this thesis. we present an efficient heuristic attack against this scheme. The basic idea of this attack is to construct a particular lattice, and one can obtain the plaintext by solving a short vector problem or a close vector problem. The plaintext can be recovered by lattice basis reduction algorithms practically, since the dimensions of the constructing lattices is low.4. Solvability of univariate sparse polynomial over finite fieldsAs the fourth contribution, we investigate the solvability of univariate sparse poly-nomials over finite fields problem. More precisely, given finite fields Fq and a univariate t-nomial f(x)=c0+c1xq1+c2xa2+…+ct-1xa-1.(4) Decide whether f(x) has a root over.To solve this problem, we design a deterministic algorithm by utilizing the lat-tice reduction algorithms in time4t+o(t)qt-2/t-1+o(1).When t is fixed, this algorithm is the first sub-linear in q algorithm, which has solved the open problem proposed by Erich Kaltofen, i.e. detecting roots for a trinomial equation a+bxd0+cxd=0with d> do>0within time sub-linear in d and q.