Lecture 20: LLL Algorithm for Lattice Basis Reduction, Application to Integer Programming

Nov. 19, 2009 18.409 An Algorithmist’s Toolkit Lecture 20 Lecturer: Jonathan Kelner 1 Brief Review of Gram-Schmidt and Gauss’s Algorithm Our main task of this lecture is to show a polynomial time algorithm which approximately solves the Shortest Vector Problem (SVP) within a factor of 2O(n) for lattices of dimension n. It may seem that such an algorithm with exponential error bound is either obvious or useless. However, the algorithm of Lenstra, Lenstra and Lovász (LLL) is widely regarded as one of the most beautiful algorithms and is strong enough to give some extremely striking results in both theory and practice. Recall that given a basis b1 , . . . , bn for a vector space (no lattices here yet), we can use the Gram-Schmidt process to construct an orthogonal basis b∗1 , . . . , b∗n such that b∗1 = b1 and b∗k = bk − [projection of bk onto span(b1 , . . . , bk−1 )] for all 2 ≤ k ≤ n (note that we do not normalize b∗k ). In particular, we have that for all k: • span(b1 , . . . , bk ) = span(b∗1 , . . . , b∗k ), k • bk = i=1 μki b∗i , and • μkk = 1. The above conditions can be rewritten as B = M B ∗ , ⎡ μ11 0 0 ... 0 ⎢ μ21 μ22 0 . . . 0 ⎢ M =⎢ . . .. ⎣ .. μn1 μn2 μn3 ... μnn where basis vectors are ⎤ ⎡ 1 0 0 ⎥ ⎢ μ21 1 0 ⎥ ⎢ ⎥ = ⎢ .. . .. ⎦ ⎣ . μn1 μn2 μn3 rows of B and B ∗ , and ⎤ ... 0 ⎥ ... 0 ⎥ ⎥. ⎦ ... 1 Obviously det(M ) = 1, and thus vol(B) = vol(B ∗ ). However, the entries of M are not integers, and thus L(B) =  L(B ∗ ). We have proved last time that for any b ∈ L, ||b|| ≥ mini {||b∗i ||}. We’ll use this to prove useful bound for the shortest vector on lattice. Recall also that last time we saw the Gauss’s algorithm which solves SVP for d = 2. There are two key ingredients of the algorithm. The first is a definition of “reduced basis” which characterizes the discrete version of bases being orthogonal: namely, a basis {u, v} for a 2-d lattices is said to be reduced, if |u| ≤ |v| and |u · v| ≤ |u|2 2 . The second is an efficient procedure that produces a reduced basis. The procedure consists of two stages: First is a Euclid-like process which subtracts a multiple of the shorter vector from the longer one to get a vector as short as possible. The second stage is, if the length ordering is broken, we swap the two vectors and repeat, otherwise (i.e., |u| ≤ |v|) the procedure ends. To make the above procedure obviously terminate in polynomial time, we change the termination criterion to be (1 − )|u| ≤ |v|. This only gives us a (1 − )­ approximation, but is good enough. The basic idea of LLL algorithm is to generalize Gauss’s algorithm to higher dimensions. 20-1 2 LLL Algorithm 2.1 Reduced Basis In order to find a short vector in the lattice, we would like to perform a discrete version of GS procedure. To this end, we need to formalize the notion of being orthogonal in lattice problems. One way to do this is to say that the result of our procedure is “almost orthogonalized” so that doing Gram-Schmidt does not change much. Definition 1 (Reduced Basis) Let {b1 , . . . , bn } be a basis for a lattice L and let M be its GS matrix defined in Section 1. {b1 , . . . , bn } is a reduced basis if it meets the following two conditions: • Condition 1: all the non-diagonal entries of M satisfy |μik | ≤ 1/2. • Condition 2: for each i, ||πSi bi ||2 ≤ 43 ||πSi bi+1 ||2 , where Si is the orthogonal complement of (i.e., the subspace orthogonal to) span(b1 , . . . , bi−1 ), and πSi is the projection operator to Si . Remark The constant 4/3 here is to guarantee polynomial-time termination of the algorithm, but the choice of the exact value is somewhat arbitrary. In fact, any number in (1, 4) will do. Remark Condition 2 is equivalent to ||b∗i+1 + μi+1,i b∗i ||2 ≥ 43 ||b∗i ||2 and one may think it as requiring that the projections of any two successive basis vectors bi and bi+1 onto Si satisfy a gapped norm ordering condition, analogous to what we did in Gauss’s algorithm for 2D case. 2.2 The algorithm Given {b1 , . . . , bn }, the LLL algorithm works as below. LLL Algorithm for SVP Repeat the following two steps until we have a reduced basis Step 1: Gauss Reduction Compute the GS matrix M for i = 1 to n for k = i − 1 to 1 m ← nearest integer to μik bi ← bi − mbk end end Step 2: Swapping if exists i s.t. ||πSi bi ||2 > 43 ||πSi bi+1 ||2 then swap bi and bi+1 go to Step 1 3 Analysis of LLL Algorithm The LLL algorithm looks pretty intuitive, but it is not obvious at all that it converges in polynomial number of steps or gives a good answer to SVP. We’ll see that it indeed works. 20-2 3.1 LLL produces a short vector We first show that reduced basis gives a short vector. Claim 2 If b1 , . . . , bn is a reduced basis, then ||b1 || ≤ 2 Proof n−1 2 λ1 (L). Note that 4 ||πSi bi+1 ||2 3 4 4 4 = ||b∗i+1 + μi+1,i b∗i ||2 = ||b∗i+1 ||2 + μ2i+1,i ||b∗i ||2 3 3 3 4 ∗ 2 1 ∗ 2 ≤ ||bi+1 || + ||bi || , 3 3 ||b∗i ||2 = ||πSi bi ||2 ≤ which gives ||b∗i+1 ||2 ≥ 12 ||b∗i ||2 . By induction on i, we have ||b∗i ||2 ≥ 1 1 ||b∗ ||2 = i−1 ||b1 ||2 . 2i−1 1 2 Recall that ∀b ∈ L, ||b|| ≥ mini ||b∗i ||. Therefore λ1 (L) ≥ mini ||b∗i ||, which combined with the inequality above yields ||b1 ||2 ≤ min{2i−1 ||b∗i ||2 } ≤ 2n−1 min{||b∗i ||2 } ≤ 2n−1 λ1 (L)2 i i as desired. 3.2 Convergence of LLL Now we show that the LLL algorithm terminates in polynomial time. Note that in each iteration of LLL, Step 1 takes polynomial time and Step 2 takes O(1) times. What we need to show is that we only need to repeat Step 1 and Step 2 a polynomial number of times. To this end, we define a potential function as follows: n D(b1 , . . . , bn ) = ||b∗i ||n−i . i=1 It is clear that Step 1 does not change D since we do not change the Gram-Schmidt basis. We are going to show that each iteration of Step 2 decreases D by a constant factor. In Step 2, we swap i and i + 1 only when ||b∗i ||2 > 4/3||πSi bi+1 ||2 ≥ 4/3||b∗i+1 ||2 . Therefore each swapping decreases D by a factor √ of at least 2/ 3, as desired. It is left to show that D can be upper- and lower-bounded. Since ||b∗i || ≤ ||bi ||, the initial value of D can n be upper bounded by (maxi ||bi ||)n(n−1)/2 . On the other hand, we may rewrite D as i=1 |det(Λi )|, where Λi is the lattice spanned by b1 , . . . , bi . Since we assume that the lattice basis vectors are integer-valued, so D is at least 1. In sum, the algorithm must terminate in log2/√3 (maxi ||bi ||)n(n−1)/2 = poly(n) iterations. 4 Application of LLL–Lenstra’s Algorithm for Integer Program­ ming 4.1 Applications of LLL LLL algorithm has many important applications in various fields of computer science. Here are a few (many taken from Regev’s notes): 1. Solve integer programming in bounded dimension as we are going to see next. 20-3 2. Factor polynomials over the integers or rationals. Note that this problem is harder than the same task but over reals, e.g. it needs to distinguish x2 − 1 from x2 − 2. 3. Given an approximation of an algebraic number, find its minimal polynomial. For example, given 0.645751 outputs x2 + 4x − 3. 4. Find integer relations among a set of numbers. A set of real numbers {x1 , . . . , xn } is said to have an integer relation if there exists a set of integers {a1 , . . . , an } not identically zero such that a1 x1 + · · · + an xn = 0. As an example, if we are given arctan(1), arctan(1/5) and arctan(1/239), we should output arctan(1) − 4 arctan(1/5) + arctan(1/239) = 0. How would you find this just given these numbers as decimals? 5. Approximate to SVP, CVP and some other lattice problems. 6. Break a whole bunch of cryptosystems. For example, RSA with low public exponent and many knapsack based cryptographic systems. 7. Build real life algorithms for some NP-hard problems, e.g. subset sum problem. 4.2 4.2.1 Integer Programming in Bounded Dimension Linear, Convex and Integer Programming Consider the following feasibility version of the linear programming problem: • Linear Programming (feasibility) Given: An m × n matrix A and a vector b ∈ Rn Goal: Find a point x ∈ Rn s.t. Ax ≤ b, or determine (with a certificate) that none exists One can show that other versions, such as the optimization version, are equivalent to feasibility version. If we relax the searching regions from polytopes to convex bodies, we get convex programming. • Convex Programming (feasibility) Given: A separation oracle for a convex body K and a promise that – K is contained in a ball of singly exponential radius R – if K is non-empty, it contains a ball of radius r which is at least 1/(singly exponential) Goal: Find a point x ∈ Rn that belongs to K, or determine (with a certificate) that none exists Integer programming is the same thing as above, except that we require the program to produce a point in Zn , not just Rn . Although linear programming and convex programming are known to be in P, integer programming is a well-known NP-complete problem. 4.2.2 Lenstra’s algorithm Theorem 3 (Lenstra) If our polytope/convex body is in Rn for any constant n, then there exists a poly­ nomial time algorithm for integer programming. 20-4 Remark. • For linear programming (LP), the running time of the algorithm will grow exponentially in n, but polynomially in m (the number of constrains) and the number of bits in the inputs. • For convex programming, the running time is polynomial in log(R/r). • As before, we could also ask for maximum of c · x over all x ∈ K ∩ Z n , which is equivalent to the feasibility problem, as we can do a binary search on the whole range of c · x. The main idea of Lenstra’s algorithm is the following. The main difficulty of integer programming comes from the fact that K may not be well-rounded, therefore it could be exponentially large but still contain no integral point, as illustrated in the following figure: x2 x1 + x2 x1 Figure by MIT OpenCourseWare. Figure 1: A not-well-rounded convex body Our first step is thus to change the basis so that K is well-rounded, i.e., K contains a ball of radius 1 and is contained in a ball of radius c(n) for some function that depends only on n. Such a transformation will sends Zn to some lattice L. Now our convex body is well-rounded but the basis of lattice L may be ill-conditioned, as shown in the following figure: Figure by MIT OpenCourseWare. Figure 2: A well-rounded convex body and an ill-conditioned lattice basis 20-5 It turns out that the lattice points are still well-separated and we can remedy the lattice basis by a basis reduction procedure of LLL (i.e., discrete Gram-Schmidt). Finally we chop the lattice space up in some intelligent way and search for lattice points in K. Note that in the first step of Lenstra’s algorithm, what we need is an algorithmic version of Fritz John’s theorem. As we saw in the problem set, there is an efficient algorithm which, for any convex body K specified by a separation oracle, constructs an ellipsoid E such that E(P  ) ⊆ K ⊆ O(n3/2 )E(P  ). Next let T : Rn → Rn be the linear transformation such that E(P  ) is transformed to B(P, 1). Now K is sandwiched between two reasonably-sized balls: B(P, 1) ⊆ T K ⊆ B(P, R), where R = O(n3/2 ) is the radius of the outer ball. Let L = T Zn with basis T e1 , . . . , T en . Our goal is to find a point (if it exists) in T K ∩ T Zn = T K ∩ L. Our next step is to apply the basis reduction in LLL algorithm. We will need the following two lemmas in analyzing Lenstra’s algorithm. The proofs of the lemmas are left as exercises. Lemma 4 Let b1 , . . . , bn be any basis for L with ||b1 ||2 ≤ · · · ≤ ||bn ||2 . Then for every x ∈ Rn , there exists a lattice point y such that 1 (||b1 ||2 + · · · + ||bn ||2 ) 4 1 ≤ n||bn ||2 . 4 Lemma 5 For a reduced basis b1 , . . . , bn ordered as above, ||x − y||2 ≤ n ||bi || ≤ 2n(n−1)/4 det(L). i=1 Consequently, if we let H = span(b1 , . . . , bn−1 ), then 2−n(n−1)/4 ||bn || ≤ dist(H, bn ) ≤ ||bn ||. Let b1 , . . . , bn 1√ n||b n ||. 2 be a reduced basis for L. Applying Lemma 4 gives us a point y ∈ L such that ||y − P || ≤ • case 1: y ∈ T K. We find a point in T K ∩ L. • case 2: y ∈ / T K, hence y ∈ / B(P, 1). Consequently, ||y − P || ≥ 1 and ||bn || ≥ √2 . n This means that the length of bn is not much smaller than R. In the following we partition L along the sublattice “orthogonal” to bn and then apply this process recursively. Let L be the lattice spanned by b1 , . . . , bn−1 and let Li = L + ibn for each i ∈ Z. Clearly L = i∈Z Li . From Lemma 5 the distance between two adjacent hyperplanes is at least dist(bn , span(b1 , . . . , bn−1 )) ≥ 2−n(n−1)/4 ||bn || 2 ≥ √ 2−n(n−1)/4 ||bn || = c1 (n), n where c1 (n) is some function that depends only on n. This implies that the convex body T K can not intersect with too many hyperplanes. That is |{i ∈ Z : Li ∩ B(P, R) = ∅}| ≤ 2R/c1 (n) = c2 (n) for some function c2 (n) that depends only on n. Now we have reduced our original searching problem in n-dimensional space to c2 (n) instances of searching problems in (n − 1)-dimensional space. Therefore we can apply this process recursively and the total running time will be a polynomial in the input size times a function that depends only on n. 20-6