4
$\begingroup$

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?

$\endgroup$
3

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)

$\endgroup$

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.