9
$\begingroup$

I have seen the terms multiplicative depth and multiplicative level while reading

Is there a difference between the term multiplicative depth and multiplicative level?

$\endgroup$
0

2 Answers 2

10
$\begingroup$

In Fully Homomorphic Encryption (in short FHE), we have a noise that increased with every operation, and it is almost doubled with the multiplication. When preparing the circuit $\mathcal{C}$ to $\texttt{EVAL}$ on the cloud we have to consider various parameters to deal with the noise of which the FHE scheme provides. Minimizing boothstrapping calls, which is very costly, number of modulus switching and linearization, etc. According to parameters, the FHE scheme may provide more than 1 multiplication without bootstrapping.

Multiplicative depth (From your reference) :

The multiplicative depth is the maximal number of sequential homomorphic multiplications which can be performed on fresh ciphertexts such that once decrypted we retrieve the result of these multiplications.

What is multiplicative level?

This cannot be easily understood if you don't implement some problems. Here is a simple explanation from Efficient Fully Homomorphic Encryption from (Standard) LWE

During the homomorphic evaluation, we will generate ciphertexts of the form $c = ((v, w), \ell)$, where the tag $\ell$ indicates the multiplicative level at which the ciphertext has been generated (hence fresh ciphertexts are tagged with 0). The requirement that $f$ is layered will make sure that throughout the homomorphic evaluation all inputs to a gate have the same tag.

Here is the trick, if you need to add a fresh ciphertext $c_i$ into a level $l$ (that can be quite common as encryption of 1 or 0 1), you need to increase the level of $c_i$ to $l$. Otherwise, the operations will fail.

Example: Let we want to multiply $p_1,p_2, p_3$ with FHE. Let $c_i = Enc_{k_{pub}}(p_i)$, and clearly they have 0 multiplication level. You need to send $$\texttt{EVAL}(\mathcal{C},k_{pub},c_1,c_2,c_3)$$ The server first calculates3 $$c_4 = c_1 \cdot c_2.$$ Now, the $c_4$ has multiplication level 1. To multiply $c_4 \cdot c_3$ we need to increase the multiplication level of $c_3$ to 1. Once they are equal, we can multiply.


In short: multiplicative depth is how much multiplication can be performed and multiplicative level is how many multiplication is performed on a ciphertext2.

For the comment: While implementation we want to keep track of the current level of the ciphertexts so that if the scheme doesn't allow multiplications of different ciphertext we can adjust or we make sure that the level on any ciphertext doesn't exceed the depth. So, it is a quite useful definition for a variable.


1 The Private Information Retrieval article Bandwidth Efficient PIR from NTRU is implemented as Mux and the selector bits needs to have the same multiplicative level.

2Multiplcative level cannot exceed the multiplicative depth, otherwise you cannot decrypt.

3The calculation performed according to your circuit $\mathcal{C}$.

$\endgroup$
5
  • $\begingroup$ Is there any reason for using the term "level"? $\endgroup$
    – fallere456
    Commented Sep 4, 2019 at 8:42
  • $\begingroup$ @fallere456 see the update. $\endgroup$
    – kelalaka
    Commented Sep 4, 2019 at 16:41
  • $\begingroup$ is the concept of this level and the level in Leveled Homomorphic Encryption the same? $\endgroup$
    – fallere456
    Commented Sep 5, 2019 at 4:39
  • $\begingroup$ why the noise is almost doubled with the multiplication? Any papers? $\endgroup$
    – macknight
    Commented Jul 20, 2023 at 14:34
  • $\begingroup$ @macknight Just multiply two number and see that the size almost doubles, the ciphertext will inherit the same properties. To see in mode detail, work on one shceme and you will see. $\endgroup$
    – kelalaka
    Commented Aug 7, 2023 at 13:56
4
$\begingroup$

Fresh ciphertext, i.e., output by the encryption function, are at level $1$. When you multiply ciphertexts $c_0$ and $c_1$ that are at level $L_0$ and $L_1$, you get a ciphertext in level $L_0 + L_1$.

Hence, if a $c$ is at level $L$, then the homomorphic computation that generated $c$ involved something like $\prod_{i=1}^L c_i$ (more accurately, you computed a polynomial of degree $L$ in order to get $c$).

Thus, if you evaluate a circuit of depth $L$, you start with ciphertexts in the lower level $1$ and goes obtaining ciphertexts in the middle levels, until you perform a sequence of $L$ products, and you get ciphertexts in the upper level $L$.

Some authors can state things in the other way around, that is, saying that you start with ciphertexts at level $L$ (or $L-1$) and products "consume" the level, generating ciphertexts in lower levels, until you reach the level $1$ (or $0$).

$\endgroup$
1
  • $\begingroup$ If multiplicative depth indicates the how many ct multiplications can be done before decryption fails, does it mean it is necessary (or desirable) to have a higher multiplicative depth? I suppose higher multiplicative depth also increases the computational complexity as this means large modulo q. $\endgroup$
    – shijuza
    Commented Mar 3, 2022 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.