Skip to content

Elette Boyle: LLL Lattice Basis Reduction Algorithm

by on February 28, 2012

Having just come back from a workshop on lattices, I would have to say my current algorithm of choice is the LLL Lenstra-Lenstra-Lovasz lattice basis reduction algorithm. Given a basis B = (v_1,…,v_n) for a lattice in R^n, the algorithm outputs an new basis for the same lattice whose vectors are shorter and more orthogonal. This is useful for things like trying to find a short vector in a lattice given only a “bad” (ie, skewed, long-vector) basis. Indeed, LLL can be used to solve the Shortest Vector Problem within exponential approximation factors, which is surprisingly nontrivial and useful. What impresses me about this algorithm is that it is very simple and yet has a wide array of applications, by framing (sometimes seemingly unrelated) problems in the language of lattices. Plus, after 30 years it still remains our best tool for many of these problems.

The algorithm loosely works by repeating three steps: (1) computing the Gram Schmidt orthogonalization of the current basis, (2) stepping through the basis vectors v_i and subtracting out the projections onto the Gram Schmidt vectors up to i (rounding to ensure the resulting vector stays in the lattice), and (3) swapping basis vectors occasionally, if a certain condition holds.

An example application of the algorithm is in cryptanalyzing schemes based on knapsack or subset sum. (Yes, this is the cryptographer’s perspective of solving these problems) : ) In the subset sum problem, you are given a modulus N, a huge list of numbers x = (x_1,…,x_n), and a challenge value z such that z = \sum_{i \in I} x_i mod N for some secret subset I of [n]; the problem is to identify the corresponding subset I of values who sum to z. One way to view this is as a lattice problem. Consider the lattice of all vectors y = (y_1,…,y_{n+1}) such that y \cdot (x|-z) = 0: ie, for which \sum_{i=1}^n (x_i)(y_i) = (z)(y_{i+1}). In this language, the desired set I of indices corresponds to a 0-1 vector contained in the lattice, such that its last component is 1. In fact, this is going to be one of the only *short* vectors in this lattice. Thus, one approach to solving the problem is to run the LLL algorithm on a basis of the lattice and use it to find short vectors.

Advertisements

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: