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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$
end
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.
