LLL算法的介绍应用.pdf-资料库

99be270c-dede-4a69-b74c-586c8001fe9d.pdf-第1页.png

第1页 / 共27页

99be270c-dede-4a69-b74c-586c8001fe9d.pdf-第2页.png

第2页 / 共27页

99be270c-dede-4a69-b74c-586c8001fe9d.pdf-第3页.png

第3页 / 共27页

99be270c-dede-4a69-b74c-586c8001fe9d.pdf-第4页.png

第4页 / 共27页

99be270c-dede-4a69-b74c-586c8001fe9d.pdf-第5页.png

第5页 / 共27页

99be270c-dede-4a69-b74c-586c8001fe9d.pdf-第6页.png

第6页 / 共27页

99be270c-dede-4a69-b74c-586c8001fe9d.pdf-第7页.png

第7页 / 共27页

99be270c-dede-4a69-b74c-586c8001fe9d.pdf-第8页.png

第8页 / 共27页

LLL lattice basis reduction algorithm Helfer Etienne 21.03.2010 Contents 1 Lattice 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Deﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Shortest vector problem . . . . . . . . . . . . . . . . . . . . . 2 Basis reduction 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Rank 2 basis reduction . . . . . . . . . . . . . . . . . . . . . . 2.3 LLL basis reduction . . . . . . . . . . . . . . . . . . . . . . . 3 LLL basis reduction for solving RSA problem 3.1 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Coppersmith . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Implementation and examples 4.1 LLL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Coppersmith . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 RSA attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Acknowledgements 6 Bibliography 1 Lattice 1.1 Introduction 1 1 2 3 5 6 6 7 10 17 17 18 21 21 22 24 26 27 27 Since the LLL lattice reduction basis algorithm operates on a lattice it is important to understand what is it. Many concepts in Lattice theory are related with linear algebra : a lattice can be represented with the matrix 1

of its basis, it has a determinant, and so on. Later we will need linear algebra methods and matrix properties for the LLL algorithm. I won’t give a complete and precise view of the lattice theory but favor the geometrical point of view and focus on the elements that are needed to understand LLL basis reduction. 1.2 Deﬁnition A lattice is a discrete subgroup of an Euclidean vector space. In general the vector space is Rn or a subspace of Rn. It is conveniant to describe a lattice using its basis. The basis of a lattice is a set of linearly independent vectors in Rn which can generate the lattice by combining them. Notice that diﬀerent bases can generate the same lattice (cf. ﬁgure 1). Deﬁnition 1. A set of vectors {b1, b2, . . . , bm} in Rn is linearly indepen- dent if the equation c1b1 + c2b2 + ··· + cmbm = 0 where ci ∈ R (1) accepts only the trivial solution c1 = c2 = ··· = cm = 0 Theorem 1. If a set of vectors in Rn contains more vectors than n (if m > n), then this set of vectors is not linearly independent. Deﬁnition 2. A subspace of Rn is a an arbitrary set H that has the following properties : 1. the nul vector 0 is an element of H 2. H is close under addition : for every u and v in H, their sum u + v is an element of H 3. H is close under scalar multiplication : for every u in H and scalar c, the vector cu is an element of H Notice that Rn is a subspace of Rn Deﬁnition 3. A basis B of a subspace H of Rn is a set of linearly indepen- dent vectors in Rn that generates H. Deﬁnition 4. A lattice Λ is a discrete subgroup of H generated by all the integer combinations of the vectors of some basis B : Λ = Zbi = zibi where zi ∈ Z, bi ∈ Rn i=1 i=1 2 B = {b1, b2, ..., bm} where bi ∈ Rn H = Rbi = cibi where ci ∈ R, bi ∈ Rn m i=1 m m m i=1 (2) (3) (4)

