Security optimize

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.

About

Information is my field...Writing is my passion...Coupling the two is my mission.

54 comments
masoodaM
masoodaM

can fully homomorphic encryption be used for privacy preserving association rule miningĀ 

Wunderbarb
Wunderbarb

This is an interesting area of exploration of cryptography. Unfortunately, it is not yet convenient enough to be widely used. Remember also that all the calculus are nor homomorphic algebraic functions. It will take ,many years before we will be able to trust such algo as mush as we trust AES or RSA for instance. Using the Sony snaffu to illustrate the advantage of homomorphic encryption seems not a good example to me. In any case, you must first properly encrypt your data to avoid that a hacker access them in the clear. Homomorphic encryption may allow you to avoid to make some calculation in the clear. This is useful in a model where the attacker may have access to the host during calculation. In the case of Sony (I suppose that you speak about the personal data leakage and not the signing private key leakage which is a totally other issue), the attacker accessed the data while stored in database and did not intercept them while being used. The data themselves were not properly protected. Homomorphic encryption would not solve this problem. here it was the access to the database that was not trusted. But you are right, if you do not trust the host that is making the processing, then homomorphic encryption may (one day) bring some solutions. For instance, in the domain of multimedia, being able to add a forensic watermark to an encrypted content without having to decrypt it is of interest. This would allow a secure tracing of data. By the way, it could be used for other forms of data.

tom.marsh
tom.marsh

Because security is just one of a myriad of problems inherent in the cloud. The other is "quality of service"--and here I'm not talking about the network concept of "QoS" but rather the quality of how it works. To "monetize" a service for the cloud there are a number of compromises that usually get made--some features may be disabled for legitimate security reasons, others may in fact be restricted as a means of increasing your bill. And then there's support... What's your SLA for tickets? Is it minutes, hours, or days? That's an important question to ask: You'd hate to be in mid-crisis over the weekend, call from health, and have the person who answer the phone say, "Okay, we've got your ticket logged... Talk to you on Monday!" And "unreliability" is a major part of the cloud story now... Several big-names have had significant failures in recent weeks, and almost all of the "public" cloud email services have lost customer data before. It's only a matter of time until the put somebody out of business.

bond.masuda
bond.masuda

