[Bug report] 128-bit CKKS scalar EvalAdd/EvalSub/EvalMult can shift by out-of-range counts for tiny operands, and EvalMult can produce wrong results

Library Questions
1

Hi OpenFHE team,

I would like to report a reproducible 128-bit CKKS scalar-processing bug for extremely small finite double operands.

Summary

In the NATIVEINT == 128 CKKS scalar paths, OpenFHE derives:

int32_t pRemaining = pCurrent + n1;

from the scalar exponent returned by std::frexp(...).

For sufficiently small operands, pRemaining becomes strongly negative. The current negative branch then performs an unchecked right shift:

scaledConstant = NativeInteger(((uint128_t)scaled64) >> (-pRemaining));

in the EvalAdd/EvalSub helper, and:

scaled128 = scaled64 >> (-pRemaining);

in the EvalMult helper.

I reproduced two public effects on a 128-bit CKKS build:

  1. EvalMult(ciphertext, -2^-103):

    • reaches pRemaining = -64
    • triggers UBSan for a signed 64-bit right shift by 64 on an instrumented build
    • and, on a separate ordinary Clang 14 build, decrypts to approximately -1.8189894e-12 instead of a tiny or zero result

  2. EvalAdd(ciphertext, -denorm_min):

    • reaches pRemaining = -1035
    • reaches the EvalSub(...) path for negative operands
    • triggers UBSan for a 128-bit right shift by 1035

As a control, EvalMult(ciphertext, -2^-102) reaches pRemaining = -63, does not trigger shift-count UBSan, and decodes to a near-zero result. So the observed fault boundary is not just “small values in general” but the negative branch once the shift count first reaches the bit width of the shifted intermediate type or beyond.

Environment

  • OpenFHE local tested revision: ed361af22049007db2107e7c69bcff209e8c420d
  • Source links below use that exact tested revision
  • Configuration: NATIVE_SIZE=128, MATHBACKEND=4
  • OS: Linux x86_64
  • Compiler: Clang 14.0.0
  • UBSan/ASan confirmation build: AddressSanitizer, UndefinedBehaviorSanitizer
  • Separate wrong-result confirmation build: ordinary Clang 14 build without sanitizers

Representative OpenFHE build:

cmake -S openfhe-development -B build-openfhe-128-asan \
  -DNATIVE_SIZE=128 \
  -DMATHBACKEND=4 \
  -DCMAKE_C_COMPILER=clang-14 \
  -DCMAKE_CXX_COMPILER=clang++-14 \
  -DCMAKE_BUILD_TYPE=Debug \
  -DBUILD_UNITTESTS=OFF \
  -DBUILD_EXAMPLES=OFF \
  -DBUILD_BENCHMARKS=OFF \
  -DWITH_OPENMP=OFF \
  -DCMAKE_CXX_FLAGS='-fsanitize=address,undefined -fno-omit-frame-pointer -g -O0' \
  -DCMAKE_C_FLAGS='-fsanitize=address,undefined -fno-omit-frame-pointer -g -O0'
cmake --build build-openfhe-128-asan -j

Representative ordinary OpenFHE build used for wrong-result confirmation:

cmake -S openfhe-development -B build-openfhe-128-nosan \
  -DNATIVE_SIZE=128 \
  -DMATHBACKEND=4 \
  -DCMAKE_C_COMPILER=clang-14 \
  -DCMAKE_CXX_COMPILER=clang++-14 \
  -DCMAKE_BUILD_TYPE=Debug \
  -DBUILD_UNITTESTS=OFF \
  -DBUILD_EXAMPLES=OFF \
  -DBUILD_BENCHMARKS=OFF \
  -DWITH_OPENMP=OFF
cmake --build build-openfhe-128-nosan -j

Minimal reproduction

The reproducer below encrypts a vector of 1.0 values and then applies scalar EvalAdd, EvalSub, and EvalMult with tiny finite operands. It also prints the runtime plaintext modulus bits read from the generated crypto context, so the displayed pRemaining values are derived from the same internal parameter used by the helper.

#include <cmath>
#include <complex>
#include <iomanip>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

#include "openfhe.h"

using namespace lbcrypto;

