Accuracy Degradation in Iterative Bootstrapping with CKKS Scheme in Deep Circuits

Library Questions
1

I am developing an application using the CKKS scheme for complex computations, but I am encountering issues with accuracy during iterative bootstrapping.

Problem Description

My workflow involves 128 iterative bootstrappings, interleaved with complex calculations that require 25 multiplicative levels and numerous rotations. The input message is always downscaled to [-1, 1].

To diagnose the issue, I compared the data directly before and after each bootstrapping operation. Initially, the results seem accurate, with an L_\infty error of about 10^{-12} to 10^{-11} after each bootstrapping.

However, as the number of bootstrappings increases, the error grows significantly. By the 128th bootstrapping, the error reaches approximately 10^{-3}, which is too high for my application.

This behavior is puzzling because I observe the error increasing for every distinct bootstrapping operation, even though the operations are independent. While some accumulation of error across iterations is expected, the increasing error for each bootstrapping in isolation seems strange.

Observations and Challenges

  1. Single bootstrapping crashes when approximation errors become too high.
  2. I considered using 128-bit native size, but the combination of the required 25 multiplicative levels and the increased scaling modulus size (that is the matter of using 128-bit) would violate the 128-bit security level (with OpenFHE’s limit of ring dimension 2^{17}).

Parameters Used

  • Secret Key Distribution: SPARSE_TERNARY
  • Security Level:
    • Testing: HEStd_NotSet
    • Production: HEStd_128_classic
  • Ring Dimension:
    • Testing: 2^7
    • Production: 2^{17}
  • Number of Slots: 2^6
  • Rescale Technique: FLEXIBLEAUTO
  • Scaling Mod Size: 59
  • First Mod Size: 60
  • Bootstrapping Level Budget: [2, 2]
  • Approximate Precision of Single Bootstrapping: 19 bits

Questions

  1. Could someone help explain why accuracy degrades for each distinct bootstrapping operation, as observed in direct comparisons before and after each bootstrapping?
  2. Are there any techniques or parameter adjustments that could help improve the accuracy of iterative bootstrapping while maintaining the required security level?

Any ideas or insights would be greatly appreciated!

2

This is not easy to address without examining the problem closely.

You can try the following though:

  1. Use FLEXIBLEAUTOEXT (default in OpenFHE) instead of FLEXIBLEAUTO.
  2. For the bootstraps that fail, try to bootstrap one level earlier, that is, move the final multiplication right before bootstrapping to be done after bootstrapping.
  3. Reduce the scaling mod size to 50-ish (maybe 53). If your message magnitude is small, I do not think you need a large scale.

The best approach is to keep examining this closely. There are several studies that used CKKS for even higher deth circuits than what is described here.

BTW, if 128-bit integer size is an option, there is no reason to keep the multiplicative depth high, reduce it (to satisfy the 128-bit security requirements) and bootstrap more.

3

Thank you for the response!

The three suggestions didn’t solve the issue. But you are right, it is really something very application-specific. I tried adjusting other numerical parameters in my application (which are not directly related to OpenFHE), and I managed to achieve a precision of 10^{-7} even for a circuit that is twice as deep.

The suggestion about 128-bit native size and reducing the multiplicative depth is very interesting—I will definitely try it!

Since my issue now appears to be more application-specific rather than general, I will mark your answer as a solution and continue examining my specific case more closely.

Thank you again for your valuable insights!