[Bug report] High CKKS precision can make `encodeScalingFactor()` abort or trigger undefined behavior during key generation

I would like to report a reproducible CKKS configuration bug in HElib's public context/key-generation path for high `precision(...)` settings.

On the checked-out HElib revision, a normal CKKS setup using:

```cpp
helib::ContextBuilder<helib::CKKS>().precision(54)
```

or larger can reach an unrepresentable scaling-factor computation in `EncryptedArrayCx::encodeScalingFactor()` during `SecKey::GenSecKey()`, causing an NTL abort at `54` and undefined behavior at `55` on the tested build.

## Summary

In the checked-out implementation, `SecKey::ImportSecKey()` computes the public encryption key's CKKS scaling factor with:

```cpp
pubEncrKey.ratFactor =
    pubEncrKey.noiseBound * getContext().getEA().getCx().encodeScalingFactor();
```

and `encodeScalingFactor()` defaults to:

```cpp
precision = (1L << alMod.getR());
...
long f = std::ceil(precision * roundErr);
return (1L << NTL::NextPowerOfTwo(f));
```

For high CKKS precision values, this can reach an unrepresentable scaling-factor computation before any explicit rejection of the context-derived default.

I reproduced the following behavior:

- `precision = 53`: key generation succeeds normally
- `precision = 54`: key generation aborts with `NextPowerOfTwo: overflow`
- `precision = 55`: UBSan reports an out-of-range conversion to `long` in `encodeScalingFactor()`
- in a separate UBSan recovery-mode run, `precision = 56` reports the same out-of-range conversion class with a larger operand

This occurs in a normal public setup path:

```text
ContextBuilder<CKKS> -> SecKey(context) -> GenSecKey()
```

without malformed serialized input or manual object corruption.

## Environment

- HElib checked-out revision: `3e337a66a91a92d49de6a9505340826b0eb71081`
- OS: Linux x86_64
- Compiler: `Clang 14.0.0`
- Sanitizers: AddressSanitizer and UndefinedBehaviorSanitizer
- Linked libraries: system `NTL` and `GMP`
- `NTL_SP_NBITS = 60`
- `NTL_SP_BOUND = 1152921504606846976`
- `sizeof(long) = 8`
- `LONG_MAX = 9223372036854775807`
- I confirmed the checked-out copies of `include/helib/EncryptedArray.h`, `include/helib/Context.h`, and `src/keys.cpp` were clean when running this reproducer.
- The auxiliary include directory `/tmp/helib-system-headers-v1` contains only `NTL/` and `gmp.h` headers used to prefer the system NTL 11 headers; it does not contain HElib headers.

Representative build command:

```bash
clang++-14 -std=c++17 -g -O1 -fno-omit-frame-pointer \
  -fsanitize=address,undefined \
  -I /tmp/helib-system-headers-v1 \
  -I HElib/dependencies/json \
  -I HElib/include \
  -I build-helib-sys-asan3/src \
  fuzz/helib_ckks_precision_keygen_probe.cpp \
  -L build-helib-sys-asan3/lib \
  -Wl,-rpath,/home/sht/agent-fuzzing/build-helib-sys-asan3/lib \
  build-helib-sys-asan3/lib/libhelib.a \
  -lntl -lgmp -lpthread -ldl -lm \
  -o fuzz/bin/helib_ckks_precision_keygen_probe
```

## Minimal reproduction

```cpp
#include <helib/helib.h>

#include <iostream>

int main(int argc, char** argv)
{
  const long precision = (argc >= 2) ? std::stol(argv[1]) : 55;

  std::cout << "precision=" << precision << std::endl;

  helib::Context context = helib::ContextBuilder<helib::CKKS>()
                               .m(16384)
                               .bits(300)
                               .precision(precision)
                               .c(2)
                               .build();

  std::cout << "about to generate secret key" << std::endl;
  helib::SecKey secret_key(context);
  secret_key.GenSecKey();
  std::cout << "keygen_ok" << std::endl;
  return 0;
}
```

Control case:

```bash
ASAN_OPTIONS=detect_leaks=0 UBSAN_OPTIONS=print_stacktrace=1 \
./fuzz/bin/helib_ckks_precision_keygen_probe 53
```

Output:

```text
precision=53
NTL_SP_NBITS=60
NTL_SP_BOUND=1152921504606846976
sizeof_long=8
LONG_MAX=9223372036854775807
about to generate secret key
keygen_ok
```

Failing boundary:

```bash
ASAN_OPTIONS=detect_leaks=0 UBSAN_OPTIONS=print_stacktrace=1 \
stdbuf -o0 -e0 ./fuzz/bin/helib_ckks_precision_keygen_probe 54
```

