BEHZ vs. HPS/default multiplication

Library Questions
1

Hello everyone,

For the the parameters log p = 32, log q = 240, and n = 8192, we observed that with multiplication technique BEHZ we can get a multiplicative depth of 4 while with the default multiplication/HPS we only have 3. What’s the reason for this? According to this paper (also cited in the eprint document for OpenFHE), it says that BEHZ and have about the same noise level.

Many thanks for your help!!

2

Hi @enehta

Theoretically speaking, there should not be any noise growth difference between HPS and BEHZ. Could you post the example you are using for evaluating the noise growth so I could try it to recreate the issue?

Thanks,
Yuriy

4

Hi Yuriy,

Thanks for the response! Sure, I can:

CCParams<CryptoContextBFVRNS> parameters;
KeyPair<DCRTPoly> keyPair;
CryptoContext<DCRTPoly> cryptoContext;
parameters.SetPlaintextModulus(4293918721);
parameters.SetMultiplicativeDepth(3);
parameters.SetMaxRelinSkDeg(2);
parameters.SetSecurityLevel(HEStd_128_classic);
parameters.SetMultiplicationTechnique(BEHZ);
// parameters.SetMultiplicationTechnique(HPSPOVERQLEVELED);
parameters.SetKeySwitchTechnique(BV);
parameters.SetRingDim(8192);
cryptoContext = GenCryptoContext(parameters);
cryptoContext->Enable(PKE);
cryptoContext->Enable(LEVELEDSHE);
cryptoContext->Enable(ADVANCEDSHE);
keyPair = cryptoContext->KeyGen();
cryptoContext->EvalMultKeyGen(keyPair.secretKey);

std::vector<int> toEncrypt(8192);
for (size_t i=0; i < 5; i++)
{
    toEncrypt[i] = i;
}
for (size_t i=5; i < 8192; i++)
{
    toEncrypt[i] = 0;
}
Ciphertext<DCRTPoly> enc_test_vector = cryptoContext->Encrypt(keyPair.publicKey, cryptoContext->MakePackedPlaintext(toEncrypt));

for (int i = 0; i < 4; i++)
{
    enc_test_vector = cryptoContext->EvalMult(enc_test_vector, enc_test_vector);
}

Plaintext plaintextMultResult;
cryptoContext->Decrypt(keyPair.secretKey, enc_test_vector, &plaintextMultResult);
std::cout << "Dec Result: " << plaintextMultResult << endl;

Thank you!

5

Thank you for posting the code. I ran some tests. The example works correctly for BEHZ, HPS, and HPSPOVERQ. It only fails for HPSPOVERQLEVELED. This behavior is expected because HPSPOVERQLEVELED uses the same noise estimation logic as parameter generation, when deciding to what internal modulus to switch for better efficiency (see Revisiting Homomorphic Encryption Schemes for Finite Fields for more details). We never recommend using smaller multiplicative depths than the depth of the circuit to be computed. It may lead to decryption errors, and even potentially leak information about the secret key.

In summary, there is no contradiction to Note on the noise growth of the RNS variants of the BFV scheme Both BEHZ and HPS work the same way for these parameters.

6

Dear Yuriy,

Thanks for quick response. I am not sure if I fully understand why HPSPOVERQLEVELED’s/leveled BFV’s failure is expected. I read that modulus switching is applied inside HE there for better efficiency. Does this implicitly mean, that the library is expecting more noise (i.e., decryption problems) already after less multiplications? I don’t see why it should increase the depth of the circuit (but I might miss something here.)

Thanks!

7

Hi @enehta

The circuit you are trying to execute has depth 4. The multiplicated depth you are setting is 3. In other words, you are trying an unsupported scenario. The leveled approach “distributes” the noise budget over the correct depth of 4. The other three modes do not use the leveled optimization, i.e., additional noise estimation inside homomorphic multiplication. In principle, I would not recommend using the depth of 3 in this case. If you still want to use it at your own risk, you could use any of the other three options (but the probability of decryption failure still may be high for these options as well).