4
$\begingroup$

I'm dipping my toes into lattice-based cryptography, but the difference between the SVP and CVP confuses me. I'm most definitely missing something big here, but I still couldn't figure it out, so I'm asking for your help.

Imagine we can solve SVP (which I understand as finding the closest to zero, but nonzero vector of the lattice). Let's shift the origin to the target vector, solve SVP there and shift the answer back. Why doesn't this give a solution to a CVP?

I'm assuming the reduction is incorrect due to this question and it's answer suggesting it is not trivial to reduce CVP to SVP.

New contributor
maximxls is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
3
  • 4
    $\begingroup$ That reduction does---CVP on a lattice $L$ and target vector $t$ is equivalent to finding a shortest vector in the lattice coset $L−t$. The problem is that this is not how SVP is defined. SVP is defined as finding a shortest non-zero vector in a lattice, not a shortest (possibly zero) vector in a lattice coset. I still suggest reading the section of survey that's linked there :-). $\endgroup$ Commented Jul 8 at 1:05
  • 2
    $\begingroup$ I encourage you to write that as an answer, rather than as a comment, so we can upvote it and the question can be treated as answered. It sounds like an answer to the question. The Stack Exchange platform discourages writing answers in the comments. No need to write anything more or longer than that -- that is already perfectly sufficient as an answer. $\endgroup$
    – D.W.
    Commented Jul 8 at 4:24
  • 2
    $\begingroup$ @D.W. Okay :-). I wrote it as an answer and deleted it when I realized I linked to my survey in the other answer too. I'll undelete it. $\endgroup$ Commented Jul 8 at 9:35

1 Answer 1

6
$\begingroup$

Let's shift the origin to the target vector, solve SVP there and shift the answer back. Why doesn't this give a solution to a CVP?

It does---CVP on a lattice $L$ and target vector $t$ is equivalent to finding a shortest vector in the lattice coset $L - t$. The problem is that this is not how SVP is defined. SVP is defined as finding a shortest non-zero vector in a lattice, not a shortest (possibly zero) vector in a lattice coset.

Self promotion: For discussion about reducing CVP to SVP and its difficulties, I suggest reading Section 3 of my survey: https://eccc.weizmann.ac.il/report/2022/170/.

$\endgroup$

Your Answer

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

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