Lattice generation from basis?

This might be a very short very obvious answer, because I've yet to come across a question similar to mine in my searches.

Given a lattice L, with a good base B1 and a bad base B2, what stops an attacker from simply re-creating the lattice structure from the public base B2?

It might just be a terminology mix-up on my part, but that's what I recall being the purpose of basis's in regular algebra.

• There's nothing stopping them, the lattice structure isn't secret. Like you say, examining the lattice structure is trivial. The use of lattices in cryptography derives from the fact that even if you know the lattice's structure (e.g. have some basis B), deriving a "good" basis is hard. Jul 15, 2018 at 19:13
• Still, deriving the lattice structure wouldn't mean that one could, for example in a CVP problem, easily output the closest vector? Jul 15, 2018 at 21:44

I'll turn my comment into an answer:

Given a lattice L, with a good base B1 and a bad base B2, what stops an attacker from simply re-creating the lattice structure from the public base B2?

There's nothing stopping them, the lattice structure isn't secret. Like you say, examining the lattice structure is trivial. The use of lattices in cryptography derives from the fact that even if you know the lattice's structure (i.e. have some basis B), deriving a "good" basis is hard.

Still, deriving the lattice structure wouldn't mean that one could, for example in a CVP problem, easily output the closest vector?

No. :) When you visualize this problem in low dimensions, like 2, it seems like it should be that way, no? But in high dimensions, this problem is very difficult when you have a random (i.e. bad) basis.

Try out your technique. Suppose we have $n$ dimensions. Our basis $B$ is a bunch of vectors going in random directions. We want to enumerate the points close to $\mathbf{t}$. How many points could potentially be "close" to the target? How do you generate these points efficiently with your basis $B$?

• "How do you generate these points with your basis B?" By using the basis? :^) Jul 16, 2018 at 9:05
• Sorry, let me rephrase that. How do you generate these points efficiently? Jul 16, 2018 at 9:48
• This might just be a gut feeling, but since quantum is good at finding periodic structures, and lattices are inherently periodic, isn't this whole lattice crypto business just a disaster waiting to happen? Jul 16, 2018 at 10:01
• It's possible, but improbable. If you think you can solve lattice problems more efficiently than the (quantum) algorithms known today, do it! You'll be famous :) Jul 16, 2018 at 12:12
• "But in high dimensions, this problem is very difficult when you have a random (i.e. bad) basis." - More precise would be "But in high dimensions, this problem is very difficult." since even with a good basis this is hard. Lattice-based cryptography generally relies on the hardness of finding good bases from bad bases for security, and is therefore much easier to break than solving random instances of CVP.
– TMM
Dec 26, 2018 at 19:00

Just to complement bkjvbx's answer. To understand why an attacker can't do that, you have to understand the underlying lattice problem that he/she is supposed to solve.

For some problems, a good basis gives you the same power that a bad basis does. For instance, to enumerate the lattice points, or to find the dual of a lattice, or to find the intersection of two lattices... For these problems, the format of the basis doesn't really matters.

On the other hand, some other problems are much easier to solve when the vectors of the available basis are short and nearly orthogonal. For instance, we can solve CVP easily using Babai's algorithm if we have a good basis. However, with a bad basis, this problem seems to be very hard.

And of course, transforming a bad basis in a good one (reducing the basis) is also hard.

• So Gramm-Schmidt has its limitations, I understand? Jul 16, 2018 at 13:43
• Which limitations? I didn't understand. Sorry. Jul 16, 2018 at 13:46
• I could rephrase it as: What stops someone from using G-S to turn a bad base into an orthogonal one? Jul 16, 2018 at 16:12
• @DanielB it doesn't work because Gramm-Schmidt orthogonalization doesn't preserve lattice basis. The output will surely be orthogonal, but probably will not be a basis, because the algorithm uses real linear combinations instead of integer combinations (so, the output will probably have vectors that are not in the lattice). Jul 16, 2018 at 16:16
• @DanielB Take a look at the second section of this PDF to see an example: cseweb.ucsd.edu/classes/wi12/cse206A-a/lec1.pdf Jul 16, 2018 at 16:19