## Encrypted Cloud Computing

June 14, 2010

The Technology Review has an interesting report on a new cryptographic technique that might, in the future, allow computing to be done “in the cloud” using encrypted data, without the data ever having to be present in clear text.   The technique is called “fully homomorphic encryption”, and its feasibility was proved in a PhD thesis by an IBM researcher.

In 2009 Craig Gentry of IBM published a cryptographic proof that was that rare thing: a true breakthrough. He showed that it was possible to add and multiply encrypted data to produce a result that–when decrypted–reveals the result of performing the same operations on the original, unencrypted data.

In other words, if we have two numbers, α and β, and suitable encryption and decryption functions E(x) and D(x), respectively, and if

α + β = S

Then, if

E(α) + E(β) = S*

it will be true that

D(S*) = S

So we are able to add the two encrypted values to get a sum that, when decrypted, is the sum of the original (unencrypted) numbers.  A similar trick also works for multiplication.  (For the mathematically literate and adventurous, Mr. Gentry’s original thesis can be downloaded here [PDF, 209 pages].)

Two European researchers, Nigel Smart, of Bristol University in the UK, and Frederik Vercauteren, of Katholieke Universiteit Leuven, in Belgium, have recast Gentry’s framework in a somewhat simpler form, using integers and polynomials, rather than vectors and matrices.

The original scheme’s reliance on large matrices and vectors made it impractical because of the complexity of working with every element of the matrices at each step, and the fact that their complexity grows significantly with each extra operation on the data. Smart and Vercauteren’s rewrite of the scheme sidesteps that enough to allow testing of actual implementations of Gentry’s idea on a desktop computer.

Although the test implementation is still somewhat limited (to about 30 consecutive arithmetic operations), it does give a wider group a chance to experiment with the technique, and, hopefully, improve it.  Gentry and an IBM colleague, Shai Helevi, have been experimenting with another variant of the technique.

At this point, no one can really say when or if a practical implementation of this approach will be developed; but the interest in it is high, because it potentially allows even very sensitive information to be processed in the cloud.  It has the potential to change the way we think about some aspects of information security.