so, i took quick glance at the thesis and realized that even with a math degree there were constructs discussed there that i'm not familiar with. so, even though i studied homomorphisms in my grad school days, i'll admit I don't understand the math and what it all implies. i'm sure one could read the referenced material and figure it out, but i'm not in the mood for intense math reading... that said, can't the problem of storing PII already be solved with the technology that is already widely available? for example (a very crude one): 1. card holder (CH) wants to subscribe to merchant (MC) services for next 3 months at $X per month. 2. CH generates a Payment Authorization (PA) token by doing something like: 2a - write a message "I, CH, authorize MC to charge me X amount once per month, for May, Jun, and July" 2b - generate a random key, the longer the better. combine this random key with PII to create encryption key. 2c - encrypt the above message with encryption key. 2d - send the random key to card Issuer (IS) marked good only for MC, payment of $X once per month for May, Jun, and July only. 3. send PA token to MC. MC can then use this with the payment gateway (PG) by proving to PG that MC is indeed who they claim to be. PG passes the payment authorization request to the IS and since the IS knows my PII and the random key, they can decrypt it and see that I authorize the payment. IS tells PG everything is good; go ahead. 4. at the end of the month, IS sends CH a statement/bill for the charge. If the PA token is stolen, it has the following properties: 1. it doesn't contain any PII 2. it's only valid for a limited time. (you can increase the random key length to make it harder to bruteforce so by the time a bruceforce succeeds, it's expired) 3. it's only usable to receive funds if you can prove you are MC to the PG 4. even if you decrypt the PA token after it has expired, the cleartext is worthless and the encryption key is just a random key that is no longer valid. no PII revealed. 5. PII is never transmitted at any step. It's already a shared secret between CH and IS and no one else needs to have it. of course, if you can MIM intercept the communication between CH and IS, and spoof your identity as MC to the PG, i suppose you could still steal $$$. or, ultimately, if you hack CH and gain their PII, the floodgates are wide open. But, at least in this scheme, CH's PII is never copied and disseminated to multiple parties. You can't hack a MC or PG to gain CH's PII. I didn't put a lot of thought into the above scheme, so i'm sure some experts can find a hole in it somewhere. Nonetheless, I think with more careful thought, the above scheme or something similar can be improved to plug any holes with currently available technology. my point is, i think with today's technology, there should be a way to design a system where PII information isn't getting disseminated everywhere and no MC should ever have to store such PII. therefore, even without homomorphic encryption, massive PII compromise should already have been a thing of the past. i don't think we're full utilizing the technology that is already available.

Michael Kassner
Michael Kassner

I asked Mr. Craig Stuntz if credit-card transactions were a bad example. He was kind enough to straighten me out. Here are his comments: "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 cyphertext of the results which they themselves couldn't decrypt, but you could."

loidab
loidab

"...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..." Regarding Lastpass, this point is moot. Data is manipulated, encrypted and decrypted locally. Therefore your sensitive data never reaches Lastpass servers in cleartext. I believe this is not a problem that homomorphic encryption tries to solve, and in fact was a very poorly chosen example. Regarding PSN, Playstation will eventually need to access the credit card information. So I don't see how the servers not having access to that information, which one assumes is critical for billing, is helpful in any way. Regards,

Zorched
Zorched

If you are unscrambling the inner wrapped data to be able to clean it, data that is encrypted, wouldn't you need the encryption key? So you've added an encryption wrapper around the encrypted data, but then you still require both keys (the original and layer you added), which rather makes the whole thing pointless, doesn't it? This whole process seems rather unnecessary unless you have hackers hanging probes off the main CPU bus or force dumping sections of memory, which shouldn't be possible outside of the owner process. Once data is in the machine being processed, the necessity for security is lessened (assuming it's enforced that non owner processes can't touch the data in memory). It's the ability to steal a file off a storage medium that enabled the Sony Hack, wasn't it? So, encrypt the data on the hard drive. Yes, it's cool and the process problems (most of them) got solved, but really how much manipulation can be done in the encrypted state? concatenate (add data), deletion (remove data), multiplication (not sure of the use here). If you need to change the data, or say, feed it to your e-mailer program you still have to decrypt it, right?

oldbaritone
oldbaritone

So what's the revolutionary development between homomorphic and other "encrypt the encrypted" technologies like 3DES, or sending PGP-encrypted data over SSL?? It sounds like a similar idea to me, encrypting encrypted data again, so that someone working with a decrypted data stream is still seeing encrypted data. What's new?

jsowell42
jsowell42

In my humble opinion, I can envision homomorphic encryption being applied via copper, fiber, cellular, or microwave channels or even locking mechanisms. The questions I have are: how will the key be stored? will the key be encrypted by some method? or plain text? who will have access to the key(s) and under what regulated conditiuons will these people have access to any availabe key(s)? how much more bloated is this encryption method going to cause software to become? what about bandwidth economy - is it going to congest transmissions? I sound like I am really harshing on the cool with all this, so allow me to clarify that I think this is a totally amazing hash! I am just trying to ask the questions

phyrefly.phyre
phyrefly.phyre

The only improvement I can see is that the crdit card number (for example) can be encrypted before it is sent to the cloud. But then the encrypted version of the number is a valid value to pass in, and so THAT in turn has to be protected too... If I'm missing the point, please explain?

seanferd
seanferd

Otherwise, I'd be wondering what the glove compartment in a car would have in the way of a solution for the jeweler. :D Very interesting concept, and kudos to Gentry for finding a workable method.

Michael Kassner
Michael Kassner

Game changer, disruptive technology, call it what you want. Homomorphic encryption is about to become a big deal.

apotheon
apotheon

The PSN fiasco is definitely not the greatest example of where some new technology like homomorphic encryption would solve the problem. The fact of the matter is that older technologies would have solved the problem as well. The reason there was a problem to begin with is that Sony's people didn't implement the most basic, simplistic, stupidly obvious security measures. If Sony wasn't able or willing to do even that, the game's already over.

apotheon
apotheon

Cloud-based computing needs redundancy for reliability, as does everything else. Anyone who thinks "Oh, I stuck all that in the cloud, so I don't have to worry about it any longer," is doing something wrong. This doesn't mean the "cloud" solution is bad; it means it has the same problem as everything else, in that any single point of failure means a failure can be catastrophic.

AnsuGisalas
AnsuGisalas

The cloud is great for some things. Any task that can be distributed, basically - provided security is good enough.

Michael Kassner
Michael Kassner

Just growing pains? Or show stoppers? Would you consider not providing security for data a show stopper? That was my thinking.

apotheon
apotheon

Simultaneous transactions can be kind of tricky to set up so that they run pretty much transparently for the end user, but if properly managed the result can be out-of-band validation and secure operations where, in general, the whole purpose of homomorphic encryption becomes unnecessary. The question is which of them provides the most convenient way to accomplish a given transaction without compromising security.

Michael Kassner
Michael Kassner

I took all sorts of math, albeit at least a century ago. Yet I had little clue as to what was taking place.

AnsuGisalas
AnsuGisalas

It's also good for keeping business secrets, letting road warriors or far-off business partners work on the data in the cloud, without fear of outsiders getting to sniff the data (barring screen grabbers).

apotheon
apotheon

Validation operations can be accomplished using homomorphic encryption without decrypting, because credit card validation is performed by way of mathematical operations. In addition, it seems likely that credit card transactions can be completed entirely using credit card data subject to homomorphic encryption without ever decrypting it, but only if every step of the process is using the same encryption technologies -- including the card processing entity at the far end of the process. That kind of buy-in from all parties for the same process is likely to be very difficult to achieve at this point, unfortunately.

Michael Kassner
Michael Kassner

Have you read Mr's Gentry's paper? It provides detailed information that I did not supply in this article. As for LastPass, your point is taken, Still, the master password (hashed or not) is stored on their servers and that appears to be a problem. FYI, I've been an avid user of LastPass and have written about it: http://www.techrepublic.com/blog/security/lastpass-is-it-the-password-manager-for-you/3291 As for credit-card information, you are using "present-day" methodology. I would wish for you to think "outside the box". I suspect that sensitive information will not need to be reverted to a format that is usable if stolen. Is that not the whole point of homomorphic encryption?

Michael Kassner
Michael Kassner

I am not by any means versed enough to answer most of them. I suggest you read Mr. Gentry's paper critically. I suspect most of your technical questions will be resolved. As for decrypting at the process location, that would then allow internal knowledge and possible illegal use of the private data. Not good. You also have to guarantee that bad guys do not have control of the process. As for the amount of manipulation, I got the impression that all of it is within reason. You mentioned email. Mr.Gentry specifically mentioned that homomorphic encryption would work for it. Please remember these are my best guesses. I think for better than that we will have to stay tuned.

Michael Kassner
Michael Kassner

All the examples you have mentioned need to be decrypted when they reach the process that is going to act on the data. Homomorphic-encrypted data does not have to be decrypted. That is huge. All the recent data breaches would have only netted the bad guys encrypted data.

Michael Kassner
Michael Kassner

I am sorry, but I do not have the answers. This is cutting-edge information that I wanted to get to you the readers as soon as I learned about it. I'm guessing researchers are still theorizing about questions similar to yours.

pgit
pgit

The results of whatever calculation on the cypher only make sense to the one who encrypted/transmitted it in the first place. You could intercept the cypher and put it through a system (calculation) and get a result, but that result would be useless to you without the original key. It does no good to even bother intercepting any traffic encrypted this way. Remember we're talking 'cloud' here, the end user's device is a crucial part of the entire transaction. The key is never transmitted. A cracker would need to find a way to get your iphone, android or what have you to cough up the key it's using to encrypt, in real time, as this key itself is probably changing constantly. This does look like a breakthrough. That secondary encryption is exactly that kind of stroke of genius that keeps my faith in the human race alive. As I understand it, in the midst of things it will randomly decrypt the function and have a look at it. Say at this point it sees "2 X 3 = 8." It compares the current "answer" with the actual answer derived from the components, replaces the wrong answer with a correct one, re-encrypts the whole thing and inputs this back into the original stream. Of course the math in that example is "ludicrous simplified" as Mike Tyson might say. But I think that is the general gist. The unencrypted 'snapshot' the system looks at is useless to anyone that could steal it, it would be like seeing a fleck of paint... ok, is this paint on a car? A boat? A tricycle? Is it a car traveling from Cleveland to Chicago? At night?? Is it paint on a toy on a ship in transit from Taiwan to Buenos Ares??!? The reality is impossible to glean from any possibilities presented in this mid-stream clear text error check, as the overlying system remains encrypted and can only be unlocked in toto by the original key. I love having to think about stuff like this. :)

Michael Kassner
Michael Kassner

I first want to mention that this is bleeding-edge research right now. So what becomes of it is any one's guess. The potential is boundless. I am not privy to what the experts have in mind, but I could easily see the encrypted credit-card number only working for that particular application and only that one instance.

Michael Kassner
Michael Kassner

I work with glove boxes (also called isolators). So, thinking of car parts, I don't. It was luck and I that wanted to show how they worked.

bboyd
bboyd

To paraphrase one of the axioms used to understand catastrophic failure. If you strengthen steel to keep it from bending when mishandled, you may cause it to snap when hit with a stronger force. Making a simple problem like a bent nail into a dangerous problem like a flying shard of metal in the eye. What is our metaphorical eye protection? Does this system inject a wholesale failure in a problem that should just be modular encryption. The worst failure of the system would be if by decrypting one item the whole key mechanism is breached.

eulerianpath
eulerianpath

A homomorphism is a function between two (algebraic) structures that preserves the algebraic structure. e.g.: Consider the integers, Z, (with the operation of addition and multiplication) and the integers mod 24, Z_24, (i.e. a military-time clock). We have a function f: Z -> Z_24 which sends the integer 1 to the integer 1 mod 24. This function is a homomorphism because if you a) add/multiply two integers together and then apply the function you would get the same result if you were to b) first apply the function to the two integers and then add/multiply them together. An encryption is a function from two sets, in particular from the integers to itself. It is a homomorphic encryption if the function is a homomorphism--in other words if you can do the addition/multiplication before OR after the function is applied, and you get the same result either way.

