1
$\begingroup$

I am studying the Shortest Vector Problem and I have some troubles understanding the actual Lovàsz condition used in the LLL algorithm.

On the one hand, the original LLL article, the Springer book "The LLL Algorithm" and A Complete Analysis of the BKZ Lattice Reduction Algorithm state that the LLL algorithm outputs a reduced basis meaning that:

  • $|\mu_{i,j}| \le 0.5\quad\forall 1\le j < i \le n$ and
  • $\delta\|b_k^*\|^2 \le \|b^*_{k+1} + \mu_{k+1,k}b^*_k\|^2$

On the other hand, other sources, like International Symposium on Mathematics, Quantum Theory, and Cryptography, page 198, Wikipedia and these course notes state that the LLL algorithm outputs a reduced basis meaning that:

  • $|\mu_{i,j}| \le 0.5\quad\forall 1\le j < i \le n$ and
  • $\delta\|b_k^*\|^2 \le \|b^*_{k+1}\|^2 + \mu_{k+1,k}^2\|b^*_k\|^2$

I am a bit confused as I cannot even apply the triangle inequality to infer the latter from the former.

Any hint is appreciated.

$\endgroup$
5
  • 1
    $\begingroup$ Little search Prove Euclidean norm satisfies the triangle inequality $\endgroup$
    – kelalaka
    Commented Nov 3, 2023 at 20:05
  • 1
    $\begingroup$ Maybe the closest answer is about the definition of a norm by Mark On the spectral norm in lattice-based cryptography $\endgroup$
    – kelalaka
    Commented Nov 3, 2023 at 20:16
  • $\begingroup$ I thought of triangle inequality but while $\|b^*_{k+1} + \mu_{k+1,k} b^*_k\| \le \|b^*_{k+1}\| + \mu_{k+1,k}\|b^*_k\|$ is valid, if we square it we obtain $\|b^*_{k+1} + \mu_{k+1,k} b^*_k\|^2 \le \|b^*_{k+1}\|^2 + \mu_{k+1,k}^2\|b^*_k\|^2 \mathbf{+ 2\mu_{k+1,k}\|b^*_{k+1}\|\|b^*_k\|}$. I know no ways to check if $\|b^*_{k+1} + \mu_{k+1,k} b^*_k\|^2 \le \|b^*_{k+1}\|^2 + \mu_{k+1,k}^2\|b^*_k\|^2$ is also true (which is what we want). Or am I missing something? $\endgroup$ Commented Nov 3, 2023 at 20:57
  • $\begingroup$ And even if the triangle inequality explained the validity of the second definition, they are not equivalent: if LLL returns a basis $B$ that followed the first definition, then, assuming the inequality can be applied, it follows also the second one, but the opposite is not true (if $B$ follows the second "version" of the Lovász condition, we have no ways to say it also follows the first). PS: a small note, I'm unable to edit my former comment, but there is a typo: $\|b^*_{k+1}+\mu_{k+1,k}b^*_k\|\le\|b^*_{k+1}\|+\mathbf{|\mu_{k+1,k}|}\|b^*_k\|$ $\endgroup$ Commented Nov 3, 2023 at 21:06
  • $\begingroup$ It is worth mentioning that often when working with the squared euclidean norm $\lVert x+y\rVert_2^2$, one may apply convexity of $x\mapsto \lVert x\rVert_2^2$ as a substitute for the triangle inequality. Working on this briefly I it hasn't sufficed (for me) to show equivalence, but it might plausibly be useful anyway, hence this comment. $\endgroup$
    – Mark Schultz-Wu
    Commented Nov 3, 2023 at 21:29

1 Answer 1

2
$\begingroup$

Actual answer to your question:

For the Euclidean norm, both conditions are equivalent because $b^*_{k}$ and $b^*_{k+1}$ are orthogonal.

Remember that they are obtained via Gram-Schmidt orthogonalization, thus, $b^*_{k} \cdot b^*_{k+1} = 0$.

Also, remember that for any vectors $u$ and $v$, because the Euclidean norm is $\|u\| = \sqrt{u \cdot u}$, we have

$\|u + v\|^2 = (u + v) \cdot (u + v) = u\cdot u + v \cdot v + 2\cdot u\cdot v = \|u\|^2+\|v\|^2 + 2\cdot u\cdot v$

Then, if $u$ and $v$ are orthogonal, we obtain $\|u + v\|^2 = (u + v) \cdot (u + v) = u\cdot u + v \cdot v + 2\cdot u\cdot v = \|u\|^2+\|v\|^2$.


A comment about your comments:

From your comments, it seems that you are getting confused because you are using the "squared triangular inequality", which says that

$ \|u + v\|^2 \le \|v\|^2 + \|v\|^2 + 2\|u\|\|v\| $

This is true, of course, but this inequality is often obtained using the Cauchy–Schwarz inequality, i.e., $u\cdot v \le \|u\|\|v\|$... That is, we write

$\|u + v\|^2 = (u + v) \cdot (u + v) = u\cdot u + v \cdot v + 2\cdot u\cdot v = \|u\|^2+\|v\|^2 + 2\cdot u\cdot v ~~ (1)$

then use Cauchy–Schwarz to obtain

$\|u + v\|^2 \le \|u\|^2+\|v\|^2 + 2\cdot \|u\|\cdot \|v\|$.

But of course, in your case, instead of using this upper bound, you can just set $u \cdot v = 0$ in Equality (1)

$\endgroup$
2
  • 1
    $\begingroup$ @kelala thanks! $\endgroup$ Commented Nov 6, 2023 at 21:02
  • 1
    $\begingroup$ So just to complete the trivial passages: $\delta\|b^*_k\|^2 \le \|b^*_{k+1} + \mu_{k+1,k}b^*_k\|^2 = \|b^*_{k+1}\|^2 + \mu_{k+1,k}^2\|b^*_k\|^2$ therefore $(\delta - \mu_{k+1,k}^2)\|b^*_k\| \le \|b^*_{k+1}\|^2$ which is the common other "version" of the Lovász condition. Thanks a lot for your answer! :) $\endgroup$ Commented Nov 7, 2023 at 12:39

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.