Output:

```text
precision=54
NTL_SP_NBITS=60
NTL_SP_BOUND=1152921504606846976
sizeof_long=8
LONG_MAX=9223372036854775807
about to generate secret key
NextPowerOfTwo: overflow
```

UBSan boundary:

```bash
ASAN_OPTIONS=detect_leaks=0 UBSAN_OPTIONS=print_stacktrace=1:halt_on_error=1 \
./fuzz/bin/helib_ckks_precision_keygen_probe 55
```

Output:

```text
precision=55
NTL_SP_NBITS=60
NTL_SP_BOUND=1152921504606846976
sizeof_long=8
LONG_MAX=9223372036854775807
about to generate secret key
/home/sht/agent-fuzzing/HElib/include/helib/EncryptedArray.h:1310:14: runtime error: 9.41356e+18 is outside the range of representable values of type 'long'
    #0  helib::EncryptedArrayDerived<helib::PA_cx>::encodeScalingFactor(...)
    #1  helib::SecKey::ImportSecKey(...)
    #2  helib::SecKey::GenSecKey(...)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sht/agent-fuzzing/HElib/include/helib/EncryptedArray.h:1310:14 in
```

In a separate UBSan recovery-mode run, `precision = 56` produced the same class of out-of-range conversion with a larger operand (`1.88271e+19`) and then continued to print `keygen_ok`. I do not rely on that continued execution to establish the bug.

## Actual behavior

High `precision(...)` values accepted by the CKKS `ContextBuilder` can make `encodeScalingFactor()` abort or trigger undefined behavior during `GenSecKey()`.

At `precision = 54`, the process aborts in `NTL::NextPowerOfTwo`.

At `precision = 55`, UBSan reports an out-of-range conversion to `long` in `encodeScalingFactor()`.

With UBSan recovery enabled, later execution can continue and print `keygen_ok`, but that post-UB continuation is not required to establish the bug.

## Expected behavior

If the current CKKS implementation does not support these high precision settings, the library should reject them explicitly before key generation reaches overflow or undefined behavior.

At minimum, a normal public `ContextBuilder<CKKS>` plus `GenSecKey()` setup should not evaluate overflowing arithmetic or narrowing conversions in its internal scaling-factor computation.

## Impact

This affects a normal public configuration path for CKKS.

An honest caller can select a high precision through the documented builder API and trigger either:

- an abort during key generation; or
- undefined behavior during key generation due to an out-of-range floating-to-integer conversion

I have not yet established a downstream wrong-result case from any key material produced after UBSan-recovery execution, but the key-generation path itself already reaches overflow and undefined behavior on a normal public configuration path.

## Cause analysis

The checked-out implementation of `encodeScalingFactor()` is:

```cpp
long encodeScalingFactor(long precision = -1, double roundErr = -1.0) const
{
  assertTrue<InvalidArgument>(precision < NTL_SP_BOUND,
                              "Precision exceeds max single precision bound");
  if (precision <= 0)
    precision = (1L << alMod.getR());
  if (roundErr < 0)
    roundErr = encodeRoundingError();

  long f = std::ceil(precision * roundErr);
  return (1L << NTL::NextPowerOfTwo(f));
}
```

Two different quantities are called "precision" here:

- the public `ContextBuilder<CKKS>::precision(r)` parameter is a bit precision
- `encodeScalingFactor()` then converts that bit precision into the integer quantity `2^r`

So when `SecKey::ImportSecKey()` uses the default `encodeScalingFactor()`, the context bit precision `r` is converted into:

```cpp
1L << alMod.getR()
```

where `alMod.getR()` is the CKKS bit precision configured by the public builder.

The existing `precision < NTL_SP_BOUND` check does not validate that context-derived default value: it runs while `precision` is still the `-1` sentinel, before `precision` is replaced with `1L << alMod.getR()`.

That validation-order gap is real, but it is not by itself a sufficient explanation for the observed `54/55` boundary on this build. In the tested NTL configuration above, both `2^54` and `2^55` are still below `NTL_SP_BOUND`.
The more direct failure condition is that the helper never validates the full representability of:

```cpp
precision * roundErr
```

or of the final rounded power-of-two scaling factor before performing the narrowing conversion to `long` or forming a final power-of-two scaling factor that is not representable as a positive `long`.

For the reproducer parameters above:

- `m = 16384`, so `phi(m) = 8192`
- the builder default is `scale_ = 10`
- `encodeRoundingError()` returns `noiseBoundForUniform(0.5, phim)`
- `noiseBoundForUniform()` computes `scale * sqrt(degBound / 3.0) * magBound`

So the default rounding-error bound here is:

