Homomorphic cryptography has some astonishing properties. Mathematical operations are performed on encrypted data giving encrypted results. So you can outsource calculations on confidential information to parties that you do not trust. They will only see the encrypted data and provide you with an encrypted result. All you have to do is decrypt the data with your secret key and, voila, there is your result in clear text.
To explain the mechanism behind homomorphic encryption, I shall show a simplified example. Suppose that we encrypt data by using the power of two. Decryption, is then by taking the logarithm of base two. For reasons of simplicity no secret keys are involved in this example. Also, assume that decryption is infeasible without the secret keys. For most people, logarithms are infeasible anyway 8-).
Suppose that Anna wants Boris to add two numbers, say 5 and 7. But Anna does not trust Boris, so Boris should never know the exact numbers he is about to add. First Anna encrypts the numbers by calculating the power of two:
input#1 = 5
input#2 = 7
cryptoText#1 = 2^5 = 2 x 2 x 2 x 2 x 2 = 32
cryptoText#2 = 2^7 = 2 x 2 x 2 x 2 x 2 x 2 x 2 = 128
Now, Anna sends the cryptotext numbers to Boris for addition. Since the numbers are encrypted, this is cannot be an ordinary addition. Instead it is a special algorithm, in this case multiplication. So Boris must multiply the cryptotexts:
encryptedResult = crypotoText#1 x crypotoText#2 = 32 x 128 = 4096
Then Boris sends the encrypted result back to Anna. Anna determines the result by taking the logarithm of 2 of the result from Boris:
result = 2log(encryptedResult) = 2log(4096) = 12
As we can see, Anna obtained the correct result from Boris (since 5 + 7 = 12 indeed), even though Boris has never seen the actual numbers.
There are interesting applications for homomorhic cryptography. Cloud providers can manipulate your data without them knowing what the data really is. For example, a financial analist can perform a complex financial analysis without him ever knowing your personal wealth.
But now the bad news
Homomorphic cryptography is 100_000 times slower then operations in the clear. A homomorphic multiplication takes little less than a second (as of 2012). That throws us back to the computing performance of around 1946.
So homomorphic cryptography is very expensive. We need 100_000 as much time, 100_000 times as much energy for computing and cooling, etc. The bill from your hosting company will 100_000 times higher. So it may be secure, but it is not sustainable [in het Nederlands vaak ten onrechte aangeduid als duurzaam].
Almost a second per multiplication is totally unacceptable, of course. What if computers get faster so that the execution times become acceptable?
First given Moore’s law, it takes almost 25 years for computers to become 100_000 times faster. So in 2037 homomorphic computations will show 2012 performance. However, the performance penalty relative to computations on clear numbers is not taken away by that: these also become faster. So homomorphic computations remain slow and wasteful. We should also take into consideration that Moore’s law may no longer be true in the future and yearly performance improvements may slow down significantly.
And the really bad news
If computer performance increases with a factor X, then this will not only benefit the homomorphic computations, but also cracking efforts by the same amount. Then to make cracking through brute forcing impossible, we must increase the complexity of the encryption scheme by the same amount.
So any performance increase is immediately undone by the necessary strengthening of the chosen encryption scheme to stop brute forcing…