Deﬁnition 5. The rank m of a lattice Λ generated by a basis B of a subspace H of Rn is the number of vectors in B. Theorem 1 implies that m ≤ n. If m = n then H is Rn and Λ is a full rank lattice. b2 b1 b2 b1 b2 b1 b1 Figure 1: Examples of lattices generated with diﬀerent bases in R2. The ﬁrst and the second lattice are the same. The ﬁrst three lattices are rank 2 and the fourth is rank 1. 1.3 Determinant The determinant of a lattice Λ (det Λ) is an important numerical invariant of Λ. Geometrically speaking, det Λ is the volume of the parallelepiped spanned by the basis. The determinant does not depend on the choice of the basis. Another more general perspective is to consider det Λ as the inverse of the volume density of elements in Λ. Deﬁnition 6. The volume of a n-dimensional ball B of radius r is given by proposition where n 2 ! is inductively deﬁned by 0! = 1, 1 volB(r, n) = rnvolB(1, n) = √ 2 , and n 2 ! = n 2 ! π 2 ! = n 2 rnπn/2 (5) n−2 2 ! Deﬁnition 7 (Determinant deﬁnition). det Λ is the volume of the m-dimensional ball B, where m is the rank of Λ, divided by the number of elements belonging to Λ in B when radius of B tends to inﬁnity. det Λ = lim r→∞ (6) Theorem 2. Given a lattice Λ with a basis {b1, b2, . . . , bi} then the deter- minant is equal to the volume of the parallelepiped spanned by b1, b2, . . . , bm. #{y ∈ Λ where y ≤ r} volB(r, m) Proof. Argument : It is coherent with our deﬁnition because when the ra- dius of the ball r is big then volB(r, n) ≈ #{y ∈ Λ where y ≤ r} times the volume of the parallelepiped. Figure 2 is an illustration of this approxi- mation. 3

Notice that for a full rank lattice, from linear algebra we know that | det [b1 b2 . . . bn]| is the volume of the parallelepiped spanned by the basis vectors b1, b2, . . . , bn, so det Λ = | det [b1 b2 . . . bn]| Theorem 3 (Hadamard’s inequality). The determinant is less than or equal to the product of the norm of the basis vectors. det Λ ≤ m bi (7) i=1 Equality holds if and only if the vectors bi are pairwise orthogonal (if bi · bj = 0 when i = j and · is the scalar product). Figure 2: Illustration with a lattice of rank 2 that the volume of the ball approximates det Λ times the number of elements in Λ lying inside the ball. 4

r Figure 3: A lattice Λ of rank 3. On the left det Λ is represented as the ball and the elements of Λ inside. On the right det Λ is represented as the volume of the parallelepiped spanned by a basis of Λ. 1.4 Shortest vector problem The shortest vector is the following : given a lattice Λ ﬁnd a shortest vector v among the set of vectors going from the zero element to any non-zero element x in Λ. Notice that −v is also a shortest vector. In an algorithmic context, one may take ’shortest possible’ to mean : shortest possible given the time one is willing to spend. The main theoretical result about this is the Minkowski’s theorem which gives us an upper bound for the shortest vector. Theorem 4 ( Minkowski’s theorem ). Given a lattice Λ of rank m, if λ is the norm of the shortest vector then : λ ≤ 2√ π m 2 1 m det Λ ! 1 m (8) Proof. Argument : If we place a m-dimensional ball of radius λ 2 on each element of Λ one can see that the balls are pairwise disjoint (cf Figure 4). From that one deduces that the volume of the ball is less than or equal than the determinant and the theorem follows : volB( , m) ≤ det Λ λ 2 πm/2 m 2 ! m λ 2 ≤ det Λ 5

m ≤ m 2 ! det Λ λ 2 m 2 π 1 λ ≤ 2√ π m 2 m det Λ ! 1 m Equality holds only with lattices of rank 1. λ 2 Figure 4: Illustration of a rank 2 lattice. One can see that the balls of radius λ 2 are pairwise disjoint. From that and the fact that the determinant is the inverse of the volume density of elements one concludes that det Λ < πλ2 4 . 2 Basis reduction 2.1 Introduction The idea of the basis reduction is to change a basis B of a lattice Λ into a shorter basis B’ such that Λ remains the same. To do this we can use these following operations : 1. Swapping 2 vectors of the basis. As the swapping changes only the order of vectors in the basis it is trivial that Λ is not aﬀected. 2. Replacing bj by −bj. It is trivial that Λ is not aﬀected. 3. Adding (or substracting) to a vector bj a linear and discrete combina- tion of the other vectors of the basis. The lattice is not aﬀected because 6

