This bugreport is already up as issue 1264 on github, but this website seems like the more appropriate place for it, so ill duplicate it here. If I am wrong, apologies for the double report 
Version v1.5.1 release and dev @ acdaf5e; CPU backend,
macOS/clang, NATIVE_SIZE=64, FLEXIBLEAUTO, HYBRID, UNIFORM_TERNARY, ring 4096.
what
With sparse packing (64 out of 2048 slots), a correct (to 1.2e-14 immediately before) ciphertext comes back with O(1) error (~0.5 absolute on a 0.3 amplitude message) after EvalBootstrap for level budgets {4,4} and {5,5}, while {3,1}, {2,2}, {3,3}, {4,2}, {4,3}, {4,6} and {6,6} all return the expected ~5e-07. Fully packed ciphertexts are unaffected at every budget I tested.
which budgets fail
The trigger is the decoding budget levelbudget[1] alone, as levelbudget[0] does not demonstrate this behavior. It requires SelectLayers(logSlots, levelBudget[1]) (ckksrns-utils.cpp:55-77) to return rem != 0 — necessary but not sufficient, see below. For 64 slots (=> logSlots = 6), every rem != 0 budget does fail:
| levelBudget {enc,dec} | SelectLayers(6,dec) = {layers,rows,rem} | max abs err after bootstrap |
|---|---|---|
| {3,1} | {6,1,0} | 5.887723e-07 |
| {2,2} | {3,2,0} | 5.336707e-07 |
| {3,3} | {2,3,0} | 3.912903e-07 |
| {4,2} | {3,2,0} | 4.342297e-07 |
| {4,3} | {2,3,0} | 4.820358e-07 |
| {4,4} | {1,3,3} | 4.390237e-01 |
| {2,4} | {1,3,3} | 4.556276e-01 |
| {6,4} | {1,3,3} | 5.332023e-01 |
| {4,6} | {1,6,0} | 4.689344e-07 |
| {5,5} | {1,4,2} | 3.515473e-01 |
| {6,6} | {1,6,0} | 4.954322e-07 |
The 6 decoding budgets allowed at logSlots = 6 are covered. The rule predicted {2,4} and {6,4} to fail and {4,6}, {3,1} to pass before they were run. EvalBootstrapSetup warns/clamps only when the budget is over logSlots (ckksrns-fhe.cpp:130-148).
At 256 slots (logSlots = 8, all 8 decoding budgets, enc fixed at 2) rem != 0 is not sufficient: dec 1, 2, 4, 8 (rem = 0) all clean at 1.19e-06 to 1.61e-06 and dec 5, 6, 7 (rem = 4, 3, 2) fail at 6.919277e-01, 5.906955e-01 and 4.644120e-01, but dec 3 (rem = 2) is clean at 1.385e-06. rem != 0 is required for the faulty block to run, but the message is destroyed only when the wrong stride also changes the rotation modulo slots. At 256/dec=3 it doesn’t — g=8, gRem=4, shiftScaleRem=64, so the correct 64 x 4 = 256 and the buggy 64 x 8 = 512 are both 0 mod 256.
reproduction (c11a_repro.cpp) encrypt 64 out of 2048 slots, apply 29 levels EvalMult by the all-ones plaintext encoded at the ciphertext’s own slot count (so no slot mismatch is involved and the expected result is the input), then EvalBootstrap and compare against the plaintext reference. ./c11a_repro 4 4 vs ./c11a_repro 3 3.
Build
c++ -std=c++17 -O2 c11a_repro.cpp -o c11a_repro \
-I$P/include/openfhe -I$P/include/openfhe/core -I$P/include/openfhe/pke \
-I$P/include/openfhe/binfhe -L$P/lib \
-lOPENFHEpke -lOPENFHEcore -lOPENFHEbinfhe # $P = install prefix
Run (with results on stock v1.5.1)
$ ./c11a_repro 4 4
sparse slots=64 levelBudget={4,4} err before boot = 1.225e-14 err AFTER boot = 6.150e-01 (towers 26 -> 33)
full slots=2048 levelBudget={4,4} err before boot = 1.053e-13 err AFTER boot = 3.480e-05 (towers 26 -> 33)
$ ./c11a_repro 3 3
sparse slots=64 levelBudget={3,3} err before boot = 1.094e-14 err AFTER boot = 6.102e-07 (towers 24 -> 33)
full slots=2048 levelBudget={3,3} err before boot = 1.185e-13 err AFTER boot = 2.767e-05 (towers 24 -> 33)
$ ./c11a_repro 2 4 # encoding budget changed, decoding budget still 4
sparse slots=64 levelBudget={2,4} err before boot = 1.521e-14 err AFTER boot = 7.057e-01 (towers 24 -> 33)
full slots=2048 levelBudget={2,4} err before boot = 1.311e-13 err AFTER boot = 3.325e-05 (towers 24 -> 33)
root cause
Issue #1112 - this is its’ unfixed half. PR #1113 corrected the divisor ij / p.g → ij / p.gRem in both branches of FHECKKSRNS::EvalSlotsToCoeffsPrecompute but left the multiplier. In the sparse branch’s flagRem == 1 block (v1.5.1 :1803, dev commit acdaf5e :2115) rotScale is still p.g even though the rotation divides by p.gRem (dev :2131, v1.5.1 :1817), so it comes out as -shiftScaleRem * p.g * (ij / p.gRem) instead of -shiftScaleRem * p.gRem * (ij / p.gRem). The full-packing branch (dev :2055, v1.5.1 :1749) uses p.gRem already, and the same sparse block’s limit is p.bRem * p.gRem. flagRem == 1 explains why at 64 slots this occurs only for decoding budgets 4 and 5, as 6 can’t be divided by them.
one-line fix for dev acdaf5e, tested
diff --git a/src/pke/lib/scheme/ckksrns/ckksrns-fhe.cpp b/src/pke/lib/scheme/ckksrns/ckksrns-fhe.cpp
--- a/src/pke/lib/scheme/ckksrns/ckksrns-fhe.cpp
+++ b/src/pke/lib/scheme/ckksrns/ckksrns-fhe.cpp
@@ -2112,7 +2112,7 @@ std::vector<std::vector<ReadOnlyPlaintext>> FHECKKSRNS::EvalSlotsToCoeffsPrecomp
if (flagRem == 1) {
const int32_t shiftScaleRem = 1 << (smax * p.layersCollapse);
- const int32_t rotScale = shiftScaleRem * static_cast<int32_t>(p.g);
+ const int32_t rotScale = shiftScaleRem * static_cast<int32_t>(p.gRem);
const uint32_t limit = p.bRem * p.gRem;
After applying:
| config | before | after |
|---|---|---|
| {4,4} | 6.210330e-01 | 3.887558e-07 |
| {5,5} | 3.515473e-01 (v1.5.1) | 5.317378e-07 |
| {2,4} | 4.556276e-01 (v1.5.1) | 6.175081e-07 |
| {3,3} (control, was passing) | 4.916959e-07 | 5.794481e-07 |
| full packing (control) | 3.577487e-05 | 3.786088e-05 |
| fresh sparse (control) | 1.169898e-14 | 1.450923e-14 |
Reverting the patch and rebuilding brings the failure back (5.742682e-01).
I’ll happily open the PR if needed.