Questions Regarding Multiplicative Depth in BGV and CKKS Schemes

Library Questions
1

Hello OpenFHE Team,
Thank you so much for developing this impressive library!

I am currently conducting several tests on homomorphic encryption libraries and have some questions regarding the OpenFHE library.

I have observed that using the BGV scheme in the following code results in incorrect outcomes when performing more multiplications than the multiplicative depth allows.

#include <iostream>
#include "openfhe.h"

using namespace lbcrypto;
using namespace std;

int main(void) {
  CCParams<CryptoContextBFVRNS> parameters;
  parameters.SetRingDim(16384);
  size_t plaintext_modulus = 65537;
  parameters.SetPlaintextModulus(plaintext_modulus);
  parameters.SetMultiplicativeDepth(3);
  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;
  Ciphertext<DCRTPoly> tmp_;

  Ciphertext<DCRTPoly> x, y;
  // x = 1
  fill(tmp_vec_.begin(), tmp_vec_.end(), 1);
  tmp = cc->MakePackedPlaintext(tmp_vec_);
  x = cc->Encrypt(keyPair.publicKey, tmp);
  // x = 5
  fill(tmp_vec_.begin(), tmp_vec_.end(), 5);
  tmp = cc->MakePackedPlaintext(tmp_vec_);
  y = cc->Encrypt(keyPair.publicKey, tmp);
  // x *= y
  x = cc->EvalMultAndRelinearize(x, y);
  cc->Decrypt(keyPair.secretKey,x, &tmp);
  tmp_vec_ = tmp->GetPackedValue();
  // print(x)
  cout << tmp_vec_[0] << endl;
  // x *= y
  x = cc->EvalMultAndRelinearize(x, y);
  cc->Decrypt(keyPair.secretKey,x, &tmp);
  tmp_vec_ = tmp->GetPackedValue();
  // print(x)
  cout << tmp_vec_[0] << endl;
  // x *= y
  x = cc->EvalMultAndRelinearize(x, y);
  cc->Decrypt(keyPair.secretKey,x, &tmp);
  tmp_vec_ = tmp->GetPackedValue();
  // print(x)
  cout << tmp_vec_[0] << endl;
  // x *= y
  x = cc->EvalMultAndRelinearize(x, y);
  cc->Decrypt(keyPair.secretKey,x, &tmp);
  tmp_vec_ = tmp->GetPackedValue();
  // print(x)
  cout << tmp_vec_[0] << endl;
  // x *= y
  x = cc->EvalMultAndRelinearize(x, y);
  cc->Decrypt(keyPair.secretKey,x, &tmp);
  tmp_vec_ = tmp->GetPackedValue();
  // print(x)
  cout << tmp_vec_[0] << endl;
  return 0;
}


// output : 5 25 125 625 12042

Similarly, using the CKKS scheme in the following code, I have noticed that it throws an exception when more multiplications than the multiplicative depth are performed.

#include <iostream>
#include "openfhe.h"

using namespace lbcrypto;
using namespace std;

