Mfcttrf

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

• 
  Faster homomorphic encryption is not enough: improved heuristic for multiplicative depth minimization of Boolean circuits by Aubry et. al, 2019.

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

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 $mathcalC$ to $textttEVAL$ 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 ¹), 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 $$textttEVAL(mathcalC,k_pub,c_1,c_2,c_3)$$ The server first calculates³$$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 ciphertext².

_{¹ 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.}

_{²Multiplcative level cannot exceed the multiplicative depth, otherwise you cannot decrypt.}

_{³The calculation performed according to your circuit $mathcalC$.}

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$).