格上离散测度及格中几个困难问题研究
|
摘要
早在1994年,Shor[1]就提出了分解大整数和求解离散对数问题的多项式时间量子算法。近年来,随着量子计算的高速发展,传统公钥密码学面临着严峻挑战,因此研究抗量子攻击的密码体制被提升到一个前所未有的高度。其中,格密码体制是近十多年来逐步建立并向实用化密码体制发展的新型密码体制,是未来抗量子计算攻击公钥密码体制核心研究领域。
格是n维实空间中一类具有周期结构离散点的集合。具体地,格是Rn中n个线性无关的向量b1,…,b所有整系数线性组合构成的集合,其中b1,…,bn称为格的一组基。它是数的几何中一个经典研究对象,来源于17世纪对球堆积问题的研究。现在,在密码分析和密码体制设计方面,格理论都有很重要的应用。方面,解决格中困难问题的有效算法转变为公钥密码分析的重要工具,利用格基约化等工具已成功分析多个经典公钥密码体制,例如小加解密指数的RSA体制[2,3],背包密码体制[4-6],NTRU[7]等。另一方面,Ajtai[8]在1996年开创性的给出了格困难问题的worst-case至(?)average-case的归约,即证明了一类随机格的短向量问题(SIS)的困难性至少等价于最坏情况下格中计算问题的困难性,这使得基于格的陷门单向函数的设计成为可能,开启了基于格的密码学大门。目前,格密码体制的安全性大多基于格中计算问题的困难性。因此,对格中困难问题的研究是基于格的密码学的核心研究内容。格理论中最重要的计算困难问题有最短向量问题(SVPγ)、最近向量问题(CVPγ)以及最短线性无关向量问题(SIVPγ),其中γ≥1表示近似因子。
1.格上的高斯测度不等式及主对偶格的反转定理
作为用分析方法研究几何问题的重要工具,高斯测度在格问题的研究中发挥了重要作用。对任意的实数s＞0,定义以c∈Rn为中心,s为伸缩因子的高斯密度函数为Vx∈Rn,ρs,c(x)=e-π‖x-c‖2/s2给定格L∈Rn,其上的离散高斯测度定义为(?)x∈L,DL,s,c(x)=ρs,c(x)/,ρs,c(L)其中ρs,c(L)=∑v∈Lρs,c(v)。当s=1或c=0时,通常略去下标。
Banaszczyk[9]首次研究了格上离散高斯测度的基本性质,通过矩估计、导数计算等复杂的推导,给出了的两个重要的测度不等式,即证明了对任意的n维格L,向量u∈Rn及实数c＞(?),有其中表示l2范数n维闭单位球。Banaszczyk利用这两个测度不等式,改进了之前的主对偶格的反转定理,在相差一个常数因子情况下获得了最优的上界,即对任意的n维格L及其对偶格L*,λ1(L,Bn(2))λn(L*,Bn(2))≤n,其中,对任意的关于原点中心对称的凸体U及1≤i≤n,λi(L, U):=inf {r>0:dim(span(L n rU))≥i}为格L在凸体U诱导的度量下的第i个逐次最小值。基于相同的测度不等式,通过对格结构更加细致的分析,Cai[13]又推广了Banaszczyk的结果,即证明了存在绝对常数C＞0,使得对任意的n维格L及1≤i≤n,有λi(L,Bn(2))vn-i+1(L*,Bn(2))≤Cn,其中,对任意的关于原点中心对称的凸体U,v1(L,U)定义为使得rU中包含i个可扩充为格L的一组基的线性无关向量的最小正实数r。
2000年,Klein[10]首次利用整数上的离散高斯测度给出了一个求解目标向量距格很近时的最近向量问题的多项式时间算法,但文中并没有给出s较小时依离散高斯分布采样整数的具体算法。随后,Gentry等[12]给出了一个s较大时整数格上的离散高斯测度不等式,并由此说明拒绝采样算法可在多项式时间内依离散高斯分布返回一个整数,且进一步证明了Klein算法在伸缩因子s较大时可以依离散高斯分布输出一个格点。此外,格上的离散高斯测度在计算复杂性理论与格密码体制的安全性证明中也有重要应用。文献[11,12]将这一强有力的工具用于格困难问题的归约,用之设计了一种有效的随机采样格点的方法,改进了Ajtai的worst-case至(?)average-case的归约因子,得到了目前最好的结果。基于格上的离散高斯测度不等式,Aharonov与Regev[14]定义了一个能很好地区分目标向量与格距离大小的函数,由此证明了间隔因子为(?)的最近向量问题(GapCVP(?)n)不可能是NP-hard的。Regev[15]则利用这两个测度不等式设计了一个安全性基于计算最难格的唯一最短向量问题(uSVP)的格公钥密码体制。因此,格上高斯测度不等式的研究具有重要意义,任何本质的改进都将影响已有的格困难问题的分析结果与格密码体制的安全性。
本文第三章首先分析了整数上离散高斯测度,给出了一个与光滑参数无关的测度不等式,进而说明拒绝采样算法同样适用于伸缩因子相对较小时的离散高斯分布,完善了Klein算法的理论分析；其次用一个简洁、易懂的证明改进了Banaszczyk[9]给出的一般格上的测度不等式,即证明了对任意的n维格L,向量u∈Rn及实数c＞(?),有其中(?)。进一步,利用Banaszczyk[16]给出的一般lp范数下格上高斯测度不等式把Cai[13]的反转定理推广到lp范数,获得了比简单利用常规范数不等式推广更紧的上界,深化了主对偶格的结构关系。即证明了对任意的n维格L,1≤p,q<∞,i=1,2,…,n,存在正常数C1,C2,C3使得如下结论成立,特别地,当1/p+1/q=1时,其中Bn(p)与Bn(∞)分别表示lp与l∞范数下的n维闭单位球。
2.格上的离散拉普拉斯测度及其在CVPP问题中应用
格上离散高斯测度的引入为格结构、格中困难问题以及基于格的密码体制的研究提供了强有力的工具。是否存在其他测度工具能在格问题的研究中找到应用呢?基于以上想法,第四章推广了高斯测度,定义了格上的拉普拉斯测度,并将其应用于格困难问题的研究。
对任意的向量c,x∈Rn及实数s>0,定义以向量c为中心,以s为伸缩因子的拉普拉斯密度函数,记为其中‖·‖1表示l1范数度量。便于书写,对任意的可数集A,对任意的格L,定义格上的离散拉普拉斯分布EL,s,c为
在编码或基于格的密码系统中,译码或解密过程中通常对应着求解最近向量问题。此时,格L一般是公开的,因此允许接收者或攻击者对格进行任意形式的预处理,且编码理论中的度量一般为l1范数度量,因此考虑l1范数度量下带预处理的最近向量问题具有重要的实际意义。
在本文第四章中,我们研究了格上离散拉普拉斯测度的基本性质,得到了两个有用的格上拉普拉斯测度不等式,并将其应用于带预处理的最近向量问题研究,得到了一个求解l1范数下间隔因子为O(n/log n)的GapCVPP问题的多项式时间算法,改进了简单利用范数不等式推广Aharonov与Regev的工作[14]所得到的结果,部分解决了Peikert[17]在计算复杂性会议CCC2007上提出的一个公开问题。同时格上离散拉普拉斯测度的引入为格上其他困难问题的研究提供了潜在新工具。
3.格中困难问题的有效归约
格的最短向量问题(SVPy)与最近向量问题(CVPγ)是格理论中研究的最为广泛的两个问题,而Ajtai[8]与Regev[18]的工作表明所有基于随机格的短向量问题(SIS)与LWE问题设计的格密码体制的安全性都依赖于最短线性无关向量问题(SIVPy)的困难性。因此一个自然的问题就是比较SIVPy与SVPγ、CV凡的难易程度。为了研究SIVPγ问题的困难性,Blomer与Seifert[19]首次给出了精确CVP问题到精确SIVP司题的确定多项式归约,但不保持格的秩。Miccinacio[20]结合主对偶格反转定理改进了上述结果,得到一个保持格的秩的确定多项式时间归约。通过对格结构的细致刻画,文献[20]还给出了一个从SIVPγ至(?)CVPγ的保持秩与逼近因子的多项式时间归约,这说明精确CVP问题与精确SIVP问题是等价的。
对逼近因子较大时,SIVPγ与SVPγ、CVPγ之间的关系目前还知之甚少。对此,Miccinacio[20]在离散算法国际会议SODA2008上提出了以下两个公开问题。
公开问题1：最短向量问题(SVPγ)与最短线性无关向量问题(SIVPγ)之间是否存在保持格的秩与逼近因子的确定多项式时间归约?这两个问题是等价的,不可比较的,还是一个严格难于另一个?
公开问题2：是否存在最近向量问题(CVPγ)到最短线性无关向量问题(SIVPγ)的保持格的秩与逼近因子的确定多项式时间归约?
本文第五章对Miccinacio提出的这两个问题进行了重要探索。研究了最短向量问题与最短线性无关向量问题之间的关系,给出了SIVPγ(?)n至(?)SVPγ的一个保持格的秩的确定多项式时间归约,使最短线性无关向量问题归约因子由目前的γ2(?)降为γ(?)；其次,研究了某些较弱条件或特殊情况下最近向量问题与最短线性无关向量问题的关系,当目标向量距格距离较大时,在SIVPγ谕示下,利用Babai的最近平面算法可求解这一特殊的最近向量问题,其中近似因子2γ(?)n,并且对随机选取的目标向量,该算法是以不小于1/2的概率会得到正确解。特别地,当谕示问题的逼近因子γ∈(1,2)时,我们得到了更好的结果。当目标向量距格的距离较近时,我们详细清晰地阐述了Klein算法的去随机化算法,并从理论上严格分析了其时间复杂度,由此给出了BDDc/vn(?)(?)SIVPγ(?)(?)一个确定多项式时间归约,这里c为任一给定的常数。
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 theorem
As 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 CVPP
Gaussian 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 by
In 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 problems
The 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.
格是n维实空间中一类具有周期结构离散点的集合。具体地,格是Rn中n个线性无关的向量b1,…,b所有整系数线性组合构成的集合,其中b1,…,bn称为格的一组基。它是数的几何中一个经典研究对象,来源于17世纪对球堆积问题的研究。现在,在密码分析和密码体制设计方面,格理论都有很重要的应用。方面,解决格中困难问题的有效算法转变为公钥密码分析的重要工具,利用格基约化等工具已成功分析多个经典公钥密码体制,例如小加解密指数的RSA体制[2,3],背包密码体制[4-6],NTRU[7]等。另一方面,Ajtai[8]在1996年开创性的给出了格困难问题的worst-case至(?)average-case的归约,即证明了一类随机格的短向量问题(SIS)的困难性至少等价于最坏情况下格中计算问题的困难性,这使得基于格的陷门单向函数的设计成为可能,开启了基于格的密码学大门。目前,格密码体制的安全性大多基于格中计算问题的困难性。因此,对格中困难问题的研究是基于格的密码学的核心研究内容。格理论中最重要的计算困难问题有最短向量问题(SVPγ)、最近向量问题(CVPγ)以及最短线性无关向量问题(SIVPγ),其中γ≥1表示近似因子。
1.格上的高斯测度不等式及主对偶格的反转定理
作为用分析方法研究几何问题的重要工具,高斯测度在格问题的研究中发挥了重要作用。对任意的实数s＞0,定义以c∈Rn为中心,s为伸缩因子的高斯密度函数为Vx∈Rn,ρs,c(x)=e-π‖x-c‖2/s2给定格L∈Rn,其上的离散高斯测度定义为(?)x∈L,DL,s,c(x)=ρs,c(x)/,ρs,c(L)其中ρs,c(L)=∑v∈Lρs,c(v)。当s=1或c=0时,通常略去下标。
Banaszczyk[9]首次研究了格上离散高斯测度的基本性质,通过矩估计、导数计算等复杂的推导,给出了的两个重要的测度不等式,即证明了对任意的n维格L,向量u∈Rn及实数c＞(?),有其中表示l2范数n维闭单位球。Banaszczyk利用这两个测度不等式,改进了之前的主对偶格的反转定理,在相差一个常数因子情况下获得了最优的上界,即对任意的n维格L及其对偶格L*,λ1(L,Bn(2))λn(L*,Bn(2))≤n,其中,对任意的关于原点中心对称的凸体U及1≤i≤n,λi(L, U):=inf {r>0:dim(span(L n rU))≥i}为格L在凸体U诱导的度量下的第i个逐次最小值。基于相同的测度不等式,通过对格结构更加细致的分析,Cai[13]又推广了Banaszczyk的结果,即证明了存在绝对常数C＞0,使得对任意的n维格L及1≤i≤n,有λi(L,Bn(2))vn-i+1(L*,Bn(2))≤Cn,其中,对任意的关于原点中心对称的凸体U,v1(L,U)定义为使得rU中包含i个可扩充为格L的一组基的线性无关向量的最小正实数r。
2000年,Klein[10]首次利用整数上的离散高斯测度给出了一个求解目标向量距格很近时的最近向量问题的多项式时间算法,但文中并没有给出s较小时依离散高斯分布采样整数的具体算法。随后,Gentry等[12]给出了一个s较大时整数格上的离散高斯测度不等式,并由此说明拒绝采样算法可在多项式时间内依离散高斯分布返回一个整数,且进一步证明了Klein算法在伸缩因子s较大时可以依离散高斯分布输出一个格点。此外,格上的离散高斯测度在计算复杂性理论与格密码体制的安全性证明中也有重要应用。文献[11,12]将这一强有力的工具用于格困难问题的归约,用之设计了一种有效的随机采样格点的方法,改进了Ajtai的worst-case至(?)average-case的归约因子,得到了目前最好的结果。基于格上的离散高斯测度不等式,Aharonov与Regev[14]定义了一个能很好地区分目标向量与格距离大小的函数,由此证明了间隔因子为(?)的最近向量问题(GapCVP(?)n)不可能是NP-hard的。Regev[15]则利用这两个测度不等式设计了一个安全性基于计算最难格的唯一最短向量问题(uSVP)的格公钥密码体制。因此,格上高斯测度不等式的研究具有重要意义,任何本质的改进都将影响已有的格困难问题的分析结果与格密码体制的安全性。
本文第三章首先分析了整数上离散高斯测度,给出了一个与光滑参数无关的测度不等式,进而说明拒绝采样算法同样适用于伸缩因子相对较小时的离散高斯分布,完善了Klein算法的理论分析；其次用一个简洁、易懂的证明改进了Banaszczyk[9]给出的一般格上的测度不等式,即证明了对任意的n维格L,向量u∈Rn及实数c＞(?),有其中(?)。进一步,利用Banaszczyk[16]给出的一般lp范数下格上高斯测度不等式把Cai[13]的反转定理推广到lp范数,获得了比简单利用常规范数不等式推广更紧的上界,深化了主对偶格的结构关系。即证明了对任意的n维格L,1≤p,q<∞,i=1,2,…,n,存在正常数C1,C2,C3使得如下结论成立,特别地,当1/p+1/q=1时,其中Bn(p)与Bn(∞)分别表示lp与l∞范数下的n维闭单位球。
2.格上的离散拉普拉斯测度及其在CVPP问题中应用
格上离散高斯测度的引入为格结构、格中困难问题以及基于格的密码体制的研究提供了强有力的工具。是否存在其他测度工具能在格问题的研究中找到应用呢?基于以上想法,第四章推广了高斯测度,定义了格上的拉普拉斯测度,并将其应用于格困难问题的研究。
对任意的向量c,x∈Rn及实数s>0,定义以向量c为中心,以s为伸缩因子的拉普拉斯密度函数,记为其中‖·‖1表示l1范数度量。便于书写,对任意的可数集A,对任意的格L,定义格上的离散拉普拉斯分布EL,s,c为
在编码或基于格的密码系统中,译码或解密过程中通常对应着求解最近向量问题。此时,格L一般是公开的,因此允许接收者或攻击者对格进行任意形式的预处理,且编码理论中的度量一般为l1范数度量,因此考虑l1范数度量下带预处理的最近向量问题具有重要的实际意义。
在本文第四章中,我们研究了格上离散拉普拉斯测度的基本性质,得到了两个有用的格上拉普拉斯测度不等式,并将其应用于带预处理的最近向量问题研究,得到了一个求解l1范数下间隔因子为O(n/log n)的GapCVPP问题的多项式时间算法,改进了简单利用范数不等式推广Aharonov与Regev的工作[14]所得到的结果,部分解决了Peikert[17]在计算复杂性会议CCC2007上提出的一个公开问题。同时格上离散拉普拉斯测度的引入为格上其他困难问题的研究提供了潜在新工具。
3.格中困难问题的有效归约
格的最短向量问题(SVPy)与最近向量问题(CVPγ)是格理论中研究的最为广泛的两个问题,而Ajtai[8]与Regev[18]的工作表明所有基于随机格的短向量问题(SIS)与LWE问题设计的格密码体制的安全性都依赖于最短线性无关向量问题(SIVPy)的困难性。因此一个自然的问题就是比较SIVPy与SVPγ、CV凡的难易程度。为了研究SIVPγ问题的困难性,Blomer与Seifert[19]首次给出了精确CVP问题到精确SIVP司题的确定多项式归约,但不保持格的秩。Miccinacio[20]结合主对偶格反转定理改进了上述结果,得到一个保持格的秩的确定多项式时间归约。通过对格结构的细致刻画,文献[20]还给出了一个从SIVPγ至(?)CVPγ的保持秩与逼近因子的多项式时间归约,这说明精确CVP问题与精确SIVP问题是等价的。
对逼近因子较大时,SIVPγ与SVPγ、CVPγ之间的关系目前还知之甚少。对此,Miccinacio[20]在离散算法国际会议SODA2008上提出了以下两个公开问题。
公开问题1：最短向量问题(SVPγ)与最短线性无关向量问题(SIVPγ)之间是否存在保持格的秩与逼近因子的确定多项式时间归约?这两个问题是等价的,不可比较的,还是一个严格难于另一个?
公开问题2：是否存在最近向量问题(CVPγ)到最短线性无关向量问题(SIVPγ)的保持格的秩与逼近因子的确定多项式时间归约?
本文第五章对Miccinacio提出的这两个问题进行了重要探索。研究了最短向量问题与最短线性无关向量问题之间的关系,给出了SIVPγ(?)n至(?)SVPγ的一个保持格的秩的确定多项式时间归约,使最短线性无关向量问题归约因子由目前的γ2(?)降为γ(?)；其次,研究了某些较弱条件或特殊情况下最近向量问题与最短线性无关向量问题的关系,当目标向量距格距离较大时,在SIVPγ谕示下,利用Babai的最近平面算法可求解这一特殊的最近向量问题,其中近似因子2γ(?)n,并且对随机选取的目标向量,该算法是以不小于1/2的概率会得到正确解。特别地,当谕示问题的逼近因子γ∈(1,2)时,我们得到了更好的结果。当目标向量距格的距离较近时,我们详细清晰地阐述了Klein算法的去随机化算法,并从理论上严格分析了其时间复杂度,由此给出了BDDc/vn(?)(?)SIVPγ(?)(?)一个确定多项式时间归约,这里c为任一给定的常数。
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 theorem
As 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 CVPP
Gaussian 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 by
In 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 problems
The 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.
引文
[1]P. W. Shor. Algorithms for quantum computation:discrete logarithms and factoring. Pro-ceedings of FOCS 1994, pp.124-134,1994.
[2]D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnera-bilities. Journal of Cryptology, vol.10(4), pp.233-260,1997.
[3]D. Boneh and G. Duffee. Cryptanalysis of RSA with private key d less than N0.292. IEEE Transactions on Information Theory, vol.46(4), pp.1339-1349,2000.
[4]J. Lagarias and A.Odlyzko. Solving low-density subset sum problems. Journal of the ACM, vol.32(1), pp.229-246,1985.
[5]A. Odlyzko, The rise and fall of knapsack cryptosystems, Cryptology and Computational Number Theory, vol.42, pp.75-88,1990.
[6]P. Nguyen and J. Stern. Adapting density attacks to low-weight knapsacks. Advances in Cryptology-ASIACRYPT 2005, LNCS, vol.3788, pp.41-58, Springer-Verlag,2005.
[7]D. Coppersmith and A. Shamir. Lattice attacks on NTRU. Advances in Cryptology-EUROCRYPT 1997, LNCS, vol.1233, pp.52-61, Springer-Verlag,1997.
[8]M. Ajtai. Generating hard instances of lattice problems. Complexity of Computations and Proofs, Quaderni di Matematica, vol.13, pp.1-32,2004. Preliminary version in STOC 1996.
[9]W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen,296(4), pp.625-635,1993.
[10]P. Klein. Finding the closest lattice vector when it's unusually close. Proceedings of SODA 2000, pp.937-941,2000.
[11]D. Micciancio and O. Regev. Worst-case to average-case reductions based on Gaussian measures. SIAM Journal on Computing, vol.37(1), pp.267-302,2007. Preliminary version in FOCS 2004.
[12]C. Gentry, C. Peikert and V. Vaikuntanathan. Trapdoors for hard lattices and new crypto-graphic constructions. Proceedings of STOC 2008, pp.197-206,2008.
[13]J. Cai. A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor. Discrete Applied Mathematics, vol.126(1), pp.9-31,2003.
[14]D. Aharonov and O. Regev. Lattice problems in NP n coNP. Journal of the ACM, vol.52(5), pp.749-765,2005. Preliminary version in FOCS 2004.
[15]O. Regev. New lattice-based cryptographic constructions. Journal of the ACM, vol.51(6), pp.899-942,2004. Preliminary version in STOC 2003.
[16]W. Banaszczyk. Inequalites for convex bodies and polar reciprocal lattices in R". Discrete & Computational Geometry, vol.13, pp.217-231,1995.
[17]C. Peikert. Limits on the hardness of lattice problems in lp norms. Computational Complex-ity,2008, vol.17(2), pp.300-351, Preliminary version in Proceedings of CCC 2007.
[18]O. Regev. On lattices, learning with errors, random linear codes, and cryptography. Pro-ceedings of STOC 2005, pp.84-93, ACM,2005.
[19]J. Blomer and J. Seifert. On the complexity of computing short linearly independent vectors and short bases in a lattice. Proceedings of STOC 1999, pp.711-720,1999.
[20]D. Micciancio. Efficient reductions among lattice problems. Proceedings of SODA 2008, pp.84-93,2008.
[21]D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. Proc. Roy. Soc. London A, vol.439,553-558,1992.
[22]C. H. Bennett. Strengths and weaknesses of quantum computing. SIAM Journal on Com-puting, vol.26, pp.1510-1523,1997.
[23]E. R. Berlekamp, R. J. McEliece and H.van Tilborg. On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, vol.24, pp.384-386,1978.
[24]R. J. McEliece. A public-key cryptosystem based on algebraic coding theory. Technical Report DSN progress report 42-44, Jet Propulsion Laboratory, Pasadena,1978.
[25]J. Hoffstein, J. Pipher and J. H. Silverman. NTRU:a ring based public key cryptosystem. Proceedings of ANTS-Ⅲ, LNCS, vol.1423, pp.267-288. Springer-Verlag,1998.
[26]M. R. Garey and D. S. Johnson. Computers and Intractability:A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. New York, NY, USA, pp.128-130,1979.
[27]J. Patarin, L. Goubin and N. Courtois. Improved Algorithms for Isomorphisms of Polyno-mials. Advances in Cryptology-EUROCRYPT 1998, pp.184-200, Springer-Verlag,1998.
[28]J. Patarin. Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88. Designs, Codes and Cryptography, vol.20(2), pp.175-209,2000.
[29]J. Patarin, N. Courtois and L. Goubin. FLASH, a Fast Multivariate Signature Algorithm, CT-RSA 2001, LNCS 2020, pp.298-307, Springer-Verlag,2001.
[30]V. Dubois, P. A. Fouque, A. Shamir and J. Stern. Practical Cryptanalysis of SFLASH. Ad-vances in Cryptology-CRYPTO 2007. LNCS, vol.4622, pp.1-12, Springer-Verlag,2007.
[31]C. Gentry. Fully homomorphic encryption using ideal lattices. Proceedings of STOC 2009, pp.169-178,2009.
[32]C. Gentry. Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness. Ad-vances in Cryptology-CRYPTO 2010, pp.116-137, Springer-Verlag,2010.
[33]C. Gentry, S. Halevi and V. Vaikuntanathan. i-Hop Homomorphic Encryption and Reran-domizable Yao Circuits. Advances in Cryptology-CRYPTO 2010, pp.155-172, Springer-Verlag,2010.
[34]C. Gentry, S. Halevi and V. Vaikuntanathan. A Simple BGN-Type Cryptosystem from LWE. Advances in Cryptology-EUROCRYPT 2010, LNCS, vol.6110, pp.506-522, Springer-Verlag,2010.
[35]C. Gentry and S. Halevi. Implementing Gentry's Fully-Homomorphic Encryption Scheme. Advances in Cryptology-EUROCRYPT 2011, pp.129-148, Springer-Verlag,2011.
[36]C. Gentry and S. Halevi. Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits. Proceedings of FOCS 2011, pp.107-109,2011.
[37]P. van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Math Inst., University of Amsterdam, Amster-dam,1981.
[38]M. Ajtai. The shortest vector problem in l2 is NP-hard for randomized reductions. Proceed-ings of STOC 1998, pp.10-19,1998.
[39]J. Cai, A. Nerurkar. Approximating the SVP to within a factor (1+1/dim) is NP-hard under randomized reductions. Journal of Computer and System Sciences, vol.59(2), pp. 221-239,1999.
[40]D. Micciancio. The shortest vector problem is NP-hard to approximate to within some con-stant. SIAM Journal on Computing, vol.30(6), pp.2008-2035,2001. Preliminary version in FOCS 1998.
[41]S. Khot. Hardness of approximating the shortest vector problem in lattices. Proceedings of FOCS 2004, pp.126-135,2004.
[42]I. Haviv and O. Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Proceedings of STOC 2007, pp.469-477,2007.
[43]I. Dinur. Approximating SVP∞ to within almost-polynomial factors is NP-hard. Theoretical Computer Science, vol.285(1), pp.55-71,2002.
[44]S. Arora, L. Babai, J. Stern and Z. Sweedyk. The hardness of approximate optima in lattices, codes and linear equations. Proceedings of FOCS 1993, pp.724-733,1993.
[45]I. Dinur, G. Kindler, R. Raz and S. Safra. Approximating CVP to within almostpolynomial factors is NP-hard. Combinatorica, vol.23(2), pp.205-243,2003.
[46]O. Regev and R. Rosen. Lattice problems and norm embeddings. Proceedings of STOC 2006, pp.447-456,2006.
[47]O. Goldreich and S. Goldwasser. On the limits of nonapproximability of lattice problems. Journal of Computer and System Sciences, vol.60(3), pp.540-563,2000. Preliminary ver-sion in STOC 1998.
[48]V. Guruswami, D. Micciancio and O. Regev. The complexity of the covering radius problem on lattices and codes. Computational Complexity, vol.14, pp.90-120,2005.
[49]S. Khot. Inapproximability results for computational problems on lattices. The LLL Algo-rithm, Springer-verlag, Berlin, Heidelberg, P.Q.Nguyen and B.Vallee (eds), pp.453-473, 2010.
[50]O. Regev. On the complexity of lattice problems with polynomial approximation factors. The LLL Algorithm, Springer-verlag, Berlin, Heidelberg, P.Q.Nguyen and B.Vallee (eds), pp.475-496,2010.
[51]J. Cai and A. Nerurkar. An Improved Worst- Case to Average-Case Reduction for Lattice Problems. Proceedings of STOC 1997, pp.468-477,1997.
[52]Daniele Micciancio and Chris Peikert. Hardness of SIS and LWE with Small Parameters. http://eprint.iacr.org/2013/069.
[53]C. Peikert and A. Rosen. Lattices that admit logarithmic worst-case to average-case con-nection factors. Proceedings of STOC 2007, pp.478-487,2007.
[54]C. Peikert. Public-key cryptosystems from the worst-case shortest vector problem. Proceed-ings of STOC 2009. pp.333-342.2009.
[55]Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehle. Classical Hardness of Learning with Errors, Proceedings of STOC 2013, (to appear)
[56]A. K. Lenstra, H. W. Lenstra and Jr., L. Lovasz. Factoring polynomials with rational coef-ficients. Mathematische Annalen, vol.261, pp.513-534,1982.
[57]C. P. Schnorr. A hierarchy of polynomial lattice basis reduction algorithms. Theoretical Computer Science, vol.53, pp.201-224,1987.
[58]N. Gama and P. Q. Nguyen. Finding short lattice vectors within mordell's inequality. Pro-ceedings of STOC 2008, pp.207-216.2008.
[59]N. Gama and P. Q. Nguyen. Predicting lattice reduction. Advances in Cryptology-EUROCRYPT 2008, LNCS, vol.4965, pp.31-51. Springer-Verlag,2008.
[60]B. Vallee and A. Vera. Probabilistic Analysis of Lattice reduction Algorithm. The LLL Algorithm-Survey and Applications, pp.71-143,2010.
[61]Y. Chen and P. Q. Nguyen. BKZ 2.0:Better Lattice Security Estimates. Advances in Cryptology-ASIACRYPT 2011, LNCS, vol.7073, pp.1-20, Springer-Verlag,2011.
[62]C. P. Schnorr and M. Euchner. Lattice basis reduction:improved practical algorithms and solving subset sum problems. Mathematics of Programming, vol.66, pp.181-199,1994.
[63]M. Pohst. On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. ACM SIGSAM Bulletin, vol.15(1), pp.37-44,1981.
[64]R. Kannan. Improved algorithms for integer programming and related lattice problems. Proceedings of STOC 1983, pp.193-206.1983.
[65]N. Gama, P. Q. Nguyen and O. Regev. Lattice Enumeration Using Extreme Pruning. Advances in Cryptology-EUROCRYPT 2010, LNCS, vol.6110, pp.257-278. Springer-Verlag,2010.
[66]M. Ajtai, R. Kumar and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. Proceedings of STOC 2001, pp.601-610,2001.
[67]D. Micciancio and P. Voulgaris. Faster exponential time algorithms for the shortest vector problem. Proceedings of SODA 2010, pp.1468-1480, ACM/SIAM,2010.
[68]G. Kabatiansky and V. Levenshtein. Bounds for packings on a sphere and in space. Prob-lemy Peredachi Informatsii, vol.14(1), pp.3-25,1978.
[69]X. Pujol and D. Stehle. Solving the shortest lattice vector problem in time 22.465n. Cryptol-ogy ePrint Archive, Report 2009/605,2009.
[70]P. Q. Nguyen and T. Vidick. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology, vol.2(2), pp.181-207,2008.
[71]X. Wang, M. Liu, C. Tian and Jingguo Bi. Improved Nguyen-Vidick Heuristic Sieve Algo-rithm for Shortest Vector Problem. Proceedings of ASIACCS 2011, pp.1-9.2011.
[72]L. Babai. On Lovasz lattice reduction and the nearest lattice point problem. Combinatorica, vol.6, pp.1-13,1986.
[73]D. Micciancio and P. Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. Proceedings of STOC 2010, pp.351-358,2010.
[74]J. Blomer and S. Naewe. Sampling methods for shortest vectors, closest vectors and suc-cessive minima. Theoretical Computer Science, vol.410(18), pp.1648-1665,2009.
[75]D. Dadush, C. Peikert and S. Vempala. Enumerative lattice algorithms in any norm via mellipsoid coverings. Proceedings of FOCS 2011, pp.580-589,2011.
[76]M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/average-case equiva-lence. Proceedings of STOC 1997, pp.284-293.1997.
[77]D. Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way func-tions from worst-case complexity assumptions. Computational Complexity,16(4), pp.365-411,2007.
[78]D. Micciancio and O. Regev. Post-Quantum Cryptography, chapter Lattice-based Cryptog-raphy. Springer-Verlag, pp.147-191,2008.
[79]O. Goldreich, S. Goldwasser and S. Halevi. Public-key cryptosystems from lattice reduc-tion problems. Advances in Cryptology-CRYPTO 1997, LNCS, vol.1294, pp.112-131. Springer-Verlag,1997.
[80]O. Goldreich, S. Goldwasser and S. Halevi. Collision-free hashing from lattice prob-lems. Technical Report TR96-056, Electronic Colloquium on Computational Complexity (ECCC),1996.
[81]P. Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto'97. Advances in Cryptology-CRYPTO 1999, pp.288-304, Springer-Verlag,1999.
[82]P. Q. Nguyen and J. Stern. The two faces of lattices in cryptology. Proceedings of CaLC 2001, LNCS, vol.2146, pp.146-180, Springer-Verlag,2001.
[83]P. Q. Nguyen and O. Regev. Learning a parallelepiped:Cryptanalysis of GGH and NTRU signatures. Advances in Cryptology-EUROCRYPT 2006, LNCS, vol.4004, pp.271-288, Springer-Verlag,2006.
[84]Leo Ducas and Phong Q. Nguyen. Learning a Zonotope and More:Cryptanalysis of NTRUSign Countermeasures. Advances in Cryptology -ASIACRYPT 2012, Lecture Notes in Computer Science Volume 7658,2012, pp.433-450.
[85]D. Stehle and R. Steinfeld. Making NTRU as Secure as Worst-Case Problems over Ideal Lattices. Advances in Cryptology-EUROCRYPT 2011, LNCS, vol.6632, pp.27-47, Springer-Verlag,2011.
[86]Y. Pan and Y. Deng. A Ciphertext-Only Attack Against the Cai-Cusick Lattice-Based Public-Key Cryptosystem. IEEE Transactions on Information Theory,57(3), pp.1780-1785,2011.
[87]D. Micciancio and S. Goldwasser. Complexity of Lattice Problems:A Cryptographic Per-spective, volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, Massachusetts,2002.
[88]W. Ebeling. Lattices and codes. Advanced Lectures in Mathematics. Friedr. Vieweg & Sohn, Braunschweig, revised edition,2002. A course partially based on lectures by F. Hirzebruch.
[89]J. W. S. Cassels. An introduction to the geometry of numbers. Springer, Berlin, Gottingen Heidelberg,1959.
[90]J. C. Lagarias, H. W. Lenstra and C. P. Schnorr. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica,10(4), pp.333-348,1990.
[91]W. Banaszczyk. Inequalities for convex bodies and polar reciprocal lattices in Rn Ⅱ:Appli-cation of k-convexity. Discrete & Computational Geometry, vol.16, pp.305-311,1996.
[92]R. Fischlin and J. P. Seifert. Tensor-based trapdoors for CVP and their application to public key cryptography. In 7th IMA International Conference-Cryptography and Coding.1999, LNCS, vol.1746, pp.244-257, Springer-Verlag,1999.
[93]D. Micciancio. The hardness of the closest vector problem with preprocessing, IEEE Trans-action on Information Theory, vol.47(3), pp.1212-1215,2001.
[94]U. Feige and D. Micciancio. The inapproximability of lattice and coding problems with preprocessing. Journal of Computer and System Sciences, vol.69(1), pp.45-67,2004.
[95]O. Regev. Improved inapproximability of lattice and coding problems with preprocessing. IEEE Transactions on Information Theory, vol.50(9), pp.2031-2037,2004.
[96]M. Alekhnovich, S. Khot, G. Kindler and N. K. Vishnoi. Hardness of approximating the closest vector problem with pre-processing. Proceedings of FOCS 2005, pp.216-225,2005.
[97]S. Khot, P. Popat, N. Vishnoi:2log1-ε n hardness for the closest vector problem with prepro-cessing. Proceedings of STOC 2012, pp.277-288,2012.
[98]W. Hoeffding. Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association, vol.58, pp.13-30,1963.
[99]R. Kannan. Minkowski's convex body theorem and integer programming. Mathematics of Operations Research, vol.12, pp.415-440,1987.
[100]R. Kannan. Algorithmic geometry of numbers. Annual Review of Computer Science 2, pp. 231-267,1987.
[101]M. Ajtai, R. Kumar and D. Sivakumar. Sampling Short Lattice Vectors and the Closest Lattice Vector Problem. Proceedings of CCC 2002, pp.53-57,2002.
[102]O. Goldreich, D. Micciancio, S. Safra and J. P. Seifert. Approximating shortest lattice vec-tors is not harder than approximating closest lattice vectors. Information Processing Letters, vol.71(2), pp.55-61,1999.
[103]C. Dubey and T. Holenstein. Approximating the Closest Vector Problem Using an Approxi-mate Shortest Vector Oracle. Proceedings of APPROX/RANDOM 2011, LNCS, vol.6845, pp.184-193, Springer-Verlag,2011.
[104]Z. Brakerski, C. Gentry and V. Vaikuntanathan. Fully Homomorphic Encryption with-out Bootstrapping. Electronic Colloquium on Computational Complexity (ECCC) 18,111, 2011.
[105]K. Boroczky and G. Wintsche. Covering the sphere by equal spherical balls. Discrete & Computational Geometry, The Goodman-Pollack Festschrift,237-253,2003.
[106]H. Cohen. A Course in Computational Algebraic Number Theory,2nd edition. Springer-Verlag,1995.
[107]J. H. Conway and Neil J. A. Sloane, Sphere Packings, Lattices and Groups, Springer-Verlag, 3rd edition,1998.
[108]M. van. Dijk, C. Gentry and S. Halevi, et al. Fully Homomorphic Encryption over the Inte-gers. Advances in Cryptology-EUROCRYPT 2010, LNCS, vol.6110. pp.24-43, Springer-Verlag,2010.
[109]U. Fincke and M. Pohst. Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Mathematics of Computation, vol.44(170), pp. 463-471,1985.
[110]C. F. Gauss. Disquisitiones Arithmeticae. Leipzig:Gerh. Fleischer Iun.,1801.
[111]C. Hermite. Extraits de lettres de M. Hermite a M. Jacobi sur differents objects de la theorie des nombres, deuxieme lettre. journal fur die reine und angewandte mathematik, vol.40, pp.279-290,1850.
[112]G. Hanrot and D. Stehle. Improved analysis of kannan's shortest lattice vector algorithm. Advances in Cryptology-CRYPTO 2007, LNCS, vol.4622, pp.170-186, Springer-Verlag, 2007.
[113]V. Lyubashevsky and D. Micciancio. On bounded distance decoding, unique shortest vec-tors, and the minimum distance problem. Advances in Cryptology-CRYPTO 2009. LNCS, vol.5677, pp.577-594. Springer-Verlag,2009.
[114]O. Regev. Lattices in computer science,2004. Lecture notes of a course given at the Tel Aviv University. Available at the URL http://www.cs.tau.ac.il/odedr/teaching/lattices_fall_2004/.
[2]D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnera-bilities. Journal of Cryptology, vol.10(4), pp.233-260,1997.
[3]D. Boneh and G. Duffee. Cryptanalysis of RSA with private key d less than N0.292. IEEE Transactions on Information Theory, vol.46(4), pp.1339-1349,2000.
[4]J. Lagarias and A.Odlyzko. Solving low-density subset sum problems. Journal of the ACM, vol.32(1), pp.229-246,1985.
[5]A. Odlyzko, The rise and fall of knapsack cryptosystems, Cryptology and Computational Number Theory, vol.42, pp.75-88,1990.
[6]P. Nguyen and J. Stern. Adapting density attacks to low-weight knapsacks. Advances in Cryptology-ASIACRYPT 2005, LNCS, vol.3788, pp.41-58, Springer-Verlag,2005.
[7]D. Coppersmith and A. Shamir. Lattice attacks on NTRU. Advances in Cryptology-EUROCRYPT 1997, LNCS, vol.1233, pp.52-61, Springer-Verlag,1997.
[8]M. Ajtai. Generating hard instances of lattice problems. Complexity of Computations and Proofs, Quaderni di Matematica, vol.13, pp.1-32,2004. Preliminary version in STOC 1996.
[9]W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen,296(4), pp.625-635,1993.
[10]P. Klein. Finding the closest lattice vector when it's unusually close. Proceedings of SODA 2000, pp.937-941,2000.
[11]D. Micciancio and O. Regev. Worst-case to average-case reductions based on Gaussian measures. SIAM Journal on Computing, vol.37(1), pp.267-302,2007. Preliminary version in FOCS 2004.
[12]C. Gentry, C. Peikert and V. Vaikuntanathan. Trapdoors for hard lattices and new crypto-graphic constructions. Proceedings of STOC 2008, pp.197-206,2008.
[13]J. Cai. A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor. Discrete Applied Mathematics, vol.126(1), pp.9-31,2003.
[14]D. Aharonov and O. Regev. Lattice problems in NP n coNP. Journal of the ACM, vol.52(5), pp.749-765,2005. Preliminary version in FOCS 2004.
[15]O. Regev. New lattice-based cryptographic constructions. Journal of the ACM, vol.51(6), pp.899-942,2004. Preliminary version in STOC 2003.
[16]W. Banaszczyk. Inequalites for convex bodies and polar reciprocal lattices in R". Discrete & Computational Geometry, vol.13, pp.217-231,1995.
[17]C. Peikert. Limits on the hardness of lattice problems in lp norms. Computational Complex-ity,2008, vol.17(2), pp.300-351, Preliminary version in Proceedings of CCC 2007.
[18]O. Regev. On lattices, learning with errors, random linear codes, and cryptography. Pro-ceedings of STOC 2005, pp.84-93, ACM,2005.
[19]J. Blomer and J. Seifert. On the complexity of computing short linearly independent vectors and short bases in a lattice. Proceedings of STOC 1999, pp.711-720,1999.
[20]D. Micciancio. Efficient reductions among lattice problems. Proceedings of SODA 2008, pp.84-93,2008.
[21]D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. Proc. Roy. Soc. London A, vol.439,553-558,1992.
[22]C. H. Bennett. Strengths and weaknesses of quantum computing. SIAM Journal on Com-puting, vol.26, pp.1510-1523,1997.
[23]E. R. Berlekamp, R. J. McEliece and H.van Tilborg. On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, vol.24, pp.384-386,1978.
[24]R. J. McEliece. A public-key cryptosystem based on algebraic coding theory. Technical Report DSN progress report 42-44, Jet Propulsion Laboratory, Pasadena,1978.
[25]J. Hoffstein, J. Pipher and J. H. Silverman. NTRU:a ring based public key cryptosystem. Proceedings of ANTS-Ⅲ, LNCS, vol.1423, pp.267-288. Springer-Verlag,1998.
[26]M. R. Garey and D. S. Johnson. Computers and Intractability:A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. New York, NY, USA, pp.128-130,1979.
[27]J. Patarin, L. Goubin and N. Courtois. Improved Algorithms for Isomorphisms of Polyno-mials. Advances in Cryptology-EUROCRYPT 1998, pp.184-200, Springer-Verlag,1998.
[28]J. Patarin. Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88. Designs, Codes and Cryptography, vol.20(2), pp.175-209,2000.
[29]J. Patarin, N. Courtois and L. Goubin. FLASH, a Fast Multivariate Signature Algorithm, CT-RSA 2001, LNCS 2020, pp.298-307, Springer-Verlag,2001.
[30]V. Dubois, P. A. Fouque, A. Shamir and J. Stern. Practical Cryptanalysis of SFLASH. Ad-vances in Cryptology-CRYPTO 2007. LNCS, vol.4622, pp.1-12, Springer-Verlag,2007.
[31]C. Gentry. Fully homomorphic encryption using ideal lattices. Proceedings of STOC 2009, pp.169-178,2009.
[32]C. Gentry. Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness. Ad-vances in Cryptology-CRYPTO 2010, pp.116-137, Springer-Verlag,2010.
[33]C. Gentry, S. Halevi and V. Vaikuntanathan. i-Hop Homomorphic Encryption and Reran-domizable Yao Circuits. Advances in Cryptology-CRYPTO 2010, pp.155-172, Springer-Verlag,2010.
[34]C. Gentry, S. Halevi and V. Vaikuntanathan. A Simple BGN-Type Cryptosystem from LWE. Advances in Cryptology-EUROCRYPT 2010, LNCS, vol.6110, pp.506-522, Springer-Verlag,2010.
[35]C. Gentry and S. Halevi. Implementing Gentry's Fully-Homomorphic Encryption Scheme. Advances in Cryptology-EUROCRYPT 2011, pp.129-148, Springer-Verlag,2011.
[36]C. Gentry and S. Halevi. Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits. Proceedings of FOCS 2011, pp.107-109,2011.
[37]P. van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Math Inst., University of Amsterdam, Amster-dam,1981.
[38]M. Ajtai. The shortest vector problem in l2 is NP-hard for randomized reductions. Proceed-ings of STOC 1998, pp.10-19,1998.
[39]J. Cai, A. Nerurkar. Approximating the SVP to within a factor (1+1/dim) is NP-hard under randomized reductions. Journal of Computer and System Sciences, vol.59(2), pp. 221-239,1999.
[40]D. Micciancio. The shortest vector problem is NP-hard to approximate to within some con-stant. SIAM Journal on Computing, vol.30(6), pp.2008-2035,2001. Preliminary version in FOCS 1998.
[41]S. Khot. Hardness of approximating the shortest vector problem in lattices. Proceedings of FOCS 2004, pp.126-135,2004.
[42]I. Haviv and O. Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Proceedings of STOC 2007, pp.469-477,2007.
[43]I. Dinur. Approximating SVP∞ to within almost-polynomial factors is NP-hard. Theoretical Computer Science, vol.285(1), pp.55-71,2002.
[44]S. Arora, L. Babai, J. Stern and Z. Sweedyk. The hardness of approximate optima in lattices, codes and linear equations. Proceedings of FOCS 1993, pp.724-733,1993.
[45]I. Dinur, G. Kindler, R. Raz and S. Safra. Approximating CVP to within almostpolynomial factors is NP-hard. Combinatorica, vol.23(2), pp.205-243,2003.
[46]O. Regev and R. Rosen. Lattice problems and norm embeddings. Proceedings of STOC 2006, pp.447-456,2006.
[47]O. Goldreich and S. Goldwasser. On the limits of nonapproximability of lattice problems. Journal of Computer and System Sciences, vol.60(3), pp.540-563,2000. Preliminary ver-sion in STOC 1998.
[48]V. Guruswami, D. Micciancio and O. Regev. The complexity of the covering radius problem on lattices and codes. Computational Complexity, vol.14, pp.90-120,2005.
[49]S. Khot. Inapproximability results for computational problems on lattices. The LLL Algo-rithm, Springer-verlag, Berlin, Heidelberg, P.Q.Nguyen and B.Vallee (eds), pp.453-473, 2010.
[50]O. Regev. On the complexity of lattice problems with polynomial approximation factors. The LLL Algorithm, Springer-verlag, Berlin, Heidelberg, P.Q.Nguyen and B.Vallee (eds), pp.475-496,2010.
[51]J. Cai and A. Nerurkar. An Improved Worst- Case to Average-Case Reduction for Lattice Problems. Proceedings of STOC 1997, pp.468-477,1997.
[52]Daniele Micciancio and Chris Peikert. Hardness of SIS and LWE with Small Parameters. http://eprint.iacr.org/2013/069.
[53]C. Peikert and A. Rosen. Lattices that admit logarithmic worst-case to average-case con-nection factors. Proceedings of STOC 2007, pp.478-487,2007.
[54]C. Peikert. Public-key cryptosystems from the worst-case shortest vector problem. Proceed-ings of STOC 2009. pp.333-342.2009.
[55]Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehle. Classical Hardness of Learning with Errors, Proceedings of STOC 2013, (to appear)
[56]A. K. Lenstra, H. W. Lenstra and Jr., L. Lovasz. Factoring polynomials with rational coef-ficients. Mathematische Annalen, vol.261, pp.513-534,1982.
[57]C. P. Schnorr. A hierarchy of polynomial lattice basis reduction algorithms. Theoretical Computer Science, vol.53, pp.201-224,1987.
[58]N. Gama and P. Q. Nguyen. Finding short lattice vectors within mordell's inequality. Pro-ceedings of STOC 2008, pp.207-216.2008.
[59]N. Gama and P. Q. Nguyen. Predicting lattice reduction. Advances in Cryptology-EUROCRYPT 2008, LNCS, vol.4965, pp.31-51. Springer-Verlag,2008.
[60]B. Vallee and A. Vera. Probabilistic Analysis of Lattice reduction Algorithm. The LLL Algorithm-Survey and Applications, pp.71-143,2010.
[61]Y. Chen and P. Q. Nguyen. BKZ 2.0:Better Lattice Security Estimates. Advances in Cryptology-ASIACRYPT 2011, LNCS, vol.7073, pp.1-20, Springer-Verlag,2011.
[62]C. P. Schnorr and M. Euchner. Lattice basis reduction:improved practical algorithms and solving subset sum problems. Mathematics of Programming, vol.66, pp.181-199,1994.
[63]M. Pohst. On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. ACM SIGSAM Bulletin, vol.15(1), pp.37-44,1981.
[64]R. Kannan. Improved algorithms for integer programming and related lattice problems. Proceedings of STOC 1983, pp.193-206.1983.
[65]N. Gama, P. Q. Nguyen and O. Regev. Lattice Enumeration Using Extreme Pruning. Advances in Cryptology-EUROCRYPT 2010, LNCS, vol.6110, pp.257-278. Springer-Verlag,2010.
[66]M. Ajtai, R. Kumar and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. Proceedings of STOC 2001, pp.601-610,2001.
[67]D. Micciancio and P. Voulgaris. Faster exponential time algorithms for the shortest vector problem. Proceedings of SODA 2010, pp.1468-1480, ACM/SIAM,2010.
[68]G. Kabatiansky and V. Levenshtein. Bounds for packings on a sphere and in space. Prob-lemy Peredachi Informatsii, vol.14(1), pp.3-25,1978.
[69]X. Pujol and D. Stehle. Solving the shortest lattice vector problem in time 22.465n. Cryptol-ogy ePrint Archive, Report 2009/605,2009.
[70]P. Q. Nguyen and T. Vidick. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology, vol.2(2), pp.181-207,2008.
[71]X. Wang, M. Liu, C. Tian and Jingguo Bi. Improved Nguyen-Vidick Heuristic Sieve Algo-rithm for Shortest Vector Problem. Proceedings of ASIACCS 2011, pp.1-9.2011.
[72]L. Babai. On Lovasz lattice reduction and the nearest lattice point problem. Combinatorica, vol.6, pp.1-13,1986.
[73]D. Micciancio and P. Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. Proceedings of STOC 2010, pp.351-358,2010.
[74]J. Blomer and S. Naewe. Sampling methods for shortest vectors, closest vectors and suc-cessive minima. Theoretical Computer Science, vol.410(18), pp.1648-1665,2009.
[75]D. Dadush, C. Peikert and S. Vempala. Enumerative lattice algorithms in any norm via mellipsoid coverings. Proceedings of FOCS 2011, pp.580-589,2011.
[76]M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/average-case equiva-lence. Proceedings of STOC 1997, pp.284-293.1997.
[77]D. Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way func-tions from worst-case complexity assumptions. Computational Complexity,16(4), pp.365-411,2007.
[78]D. Micciancio and O. Regev. Post-Quantum Cryptography, chapter Lattice-based Cryptog-raphy. Springer-Verlag, pp.147-191,2008.
[79]O. Goldreich, S. Goldwasser and S. Halevi. Public-key cryptosystems from lattice reduc-tion problems. Advances in Cryptology-CRYPTO 1997, LNCS, vol.1294, pp.112-131. Springer-Verlag,1997.
[80]O. Goldreich, S. Goldwasser and S. Halevi. Collision-free hashing from lattice prob-lems. Technical Report TR96-056, Electronic Colloquium on Computational Complexity (ECCC),1996.
[81]P. Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto'97. Advances in Cryptology-CRYPTO 1999, pp.288-304, Springer-Verlag,1999.
[82]P. Q. Nguyen and J. Stern. The two faces of lattices in cryptology. Proceedings of CaLC 2001, LNCS, vol.2146, pp.146-180, Springer-Verlag,2001.
[83]P. Q. Nguyen and O. Regev. Learning a parallelepiped:Cryptanalysis of GGH and NTRU signatures. Advances in Cryptology-EUROCRYPT 2006, LNCS, vol.4004, pp.271-288, Springer-Verlag,2006.
[84]Leo Ducas and Phong Q. Nguyen. Learning a Zonotope and More:Cryptanalysis of NTRUSign Countermeasures. Advances in Cryptology -ASIACRYPT 2012, Lecture Notes in Computer Science Volume 7658,2012, pp.433-450.
[85]D. Stehle and R. Steinfeld. Making NTRU as Secure as Worst-Case Problems over Ideal Lattices. Advances in Cryptology-EUROCRYPT 2011, LNCS, vol.6632, pp.27-47, Springer-Verlag,2011.
[86]Y. Pan and Y. Deng. A Ciphertext-Only Attack Against the Cai-Cusick Lattice-Based Public-Key Cryptosystem. IEEE Transactions on Information Theory,57(3), pp.1780-1785,2011.
[87]D. Micciancio and S. Goldwasser. Complexity of Lattice Problems:A Cryptographic Per-spective, volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, Massachusetts,2002.
[88]W. Ebeling. Lattices and codes. Advanced Lectures in Mathematics. Friedr. Vieweg & Sohn, Braunschweig, revised edition,2002. A course partially based on lectures by F. Hirzebruch.
[89]J. W. S. Cassels. An introduction to the geometry of numbers. Springer, Berlin, Gottingen Heidelberg,1959.
[90]J. C. Lagarias, H. W. Lenstra and C. P. Schnorr. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica,10(4), pp.333-348,1990.
[91]W. Banaszczyk. Inequalities for convex bodies and polar reciprocal lattices in Rn Ⅱ:Appli-cation of k-convexity. Discrete & Computational Geometry, vol.16, pp.305-311,1996.
[92]R. Fischlin and J. P. Seifert. Tensor-based trapdoors for CVP and their application to public key cryptography. In 7th IMA International Conference-Cryptography and Coding.1999, LNCS, vol.1746, pp.244-257, Springer-Verlag,1999.
[93]D. Micciancio. The hardness of the closest vector problem with preprocessing, IEEE Trans-action on Information Theory, vol.47(3), pp.1212-1215,2001.
[94]U. Feige and D. Micciancio. The inapproximability of lattice and coding problems with preprocessing. Journal of Computer and System Sciences, vol.69(1), pp.45-67,2004.
[95]O. Regev. Improved inapproximability of lattice and coding problems with preprocessing. IEEE Transactions on Information Theory, vol.50(9), pp.2031-2037,2004.
[96]M. Alekhnovich, S. Khot, G. Kindler and N. K. Vishnoi. Hardness of approximating the closest vector problem with pre-processing. Proceedings of FOCS 2005, pp.216-225,2005.
[97]S. Khot, P. Popat, N. Vishnoi:2log1-ε n hardness for the closest vector problem with prepro-cessing. Proceedings of STOC 2012, pp.277-288,2012.
[98]W. Hoeffding. Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association, vol.58, pp.13-30,1963.
[99]R. Kannan. Minkowski's convex body theorem and integer programming. Mathematics of Operations Research, vol.12, pp.415-440,1987.
[100]R. Kannan. Algorithmic geometry of numbers. Annual Review of Computer Science 2, pp. 231-267,1987.
[101]M. Ajtai, R. Kumar and D. Sivakumar. Sampling Short Lattice Vectors and the Closest Lattice Vector Problem. Proceedings of CCC 2002, pp.53-57,2002.
[102]O. Goldreich, D. Micciancio, S. Safra and J. P. Seifert. Approximating shortest lattice vec-tors is not harder than approximating closest lattice vectors. Information Processing Letters, vol.71(2), pp.55-61,1999.
[103]C. Dubey and T. Holenstein. Approximating the Closest Vector Problem Using an Approxi-mate Shortest Vector Oracle. Proceedings of APPROX/RANDOM 2011, LNCS, vol.6845, pp.184-193, Springer-Verlag,2011.
[104]Z. Brakerski, C. Gentry and V. Vaikuntanathan. Fully Homomorphic Encryption with-out Bootstrapping. Electronic Colloquium on Computational Complexity (ECCC) 18,111, 2011.
[105]K. Boroczky and G. Wintsche. Covering the sphere by equal spherical balls. Discrete & Computational Geometry, The Goodman-Pollack Festschrift,237-253,2003.
[106]H. Cohen. A Course in Computational Algebraic Number Theory,2nd edition. Springer-Verlag,1995.
[107]J. H. Conway and Neil J. A. Sloane, Sphere Packings, Lattices and Groups, Springer-Verlag, 3rd edition,1998.
[108]M. van. Dijk, C. Gentry and S. Halevi, et al. Fully Homomorphic Encryption over the Inte-gers. Advances in Cryptology-EUROCRYPT 2010, LNCS, vol.6110. pp.24-43, Springer-Verlag,2010.
[109]U. Fincke and M. Pohst. Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Mathematics of Computation, vol.44(170), pp. 463-471,1985.
[110]C. F. Gauss. Disquisitiones Arithmeticae. Leipzig:Gerh. Fleischer Iun.,1801.
[111]C. Hermite. Extraits de lettres de M. Hermite a M. Jacobi sur differents objects de la theorie des nombres, deuxieme lettre. journal fur die reine und angewandte mathematik, vol.40, pp.279-290,1850.
[112]G. Hanrot and D. Stehle. Improved analysis of kannan's shortest lattice vector algorithm. Advances in Cryptology-CRYPTO 2007, LNCS, vol.4622, pp.170-186, Springer-Verlag, 2007.
[113]V. Lyubashevsky and D. Micciancio. On bounded distance decoding, unique shortest vec-tors, and the minimum distance problem. Advances in Cryptology-CRYPTO 2009. LNCS, vol.5677, pp.577-594. Springer-Verlag,2009.
[114]O. Regev. Lattices in computer science,2004. Lecture notes of a course given at the Tel Aviv University. Available at the URL http://www.cs.tau.ac.il/odedr/teaching/lattices_fall_2004/.