How does batching in FHE work?

Question

Let's say we have a BGV style homomorphic encryption scheme. The message space will be the ring $$R_p = \mathbb Z_p[x]/(x^d + 1)$$ where $p$ is a prime congruent to $1$ modulo $2d$. Now let's say we say messages $m_1(x), m_2(x) \in R_p.$ How do we obtain a ciphertext encrypting both $m_1(x)$ and $m_2(x)$? The BGV paper mentions the CRT isomorphism $$R_p \cong R_{\mathscr{p_1}} \times ... \times R_{\mathscr{p_d}}.$$ Under this isomorphism, we have the mapping $m_1(x) \to ((m_{1,1})(x),...,(m_{1,d})(x))$ and we have a similar representation for $m_2(x)$. I'm still not sure how we use this mapping to get a ciphertext encrypting both $m_1(x)$ and $m_2(x)$ at the same time however.

Any clarification would be greatly appreciated.

Answer 1

Your isomorphism implies that you are factoring the prime $p$ into several primes $p_1,...p_d$, but of course, what you actually factor is the cyclotomic polynomial modulo $p$, i.e., $x^d + 1 = f_1(x) \cdot ... \cdot f_u(x) \pmod p$. Because of the properties of the cyclotomic polynomial, every $f_i$ has the same degree $o$, which is actually equal to the order of $p$ in $\mathbb{Z}_{2d}^*$. And then, the number of slots is $u = d / o$.

So, you cannot encrypt two polynomials of degree $d$ into a single ciphertext. What you can do is to choose $u$ polynomials $m_1,...,m_u$ of degree up to $o-1$, then "pack" them with CRT, obtaining $m \in R_p$, and finally encrypt $m$.

This answer may be helpful.