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

1 Answer 1

0
$\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$

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.