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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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