Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
