A hospital that wants to use a cloud computing service to perform artificial intelligence data analysis on sensitive patient records needs a guarantee those data will remain private during computation. Homomorphic encryption is a special type of security scheme that can provide this assurance.
The technique encrypts data in a way that anyone can perform computations without decrypting the data, preventing others from learning anything about underlying patient records. However, there are only a few ways to achieve homomorphic encryption, and they are so computationally intensive that it is often infeasible to deploy them in the real world.
MIT researchers have developed a new theoretical approach to building homomorphic encryption schemes that is simple and relies on computationally lightweight cryptographic tools. Their technique combines two tools so they become more powerful than either would be on its own. The researchers leverage this to construct a “somewhat homomorphic” encryption scheme—that is, it enables users to perform a limited number of operations on encrypted data without decrypting it, as opposed to fully homomorphic encryption that can allow more complex computations.
This somewhat homomorphic technique can capture many applications, such as private database lookups and private statistical analysis.
While this scheme is still theoretical, and much work remains before it could be used in practice, its simpler mathematical structure could make it efficient enough to protect user data in a wider range of real-world scenarios.
“The dream is that you type your ChatGPT prompt, encrypt it, send the encrypted message to ChatGPT, and then it can produce outputs for you without ever seeing what you are asking it,” says Henry Corrigan-Gibbs, the Douglas Ross Career Development Professor of Software Technology in the MIT Department of Electrical Engineering and Computer Science (EECS) and a co-author of a paper on this security scheme.
“We are a long way from getting there, in part because these schemes are so inefficient. In this work, we wanted to try to build homomorphic encryption schemes that don’t use the standard tools, since different approaches can often lead to more efficient, more practical constructions.”
His co-authors include Alexandra Henzinger, an EECS graduate student; Yael Kalai, an Ellen Swallow Richards (1873) Professor and professor of EECS; and Vinod Vaikuntanathan, the Ford Professor of Engineering and a principal investigator in the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). The research will be presented at the International Conference on the Theory and Applications of Cryptographic Techniques.
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.
More information:
Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN, eprint.iacr.org/2024/1760
Provided by
Massachusetts Institute of Technology
This story is republished courtesy of MIT News (web.mit.edu/newsoffice/), a popular site that covers news about MIT research, innovation and teaching.
Citation:
Researchers develop innovative method for secure operations on encrypted data without decryption (2025, March 13)
