difference between leveled FHE and normal FHE scheme

Question

What is/are difference/s between leveled Fully Homomorphic Encryption and normal Fully Homomorphic Encryption?

Answer 1

FHE should be able to evaluate any circuit. Leveled FHE can evaluate circuits which have a bounded depth.

BGV was, I believe, the first to offer leveled FHE. The gain was in performance. By restricting to only certain depths (where the depth is calculated by looking at multiplication gates), they were able to remove the bootstrapping operation of Gentry's construction (which was very expensive) or at least spread out the bootstrapping.

Another benefit for leveled schemes is that you can remove the assumption of circular security, i.e., that you can safely encrypt your private key with your public key. We don't know (as far as I remember) how safe this is. Note that we can convert a leveled-FHE to an FHE scheme if we assume circular security though (see footnote 1 in the BGV paper).

Answer 2

The difference.

Considering only the definitions of such kinds of schemes, the difference is just that:

• "Normal" FHE schemes can perform any sequence of additions and multiplications homomorphically (that is, over ciphertexts in a way that is equivalent to operate over plaintexts).
• Leveled FHE schemes can perform up to $L$ multiplications in sequence, where $L$ is a scheme's parameter (sometimes an implicit parameter).

All the other possible differences are consequences of this difference or only apply to some particular schemes (therefore, not applied in general).

For instance, some differences that are consequences of this difference are:

1. The keys' sizes depend on $L$ and on $\lambda$ in leveled schemes while in pure FHE they depend only on the security parameter $\lambda$ (so, the bigger $L$ is, the bigger the keys will be).
2. Since ciphertext's sizes depend on the key's sizes, they also depend on $L$ in leveled schemes.

A note about the circular security assumption.

I am sorry, but I disagree that there is a relation between leveled schemes and circular security assumption... There is nothing prohibiting someone from creating a (normal) FHE that doesn't rely on the circular security. In the other hand, someone can create a leveled FHE scheme that rely on that assumption (the FV scheme, for instance, uses what authors call weak circular security assumption).

BGV scheme does not rely on this assumption because it defines $L$ keys instead of one single key, and each of those $L$ keys is used in one level of the circuit being evaluated. Not all leveled FHE will necessarily have this feature.

Answer 3

A leveled fully homorphic encryption scheme is a homorphic scheme where FHE.KeyGen receives an additional input $1^{d}$ and the resulting scheme is homorphic for all depth-d arithmetic circuits over GF(2)