6
$\begingroup$

Let $A$ be a positive definite, real $n \times n$ matrix. This defines a norm on $\mathbb{R}^n$. Now I have a given point $p \in \mathbb{R}^n$ and I want to find the lattice point $x \in \mathbb{Z}^n$ that is closest to $p$ with respect to this norm. This is commonly known as the Closest Vector Problem (CVP) and seems to be very important. So I guess algorithms to solve this should be implemented somewhere. However, I was not able to find something.

Is this there a package for solving this problem for some common mathematical software like Maple, Mathematica, Sage, etc?

Note that I am not interested in some approximation using LLL or so, I want really the (or one) closest vector!

Improve this question
$\endgroup$
2
  • $\begingroup$ I believe this eventually boils down to checking all lattice vectors within a certain box around zero, depending on $A$. If you do that smartly (see ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777278-8/…) you might save some time, but depending on your application a rougher (=larger) box doesn't matter. Or your dimension is so large that you cannot solve it anyways... $\endgroup$
    – senegrom
    Commented Dec 1, 2016 at 18:34
  • $\begingroup$ Am I missing something or is your reference about the shortest vector problem rather than the closest vector problem (I think the former is only a spectal case of the latter). $\endgroup$
    – Hans
    Commented Dec 1, 2016 at 19:10

5 Answers 5

Reset to default
6
$\begingroup$

fplll (available here: https://github.com/fplll/fplll), a C++ implementation of a selection of lattice algorithms, has a CVP solver:

It also includes a floating-point implementation of the Kannan-Fincke-Pohst algorithm [K83,FP85] that finds a shortest non-zero lattice vector. For the same task, the GaussSieve algorithm [MV10] is also available in fplll. Finally, it contains a variant of the enumeration algorithm that computes a lattice vector closest to a given vector belonging to the real span of the lattice.

Magma has a CVP solver. Details here: https://magma.maths.usyd.edu.au/magma/overview/2/17/9/

Magma includes a highly optimized algorithm for enumerating all short vectors in a lattice with given norm. This algorithm, developed by Damien Stehlë, is used for computing the minimum, the shortest vectors, short vectors in a given range, and vectors close to or closest to a given vector (possibly) outside the lattice.

Improve this answer
$\endgroup$
4
$\begingroup$

Victor Shoup's NTL package has an implementation of LLL-BKZ. The "B" in the name stands for "block". If you set the block size equal to the dimension of the lattice, then it should return a list of short basis vectors, with the smallest vector in the basis being a solution to SVP. I guess for CVP you can try to set up your CVP as an SVP in one higher dimension.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Basic question: how can CVP be expressed as an SVP in one higher dimension? $\endgroup$
    – Elliot Gorokhovsky
    Commented Dec 30, 2018 at 15:12
  • 1
    $\begingroup$ @ElliotGorokhovsky Let $A$ be an $n$-by-$n$ matrix whose rows are the given basis for $L$, and let $\boldsymbol{v}$. Form a new matrix $B$ whose upper right is $A$, whose last column is $0,0,\ldots,0,c$, and whose last row is $(\boldsymbol{v},c)$. Then one adjust $c$, depending on the length of $\boldsymbol{v}$ and the discriminant of $A$, so that a small vector in $B$ is likely to consist of a linear combination of its first $n$ rows together with exactly $\pm1$ copy of its bottom row. And that expresses $\boldsymbol v$ as a lattice vector plus a small error, so approximately solves CVP. $\endgroup$
    – Joe Silverman
    Commented Dec 30, 2018 at 15:53
  • $\begingroup$ Thanks for the quick response! Could you explain a bit more how a $c$ with the desired property could be chosen? (Or at least why such a $c$ should exist?) $\endgroup$
    – Elliot Gorokhovsky
    Commented Dec 30, 2018 at 16:09
4
$\begingroup$

Sage provides function closest_vector() in the module free_module_integer.

Improve this answer
$\endgroup$
3
$\begingroup$

Mathematica has LatticeReduce, an implementation of a variant of the LLL algorithm.

Victor Shoup's NTL has a C++ implementation of the LLL algorithm.

Babai's approximation algorithm for CVP, the nearest plane algorithm, uses the LLL algorithm. Take a look at Regev's lecture notes. You may also want to take a look at Peikert's lecture notes.

Also, take a look at Peikert's comments on this question on the Cryptography Stack Exchange.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I think MAGMA also has a CVP implementation, and fplll, despite its name, also does. $\endgroup$
    – Yoav Kallus
    Commented Dec 1, 2016 at 18:35
  • $\begingroup$ Are you sure that these do what they should? I thought that the LLL algorithm just gives a close vector (which is close enough for many applications) but not necessarily the closest one? $\endgroup$
    – Hans
    Commented Dec 1, 2016 at 18:37
  • $\begingroup$ Yoav, is fplll a command in magma or where? $\endgroup$
    – Hans
    Commented Dec 1, 2016 at 18:38
  • 3
    $\begingroup$ I am totally aware of the fact that this is a hard problem. I'm not hoping for short running time, but it should be possible to compute it in reasonable time for small $n$ and I am looking for implementations of this. $\endgroup$
    – Hans
    Commented Dec 1, 2016 at 19:07
3
$\begingroup$

It can be formulated as an integer quadratic programming problem, for which you can use e.g. Cplex.

Of course, running time for this approach is likely to be exponential in $n$, but in practice it should be considerably better than exhaustive search in a box.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .