IBM takes a big new step in cryptography: practical homomorphic encryption

IBM just released an open source software package called HELib.

The HE stands for homomorphic encryption.

Although it doesn't sound terribly sexy or impressive, HELib is actually an interesting and important milestone in cryptography.

HE is also a surprisingly relevant topic right now, with our ever-increasing attraction to cloud computing.

Bear with me, and I'll try to explain.

Imagine that I am your cloud provider, and I keep databases online for you.

Imagine also that I am a security-conscious vendor, so I keep all your data encrypted, both when I serve it up to you, and when I save it to disk.

That's about as good as it gets these days from a cloud security perspective.

→ It doesn't matter whether I'm a pure-play over-the-internet cloud provider, or just the manager of the server farm team in your own IT department. The situations are similar, though they may differ in degree: I've got your data, and you have no alternative but to trust me to do the right thing with it.

Now imagine that you want me to search through your data, for example to see how many ACME-WIDGETS were bought by customers called DUCKLIN in the last year.

Traditionally, the process would go something like this:

• You encrypt the search terms and upload them to me.
• I decrypt the search terms so I know what to look for.
• I decrypt your data (perhaps only record by record, not all at once - that's a detail that doesn't matter here) so I have somewhere to search.
• I perform the search using the decrypted data.
• I encrypt the search results, if there are any, and return them to you.

Additionally, you hope that:

• I get rid of all remnants, on disk and in memory, of both the search terms and the decrypted data once the search is complete.
• I don't take advantage of you, since I'm decrypting your data for this search, to sneak in other searches at the same time, whether for my own benefit, or for my government, or for one of your competitors.

There's a lot that could go wrong - for you, at any rate.

The homomorphic difference

Imagine, however, if I could simply take your encrypted search terms, leave them encrypted, search for them directly in the still-encrypted database, and get the same results.

If I can perform calulations directly on your encrypted data, yet get the same results that you get from the unencrypted data, we both win enormously from a security and privacy point of view.

You don't need to give me any decryption keys at all, so you no longer have to trust me not to lose, steal or sell your data. (You still have to trust me to tell you the truth about any results I work out for you, but that is a completely different issue.)

And I no longer need your decryption keys, so I can't lose or abuse your data even if I wanted to.

That's the promise of homomorphic encryption, which we mentioned at the start.

Until 2009, no-one was sure whether homomorphic encryption was even possible.

Then, a Stanford student and IBM researcher called Craig Gentry showed that it could be done, in a PhD thesis entitled simply, "A fully homomorphic encryption scheme."

We weren't home and dry yet, though.

Gentry had what amounted to an existence proof, showing that homomorphic encryption could no longer be considered impossible, but he didn't have a practicable real-world implementation of the concept.

At the time, back in July 2009, well-known cryptographic personality Bruce Schneier praised Gentry's efforts, but pointed out that:

Gentry's scheme is completely impractical... Gentry estimates that performing a Google search with encrypted keywords - a perfectly reasonable simple application of this algorithm - would increase the amount of computing time by about a trillion.

Well, we're now a few steps further forwards, with IBM's release of the abovementioned software package HELib:

HElib is a software library that implements homomorphic encryption (HE). Currently available is an implementation of the Brakerski-Gentry-Vaikuntanathan (BGV) scheme, along with many optimizations to make homomorphic evaluation runs faster, focusing mostly on effective use of the Smart-Vercauteren ciphertext packing techniques and the Gentry-Halevi-Smart optimizations.

With a package description like that, it's obvious that consumer-facing homomorphic encryption tools aren't going to be a click away at the Play Store or the App Store for a while yet.

On the other hand, four years ago we didn't even know whether it would be possible to have homomorphic encryption at all.

So, watch this space! 

By: Paul Ducklin
Source: http://nakedsecurity.sophos.com/2013/05/05/ibm-takes-big-new-step-in-cryptography/