Michael Kassner
Michael Kassner

As I tried to point out in the title, this could really help cloud computing.

AnsuGisalas
AnsuGisalas

Over here the EU can just demand it, and the banks and businesses and providers will just have to figure out a common standard.

loidab
loidab

Hi, Thank you for addressing my questions! In Lastpass there's a problem because the encryption key can be brute-forced. An hypothetical encryption key used in homomorphic encryption would also be vulnerable. My point is: the security lies in the strength of the key. Using symmetric encryption (AES-256 in the Lastpass case) or using other type of encryption is vulnerable, in this scenario, to similar attacks. I admit that I'm indeed thinking inside the box regarding credit card info :) There's something that still hasn't clicked on how can a party A use some information with other party B and somehow only use it when it "should". It seems a little bit like the problem that DRM tries to solve. Please note that the if the confidential info used in the PSN had been properly encrypted and the attackers had not gained access to the keys, there shouldn't be any issue. Right? :)

AnsuGisalas
AnsuGisalas

it's like a database, where you can pull what you need right out, or rather, work with it as-is. It stays encrypted, even when being worked on? Huge indeed.

Michael Kassner
Michael Kassner

Your mention of "keeping the faith" was my first emotion (if it can be called that) when I obtained my limited grasp of what he accomplished. Wonder what kind of coffee it was.

