Communications of the ACM
Cloud Computing Spurs New Encryption Solutions
Last month’s announcement that University of Washington researchers created an encryption scheme called Vanish caught the eye of many for its elegant simplicity, but two more arcane developments—presented at the Massachusetts Institute of Technology’s recent Crypto in the Clouds Workshop on the security challenges of cloud computing—promise more fundamental changes in applied cryptography.
The first is a solution to one of the oldest problems in cryptography, called fully homomorphic encryption. The challenge, not limited to cloud computing, has been to encrypt data in such a way that users can perform operations on it without decryption. Craig Gentry, the research scientist at IBM’s Watson Research Center who cracked the problem, likens the situation to a jewelry-store owner trying to ensure her underlings can assemble finished products without absconding with the precious raw materials. Past attempts at this kind of encryption haven’t been fully homomorphic because they handled addition but not multiplication, whereas Gentry’s solution handles both operations.
His algorithm achieves this through bootstrapping from a partly homomorphic system; Gentry starts with something akin to the jewelry store owner locking the jewels along with the jewelers’ hands inside a box and keeping the key. But this initial setup works for only a while before a growing error makes decryption impossible; so before that happens, Gentry embeds the whole setup inside another box with another key—and so on in recursive fashion until the system becomes fully homomorphic.
This algorithm could be useful for spam-filtering encrypted emails, Gentry says, but on large data sets it’s too slow to be practical. For example, responding to an encrypted Google search of all Web pages would be a trillion times slower than responding to the same query sent in the clear, says Gentry, who is hopeful that he can make the algorithm more efficient. (For more details about Gentry’s solution, visit http://domino.research.ibm.com/comm/research_projects.nsf/pages/security.homoenc.html.)
The flip side of homomorphic encryption is another development presented at the Crypto in the Clouds Workshop: functional encryption. In homomorphic encryption the input and the output remain encrypted to everyone but the owner of the private key, but with functional encryption, the program can send decrypted output to others meeting certain conditions. For example, if a city outsources its email and other data to Google, functional encryption can enable only users who are part of, say, the police department, to view some of the data, explains Brent Waters, an assistant professor of computer science at the University of Texas at Austin. In fact, Waters and his colleagues have created a system that controls access based on any Boolean formula (such as, to use a simple example, enabling decryption for a police officer who is working undercover).
Even so, Waters says he and his colleagues are still a good deal away from their ultimate goal: functional encryption for any function. “If you could do this you could virtually integrate any type of program into the decryption algorithm,” he says. Using a facial-recognition program, for example, functional encryption could enable group photos to be stored in a way that only a user who’s in the photo can view it.
Marina Krakovsky (marinakrakovsky.com ) is a writer in the San Francisco Bay Area.
No entries found