3
$\begingroup$

I'm reading about the CVP problem, and all the papers I've read so far handle the case where the CVP matrix and vector are over $\Bbb R^{n}$ (or over $\Bbb Z^{n}$), and the distance is a real number.

However, I failed to find any references for the same problem over $\Bbb Z_{q}$. That is, where we have a matrix $A \in \Bbb Z_{q}^{n \times m}$ and vector $t \in \Bbb Z_{q}^{n}$ , and we have to decide whether there is some $v$ such that $A\,v - t\;\underline{\underline{\bmod q\;}}$ has a small norm.

(The norm I'm interested at is L1, since other norms might not be defined $\bmod q$ ).

Am I missing something, and this version of CVP is trivially easy / trivially equivalent to the "regular" CVP problem? If not, are you aware of papers that considered this version?

$\endgroup$
  • $\begingroup$ How do you define a norm over $\mathbb{Z}_q$? For example, let $u := (q/2, 0)$, then $v := u + u = (q, 0) = (0, 0)$, hence is $||v|| = 0$ or $||v|| \ge q$? $\endgroup$ – Hilder Vitor Lima Pereira Jul 22 '19 at 7:49
  • $\begingroup$ $||v||$ will be zero in this case (because all the calculation is $\mod q$)... that why I suspect it may be easier (or at least behave differently) compared to CVP over the integers... $\endgroup$ – Bartolinio Jul 22 '19 at 9:29
  • $\begingroup$ Okay. I guess you want to embed $\mathbb{Z}_q$ into the integer interval $[0, q-1]\cap \mathbb{Z}$ before computing the norm, which solves the problem of multiple representations of each vector, but then the "norm" does not satisfy $||a u|| = |a| ||u||$, which means it is not a norm. For example, take $q = 5$, $u = (2, 3)$ and $a = 2$, then $au = (4, 6) = (4, 1)$, so $||au|| = \sqrt{17}$, but $|a|||u|| = 2\cdot \sqrt{13}$. $\endgroup$ – Hilder Vitor Lima Pereira Jul 22 '19 at 9:48
  • $\begingroup$ You are right, of course, but what happens if we look at L1 norm? The problem doesn't exist there, and many papers do consider the L1 norm case in the "regular" CVP problem. Thanks for this comment, I'll edit the question accordingly... $\endgroup$ – Bartolinio Jul 22 '19 at 10:07
  • 1
    $\begingroup$ I don't see how the problem is solved, since $0 = ||(0, 0)|| = ||(q, q)|| = ||q(1, 1)|| \not = |q| || (1, 1)|| = 2q$. I am sorry for all these comments, but I just would like to know exactly what you mean by norm... Anyway, it seems that any solution to CVP over the $q$-ary lattice $\Lambda_q(A)$ would also be a solution to the problem you are trying to define. $\endgroup$ – Hilder Vitor Lima Pereira Jul 22 '19 at 11:38

Your Answer

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

Browse other questions tagged or ask your own question.