Leveled-gate operation

Zama TFHE-rs
1

Dear community,

I have a couple of questions regarding the TFHE (TFHE or TFHE-rs library) and its capabilities for leveled-gate operations:

  1. Is it possible to perform a leveled-gate operation in TFHE? For instance, can we compute NAND gate ((0,1/8) - ca - cb) two times and then bootstrap the resulting value?
  2. While examining the TFHE source code, I noticed that it utilizes 32-bit long signed integer data for message encoding, including the error. Would it be feasible to increase the length to 64 bits? By doing so, could we potentially enhance the depth of leveled-gate operations? If its possible to do leveled-gate operation in the first place.

Thank you

2

Hello @Fakhri_Hidayat

I’m moving your question to the tfhe-rs category.

1 Like
3

hello @Fakhri_Hidayat

  1. If I understand you question correctly you would like to perform non linear operations in a leveled fashion (i.e. without a PBS) and then bootstrap after a certain number of levels have been effectively used ?

  2. Going to 64 bits (i.e. q = 2^64) does give more space for the message we can encrypt, giving the possibility to compute more leveled operations. If it’s possible to represent your gate computations in a leveled manner then using the shortint API might allow a certain number of “leveld gate” operation before having to bootstrap. But that’s only if the gates you want to compute can be expressed with leveled additions and multiplications by clear values I would think.

Let me know if I understood your questions correctly.

Cheers

4

Hello @IceTDrinker, thank you very much for your answer!

  1. Yes, for example if I have four ciphertexts c1, c2, c3, c4 as an input and want to compute AND operation:
    c’ = (c1 + c2) - (1/8)
    c’’ = (c3 + c4) - (1/8)
    c’’’ = (c’ + c’’) - (1/8)
    Can I do that without bootstrapping and still have the correct decryption result?

  2. I see, thanks! So in that case if I want to implement AND operation by using shortint with the same encoding as boolean implementation (0 → -q/8, 1 → q/8). It’s probably okay for me to choose 0 for CarryModulus and 3 for MessageModulus? How many leveled operations could I do, if I only do ciphertext-ciphertext addition in all my operations? Probably the bootstrapping time will take around 129.4 ms (same as PARAM_MESSAGE_3_CARRY_3, according to Benchmarks - TFHE-rs if executed on that machine)?

Thank you.

5

  1. I have a doubt this works ok, as if c1 and c2 are both -1/8 you then get out -3/8 for c’ which does not conform to the encodign ?

  2. the MESSAGE_X_CARRY_Y notation indicates you have X bits of message and Y bits of carry, in general I would keep the carry bits as when encrypting we have to assume the ciphertext message space is full, you should be able to do as many additions as required to fill X + Y bits supposing all messages contain 2^X - 1 as initial value.

i.e. for 2_2 parameters, you have to assume all encrypted messages are 3 and you will be able to do 5 additions to fill the msg + carry space which is 2^2 * 2 - 1= 15

1 Like
6
  1. Ah right I overlooked the -3/8 part
  2. I see, got it

Thanks for your kind answer!