Skip to content

CKKS: single-iteration UNIFORM_TERNARY standard bootstrap produces wrong values (FLEXIBLEAUTO, scaleModSize 50, multDepth ≥ 25) #1364

Closed

Description

@carlostriste

Summary

On OpenFHE v1.6.0, the single-iteration standard CKKS bootstrap with a UNIFORM_TERNARY
secret returns value-wrong output
at common parameters. The result fails to decrypt through the
public API:

Decode(): The decryption failed because the approximation error is too high. Check the parameters.

and a guard-free decode shows the values are off by ~0.2–0.5 instead of ~1e-4.

The SPARSE_TERNARY table and the 2-iteration pipeline are unaffected, so this is not a generic
bootstrap break.

  • Affected: FLEXIBLEAUTO, UNIFORM_TERNARY, levelBudget={3,3}, scalingModSize=50,
    multiplicativeDepth ≥ 25, 1 iteration, ModRaise-first standard bootstrap.
  • Not affected: SPARSE_TERNARY (same config); 2-iteration UNIFORM_TERNARY;
    scalingModSize=59; multiplicativeDepth=20.
  • Reproduces on a clean checkout of tag v1.6.0 (6206d24f), no patches, no FIDESlib, CPU only.
  • Correct on 1.5.1 with the same program.

Environment

OpenFHE (failing) tag v1.6.0, commit 6206d24f ("Merge pull request #1362 from openfheorg/dev")
OpenFHE (working) 1.5.1
Build Release, MATHBACKEND=4, 64-bit, -O3 -fopenmp, no NATIVEINT override
OS / toolchain Ubuntu 22.04.5, g++ 11.4.0, CMake 4.1.0, AMD Ryzen 9 7900
GPU / accelerator none involved — raw OpenFHE only

Stock tag build:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release \
      -DBUILD_UNITTESTS=OFF -DBUILD_EXAMPLES=OFF -DBUILD_BENCHMARKS=OFF \
      -DBUILD_SHARED=ON -DBUILD_STATIC=OFF \
      -DCMAKE_INSTALL_PREFIX=$PREFIX
cmake --build build -j"$(nproc)" && cmake --install build

Minimal reproducer

// uniform_bootstrap_1iter.cpp
#include "openfhe.h"
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace lbcrypto;

// Decrypt while bypassing CKKSPackedEncoding::Decode's precision guard (EXEC_EVALUATION
// instead of EXEC_DECRYPT), so the wrong values can be printed. The public cc->Decrypt
// path is also exercised: on the buggy version it throws before we get here.
static std::vector<std::complex<double>> DecodeNoGuard(CryptoContext<DCRTPoly>& cc,
                                                       const PrivateKey<DCRTPoly>& sk,
                                                       ConstCiphertext<DCRTPoly> shell, uint32_t slots) {
    Plaintext p = PlaintextFactory::MakePlaintext(CKKS_PACKED_ENCODING, shell->GetElements()[0].GetParams(),
                                                  cc->GetEncodingParams(), SCHEME::INVALID_SCHEME, COMPLEX);
    cc->GetScheme()->Decrypt(shell, sk, &p->GetElement<Poly>());
    auto ckks = std::dynamic_pointer_cast<CKKSPackedEncoding>(p);
    ckks->SetNoiseScaleDeg(shell->GetNoiseScaleDeg());
    ckks->SetLevel(shell->GetLevel());
    ckks->SetScalingFactor(shell->GetScalingFactor());
    ckks->SetSlots(slots);
    auto params = std::dynamic_pointer_cast<CryptoParametersRNS>(cc->GetCryptoParameters());
    ckks->Decode(shell->GetNoiseScaleDeg(), shell->GetScalingFactor(), params->GetScalingTechnique(),
                 EXEC_EVALUATION);
    return ckks->GetCKKSPackedValue();
}

