While I'm trying to implement BGV scheme myself, I found that I'm really confusing about the encryption and decryption of the scheme. Here's my understanding:
Let $p$ be a plaintext modulus and $q$ be a ciphertext modulus (they are coprime). Let $\mathbb{Z}_{m} = (-m/2, m/2] \cap \mathbb{Z}$ be the fixed set of representatives modulo $m$ and $[\cdot]_{m}: \mathbb{Z} \to \mathbb{Z}_{m}$ be modulo $m$ map. Let $R = \mathbb{Z}[x] / (x^{n} + 1)$, $R_{m} = \mathbb{Z}_{m}[x]/(x^{n}+1)$ as usual ($n$ is a power of 2). I would ignore the level and bootstrapping stuffs.
- $a \leftarrow U_{q}$, where $U_{q}$ is uniform distribution over $R_{q}$
- $s \leftarrow \{-1, 0, 1\}^{n}$
- $e \leftarrow GD(\sigma)^{n}$, where $GD(\sigma)$ is a (discrete) Gaussian distribution with standard deviation $\sigma$
- $b = [as + pe]_{q} \in R_{q}$ and $pk = (a, b) \in R_{q}^{2}$
- $r \leftarrow \{-1, 0, 1\}^{n}$, with $P(X=0) = 1/2$ and $P(X=-1) = P(X=1) = 1/4$.
- $e_0, e_1 \leftarrow GD(\sigma)^{n}$.
- message $m \in R_{p}$
- $c_{0} = [br + pe_{0} + m]_{q} \in R_{q}$
- $c_{1} = [ar + pe_{1}]_{q} \in R_{q}$
- Encrypt $m$ as $\mathrm{Enc}(m) = (c_{0}, c_{1}) \in R_{q}^{2}$
- For a ciphertext $(c_{0}, c_{1})$, decrypt it as $[[c_{0} - c_{1}s]_{q}]_{p}\in R_{p}$.
I understand how this is intended to be $\mathrm{Dec}(\mathrm{Enc}(m)) = m$, but when I tried to do some toy examples with own hands, I found that there's something I'm missing now.
What I think is that, there are two modulus (plaintext and ciphertext) and using both actually makes decryption fail. This is because $[[x]_{q} + [y]_{q}]_{p} \neq [[x+y]_{q}]_{p}$ and $[[x]_{q}[y]_{q}]_{p} \neq [[xy]_{q}]_{p}$ in general. Especially, if $x + pe \not\in \mathbb{Z}_{q}$, then reducing modulo $q$ would make $[[x+pe]_{q}]_{p} \neq [[x]_{q}]_{p}$ which yields decryption fail. I think I'm missing something really simple but I can't figure out.