namespace {

std::vector<std::complex<double>> DecryptVec(CryptoContext<DCRTPoly> cc, const PrivateKey<DCRTPoly>& sk,
                                             const Ciphertext<DCRTPoly>& ct, size_t slots) {
    Plaintext pt;
    cc->Decrypt(sk, ct, &pt);
    pt->SetLength(slots);
    return pt->GetCKKSPackedValue();
}

uint64_t RuntimePBits(CryptoContext<DCRTPoly> cc) {
    auto cryptoParams =
        std::dynamic_pointer_cast<CryptoParametersCKKSRNS>(cc->GetCryptoParameters());
    return cryptoParams->GetPlaintextModulus();
}

int32_t ComputePRemaining(double operand, uint64_t pBits) {
    int32_t n1 = 0;
    (void)std::frexp(operand, &n1);
    return static_cast<int32_t>(pBits - 52) + n1;
}

void RunCase(CryptoContext<DCRTPoly> cc, const PublicKey<DCRTPoly>& pk, const PrivateKey<DCRTPoly>& sk,
             const std::string& name, double operand) {
    std::vector<std::complex<double>> base(8, {1.0, 0.0});
    auto pt = cc->MakeCKKSPackedPlaintext(base);
    auto ct = cc->Encrypt(pk, pt);
    const auto pBits = RuntimePBits(cc);

    std::cout << "case=" << name << '\n';
    std::cout << std::setprecision(17);
    std::cout << "operand=" << operand << '\n';
    std::cout << "runtime_plaintext_modulus_bits=" << pBits << '\n';
    std::cout << "pRemaining=" << ComputePRemaining(operand, pBits) << '\n';

    auto addCt   = cc->EvalAdd(ct, operand);
    auto subCt   = cc->EvalSub(ct, std::fabs(operand));
    auto multCt  = cc->EvalMult(ct, operand);
    auto addDec  = DecryptVec(cc, sk, addCt, 8);
    auto subDec  = DecryptVec(cc, sk, subCt, 8);
    auto multDec = DecryptVec(cc, sk, multCt, 8);

    std::cout << "add_decoded0_real=" << addDec[0].real() << '\n';
    std::cout << "add_decoded0_imag=" << addDec[0].imag() << '\n';
    std::cout << "sub_decoded0_real=" << subDec[0].real() << '\n';
    std::cout << "sub_decoded0_imag=" << subDec[0].imag() << '\n';
    std::cout << "mult_decoded0_real=" << multDec[0].real() << '\n';
    std::cout << "mult_decoded0_imag=" << multDec[0].imag() << '\n';
}

}  // namespace

int main(int argc, char** argv) {
    std::cout << std::unitbuf;

    CCParams<CryptoContextCKKSRNS> parameters;
    parameters.SetMultiplicativeDepth(1);
    parameters.SetScalingModSize(90);
    parameters.SetFirstModSize(90);
    parameters.SetBatchSize(8);
    parameters.SetCKKSDataType(COMPLEX);

    auto cc = GenCryptoContext(parameters);
    cc->Enable(PKE);
    cc->Enable(KEYSWITCH);
    cc->Enable(LEVELEDSHE);

    auto kp = cc->KeyGen();

    if (argc == 2) {
        const std::string which = argv[1];
        if (which == "neg_pow2_102") {
            RunCase(cc, kp.publicKey, kp.secretKey, which, -std::ldexp(1.0, -102));
            return 0;
        }
        if (which == "neg_pow2_103") {
            RunCase(cc, kp.publicKey, kp.secretKey, which, -std::ldexp(1.0, -103));
            return 0;
        }
        if (which == "neg_denorm_min") {
            RunCase(cc, kp.publicKey, kp.secretKey, which, -std::numeric_limits<double>::denorm_min());
            return 0;
        }
        std::cerr << "unknown case: " << which << '\n';
        return 2;
    }

    RunCase(cc, kp.publicKey, kp.secretKey, "neg_pow2_102", -std::ldexp(1.0, -102));
    RunCase(cc, kp.publicKey, kp.secretKey, "neg_pow2_103", -std::ldexp(1.0, -103));
    RunCase(cc, kp.publicKey, kp.secretKey, "neg_denorm_min", -std::numeric_limits<double>::denorm_min());
    return 0;
}

Representative probe build:

clang++-14 -std=gnu++17 -fno-omit-frame-pointer -g -O0 \
  -fsanitize=address,undefined \
  openfhe_ckks_scalar_tiny_probe.cpp \
  -Iopenfhe-development/src/pke/include \
  -Iopenfhe-development/src/core/include \
  -Iopenfhe-development/src/binfhe/include \
  -Iopenfhe-development/third-party/cereal/include \
  -Ibuild-openfhe-128-asan/src/core \
  -Ibuild-openfhe-128-asan/src/pke \
  build-openfhe-128-asan/lib/libOPENFHEpke.so.1.5.1 \
  build-openfhe-128-asan/lib/libOPENFHEbinfhe.so.1.5.1 \
  build-openfhe-128-asan/lib/libOPENFHEcore.so.1.5.1 \
  -lpthread -ldl -lm \
  -Wl,-rpath,build-openfhe-128-asan/lib \
  -o openfhe_ckks_scalar_tiny_probe_asan

