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?

  • $\begingroup$ what are usual calculations according to you? $\endgroup$ – Florian Bourse Aug 9 '18 at 15:04
  • $\begingroup$ Are you asking about encryption and decryption times or about the homomorphic operations? $\endgroup$ – Hilder Vítor Lima Pereira Aug 9 '18 at 16:48
  • $\begingroup$ The Impossible we do right away, Miracles take a little longer. Don't expect the miracle of being able to do calculation on encrypted data (without decrypting it before) become even remotely a fast as "conventional calculation". As the homomorphic calculation cannot reveal anything about the data the implementation has to take all possible paths through the program requiring always worst time running times or even worse. Take for example a look, how a simple if-else has to be coded. $\endgroup$ – j.p. Aug 11 '18 at 7:38