2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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'$.

$\endgroup$
2
  • $\begingroup$ Dear Daniel thanks for the answer. I figure out some points of this problem with the help of your answer. But I have another question. In this explanation I cannot imagine the graphical intuition of the lattice. We use B and target vector b to obtain B' but why we increase the dimension of B' with zero's and M? Is it about unique-SVP instance? If so, why unique-SVP instance consist of a vector and a number(say M)? $\endgroup$ – Erk Us Mar 16 at 11:24
  • $\begingroup$ 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. $\endgroup$ – Daniel Shiu Mar 16 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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