In what ways does Full or Partial Homomorphic Encryption benefit the cloud?

Question

Can someone explain, in plain English, the practical ways FHE and PHE can be leveraged in the cloud? Some interesting (and confusing) links include this Microsoft Research PDF and this Wikipedia entry.

Questions:

• Is homomorphic encryption considered secure, from a cryptanalysis point of view?

• What operations can/can't be done with FHE/PHE data?

• Considering that some PHE algorithms exist today, and they are apparently fast enough; should they be considered for production use? Please provide some scenarios in which PHE could be used.

Related:

What Partial Homomorphic Encryption implementations exist and how do I leverage them?

Answer 1

Homomorphic encryption is about encryption schemes which allow computing with encrypted value without decrypting them. For instance, given E(a) and E(b) (the encryption of a and b), you can compute E(a+b) without knowing a, b nor the decryption key.

Homomorphic encryption schemes are very useful in voting schemes, with the following structure: voters encrypt their votes, the homomorphic property is used to add all votes together, and the result is decrypted (with group decryption by a set of authorities who need to gather together, in a very public way, to perform a decryption). There are several homomorphic encryption schemes, some have been known for decades (e.g. El Gamal). They are efficient, and secure (as secure as asymmetric encryption can be). Note that homomorphic encryption solves the question of anonymous tallying, but that's only a small part of a proper voting scheme (e.g. the voter must also prove that they encrypted a 0 or a 1, not a 20 -- otherwise, they could get 20 votes). Homomorphic encryption can also be used in digital cash systems, there again in order to ensure anonymity or some other properties.

Fully homomorphic encryption is a term which was coined when were first found encryption schemes which preserved two algebraic operations in a ring structure: namely, given E(a) and E(b), you can compute E(a+b) and E(ab). It turns out that with those two operations, you can compute just about everything. This is where the "cloud" gets into the picture: the cloud is powerful, but not trustworthy; hence, you could encrypt your data, send it to the cloud which performs the computation you want to do, and then decrypt the result.

Offloading computations to the cloud is, right now, a pure fantasy. The most efficient fully homomorphic encryption schemes currently known, based on a scheme by Gentry (published in 2009), are still very expensive, and the "arbitrary computation" part involves representing the computation as a circuit where each logic gate is emulated through its own homomorphic encryption. We are not talking about a 10x slowdown here; rather, we are talking about the whole Amazon EC2 cloud not being able, in a day, to perform homomorphically a computation which would take one second on a single iPhone. So while this is very interesting on a theoretical point of view, it will take a while before anything applicable in practice is discovered. Also, 2009 is quite recent; traditionally, we wait for at least 5 to 10 years before declaring that an asymmetric encryption scheme is "secure".

Answer 2

It is already possible, via end-to-end voting systems like Helios to publicly store voted ballots in the cloud in an encrypted fashion, so that the public can add them up to confirm the totals, and to also check that their own vote was indeed included in the total. Without giving someone a 'receipt' that they can use to sell their vote. Surprising, but true. It's great for low-risk private elections. Note however, that even the inventor of Helios, Ben Adida, says “A government election is something that you don’t want to do over the Internet,” citing both the potential for computer viruses to corrupt the voting and the possibility of voter intimidation.

This is possible since only addition is required, and thus partial homomorphic approaches work. I expect we'll find other interesting cases like this, but real general-purpose computation would require further advances in efficiency.

Note that the "Practical?" paper you reference talks of the size of the ciphertexts in one scheme being on the order of 50 kB. That means that every number (e.g. in a set of medical lab data) is represented by a ciphertext which is 4 orders of magnitude larger.... That makes the cost of the cloud storage rather impractical.

And D.W. writes in a comment above:

In some cases, it may be worse than that: it may be that you have to construct a boolean circuit, and each bit may be represented by some ginormous ciphertext. No, it is not practical today. It is many orders of magnitude away from being economically viable. But it's so darn cool...

My take is that

• Homomorphic encryption is a major advance in theoretical computer science, that could have enormous ramifications for security
• ...or it may remain a beautiful toy, useful only for very restricted problems like election transparency.

Answer 3

Homomorphic encryption is a category of systems; some implementations might be weak, and others might be strong, but it doesn't make sense to talk of the entire category as "weak" or cryptanalyzable.

Partially homomorphic cryptosystems (which used to be called just "homomorphic" before "fully homomorphic" cryptosystems were discovered) have been used in crypto for a while, including, as Neal points out, in my voting system, Helios. In these systems, you can perform one operation, either addition OR multiplication, under the covers of encryption. That lets you do interesting things, like counting individual votes and only decrypting the tally.

Now, when I say "don't use Helios for public-office elections," it's not because of any weakness in homomorphic encryption. That's the strongest part of the system. The problem with online voting is that your desktop client could be compromised by malware, thereby changing your vote before it is encrypted. The homomorphic tallying portion is quite secure, and there are no known attacks against it.

Boneh, Goh, and Nissim designed a more homomorphic cryptosystem in 2005, where you could do any number of additions, followed by one multiplication, followed by any number of additions, before decrypting. That enabled more interesting applications, e.g. my work on Public Mixing (also applicable to voting), where you can shuffle a set of encrypted values in a public operation, without revealing in what order you shuffled them (pretty crazy, when you think about it.)

Fully hommomorphic cryptosystems, where you can do arbitrary additions and multiplications, were thought to be impossible until Gentry's work a couple of years ago. What's meaningful about this category of cryptosystem is that you could fully outsource any computation to the cloud without ever revealing plaintext data. For example, if you wanted to perform a full text search of the word "cryptography" on a corpus of text, you could encrypt the corpus, encrypt the word "cryptography", and ship that to another party who would perform the full-text search on fully encrypted data, and return to you the encrypted result, which you could then decrypt to get the answer. The system that does the computation would known nothing about the corpus or the search query. Pretty amazing.

But of course, this only makes sense if the process of encrypting, and the process of performing homomorphic operations, is still cheaper on the cloud than doing it yourself in plaintext on your local machine. We're very, very far from that. That said, cryptosystems only get better with time, so maybe we'll see generic homomorphic computation become useful in a few years.

In the meantime, there are probably plenty of specific problems -- not generic computation -- that can be outsourced more securely thanks to homomorphic technology.

Answer 4

How can they be used? Right now? They can't. They're too slow for most/all practical applications. No point in considering homomorphic encryption for production use today -- way too slow.

The hope is that, if we can improve the algorithms to make them a lot faster, someday in the future, it may enable us to run computations in the cloud without trusting the cloud provider. The dream is that we encrypt all our data locally, send the encrypted data up to the cloud provider, the cloud provider can do all the computation we wanted on the data (while it is still in encrypted form), ending up with the final results in encrypted form, and then we can download the results and decrypt them locally. The result is that the cloud provider doesn't get to see our data. That's the dream, anyway, and fully homomorphic encryption has the potential to help us achieve this dream someday -- if cryptographers can figure out how to make it a lot faster.