3
$\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!

$\endgroup$
  • $\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 Dec 1 '16 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 Dec 1 '16 at 19:10
5
$\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.

| cite | 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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Basic question: how can CVP be expressed as an SVP in one higher dimension? $\endgroup$ – Elliot Gorokhovsky Dec 30 '18 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 Dec 30 '18 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 Dec 30 '18 at 16:09
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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think MAGMA also has a CVP implementation, and fplll, despite its name, also does. $\endgroup$ – Yoav Kallus Dec 1 '16 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 Dec 1 '16 at 18:37
  • $\begingroup$ Yoav, is fplll a command in magma or where? $\endgroup$ – Hans Dec 1 '16 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 Dec 1 '16 at 19:07
2
$\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.

| cite | improve this answer | |
$\endgroup$

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.