Does the plaintext modulus have to be prime in BGV?

Fishy Sticks

4/20/24, 7:56 PM

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?

1 + 1

homomorphic-encryption

Don Freecs

4/21/24, 2:45 AM

in general, the CRT needs mutually coprime numbers, not necessarily prime numbers.

Score:0

Crypto

The Dice Man

6/15/24, 1:47 PM

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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Does the plaintext modulus have to be prime in BGV?

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.