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$
6
  • $\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$ Jul 22, 2019 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, 2019 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$ Jul 22, 2019 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, 2019 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$ Jul 22, 2019 at 11:38

0

Your Answer

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

Browse other questions tagged or ask your own question.