Hi OpenFHE team,
I would like to report a possible correctness issue in the vector modular-exponentiation APIs and ask for confirmation of the intended contract.
Summary
`NativeVector::ModExp` and `NativeVector::ModExpEq` return a different result from both scalar `NativeInteger::ModExp` and an independent modular-exponentiation reference when the exponent is greater than or equal to the vector modulus.
In the affected implementations, the vector code reduces the exponent modulo the vector modulus before calling scalar modular exponentiation. For example, an exponent of `q + 1` becomes `1`.
Reducing an exponent modulo the modulus is not generally valid for modular exponentiation. In the reproducer below, the expected result is `4`, but both vector APIs return `2`.
During source inspection, I found the same kind of exponent reduction in the dynamic-bigint vector implementation and in the optional NTL vector implementation. The fixed-bigint vector implementation already passes the exponent through unchanged.
Environment
- OpenFHE source under test: `main` commit `ed361af22049007db2107e7c69bcff209e8c420d` (the build reports version `1.5.1`)
- OS/compiler: Linux x86_64, Clang 14
- Reproduced with `NATIVE_SIZE=64`; the corrected regression test also passes with `NATIVE_SIZE=128`
Minimal Reproduction
This program uses public core APIs only.
cpp
#include
#include
#include “math/hal/vector.h”
#include “math/hal/nativeintbackend.h”
using namespace lbcrypto;
static uint64_t ReferenceModExp(uint64_t base, uint64_t exponent,
uint64_t modulus) {
unsigned __int128 result = 1U % modulus;
unsigned __int128 factor = base % modulus;
while (exponent != 0) {
if ((exponent & 1U) != 0)
result = (result * factor) % modulus;
factor = (factor * factor) % modulus;
exponent >>= 1U;
}
return static_cast<uint64_t>(result);
}
int main() {
// q is below 2^60.
constexpr uint64_t q = 1152921504606584833ULL;
constexpr uint64_t base = 2;
constexpr uint64_t exponentValue = q + 1;
const NativeInteger modulus(q);
const NativeInteger exponent(exponentValue);
NativeVector values(1, modulus);
values[0] = NativeInteger(base);
const auto expected = ReferenceModExp(base, exponentValue, q);
const auto scalar = NativeInteger(base)
.ModExp(exponent, modulus)
.ConvertToInt<uint64_t>();
const auto vector = values.ModExp(exponent)[0].ConvertToInt<uint64_t>();
values.ModExpEq(exponent);
const auto inPlace = values[0].ConvertToInt<uint64_t>();
std::cout << “expected=” << expected
<< " scalar=" << scalar
<< " vector=" << vector
<< " in_place=" << inPlace << ‘\n’;
}
Output on the Affected Source Revision
expected=4 scalar=4 vector=2 in_place=2
The scalar API agrees with the independent reference; both vector variants disagree.
Expected Output
Both `NativeVector::ModExp` and `NativeVector::ModExpEq` should return `4` in this example. That is the result returned by scalar `NativeInteger::ModExp` and by the independent `unsigned __int128` reference implementation.
Actual Output
Before the correction, the non-mutating vector API returned `2` and the in-place API also left the vector element as `2`. The result is deterministic; this is not a sanitizer-only or memory-safety finding.
Diagnostic Results
| Check | Expected | Observation before the correction |
| Native `ModExp(q + 1)`, base `2` | `4` | `2` |
| Native `ModExpEq(q + 1)`, base `2` | `4` | `2` |
| Dynamic-bigint vector `ModExp(q + 1)`, bases `2` and `3` | `4` and `9` | `2` and `3` |
| Scalar `NativeInteger::ModExp` | `4` | `4` |
| Independent reference | `4` | `4` |
The NTL implementation was identified by source inspection: it passed `b % m_modulus` to scalar `ModExp`, which has the same exponent-reduction semantics. The corrected NTL regression test passes; I am separating that source observation from the pre-correction runtime observations above.
Root Cause Analysis
In the affected native vector implementation, `src/core/lib/math/hal/intnat/mubintvecnat.cpp` did the following in both `ModExp` and `ModExpEq`:
cpp：
auto bv{b};
if (bv.m_value >= mv.m_value)
bv.ModEq(mv);
Thus the reproducer’s exponent, `q + 1`, becomes `1`, and the vector code computes `2^1 mod q = 2` instead of `2^(q + 1) mod q = 4`.
I observed equivalent reductions in these implementations as well:
| Implementation | Previous exponent handling |
| `NativeVectorT` | `bv.ModEq(m_modulus)` when `b >= m_modulus` |
| dynamic `mubintvec` | `bLocal.ModEq(m_modulus)` when `b >= m_modulus` |
| NTL `myVecP` | passes `b % m_modulus` to scalar `ModExp` |
| fixed bigint vector | passes `b` unchanged |
Exact Source Locations
Since new users are limited to posting only two links, this section has been modified.
At source revision `ed361af22049007db2107e7c69bcff209e8c420d`, the relevant locations are:
| Implementation | Source location | Relevant behavior |
| Native vector | `src/core/lib/math/hal/intnat/mubintvecnat.cpp`, `ModExp` / `ModExpEq`, lines 359–378 | Copies `b` into `bv`, then calls `bv.ModEq(mv)` when `bv >= mv` |
| Dynamic-bigint vector | `src/core/lib/math/hal/bigintdyn/mubintvecdyn.cpp`, `ModExp` / `ModExpEq`, lines 419–439 | Copies `b` into `bLocal`, then calls `bLocal.ModEq(modulus)` when `bLocal >= modulus` |
| NTL vector | `src/core/lib/math/hal/bigintntl/mubintvecntl.cpp`, `ModExp` / `ModExpEq`, lines 515–530 | Passes `b % m_modulus` to scalar `ModExp` |
| Fixed-bigint vector | `src/core/lib/math/hal/bigintfxd/mubintvecfxd.cpp`, `ModExp` / `ModExpEq`, lines 447–459 | Passes the original `b` to scalar `ModExpEq` |
For a prime modulus and a nonzero base, any valid exponent-period reduction would relate to the group order (for example, `q - 1` in the simplest prime-modulus case), not to `q`. For composite moduli or non-unit bases, the conditions are more restrictive. Therefore, reducing a general public-API exponent modulo the vector modulus does not appear mathematically sound.
Existing API Documentation and Scalar Behavior
The public headers describe these methods as “Scalar modulus exponentiation operation” and do not document an `exponent < modulus` precondition:
This is also inconsistent with the scalar `NativeInteger::ModExp` API, which accepts the full exponent in the reproducer.
Why This Bug May Be Rarely Triggered
The incorrect branch is taken only when the exponent is at least the vector modulus. Typical uses may use small exponents, or may never call the vector modular-exponentiation API directly. This is an inference from the branch condition, rather than a claim about any particular FHE scheme workflow.
Suggested Fix
Remove the exponent-modulus reduction and pass the original exponent to scalar `ModExp` for every vector component:
| Implementation | Suggested change |
| `NativeVectorT` | Remove the `bv.ModEq(mv)` branch; retain the existing local copy of `b` |
| dynamic `mubintvec` | Remove the `bLocal.ModEq(modulus)` branch; retain the existing local copy of `b` |
| NTL `myVecP` | Pass `b` instead of `b % m_modulus` |
The local copies in the native and dynamic implementations should remain, because they preserve the existing behavior if a caller supplies an object that aliases a vector element to the in-place API.
Current Workarounds
1. Apply scalar `ModExp` separately to each element instead of using the vector API.
2. Restrict an exponent to be below the modulus only when the caller has independently established a mathematically valid exponent equivalence for its own modulus and base. In particular, reducing a general exponent as `exponent % modulus` is not a safe workaround.
3. Avoid using the vector `ModExp` / `ModExpEq` APIs for exponents at or above the vector modulus until the intended contract is clarified.
Impact
This is a deterministic silent-correctness issue in a public core arithmetic API. It is not specific to BFV, BGV, CKKS, or another individual FHE scheme; any OpenFHE code using the affected vector APIs can obtain a result that disagrees with the corresponding scalar API. No exception is raised to warn the caller.
Validation Results
I tested this correction with regression tests for the native, dynamic-bigint, and NTL vector implementations. The relevant validation was:
| Configuration / suite | Result |
| Targeted native, dynamic-bigint, and NTL regressions | pass |
| core tests, 64-bit native/default bigint backend | 158 passed |
| PKE tests, 64-bit native/default bigint backend | 1888 passed |
| BinFHE tests, 64-bit native/default bigint backend | 78 passed |
| core tests, `NATIVE_SIZE=128` | 160 passed |
| core tests, NTL backend | 151 passed |
The full suites above use the repository’s normal default test selection, which excludes tests explicitly marked `*_VERY_LONG`.
Full Diagnostic Code
The program in “Minimal Reproduction” is the complete standalone diagnostic for this report. It prints the independent reference result, the scalar result, the non-mutating vector result, and the in-place vector result in one run. It requires no cryptographic context, keys, or scheme-specific setup because the issue is in the public core vector-arithmetic API.
I would appreciate confirmation of whether vector ModExp / ModExpEqare intended to accept exponents greater than or equal to the vector modulus. If not, could you advise whether removing the exponent reduction across the native, dynamic-bigint, and NTL implementations is the intended direction, or point me to any existing discussion or issue?
Reported by Jiang Chao, Beijing University of Posts and Telecommunications