2
$\begingroup$

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.

| improve this question | |
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – bkjvbx Jul 15 '18 at 19:13
  • $\begingroup$ Still, deriving the lattice structure wouldn't mean that one could, for example in a CVP problem, easily output the closest vector? $\endgroup$ – Daniel B Jul 15 '18 at 21:44
2
$\begingroup$

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$?

| improve this answer | |
$\endgroup$
  • $\begingroup$ "How do you generate these points with your basis B?" By using the basis? :^) $\endgroup$ – Daniel B Jul 16 '18 at 9:05
  • $\begingroup$ Sorry, let me rephrase that. How do you generate these points efficiently? $\endgroup$ – bkjvbx Jul 16 '18 at 9:48
  • $\begingroup$ 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? $\endgroup$ – Daniel B Jul 16 '18 at 10:01
  • $\begingroup$ 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 :) $\endgroup$ – bkjvbx Jul 16 '18 at 12:12
  • $\begingroup$ "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. $\endgroup$ – TMM Dec 26 '18 at 19:00
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ So Gramm-Schmidt has its limitations, I understand? $\endgroup$ – Daniel B Jul 16 '18 at 13:43
  • $\begingroup$ Which limitations? I didn't understand. Sorry. $\endgroup$ – Hilder Vitor Lima Pereira Jul 16 '18 at 13:46
  • $\begingroup$ I could rephrase it as: What stops someone from using G-S to turn a bad base into an orthogonal one? $\endgroup$ – Daniel B Jul 16 '18 at 16:12
  • $\begingroup$ @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). $\endgroup$ – Hilder Vitor Lima Pereira Jul 16 '18 at 16:16
  • $\begingroup$ @DanielB Take a look at the second section of this PDF to see an example: cseweb.ucsd.edu/classes/wi12/cse206A-a/lec1.pdf $\endgroup$ – Hilder Vitor Lima Pereira Jul 16 '18 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.