I've read the series of blog posts explaining TFHE scheme on zama.ai's website (four parts), and some things are not clear to me. I would appreciate if someone can shed some light on those topics.

  1. I am not sure I understand how multiplication by a "big" constant works in practice: what are the typical values for beta and # of levels? If M's coefficients are at most 2^p and we multiply the coefficients of M by q/betta, would we always stay in bounds? Or do we do the multiplication modulo q, and we don't care if we have the overflow? Here is the link to original blog post on zama's website.

  2. The second question is about bootstrapping and the encoding of the values of V. As I understand the procedure, we would want to rotate a huge polynomial whose coefficients are all possible message values to pick the "correct" one. However, the length of this polynomial would be impractically long to store. Here I am lost. What is the length of V in practice? 2N? What is the size of each of those 2N coefficients?


1 Answer 1

  1. The multiplication is modulo $q$. We don't care about overflow, but we do care about error growth. In other words, if we have a ciphertext $(\vec a, \langle \vec a,\vec s\rangle + (q/p)m+e)$, and multiply by $\alpha$ to get $(\alpha\vec a, \alpha\langle \vec a,\vec s\rangle + (q/p)\alpha m+\alpha e)$, we don't care that there may be a reduction modulo $q$ in computing $\alpha\langle \vec a,\vec s\rangle + (q/p)\alpha m+\alpha e)\bmod q$, but do care if $\alpha e$ is too large (as written, larger than $(q/2p)$ causes issues).

  2. You're not lost, this is the main downside of the technique. TFHE (and other schemes like it, e.g. FHEW and FINAL) essentially encode arithmetic in the exponent of polynomials. Practically we can work with polynomials of degree $\approx [2^{10}, 2^{15}]$ while keeping things reasonable. This means that we have $\approx [10,15]$ bits of arithmetic to work with. This ends up being a slight overestimate as we encode ciphertexts into this size of arithmetic --- generally I see TFHE advertise $\approx 8$ bits of plaintext arithmetic on the top end.

    Note that one can build higher-precision arithmetic circuits from these lower-precision building blocks, though this obvious comes at a cost. The idea of building reasonably sized plaintext arithmetic (say 32 bits) using these techniques runs into precisely the issue you identify, namely that a polynomial of degree $\geq 2^{32}$ can't reasonably be computed on.

As for typical values, someone who is particularly interested can always examine Zama's code directly. Here's a file for instantiating a parameter set of theirs. They decompose with respect to a modulus $2^{3}$ (ks_base_log) or $2^6$ (pbs_base_log), in 3 or 4 levels, depending on which subroutine is being called. They don't include a parameter for the RLWE ciphertext size here, but have a separate parameters file here. It looks like they handle up to computation modulo $128$ (e.g. 6 bit) arithmetic in a default parameter set. As for the size of their LWE ciphertext moduli, it used to be hardcoded to be $\approx 32$ or $\approx 64$ bits iirc. I am seeing some references to CRT/RNS forms of ciphertexts in the codebase though, so this may no longer be the case, and I can't easily find specific parameter sets they use for this.

  • $\begingroup$ Thank you Mark for the answer! So, w.r.t. Q1 — when we decompose “big constant”, our main goal is to make sure that q/betta^level is small enough that the noise growth is “good”, right? In this case, q/betta, which is the largest factor in the decomposition, should by itself be small enough, no? Q2. I think it makes sense. Great suggestion to comb through the source code, I hope it will help me to “close the loop” here so to speak. $\endgroup$
    – Pier
    Jan 30 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.