1
$\begingroup$

I've been looking through https://courses.maths.ox.ac.uk/node/view_material/12662 and it mentions that:

Some bases make SVP easier:

  • A “good” basis has shorter vector norms
  • A “good” basis has nearly orthogonal vectors

I assume the reason for shorter vector norms being helpful is that there if we use an algorithm such as LLL, we will have a better starting point and that there will be less to reduce? However, I'm unsure exactly why nearly orthogonal basis vectors makes SVP easier. Is it only because it somehow makes it easier for algorithms such as LLL(-BKZ) to reduce the basis vectors?

$\endgroup$
0
$\begingroup$

Is it only because it somehow makes it easier for algorithms such as LLL(-BKZ) to reduce the basis vectors?

You have this somewhat backwards --- the point of basis reduction is to find a basis that is "shorter" and "more orthogonal", which you then use for useful applications.

Babai's nearest planes is a fairly well-known algorithm to solve an approximate form of CVP, that is defined relative to some fixed basis $B = [b_1,\dots,b_n]$ of a lattice. If $x\in\mathbb{R}^n$, and:

  1. $v$ is the output of Babai's nearest planes, and
  2. $v_{opt}$ is the closest vector to $x$,

then one can prove that: $$\lVert v-v_{opt}\rVert_2^2 \leq \frac{1}{4}\sum_{i = 1}^n \lVert b_i^*\rVert_2^2$$ where $\{b_1^*,\dots, b_n^*\}$ is the Gram-Schmidt orthogonalization of $B$. Note that as the Gram-Schmidt orthogonalization applies solely elementary operations, one has that:

$$\det([b_1^*,\dots, b_n^*]) = \det B$$

e.g. the total product $\prod_{i=1}^n \lVert b_i^*\rVert_2 = \det B$ is kept invariant. It should be easy to see that the error bound in Babai's nearest planes will be minimized if this "$\det B$ amount of mass" is "spread out evenly" through all of $\{b_1^*,\dots, b_n^*\}$, e.g. if the basis is short and nearly orthogonal.

$\endgroup$
2
  • $\begingroup$ Thanks. I understand how having basis that is fairly short and orthogonal would allow for Babai's to help solve CVP, but I still don't understand how such basis would help solve SVP? $\endgroup$
    – Aishimaru
    May 26 '21 at 9:26
  • $\begingroup$ @Aishimaru there is an efficient reduction from $\gamma$-SVP to $\gamma$-CVP. How I have phrased things means this isn't immediately applicable (the error bound I have stated is not absolute, e.g. is not some multiplicative approximation error bound), but if one reproves the theorem with the above error bound you'll get some additive approximation to the shortest vector in terms of $\sum_{i = 1}^n \lVert b_i^*\rVert_2^2$. $\endgroup$
    – Mark
    May 26 '21 at 17:04

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.