Research on Discrete Measures and Several Hard Problems on Lattices 

Author  TianChengLiang 
Tutor  WangXiaoYun; XuGuangWu 
School  Shandong University 
Course  Information Security 
Keywords  Latticebased cryptography Gaussian measure Laplace measure Transference theorem Closest vector problem with preprocessing 
CLC  TN918.1 
Type  PhD thesis 
Year  2013 
Downloads  59 
Quotes  0 
In1994, Shor [1] presented polynomial time quantum algorithms for factoring large integers and solving discrete logarithm problem. Recently, the rapid development of quantum computing has brought about a huge challenge to traditional public key cryptography. Therefore, research on cryptosystems resisting to the attack of quantum computing is promoted to an unprecedented level. Among them, latticebased cryptography which is gradually established in the past decade has been put into practice in recent years and becomes a hot research field in the postquantum cryptography era.A lattice is a set of points in ndimensional space with a periodic structure. Concretely, a lattice is the set of all integer combinations of n linearly independent vectors b1,…,bn∈Rn. The vectors b1,…, n, are known as a basis of the lattice. Lattice is a classical object in the geometry of numbers and the study of lattices originates from the sphere packing problems in the17th century. Now lattice theory has become an important tool in cryptanalysis and in the design of cryptosystems. On one hand, the efficient algorithms solving hard problems in lattice have been converted to vital tools in publickey cryptanalysis. Using lattice basis reduction algorithms, we can attack many classical publickey cryptosystems, e.g. RSA with small private exponents [2,3], knapsackbased cryptosystems [46], NTRU [7], etc. On the other hand, in1996, the breakthrough work of Ajtai [8] which connected the worstcase and the averagecase complexity of certain computational problems on lattices has opened the door to cryptography based on the worstcase hardness. At present, latticebased cryptographic constructions are based on the presumed hardness of lattice problems, the most basic of which are the shortest vector problem (SVPy), the closest vector problem (CVPγ), and the shortest independent vectors problem (SIVPγ), where γ≥1denotes the approximate factor. The study of these hard problems is one core research area in latticebased cryptography.1. Gaussian measure inequalities on lattices and the transference theoremAs an important analytical tool in the study of geometry problems, Gaussian measures play an important role in the research on lattice problems. For any s>0, define the Gaussian function centered at c∈Rn with parameter s as: Vx∈Rn,ρs,c(x)=eπxc2/s2. For any vector c∈Rn, real s>0, and lattice L, the discrete Gaussian distribution over L is defined as:(?)x∈L, DL,s,c(x)=ρs,c(x)/ρs,c(L) where ρs,c(L)=∑V∈L ρs,c(v).When s=1and/or c=0, the corresponding subscripts are omitted.Banaszczyk [9] first studied the basic properties of the Gaussian measures on lattices. Using moment estimation, derivative calculation, and other complex derivations, he got two important measure inequalities. Namely, the author proved that for any vector u∈Rn and constant c>1/(?)π, where C=c(?)πe·eπc2<1,Bn(2) denotes the ndimensional closed unit ball in h norm. Using these two measure inequalities, Banaszczyk improved the transference theorem of primaldual lattices, and obtained almost optimal upper bound within a factor of constant. Formally, he proved that for any ndimensional lattice L,λ1(L,Bn(2))λn(L*,Bn(2))≤n, where L*denotes the dual lattice of L and for any convex body U which is symmetric with respect to the origin, λi/(L, U):=inf{r>0:dim (span(L∩rU))≥i},1≤i≤n denotes the ith successive minima of L with respect to U. Based on the same measure inequalities and through elaborate analysis of lattice structure, Cai [13] generalize Banaszczyk’s results and proved that there exists a absolute constant C>0such that for any ndimensional lattice L and1≤i≤n,λi(L,Bn(2)vni+1(L*,Bn(2))≤Cn, where for any convex body U which is symmetric with respect to the origin, v,(L, U) denotes the minimum r such that there are i linearly independent lattice vectors in rU that can be extended to a basis of L.In2000, Klein [10], using discrete Gaussian measures on integers, proposed a polynomial time algorithm to solve CVP when the target vector is unusually close to the lattice. But the author didn’t show us how to sample an integer according to discrete Gaussian with a small scale factor s. Later on, Gentry et al [12], relying on the discrete Gaussian measure inequality with a big s, showed that the Rejection Sampling Algorithm can be used to sample an integer according to discrete Gaussian on integers and further proved that the Klein’s algorithm can output an lattice point according to discrete Gaussian on lattices with a big scale factor s. Moreover, Gaussian measures inequalities also play an significant role in computational complexity theory and the security proof of latticebased cryptographic constructions. Using this power tool, references [11,12] devised an efficient algorithm to chose an lattice point uniformly at random and improved Ajtai’s worstcase to averagecase connection factors, which is the best results now. Based on the two inequalities, Aharonov and Regev [14] defined a function which can be used to distinguish the distance between the target vector and the lattice in l2norm with gap γ=O{(?)n/logn), and proved that the closest vector problem with preprocessing and gap (?)n (GapCVP(?)n) is unlikely NPhard. Regev [15] designed a latticebased cryptosystem and using these two inequalities proved that its security was based on the hardness of unique shortest vector problem. Therefore, it is important for us to study the Gaussian measure inequalities on lattices, and any essential improvement will make a substantial influence on the hardness of lattice problems and the security of latticebased cryptosystems.In Chapter3, we first analyze the discrete Gaussian measures on integers, and give a new measure inequality independent of s which implies that the Rejection Sampling Algorithm is also fit for sampling an integer according to discrete Gaussian with a relatively small scale factor. This complete the theoretical analysis on Klein’s algorithm. Secondly, we also improve Banaszczyk’s measure inequlities on general lattices with an uniform, concise yet elementary and transparent proof. Namely, we prove that for any ndimensional lattice L, vector u Rn and constant c>1/(?)π, where Cc(?)2πe·eπc2<1. Furthermore, using the Gaussian measure inequalities in lp norm given by Banaszczyk[16], we generalize the transference theorem of Cai [13] to general convex bodies. The bound is better than that obtained by simply generalizing the h norm using the canonical norm inequalities. Namely, we prove that for any ndimensional lattice L,1≤p,q<∞,i=1,2,…,n, there exist three positive constants C1,C2,C3such that In particular, if1/p+1/q1, then where Bn(p) and Bn(∞) denote the ndimensional closed unit ball in lp norm and in l∞, norm, respectively.2. Discrete Laplace measures on lattices and their applications to CVPPGaussian measure on lattices has been a significant tool in the study of lattice structures, computational complexity of lattice hard problems and latticebased cryptosystem constructions. A natural question is whether there exist other measures that can be applied to latticebased cryptography. As an exploration, in Chapter4, we generalize the Gaussian measure and define the discrete Laplace measure on lattice, which can be applied to solve the closest vector problem with preprocessing.For any vectors c, x∈Rn and constant s>0, the Laplace density function centered in c scaled by a factor of s is defined as ps,c(1)(x)=e2xc/s1, where·1denotes the l1norm. To simplify the notation, we write ρs,c(1)(A)=∑x∈A ρs,c(1)(x) for any countable set A. For any lattice L, define the discrete Laplace distribution EL,s,c on L byIn coding theory or latticebased cryptosystems, the closest vector problem corresponds to the decoding or decryption process. Notice that the lattice L is usually fixed, and it is known long before transmission occurs, therefore it is allowed to preprocess the lattice arbitrarily in advance. And in coding theory,l1metric is common, hence it is of practical significance to consider the closest vector problem with preprocessing in l1norm.Chapter4gives the basic properties of discrete Laplace measure on lattices, and obtains two useful Laplace measure inequalities. Furthermore, we apply these two measure inequalities to CVPP and get a polynomial time algorithm for GapCVPP in l1norm with gap O(n/log n), which improves Aharonov and Regev’s result in l1norm and partially solves the open problems proposed by Perkert in CCC2007[17]. In addition, the discrete Laplace measures over lattices provide a new tool for the study of hard problems on lattices.3. Efficient reductions among lattice problemsThe shortest vector problem (SVPy) and closest vector problem (CVPγ) are the most popular hard problems in lattice theory. While Ajtai [8] and Regev [18]’s work indicate that the security of all the lattice cryptosystems based on SIS or LWE problem is depended on the hardness of shortest independent vectors problem (SIVPγ). Thereby, it is natural to compare the hardness among these three problems SIVPy, SVPγ and CVPy. In order to study the hardness of SIVPγ, Blomer and Seifert [19] presented an deterministic reduction from CVP to SIVP in their exact versions (namely γ1), but the reduction dosen’t preserve the rank of lattices. Using the transference theorem in the geometry of numbers, Miccinacio [20] improved Blomer and Seifert’s result and gave a deterministic polynomial time rankpreserving reduction. Thorough an elaborate analysis on lattice structure, the reference [20] also gave an polynomial time rankpreserving reduction from SIVPγ to CVPγ for any factor γ>1. From the above two reductions, it is obviously that the exact versions of CVP and SIVP are equivalent.Little is known about the relationships among problems SIVPγ, SVPγ and CVPγ when the approximate factor γ>1, for which reasons, Miccinacio proposed the following two open problems in SODA2008[20].Open Problem1:Are there deterministic polynomial time reductions between SVPγ and SIVPγ that preserve both the rank of lattices and quality of approximation? Are the two problems equivalent? Incomparable? Or one strictly harder than the other?Open Problem2:Is there a deterministic polynomial time reduction from CVPγ to SIVPγ that preserves the rank of lattices and approximation factor?In Chapter5, we give some helpful explorations on these two open problems. More precisely, we study the relationship between SIVPγ and SVPy and give a deterministic polynomial time rankpreserving reduction from SIVPγ(?)n to SVPγ, which improves the known result by a factor of y. Moreover, we study the relationship between SIVPγ and CVPγ’ in some special cases. When the target vector is far from the lattice, using the SIVPγ oracle and Babai’s nearest plane algorithm, we can solve this special case CVP with approximate factor2γ(?)n, and for a uniformly random chosen target, the successful probability of the algorithm is not less than1/2. Specially, when γ∈(1,2) in the SIVPγ oracle, we obtain a better result. When the target vector is close to the lattice, we give an elaborately and strictly theoretical analysis on the derandomization of Klein’s algorithm. With the help of this algorithm, we give a deterministic polynomial time reduction from BDDc/vn to SIVPγ for any given constant c.