About bootstrapping parameters

Library Questions
1

Hello everyone

I’m working on bootstrapping on CKKS.

I have three questions:

  1. How does levelBudget work? What are the advantages of having a large levelBudget and a small levelBudget?

  2. As above, what is bsgsDim? What is the difference between having a large bsgsDim and a small bsgsDim?

  3. Regarding static uint32_t GetBootstrapDepth(uint32_t approxModDepth, const std::vector<uint32_t> &levelBudget, SecretKeyDist secretKeyDist), I believe approxModDepth is the level consumed by the bootstrap. How does it work?

What can I do to improve the precision of bootstrapping?

Thank you in advance.

2

The OpenFHE implementation of CKKS bootstrapping uses the collapsed FFT method from this paper and the hoisting and modular approximation from this paper. Please read them to enhance your understanding of the bootstrapping procedure.

The levelBudget (for the CoeffsToSlots and SlotsToCoeffs transformations) dictate how many levels these transformations should take; more levels imply fewer rotations, see Section 3 of the first paper above.

The bsgsDim is used for the “baby-step giant-step” method for linear transforms. It also affects the efficiency through the number of rotations, and the internal default logic selects it according to the cost of rotations (see the second paper referenced above).

approxModDepth is the number of levels consumed by the evaluation of the approximate modular reduction inside bootstrapping, which is based on evaluating a trigonometric function and then double angle formula, as in the second paper reference above. The depth of the bootstrapping also includes the depth of the linear transformations (and some scaling), as seen from the definition of the function GetBootstrapDepth.

Precision depends on many factors. You can get a better precision by increasing the scaling factor, by ensuring the inputs to the bootstrap are between [-1,1], or by doing multiple iterations of bootstrapping such as in the example file iterative-ckks-bootstrapping. There are many discussions on the discourse forum about this, please take a look.

1 Like
3

Thanks for your reply.

I now have a better understanding of bootstrap.

I’ll take a look at the paper you mentioned.