Homomorphic encryption: Can it save cloud computing?

An idea of how to prevent what happened to Sony of late was introduced in 1978. It took thirty years, but homomorphic encryption is no longer a theory.

Homomorphic what? My OED suggests the following definition:

"Pertaining to two sets that are related by a homomorphism."

Come on. Let's try homomorphism:

"A transformation of one set into another that preserves in the second set the relations between elements of the first."

Put homomorphic with encryption and thankfully Wikipedia provides something useful:

"A form of encryption where a specific algebraic operation performed on the plain text is equivalent to another (possibly different) algebraic operation performed on the cipher text."

My turn. Homomorphic encryption is a process by which complex calculations can be performed on data, and it does not matter that the data is encrypted.

Why should we care?

Here's why.

Data breaches by those intent on stealing sensitive information will become a distant memory. With homomorphic encryption in play, sensitive information is always encrypted, therefore useless to the bad guys.

Update: Some astute members questioned whether this makes sense for payment-card transactions. My first inclination was that it did. Then I woke up, realizing I better ask someone who knows. Mr. Craig Stuntz was kind enough to set me straight:

"I'm not sure if there's a great case for using homomorphic encryption on CC transactions, because you don't normally do computations on credit card info."

Mr. Stuntz provides a more realistic scenario:

"Consider a tax preparer, or a finance service like mint.com: You give them your personal info, and they use algorithms to optimize your tax/finance strategy. But do you really want to upload your bank account numbers and balances to the web?

What if you could give them, instead, a key by which they could download homomorphically-encrypted data from your bank? They could perform their proprietary computations on your financial data and give you cipher text of the results which they themselves couldn't decrypt, but you could."

Step back

I first became aware of homomorphic encryption back in September 2009, when I encountered the Ph.D thesis of Craig Gentry. Mr. Gentry, later with IBM, was able to take what was proposed in a still earlier 1978 paper by Professor Ronald Rivest et al. and make it happen.

I'm a lightweight when it comes to intense cryptography theory. So, I was hesitant to wade through the paper. But, I noticed Mr. Gentry likes to explain things using analogy. Buoyed by that, I had a go.

Like a glove box

The analogy that caught my eye (you will see why later) was that of a jewelry store owner, Alice, who has an ingenious way to prevent theft:

"Alice, the owner of a jewelry store wants her employees to assemble precious materials into finished jewelry, but she is worried about theft. She addresses the problem by constructing glove boxes for which only she has the key."

Using the glove box, employees are able to fabricate the jewelry and only that. Alice controls the ingress of raw materials and the egress of the finished product using her key.

(My employer happens to manufacture glove boxes.)

The connection

Let's see if I understand the analogy:

  • Alice > end user
  • Precious materials > raw data
  • Key > network
  • Locked glove box > encryption
  • The workers > computational processes
  • Finished jewelry > results of manipulation

Keeping that in mind, let's look at how homomorphic encryption could be used to solve 2+3. The data is encrypted locally, 2 becomes 22 and 3 becoming 33. The encrypted numbers are sent to the server where the encrypted numbers are added together. The server then returns the encrypted answer of 55. It is then decrypted locally to reveal the final answer of 5.

On his blog site, Craig Stuntz offers another layman's explanation of homomorphic encryption, allowing me to better grasp the concept. He included the following diagram:

Mr. Stuntz adds:

"It just so happens that in this case the homomorphic concatenation (concatenating the two fragments of cipher text) is the same operation as the non-homomorphic concatenation (concatenating two fragments of plaintext). This is not always the case.

What is important is that we can perform some operation on the input cipher text which will produce new cipher text that, when decrypted, will produce output plain text corresponding to a desired operation on the input plain text."

Not quite that simple

It's not hard to see that there's a lot going on under the hood or glove box and I won't pretend to understand it. What's more, many brilliant people have tried over the past three decades to get this to work. All failed. Experts were starting to wonder if it was possible -- even Dr. Rivest.

A solution

I wasn't able to ask Mr. Gentry how he discovered the answer. But, Andy Greenberg of Forbes Magazine was. Here's the scoop on the problem and how Mr. Gentry overcame it:

"Gentry's fully homomorphic revelation came to him as he sat in a New York City cafe that summer. The encryption method that intrigued him allows a few multiplications or additions of encrypted data. But it suffers from an interesting handicap.

Every arithmetic step unavoidably introduces small amounts of error into the encrypted data. Performing just a dozen or so computations corrupts the data to the degree that it can no longer be accurately decrypted.

Gentry's insight was to double-encrypt the data in such a way that the errors could be removed, so to speak, in the dark.

By periodically unlocking the inner layer of encryption underneath an outer layer of scrambling, the cloud computer would clean up its messes as it went along, without ever seeing the secret data.

It took Gentry another 15 minutes to realize that he'd just solved an epic cryptographic problem."

Not ready for prime time

Like all good things, putting homomorphic encryption into play will take time. And, there are some steep obstacles to overcome, one being the intense computational requirements. Gentry estimates that adding homomorphic encryption to a simple search would increase the effort a trillion times.

Still, experts appear confident. Like the four-minute mile, once a barrier is broken, the flood gates tend to open presenting all sorts of possibilities. In fact, Mr. Gentry already has a new and improved version, but it's under wraps until he publishes.

It's a big deal

Others see the potential of homomorphic encryption. Recently, DARPA announced a 20-million-dollar research project to solve the cryptographic problems, already awarding the research company Galois five million dollars.

I also wanted to mention that Craig Gentry has been awarded the Association for Computing Machinery's (ACM) Grace Murray Hopper Award. Never heard of the award? Well, Steve Wozniak and Bob Metcalfe are fellow recipients. Both managed to make serious dents in the computing world.

Final thoughts

I'm having trouble deciding: Is homomorphic encryption really a game changer? Like this year's tornado season, it seems that time and conditions are ripe for some disruptive technology. Stay tuned.