Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
The approximate Shortest Vector Problem (apprSVP) is a problem where, given the basis and the approximation factor $\gamma$ (a function of the dimension $n$), one must find a vector $v$ belonging to the lattice $L$ such that its norm is less than $\gamma$ times the length of the shortest vector in the lattice $L$.
But it is hard to find even the length of the shortest vector, so then what value should we substitute in place of the length of the shortest vector when defining apprSVP?
As you write, an algorithm for SVP$_\gamma$ must output a nonzero lattice vector $v \in L$ such that $\| v \| \leq \gamma \cdot \lambda_1(L)$, where $\lambda_1(L)$ denotes the minimum distance of $L$. It is also true that we don't have an efficient algorithm to verify that a candidate $v$ meets this condition, because $\lambda_1(L)$ appears hard to compute. But this does not mean the definition needs to be changed: $\lambda_1(L)$ is a well-defined quantity, and as long as the algorithm always outputs some $v$ meeting the condition, the algorithm is correct.
For example, once can prove that the LLL algorithm finds a nonzero $v \in L$ such that $\| v \| \leq 2^{n/2} \cdot \lambda_1(L)$, where $n$ is the dimension. This holds even though LLL does not compute $\lambda_1(L)$ exactly.
