What is/are difference/s between leveled Fully Homomorphic Encryption and normal Fully Homomorphic Encryption?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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).