Score:4

Closest Vector Problem in RLWE

eg flag

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

Hilder Vitor Lima Pereira avatar
us flag
There are some problems in your definition... CVP asks us to find a vector in a lattice that is closest to a target vector. But $R_q$ is not a lattice, since it is finite (the number of "points", or polynomials, in it is $N^q$).
Score:4
ng flag

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

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.