a discrete combination of the vectors of the basis : v =m basis : bj ← bj+ i=j zibi+zj(bj− tion of the vectors of the new basis : v = if we take an arbitrary vector v which belongs to Λ we can express it as i=1 zibi and if then we replace bj by a discrete combination of the other vectors of the i=j yibi we can still express v as a discrete combina- i=j yibi). In a similar way we can show that if v belongs not to Λ, then we can- not express it with a discrete combination of the new basis. It follows that the 2 bases generate the exact same lattice. Basis reduction can be used to solve the shortest vector problem in the sense that the shortest vector of the basis (b1 in the basis reduction algorithms we will see) is very short. In rank 2 for a reduced basis we have that b1 is the shortest vector of Λ and we can get it in polynomial time. But for higher ranks there is no known algorithms that ﬁnds the shortest vector in polynomial time. The LLL basis reduction algorithm ﬁnds a fairly short vector in polynomial time and it is often suﬃcient for applications. (7, 9) (3, 5) (−1, 1) (4, 4) Figure 5: A lattice of rank 2 with two diﬀerent bases. The determinant is depicted as the area of the parallelogram deﬁned by the basis. The second basis is reduced and orthogonal. 2.2 Rank 2 basis reduction Basis reduction of rank 2 lattices is easy to understand and plays a pivotal role in LLL basis reduction algorithm. We start with a basis {b1, b2} and we try to reduce it. If b1 is shorter than b2 the intuitive approach is to substract from b2 an integer multiple z of b1. We want to choose z such that the new vector b2 − zb1 is as short as possible. To solve this problem we take for z the coeﬃcient u of the orthogonal projection of b2 on b1 (cf 7

ﬁgure 6) rounded to the nearest integer. We repeat this process until we can no longer reduce the basis. Deﬁnition 8 (Reduced basis in rank 2). A basis {b1, b2} is said to be reduced if and only if the norm of b1 is less than or equal to the norm of b2 and the absolute value of the orthogonal projection coeﬀecient u = b1·b2 is b1·b1 less than or equal to 1 2 . {b1, b2} is reduced ⇐⇒ b1 ≤ b2 and |b1 · b2| b1 · b1 ≤ 1 2 (9) To picture this observe that in ﬁgure 7 given an arbitrary b1 the basis is reduced if and only if b2 lies on the shaded area. Theorem 5. Given a lattice Λ of rank 2, if λ is the norm of the shortest vector then : λ ≤ 2√ 3 det Λ (10) Proof. Suppose that we have a reduced basis {b1, b2} of Λ. Using orthog- onal projection and the properties of reduced bases we get : b2 = b∗ b22 = b∗ 2 + ub1 22 + u2b12 22 = b22 − u2b12 ≥ b12 − 1 4 b∗ b12 = b12 3 4 b∗ 2 ≥ √ 3 2 b1 √ b∗ 2b1 = det Λ ≥ 3 2 det Λ ≥ b1 2√ 3 b12 It gives us for rank 2 lattice a new bound for λ which is better than the bound given by the Minkowski’s theorem (cf theorem 4). Theorem 6. If a basis {b1, b2} of Λ is reduced then b1 is a shortest vector of Λ. {b1, b2} is reduced ⇒ b1 is a shortest vector. (11) Proof. Let x be a shortest vector of Λ − {0}. We can express it with the reduced basis : x = z1b1 + z2b2. We have x2 = z1b1 + z2(b∗ 2 + ub1)2 = (z1 − z2u)2b12 + z2 2 ≥ (z1 − z2u)2b12 + 3 2b∗ x2 ≥ (z1 − z2u)2b12 + 2b12. 4 z2 2b12 z2 3 4 8

资料库

LLL算法的介绍应用.pdf

相关推荐

开发技术

热门标签

最新资料