Summary
When using EvalMultNoRelin in BFV to produce a 3-element ciphertext (vital for lazy relinearization related research), the resulting ciphertext’s DCRTPoly elements are in COEFFICIENT format. However, freshly encrypted ciphertexts have elements in EVALUATION (NTT) format. Calling EvalAdd on these two ciphertexts — or even performing direct element-wise operator+= — produces a mathematically meaningless result because polynomial addition across different domains (NTT vs coefficient) is undefined.
This affects any BFV/BGV workflow that defers relinearization and then adds the unrelinearized ciphertext to a fresh or independently computed ciphertext.
Environment
-
OpenFHE version: 1.2.3, also reproducible on 1.4.2 (stable) and 1.5.0 (dev)
-
Scheme: BFV (BFVrns)
-
OS: Windows (MINGW64), but the issue is platform-independent
Minimal Reproduction
#include "openfhe.h"
using namespace lbcrypto;
int main() {
CCParams<CryptoContextBFVRNS> params;
params.SetPlaintextModulus(65537);
params.SetMultiplicativeDepth(4);
auto cc = GenCryptoContext(params);
cc->Enable(PKE);
cc->Enable(LEVELEDSHE);
auto keys = cc->KeyGen();
cc->EvalMultKeyGen(keys.secretKey);
uint32_t N = cc->GetRingDimension();
auto ct_a = cc->Encrypt(keys.publicKey, cc->MakePackedPlaintext(std::vector<int64_t>(N, 100)));
auto ct_b = cc->Encrypt(keys.publicKey, cc->MakePackedPlaintext(std::vector<int64_t>(N, 200)));
auto ct_c = cc->Encrypt(keys.publicKey, cc->MakePackedPlaintext(std::vector<int64_t>(N, 333)));
// 3-poly ciphertext from multiplication without relinearization
auto ct_ab = cc->EvalMultNoRelin(ct_a, ct_b); // elements in COEFFICIENT format
// Diagnostic: check formats
std::cout << "ct_ab format: "
<< (ct_ab->GetElements()[0].GetFormat() == Format::EVALUATION ? "EVALUATION" : "COEFFICIENT")
<< std::endl; // prints COEFFICIENT
std::cout << "ct_c format: "
<< (ct_c->GetElements()[0].GetFormat() == Format::EVALUATION ? "EVALUATION" : "COEFFICIENT")
<< std::endl; // prints EVALUATION
// This EvalAdd mixes COEFFICIENT + EVALUATION domains → silent corruption
auto ct_sum = ct_ab->Clone();
auto& elems = ct_sum->GetElements();
const auto& cElems = ct_c->GetElements();
elems[0] += cElems[0]; // COEFFICIENT += EVALUATION → meaningless
elems[1] += cElems[1];
// Decrypt: expect 20333, get garbage
Plaintext result;
cc->Decrypt(keys.secretKey, ct_sum, &result);
std::cout << "Expected: 20333, Got: " << result->GetPackedValue()[0] << std::endl;
// Fix: align format before addition
auto ct_c_copy = ct_c->Clone();
auto& fixElems = ct_c_copy->GetElements();
for (auto& e : fixElems) {
e.SetFormat(ct_ab->GetElements()[0].GetFormat()); // EVALUATION → COEFFICIENT
}
auto ct_sum_fixed = ct_ab->Clone();
auto& fixedR = ct_sum_fixed->GetElements();
fixedR[0] += fixElems[0];
fixedR[1] += fixElems[1];
Plaintext result2;
cc->Decrypt(keys.secretKey, ct_sum_fixed, &result2);
std::cout << "After format fix: " << result2->GetPackedValue()[0] << std::endl; // prints 20333
return 0;
}
Expected output: 20333
Actual output: Garbage value (e.g., 1934, varies per run)
After manual format alignment: 20333 (correct)
Diagnostic Results
A comprehensive diagnostic test was conducted:
| Test | Operation | Result |
|---|---|---|
| 1 | Decrypt 3-poly ct_ab directly (baseline) |
PASS (20000) |
| 2 | ManualAdd (no format align) → Decrypt 3-poly | FAIL (1934) |
| 3 | ManualAdd (no format align) → Relin → Decrypt | FAIL (-13067) |
| 4 | ManualAdd WITH format align → Decrypt 3-poly | PASS (20333) |
| 5 | ManualAdd WITH format align → Relin → Decrypt | PASS (20333) |
| 6 | ctOne fix EvalMultNoRelin(ct_c, enc(1)) (control) |
PASS (20333) |
| 7 | Relin both sides first → EvalAdd 2+2 |
PASS (20333) |
Key finding from format inspection:
ct_ab[0] format: COEFFICIENT
ct_c[0] format: EVALUATION
ct_ab num primes: 4
ct_c num primes: 4
All CRT moduli match
The CRT moduli are identical, but the polynomial representation formats differ. This is the root cause. Tests 4-5 confirm that aligning the format before addition completely resolves the issue.
Root Cause Analysis
Exact location: base-leveledshe.cpp, lines 574–590
// line 574
void LeveledSHEBase<Element>::EvalAddCoreInPlace(Ciphertext<Element>& ciphertext1,
ConstCiphertext<Element>& ciphertext2) const {
VerifyNumOfTowers(ciphertext1, ciphertext2);
auto& cv1 = ciphertext1->GetElements();
auto& cv2 = ciphertext2->GetElements();
uint32_t c1Size = cv1.size();
uint32_t c2Size = cv2.size();
uint32_t cSmallSize = std::min(c1Size, c2Size);
cv1.reserve(c2Size);
uint32_t i = 0;
for (; i < cSmallSize; ++i)
cv1[i] += cv2[i]; // ← line 587: NO format check before +=
for (; i < c2Size; ++i)
cv1.emplace_back(cv2[i]);
}
Line 587 calls cv1[i] += cv2[i] without checking or unifying the Format of the two DCRTPoly operands. When cv1[i] is in COEFFICIENT format (from EvalMultNoRelin) and cv2[i] is in EVALUATION format (from fresh encryption), this produces a mathematically meaningless result.
The same bug exists in EvalSubCoreInPlace (lines 600–617)
Line 613: cv1[i] -= cv2[i] has the identical issue.
Notably, the plaintext version already handles this correctly
In the same file, EvalAddInPlace for plaintext addition (lines 90–95) does align the format:
// line 90
void LeveledSHEBase<Element>::EvalAddInPlace(Ciphertext<Element>& ciphertext, ConstPlaintext& plaintext) const {
auto& cv = ciphertext->GetElements();
auto pt = plaintext->GetElement<Element>();
pt.SetFormat(cv[0].GetFormat()); // ← line 93: FORMAT ALIGNMENT EXISTS HERE
cv[0] += pt;
}
The ciphertext-plaintext path calls SetFormat() to unify the representation. The ciphertext-ciphertext path (EvalAddCoreInPlace) does not. This inconsistency strongly suggests the omission was unintentional.
Why this bug is rarely triggered
In the standard workflow, EvalMult (not EvalMultNoRelin) automatically calls Relinearize, which involves key-switching operations that convert elements back to EVALUATION format. Users almost never encounter mixed-format ciphertexts unless they explicitly use EvalMultNoRelin for lazy relinearization — a legitimate and well-documented optimization strategy.
Suggested Fix
Add format unification in EvalAddCoreInPlace before element-wise addition, consistent with the existing plaintext version:
void LeveledSHEBase<Element>::EvalAddCoreInPlace(Ciphertext<Element>& ciphertext1,
ConstCiphertext<Element>& ciphertext2) const {
VerifyNumOfTowers(ciphertext1, ciphertext2);
auto& cv1 = ciphertext1->GetElements();
auto& cv2 = ciphertext2->GetElements();
// Unify format (consistent with plaintext EvalAddInPlace at line 93)
Format format = cv1[0].GetFormat();
uint32_t c1Size = cv1.size();
uint32_t c2Size = cv2.size();
uint32_t cSmallSize = std::min(c1Size, c2Size);
cv1.reserve(c2Size);
uint32_t i = 0;
for (; i < cSmallSize; ++i) {
auto tmp = cv2[i];
tmp.SetFormat(format);
cv1[i] += tmp;
}
for (; i < c2Size; ++i) {
cv1.emplace_back(cv2[i]);
cv1.back().SetFormat(format);
}
}
The same fix should be applied to EvalSubCoreInPlace (lines 600–617).
Alternatively, a lighter-weight fix would be to add a format check with a clear error message, alerting users to the mismatch rather than silently producing incorrect results.
Current Workarounds
-
Always relinearize before adding ciphertexts of different origins (defeats the purpose of lazy relinearization)
-
Multiply by
enc(1)before adding:EvalMultNoRelin(ct_fresh, ct_one)forces the fresh ciphertext through the multiplication pipeline, aligning its format (expensive: costs one full ciphertext multiplication) -
Manual format conversion before addition:
auto ct_c_copy = ct_c->Clone();
auto& elems = ct_c_copy->GetElements();
Format targetFormat = ct_ab->GetElements()[0].GetFormat();
for (auto& e : elems) {
e.SetFormat(targetFormat);
}
// Now element-wise addition is safe
Workaround 3 is the most efficient (cost: one NTT/INTT per element).
Impact
This bug affects any research or application that implements lazy (deferred) relinearization in BFV — a well-known optimization that reduces the number of expensive relinearization operations by deferring them until necessary. The bug makes it impossible to add an unrelinearized ciphertext to a fresh ciphertext through the standard API without a workaround.
Full Diagnostic Code
A self-contained diagnostic test file is attached below. It can be compiled against OpenFHE and run directly to reproduce all results described above.
diag_test.cpp (click to expand)
// ============================================================
// BFV Mixed-Source Ciphertext Addition Diagnostic Test
// ============================================================
#include "openfhe.h"
#include <iostream>
#include <iomanip>
using namespace lbcrypto;
using namespace std;
using CT = Ciphertext<DCRTPoly>;
void printCtInfo(const string& name, const CT& ct) {
cout << " " << name << ": polys=" << ct->GetElements().size()
<< " level=" << ct->GetLevel()
<< " noiseScaleDeg=" << ct->GetNoiseScaleDeg()
<< " towers=" << ct->GetElements()[0].GetNumOfElements()
<< " format=" << (ct->GetElements()[0].GetFormat() == Format::EVALUATION ? "EVAL" : "COEFF")
<< endl;
}
CT ManualAdd(const CT& ct_big, const CT& ct_small) {
auto result = ct_big->Clone();
auto& rElems = result->GetElements();
const auto& sElems = ct_small->GetElements();
for (size_t i = 0; i < sElems.size(); i++) {
rElems[i] += sElems[i];
}
return result;
}
CT ManualAddWithFormatAlign(const CT& ct_big, const CT& ct_small) {
auto result = ct_big->Clone();
auto& rElems = result->GetElements();
Format targetFormat = rElems[0].GetFormat();
auto ct_small_copy = ct_small->Clone();
auto& sElems = ct_small_copy->GetElements();
for (auto& e : sElems) {
e.SetFormat(targetFormat);
}
for (size_t i = 0; i < sElems.size(); i++) {
rElems[i] += sElems[i];
}
return result;
}
int main() {
cout << "============================================" << endl;
cout << " BFV Mixed-Source Addition Diagnostic Test" << endl;
cout << "============================================" << endl;
CCParams<CryptoContextBFVRNS> params;
params.SetPlaintextModulus(65537);
params.SetMultiplicativeDepth(4);
CryptoContext<DCRTPoly> cc = GenCryptoContext(params);
cc->Enable(PKE);
cc->Enable(LEVELEDSHE);
auto keys = cc->KeyGen();
cc->EvalMultKeyGen(keys.secretKey);
uint32_t N = cc->GetRingDimension();
cout << "Ring dimension: " << N << endl;
int64_t val_a = 100, val_b = 200, val_c = 333;
int64_t expected_ab = val_a \* val_b;
int64_t expected_sum = val_a \* val_b + val_c;
auto ct_a = cc->Encrypt(keys.publicKey, cc->MakePackedPlaintext(vector<int64_t>(N, val_a)));
auto ct_b = cc->Encrypt(keys.publicKey, cc->MakePackedPlaintext(vector<int64_t>(N, val_b)));
auto ct_c = cc->Encrypt(keys.publicKey, cc->MakePackedPlaintext(vector<int64_t>(N, val_c)));
auto ct_one = cc->Encrypt(keys.publicKey, cc->MakePackedPlaintext(vector<int64_t>(N, 1)));
auto ct_ab = cc->EvalMultNoRelin(ct_a, ct_b);
cout << "expected a\*b = " << expected_ab << ", expected a\*b+c = " << expected_sum << endl;
printCtInfo("ct_ab (noRelin)", ct_ab);
printCtInfo("ct_c (fresh)", ct_c);
cout << endl;
Plaintext ptResult;
int numTests = 0, numPass = 0;
auto check = [&](const string& name, int64_t expected) {
numTests++;
int64_t got = ptResult->GetPackedValue()[0];
bool pass = (got == expected);
if (pass) numPass++;
cout << " Slot[0] = " << got << (pass ? " PASS" : " FAIL")
<< " (expected " << expected << ")" << endl << endl;
};
// Test 1: Baseline
cout << "=== Test 1: Decrypt 3-poly ct_ab directly ===" << endl;
cc->Decrypt(keys.secretKey, ct_ab, &ptResult);
check("baseline", expected_ab);
// Test 2: ManualAdd without format alignment -> Decrypt 3-poly
cout << "=== Test 2: ManualAdd (NO format align) -> Decrypt 3-poly ===" << endl;
{ auto s = ManualAdd(ct_ab, ct_c);
cc->Decrypt(keys.secretKey, s, &ptResult);
check("ManualAdd raw", expected_sum); }
// Test 3: ManualAdd without format alignment -> Relin -> Decrypt
cout << "=== Test 3: ManualAdd (NO format align) -> Relin -> Decrypt ===" << endl;
{ auto s = ManualAdd(ct_ab, ct_c);
cc->Decrypt(keys.secretKey, cc->Relinearize(s), &ptResult);
check("ManualAdd+Relin", expected_sum); }
// Test 4: ManualAdd WITH format alignment -> Decrypt 3-poly
cout << "=== Test 4: ManualAdd (WITH format align) -> Decrypt 3-poly ===" << endl;
{ auto s = ManualAddWithFormatAlign(ct_ab, ct_c);
cc->Decrypt(keys.secretKey, s, &ptResult);
check("FormatAlign direct", expected_sum); }
// Test 5: ManualAdd WITH format alignment -> Relin -> Decrypt
cout << "=== Test 5: ManualAdd (WITH format align) -> Relin -> Decrypt ===" << endl;
{ auto s = ManualAddWithFormatAlign(ct_ab, ct_c);
cc->Decrypt(keys.secretKey, cc->Relinearize(s), &ptResult);
check("FormatAlign+Relin", expected_sum); }
// Test 6: ctOne fix (control)
cout << "=== Test 6: ctOne fix (control) ===" << endl;
{ auto cv = cc->EvalMultNoRelin(ct_c, ct_one);
auto s = cc->EvalAdd(ct_ab, cv);
cc->Decrypt(keys.secretKey, cc->Relinearize(s), &ptResult);
check("ctOne fix", expected_sum); }
// Test 7: Relin first, EvalAdd 2+2
cout << "=== Test 7: Relin first, EvalAdd 2+2 ===" << endl;
{ auto s = cc->EvalAdd(cc->Relinearize(ct_ab), ct_c);
cc->Decrypt(keys.secretKey, s, &ptResult);
check("Relin-first", expected_sum); }
// Format diagnostic
cout << "=== Format Diagnostic ===" << endl;
{ const auto& abE = ct_ab->GetElements();
const auto& cE = ct_c->GetElements();
cout << " ct_ab[0] format: " << (abE[0].GetFormat()==Format::EVALUATION?"EVALUATION":"COEFFICIENT") << endl;
cout << " ct_c[0] format: " << (cE[0].GetFormat()==Format::EVALUATION?"EVALUATION":"COEFFICIENT") << endl;
auto abP = abE[0].GetParams(); auto cP = cE[0].GetParams();
cout << " ct_ab primes: " << abP->GetParams().size()
<< ", ct_c primes: " << cP->GetParams().size() << endl;
bool same = true;
for (size_t i = 0; i < min(abP->GetParams().size(), cP->GetParams().size()); i++)
if (abP->GetParams()[i]->GetModulus() != cP->GetParams()[i]->GetModulus()) same = false;
cout << " CRT moduli: " << (same ? "ALL MATCH" : "MISMATCH") << endl; }
cout << "============================================" << endl;
cout << " SUMMARY: " << numPass << "/" << numTests << " passed" << endl;
cout << "============================================" << endl;
return 0;
}
I am happy to submit a PR for the fix if the team agrees on the approach. I see at least two possible directions:
-
(A) Add format unification in
EvalAddCoreInPlace/EvalSubCoreInPlace, consistent with the existing plaintext addition path at line 93. -
(B) Ensure that
EvalMultCore(and the BFV-specific multiplication paths) output ciphertexts in EVALUATION format, resolving the mismatch at the source.
I’d appreciate guidance on which approach is preferred.
Reported by Zhongqi Wang from University of Tsukuba