http://www.forbes.com/sites/andygreenberg/2011/12/19/an-mit-magic-trick-comp... 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 b fully 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 b one of those boxes with the gloves that are used to handle toxic chemicals,b as he once put it. b All 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. b 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,b says MIT professor of software technology Nickolai Zeldovich. b For 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 b onionb of encryption. Every layer allows different kinds of computation and has a different key. b You 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 b leakb 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 b sensitiveb 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. b I donbt think webll see anyone using Gentrybs solution in our lifetimes,b he says. b But 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