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