1
$\begingroup$

Why are homomorphic algorithms slower than regular(symmetric and asymmetric) algorithms?

For example RSA in regular asymmetric cryptography uses the same algorithm as in RSA homomorphic (partially HE) cryptography.

but in homomorphic Whereas there isn't decryption time for execution time homomorphic is slow?

$\endgroup$
  • 2
    $\begingroup$ homomorphismens -> more structure -> higher security parameters -> more effort -> slower $\endgroup$ – SEJPM Dec 30 '16 at 16:02
  • 2
    $\begingroup$ Your question is a bit ill-stated. Homomorphic encryption schemes are not necessarily slower then non-homomorphic ones. For instance, RSA or ELgamal encryption. Those schemes are only homomorphic with respect to one group operator. What you had in mind is presumably fully homomorphic encryption, I.e. homomorphic with respect to two operations of a ring structure. $\endgroup$ – user27950 Dec 31 '16 at 6:20
  • $\begingroup$ @Heo Can you please clear up that last line? I cannot make any sense of it. Maybe an example where homomorphic encryption is clearly slower than you expect would be in order? Then we've got something to base answers on. $\endgroup$ – Maarten Bodewes Dec 31 '16 at 9:30
  • $\begingroup$ thanks for your help my purpose in last line is compare two rsa (homomorphic and non-homo.) . for examplae in non homomorphic when you send encrypt data to server data must decrypt until process in data affect , but in homomorphic decryption in server side doesn't exist so question are here Whereas there isn't decryption time in server side for homomorphic why it is slower in all ? $\endgroup$ – Heo Dec 31 '16 at 11:31
2
$\begingroup$

The fundamental issue is that we can not branch on the secret values, so we must execute all possible branches, and execute additional logic to select the correct branch result.

Another issue that is specific to current fully homomorphic encryption schemes, is that they rely on noise to hide the secrets. This immediately yields that we must work on larger data than our actual values, but more importantly the noise growth eventually will overflow, and so a very costly operation called "bootstrapping" is invoked to reduce it, this involves homomorphically evaluating the decryption routine using an encrypted private key, so that you obtain a "fresh" encryption of the decryption, with less noise.

$\endgroup$
2
$\begingroup$

We consider the following cases.

Somewhat Homomorphic Schemes(SHS), Fully H.S. (FHS) and Partially Homomorphic Schemes (i.e. homomorphic with respect one operation, either addition or multiplication). RSA belongs to the third case, which is multiplicative homomorphic and is fast. Remark that, the textbook-RSA is multiplicative homomorphic and so insecure, since we do not use a secure padding scheme. A secure cryptosystem in this class is the Pallier's additive homomorphic cryptosystem.

SHS support both operations, addition and multiplication but up to some level. In these systems, beyond some level, the noise to the ciphertext increases so much as a result the decryption is not correct. There are many SHS such as, the family based on the Learning With Errors problem. These systems are slow because they use large keys in order to get the necessary security.

FHS start with a SHS (all SHS are noisy encryption schemes). The construction of Gentry, found a way to refresh the ciphertext in order to decrease the noise (bootstrapping). The reason that make them slow is the bootstrapping step. It applies an operation to ciphertext called ${\tt Recrypt}$, which increases the complexity of the system but also manages to control the noise. So allows as many operation we want and the decryption will be correct. I suggest you to read the original paper of Gentry for the case of FHE. Also see this post.

$\endgroup$

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.