Dissertation
Dissertation > Industrial Technology > Radio electronics, telecommunications technology > Communicate > Confidentiality of communications and communications security > Theory

Research on Discrete Measures and Several Hard Problems on Lattices

Author TianChengLiang
Tutor WangXiaoYun; XuGuangWu
School Shandong University
Course Information Security
Keywords Lattice-based cryptography Gaussian measure Laplace measure Transference theorem Closest vector problem with preprocessing
CLC TN918.1
Type PhD thesis
Year 2013
Downloads 59
Quotes 0
Download Dissertation

In1994, Shor [1] presented polynomial time quantum algorithms for factoring large integers and solving discrete logarithm problem. Recently, the rapid develop-ment of quantum computing has brought about a huge challenge to traditional pub-lic key cryptography. Therefore, research on cryptosystems resisting to the attack of quantum computing is promoted to an unprecedented level. Among them, lattice-based cryptography which is gradually established in the past decade has been put into prac-tice in recent years and becomes a hot research field in the post-quantum cryptography era.A lattice is a set of points in n-dimensional space with a periodic structure. Con-cretely, 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 public-key cryptanalysis. Using lattice basis reduction algorithms, we can at-tack many classical public-key cryptosystems, e.g. RSA with small private exponents [2,3], knapsack-based cryptosystems [4-6], NTRU [7], etc. On the other hand, in1996, the breakthrough work of Ajtai [8] which connected the worst-case and the average-case complexity of certain computational problems on lattices has opened the door to cryptography based on the worst-case hardness. At present, lattice-based 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 approxi-mate factor. The study of these hard problems is one core research area in lattice-based cryptography.1. Gaussian measure inequalities on lattices and the transference theoremAs an important analytical tool in the study of geometry problems, Gaussian mea-sures 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-π||x-c||2/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 lat-tices. 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 n-dimensional closed unit ball in h norm. Using these two measure inequalities, Banaszczyk improved the trans-ference theorem of primal-dual lattices, and obtained almost optimal upper bound within a factor of constant. Formally, he proved that for any n-dimensional 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 Ba-naszczyk’s results and proved that there exists a absolute constant C>0such that for any n-dimensional lattice L and1≤i≤n,λi(L,Bn(2)vn-i+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 dis-crete 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 lattice-based cryptographic constructions. Using this power tool, ref-erences [11,12] devised an efficient algorithm to chose an lattice point uniformly at random and improved Ajtai’s worst-case to average-case 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 NP-hard. Regev [15] designed a lattice-based 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 essen-tial improvement will make a substantial influence on the hardness of lattice problems and the security of lattice-based 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 rel-atively 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 n-dimensional lattice L, vector u Rn and constant c>1/(?)π, where C-c(?)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 n-dimensional lattice L,1≤p,q<∞,i=1,2,…,n, there exist three positive constants C1,C2,C3such that In particular, if1/p+1/q-1, then where Bn(p) and Bn(∞) denote the n-dimensional 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 lattice-based cryp-tosystem constructions. A natural question is whether there exist other measures that can be applied to lattice-based cryptography. As an exploration, in Chapter4, we gen-eralize 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)=e-2||x-c/s||1, 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 lattice-based cryptosystems, the closest vector problem corre-sponds 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 rank-preserving reduction. Thorough an elaborate analysis on lattice structure, the reference [20] also gave an polynomial time rank-preserving 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 fol-lowing 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 de-terministic polynomial time rank-preserving reduction from SIVPγ(?)n to SVPγ, which improves the known result by a factor of y. Moreover, we study the relationship be-tween 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 derandom-ization 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.

Related Dissertations
More Dissertations