[Bug report] CKKS `COMPOSITESCALINGAUTO` can generate a first composite modulus over 5 bits below `firstModSize`

Bug Reports
1

Hi OpenFHE team,

I would like to report a CKKS parameter-generation correctness issue in the composite-scaling path.

Summary

At OpenFHE v1.5.1 commit 1306d14f8c26bb6150d3e6ad54f28dfe1007689e, a public GenCryptoContext(...) call with COMPOSITESCALINGAUTO can generate a first composite modulus whose product is much smaller than the configured firstModSize.

The reproducer uses ordinary public CKKS parameters:

multiplicativeDepth = 0
scalingTechnique    = COMPOSITESCALINGAUTO
scalingModSize      = 36
firstModSize        = 38
registerWordSize    = 20
securityLevel       = HEStd_NotSet
ringDim             = 8192
batchSize           = 8

GenCryptoContext(...) accepts this configuration and produces a composite degree of 2, but the first two towers have a combined size of only about 32.807 bits:

tower[0] modulus=114689 log2=16.807367501305226
tower[1] modulus=65537  log2=16.00002201361136
first_composite_log2_product=32.807389514916586

This is about 5.19 bits below the configured firstModSize=38.

The root cause appears to be inconsistent remaining-budget accounting inside CompositePrimeModuliGen(...). The regular-modulus loop subtracts the actual selected prime width, while the first-modulus loop subtracts the requested qBitSize. In the witness above, using actual-width accounting in the first-modulus loop changes the second first-modulus prime from 65537 to 1032193 and raises the first composite product to about 36.785 bits.

The confirmed issue is that an accepted CKKS composite-scaling context silently starts with less precision and noise headroom than the visible firstModSize budget suggests.

Environment

  • OpenFHE baseline revision: 1306d14f8c26bb6150d3e6ad54f28dfe1007689e
  • OpenFHE configuration used for validation: NATIVE_SIZE=64, MATHBACKEND=4, WITH_OPENMP=OFF
  • Generated config observed locally: NATIVEINT=64, HAVE_INT128=TRUE, WITH_BE4
  • OS: Linux x86_64

Minimal reproduction

The public-path reproducer uses:

CCParams<CryptoContextCKKSRNS> parameters;
parameters.SetMultiplicativeDepth(0);
parameters.SetScalingTechnique(COMPOSITESCALINGAUTO);
parameters.SetScalingModSize(36);
parameters.SetFirstModSize(38);
parameters.SetRegisterWordSize(20);
parameters.SetSecurityLevel(HEStd_NotSet);
parameters.SetRingDim(8192);
parameters.SetBatchSize(8);

auto cc = GenCryptoContext(parameters);

After context generation, the probe prints the generated tower moduli from cc->GetCryptoParameters()->GetElementParams()->GetParams() and computes the log2 product of the first compositeDegree towers.

I used HEStd_NotSet and a small ring dimension to keep the reproducer fast. The issue being exercised is deterministic public parameter generation, and the arithmetic mismatch does not depend on secret data.

Representative command from my local probe:

./openfhe_composite_context_case 36

Actual behavior

The public GenCryptoContext(...) case prints:

scalingModSize=36 ringDim=8192 cyclOrder=16384 compositeDegree=2 numTowers=2
tower[0] modulus=114689 log2=16.807367501305226
tower[1] modulus=65537 log2=16.00002201361136
first_composite_log2_product=32.807389514916586

The same output was observed with scalingModSize=37 in this reduced configuration.

Accounting witness

The following current-vs-fixed helper model mirrors the relevant prime-selection logic:

uint32_t remBits = firstModSize;
for (uint32_t d = 1; d <= compositeDegree; ++d) {
    uint32_t qBitSize = std::ceil(static_cast<double>(remBits) / (compositeDegree - d + 1));
    NativeInteger q = FirstPrime<NativeInteger>(qBitSize, cyclOrder);
    q = PreviousPrime<NativeInteger>(q, cyclOrder);
    while (bits_of(q) > registerWordSize ||
           bits_of(q) > qBitSize ||
           seen.count(static_cast<uint64_t>(q.ConvertToInt())) != 0) {
        q = PreviousPrime<NativeInteger>(q, cyclOrder);
    }

    // Current first-modulus loop:
    remBits -= qBitSize;

    // Actual-width accounting:
    // remBits -= bits_of(q);
}

For the same public context parameters, the model prints:

buggy_model: [q=19 bits=17 prime=114689] [q=19 bits=17 prime=65537] log2_product=32.807389514916586
fixed_accounting_model: [q=19 bits=17 prime=114689] [q=21 bits=20 prime=1032193] log2_product=36.784648822504735

This does not prove that a one-line change is the complete policy for every parameter set. It does show that the current requested-width subtraction materially changes prime selection and accounts for almost 4 bits of the observed first-modulus shortfall in this public-path witness.

Expected behavior

The first-modulus loop should account for the actual width of the selected prime, just like the earlier regular-modulus loop does.

If exact fulfillment of a requested firstModSize is impossible under the active prime-search constraints, GenCryptoContext(...) should either generate the closest valid composite modulus using consistent accounting, reject the parameter combination with a clear diagnostic, or document the attainable range. It should not silently drift several bits below the configured budget because one branch subtracts requested width while another branch subtracts selected width.

Root cause analysis

CompositePrimeModuliGen(...) already uses actual-width accounting in the regular modulus loop:

remBits -= std::ceil(std::log2(q.ConvertToDouble()));

but the first-modulus loop uses the requested width:

remBits -= qBitSize;

In the reproduced context, the first selected prime for the first composite modulus is requested with qBitSize=19 but has only 17 actual bits. The current loop subtracts 19, leaving the next selection at qBitSize=19. Actual-width accounting would leave a larger remaining budget and select the next first-modulus prime at qBitSize=21.

This helper is reached from public CKKS context generation for composite scaling.

Impact

The confirmed impact is a public CKKS context that appears valid but starts with a first composite modulus substantially below the configured firstModSize.

In the witnessed case, the caller requests firstModSize=38, but the generated first composite modulus is about 2^32.8. That reduces the initial precision and noise headroom by about 5.19 bits relative to the user-visible budget. The accounting mismatch itself changes the selected prime sequence and accounts for almost 4 bits of that gap in the reduced witness.

This can make composite-scaling CKKS contexts lose precision earlier than expected or provide less evaluation headroom than the parameter configuration suggests.

Source locations

Suggested direction

Update the first-modulus loop to subtract the actual selected prime width after the final candidate has been chosen.

The local accounting should mirror the earlier regular-modulus loop. If additional constraints make the requested firstModSize unattainable for some public parameter combinations, those combinations should be rejected or documented rather than silently producing a much smaller first composite modulus.

2

Thank you for reporting it. Added a new issue.