static bool run(const char* label, SecretKeyDist skd, uint32_t numIterations, uint32_t precision) {
    const uint32_t multDepth = 25, scaleModSize = 50, batchSize = 8, ringDim = 1 << 12;

    CCParams<CryptoContextCKKSRNS> parameters;
    parameters.SetSecretKeyDist(skd);
    parameters.SetScalingTechnique(FLEXIBLEAUTO);
    parameters.SetMultiplicativeDepth(multDepth);
    parameters.SetScalingModSize(scaleModSize);
    parameters.SetBatchSize(batchSize);
    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetRingDim(ringDim);

    CryptoContext<DCRTPoly> cc = GenCryptoContext(parameters);
    cc->Enable(PKE);
    cc->Enable(KEYSWITCH);
    cc->Enable(LEVELEDSHE);
    cc->Enable(ADVANCEDSHE);
    cc->Enable(FHE);

    auto keys = cc->KeyGen();
    cc->EvalMultKeyGen(keys.secretKey);
    cc->EvalBootstrapSetup({ 3, 3 }, { 0, 0 }, batchSize, /*correctionFactor=*/0);
    cc->EvalBootstrapKeyGen(keys.secretKey, batchSize);

    const std::vector<double> x = { 0.25, 0.5, 0.75, 1.0, 2.0, 3.0, 4.0, 5.0 };
    auto ptxt = cc->MakeCKKSPackedPlaintext(x, 1, multDepth - 1, nullptr, batchSize);
    auto ctxt = cc->Encrypt(keys.publicKey, ptxt);

    auto c = cc->EvalBootstrap(ctxt, numIterations, precision);

    // The public decrypt path (with the precision guard).
    bool publicDecryptOk = true;
    try {
        Plaintext r;
        cc->Decrypt(keys.secretKey, c, &r);
    } catch (const std::exception& e) {
        publicDecryptOk = false;
        std::cout << "[" << label << "] public Decrypt THREW: " << e.what() << "\n";
    }

    // Guard-free decode to measure the actual error.
    double maxErr = 0.0;
    std::vector<double> got;
    try {
        auto v = DecodeNoGuard(cc, keys.secretKey, c, batchSize);
        for (uint32_t i = 0; i < batchSize; ++i) {
            got.push_back(v[i].real());
            maxErr = std::max(maxErr, std::abs(v[i].real() - x[i]));
        }
    } catch (const std::exception& e) {
        std::cout << "[" << label << "] guard-free decode THREW: " << e.what() << "\n";
        return false;
    }

    const bool pass = publicDecryptOk && maxErr < 1e-2;
    std::cout << "[" << label << "] maxErr=" << std::scientific << std::setprecision(3) << maxErr
              << "  first values:";
    for (int i = 0; i < 4; ++i)
        std::cout << " " << std::fixed << std::setprecision(4) << got[i];
    std::cout << "  => " << (pass ? "PASS" : "FAIL") << std::endl;
    return pass;
}

int main() {
    std::cout << "MRE: standard CKKS bootstrap, FLEXIBLEAUTO, ring 2^12, slots 8, "
                 "scaleModSize 50, multDepth 25, levelBudget {3,3}, auto correction factor\n";
    bool ok = true;
    ok &= run("UNIFORM FLEX 1it", UNIFORM_TERNARY, /*numIterations=*/1, /*precision=*/0);
    ok &= run("UNIFORM FLEX 2it", UNIFORM_TERNARY, /*numIterations=*/2, /*precision=*/10);
    ok &= run("SPARSE  FLEX 1it", SPARSE_TERNARY, /*numIterations=*/1, /*precision=*/0);
    return ok ? 0 : 1;
}

Build / run:

PREFIX=<an OpenFHE install prefix>
g++ -std=c++17 -O2 uniform_bootstrap_1iter.cpp -o repro \
    -I$PREFIX/include/openfhe/pke -I$PREFIX/include/openfhe/core \
    -I$PREFIX/include/openfhe/binfhe -I$PREFIX/include/openfhe -I$PREFIX/include \
    -L$PREFIX/lib -lOPENFHEpke -lOPENFHEcore -lOPENFHEbinfhe -Wl,-rpath,$PREFIX/lib
./repro   # exits non-zero if any row FAILs

Expected vs actual

Expected (correct), e.g. OpenFHE 1.5.1:

