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.

Improve this question
$\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$
    – Huck Bennett
    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$
    – Huck Bennett
    Commented Jul 8 at 9:35

1 Answer 1

Reset to default
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/.

Improve this answer
$\endgroup$

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