In Babai nearest plane algorithm(solve approximate version of CVP), given the basis as input first step is to find the reduced basis(using LLL reduction algorithm). Why the reduced basis is used for further steps?


1 Answer 1


Short answer: If the basis is not reduced, then there are no guarantees on the distance between the target and the output, compared to the distance between the target and an actual closest vector. By LLL-reducing the basis you can bound this distance, and therefore Babai's nearest plane algorithm solves CVP to a certain approximation.

Take a look at the second step of Babai's nearest plane algorithm, where $t$ refers to the target vector.

$ b \leftarrow t$
for $i = n$ to 1 do
$\quad b \leftarrow b - c_i b_i$ where $c_i = \lceil \langle b, \tilde b_i \rangle / \langle \tilde b_i, \tilde b_i \rangle \rfloor$
output $t-b$

Where the tilde denotes the Gram-Schmidt orthogonalization of the basis. Essentially, it looks for an integer combination of the basis vectors that is close to the target vector.

Now, if $t \in$ span$(B)$, you can see that you can bound the distance between the output and $t$ by the sum of $\langle \tilde b_i, \tilde b_i \rangle$. LLL gives us a bound on these values. For an arbitrary basis, these norms could be very large, meaning the second step could be very, very off.

In the case that $t \notin$ span$(B)$, you can use a similar argument on the projection of $t$ onto span$(B)$.

For the exact details of how the LLL properties of the basis are used to prove the correctness of the algorithm, see this lecture.


Your Answer

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

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