8
$\begingroup$

What are the main open problems on lattice-basis reduction algorithms (such as LLL)? I am looking for problems satisfying the following two conditions:

(a) their solution would likely be of some practical utility,

(b) their statement is neat and simple. (For instance, I understand that, while the fact that LLL performs better in practice than it does in theory is interesting, important and, by definition, not fully explained, it is also difficult to phrase clearly, due to the fact that "real-world" inputs are not typical, i.e., don't tend to mimic what would seem to be a natural distribution from a mathematical perspective).

Please understand this question to cover also algorithms that find a short vector in a lattice (without finding a full basis). For example - the ratio between the shortest vector that LLL finds and the minimal vector can be as large as exponential on $n$. Finding the minimal vector is, if I understand correctly, computationally hard - but what about finding a short vector whose ratio to the minimal vector is much less than exponential? (I understand there is an algorithm that does give a ratio that is slightly less than exponential - what is it?) How interesting and how hard is this felt to be?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

It is known that a constant approximation is also NP-hard (under randomized reductions), see Daniele Micciancio: The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant (and in general more papers from him).

If you perform the original LLL algorithm, then their are two constants that they choose to be $\frac 12$ and $\frac 34$ that they pick (see (1.4) and (1.5) in the original paper). If you instead use $\epsilon$ and $1-\epsilon$, then you get an algorithm that gives roughly a $(1+\epsilon)^n$ approximation (where $n$ is the dimension) and I think runs in time $2^\frac 1\epsilon$ (though I am not 100% sure about this, but should be something like that).

I guess an open problem is to show that there is or isn't a polynomial time polynomial approximation.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The constant in (1.4) cannot be set to less than 1/2. $\endgroup$
    – Daniele Micciancio
    Commented Sep 30, 2013 at 3:26
  • $\begingroup$ The constant in (1.4) cannot be set to less than 1/2. Choosing values higher than 1/2 can help with numerical stability (when using floating point numbers), but other than that 1/2 is the optimal value. The constant in (1.5) can be set to $\approx 1$, but this only improves the approximation factor to $(2/\sqrt{3})^{n}$. In order to get $(1+\epsilon)^n$ approximation you need better algorithms than LLL. (E.g., Schnorr's.) $\endgroup$
    – Daniele Micciancio
    Commented Sep 30, 2013 at 3:33

You must log in to answer this question.

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