Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  mikeazo Aug 1 at 13:56
5  
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. –  Chris Peikert Aug 1 at 15:02
    
@mikeazo Not necessarily the shortest basis, but one that has been LLL-reduced. –  pg1989 Aug 1 at 18:40
2  
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. –  Chris Peikert Aug 1 at 19:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.