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?

  • $\begingroup$ 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$? $\endgroup$
    – Sam Jaques
    Commented Dec 14, 2020 at 18:18
  • $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu
    Commented Dec 14, 2020 at 18:22
  • $\begingroup$ 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$). $\endgroup$
    – Mark Schultz-Wu
    Commented Dec 14, 2020 at 18:25
  • $\begingroup$ 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). $\endgroup$
    – a196884
    Commented Dec 14, 2020 at 20:51
  • $\begingroup$ 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. $\endgroup$ Commented Dec 15, 2020 at 1:04


Your Answer

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