<blockquote>
<p>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?</p>
</blockquote>
<p>It does---CVP on a lattice <span class="math-container">$L$</span> and target vector <span class="math-container">$t$</span> is equivalent to finding a <em>shortest</em> vector in the lattice coset <span class="math-container">$L - t$</span>. 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.</p>
<p>Self promotion: For discussion about reducing CVP to SVP and its difficulties, I suggest reading Section 3 of my survey: <a href="https://eccc.weizmann.ac.il/report/2022/170/" rel="noreferrer">https://eccc.weizmann.ac.il/report/2022/170/</a>.</p>

CC BY-SA 4.0
2024-07-08T01:03:05.597Z
2024-07-08T01:03:05.597Z
Huck Bennett
<p>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.</p>
<p>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?</p>
<p>I'm assuming the reduction is incorrect due to <a href="https://cstheory.stackexchange.com/questions/53017/cvp-to-svp-reduction">this question and it's answer</a> suggesting it is not trivial to reduce CVP to SVP.</p>

CC BY-SA 4.0
2024-07-08T04:24:49.050Z
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.
D.W.
<lattice><integer-lattice><cryptography>
Why can't CVP be trivially reduced to SVP by shifting?
maximxls
# Why can't CVP be trivially reduced to SVP by shifting?

(Asked by: username_0 on 2024-07-07)

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](https://cstheory.stackexchange.com/questions/53017/cvp-to-svp-reduction) suggesting it is not trivial to reduce CVP to SVP.

**Tags:** lattice, integer-lattice, cryptography
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2024-07-08. Score: 6 | Accepted answer

> 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/>.


---

