Score:0

Simple question about BGV scheme

pk flag

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.

Score:1
ph flag

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

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.