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.


1 Answer 1


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$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.