CKKS bootstrapping procedure

FHE Questions
1

I’m curious about actual bootstrapping procedure of CKKS (also, RNS CKKS). i.e. I want to know about more detailed equations with examples (if possible) while conducting bootstrapping.

Bootstrapping for Approximate Homomorphic Encryption proposes bootstrapping for CKKS.
Bootstrapping is consist of mod raise, coeff to slot, eval on approx. sine function and slot to coeff.

Can you explain about each process with equations or examples?

  1. In mod raise step, how it actually raise their modulus on CKKS and RNS CKKS?
    Raise their modulus by Approximate Modulus Raising in page 8 of A Full RNS Variant of Approximate Homomorphic Encryption ? or using other method?

  2. In coeff to slot and slot to coeff, Bootstrapping for Approximate Homomorphic Encryption says that multiply the en/decoding matrix to the coefficient of mod raised cihertext. It actually perform the multiplication between the coefficient vector and en/decoding matrix?
    I mean, coefficient vector is consist of integers and en/decoding matrix are consist of complex number, we conduct the complex number - integer multiplication for coeff to slot/ slot to coeff?
    The result is integer vector (polynomial in integer ring (without modular)) produced by above matrix-vector multiplication?

  3. Improved bootstrapping for approximate homomorphic encryption proposes FFT-like algorithms for coeff to slot and slot to coeff.
    Can you explain more detailed about page 9,10?
    Equation in middle of page 9, w := a[i]*w + b[i] *(w << 2^(i-1)) + c[i] *(w >>(2^(i-1)), a,b and c are vectors consist of complex number.
    The w is coefficient vector and a,b and c are complex vectors that consist of encoding matrix values? (actually, diagonal component?) and the result is also integer vector same as above question?

2

I suggest looking at the OpenFHE implementation: method EvalBootstrap (openfhe-development/src/pke/lib/scheme/ckksrns/ckksrns-fhe.cpp at v0.9.3 · openfheorg/openfhe-development · GitHub) All the main subroutines are implemented in the same place (or can be traced from that code).

The closest algorithmic description of what is implemented in OpenFHE is provided in Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys Note we use the same scaling factor for all ciphertexts at the same multiplicative level (a different RNS variant of CKKS). More information on the CKKS implementation in OpenFHE is available at Approximate Homomorphic Encryption with Reduced Approximation Error

2 Likes
3

Thanks for your answer.
I’ll check the code and other papers that you suggested.