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 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 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 times 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.