int main(void) {
  CCParams<CryptoContextCKKSRNS> parameters;
  parameters.SetRingDim(16384);
  parameters.SetMultiplicativeDepth(3);
  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()/2);
  vector<complex<double>> tmp_vec_(slots);
  Plaintext tmp;
  Ciphertext<DCRTPoly> tmp_;

  Ciphertext<DCRTPoly> x, y;
  vector<double> tmp_vec_1(slots, 1.0);
  tmp = cc->MakeCKKSPackedPlaintext(tmp_vec_1);
  x = cc->Encrypt(keyPair.publicKey, tmp);
  vector<double> tmp_vec_2(slots, 5.0);
  tmp = cc->MakeCKKSPackedPlaintext(tmp_vec_2);
  y = cc->Encrypt(keyPair.publicKey, tmp);
  x = cc->EvalMultAndRelinearize(x, y);
  cc->Decrypt(keyPair.secretKey,x, &tmp);
  tmp->SetLength(1);
  tmp_vec_ = tmp->GetCKKSPackedValue();
  cout << fixed << setprecision(1) << real(tmp_vec_[0]) << endl;
  x = cc->EvalMultAndRelinearize(x, y);
  cc->Decrypt(keyPair.secretKey,x, &tmp);
  tmp->SetLength(1);
  tmp_vec_ = tmp->GetCKKSPackedValue();
  cout << fixed << setprecision(1) << real(tmp_vec_[0]) << endl;
  x = cc->EvalMultAndRelinearize(x, y);
  cc->Decrypt(keyPair.secretKey,x, &tmp);
  tmp->SetLength(1);
  tmp_vec_ = tmp->GetCKKSPackedValue();
  cout << fixed << setprecision(1) << real(tmp_vec_[0]) << endl;
  x = cc->EvalMultAndRelinearize(x, y);
  cc->Decrypt(keyPair.secretKey,x, &tmp);
  tmp->SetLength(1);
  tmp_vec_ = tmp->GetCKKSPackedValue();
  cout << fixed << setprecision(1) << real(tmp_vec_[0]) << endl;
  x = cc->EvalMultAndRelinearize(x, y);
  cc->Decrypt(keyPair.secretKey,x, &tmp);
  tmp->SetLength(1);
  tmp_vec_ = tmp->GetCKKSPackedValue();
  cout << fixed << setprecision(1) << real(tmp_vec_[0]) << endl;
  return 0;
}

// output : terminate called after throwing an instance of 'lbcrypto::math_error'
  what():  OpenFHE/src/pke/lib/encoding/ckkspackedencoding.cpp:535 The decryption failed because the approximation error is too high. Check the parameters.

Question 1: Can I understand that the OpenFHE library guarantees correct results only for programs that use consecutive multiplications within the multiplicative depth for all arithmetic schemes (BFV, BGV, CKKS)?

Question 2: In the case of the BGV scheme, when operations exceed the multiplicative depth, is the occurrence of incorrect results without an exception an intended behavior?

Thank you very much!

2

Hi @Maokami,

I am a little bit confused by the question. Your first example is for BFV rather than BGV. In BFV, the ciphertext modulus remains the same whereas in BGV and CKKS modulus switching/rescaling is done after every multiplication. So in BGV and CKKS, an exception will be thrown. In BFV, an exception is not currently thrown (though it is best to do it to prevent incorrect results from being displayed).

The main parameter is the multiplicative depth (number of chained multiplications). Note that many multiplications are typically evaluated in a binary tree fashion to require a depth that is logarithmic in the number of multiplications.

3

Thanks for the clarification @ypolyakov !

You’re right, my question was for BFV :sweat_smile:

Now I understand why CKKS throws an exception but BFV doesn’t.
However, when I changed the above program to BGV scheme,
(i.e. change CCParams<CryptoContextBFVRNS> to CCParams<CryptoContextBFVRNS>)
it also produced an incorrect result as BGV, which seems to me weird because I guessed it will throw an error because of the multiple modulus switching (exceeding the multiplicative depth), as you said.

Could you check it again please? :grinning:

4

Sorry, “to CCParams<CryptoContextBGVRNS>” :sweat_smile:

5

Hmm. I ran your BFV program and only replaced CCParams<CryptoContextBFVRNS> parameters; with CCParams<CryptoContextBGVRNS> parameters;

I got the following result, which is what I would expect:

bin/examples/pke/simple-integers-bgvrns
5
25
125
1796
terminate called after throwing an instance of ‘lbcrypto::config_error’
what(): …/openfhe-development/src/pke/lib/scheme/bgvrns/bgvrns-leveledshe.cpp:64 ERROR: Not enough towers to support ModReduce.
Aborted (core dumped)

6

Oh, it seems like I made a mistake. I’ll mark it as a solution. Thank you sincerely for taking the time to answering!