```text
roundErr = 10 * sqrt(8192 / 3) * 0.5
         ≈ 261.2789059
```

That makes the key boundaries:

```text
r = 53:  ceil(2^r * roundErr) ≈ 2.3534e18
         Next power of two is 2^62, which still fits in signed long

r = 54:  ceil(2^r * roundErr) ≈ 4.7068e18
         This still fits in signed long, but its next power of two is 2^63.
         Therefore `NTL::NextPowerOfTwo(f)` would need exponent 63. In the
         tested build, NTL terminates with `NextPowerOfTwo: overflow`.
         Thus, although `f` itself still fits in `long`, the mathematically
         required scaling factor no longer does.

r = 55:  ceil(2^r * roundErr) ≈ 9.4136e18
         This already exceeds LONG_MAX, so the conversion performed by
         `long f = std::ceil(...)` is out of range
```

The `55` UBSan output above directly matches that last threshold. In the separate tested `r = 56` recovery-mode run, the same intermediate is larger still.

So there are two distinct failure modes:

- at `r = 54`, `f` is representable but its next power of two is `2^63`
- at the tested `r = 55`, and likewise in the tested `r = 56` recovery-mode run, the intermediate assigned to `long f` is already out of range

This is why the reproducer sees `NextPowerOfTwo: overflow` at `54`, but an out-of-range floating-to-`long` conversion at `55`.

The source itself already carries:

```cpp
// VJS-FIXME: the computation of f and/or return value could overflow
```

which matches the behavior above.

## Relevant source locations

- `include/helib/Context.h`
  - `Context::getR()` / `Context::getPrecision()`: lines 299-321
  - `Context::noiseBoundForUniform(...)`: lines 475-486
  - `ContextBuilder` default `scale_ = 10`: line 1081
  - `ContextBuilder<SCHEME>::precision(long)`: lines 1143-1146
  - `ContextBuilder<SCHEME>::scale(double)`: lines 1154-1157
  - GitHub blob:
    <https://github.com/homenc/HElib/blob/3e337a66a91a92d49de6a9505340826b0eb71081/include/helib/Context.h#L299-L321>
  - GitHub blob:
    <https://github.com/homenc/HElib/blob/3e337a66a91a92d49de6a9505340826b0eb71081/include/helib/Context.h#L475-L486>
  - GitHub blob:
    <https://github.com/homenc/HElib/blob/3e337a66a91a92d49de6a9505340826b0eb71081/include/helib/Context.h#L1081-L1081>
  - GitHub blob:
    <https://github.com/homenc/HElib/blob/3e337a66a91a92d49de6a9505340826b0eb71081/include/helib/Context.h#L1143-L1146>
  - GitHub blob:
    <https://github.com/homenc/HElib/blob/3e337a66a91a92d49de6a9505340826b0eb71081/include/helib/Context.h#L1154-L1157>

- `include/helib/EncryptedArray.h`
  - `encodeRoundingError(...)`: lines 1287-1296
  - `encodeScalingFactor(...)`: lines 1299-1312
  - GitHub blob:
    <https://github.com/homenc/HElib/blob/3e337a66a91a92d49de6a9505340826b0eb71081/include/helib/EncryptedArray.h#L1287-L1296>
  - GitHub blob:
    <https://github.com/homenc/HElib/blob/3e337a66a91a92d49de6a9505340826b0eb71081/include/helib/EncryptedArray.h#L1299-L1312>

- `src/keys.cpp`
  - `SecKey::ImportSecKey(...)`: lines 1099-1118
  - CKKS `ratFactor` assignment using `encodeScalingFactor()`: lines 1114-1117
  - `SecKey::GenSecKey(...)`: lines 1139-1155
  - GitHub blob:
    <https://github.com/homenc/HElib/blob/3e337a66a91a92d49de6a9505340826b0eb71081/src/keys.cpp#L1099-L1118>
  - GitHub blob:
    <https://github.com/homenc/HElib/blob/3e337a66a91a92d49de6a9505340826b0eb71081/src/keys.cpp#L1139-L1155>

## Suggested direction

`encodeScalingFactor()` should resolve its context-derived default and then validate the complete scaling-factor computation before performing any potentially overflowing shift or floating-to-integer conversion.

In practice this likely means:

- primarily hardening `encodeScalingFactor()` itself so that, after resolving the context-derived default, it validates both the `precision * roundErr` intermediate and the final rounded power-of-two scaling factor for representability by the helper's return type; and/or
- validating the builder-level CKKS precision range before `GenSecKey()` reaches `encodeScalingFactor()`

