An MIT Magic Trick: Computing On Encrypted Databases Without Ever Decrypting Them

[Eugen Leitl]

http://www.forbes.com/sites/andygreenberg/2011/12/19/an-mit-magic-trick-computing-on-encrypted-databases-without-ever-decrypting-them/

An MIT Magic Trick: Computing On Encrypted Databases Without Ever Decrypting
Them

CryptDB can perform the digital equivalent of pulling the desired file out of
a locked filing cabinet without ever unlocking it.

For the last three decades or so, the big problem in using encryption hasnbt
been whether strongly encrypted files can be cracked. The problem remains
that to actually do anything with encrypted databsearch it, sort it, or
perform computations with itbthat data must be decrypted and exposed to
prying eyes.

Now the Google- and Citigroup-funded work of three MIT scientists holds the
promise of solving that long-nagging issue in some of the computing worldbs
most common applications. CryptDB, a piece of database software the
researchers presented in a paper (PDF here) at the Symposium on Operating
System Principles in October, allows users to send queries to an encrypted
set of data and get almost any answer they need from it without ever
decrypting the stored information, a trick that keeps the info safe from
hackers, accidental loss and even snooping administrators. And while itbs not
the first system to offer that kind of magically flexible cryptography, it
may be the first practical one, taking a fraction of a second to produce an
answer where other systems that perform the same encrypted functions would
require thousands of years.

Cryptographers have long sought to implement a system they call bfully
homomorphic encryption,b in which a user can encrypt data into indecipherable
strings of numbers, do math with those strings, and then decrypt the results
to get the same answer he or she would have if the data hadnbt been encrypted
at all. Thatbs a useful trick if you need to perform operations on health
care or financial data in a situation like cloud computing, where the
computer (or the IT administrator) doing the calculations canbt always be
trusted to access the private numbers being crunched. IBM cryptographer Craig
Gentry compares the idea to bone of those boxes with the gloves that are used
to handle toxic chemicals,b as he once put it. bAll the manipulation happens
inside the box, and the chemicals are never exposed to the outside world.b

In fact, Gentry solved that problem of fully homomorphic encryption with a
brilliant new system in 2009. But his theoretical solution had a practical
problem: It multiplied the time to perform the calculation by around a
trillion.

CryptDB, on the other hand, manages to emulate fully homomorphic encryption
for most of the functions of the SQL databases used in many applications,
computing only with encrypted data and adding just 15% to 26% to those
applicationsb computing time.

The MIT researchersb approach was to avoid fancy new cryptography schemes,
and instead piece together existing ones that get the job done. The RSA
scheme, for instance, lets you multiply encrypted numbers, and another called
the Paillier scheme lets you add them. For the simpler task of looking for
matches in data, plenty of schemes allow you to compare encrypted information
and see whether the scrambled codes are equal, and thus determine if the
unencrypted data points were also the same.

bThe insight we had, the cool idea, is that SQL queries in a database are
composed of relatively few types of operations: equal to, less than, summing
up, sorting,b says MIT professor of software technology Nickolai Zeldovich.
bFor each operation, we were able to find an encryption scheme that is quite
efficient at computing on encrypted data.b

The cleverest part of CryptDB, however, is that itbs able to switch between
crypto systems on the fly depending on the operation. The data in the
database is encrypted in multiple layers of different encryption, what the
researchers call an bonionb of encryption. Every layer allows different kinds
of computation and has a different key. bYou just strip off the levels of the
onion until you reach the level that allows a certain operation,b says MIT
researcher Raluca Ada Popa.  The most secure schemes are used on the outside
of that onion and the least secure are used on the inside. CryptDB manages to
perform all its functions of a database without ever removing that last layer
of the onion, so that the data always remains secure.

CryptDB has its limits, the MIT researchers warnbno square roots, for one
example. And while the data is never completely decrypted, it does bleakb
information about the underlying data when enough outer layers of encryption
are removed, revealing attributes like which data points are equal to each
other. But in their paper they sampled operations from several real databases
like one used by a Web forum and another by a grade-calculating application,
and found that their encrypted system would allow the same calculations as an
unencrypted database in 99.5% of those operations, and that data the
researchers deemed bsensitiveb is never leaked in those test cases.

The limitations of CryptDB arenbt insignificant, says Butler Lampson, a
security-focused Microsoft Research fellow.  bIt might not be easy to get
customers to understand the subset of queries this can and canbt handle,b he
points out.

But Lampson still argues that CryptDB is remarkably practical compared to
other attempts at solving the problem of computing with encrypted data. bI
donbt think webll see anyone using Gentrybs solution in our lifetimes,b he
says. bBut itbs very likely webll actually see this applied in practice. I
donbt see any real barrier.b

At least two companies already seem interested: Google and Citigroup funded
the research, along with the National Science Foundation. The Pentagonbs
Defense Advanced Research Projects Agency (DARPA) has shown it wants in on
fully homomorphic cryptography, too. The agency is putting up $20 million for
anyone who can create a scheme that takes only 100,000 times as long as
unencrypted calculationsba tough task, compared to Craig Gentrybs system from
2009. But given that in many cases CryptDB performs 80,000 faster than
DARPAbs goal, the MIT researchers shouldnbt be surprised to see the military
come calling soon.

The full paper on CryptDB is available here.

http://people.csail.mit.edu/nickolai/papers/raluca-cryptdb.pdf