Hi OpenFHE team,
I would like to ask whether the following SignedDigitDecompose behavior is intentional and report an UndefinedBehaviorSanitizer (UBSan) finding from a normal BinFHE gate evaluation.
Summary
In OpenFHE v1.5.1, RingGSWAccumulator::SignedDigitDecompose performs left shifts on NativeInteger::SignedNativeInt values:
auto r0 = (d0 << gBitsMaxBits) >> gBitsMaxBits;
For the public TOY / LMKCDEY BinFHE parameter set, UBSan reliably reports both negative signed left shifts and left shifts whose result is not representable by the signed type. The operation is reached by a normal, well-formed EvalBinGate call; it does not require a malformed ciphertext or invalid API use.
The undefined behavior is deterministic and is reached through a normal public BinFHE EvalBinGate call in the RingGSW accumulator path. Because this code executes during bootstrapped gate evaluation, its behavior cannot be relied upon across supported compiler
configurations and target platforms.
I therefore believe this warrants a correctness/portability fix.
Environment
- OpenFHE version: 1.5.1
- Component: BinFHE,
TOYparameter set,LMKCDEYbootstrapping method - OS: Linux x86_64
- Compiler: Clang 14
- Instrumentation: AddressSanitizer and UndefinedBehaviorSanitizer
Minimal Reproduction
This program uses only public OpenFHE BinFHE APIs. I compiled it against an instrumented OpenFHE v1.5.1 build and ran it with:
ASAN_OPTIONS=detect_leaks=0 UBSAN_OPTIONS=print_stacktrace=1 ./repro
#include <iostream>
#include "binfhecontext.h"
int main() {
lbcrypto::BinFHEContext context;
context.GenerateBinFHEContext(lbcrypto::TOY, lbcrypto::LMKCDEY);
const auto secret = context.KeyGen();
context.BTKeyGen(secret);
const auto zero = context.Encrypt(secret, 0);
const auto one = context.Encrypt(secret, 1);
const auto result = context.EvalBinGate(lbcrypto::NAND, zero, one);
lbcrypto::LWEPlaintext decrypted = 0;
context.Decrypt(secret, result, &decrypted);
std::cout << "NAND(0, 1)=" << decrypted << '\n';
return decrypted == 1 ? 0 : 1;
}
The code block above is the complete standalone reproducer used for this run.
Actual Result
The program exits successfully and decrypts the gate result correctly:
NAND(0, 1)=1
UBSan nevertheless reports, among others:
src/binfhe/lib/rgsw-acc.cpp:75:21: runtime error:
left shift of negative value -16776961
src/binfhe/lib/rgsw-acc.cpp:85:22: runtime error:
left shift of negative value -32768
src/binfhe/lib/rgsw-acc.cpp:109:21: runtime error:
left shift of 3578473 by 55 places cannot be represented in type
'NativeInteger::SignedNativeInt' (aka 'long')
src/binfhe/lib/rgsw-acc.cpp:113:22: runtime error:
left shift of 6989 by 55 places cannot be represented in type
'NativeInteger::SignedNativeInt' (aka 'long')
The same run also reaches the corresponding expressions at lines 72 and 79.
Root Cause Analysis
In src/binfhe/lib/rgsw-acc.cpp, both overloads of RingGSWAccumulator::SignedDigitDecompose store the working values in NativeInteger::SignedNativeInt:
auto d0{static_cast<NativeInteger::SignedNativeInt>(
t0 < QHalf ? t0 : t0 - Q_int)};
They then use a signed left-shift/right-shift sequence to recover a signed gadget digit. At v1.5.1, the relevant expressions are at lines 72, 75, 79, 85, 109, and 113:
auto r0{(d0 << gBitsMaxBits) >> gBitsMaxBits};
With this parameter set, gBitsMaxBits is 55. In C++, left shifting a negative signed value is undefined, and left shifting a non-negative signed value to a result that is not representable in the signed type is also undefined. These are the two UBSan conditions shown above.
My reading is that the code is using the common two’s-complement idiom for sign extension / signed-digit extraction. That can appear to work on the current platform, but it does not provide defined C++ semantics for the intermediate signed left shift.
Expected Result
The normal BinFHE operation should not execute undefined signed shifts under UBSan. Ideally, the signed-digit extraction should be expressed using defined operations for every supported compiler and target.
Suggested Direction
A possible direction is to perform the bit manipulation in an unsigned representation and explicitly reconstruct the signed digit using its sign bit and range, rather than relying on signed two’s-complement shifts. Any such formulation should preserve the intended gadget-digit decomposition semantics and performance characteristics. Guidance on the intended semantics and on an appropriate defined unsigned/sign-extension formulation would be appreciated.
Scope / Impact
- The finding is deterministic in a standalone reproducer that uses only normal public BinFHE APIs; it is not dependent on malformed ciphertext input or invalid API use.
- The affected function is in the RingGSW accumulation path used by bootstrapped gate evaluation, so a normal gate operation reaches the undefined behavior.
- The C++ language provides no defined semantics for this computation. A successful result on the current compiler and platform therefore does not establish that the operation is correct across supported build configurations, optimization levels, or target platforms.
- The present finding is a deterministic correctness and portability defect that warrants remediation in this core evaluation path.
Reported by Jiang Chao, Beijing University of Posts and Telecommunications.