Precision for the bootstrapping

Library Questions
1

Hi,

I have a few questions regarding repeated bootstrapping and its effect on precision in the CKKS scheme.

  1. When I perform bootstrapping multiple times on a ciphertext, I observe that the precision drops significantly after the first bootstrapping (e.g., from 36 bits down to 10 bits). However, subsequent bootstrapping operations do not reduce the precision as drastically. What could be the reason for this sharp drop only during the first bootstrapping?
  2. After performing a large number of consecutive bootstrapping operations, I observe that the precision eventually drops to zero, even though the ciphertext still has sufficient remaining levels. Is there any recommended way to refresh or restore the precision at this point?
  3. If precision loss makes further computation unusable even though bootstrapping is applied, can we still claim that this is a fully homomorphic encryption scheme in practice?
2

Hi @Nightingale,

I suggest reading the following two papers: https://arxiv.org/pdf/2410.21824 (discusses practical CKKS errors and single- and double-precising bootstrapping - this paper is for a non-FHE-expert) and Appendix E.3 of Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys (this is a crypto paper that has relevant graphs for successive CKKS bootstrapping invocations).

A couple of guidelines:

  1. The precision of CKKS bootstrapping is sensitive to the parameters, especially the scaling mod size, the ratio of first modulus size and scaling mod size, and the number of slots. For instance, a larger scaling factor can be used. See openfhe-development/src/pke/examples/simple-ckks-bootstrapping-composite-scaling.cpp at main · openfheorg/openfhe-development · GitHub for an example with a very high precision.
  2. The double-precision CKKS bootstrapping can be used. See openfhe-development/src/pke/examples/iterative-ckks-bootstrapping.cpp at main · openfheorg/openfhe-development · GitHub and openfhe-development/src/pke/examples/iterative-ckks-bootstrapping-composite-scaling.cpp at main · openfheorg/openfhe-development · GitHub for examples.
  3. In many cases, the precision loss of CKKS matches the precision of fixed-precision or floating-precision arithmetic for problems dealing with real-number arithmetic. So it can be used to solve the same problems as double-precision floating arithmetic (in the clear) is used for. Most of the practical ML problems typically do not require a larger floating-point precision (actually single-precision arithmetic is even often used).
  4. Note that CKKS bootstrapping can be applied for exact arithmetic and can be used for evaluating an arbitrary circuit (in a theoretical sense). In this setting, the noise can be reduced using Hermite interpolation polynomials (by setting derivatives at desired interpolation points to zero). See General Functional Bootstrapping using CKKS for more details (and specifically section 3.4 for details on noise reduction).

In summary, CKKS can theoretically be used for an arbitrary approximate or exact arithmetic circuit. Of course, the cost will become higher as the precision is increased.

1 Like