1
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\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
    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
    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
    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
    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$
    – Chris Peikert
    Dec 15, 2020 at 1:04

0

Reset to default

Your Answer

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