6
$\begingroup$

Consider a full-rank lattice in $\mathbb{R}^n$. Let $\lambda_1$ be the length of the shortest nonzero vector. Given a vector in $\mathbb{R}^n$ we wish to find the nearest lattice vector, as measured by Euclidean distance. In general this is NP-hard. However, we can add the promise that distance to the nearest lattice vector is at most $d$. I'll refer to this as the bounded distance decoding problem. My understanding is that Babai's nearest plane algorithm provably solves this for $d \leq 2^{-c n} \lambda_1$ for some specific value of $c$ (which I don't know but which I believe to be known, and which I think maybe originates from an LLL preprocessing step). My question is whether there is a known way to efficiently go beyond this by a polynomial factor. For example, is there a known polynomial-time algorithm to solve bounded distance decoding at $d = n 2^{-cn} \lambda_1$? The closest to this that I have managed to find in the literature is an algorithm by Klein and subsequent extension by Liu, Ling, and Stehle, which appears to extend beyond the radius of Babai's algorithm by a factor of $k$ at a complexity cost of $n^{k^2}$.

$\endgroup$
3
$\begingroup$

I realize that this is a very late reply, but the answer is yes. You can get an approximation factor of $2^{C n \log \log n/\log n}$ for any constant $C$ in polynomial time. In fact, you can do this with Babai's algorithm together with better preprocessing than LLL.

Unfortunately, I don't know of a great write up for this specific fact.

The main point is simply that the LLL algorithm is not our best polynomial-time algorithm for basis reduction. Instead, our best algorithms are generalizations of this, known as block reduction, or sometimes BKZ reduction (for Block Korkine-Zolotareff, though the name is not very helpful). The idea, originally due to Schnorr [1], is to look at various (projections of) $k$-dimensional sublattices and to find short bases for these (projections of) sublattices. LLL is just the case $k = 2$. I.e., LLL performs a bunch of simple operations on $2 \times 2$ matrices. See, e.g., [2] for a more recent version of this approach.

In polynomial time, we can take $k = C \cdot \log n$ for any constant $C > 0$ (because we can solve more-or-less any lattice problem in exponential time), and the approximation factor that falls out is $2^{C' n \log \log n/\log n}$ for more-or-less any lattice problem that might interest you. As I said, I don't know of a specific write up about this for BDD, but the fact that we can get a $2^{C' n \log \log n/\log n}$-approximation to SVP via this approach was first proven by Ajtai, Kumar, and Sivakumar [3], as a consequence of their famous sieving algorithm. (See Corollary 11 in their paper.) You can then just use a generic reduction from BDD to SVP to get the same result for SVP (see, e.g., [4]).

You can also get this via BKZ reduction together with Babai's algorithm by observing that the approximation factor of Babai's algorithm is controlled by a certain quality measure on the basis---the decay of the Gram-Schmidt vectors---that we can bound for BKZ bases. The best write up that I know of about this property of Babai's algorithm is in my own lecture notes [5].

[1] Schnorr, C. P., A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci. 53, 201-224 (1987). ZBL0642.10030..

[2] Gama, Nicolas; Nguyen, Phong Q., Finding short lattice vectors within Mordell’s inequality, STOC’08. Proceedings of the 40th annual ACM symposium on theory of computing 2008, Victoria, Canada, May 17--20, 2008. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-047-0). 207-216 (2008). ZBL1230.11153.

[3] Ajtai, Miklós; Kumar, Ravi; Sivakumar, D., A sieve algorithm for the shortest lattice vector problem, Proceedings of the thirty-third annual ACM symposium on theory of computing, STOC 2001. Hersonissos, Crete, Greece, July 6--8, 2001. New York, NY: ACM Press (ISBN 1-581-13349-9). 601-610 (2001). ZBL1323.68561.

[4] Lyubashevsky, Vadim; Micciancio, Daniele, On bounded distance decoding, unique shortest vectors, and the minimum distance problem, Halevi, Shai (ed.), Advances in cryptology -- CRYPTO 2009. 29th annual international cryptology conference, Santa Barbara, CA, USA, August 16--20, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03355-1/pbk). Lecture Notes in Computer Science 5677, 577-594 (2009). ZBL1252.94084.

[5] http://www.noahsd.com/mini_lattices/05__babai.pdf .

$\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.