No Need for Decryption

Is it possible to perform operations on encrypted data, while keeping it secure from all prying eyes (or circuits), even if that data is stored remotely, in the "cloud?" Will our end result still be encrypted, and when we decode it with our private decryption key, will our result be correct? To put it another way, could we allow sensitive data - say private medical information - to be monitored on-line and feel completely secure in the knowledge that no one can access it without our express permission? Can we use a cloud service to store our encrypted data and perform a search on that data without allowing the servers to "see" our search?

Welcome to the world of fully homomorphic encryption. The concept was first proposed in 1978 - long before the advent of remote computing services - by Rivest, Adelman and Dertouzos. (Rivest and Adelman, together with the Weizmann Institute's Prof. Adi Shamir, invented the RSA scheme used for almost all computer encryption today.) Since then, various researchers have come up with "partly homomorphic" methods, but none of them enabled full homomorphism. Only in 2009 was a fully homomorphic method demonstrated, by Craig Gentry at Stanford. That method, though proof of concept, was much too heavy and slow to be of any practical use.

Gentry published his method as his Ph.D. thesis. But it could be the doctoral work of another recent graduate - Dr. Zvika Brakerski from the Weizmann Institute (a student of Prof. Shafi Goldwasser) - that ultimately enables fully homomorphic encryption to become reality. Brakerski worked with Dr. Vinod Vaikuntanathan, a former student of Goldwasser's at MIT, who was at Microsoft Research at the time and is currently a professor at the University of Toronto.

In a nutshell: Gentry made some assumptions about the complexity of the math needed to achieve fully homomorphic encryption, and then used "a bit of a hack" (his words) to make it all work. Brakerski and Vaikuntanathan managed to change some of those assumptions (to "weaker" - more plausible and widely accepted - assumptions), simplifying the math and even eliminating the need for some of the hacks. The result, they say, is a method that is hundreds or even thousands of times faster than the original, but still fully homomorphic.

Brakerski, now doing postdoctoral research at Stanford, is continuing to research the math involved in fully homomorphic encryption. In the meantime, software engineers are already applying his insights to the future of data security.

Shafi Goldwasser.jpg

Prof. Shafi Goldwasser and Dr. Zvika Brakerski

Also today at the Weizmann Institute:
White blood cells that reach into the blood vessel lining looking for "exit signs" and the closest supernova observation in the past 25 years yields new insights into how stars explode.

Categories

More like this

Technorati Tags: cryptography, public-key, encryption, RSA, asymmetric encryption The most successful public key cryptosystem in use today is RSA - named for its inventors Rivest, Shamir, and Adleman. I first learned about RSA in grad school from one of my professors, Errol Lloyd, who was one of…
Ok, away from politics, and back to the good stuff. When I left off talking about encryption, we were href="http://scienceblogs.com/goodmath/2008/12/public_key_cryptography_using.php">looking at RSA, as an example of an asymmetric encryption system. Since it's been a while, I'll start off…
Prof. Shafi Goldwasser, who is at both the Weizmann Institute and MIT, will receive the 2012 A.M. Turing Award, together with Prof. Silvio Micali of MIT. Goldwasser is only the third woman to receive the Award since its inception in 1966, and she is the third faculty member of the Weizmann…
The starting point talking about encryption is to understand what the point of it is; what it's supposed to do, what problems it's supposed to avoid. Encryption is fundamentally about communication: you've got two parties who want to communicate, but don't want anyone else to be able to listen in…