4
$\begingroup$

Is there a point in using LHE over SHE?

From what I understand, SHE is like an extended version of LHE, the only difference is that you limit the depth of circuits that can be evaluated. Therefore, I wonder which is better to use since they seem to be the same.

What is the effect of limiting the depth of the circuits? That does not make much sense to me.

$\endgroup$
  • $\begingroup$ That will depend on your problem, and in this form, this is too broad. $\endgroup$ – kelalaka Aug 28 '19 at 9:15
  • $\begingroup$ How can i make it less broad since what i am trying to find out is is there even any point in using LHE since from what i understood LHE is supposed to be a better version SWHE $\endgroup$ – fallere456 Aug 28 '19 at 9:42
  • $\begingroup$ Did you look at the help page $\endgroup$ – kelalaka Aug 28 '19 at 9:44
1
$\begingroup$

I would take a look at Brakerski's survey to clarify the exact differences between LFHE and SHE.

In the survey it says

Leveled FHE [...] refers to a family of FHE schemes that allow, for any depth bound $d$, to generate an instance of the FHE scheme that supports the evaluation of depth-$d$ circuits.

And also

In early works on FHE, the term somewhat homomorphic encryption (SHE) was used to indicate a scheme with homomorphic capabilities against a restricted class of functions (depth bounded). The two terms are sometimes used interchangeably, however in the original SHE scheme [Gen09b, Gen09a] the parameters of the scheme grew exponentially with $d$.

So, even though both of them accept a restricted family of circuits, we see that with LFHE you can "plan" in advance which type of functions you want to compute (i.e. up to what depth) and then you can obtain FHE for that family, whereas with SHE this bound on the depth is more 'universal', in the sense that it doesn't scale well with the depth and hence you're forced to keep a relatively low depth (but you can still use bootstrapping if this depth is large enough).

Notice that LFHE actually makes sense in practice: You probably use an FHE scheme with some specific application in mind, and in that case you can find a suitable LFHE scheme that fits your function.

$\endgroup$
  • $\begingroup$ What does it exactly mean by SHE not scaling well with the depth how does this compare to Leveled HE? $\endgroup$ – fallere456 Sep 4 '19 at 8:43
1
$\begingroup$

since from what i understand SHE is like an extended version of LHE

Your understanding is, unfortunately, not correct.

What is the effect of limiting the depth of the circuits? it does not seems to make much sense to me.

I am not sure if you got the point, but the limitation imposed by SHE schemes was not intentional, the authors didn't propose homomorphic schemes with such limitations because they though it was better like that, it just happened to be the only way people knew how to construct homomorphic encryption schemes at the time.

So, just highlight some differences between leveled and somewhat homomorphic schemes:

Squashing the decryption circuit

Somewhat homomorphic encryption schemes are schemes that can perform two operations homomorphically (basically, addition and multiplication), but only a limited number of them, but the important point is that you can't increase this limit by choosing new parameters. That is, if a scheme is somewhat homomorphic, it has an intrinsic limit in the depth of the circuits it can evaluate, typically, $O(\log \lambda)$.

It is because of that limitation that the first SHE schemes "squashed" the decryption function in order to bootstrap, i.e., they published some auxiliary information about the secret key so that we reduce the depth of the decryption circuit to meet this $O(\log \lambda)$ limit. As an example, check section 6.1 of of this paper by Dijk, Gentry, and others.

In Leveled homomorphic encryption schemes, for any $L$, you can choose the parameters in such a way that you can evaluate circuits of depth $L$. As a consequence, you no longer need to squash the decryption circuits, since now, to bootstrap, you can just set the parameters to support a depth $L$ slightly bigger than the decryption depth. That is an advantage, because it means that you don't need to publish information about the secret key, thus, you have less security assumptions. Moreover, public key size decreases, since you are making less things public.

Using the schemes without bootstrapping

LHE are more flexible in the sense that you can use them without bootstrapping targeting some application. I mean, imagine you have an application in mind for which you just need to evaluate circuits with depth $\lambda\log \lambda$. If you use SHE, then you will need to bootstrap anyway, probably to perform the bootstrapping procedure several times after some sequences of operations, but this is very costly! Using LHE, you can set $L = \lambda \log \lambda$, then you don't need to bootstrap and, maybe (depending on the scheme), the evaluation can be much faster.

$\endgroup$
  • $\begingroup$ In LHE can you still use bootstrapping to go beyond the selected parameter? $\endgroup$ – fallere456 Sep 4 '19 at 8:44
  • $\begingroup$ Yes. Let's say that the decryption circuit has a depth equal to $\lambda$, then, if you set, for example, $L = \lambda + 1$, then you can homomorphically perform one multiplication plus the decryption, therefore, you can perform as many multiplications as you want, by bootstrapping after each product. That is why you don't need to "squash the decryption circuit". $\endgroup$ – Hilder Vitor Lima Pereira Sep 4 '19 at 9:14
  • $\begingroup$ So other than being faster than SHE in its computation performance it is also less expensive and the scaling of error is also lower? and also to clarify in spite of setting a certain parameter it is still possible to go beyond that so for example if I perform a certain a multiplication 100 times i can still go beyond that set parameter even though i already set a certain depth i can still go beyond the parameter by bootstrapping? $\endgroup$ – fallere456 Sep 4 '19 at 9:36
  • $\begingroup$ The error grows exponentially in SHE schemes as the one I linked while in LHE schemes the error growth is only polynomial, so, yes, lower. It implies that, for general functions, mainly when you have to use bootstrap, LHE are usually faster and have smaller public keys. But you have to be careful to not compare apples and oranges. For instance, doing a single homomorphic addition may be faster than using a SHE schemes over the integers than using a LWE-based LHE. Another advantage of LHE, as I said in the answer, is that they typically need less hardness assumptions, so tend to be more secure $\endgroup$ – Hilder Vitor Lima Pereira Sep 4 '19 at 9:47
  • $\begingroup$ How would you compare the scalability of SHE schemes with LHE schemes? and in terms of parameters what are the parameters in SHE schemes? $\endgroup$ – fallere456 Sep 5 '19 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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