Blog

Ideal lattices

Ideal lattices have been mentioned a lot recently, particularly in association with Gentry's homomorphic encryption scheme. Exactly what is an ideal lattice?

Let's suppose that we know what a vector space is. With a vector space over the real numbers, for example, we have a set of vectors called a basis, and all of the sums of real multiples of the basis elements form the vector space. If we look at sums of integer multiples of the basis elements, that's a lattice. We can think of the basis as generating a lattice, and to call it a set of generators in that context.

An ideal is a generalization of the idea of "even numbers" or "multiples of 3." A bit more precisely, a set is an ideal if it fulfills two conditions. First, if we add elements in the ideal, we get something else that's also in the ideal. If you add two even numbers you get another even number, for example. We also have the property that if we multiply something in the ideal by something outside the ideal, we get something back in the ideal. That's just like what we get when we multiply any integer by an even integer and get another even integer.

If we have an ideal, we can use its generators as the basis for a lattice, so for every ideal there’s a lattice that we can associate with it in a fairly natural way. Suppose that we look at polynomials with integer coefficients, for example. In this case, if we have the ideal generated by 1 and x, the lattice with basis 1 and x corresponds to this ideal in a natural way.

Not every lattice corresponds to an ideal in the same way, however. If we consider the lattice which has 1 and 2x as its basis, we find that there's no ideal that corresponds to this lattice. The element x, which we can get by multiplying x (from outside the lattice) by 1 (from inside the lattice), isn’t an element of the lattice. This means that this example doesn’t meet the conditions necessary for an ideal, so there’s no ideal that corresponds to the lattice.

Since not every lattice corresponds to an ideal in this way, those that do are interesting, and these are what are called ideal lattices. They’re the framework used to create Gentry’s homomorphic encryption scheme, which is probably the most interesting use of ideal lattices discovered so far.