[Bug report] BFV/BGV `EvalAtIndexKeyGen(INT_MIN)` can hang in automorphism-index computation

Library Questions
1

Hi OpenFHE team,

I would like to report a reproducible public-API availability bug in the BFV/BGV EvalAtIndex key-generation path.

Summary

For BFV and BGV, the public APIs:

  • CryptoContextImpl::EvalAtIndexKeyGen(...)
  • the lower LeveledSHEBase<Element>::EvalAtIndexKeyGen(...) path

can hang when the caller supplies INT_MIN in the index list.

On my instrumented build, the following BFV and BGV calls both failed to return within 6 seconds:

cc->EvalAtIndexKeyGen(sk, {std::numeric_limits<int32_t>::min()});

The same CKKS public call returned normally on this particular build. CKKS dispatches to a different helper:

  • BFV/BGV: FindAutomorphismIndex2n(...)
  • CKKS: FindAutomorphismIndex2nComplex(...)

Direct helper-level probing also reproduced the same issue in FindAutomorphismIndex2n(...) itself for both:

  • signed INT_MIN
  • static_cast<uint32_t>(INT_MIN) passed through the BFV/BGV-style unsigned interface

However, the CKKS helper also applies std::abs(...) to a reconstructed signed index, so that one observed normal return should not be interpreted as proof that the CKKS path is free of the same edge case. The public practical hang dynamically reproduced in these tests is limited to BFV and BGV.

So this is not limited to a synthetic helper-only call: on the tested platform it is reachable through public BFV/BGV EvalAtIndexKeyGen(...).

Environment

  • Release baseline: OpenFHE v1.5.1
  • Official v1.5.1 release commit: 1306d14f8c26bb6150d3e6ad54f28dfe1007689e
  • Tested revision and source-link revision: ed361af22049007db2107e7c69bcff209e8c420d
  • The tested revision is the immediate child of the v1.5.1 release commit and changes only README.md; the relevant source files for this report are unchanged.
  • OS: Linux x86_64
  • Compiler: Clang 14.0.0
  • Sanitizers: AddressSanitizer, UndefinedBehaviorSanitizer

Representative OpenFHE build:

cmake -S openfhe-development -B build-openfhe-asan \
  -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 -O1' \
  -DCMAKE_C_FLAGS='-fsanitize=address,undefined -fno-omit-frame-pointer -g -O1'
cmake --build build-openfhe-asan -j

Minimal reproduction

The reproducer below exercises the public EvalAtIndexKeyGen(...) entry point in three schemes.

#include <cstdint>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

#include "openfhe.h"

using namespace lbcrypto;

namespace {

template <class ContextBuilder>
int Run(ContextBuilder&& buildContext, const char* schemeName) {
    std::cout << std::unitbuf;
    std::cout << "scheme=" << schemeName << '\n';
    std::cout << "building context\n";

    CryptoContext<DCRTPoly> cc = buildContext();
    std::cout << "enabling features\n";
    cc->Enable(PKE);
    cc->Enable(KEYSWITCH);
    cc->Enable(LEVELEDSHE);
    std::cout << "running keygen\n";

    auto kp = cc->KeyGen();
    std::cout << "keygen done\n";

    std::vector<int32_t> indices{std::numeric_limits<int32_t>::min()};
    std::cout << "about to call EvalAtIndexKeyGen with index=" << indices[0] << '\n';
    cc->EvalAtIndexKeyGen(kp.secretKey, indices);
    std::cout << "returned normally\n";
    return 0;
}

CryptoContext<DCRTPoly> MakeCKKS() {
    CCParams<CryptoContextCKKSRNS> parameters;
    parameters.SetSecretKeyDist(UNIFORM_TERNARY);
    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetRingDim(1 << 8);
    parameters.SetBatchSize(8);
    parameters.SetScalingTechnique(FLEXIBLEAUTO);
    parameters.SetFirstModSize(60);
    parameters.SetScalingModSize(50);
    parameters.SetMultiplicativeDepth(1);
    return GenCryptoContext(parameters);
}

CryptoContext<DCRTPoly> MakeBFV() {
    CCParams<CryptoContextBFVRNS> parameters;
    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetRingDim(1 << 8);
    parameters.SetPlaintextModulus(65537);
    parameters.SetMultiplicativeDepth(1);
    parameters.SetBatchSize(8);
    return GenCryptoContext(parameters);
}

CryptoContext<DCRTPoly> MakeBGV() {
    CCParams<CryptoContextBGVRNS> parameters;
    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetRingDim(1 << 8);
    parameters.SetPlaintextModulus(65537);
    parameters.SetMultiplicativeDepth(1);
    parameters.SetBatchSize(8);
    return GenCryptoContext(parameters);
}

}  // namespace

int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cerr << "usage: <ckks|bfv|bgv>\n";
        return 1;
    }

    std::string mode = argv[1];
    if (mode == "ckks") {
        return Run(MakeCKKS, "ckks");
    }
    if (mode == "bfv") {
        return Run(MakeBFV, "bfv");
    }
    if (mode == "bgv") {
        return Run(MakeBGV, "bgv");
    }

    std::cerr << "unknown mode: " << mode << '\n';
    return 1;
}

Representative probe build:

clang++-14 -std=gnu++17 -fno-omit-frame-pointer -g -O1 \
  -fsanitize=address,undefined \
  openfhe_evalatindex_intmin_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-asan/src/core \
  -Ibuild-openfhe-asan/src/pke \
  build-openfhe-asan/lib/libOPENFHEpke_static.a \
  build-openfhe-asan/lib/libOPENFHEbinfhe_static.a \
  build-openfhe-asan/lib/libOPENFHEcore_static.a \
  -lpthread -ldl -lm \
  -o openfhe_evalatindex_intmin_probe