CharlieSpencer
CharlieSpencer

And we still don't have a Vulcan emoticon, dang it.

seanferd
seanferd

and probably several other designations. I'd never heard glovebox before, which is odd, given the prevalence of the term. The law of unintended education! Thanks.

Michael Kassner
Michael Kassner

If the process acts upon the unencrypted and encrypted data in similar fashion and the data is meaningless to everyone except the one holding the key. What wrong?

Michael Kassner
Michael Kassner

That was the explanation I needed. Simple, yet elegant. Kind regards.

Michael Kassner
Michael Kassner

What if the LastPass master password did not need to be decrypted? Would that not make a difference, if it was stolen? I share your sentiment and have been struggling with how this all might work out. I wish more information was available. But, there's not, as this technology is just getting started. I think the "big picture thing" to take away is there will not be a repository of passwords and keys. If the process is able to act on encrypted data, the bad guys will have to glean those individually.

AnsuGisalas
AnsuGisalas

They just have really boring women's fashion! >:| Compare, Hemul Now it looks like, with the Most Honored Blogger's consent, this part of the thread has become ripe for my split-second misinterpretation of "homomorphic encryption", asinine as it was: [b]Encryption which [i]looks gay [/i]... [/b]

JCitizen
JCitizen

hopefully the cost of the nuclear waste treatment will be less than the cost of trying to store it.

Michael Kassner
Michael Kassner

I hope. The debate now has to focus on the definition of wasted space and whether the total mass of electrons required to display this is sufficient to meet the agreed upon definition's requirements.

Michael Kassner
Michael Kassner

As I get older, I realize more and more complexity is not a good thing.

bboyd
bboyd

At first glance its seems to fill several roles very well. My thought is that like a dam, stopping floods, generating power, providing recreation, its failure can kill many more people than a simple river flood in one event. I'm not a crypto specialist so my sights aren't on that topic. As for cloud computing being saved by it. Happy that a step in the right direction is now available.