Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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$?
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.
