Friday, June 26, 2009

Fully Homomorphic encryption

This was originally a response to an email from my dad, but I've turned it into a blog post. The original story is on Slashdot and the abstract for the paper is also available.

This is great. We can then store all our data on NSA computers, access it anywhere, and not care that they can read the unencrypted data. In fact, I am sure they have high quality back up.

I think you are being sarcastic, but the idea behind the system is that if it works correctly (which is something that the NSA might have figured out a way around), you would never actually send the NSA your unencrypted data.

Interesting that IBM would push this as a feature of cloud computing.

Well, the big idea is that this lets you overcome one of the classical big problems with cloud computing, namely the hesitation associated with giving anyone (even a "super-duper-trustworthy person") all of your private data. This way, you get the advantage of letting someone else deal with your IT costs (where they can apply more specialized expertise and take advantage of economies of scale) without having to give up confidentiality of your data.

IBM could build a bunch of big datacenters, and then have people pay to host their applications and data in the cloud, secure in the knowledge that their data is safer than with a traditional cloud.

After all, this could be valuable without ever resorting to a cloud.

Absolutely. Assuming this holds up to scrutiny (which is certainly not a guarantee), this could be one of the biggest advances in cryptography in decades, perhaps even since the invention of public-key cryptography (which enabled https, among many others). It would allow computers to process information they know nothing about, including down to the level of the processor. That is, the processor itself can't decrypt the data on which it is operating.

Suppose your accountant was working on the company's books. The laptop could have encrypted data, and the accountant could do all their work without ever having an unencrypted copy on the computer.

Exactly. Or think of a database admin who has to ensure that the database stays running efficiently, but shouldn't be allowed to see the people's encrypted data.

Even the output file could be encrypted (I assume).

Yes, that is the whole point. The client takes some encrypted data and a program and produces an encrypted version of that data and a modified program which, when run on the encrypted data, will produce the same result as running the original program on the unencrypted data and then encrypting it.

So I fill out my tax form, send it to some company, they do a computation, and give me an encrypted tax return, but they never get to see any of my private data. The result only gets decrypted on my computer.

If someone stole the laptop they would have useless files.

Exactly, and that could be a big boon as well. Not only do you not have to worry about lost laptops revealing information, but that info never needs to make it to those companies in the first place.

But IBM has to find a way to say this is marketable. Right now the advantage of the cloud to a commercial entity has to be its capacities: High volume storage, data integrity, security, or analysis expertise. By offering to do at least some things without ever seeing the data the big company gives you a reason to let them have your data. Or, I suppose, one could say "they have your files, but they do NOT have your data"

Exactly. They will say, "running a massive supercomputer is HARD! Let us do that for you and sell you some time and space on the server." It is like the old time-sharing days.

I think that if the following three things happen, this could be earthshattering:

  1. The system turns out to be secure.

  2. The overhead (both time and space) of the system isn't vastly higher than the unencrypted version; say, less than an order of magnitude slower.

  3. IBM resists the temptation to patent the idea.

1) is important for obvious reasons; if the system isn't secure, it is just a fancy waste of time. If doing the fully homomorphic encryption is much, much slower then this won't see much use outside of specialized applications. 3) is important because putting a patent on the system which prevented or impeded the development of alternative implementations and usages would prevent it from becoming a universal standard, able to replace legacy systems. The temptation to patent and hold onto it will be high, as it could be a large competitive advantage, but it could end up being much more useful to the world in general if it became ubiquitous.