Closest Vector Problem in RLWE

Question

I am interested in a polynomial form of the lattice problem Closest Vector Problem (C.V.P), or in other words if C.V.P. can be ''transferred'' to Ring-LWE.

My idea about this question is that a polynomial form of C.V.P will look like the following:

Let $R = \mathbb{Z}[X]/\Phi_M(X)$ and its residue filed $R_q = \mathbb{Z}_q[X]/\Phi_M(X)$ where $q$ is a modulus and $\Phi_M(X)$ a cyclotomic polynomial with $M$ to be a power of 2. Then the polynomial C.V.P problem would be: Let $h(x)$ be a polynomial with fixed non-integer coefficients, we want to find the closest polynomial $u(x) \in R_q = \mathbb{Z}_q[X]/\Phi_M(X)$ to $h(x)$

What I have so far is something pretty vague, so I was wondering if anyone is familiar with a more accurate definition. (I wasn't able to find something with online research.)

Thank you in advance

Answer 1

CVP is a problem over general lattices. RLWE is a specialization of LWE to ideal lattices, a subset of all (general) lattices. So one can already define a perfectly reasonable version of CVP in the ring setting --- specialize the definition of CVP from general lattices to ideal lattices.

This is what people do in the literature. For example, in the paper that shows pseudorandomness of RLWE in general number fields based on worst-case lattice problems, RLWE is conected to two problems, namely K-DGS and K-SIVP. These problems are (implicitly) defined on page 9, in

All of the computational problems on lattices defined in Section 2.2 can be specialized by restricting them to (fractional) ideal lattices in a number field $K$. We refer to these specialized problems by prefixing them by $K$, e.g., $K\mathsf{-GDP}_{\mathcal{I},r}$, $K\mathsf{-DGS}_{\gamma}$ , etc.

Of course, you're free to define your own variant of CVP over ideal lattices directly. It's not immediately clear to me it will be equivalent to $K\mathsf{-CVP}$, i.e. the specialization of CVP to fractional ideal lattices in $K$. The main issues I see immediately (as someone with only a passing familiarity with algebraic number theory, for the record) are

1. it is not clear what "closest" means in your definition. Typically this is defined by defining "close" as "in the euclidean norm in the canonical embedding", or something of this sort. By not fixing an embedding (of coefficient/canonical), you could mean two very different things, for example something similar to the "Polynomial Learning with Errors" problems, or RLWE. For power of two cyclotomics things are mostly equivalent, but its still a good habit to be precise.

2. It's not clear to me that $R_q$ is a residue field of $R$? A residue field of a ring $R$ typically means $R / \mathfrak{m}$ for $\mathfrak{m}$ a maximal ideal. Your $R$ is really $R / (q)$, and $(q)$ need not be maximal (as $q$ need not be prime, either in your definition, or for RLWE to be hard).

3. Again, it's not clear what it means for $h(x)$ to have non-integer coefficients. This is another thing that would be clearer if you fix some choice of embedding $\phi: R \to k^n$ (for $k\in\{\mathbb{R}, \mathbb{C}\})$, and then let $h\in k^n$.