[FoRK] [info] An MIT Magic Trick: Computing On Encrypted Databases Without Ever Decrypting Them

Eugen Leitl eugen at leitl.org
Tue Dec 20 05:09:00 PST 2011


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

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 hasn’t
been whether strongly encrypted files can be cracked. The problem remains
that to actually do anything with encrypted data—search it, sort it, or
perform computations with it–that 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 world’s
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 it’s 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 “fully
homomorphic encryption,” 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 hadn’t been encrypted
at all. That’s 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 can’t always be
trusted to access the private numbers being crunched. IBM cryptographer Craig
Gentry compares the idea to “one of those boxes with the gloves that are used
to handle toxic chemicals,” as he once put it. “All the manipulation happens
inside the box, and the chemicals are never exposed to the outside world.”

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

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
applications’ computing time.

The MIT researchers’ 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.

“The 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,” says MIT professor of software technology Nickolai Zeldovich.
“For each operation, we were able to find an encryption scheme that is quite
efficient at computing on encrypted data.”

The cleverest part of CryptDB, however, is that it’s 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 “onion” of encryption. Every layer allows different kinds
of computation and has a different key. “You just strip off the levels of the
onion until you reach the level that allows a certain operation,” 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 warn–no square roots, for one
example. And while the data is never completely decrypted, it does “leak”
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 “sensitive” is never leaked in those test cases.

The limitations of CryptDB aren’t insignificant, says Butler Lampson, a
security-focused Microsoft Research fellow.  ”It might not be easy to get
customers to understand the subset of queries this can and can’t handle,” 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. “I
don’t think we’ll see anyone using Gentry’s solution in our lifetimes,” he
says. “But it’s very likely we’ll actually see this applied in practice. I
don’t see any real barrier.”

At least two companies already seem interested: Google and Citigroup funded
the research, along with the National Science Foundation. The Pentagon’s
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 calculations–a tough task, compared to Craig Gentry’s system from
2009. But given that in many cases CryptDB performs 80,000 faster than
DARPA’s goal, the MIT researchers shouldn’t be surprised to see the military
come calling soon.

The full paper on CryptDB is available here.

info mailing list
info at postbiota.org

More information about the FoRK mailing list