# Solving RLWE modulo a prime ideal

Suppose you have the following set up for RLWE: $$K$$ is a cyclotomic field of degree $$n$$ over $$\mathbb{Q}$$, and $$p\in\mathbb{Z}$$ is a prime integer that splits as follows in $$R = \mathcal{O}_K$$: $$p\mathcal{O}_K = \prod_{i=0}^{n-1}\mathfrak{p}^{e}_i$$. Let $$R_p = R/pR$$ and $$R^\vee$$ denote the dual lattice. Let an RLWE sample be $$(a,b)=(a,(a\cdot s)/p+e)\in R_p\times \mathbb{T}$$, where $$s\in R_p^\vee$$.

My question is: given access to samples $$(a,b)$$ and $$s \bmod \mathfrak{p}_iR^\vee$$, can you solve $$\mathfrak{p}^e_i$$-RLWE? i.e. can you find $$s\bmod\mathfrak{p}^e_iR^\vee$$? If not in generality, then what conditions need you impose to find a solution?

• To clarify: given the reduction you already described, can we just solve for $s$ using $s\mod {\frak{p}}_i R^\vee$, then reduce $s$ mod ${\frak{p}}_i^2 R^\vee$? Dec 14, 2020 at 18:18
• In the quote you ask about, $p$ is assumed to "split completely", meaning $p = \prod_{i = 1}^n \mathfrak{p}_i$ is "square-free". One then gets by the chinese remainder theorem that $\mathcal{O}/p\mathcal{O}\cong \prod_{i = 1}^n \mathcal{O}/\mathfrak{p}_i\mathcal{O}$. This is to say that in the split completely case, $\mathfrak{p}_i^2$-RLWE is not immediately interesting.
– Mark
Dec 14, 2020 at 18:22
• That being said, it becomes relevant if you want to apply the CRT to more general $p$. If one wants to repeat the CRT argument for general $K$ you get that $p = \prod_{i = 1}^k \mathfrak{p}_i^{e_i}$, and that $\mathcal{O}/p\mathcal{O} \cong \prod_{i = 1}^k \mathcal{O}/\mathfrak{p}_i^{e_i}\mathcal{O}$. If $K$ is Galois as well, then $e_i = e_j$ for all $j$, so things simplify somewhat. But in this context $\mathfrak{p}_i^{e_i}$-RLWE becomes relevant (For $e_i > 1$).
– Mark
Dec 14, 2020 at 18:25
• So I suppose I'm actually thinking about when the ramification isn't quite as nice as for completely split primes. Let $p$ such that $p\mathcal{O}_K = \prod \mathfrak{p}_i^{e}$. Now: given an RLWE sample $(a,b)$ and $s\bmod\mathfrak{p}_i R^\vee$, is that sufficient to find $s\bmod\mathfrak{p}^2_i R^\vee$? (I'll edit the original question to reflect your comments). Dec 14, 2020 at 20:51
• Do you only have $s \bmod \mathfrak{p}_i$, or an oracle for solving $\mathfrak{p}_i$-RLWE? In the latter case I think you should be able to do what you’re asking in a digit-by-digit fashion, by solving for $s \bmod p$, “shifting” it to be zero, “dividing” by $p$, and repeating. This is just a sketch but I think it has a good chance of going through. Dec 15, 2020 at 1:04