Metrosexual/Bi-Curious Cryptography article

[ewmayer]

Brian Hayes has an interesting piece about this in his latest American Scientist computing-science column:

Alice and Bob in Cipherspace: A new form of encryption allows you to compute with data you cannot read

Alice hands bob a locked suitcase and asks him to count the money inside. “Sure,” Bob says. “Give me the key.” Alice shakes her head; she has known Bob for many years, but she’s just not a trusting person. Bob lifts the suitcase to judge its weight, rocks it back and forth and listens as the contents shift inside; but all this reveals very little. “It can’t be done,” he says. “I can’t count what I can’t see.”

Alice and Bob, fondly known as the first couple of cryptography, are really more interested in computational suitcases than physical ones. Suppose Alice gives Bob a securely encrypted computer file and asks him to sum a list of numbers she has put inside. Without the decryption key, this task also seems impossible. The encrypted file is just as opaque and impenetrable as the locked suitcase. “Can’t be done,” Bob concludes again.

But Bob is wrong. Because Alice has chosen a very special encryption scheme, Bob can carry out her request. He can compute with data he can’t inspect. The numbers in the file remain encrypted at all times, so Bob cannot learn anything about them. Nevertheless, he can run computer programs on the encrypted data, performing operations such as summation. The output of the programs is also encrypted; Bob can’t read it. But when he gives the results back to Alice, she can extract the answer with her decryption key.

The technique that makes this magic trick possible is called fully homomorphic encryption, or FHE. It’s not exactly a new idea, but for many years it was viewed as a fantasy that would never come true. That changed in 2009, with a breakthrough discovery by Craig Gentry, who was then a graduate student at Stanford University. (He is now at IBM Research.) Since then, further refinements and more new ideas have been coming at a rapid pace.

Homomorphic encryption is not quite ready for everyday use. The methods have been shown to work in principle, but they still impose a heavy penalty of inefficiency. If the system can be made more practical, however, there are applications ready and waiting for it. Many organizations are eager to outsource computation: Instead of maintaining their own hardware and software, they would like to run programs on servers “in the cloud,” a phrase meant to suggest that physical location is unimportant. But letting sensitive data float around in the cloud raises concerns about security and privacy. Practical homomorphic encryption would address those worries, protecting the data against eavesdroppers and intruders and even hiding it from the operators of the cloud service.

So this promises - if it can be made efficient enough to allow for bulk en-and-decryption (which is a highly nontrivial 'if') - to make cloud computing safe, which would be a very big deal.

[Jeff Gilchrist]

Very interesting, thanks for posting.

[retina]

Mathematically speaking this is a nice advancement. But practically speaking what is so enticing about cloud computing? Even if this can be made more efficient the user would still need a local computer available to encrypt the input before sending and later decrypt the output after receiving. So why not just run it natively and forget about all the extra steps required to get someone else to compute it?

[Puzzle-Peter]

Originally Posted by retina

Mathematically speaking this is a nice advancement. But practically speaking what is so enticing about cloud computing? Even if this can be made more efficient the user would still need a local computer available to encrypt the input before sending and later decrypt the output after receiving. So why not just run it natively and forget about all the extra steps required to get someone else to compute it?

I think it's not about avoiding computers in general, but the costly and complicated systems. For the FEM and CFD stuff I'm doing one high end PC is enough to do all the pre- and postprocessing. But the computation itself requires days of runtime on dozens or even hundreds of cores on a cluster designed to run that kind of stuff. The workplace machine I'd need anyway for office work, just not as powerful. But that's not much of a difference regarding cost and administration. Getting rid of the clusters and everything that's needed to run them might sound enticing to the guys in the controlling department though.

[cheesehead]

Originally Posted by ewmayer

So this promises - if it can be made efficient enough to allow for bulk en-and-decryption (which is a highly nontrivial 'if') - to make cloud computing safe, which would be a very big deal.

The efficiency consideration reminds me of an encryption method I encountered in the late 1980s.

I was working for a company that sold electronic financial transaction software and services. One day I was asked to analyze the feasibility of incorporating an encryption method that enabled Alice to compute one category of keys used in communication with Bob, without having those keys actually transmitted between Alice and Bob, by substituting a special sequence of sixteen en-/decryptions operating on data that Alice (& Bob) already had. Sounds wacky, but though I forget the details, it wasn't just some method of hiding the key among the other data or using other data as a pseudorandom number generator's seed.

The analysis boiled down to determining how many instruction cycles the extra sixteen-layer 'cryption sequence required on an IBM mainframe and how that would affect transaction processing time.