Good and Bad Bases

This note contains the idea that makes lattice cryptography possible. Everything before it was setup.

The observation is that one lattice has many different bases, that some of those bases are far more useful than others, and that working out a good basis from a bad one is itself a hard problem.

01.The same lattice, described twice

Keep the running lattice, generated by $b_1 = (3,1)$ and $b_2 = (1,2)$.

Now take a different pair of vectors:

$$c_1 = (7, 4), \qquad c_2 = (11, 7).$$

These generate exactly the same set of points. Not a similar set. The same one.

To see it, express each new vector in terms of the old ones, and check the coefficients come out as whole numbers:

$$c_1 \;=\; 2 b_1 + 1 b_2 \;=\; (6,2) + (1,2) \;=\; (7,4), \qquad\checkmark$$ $$c_2 \;=\; 3 b_1 + 2 b_2 \;=\; (9,3) + (2,4) \;=\; (11,7). \qquad\checkmark$$

Because those coefficients are integers, every point reachable with $c_1$ and $c_2$ was already reachable with $b_1$ and $b_2$.

The reverse direction has to hold too, or the new pair would generate only part of the lattice. It does:

$$b_1 \;=\; 2 c_1 - 1 c_2 \;=\; (14,8) - (11,7) \;=\; (3,1), \qquad\checkmark$$ $$b_2 \;=\; -3 c_1 + 2 c_2 \;=\; (-21,-12) + (22,14) \;=\; (1,2). \qquad\checkmark$$

Again integers. So the two bases generate each other, which means they generate the same lattice.

02.When does this happen

The bookkeeping above has a compact statement. Collect the change of coefficients into a matrix

$$U \;=\; \begin{pmatrix} 2 & 3 \\ 1 & 2 \end{pmatrix},$$

so that the new basis is $B' = BU$. Then

$$\det U \;=\; 2 \cdot 2 - 3 \cdot 1 \;=\; 4 - 3 \;=\; 1.$$

A square integer matrix whose determinant is $+1$ or $-1$ is called unimodular, and the rule is exactly this:

$\mathcal{L}(B) = \mathcal{L}(B')$ precisely when $B' = BU$ for some unimodular $U$.

The determinant condition is what forces the inverse of $U$ to have integer entries as well, which is what makes the reverse direction work. Any other determinant would give a basis generating only a sparser sub-grid.

There are infinitely many unimodular matrices, so a lattice in dimension $2$ already has infinitely many bases. In dimension $256$ the supply is beyond description.

03.Good and bad

Now compare the two bases as tools rather than as sets.

The original pair, $b_1 = (3,1)$ and $b_2 = (1,2)$, has lengths $\sqrt{10} \approx 3.16$ and $\sqrt{5} \approx 2.24$, and the angle between them is exactly $45^\circ$. Short, and pointing in genuinely different directions.

The second pair, $c_1 = (7,4)$ and $c_2 = (11,7)$, has lengths $\sqrt{65} \approx 8.06$ and $\sqrt{170} \approx 13.04$, and the angle between them is about $2.7^\circ$. Long, and very nearly parallel.

Look at the dots, not the arrows. They are the same points in both panels, in the same places. The lattice did not change. Only the pair of arrows used to describe it did.

Now ask a practical question of each panel. Given some arbitrary point in the plane, which lattice point is nearest?

With the good basis this is easy. The two arrows are short and point in different directions, so you step along $b_1$ until you are roughly in the right place, then along $b_2$ to close the gap, and you land next to the target. Small corrections are available because the steps are small.

With the bad basis it is genuinely awkward. Both arrows point in almost the same direction, so moving sideways at all requires taking a large number of steps along $c_1$ and almost as many back along $c_2$, and the two nearly cancel. To move a short distance perpendicular to the shared direction, you need enormous coefficients. Guessing them is not possible by eye, and in high dimension it is not possible by computer either.

04.Where the trapdoor comes from

Recall the contract from One-Way Functions and Trapdoors. Easy forwards, hard backwards, easy backwards again for whoever holds a secret.

Lattice cryptography fills it in like this:

The private key is a good basis. The public key is a bad basis of the same lattice.

Bob generates a lattice by choosing a good basis, short and nearly perpendicular. He then multiplies by a large unimodular matrix to produce a bad basis of the identical lattice, and publishes that.

Anybody can use the public bad basis to do the forward operation, which amounts to picking a lattice point and pushing it slightly off. Nobody with only the bad basis can undo it, because undoing it means finding the nearest lattice point and the bad basis makes that search hopeless. Bob undoes it immediately, because his good basis makes the same search easy.

The asymmetry does not come from the lattice. Both parties have the same lattice. It comes from which description of it they hold.

05.Why you cannot just improve the bad basis

The obvious objection: if both bases describe the same lattice, why not convert the bad one into a good one and be done?

That conversion is called lattice basis reduction, and it is a real and well-studied algorithm rather than a wish. In two dimensions it is completely solved, by a method due to Gauss, and it takes almost no time. So the picture above is genuinely breakable, exactly as the overview warned.

The best general algorithm is LLL, from Lenstra, Lenstra and Lovász in 1982. It runs in polynomial time and it always terminates with a better basis than it started with. That sounds fatal until you look at how much better. LLL guarantees a vector within a factor of roughly $2^{n/2}$ of the shortest, in dimension $n$. For $n = 2$ that factor is $2$, which is nearly perfect. For $n = 256$ it is $2^{128}$, which is no guarantee at all.

Stronger algorithms exist, principally the BKZ family, which trade running time for a better factor. Choosing lattice parameters for a cryptosystem is essentially the exercise of picking a dimension where the best achievable BKZ factor is still useless to an attacker while the honest party's good basis remains comfortable.

So the answer is that you can improve a bad basis, always, and in the dimensions that matter you cannot improve it nearly enough.