Incorrect result after EvalMultNoRelin followed by Relinearize

Library Questions
1

Hello,

I encountered an issue where using EvalMultNoRelin followed by Relinearize produces incorrect results in subsequent computations, such as EvalAdd or EvalRotate. This problem does not occur when EvalMult is used instead. This seems to indicate a bug in how the ciphertext behaves after delayed relinearization.

Code Example

Here’s the simple version of code examples (BFV, v1.2.4):

Working Case: Using EvalMultNoRelin + Relinearize

Just ending up with relinearization after EvalMultNoRelin does not produce incorrect result. (Same result with when EvalMult is used instead.)

int main(void) {
  CCParams<CryptoContextBFVRNS> parameters;
  parameters.SetRingDim(32768);
  size_t plaintext_modulus = 65537;
  parameters.SetPlaintextModulus(plaintext_modulus);
  parameters.SetMultiplicativeDepth(5);
  CryptoContext<DCRTPoly> cc = GenCryptoContext(parameters);
  cc->Enable(PKE);
  cc->Enable(KEYSWITCH);
  cc->Enable(LEVELEDSHE);
  KeyPair<DCRTPoly> keyPair;
  keyPair = cc->KeyGen();
  cc->EvalMultKeyGen(keyPair.secretKey);
  size_t slots(cc->GetRingDimension());
  vector<int64_t> tmp_vec_(slots);
  Plaintext tmp;
  int rots_num = 20;
  vector<int> rots(rots_num + 1);
  for (int tmp_i = 2; tmp_i< rots_num+2; tmp_i += 2) {
     rots[tmp_i - 2] = tmp_i / 2;
     rots[tmp_i - 1] = -(tmp_i / 2);
  }
  rots[rots_num] = 0;
  cc->EvalRotateKeyGen(keyPair.secretKey, rots);
  Ciphertext<DCRTPoly> tmp_;

  Ciphertext<DCRTPoly> x, y;
  int yP;
  int yC;
  int c;
  vector<int64_t> tmp_vec_1 = { 1, 2, 3 };
  tmp = cc->MakePackedPlaintext(tmp_vec_1);
  x = cc->Encrypt(keyPair.publicKey, tmp);
  vector<int64_t> tmp_vec_2 = { 10, 10, 10 };
  tmp = cc->MakePackedPlaintext(tmp_vec_2);
  y = cc->Encrypt(keyPair.publicKey, tmp);
  x = cc->EvalMultNoRelin(x, y);
  cc->Relinearize(x);
  cc->ModReduceInPlace(x);

  // *** Place where additional operations comes in following cases *** //

  cc->Decrypt(keyPair.secretKey, x, &tmp);
  tmp->SetLength(5);
  tmp_vec_  = tmp->GetPackedValue();
  for (auto v : tmp_vec_) {
    cout << v << " ";
  }
  cout << endl;
  return 0;
}
  • Output (correct): 10 20 30 0 0

Failing Case: Subsequent operations like addition or rotation after EvalMultNoRelin + Relinearize

It seems that when additional operations which come after EvalMultNoRelin followed by Relinearize produce incorrect results. Here are example operations to be added at the above code before decryption.

  • Case 1: EvalAdd

    yP = 1;
fill(tmp_vec_.begin(), tmp_vec_.end(), yP);
tmp = cc->MakePackedPlaintext(tmp_vec_);
x = cc->EvalAdd(x, tmp);
    • Output (incorrect): 9 23310 12377 29529 -11219
    • Expected: 11 21 31 1 1

  • Case 2: EvalRotate

    c = 1;
x = cc->EvalRotate(x, c);
    • Outputs (incorrect): (Each execution yields a different value.)
      • 23585 -1249 23093 -12131 9268
      • 24908 3152 9860 -1723 -7809
      • 9060 7869 -25765 -15593 -30658
      • … and more
    • Expected: 20 30 0 0 0

Questions

Q1. Even after applying Relinearize and ModReduce, the result of subsequent operations like EvalAdd is incorrect. Since the ciphertext has already been relinearized and modulus-reduced, I would expect its size and scale to be normalized. Are there any known issues or subtle requirements regarding the state of a ciphertext after delayed relinearization?

Q2. EvalRotate produces different results when applied to the same ciphertext, suggesting non-determinism or possible corruption. Given that this occurs after relinearization, shouldn’t the ciphertext be stable for rotation? What could be the cause of this instability?

Q3. When replacing EvalMultNoRelin + Relinearize with a direct EvalMult, everything works fine. What is the internal difference that could cause such divergence in behavior between these two approaches?
__
Thank you for your attention!

2

Please either use cc->RelinearizeInPlace(x) or x = cc->Relinearize(x) instead of cc->Relinearize(x) and it will work. You weren’t actually applying the relinearization; decryption looks at the number of polynomials and knows to decrypt, however the rest of the homomorphic operations needed the relinearized ciphertext.

Another point to keep in mind when using EvalMultNoRelin is to specify parameters.SetMaxRelinSkDeg(*) and cc->EvalMultKeysGen(keyPair.secretKey), otherwise it will not work for more than a multiplication, since the default value of SetMaxRelinSkDeg is 2.

3

Thank you for pointing out my misuse! The code works correctly now.

However, I still have one open question:
Assuming the example code was incorrect because the ciphertext was not relinearized, I noticed that when using BGV instead of BFV, the library throws an exception with the message:
src/pke/lib/schemebase/base-leveledshe.cpp: l.426: EvalAutomorphism(): Ciphertext should be relinearized before.
It seems that the ciphertext size is being checked before performing the rotation by EvalAutomorphism.

I believe this is the appropriate behavior — returning an exception rather than producing incorrect results, as happens with BFV in the same scenario. So I would like to kindly suggest making a similar check in the BFV implementation, just as it’s done for BGV.

Thanks again, and I’d appreciate your opinion on this!