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.
What’s happening to members of Sony’s game network, or users of LastPass, also compromised, will become a distant memory. With homomorphic encryption in play, your credit-card number or any sensitive information for that matter is always encrypted, therefore useless to the bad guys.

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.