Multiplication Depth in BFV

Library Questions
1

Hi,

I’m using BFV, the multiplication depth is set to 3, and the plaintext modulus is set to 65537. But I observe that I can do only a few number of operations like ciphertext-plaintext multiplications.

For example, the algorithm contains 5 ciphertext-plaintext multiplications and 1 ciphertext-ciphertext multiplication, and I cannot decrypt the correct results due to the noise growth. Can you suggest a reasonable parameter setting for this use case? And I don’t want to increase the dimension N, which is currently 8192, and increasing it will make the computation much slower.

Thanks!

2

Also, does increasing the depth will increase the computation overhead, even if the ring dimension is the same? If this is the case, could you explain a bit why?

3

Hi @somnus

First, I would like to confirm whether you are getting incorrect results due to noise growth or an overflow over the plaintext modulus. These are two different issues. I suggest watching Homomorphic Encryption for OpenFHE Users – OpenFHE.org to get more familiar with both. Slides 15 and 16 should be especially helpful. Please let me know if you still have questions after watching the webinar.

4

Hi, I already read this and I confirm it is noise growth. Does 5 cipher-plain multiplication and 1 cipher-cipher multiplication necessarily require 6 multiplicative depth?

5

Depends on how you evaluate the circuit. If you look at slide 16, you will see that the preferred way is to use the binary tree multiplication technique. In this case, the depth is logarithmic with the number of multiplications. I suggest watching/reading the material on slide 16 more carefully.

6

I know this. Indeed the depth is 6. I’m just asking if the plaintext-ciphertext multiplications consume the same depth as ciphertext-ciphertext multiplications.

7

In terms of noise growth, a ciphertext-plaintext multiplication has a noise growth that is about 4 \sqrt{n} smaller than a ciphertext-ciphertext multiplication. However, for simplicity OpenFHE uses a more conservative estimate in choosing \log q: it treats all multiplications along the longest binary tree path as ciphertext-ciphertext multiplications. Theoretically speaking, you could use a lower \log q but there are no guarantees for its correctness; and you would have to perform heuristic analysis yourself to justify tighter parameters.

8

@ypolyakov May I ask if there are any other parameters I need to modify? If I simply decrease q or increase p, the results are becoming random. I’m also wondering if there are any APIs I can use to check the noise budget left. I’m currently using this set of parameters:

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.SetKeySwitchTechnique(BV);
parameters.SetFirstModSize(55);
parameters.SetRingDim(8192);
cryptoContext = GenCryptoContext(parameters);
cryptoContext->Enable(PKE);
cryptoContext->Enable(LEVELEDSHE);
cryptoContext->Enable(ADVANCEDSHE);
keyPair = cryptoContext->KeyGen();
cryptoContext->EvalMultKeyGen(keyPair.secretKey);
9

I don’t completely understand the question. Generally speaking, you can increase the multiplicative depth to increase the noise budget - so you are probably asking about this parameter.

The plaintext modulus is determined by the functionality - if you want to perform integer computations, then the result (including intermediate results) should not overflow the modulus. A larger plaintext modulus may also increase the underlying q (each level requires noise proportional to the plaintext modulus).

SetFirstModSize is not relevant for BFV.

10

I want to also add that the scenario of using a multiplicative depth smaller than the depth of the computation is not recommended. First, it can lead to decryption errors. Second, if it produces incorrect results, it may leak information about the secret key. It’s best to use the actual depth instead.