# Does the plaintext modulus have to be prime in BGV?

I'm thinking about storing packed integers $$(x_1,x_2,...,x_k)$$ into a single ciphertext slot using the Chinese Remainder Theorem (CRT). However, in order for the CRT to work, the plaintext modulus would have to be a product of prime values (the same prime values used in the CRT). So I ask, does the plaintext modulus have to be prime in BGV?

• in general, the CRT needs mutually coprime numbers, not necessarily prime numbers. Apr 21, 2023 at 2:45
• BGV stands for the cryptosystem in Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan: (Leveled) Fully Homomorphic Encryption without bootstrapping, in ACM Transactions on Computation Theory (TOCT), 6(3):1–36, 2014; with 2011 version on eprint.
– fgrieu
Nov 12, 2023 at 16:48
• The work Overdrive2k eprint.iacr.org/2019/153.pdf explores BGV over $\mathbb{Z}_{2^k}$, and the associated CRT packing Mar 11 at 15:38

BGV can be set up with arbitrary moduli, as far as I know (BFV can, and BGV is just a different encoding). However, as you observed correctly, to make use of the CRT you would need pairwise coprime factors, which implies that the selection of a $$2^k$$ modulus (which is very natural to a computer) is bad in terms of CRT packing concerning the modulus. Nevertheless, there is also a packing available using CRT on the quotient ring itself, which is an independent thing.
The main requirement for the plaintext modulus comes from the Lemma in the Modulus Switching Section of the original BGV paper (page 3). In order for this to work the the requirement for the plaintext modulus $$p$$ relative to the ciphertext modulus $$q$$ is that $$p \cong q \bmod 2$$ In the concrete instantiation described in the same paper the plaintext ring is described as $$R_2 = \mathbb{Z}_2[X]/\langle\phi_m(x)\rangle$$ i.e. $$p=2$$ (section 3.1)