# Understanding Unique-SVP and Kannan's Embedding I am trying to understand the Kannan embedding technique. But I am confused about the formation of the B' and the finding of the short vector inside that basis. How does this basis matrix in the algorithm produce a lattice? Or more specifically why a uSVP instance consist of a vector(e^T) and an integer(M)?

Thanks.

The columns of matrix $$B'$$ generate a lattice $$\Lambda'=\{\mathbf v'\in\mathbb Z^{n+1}\}$$ where the first $$n$$ entries form a vector which differs from a vector of $$\Lambda$$ by some multiple of $$\mathbf e$$ and the last entry is the same multiple of $$M$$. We also need some guarantee that $$\mathbf e$$ is shorter than the shortest vector of $$\Lambda$$ by some amount and that $$\mathbf {As}$$ is the closest vector to $$\mathbf b$$.
$$M$$ is not necessarily an integer, but is some value such that e.g. $$M=||\mathbf e||$$ when we know $$||\mathbf e||<\lambda_1/2$$ where $$\lambda_1$$ is the length of the shortest vector of $$\Lambda$$. It follows that the vector $$(\mathbf e, M)^T$$ has length at most $$\sqrt 2M<\lambda_1/\sqrt 2$$. This is shorter than any vector of the form $$(\mathbf x, 0)^T$$ which corresponds to a vector $$\mathbf x$$ of $$\Lambda$$ and so is of length at least $$\lambda_1$$. It is shorter than any other vector of the form $$(\mathbf y, M)^T$$ by the definition of the closest vector. It is also short than any vector of the form $$(\mathbf z, kM)^T$$ for any $$|k|\ge 2$$ as such a vector has length at least $$|k|M>\sqrt 2 M$$ based on the final component. It follows that $$(\mathbf e, M)$$ is the unique shortest vector of $$\Lambda'$$.
• If we did not add an extra row we would have an $n$ dimensional lattice with $n+1$ generators with determinant dividing $q$ but less than $q$. This would almost certainly have vectors that are shorter than $e$ but are of the form $\mathbf {Ax}+k\mathbf e$ for some (unknown) $k$. Instead we embed $\Lambda$ in this larger lattice and weight the extra dimension in order to single out the $k=1$ case. – Daniel Shiu Mar 16 at 12:10