[UNIFORM FLEX 1it] maxErr=1.107e-04  first values: 0.2499 0.5000 0.7500 1.0000  => PASS
[UNIFORM FLEX 2it] maxErr=1.229e-07  first values: 0.2500 0.5000 0.7500 1.0000  => PASS
[SPARSE  FLEX 1it] maxErr=3.406e-05  first values: 0.2500 0.5000 0.7500 1.0000  => PASS

Actual on OpenFHE v1.6.0 (6206d24f, clean, unpatched):

[UNIFORM FLEX 1it] public Decrypt THREW: ... Decode(): The decryption failed because the approximation error is too high. Check the parameters.
[UNIFORM FLEX 1it] maxErr=4.332e-01  first values: 0.0002 0.5071 0.7654 0.9500  => FAIL
[UNIFORM FLEX 2it] maxErr=5.492e-04  first values: 0.2502 0.5001 0.7495 1.0001  => PASS
[SPARSE  FLEX 1it] maxErr=4.684e-05  first values: 0.2500 0.5000 0.7500 1.0000  => PASS

(Encryption is randomized, so decoded values vary run to run; the maxErr magnitude and the
public-Decrypt throw are stable. A patched fork additionally gave maxErr=3.185e-01, first
values 0.3176 0.3852 0.6900 0.9292 — same failure.)

Parameter sensitivity

Reproduces for scalingModSize = 50 with multiplicativeDepth >= 25 at every ring dimension
tested (2^12 … 2^16). It does not reproduce at multiplicativeDepth = 20 (scale 50) nor at
scalingModSize = 59 (depth 25/30). So it is tied to the parameter family (scale 50 + deep
chain), not the ring dimension or packing.

Analysis / probable origin

The UNIFORM_TERNARY approximation changed upstream in 1.6.0 with
#1332 "Increase K for uniform-secret CKKS bootstrapping variants":

  • K_UNIFORM 512 → 648,
  • g_coefficientsUniform degree 92 → 104,
  • a (2π)^(-1/64)-scaled double-angle formulation,
  • together with the Paterson–Stockmeyer basis adjustments in
    ckksrns-advancedshe.cpp / ckksrns-leveledshe.cpp.

1.5.1 predates #1332 and is correct. The 2-iteration error-correcting pass masks the single-pass
error, and SPARSE_TERNARY uses a different table/K, which is why both are unaffected.

The failure mode (silently wrong values on a single pass, with Decode rejecting the result rather
than an exception during evaluation) points at the single-pass Paterson–Stockmeyer evaluation of the
new degree-104 / K = 648 table interacting with the auto correction factor / degree computation —
i.e. the approximation consumes more of the available modulus at scaleModSize = 50 than the chain
budget accounts for. This is a hypothesis pending a bisect (see below).

Not caused by the reported environment's patches

The failure was first observed while validating an external CPU/GPU backend (FIDESlib) against the
1.6.0 reference, but it reproduces with raw OpenFHE only, and on a clean v1.6.0 checkout
with no patches. It is not caused by any downstream fork commit.

Upstream status

Checked at report time: upstream main is exactly the v1.6.0 commit 6206d24f (no post-1.6.0
commits), so no fix is present. No matching issue was found in the tracker.

Suggested next steps

  1. Bisect 2f499f56..v1.6.0 with this reproducer to confirm the introducing commit (expected:
    Increase K for uniform-secret CKKS bootstrapping variants #1332).
  2. If Increase K for uniform-secret CKKS bootstrapping variants #1332 is the cause, review the interaction of the new degree-104 / K = 648
    UNIFORM_TERNARY table and its scaled-double-angle formulation with:
    • the auto correction-factor / degree computation, and
    • the single-pass Paterson–Stockmeyer basis alignment (AdjustLevelsAndDepthInPlace), at
      scaleModSize = 50.
  3. Add a CPU regression test at this parameter family (the existing UTCKKSRNS_BOOT sparse/full
    UNIFORM rows use scaleModSize = 59, which does not exercise it).

Additional context

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

bugSomething isn't working

Type

No type

Projects

No projects

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions