I'm doing a little bit of reading about lattices. I read that if we can find a 'short' basis for our given lattice, we can solve CVP and SVP very efficiently. However, the paper didn't describe an algorithm. Can anyone briefly describe an algorithm for doing this?
$\begingroup$
$\endgroup$
5
-
2$\begingroup$ What do you mean by good and short? If you mean the shortest basis, then I think the answer to SVP is that the shortest vector is guaranteed to be in the shortest basis. For CVP, you probably find the linear combination of the basis vectors that equals the target vector, then round the coefficients to integers (that might not get you exactly there, but will get you close). I have a limited understanding of lattice crypto, which is why I'm not writing an answer. Hopefully someone can confirm my thoughts or point out my errors. $\endgroup$– mikeazoAug 1, 2014 at 13:56
-
11$\begingroup$ Babai's "nearest plane" algorithm will find a lattice point whose distance from the given target vector is "small," where "small" is relative to the lengths of the known basis vectors (more precisely, their Gram-Schmidt vectors). There are many good expositions of Babai's algorithm just a google search away. mikeazo describes a simpler rounding method that also works, but with a somewhat worse bound on the distance. These are the main two algorithms, though they have variants. Note that none of these is guaranteed to find a closest lattice vector to the target, just a "nearby" one. $\endgroup$– Chris PeikertAug 1, 2014 at 15:02
-
$\begingroup$ @mikeazo Not necessarily the shortest basis, but one that has been LLL-reduced. $\endgroup$– pg1989Aug 1, 2014 at 18:40
-
5$\begingroup$ Also: given just a short basis (with no other guarantees), one cannot expect to efficiently solve SVP, or even to find a vector that is "almost" as short as the shortest in the lattice. This is because the "length" of a basis is typically measured by its longest vector, which can be vastly longer than the shortest lattice vector. There are other ways of quantifying the length of a basis, but the same conclusions apply. One exception is an "HKZ-reduced" basis, which must contain a shortest vector by definition. But these are extremely costly to compute and basically never used in crypto. $\endgroup$– Chris PeikertAug 1, 2014 at 19:53
-
1$\begingroup$ I hope this short lecture can help: github.com/lducas/bamenda/blob/master/notes.pdf $\endgroup$– LeoDucasApr 15, 2017 at 5:51
Add a comment
|