[PDF] An Introduction to Lenstra-Lenstra-Lovasz Lattice Basis Reduction

View - Download An Introduction to Lenstra-Lenstra-Lovasz Lattice Basis Reduction

Previous PDF

Next PDF

An Introduction to Lenstra-Lenstra-Lovasz Lattice

Basis Reduction Algorithm

Xinyue Deng

77 Massachusetts Avenue

Cambridge, MA, 02139

Massachusetts Institute of TechnologyAbstract

Lenstra-Lenstra-Lovasz (LLL) Algorithm is an approximation algorithm of the shortest vector problem, which runs in polynomial time and nds an approximation within an exponential factor of the correct answer. It is a practical method with enough accuracy in solving integer linear program- ming, factorizing polynomials over integers and breaking cryptosystems. In this paper, we introduce its background and implementation, analyze its correctness and performance and discuss its applications. Keywords:LLL-algorithm, Lattice basis reduction1. Introduction A lattice is formed by all linear combinations with integer coecients of the subgroup of any basis inRn, as formulated in Denition 1.1. Denition 1.1(Lattice).A latticeLis a discrete subgroup ofHgenerated by all the integer combinations of the vectors of some basisB: L=mX i=1Zbi=( mX i=1z ibi;wherezi2Z;bi2B) Lattices have many signicant applications in mathematics, and cryp- tography. The Shortest vector problem (SVP) is the most famous and widely studied lattice problem, which consists in nding the shortest non- zero vector,(L) in a given latticeL. The length of the vector can be dened with any norm, but most frequently with Euclidean norm. Another 1 variant of SVP is nding the length of the shortest non-zero vector without nding the vector. SVP has been studied since 19th century due to its connectivity with many problems, like integer linear programming and number theory. The average hardness of SVP made it also an attractive topic in cryptography. In 1910s, mathematician Minowski proved an upper bound of SVP in n- dimensions, which is stated in Theorem 1.1. Theorem 1.1(Minowski's Theorem).Any convex, centrally symmetric bodySof volumevol(S)>2ndet(L)contains a non-zero lattice point. det(L)is the determinant of a latticeL. Proof.LetS0=S=2, and we havevol(S0)> det(L). We claim that there are distinct pointsx;y2S0, such thatxy2 L. To see this, we need to introduce the denition of fundamental region. Denition 1.2(Foundamental Region).A setF Rnof a latticeFif its translationx+F=fx+y:y2 Fg, taken over allx2 L, form a partition ofRn. Consider any fundamental regionFof latticeL,S0can be partitioned into setsS0v=S0\(v+F) for eachv2 L. Then, the translatesS0vv F, andvol(S0)> vol(F), so it means some regions must overlap. This indicates that there must existz2(S0vv)\(S0uu) for some distinct u;v2 L. Therefore, we havex=z+uandy=z+v2S0, and dierence xy=uv2 Lis a lattice point. Finally, we have 2x;2y2Sby the denition and central symmetry of

SandS0. Followed by convexity, the midpoint2x2y2

=xy2S.Corollary 1.1.1.For any n-dimensional latticeL, we have the length of shortest vector(L)>pndet(L)1=n. Proof.For simplicity, we assumedet(L) = 1 by scaling with the factor det(L)1=n. LetSbe a n-dimensional sphere with radiuspnat the origin, andSstrictly contains a [1;1]ncube with side length 2, and volume 2n. Therefore, we havevol(S)>2n. With Theorem 1.1, we conclude there is a non-zero lattice point insideS. Multiplying the scale factor, we have (L)>pndet(L)1=n.However, Minowski's theorem only gives a upper bound of SVP, but we still have no clue on how to nd the shortest vector. Finding shortest non- zero vector in 2-dimensional lattices was solved by Gauss in the 19th century,2 but there was not ecient algorithm of solving SVP in higher dimensions until 1980s. In 1981, mathematician Perter van Emde Boas conjectured that SVP is a NP-hard problem[1]. Up to date, there is no algorithm can solve SVP exactly and run ef- ciently, but Arjen Lenstra, Hendrik Lenstra and Laszlo Lovasz posted a well-known approximation algorithm of SVP in 1982, which can approxi- mate a non-zero lattice vector in n-dimension latticeLof length at most 2 (n1)=2times(L) in polynomial time1. Although the approximation factor seems too large at the rst glance, it is actually better than the Minowski's bound, because it only depends on the number of dimensions, while Mi- nowski's bound depends on the determinant of lattice as well. Practically, LLL algorithm can give a good approximation in reasonable time.

2. Basis Reduction

Basis reduction is a process of reducing the basisBof a latticeLto a shorter basisB0while keepingLthe same. Figure 1 shows a reduced basis

in two dimensional space. Common ways to change the basis but keep theFigure 1: A lattice with two dierent basis in 2 dimension. The determinant of the basis

is shaded. The right basis is reduced and orthogonal. same lattice include:

1. Swap two vectors in the basis.

2. For a vectorbi2B, usebiinstead.1

The approximation factor can be reduced to (2p3

)nif the algorithm is tuned, but it is still exponential inn 3

3. For a vectorbi2B, add a linear combination of other basis vectors

to it. For any vectorvin lattice, it can be expressed as v=mX i=0z ibi: After addition, we have a new basis vectorbj, where b j=bj+X i6=jy ibi;yi2Z:

We can still express latticeLwith the new basis,

v=X i6=jz ibi+zj(bj+X i6=jy ibi): Therefore, the lattice remains the same after changing the basis. Basis reduction can help solving SVP, because if we cannot reduce a basis anymore, the shortest basis vector should be the shortest vector of the lattice. We start by solving the SVP in 2-dimentional case. Denition 2.1(Two dimensional reduced basis).A basis (b1;b2) is said to be reduced if it satises following condition: kb1k kb2k u=b1b2kb1k212 uis called the orthogonal projection coecient, and Figure 2 shows a process of projection. Figure 2 shows the process of orthogonal projection. Based on this denition, we have following theorems. Theorem 2.1.Given a two dimensional latticeLwith basis rank 2, ifis the length of the shortest vector inL, then s2p3 det(L): 4 Figure 2: Orthogonal projection. The setfb1;b2gis the orthogonal basis for the lattice generated by basisfb1;b2g Proof.Suppose we have a reduced basisfb1;b2g, and its orthogonal basis isfb1;b2g.Based on the orthogonal process, we have b

2=b2+ub1

kb2k2=kb2k2+u2kb1k2 kb2k2=kb2k2u2kb1k2 kb1k214 kb1k2=34 kb1k2 kb2k p3 2 kb1k kb2kkb1k=det(L)p3 2 kb1k2 kb1k s2p3 det(L)

is smaller or equal tokb1k, so the theorem is proved.Theorem 2.2.If a basisfb1;b2gis reduced, thenb1is the shortest vector.

Proof.Letxis the shortest vector in latticeL, so we havex=z1b1+z2b2. 5 Then, kxk2=kz1b1+z2b2k2 =kz1b1+z2(b2+ub1)k2 = (z1+z2u)2kb1k2+z22kb2k2 (z1+z2u)2kb1k2+z2234 kb1k2 =kb1k2 Asxis the shortest vector, it is only possible thatkxk2=kb1k2, sob1is the shortest vector.Gauss solved SVP in 2-dimensional lattice in 19th century, and the de- scription of his algorithm is following:

1. Start with basisfb1;b2g, ifkb1k>kb2k, swapb1andb2.

2. Computeu=b1b2kb1k2. Ifu >12

, letmbe the biggest integer that is smaller thanu, and letb2=b2mb1.

3. Ifkb1k>kb2k, then swapb1andb2, and repeat step 2. Otherwise,

outputb1.

3. Gram-Schmidt Orthogonalization

The idea of basis reduction in two dimensional lattice is to nd the orthogonal basis based on the given basis. The basis we found in Gauss algorithm is not exactly orthogonal, but it is the nearest basis we can get. To generalize the algorithm to n-dimensions, we need to nd a way to construct n-dimensional orthogonal basis based on the given basis, which leads us to Gram-Schmidt Orthogonalization. Theorem 3.1(Gram-Schmidt Orthogonalization method).Given a basis fb1;b2;;bmgof a subspaceHmofRn, we dene b 1=b1; b

2=b2u1;2b1;whereu1;2=b2b1b

1b1 b m=bmX iThen,fb1;b2;;bmgis an orthogonal basis ofHm. 6 Proof.This theorem can be proved by induction on the dimension of the vector space.

1. Fork= 1,b1=b1.

2. Fork= 2:fb1;b2gis orthogonal, becauseb2is constructed by

orthogonal projection ofb2ontob1. Figure 2 shows this process. Also,b2is constructed by subtracting a linear combination of other basis vector, sofb1;b2gis a basis ofH2.

3. For 2< km:

fb1;b2;;bkgis orthogonal becausefb1;b2;;bk1g is orthogonal based on the induction hypothesis, andbkis con- structed by orthogonal projection ofbkonto every other vectors. bkis constructed by subtracting a linear combination of other basis vectors, sofb1;b2;;bkgis a basis ofHk.Based on the Theorem 3.1, if we setum;m= 1, then we have b m=mX i=1u i;mbi: Therefore, we can write the above formula in matrix form,B=BU, where basis vectors are columns inBandB. Thus, we have U=0 B BB@u

1;1u1;2u1;n

0u2;2u2;n............

0 0un;n1

C CCA=0 B

BB@1u1;2u1;n

0 1u2;n............

0 011 C CCA Uis a upper trianglar matrix with 1s on the diagonal, sodet(U) = 1. We can then factoringBbyB=QD, D=0 B

BB@kb1k

kb2k kbmk1 C CCA whereQis an orthogonal matrix. Thus, we have

B=QDU:7

Lemma 3.2.For any n-dimensional latticeLwith basisB, we havedet(L) = ni=1bik.

Proof.

det(L) =det(B) =det(Q)det(D)det(U) =det(D) = ni=1kbik:Lemma 3.3.For any n-dimensional latticeLwith basisB, we have the

length of shortest vector(L)minikbik.

Proof.For any non-zero lattice vectorv,

v=kX i=1z ibi kX i=1z ii X j=1u j;ibj =zkbk+k1X j=1k X i=1z iuj;ibj Thus, kvk kzkbkk kbkk:4. LLL Basis Reduction In Section 2, we have introduced a two dimensional reduced basis, and the way to solve the SVP in two-dimension with Gauss algorithm. How- ever, the real interesting SVP still remains unsolved in the higher dimension. In 1997, Ajtai proved SVP is NP-hard to solve exactly under randomized reduction [2], and later, Micciancio proved that SVP is NP-hard to ap- proximate with any factor less thanp2 [3]. Although the SVP is proved unsolvable within realistic time, a good approximation of the SVP would be useful in practical problems. By observing in the two dimensional case, we found that in the process of reducing the basis, we want to make the basis vectors as the most orthogonal as possible. The orthogonal basis cannot be reduced any more. With the Gram-Schmidt orthogonalization in higher8 dimensions, A. Lenstra, H. Lenstra, and L. Lovasz proposed an approxima- tion algorithm of basis reduction in higher dimensions in 1982 [4], which is called LLL basis reduction algorithm. To begin with, they dened LLL reduced basis. Denition 4.1(LLL reduced basis).Letfb1;b2;;bngbe a basis for a n-dimensional LatticeL, andfb1;b2;;bngbe the orthogonal basis generated in Theorem 3.1, and we haveui;k=bkbib ibi. We sayfb1;b2;;bng is a LLL reduced basis if it satises two conditions: (1)8i6=k;ui;k12 (2) For eachi,kbi+1+ui;i+1bik234 kbik2.

Remark.The constant34

is chosen for the simplicity of the paper. Any constant between 14 and 1 can guarantee that the algorithm terminates in polynomial time. Remark.The condition 2 emphasizes the ordering of the basis, like what we did in two dimensional case. Given a basisfb1;b2;;bngin n-dimension, to get a LLL reduced basis, the LLL algorithm works as below.Algorithm 1:LLL AlgorithmInput:fb1;b2;;bng

Repeat two steps until nd the LLL reduced basis

Step 1: Gram-Schmidt orthogonalization

fori= 1tondofork=i1to1dom nearest integer ofuk;i b i bimbk end end

Step 2: Check Condition 2, and swap

fori= 1ton1doifkbi+1+ui;i+1bik2<34 kbik2thenswapbi+1andbi go to step 1 end end9 In step 1, we computed the most orthogonal basis based on Gram- Schmidt orthogonalization, and we check our second condition in step 2. If any basis violates the order, we swap them and repeat step 1. The LLL algorithm gives us an approximation within an exponential factor of the actual shortest vector in polynomial time. First, we show that the reduced basis produced from LLL Algorithm gives a short vector within an exponential faction of the actual shortest vector. Claim 4.1.Iffb1;b2;;bngis a n-dimensional LLL reduced basis of

LatticeL, thenkb1k 2n12

(L), where(L)is the length of the shortest vector ofL. Proof.Based on our denition of LLL reduced basis, we have kbik243 kbi+1+ui;i+1bik2

By expanding the right hand side,

43
kbi+1k2+43 u2i;i+1kbik2

Withui;i+112

, we getquotesdbs_dbs47.pdfusesText_47

[PDF] math SVP urgent pour demain !!!!!!!!!!!!!

[PDF] math terminal l2 exercices corrigés pdf

[PDF] Math thales facile mais

[PDF] math théoreme de pythagore

[PDF] math triangle et cercle

[PDF] math trigonométrie

[PDF] Math trop énèrvant s**vp

[PDF] math type brevet

[PDF] Math un appartement a une superfine de 72 m2

[PDF] math un seul exo

[PDF] Math Urg*ent (docu joint)/ J'ai été absent pendant 2 semaine pour des raisons personnelles

[PDF] MATH URGENT !

[PDF] Math URGENT DEMAIN

[PDF] MATH URGENT N°2

[PDF] Math URGENT!!!!