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 Vítor Lima Pereira Jul 22 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 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 Vítor Lima Pereira Jul 22 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 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 Vítor Lima Pereira Jul 22 at 11:38
0
$\begingroup$

Bartolinio -> As far as I know, it's better to link CVP to SVP (with the same Ring), that "to change the ring" of CVP. Edit -> in fact I'm wrong, it's easier to see think truth the LWE problem and the SIS problem (because your problem looks like the SIS problem).

$\endgroup$
  • $\begingroup$ Thanks on the answer but I'm not sure I follow... I didn't find any place that considers the hardness of CVP (or SVP) over finite rings or fields. Are you aware of such a place and able to point me? $\endgroup$ – Bartolinio Jul 22 at 10:37
  • $\begingroup$ In fact, I was wrong. I advise you to search about SIS (small integer problem), it's probably nearer the problem you spoke than CVP: ( page 5 : pdfs.semanticscholar.org/4cb8/… ) $\endgroup$ – Ievgeni Jul 22 at 11:29
  • $\begingroup$ But your problem could be seen as SIS. Is not it? $\endgroup$ – Ievgeni Jul 22 at 11:31
  • $\begingroup$ A tip: You can use @username to address someone in the comments; doing so will cause them to receive a notification in their inbox (this does not work in questions/answers, only in comments and in chat) $\endgroup$ – Ella Rose Jul 22 at 15:06
  • $\begingroup$ @Ella Rose Thanks a lot $\endgroup$ – Ievgeni Jul 22 at 15:09

Your Answer

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

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