I wanted to understand how the parameters levelBudget and levelsAvailableAfterBootstrap affects computation time for bootstrapping? What I understand currently from the implementation of the CKKS bootstrapping example is by decreasing levelBudget value from 4 to 1, we can decrease the modulus size. Does this affect the bootstrapping time in general? I think it would increase the time taken for every bootstrapping we do, since we are letting it do the computation with lesser levels? Also, if we decrease the levelsAvailableAfterBootstrap parameter, does it mean more frequent bootstrapping is required for multiplying, since the depth has deceased and more bootstrapping would increase the depth?
Another query I had is when you are doing multiplication for CKKS (advanced-real-numbers.cpp), does it invoke the bootstrapping function (EvalBootstrap(ciph)) implicitly? And how does it determine when to call, how is the depth determined for when to call bootstrapping?
What I understand currently from the implementation of the CKKS bootstrapping example is by decreasing levelBudget value from 4 to 1, we can decrease the modulus size. Does this affect the bootstrapping time in general?
Yes, it significantly affects the time. If you use less levels (using levelBudget), more rotations will be needed for the linear transform (especially for full packed ciphertexts).
Also, if we decrease the levelsAvailableAfterBootstrap parameter, does it mean more frequent bootstrapping is required for multiplying, since the depth has deceased and more bootstrapping would increase the depth?
Yes, more frequent bootstrapping will be needed.
Another query I had is when you are doing multiplication for CKKS (advanced-real-numbers.cpp), does it invoke the bootstrapping function (EvalBootstrap(ciph)) implicitly?
No, bootstrapping is needed only when all levels are exhausted (only 1 level is left). If you have 10 levels after bootstrapping, you can evaluate circuits with multiplicative depth up to 9 w/o any bootstrapping.
And how does it determine when to call, how is the depth determined for when to call bootstrapping?
EvalBootstrap is called by the user explicitly. Only key switching and modulus switching/rescaling are done automatically by the library.
Thanks a lot. That was very helpful. I am very confused about what the parameter levelBudget does exactly. I have read it in the comments, but could you give a more precise explanation as to what is its purpose? How is it different from bootstrapdepth parameter?
The OpenFHE implementation uses the optimized collapsed-FFT algorithm for homomorphic encoding/decoding proposed in Section 3 of Improved Bootstrapping for Approximate Homomorphic Encryption I suggest looking at Figure 1 of the cited paper to get an idea how the number of consumer levels (level budget) affects the computational complexity (for different numbers of slots).