Assume we have an oracle which gives the length of the shortest vector in a lattice. Given this oracle can we find the shortest vector in polynomial time?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes you can. I'll write $\lambda_1(L) = \min_{l\in L\setminus \{0\}} \lVert l\rVert_2$. I will also identify a lattice with any of its basis, e.g. I will write $\lambda_1(B)$ where $B$ is a lattice basis.
There are two relevant forms of SVP
- Search: Given a lattice basis $B$, recover $\vec x$ such that $\lVert B\vec x\rVert_2 = \lambda_1(B)$ is the shortest vector in the lattice.
- Decision: Given a lattice basis $B$ and length bound $t$, return "yes" if $\lambda_1(B) \leq t$, and "no" otherwise.
What you're asking for is implied by a reduction from the search SVP problem to the decision SVP problem, as your oracle can easily be used to solve decision SVP. Such reductions are known to exist, see for example this.