The same source was also compiled without -fsanitize=... against build-openfhe-128-nosan to confirm the EvalMult(-2^-103) wrong-result behavior without UBSan recovery.

Representative ordinary probe build:

clang++-14 -std=gnu++17 -fno-omit-frame-pointer -g -O0 \
  openfhe_ckks_scalar_tiny_probe.cpp \
  -Iopenfhe-development/src/pke/include \
  -Iopenfhe-development/src/core/include \
  -Iopenfhe-development/src/binfhe/include \
  -Iopenfhe-development/third-party/cereal/include \
  -Ibuild-openfhe-128-nosan/src/core \
  -Ibuild-openfhe-128-nosan/src/pke \
  build-openfhe-128-nosan/lib/libOPENFHEpke.so.1.5.1 \
  build-openfhe-128-nosan/lib/libOPENFHEbinfhe.so.1.5.1 \
  build-openfhe-128-nosan/lib/libOPENFHEcore.so.1.5.1 \
  -lpthread -ldl -lm \
  -Wl,-rpath,build-openfhe-128-nosan/lib \
  -o openfhe_ckks_scalar_tiny_probe_nosan

Actual behavior

On the UBSan/ASan build, running the neg_pow2_103 case:

ASAN_OPTIONS=detect_leaks=0 \
UBSAN_OPTIONS=print_stacktrace=1:halt_on_error=0 \
./openfhe_ckks_scalar_tiny_probe_asan neg_pow2_103

reports:

case=neg_pow2_103
operand=-9.8607613152626476e-32
runtime_plaintext_modulus_bits=90
pRemaining=-64
.../ckksrns-leveledshe.cpp:413:30: runtime error: shift exponent 64 is too large
for 64-bit type 'int64_t'
...
add_decoded0_real=1
sub_decoded0_real=1
mult_decoded0_real=-1.8189894035458565e-12

On the same UBSan/ASan build, running the neg_denorm_min case:

ASAN_OPTIONS=detect_leaks=0 \
UBSAN_OPTIONS=print_stacktrace=1:halt_on_error=0 \
./openfhe_ckks_scalar_tiny_probe_asan neg_denorm_min

reports:

case=neg_denorm_min
operand=-4.9406564584124654e-324
runtime_plaintext_modulus_bits=90
pRemaining=-1035
.../ckksrns-leveledshe.cpp:239:62: runtime error: shift exponent 1035 is too large
for 128-bit type 'uint128_t'
...
add_decoded0_real=0.99999999999999911
sub_decoded0_real=0.99999999999999911

The reproducer directly invokes the public EvalSub(ct, fabs(operand)) call as well. In the neg_denorm_min case, its decoded output matches the negative EvalAdd path; the sanitizer stack shown above is emitted by the earlier negative EvalAdd(...) dispatch into the same scheme EvalSub(...) helper.

On a separate ordinary Clang 14 build without sanitizers, the wrong-result behavior remains observable:

./openfhe_ckks_scalar_tiny_probe_nosan neg_pow2_103
./openfhe_ckks_scalar_tiny_probe_nosan neg_pow2_102

which reports:

case=neg_pow2_103
operand=-9.8607613152626476e-32
runtime_plaintext_modulus_bits=90
pRemaining=-64
mult_decoded0_real=-1.8189894035458565e-12

case=neg_pow2_102
operand=-1.9721522630525295e-31
runtime_plaintext_modulus_bits=90
pRemaining=-63
mult_decoded0_real=-8.0779356694631609e-28

So the same public scalar API family reaches two separate out-of-range negative-shift sites:

  • EvalMult(...): signed 64-bit right shift by 64
  • EvalAdd(...) / EvalSub(...): 128-bit right shift by 1035

and EvalMult(1.0, -2^-103) produces a decoded value around -1.8189894e-12, which is many orders of magnitude larger than the tiny input and is not a sensible underflow-to-zero result.

Expected behavior

Very small finite scalars should not trigger invalid shift counts inside public CKKS scalar APIs.

If a tiny scalar is below the representable range of the chosen internal scaling path, the implementation should either:

  • reject it explicitly; or
  • underflow it to zero deterministically.

It should not:

  • invoke UBSan via out-of-range shift counts; or
  • produce a much larger unrelated finite result in EvalMult(...).

