2
$\begingroup$

Let's suppose I've given a lattice $L$. I'm allowed to spend as much pre-computation as I want to produce a poly-sized advice string, and I use it to find the best basis possible for the lattice.

Then I am given CVP challenges. I use Babai's nearest plane, with my high-quality basis, to solve CVP. How well do I do?

I can see from, e.g., http://www.noahsd.com/mini_lattices/05__babai.pdf, that I can solve $\gamma$-CVP with

$$\gamma = \sqrt{n+1}\max_{i\geq j}\frac{\Vert b_j^*\Vert}{\Vert b_i^*\Vert}$$

where $b_i^*$ are the Gram-Schmidt vectors from the lattice. So I would want this value to be as small as possible. But what guarantees can I have about this? Is there a worst-case lattice where this quantity is exponentially large? Is there an average-case behaviour?

I can see lots written to bound this quantity after LLL, or after some quantity of BKZ, but I want to know about the best possible.

Improve this question
$\endgroup$
3
  • $\begingroup$ Worth mentioning that you need to introduce some sort of normalization, otherwise a lattice like $\mathbb{Z}^{n-1}\oplus 2^n \mathbb{Z}$ trivially has $\gamma \geq \sqrt{n}2^n$, but you probably view this as "boring". This can be fixed by mandating that $\det L = 1$, or studying $\gamma / \sqrt[n]{\det L}$. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Oct 31 at 20:41
  • $\begingroup$ In that lattice, can't I take $b_n=b_n^*=(0,\dots,0,2^n)$ and $b_i=b_i^*=e_i$ for $i\leq n-1$, so that I actually get $\gamma\leq \sqrt{n+1}$? $\endgroup$
    – Sam Jaques
    Commented Nov 1 at 14:44
  • $\begingroup$ Yes, for some reason when I suggested that lattice I thought the quotient was $\lVert b_{\color{red}i}^*\rVert / \lVert b_{\color{red}j}^*\rVert$. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Nov 2 at 0:07

1 Answer 1

Reset to default
1
$\begingroup$

Theorem 2 of KF17 (seems to) state that one can take $\frac{\lVert b_j^*\rVert}{\lVert b_i^*\rVert} \leq \beta^{O((j-i)/\beta + \log \beta)}$ for any $\beta \leq n/2$. Setting $\beta = n/2$ and $j = n, i= 1$, this gives a bound of $\gamma \leq \sqrt{n}2^{O((\log n)^2)}$, so it does not appear that this quantity can be exponentially large.

It is also worth mentioning that your question may be rephrased in terms of the parameters $\ell_i := \log \lVert b_i^*\rVert$. This parameterization has been somewhat popular in analyzing lattice reduction lately. See Section 3 of Henninger and Ryan for a brief survey of them. Of interest to you is probably Figure 1, where Henninger and Ryan depict experimental results how $\vec \ell$ "transforms" after LLL reduction for various (average-case) input distributions.

Henninger and Ryan even investigate the quantity $ \mathsf{spread}(L) = \max_i \ell_i - \min_i \ell_i, $ e.g. something similar to your quantity. Your exact quantity appears in the proof of Theorem 2 (and is related to their novel notion of reduced basis, Definition 3). That being said though, I can only use their work to get $\lVert b_j^*\rVert/\lVert b_i^*\rVert \leq 2^{O(n)}$. As they only consider poly-time lattice reduction, this makes some degree of sense.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Those are good references! But the best bound is still super-polynomial in $n$. I don't know whether that's to be expected or not, so I'll leave this as unanswered for a few more days. The dream would be to have $\gamma=O(1)$ with sufficient precomputation... $\endgroup$
    – Sam Jaques
    Commented Nov 4 at 22:01
  • $\begingroup$ @SamJaques Do you require the preprocessed information to be a basis? If it is just some general poly-sized amount of advice, you can do better. The problem is "Search CVPP" (CVP with Preprocessing). See for example On the Closest Vector Problem with a Distance Guarantee by Dadush, Regev, and Stephens-Davidowitz. They get approximation factor $O(n/\sqrt{\log n})$ with other techniques, and mention in Section 1.2 that the bound I quoted above (using KZ basis) is the best known (as of 10 years ago). $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Nov 4 at 22:31
  • $\begingroup$ This work also appears to be relevant, and more specifically focused on your problem. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Nov 4 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.