What are the reasons that FHE is so slow? Is it possible to make the FHE algorithm so fast that it can be used in practice (say, the practical FHE algorithm should be slower no more than 10 times compared to conventional calculations)?

Or there is some fundamental limitation and any FHE implementations will always be millions of times slower than usual calculations?


I don't know how to answer why it's slow; it's slow because it's slow? The algorithm involves a lot of computation, and that takes a long time to do.

Is it possible to make a fast FHE? No one knows. It's an open problem. If it was easy, we would have done it so far. So either it's not possible; or it's possible but it's challenging and we currently don't know how to do it.

In some sense, it's not surprising that FHE is a lot slower than traditional cryptography. FHE imposes some very strong requirements on the encryption scheme. This constrains what kind of encryption scheme you can use. It's no surprise that if you add extra requirements, it's harder to make the scheme also be fast; and it feels reasonable that the stronger the requirements, the slower this might make the scheme. In this case, the FHE requirement is very strong indeed.

I'm not aware of any proof that FHE must be slow. However, there are some results that may be somewhat indicative. In particular, the following paper shows that any FHE scheme can be broken in subexponential time (while we believe that traditional encryption schemes require exponential time to break). This means that the FHE scheme will require larger parameter sizes to be secure. Usually, larger parameter sizes mean that the scheme will be slower. So, that is some weak indication that FHE schemes will need to be slower. However, it doesn't really answer the question; it's just a hint.

Algorithms for black box fields and their application to cryptography. Dan Boneh, Richard Lipton. CRYPTO '96.

  • $\begingroup$ How much slower are we talking approximately? 10x? 1000x? more? $\endgroup$ – user643011 Apr 5 '20 at 22:53

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.