Is there any difference between somewhat homomorphic encryption and leveled homomorphic encryption? I heard that leveled homomorphic encryption supports computing circuits of bounded depth on cipher text, and somewhat homomorphic encryption supports computing polynomials of low degree on cipher text. What's the difference? Which is stronger?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let $\mathcal{C}$ be the set of allowed binary circuits.
Then, a $\mathcal{C}$-evaluation scheme $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Eval}, \mathsf{Dec})$ that has (i) correct decryption and (ii) correct evaluation is called a somewhat homomorphic encryption scheme (SHE).
A $\mathcal{C}$-evaluation scheme $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Eval}, \mathsf{Dec})$ is called a levelled homomorphic scheme if it has (i) correct decryption, (ii) correct evaluation, (iii) takes an auxiliary input $d$ to $\mathsf{Gen}$ which specifies the maximum depth of circuits that can be evaluated, (iv) is compact, and finally requires that the length of the output of $\mathsf{Eval}$ does not depend on $d$.
As you can see, levelled homorphic scheme is an "extended" form of SHE. However, if you allow any circuits with depth at most $d$ in $\mathcal{C}$, then you have a levelled fully homomorphic scheme.
If you want to go a step further, there is also $i$-hop and $\infty$-hop correctness for schemes building on top of SHE/[levelled] [fully] homomorphic schemes.
Now let's come to your questions: bounded depth for levelled homomorphic encryption as well as the difference between both should be clear now. For the degree of the polynomial $p$, maybe you were referring to compactness, since it restricts the output of $\mathsf{Eval}$ to at most $p(\lambda)$ bits, where $\lambda$ is the security parameter. I don't know your definition of strong here, therefore I leave it open to you to choose the "better one".
The following paper may help you further in your questions: A Guide to Fully Homomorphic Encryption
