How exactly is the scaling factor adjusted in general functional bootstrap using ckks

FHE Questions
1

Hi, I’m trying to understand the paper General Functional Bootstrapping using CKKS (https://eprint.iacr.org/2024/1623.pdf).

bts
bts748×852 164 KB

In line 3 of the algorithm 1 in the paper, the ciphertext ct_1, encrypting \frac{q'_0}{p}m(X) \mod q'_0 is multiplied by \frac{\Delta}{q'_0} and gets a new ciphertext ct_2 encrypting
\Delta\frac{m(X)}{p} \mod q'_0.

My question is how this adjusting the scaling factor can be implemented in practice?

If \frac{\Delta}{q'_0} is an integer, the step is straightforward, it is simply a multiplication by a plaintext constant.

However, if \Delta < q'_0, then \frac{\Delta}{q'_0} is not an integer, so we cannot directly multiply the ciphertext by this factor in the usual CKKS representation. Normally, to reduce the scale factor of the ciphertext (from q'_0\frac{m(X)}{p} to \Delta\frac{m(X)}{p}), CKKS requires a rescale operation, but rescaling also changes the modulus, whereas line 3 explicitly states that the ciphertext must remain under the same modulus q'_0.

So I am unsure how this step can be performed while keeping the modulus fixed.

Any clarification on how this scaling adjustment can be performed would be greatly appreciated

2

You are right that no rescaling operation (as in CKKS) is needed. We only need to cleverly scale the coefficient and switch the modulus, as coefficient-encoded RLWE and CKKS ciphertexts are the two sides of the same coin.

In practice, the conversion is done in a single step, and we indeed have to distinguish two cases:

  • If q'_0 > q, we simply take the coefficients from the polynomial of the RLWE ciphertext, switch the modulus from q to q'_0 (hence the scaling becomes q'_0/P - with a new modulus q'_0), and then multiply and round by \Delta/q'_0 (no change to the modulus).
  • If q'_0 < q, we start by multiplying and rounding by \Delta/q'_0 (hence the scaling becomes (\Delta q)/(q'_0P) - with old modulus q), and then perform modulus switching to get the correct result - with new modulus q'_0.

Note that we only change the modulus in the modswitch. The multiply and round operation only acts on the coefficients, not the modulus.

Additionally, given that q'_0\approx \Delta and that q\approx q'_0, we can conveniently choose \Delta=q=2^k.

A concrete implementation is given in the latest version of OpenFHE as SchemeletRKWEMP::ConvertRLWEToCKKS (see the source here). In this implementation, q'_0=qPrimeCKKS and q=\Delta=Bigq.

3

Thank you for your kind reply. Well I understand that scaling the coefficients of an RLWE ciphertext changes the scaling factor of the underlying message. However, I am still unsure what happens to the actual plaintext value during this operation.
For instance, in the second case, if the RLWE ciphertext ct = (b,a) is originally under modulus q, meaning its coefficients satisfy,

b + a \cdot s \mod q = \frac{q}{P}\cdot m + e

this implies that

b + a \cdot s = \frac{q}{P}\cdot m + e + k\cdot q

for some integer k.
If we multiply and round \frac{\Delta}{q'_0}, namely

b' = \left \lceil \frac{\Delta}{q'_0} b \right \rfloor \\ a' = \left \lceil \frac{\Delta}{q'_0} a \right \rfloor

The new ciphertext ct' = (b',a') satifices

b' + a' \cdot s = \left \lceil \frac{q\Delta}{Pq'_0}\cdot m \right \rfloor+ + \left \lceil \frac{\Delta}{q'_0}\cdot k\cdot q \right \rfloor + e' + e_{r}

for some rounding error e_{r}.
My concern is the term \left \lceil \frac{\Delta}{q'_0}\cdot k\cdot q \right \rfloor, if q'_0 \approx \Delta, then this term is approximately kq, which can be reduced modulo q and therefore does not affect the plaintext.
However, if q'_0 >> \Delta, the term \left \lceil \frac{\Delta}{q'_0}\cdot k\cdot q \right \rfloor is no longer close to a multiple of q, meaning it cannot be reduced modulo q. In that case,

b' + a' \cdot s \mod q= \left \lceil \frac{q\Delta}{Pq'_0}\cdot m \right \rfloor+ + \left \lceil \frac{\Delta}{q'_0}\cdot k\cdot q \right \rfloor + e' + e_{r}

which appears to shift the plaintext to \left \lceil \frac{q\Delta}{Pq'_0}\cdot m \right \rfloor+ + \left \lceil \frac{\Delta}{q'_0}\cdot k\cdot q \right \rfloor ignoring noise terms.
This seems to suggest that the scaling step only works correctly in special cases such as q'_0 \approx \Delta, is that correct? Am I missing something?

4

Going back to the theoretical algorithm performs: it performs two distinct steps, and the wrap-around term k \cdot q is eliminated in the first step.

  • Input \mathsf{ct}\in\mathcal R_q: \mathsf{Dec}(\mathsf{ct}) = b+as = \frac{q}{P}m + e + k \cdot q

  • Line 2: \mathsf{ct}_1 = \mathsf{ModSwitch}(\mathsf{ct}, q'_0)\in\mathcal R_{q'_0}
    This operation is \mathsf{ct}_1 = \lfloor \frac{q'_0}{q} \mathsf{ct} \rceil \pmod{q'_0}.
    The new plaintext value is:
    \mathsf{Dec}(\mathsf{ct}_1) \approx \frac{q'_0}{q} (b+as) \pmod{q'_0} = \frac{q'_0}{q} (\frac{q}{P}m + e + k \cdot q) \pmod{q'_0} = (\frac{q'_0}{P}m + \frac{q'_0}{q}e + k \cdot q'_0) \pmod{q'_0}
    Since k \cdot q'_0 \equiv 0 \pmod{q'_0}, the wrap-around term vanishes. \mathsf{ct}_1 cleanly encrypts \frac{q'_0}{P}m under modulus q'_0.

  • Line 3: \mathsf{ct}_2 = (Δ/q'_0) \cdot \mathsf{ct}_1\in\mathcal R_{q'_0}
    This is now a simple plaintext multiplication on a “clean” ciphertext:
    \mathsf{Dec}(\mathsf{ct}_2) \approx \frac{\Delta}{q'_0} \cdot \mathsf{Dec}(\mathsf{ct}_1) \pmod{q'_0}

The integer-level wrap-around from the k \cdot q term is resolved by the \textsf{ModSwitch} in Line 2, before \Delta is introduced.

In my previous answer, I explained how it was done in practice because that was your question, that is in the OpenFHE library, where indeed q'_0\approx\Delta. I hope this clarifies my previous answer.

5

Thanks, my previous question may have been misleading.
I now understand that in Line 2,

\mathsf{Dec(ct_1)} \approx \frac{q'_0}{P}m + \frac{q'_0}{P}e + k\cdot q'_0

and under modulus q'_0, it encrypts \frac{q'_0}{P}m.
In Line 3, we apply a simple multiplication of \frac{\Delta}{q'_0} to ct_1, As you mentioned,

\mathsf{Dec(ct_2)} \approx \frac{\Delta}{q'_0}\mathsf{Dec(ct_1)}

Substituting the expression for \mathsf{Dec(ct_1)} = \frac{q'_0}{P}m + \frac{q'_0}{P}e + k\cdot q'_0,

\mathsf{Dec(ct_2)} \approx \frac{\Delta}{q'_0} \cdot \frac{q'_0}{P}m + \frac{\Delta}{q'_0}\cdot \frac{q'_0}{P}e + \frac{\Delta}{q'_0}\cdot k\cdot q'_0\\ \approx \frac{\Delta}{P}m + \frac{\Delta}{P}e + \Delta \cdot k

and under modulus q'_0, the resulting plaintext appears to be \frac{\Delta}{P}m + \frac{\Delta}{P}e + \Delta \cdot k \mod q'_0.
If q'_0 \approx \Delta, the resulting plaintext is \frac{\Delta}{P}m \mod q'_0.
Is this understanding correct?

6

Yes, your understanding seems to be correct. Additionally, in Table 2 of the aforementioned paper, it is indicated that \log(q) = \log(\Delta) = \log(q'_0).

7

As @jdumezy explained, we use a q'_0 such that \log(q'_0) = \log(\Delta) (and actually q = \Delta \approx q'_0) for convenience, as we did not notice a significant loss in precision from line 3. But if one starts with q'_i >> \Delta for i > 0, then the correction needs to be done also with reducing the modulus, which is why we have the line under the algorithm “Adjusting the scaling factor in line 3 of Algorithm 1 may require another level”.

1 Like
8

I see, thank you so much.