Impact

This is a correctness bug in the 128-bit CKKS scalar-processing path, with confirmed undefined behavior.

The confirmed impact is:

  • UBSan-reported invalid right shifts for very small finite scalars; and
  • wrong decoded scalar-multiplication results for public EvalMult(...) on a separate ordinary Clang 14 build without sanitizers.

The currently confirmed scope is:

  • EvalMult(ciphertext, double): dynamically affected
  • negative EvalAdd(ciphertext, double) reaching EvalSub(...): dynamically affected
  • public EvalSub(ciphertext, double): directly invoked in the reproducer and source-confirmed to use the same affected helper path, but not separately isolated in the sanitizer output

From source inspection, the complex-scalar overloads appear to inherit the same helpers because they call GetElementForEvalAddOrSub(...) and GetElementForEvalMult(...) separately for the real and imaginary components. I have not dynamically exercised the complex-scalar overloads in this report.

Cause analysis

For scalar addition/subtraction in the 128-bit path, OpenFHE does:

int32_t n1       = 0;
int64_t scaled64 = std::llround(static_cast<double>(std::frexp(operand, &n1)) * powP);
int32_t pCurrent   = cryptoParams->GetPlaintextModulus() - precision;
int32_t pRemaining = pCurrent + n1;

if (pRemaining < 0) {
    scaledConstant = NativeInteger(((uint128_t)scaled64) >> (-pRemaining));
}

For scalar multiplication in the 128-bit path, it similarly does:

int64_t scaled64   = std::llround(static_cast<double>(std::frexp(operand, &n1)) * powP);
int32_t pCurrent   = cryptoParams->GetPlaintextModulus() - precision;
int32_t pRemaining = pCurrent + n1;

if (pRemaining < 0) {
    scaled128 = scaled64 >> (-pRemaining);
}

With scalingModSize = 90, the helper uses:

pCurrent = 90 - 52 = 38

So:

  • operand = -2^-103 gives pRemaining = -64
  • operand = -denorm_min gives pRemaining = -1035

Those values exceed the safe right-shift widths of the intermediate types used in the negative branch.

The control case -2^-102 gives pRemaining = -63, which stays within the 64-bit width and does not trigger shift-count UBSan. This matches the observed boundary at which the shift count first reaches the 64-bit width. It does not make the scaled64 >> 63 case fully portable, because right-shifting a negative signed integer by an in-range count remains implementation-defined.

For operand = -2^-103, the observed ordinary-build result is also consistent with this internal scaling path:

frexp mantissa = -0.5
scaled64       = -0.5 * 2^52 = -2^51
pRemaining     = -64

The decoded value -1.8189894035458565e-12 is exactly -2^-39, which is consistent with scaled64 failing to shrink before the later CKKS scaling by 2^90:

-2^51 / 2^90 = -2^-39 = -1.8189894035458565e-12

Likewise, the control case -2^-102 gives scaled64 = -2^51, pRemaining = -63, and the observed decoded result is consistent with an arithmetic right shift to -1 followed by division by 2^90:

-1 / 2^90 = -2^-90 = -8.0779356694631609e-28

Relevant source locations

Suggested direction

To address the confirmed negative-pRemaining cases, the helpers need explicit shift-count validation before performing the right shift.

At minimum:

  • if -pRemaining is greater than or equal to the bit width of the intermediate type, the code should avoid performing the shift; and
  • the implementation should define whether that case means:
    • deterministic underflow to zero, or
    • explicit rejection as unsupported.

For EvalMult(...), checking only the shift count is not enough. The current code also relies on right-shifting a negative signed int64_t when 0 <= -pRemaining < 64, and that behavior is implementation-defined.

So the multiplication helper should also:

  • separate the sign from the unsigned magnitude of scaled64;
  • apply an explicitly chosen magnitude-shift or underflow rule; and
  • restore the sign afterwards, instead of right-shifting a negative signed integer directly.

The same negative-pRemaining review should then be applied consistently across:

  • GetElementForEvalAddOrSub(...)
  • GetElementForEvalMult(...)
  • both real and complex scalar overload families that rely on those helpers

This report is limited to the negative-pRemaining branches. I have not analyzed the corresponding positive-pRemaining left-shift bounds here.

Question

For tiny finite scalars that fall below the representable range of the current 128-bit scalar-scaling path, would you prefer OpenFHE to reject them explicitly, or to treat them as deterministic underflow-to-zero cases before any out-of-range right shift occurs?

Reported by Jiang Chao, Beijing University of Posts and Telecommunications