Extra multiplication performed in bootstrapping

Library Questions
1

Hello there, newbie question here.

I am trying to optimize my CKKS circuit, and I found that here (line 418 of ckksrns-fhe.cpp, v.1.1.1), the EvalBootstrap procedure of CKKS perform a multiplication, does this add another level in the bootstrapping process?

AFAIK, I am using 5 + 5 for CoeffToSlots and SlotsToCoeff, 6+6 for Modular Reduction, but my bootstrapping uses 23 levels (which is \neq 22= 5+5+6+6)

Thank you very much!

2

Hi @narger ,

If you are referring to the built-in configuration, then 7 levels are used for the Chebyshev interpolation (degree close to 90 - see the table at https://github.com/openfheorg/openfhe-development/blob/main/src/pke/examples/FUNCTION_EVALUATION.md for the case when the inputs are normalized), 6 iterations are used for the double-angle formula, and 5 + 5 for encoding and decoding. This adds up to 23, as computed by .GetBootstrapDepth.

However, the multiplication you are referring adds one extra level, which is not accounted for by GetBootstrapDepth. I opened the issue for it: GetBootstrapDepth gives an incorrect depth (off by 1) · Issue #594 · openfheorg/openfhe-development · GitHub

1 Like
3

Thank you for the quick response! I have two more questions:

  • Why not using 119 as a degree for the Chebyshev Interpolation (since it requires the same number of levels) ?
  • Can that extra multiplication be added at user-level? Let’s say that before bootstrapping I perform a multiplication by a, couldn’t that extra multiplication be added so that I multiply by a \cdot x (where x is the value of that extra multiplication), saving one level?

Thank you again :slight_smile:

4
  • Why not using 119 as a degree for the Chebyshev Interpolation (since it requires the same number of levels) ?

There are several tradeoffs here: 1) degree 119 requires higher computational complexity than 89 (more key switching and rescaling operations; 2) the accuracy depends on many factors, the approximation of modular reduction using the sine wave, which depends on how much q is bigger than the message, recursive double-angle iterations after Chebyshev, etc.

For the second question, the scaling is not the first step (raising the modulus is done before that). If the scaling is done before raising the modulus, then the sine approximation will not work well (will have very poor accuracy).