Question regarding PBS variants in TFHE-rs

Zama TFHE-rs
1

Hello,

I recently try to dissect the new TFHE-rs library. I notice that the library already implement the WOPBS function but the documentation hasn’t mentioned about it. I have question regarding the different flavors of PBS.

  1. What actually WOPBS is?
  2. How it different from the normal PBS?
  3. Is WOPBS actually replacing the normal PBS?
  4. If not, in what condition do we want to use WOPBS and normal PBS?
  5. In TFHE-rs, in WOPBS engine, there are these 4 functions:1) programmable_bootstrapping; 2) programmable_bootstrapping_without_padding; 3) programmable_bootstrapping_native_crt; 4) wopbs;. All of them seems to perform similar functionality. What are the different among those APIs?

Thank you!

2

Hello @Dwen !

The WOPBS is described in this paper Improved Programmable Bootstrapping with Larger Precision and Efficient Arithmetic Circuits for TFHE

  1. It’s a method to apply a look-up table on more bits/larger messages than would normally be possible using the PBS on a single ciphertext, for example allowing to apply look-up tables using 16 bits of input information.
  2. The general idea is to extract the bits of information for one or several input LWE ciphertext, converting the extracted bits (which are in the form of LWE ciphertext) to GGSW ciphertexts via an operation called “circuit bootstrapping”, then using these GGSW ciphertexts and a properly crafted look-up table it is possible to output (after computing a so-called cmux-tree and/or a blind rotate) one or several ciphertexts containing the evaluation of the function from your look-up table that used the (in our example) 16 bits of input information
  3. No as far as I’m aware the WOPBS is not meant to replace a normal PBS, the characteritics of the two primitives are pretty different
  4. You would want to use the WOPBS in the case where a single LWE ciphertext cannot hold messages large enough and would therefore need to split it over several LWE ciphertexts for example.

  • programmable_bootstrapping : in the context of its use by shortint does the following: switch from the classic PBS parameter set to WOPBS parameter set, apply PBS and come back to the classic PBS parameter set

  • programmable_bootstrapping_without_padding : it looks like this is a different method where the padding bit (normally the MSB) is used to store some information, while the assumption is generally that this bit is left as 0 to ensure the correctness of the PBS computation

  • programmable_bootstrapping_native_crt: a version of the WOPBS that accomodates the needs of the CRT representation (which does not use power of 2s in general as moduli) as it was used in some of concrete’s integer implementation

  • wopbs: an impementation of the WOPBS algorithm for a given set of WOPBS parameters using classic assumptions like ciphertext containing a 0 padding bit, power of 2 moduli

I did not work on those implementations myself, I hope my answers can help you nonetheless!

Cheers

3 Likes