Security Scheme Could Protect Sensitive Data During Cloud Computation
Balancing Security and Flexibility
MIT researchers began theorizing about homomorphic encryption in the 1970s. But designing the mathematical structure needed to securely embed a message in a manner flexible enough to enable computation proved to be enormously challenging. The first homomorphic encryption scheme wasn’t designed until 2009.
“These two requirements are very much in tension. On the one hand, we need security, but on the other hand, we need this flexibility in the homomorphism. We have very few mathematical pathways to get there,” says Henzinger.
Essentially, homomorphic schemes add noise to a message to encrypt it. As algorithms and machine-learning models perform operations on that encrypted message, the noise inevitably grows. If one computes for too long, the noise can eventually overshadow the message.
“If you run a deep neural network on these encrypted data, for instance, by the time you get to the end of the computation, the noise might be a billion times larger than the message and you can’t actually figure out what the message says,” Corrigan-Gibbs explains.
There are two main ways to get around this problem. A user could keep operations to a minimum, but this restricts how the encrypted data can be used. On the other hand, a user could add extra steps to reduce noise, but these techniques require a massive amount of additional computation.
Somewhat homomorphic encryption seeks to meet users somewhere in the middle. They can use the technique to perform secure operations on encrypted data using a specific class of functions that keep the noise from growing out of hand.
These functions, known as bounded polynomials, are designed to prevent excessively complex operations. For instance, the functions allow many additions, but only a few multiplications on encrypted data to avoid generating too much extra noise.
Greater Than the Sum of Their Parts
The researchers built their scheme by combining two simple cryptographic tools. They started with a linear homomorphic encryption scheme, which can only perform additions on encrypted data, and added one theoretical assumption to it.
This cryptographic assumption “lifts” the linear scheme into a somewhat homomorphic one that can operate with a broader class of more complex functions.
“On its own, this assumption doesn’t give us much. But when we put them together, we get something much more powerful. Now, we can do additions and some bounded number of multiplications,” Henzinger says.
The process for performing homomorphic encryptions is quite simple. The researchers’ scheme encrypts each piece of data into a matrix in a way that the matrix provably hides the underlying data. Then, to perform additions or multiplications on those encrypted data, one only needs to add or multiply the corresponding matrices.
The researchers used mathematical proofs to show that their theoretical encryption scheme provides guaranteed security when operations are limited to this class of bounded polynomial functions.
Now that they have developed this theoretical approach, one next step will be making it practical for real-world applications. For that, they will need to make the encryption scheme fast enough to run certain types of computations on modern hardware.
“We haven’t spent 10 years trying to optimize this scheme yet, so we don’t know how efficient it could get,” Henzinger says.
In addition, the researchers hope to expand their technique to allow more complex operations, perhaps moving closer to developing a new approach for fully homomorphic encryption.
“The exciting thing for us is that, when we put these two simple things together, something different happened that we didn’t expect. It gives us hope. What else can we do now? If we add something else, maybe we can do something even more exciting,” Corrigan-Gibbs says.
Adam Zewe is a writer at Massachusetts Institute of Technology. This story is reprinted with permission of MIT News.
