I'm reading "Complexity of Lattice Problems" by Micciancio and Goldwasser. Currently I am reading how the decision CVP problem is equivalent to the search CVP problem. Let $B = [b_1,...,b_n]$ be a set of linearly independent vectors in $\mathbb R^m$ and consider the lattice $\mathcal{L}(B)$. Furthermore, consider a target vector $t$. I struggle to see why $$R = \sum_{i = 1}^{n}||b_i||^2$$ is an upper bound on the squared distance from $t$ to the lattice (ie the squared distance from $t$ to the closest vector to $t$ in the lattice). I think this should be kind of obvious but I'm unfortunately not seeing it. Thanks!
1 Answer
$\begingroup$
$\endgroup$
This is true if $t$ lies in the subspace spanned by $B$. For example, $B = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ and $t = \begin{pmatrix} 0 \\ 10 \end{pmatrix}$ is a counter example. So assuming that $t\in span(B)$, $t$ lies in a fundamental region defined by the basis $B$ so that the distance of $t$ to the lattice is bounded by the maximum distance of any two points of this fundamental region. For any two points $x$ and $y$ in a fundamental region, we have $$ x-y = \sum b_iz_i \ , \ \text{ with } |z_i| \leq 1 \ . $$ Thus $$ \|x-y\|^2 = \|\sum b_iz_i\|^2 \leq \sum z_i^2\|b_i\|^2 \leq \sum \|b_i\|^2 \ . $$