Actual behavior

With:

timeout 6s ./openfhe_evalatindex_intmin_probe ckks
timeout 6s ./openfhe_evalatindex_intmin_probe bfv
timeout 6s ./openfhe_evalatindex_intmin_probe bgv

I observed:

scheme=ckks
building context
enabling features
running keygen
keygen done
about to call EvalAtIndexKeyGen with index=-2147483648
returned normally

scheme=bfv
building context
enabling features
running keygen
keygen done
about to call EvalAtIndexKeyGen with index=-2147483648

and then timeout terminated the BFV process after 6 seconds.

scheme=bgv
building context
enabling features
running keygen
keygen done
about to call EvalAtIndexKeyGen with index=-2147483648

and then timeout terminated the BGV process after 6 seconds.

I also probed the helper directly:

step=-2147483648
m=4096
about to call FindAutomorphismIndex2n

and:

step=-2147483648
m=4096
step_u32=2147483648
about to call FindAutomorphismIndex2n with uint32_t-cast step

Both direct FindAutomorphismIndex2n(...) calls also failed to return within 5 seconds.

By contrast, the CKKS-specific direct helper:

step=-2147483648
m=4096
about to call FindAutomorphismIndex2nComplex
idx2nComplex=1

returned immediately on the same build.

Expected behavior

Supplying INT_MIN should not cause work proportional to an unnormalized 32-bit index magnitude in a public API.

For BFV/BGV, the EvalAtIndexKeyGen(...) path should either:

  • reject INT_MIN explicitly if that value is outside the supported rotation-index contract; or
  • normalize the user-supplied index into the supported automorphism range before iterating.

In either case, it should fail deterministically or normalize deterministically rather than hanging in automorphism-index computation.

Impact

This is primarily an API robustness and availability issue, not a typical confidentiality issue in the honest-but-curious outsourced-computation model. The trigger occurs during evaluation-key generation, which normally runs on the secret-key holder’s side, so a ciphertext-only evaluator would not ordinarily be able to invoke it directly.

The confirmed impact on the tested build is a multi-billion-iteration computation and practical hang when the caller provides INT_MIN in the rotation-index list.

The currently confirmed dynamic scope is:

  • BFV: affected
  • BGV: affected
  • CKKS: returned normally in the tested public call; no CKKS hang was dynamically reproduced

It can become an externally triggerable algorithmic-complexity denial of service if a protocol, RPC, configuration layer, or task-description interface allows another party to influence the rotation-index list and an otherwise honest key-management component forwards those values without validation. Whether INT_MIN is protocol-compliant or malformed depends on the declared rotation-index input contract.

The demonstrated issue is a scheme-specific practical hang / extreme CPU consumption in public BFV/BGV key generation.

Cause analysis

LeveledSHEBase<Element>::EvalAtIndexKeyGen(...) accepts:

const std::vector<int32_t>& indexList

and forwards each value into a virtual helper:

autoIndices[i] = FindAutomorphismIndex(indexList[i], M);

For BFV/BGV, the scheme overrides are:

uint32_t LeveledSHEBFVRNS::FindAutomorphismIndex(uint32_t index, uint32_t m) const {
    return FindAutomorphismIndex2n(index, m);
}

and:

uint32_t LeveledSHEBGVRNS::FindAutomorphismIndex(uint32_t index, uint32_t m) const {
    return FindAutomorphismIndex2n(index, m);
}

So the signed int32_t user input first crosses a uint32_t interface boundary and is then forwarded into:

uint32_t FindAutomorphismIndex2n(int32_t i, uint32_t m)

Inside that helper, the iteration bound is derived from:

uint32_t i_unsigned = (uint32_t)std::abs(i);

and then consumed in loops such as:

for (size_t j = 1; j < i_unsigned; j++) {
    g = (g * g0) % m;
}

On the tested C++17 platform, the full conversion chain is:

  1. the public int32_t value INT_MIN is converted to uint32_t, yielding 2147483648 modulo 2^32;
  2. the BFV/BGV override passes that value to an int32_t helper parameter, which is an implementation-defined unsigned-to-signed conversion because 2147483648 is not representable as int32_t;
  3. on the tested platform it becomes INT_MIN again;
  4. std::abs(INT_MIN) then has undefined behavior because the positive magnitude is not representable in int32_t.

On the tested platform, the resulting path behaved as if the magnitude were 2147483648, which drives the helper into a multi-billion-iteration loop.

That matches the direct helper probes:

  • signed INT_MIN hangs
  • BFV/BGV-style uint32_t cast of INT_MIN also hangs
  • CKKS uses a different helper and returned normally in this test, although that helper contains a similar std::abs(INT_MIN) construct

Relevant source locations

Suggested direction

The problematic part is the magnitude/normalization step before iterating.

At minimum, the public or scheme-level boundary should prevent INT_MIN from reaching either automorphism helper in a form that is passed to std::abs(int32_t).
A more robust fix would normalize the user-supplied index in a wider signed type before any magnitude conversion or loop bound is derived. For example:

  • reduce the signed index modulo the relevant automorphism period in int64_t; and
  • only then convert to a bounded unsigned loop count.

It would also help to keep the rotation index signed across the virtual interface, rather than converting it to uint32_t in the scheme override and then converting it back to int32_t inside the helper call.

That would avoid:

  • undefined or implementation-defined behavior around INT_MIN;
  • very large accidental loop bounds; and
  • helper-specific discrepancies for the same extreme input.

Question

Is INT_MIN intended to be rejected at the public EvalAtIndexKeyGen(...) boundary for BFV/BGV, or would you prefer to normalize it into the valid automorphism range before computing the BFV/BGV rotation key indices?

Reported by Jiang Chao, Beijing University of Posts and Telecommunications