4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Hi, preethi, and welcome to Crypto Stack Exchange. I've copyedited your question a bit to hopefully make it clearer and easier to understand. Could you please check that I didn't accidentally introduce any errors while doing so? If you do find anything that you think should be corrected, please feel free to edit your question further yourself. Thanks! $\endgroup$ Commented Sep 16, 2015 at 15:03
  • $\begingroup$ What is the problem you are trying to solve here? $\endgroup$ Commented Sep 16, 2015 at 15:44
  • $\begingroup$ @ChrisPeikert, thanks for letting me know. I'll remove that comment. $\endgroup$ Commented Oct 22, 2015 at 11:51

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.