Hi, I want to ask if it is possible to perform divide a ciphertext by two efficiently in BGV or FV. I know in BGV and FV, the ciphertexts encrypts only integer values mod p, where p is the plaintext modulus. And I know that one can implemente division by a constant via interpolation, like in this paper https://hal.science/hal-02294597/document. But this approach is pretty expensive. In CKKS, division by a constant can be easily implemented as multiplication by 1/constant (since ckks supports real number).

I am wondering whether we can perform efficient division by a constant (such as division by 2) in BGV. Thanks!

General division is very challenging. By general I mean no constraints over the input data.

Some specialized divisions can be performed such as exact division.

In exact division, the dividend is an exact multiple of the divisor.

Say your encrypted vector contains multiples of 2 values, that is, all values are even numbers, then you can do efficient exact division in BGV or BFV as follows:

f = 2^{-1} \pmod p, that is the modular multiplicative inverse of 2 modulo the underlying plaintext modulus.

result = f\cdot v, where v is your encrypted data.

This can be done efficiently in BFV or BGV since f can be pre-computed and encoded as plaintext. Computing the result requires ciphertext-plaintext multiplication.

Another kind of division that you can do efficiently is flooring, but you would need as input encryption of your input vector v and encryption of |v|_2 = v \pmod 2.

Then you can compute the element-wise floor \lfloor v/2 \rfloor as follows:

\lfloor v/2 \rfloor = (v - |v|_2)\cdot f.

Other than those kinds of division, I am not aware of any straightforward methods.

It would also be useful to look into this paper which scales by 1/p during bootstrapping, but I do not think it is a straightforward technique.

Thanks for your reply. I see your point. It is true that for an even number, you can divide it by 2 via multiplyting 2^-1 (the multiplicative inverse of 2). But I think itâ€™s safe to say general division (1/c for some constant c) is still expensive in BGV, when the input has no constraints. Techniuqes in https://hal.science/hal-02294597/document and Logistic regression over encrypted data from fully homomorphic encryption - PMC are both quite expensive.