Reported by Jiang Chao, Beijing University of Posts and Telecommunications

	long getR() const { return alMod.getR(); }

	/**
	* @brief Getter method for the default `p^r` value of the created `context`.
	* @return The raised plaintext modulus `p^r`.
	* @note This value is not invariant: it is possible to work "view" objects
	* that use different `PAlgebra` objects.
	**/
	long getPPowR() const { return alMod.getPPowR(); }

	// synonymn for getR().
	// this is used in various corner cases in CKKS where
	// we really need some default precisiion parameter.
	// It is also possible to define this differently
	// in the future.
	/**
	* @brief Getter method for the `precision` value of the created
	* `CKKS` `context`.
	* @return The bit `precision` value.
	* @note This value is not invariant: it is possible to work "view" objects
	* that use different `PAlgebra` objects.
	**/
	long getPrecision() const { return alMod.getR(); }

	double noiseBoundForUniform(double magBound, long degBound) const
	{
	return scale * std::sqrt(double(degBound) / 3.0) * magBound;
	}

	/**
	*
	**/
	NTL::xdouble noiseBoundForUniform(NTL::xdouble magBound, long degBound) const
	{
	return scale * std::sqrt(double(degBound) / 3.0) * magBound;
	}

	double encodeRoundingError() const
	{
	const Context& context = getContext();
	long phim = context.getPhiM();

	// VJS-NOTE: I changed m to phi(m).
	// VJS-FIXME: for the power of two case, noiseBoundForUniform
	// is a bit too pessimistic, as this is the circularly symmetric
	// case.
	return context.noiseBoundForUniform(0.5, phim);

	long SecKey::ImportSecKey(const DoubleCRT& sKey,
	double bound,
	long ptxtSpace,
	long maxDegKswitch)
	{
	if (sKeys.empty()) { // 1st secret-key, generate corresponding public key
	if (ptxtSpace < 2)
	ptxtSpace = isCKKS() ? 1 : context.getAlMod().getPPowR();
	// default plaintext space is p^r for BGV, 1 for CKKS

	// allocate space, the parts are DoubleCRTs with all the ctxtPrimes
	pubEncrKey.parts.assign(2, CtxtPart(context, context.getCtxtPrimes()));
	// Choose a new RLWE instance
	pubEncrKey.noiseBound =
	RLWE(pubEncrKey.parts[0], pubEncrKey.parts[1], sKey, ptxtSpace);
	if (isCKKS()) {
	pubEncrKey.ptxtMag = 0.0;
	pubEncrKey.ratFactor = pubEncrKey.noiseBound *
	getContext().getEA().getCx().encodeScalingFactor();
	}

	long SecKey::GenSecKey(long ptxtSpace, long maxDegKswitch)
	{
	long hwt = context.getHwt();

	DoubleCRT newSk(context,
	context.getCtxtPrimes() \| context.getSpecialPrimes());

	if (hwt > 0) {
	// sample a Hamming-weight-hwt polynomial
	double bound = newSk.sampleHWtBounded(hwt);
	return ImportSecKey(newSk, bound, ptxtSpace, maxDegKswitch);
	} else {
	// sample a 0/+-1 polynomial
	double bound = newSk.sampleSmallBounded();
	return ImportSecKey(newSk, bound, ptxtSpace, maxDegKswitch);
	}
	}

Navigation Menu

Uh oh!

[Bug report] High CKKS precision can make `encodeScalingFactor()` abort or trigger undefined behavior during key generation #531

Summary

Environment

Minimal reproduction

Actual behavior

Expected behavior

Impact

Cause analysis

Relevant source locations

Suggested direction

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	ContextBuilder& precision(long precision)
	{
	r_ = precision;
	return *this;

	ContextBuilder& scale(double scale)
	{
	scale_ = scale;
	return *this;

	long encodeScalingFactor(long precision = -1, double roundErr = -1.0) const
	{
	assertTrue<InvalidArgument>(precision < NTL_SP_BOUND,
	"Precision exceeds max single precision bound");
	if (precision <= 0)
	precision = (1L << alMod.getR());
	if (roundErr < 0)
	roundErr = encodeRoundingError();

	// VJS-FIXME: the computation of f and/or return value could overflow

	long f = std::ceil(precision * roundErr);
	// We round the factor up to the next power of two
	return (1L << NTL::NextPowerOfTwo(f));

Uh oh!

[Bug report] High CKKS precision can make encodeScalingFactor() abort or trigger undefined behavior during key generation #531

Description

Summary

Environment

Minimal reproduction

Actual behavior

Expected behavior

Impact

Cause analysis

Relevant source locations

Suggested direction

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

[Bug report] High CKKS precision can make `encodeScalingFactor()` abort or trigger undefined behavior during key generation #531