What Is Homomorphic Encryption, and Why Should I Care? (2010)

From performance viewpoint the concept is far from practical right now, and I don't mean practical implementations, I mean the current best theoretical limits for overhead.

Basically the encrypting process itself takes longer than any operation that can be done on the on the cloud. Thus it's better to just run the software without the encryption on the device that would normally contact the cloud itself.

I think the dream of homomorphic encryption ever being practical (at least for what I would consider practical) is unrealistic.

Let f(x) represent the encryption of x.

I would assume that a practical system has the following properties: * It is possible to compose primitive operators and values to implement a +1 operator (i.e. an operator that adds one to an integer). Call this operator g(x), defined such that g(f(x)) = f(x + 1). * If the value of 1 is leaked (which might, for example, be a literal that is used in a position that is known to the attacker), that shouldn't compromise the entire scheme. * The scheme must provide a way to compare for equality so variable-length algorithms are possible. Define a function h such that h(f(x), f(y)) is true iff x = y.

By our assumptions, the attacker knows f(1). They can compute f(i + 1) = g(f(i)), and so they can compute as many small integers as they want. Suppose they have an unknown value u, that they know is a small integer, but they don't know which one. They can test h(u, i) for each i up to some limit to find the value of u. Hence, the encryption scheme is insecure.

Here's a more recent and super simple introduction to the concept: https://www.cryptologie.net/article/278/homomorphic-encrypti...