Which division algorithm does Zama for TFHE?

Zama TFHE-rs
1

I wonder which division algorithm is used in Zama for TFHE ciphertexts.

Does it use binary division, or Newton-Ralph division?

Newton-Ralph encrypts each number as whole, whereas binary division encrypts each bit one by one. So, the former should be more efficient for computing divisions in terms of space complexity.

If Zama’s ciphertext division uses binary division instead of Newton-Ralph, I wonder why.

2

For TFHE ciphertext (shortint) division is made via the bivariate PBS

for integer ciphertext which are in radix representation (i.e many TFHE ciphertext to represent on larger integer value) we use repeated subtractions.

3

Thanks for your answer.
I’d like to learn how the bivariate PBS works for shortint division. Could there be any document or resource that is easy to follow?

Thanks.

4

The bivariate PBS is a simple thing, our parameters are made such that we have a “carry modulus” and “message modulus” and the whole plaintext modulus is then carry_modulus * message_modulus

When carry_modulus >= message_modulus, and with 2 inputs a and b for which we know the encrypted value is <= message_modulus, we can “pack” the 2 inputs into one LWE (packed = a * message_modulus + b), and then apply a PBS with a lookuptable that encodes a / b (we do div_result = (packed / message_modulus) / (packed % message_modulus))