Help with TFHE (binfhe) code and its understanding

Library Questions
1

I am trying to understand the code here for decomposing the ciphertext. How is beta (the denominator for dividing the poly) chosen in the code? Also, any pointers into which algorithm exactly is the SignedDigitDecompose executing? I see two versions of the function in this code. What exactly is the code trying to do is what I want to understand.

The papers here and here are mentioned in the comment section, but which part of the papers explain the above decomposition algorithm? I don’t understand why it is called a signed decomposition, as I do not find it defined in both these papers.

2

Section of 2 Bootstrapping in FHEW-like Cryptosystems introduces the main relevant concepts. The high-level idea is that one can multiply a ciphertext by a large scalar by breaking the scalar into digits first and then multiplying by small digits. This is used for RLWE x RGSW in the accumulator (in this case acc, an RLWE ciphertext, is decomposed into digits).

3

Thank you. The SignedDigitDecompose function works on the 0th row and the 1st row of the input poly ciphertext. There could be as many as 12 rows in the input ciphertext but why is the operations done using only first two rows? What I mean to ask is why are there separate operations for d0 (and t0 and r0) and d1 (and t1 and r1) only. Why not d2 or d3 or more? Wanted to understand the logic behind it.

Also, the ‘input’ of type NativePoly passed as input to the SignedDigitDecompose contains the coefficients of the RLWE ciphertext, if my understanding is correct?

4

Because an RLWE ciphertext contains only 2 polynomials (ring elements). Digit decomposition converts (expands) a RLWE ciphertext into RLWE’ so that its multiplication by a RGSW ciphertext could be performed (this is described in Section 2 of the cited paper).

5

Thanks a lot.
Two questions here: what is RLWE’ to which the RLWE ciphertext is converted to? Is it RLEV you are referring to?

Secondly, why is it called “signed” decomposition? Any specific reason why the decomposition is done with signed digits?

6

Please read Section 2 of Bootstrapping in FHEW-like Cryptosystems (as already suggested above)

Signed digit decomposition is used for efficiency reasons (noise is smaller this way).

7

Thank you so much for the help. This really gives a good idea now. I am just curious if there is any paper which details out this algorithm for breaking the scalar into signed digits? I see it is similar to gadget decomposition, but wanted to understand how the carrries are propagated in this signed decomposition and how it helps overall with the noise. Any pointer to any relevant paper and its section will be immensely helpful!

8

It was initially introduced in FHEW: Bootstrapping Homomorphic Encryption in less than a second (see beginning of Page 10). The high-level idea is that digits will be zero-centered, and the noise growth will be smaller (following the Central Limit Theorem).

9

Awesome! That makes it clear. Is it right that FHEW/TFHE always operates on modular reductions cantered around zero?