# Simple question about BGV scheme

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.

• Key generation
1. $$a \leftarrow U_{q}$$, where $$U_{q}$$ is uniform distribution over $$R_{q}$$
2. $$s \leftarrow \{-1, 0, 1\}^{n}$$
3. $$e \leftarrow GD(\sigma)^{n}$$, where $$GD(\sigma)$$ is a (discrete) Gaussian distribution with standard deviation $$\sigma$$
4. $$b = [as + pe]_{q} \in R_{q}$$ and $$pk = (a, b) \in R_{q}^{2}$$
• Encryption:
1. $$r \leftarrow \{-1, 0, 1\}^{n}$$, with $$P(X=0) = 1/2$$ and $$P(X=-1) = P(X=1) = 1/4$$.
2. $$e_0, e_1 \leftarrow GD(\sigma)^{n}$$.
3. message $$m \in R_{p}$$
4. $$c_{0} = [br + pe_{0} + m]_{q} \in R_{q}$$
5. $$c_{1} = [ar + pe_{1}]_{q} \in R_{q}$$
6. Encrypt $$m$$ as $$\mathrm{Enc}(m) = (c_{0}, c_{1}) \in R_{q}^{2}$$
• Decryption
1. 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.

You must choose q so that the noise in the ciphertext doesn't overflow. For example, if $$p = 2$$ and $$n = 256$$ you can use $$q = 7681$$ (taken from Kyber). There are many possible instantiations, and the important point is that the norm $$||c_0 - c_1 s||_\infty = ||p (e r + e_2 - e_1 s) + m||_\infty$$ is less than $$q/2$$.