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$ Sep 16, 2015 at 15:03
  • $\begingroup$ What is the problem you are trying to solve here? $\endgroup$
    – mikeazo
    Sep 16, 2015 at 15:44
  • $\begingroup$ @ChrisPeikert, thanks for letting me know. I'll remove that comment. $\endgroup$
    – mikeazo
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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