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?

## 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.