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))

5

Thanks, I understand bivariate PBS. It seems that we should be extend this to multi-variable PBS.

6

Hi! I am interested in understanding division algorithm implemented by Zama. Since it seems that you understood both the bivariate PBS and division algorithm, can you provide me with some useful links or documentations to study it? Thanks for any help

7

The division algorithm is mainly the long binary division, with a few tricks to make it faster on tfhe