Incorrect result with rotation in BFV

Library Questions
1

Hi,

I encountered an issue where applying EvalRotate just once to a ciphertext produces an incorrect result with random values. No other operations are performed before or after the rotation, and I haven’t received any exception messages from the parameter validator, so it seems that the issue stems directly from the rotation itself.

Code Example

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

int main(void) {
  CCParams<CryptoContextBFVRNS> parameters;
  parameters.SetRingDim(16384);
  parameters.SetMultiplicativeDepth(0);
  parameters.SetPlaintextModulus(65537);
  parameters.SetScalingModSize(42);
  parameters.SetSecurityLevel(HEStd_256_classic);
  
  
  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(6458);
  vector<int64_t> tmp_vec_(6458);
  Plaintext tmp;
  int rots_num = 20;
  vector<int> rots(rots_num + 1);
  for(int i = 0; i < rots_num + 1; ++i) {
    rots[i] = i;
  }
  cc->EvalRotateKeyGen(keyPair.secretKey, rots);
  Ciphertext<DCRTPoly> tmp_;

  Ciphertext<DCRTPoly> x, y;
  int yP;
  int yC;
  int c;
  vector<int64_t> tmp_vec_1 = { 343, 512, 388, 275, 544, 376, 329, 50, 11, 102 };
  tmp = cc->MakePackedPlaintext(tmp_vec_1);
  x = cc->Encrypt(keyPair.publicKey, tmp);
  c = 1;
  x = cc->EvalRotate(x, c);
  cc->Decrypt(keyPair.secretKey, x, &tmp);
  tmp->SetLength(10);
  tmp_vec_  = tmp->GetPackedValue();
  for (auto v : tmp_vec_) {
    cout << v << " ";
  }
  cout << endl;
  return 0;
}
  • Expected: 512 388 275 544 376 329 50 11 102 0
  • Outputs (incorrect): (Each execution yields a different value.)
    • -615 -15339 27206 -7128 -5013 -31828 9618 -2709 19818 15937
    • -31953 5956 -21444 -2159 -4422 20697 3662 -1971 8724 10439
    • 32216 -9135 29255 30941 -30405 21746 7735 -2960 19231 24775
    • …

Questions

Is there any known issue related to rotation in this scheme/version?
Could this behavior indicate missing preconditions for EvalRotate that are not documented/implemented?

__
Thanks in advance!

2

Using 0 levels with your current plaintext modulus might be causing the problem. For the noise analysis based on the crypto parameters, you can check Revisiting Homomorphic Encryption Schemes for Finite Fields.
I tried your script with the following parameters and both output correct values.

Option 1:

...
    parameters.SetMultiplicativeDepth(0);
    parameters.SetPlaintextModulus(536903681);
...

Option 2:

...
    parameters.SetMultiplicativeDepth(1);
    parameters.SetPlaintextModulus(65537);
...
3

In BFV, the default key switching method is BV key switching. The noise incurred during BV key switching is high. To support rotations in this case, you need to set the key switch count to the number of rotations you want to support, i.e., parameters.SetKeySwitchCount(1). Alternatively, you can set the key switch technique to HYBRID (the noise of rotation is small in this case). The differences in the noise for BV and HYBRID key switching are described in the paper cited by @seyda

4

Thank you for the explanation and the suggestions on adjusting parameters, and I understand now why the rotation wasn’t functioning as expected with the original setup!