The Quest For the “Holy Grail of Cryptography”

Rearranging the Contents of a Locked Box

Security and openness seem to be inherently at odds with one another. For companies and institutions with sensitive data, keeping data secure while ensuring it remains useful is a problem with no clear solution. If they hold data too close to the chest, it’ll be harder to discover trends or solve problems. But if they’re too open with it, they risk security breaches that could reveal trade secrets or open them to lawsuits.

What if we lived in a world where we could share our data openly, without worrying about security? 

Enter fully homomorphic encryption (FHE), a technology that allows people to perform operations and analyses on encrypted data without decryption — like rearranging the contents of a locked box without ever having to open it.

One of the limitations of standard encryption is that once data is encrypted, it can be moved or stored, but not analyzed — that requires decryption. This problem has led, again and again, to data breaches at companies that hundreds of millions of people trust with their private information — such as Yahoo, LinkedIn, Facebook and the background check company National Public Data.

FHE has the potential to virtually eliminate data hacks. But first, it needs to pick up speed. Today, FHE operations, or computations performed on encrypted data, are about a thousand to a million times slower than plain text operations — standard computations on data that’s unencrypted and readable.

To put that in context: Most basic computations would require FHE to be a hundred times faster than it is now. For real-time applications, which perform operations on encrypted data and therefore take extra time and compute power, FHE would need to increase its speed by a magnitude of ten thousand.

In order to get it working fast enough for day-to-day use, FHE requires special ingredients: mathematical ingenuity to find algorithms that are both complex and efficient, engineering prowess to create hardware accelerators, and — the crucial link — the ability to integrate with existing software.

But if it can be perfected, FHE stands to do the seemingly impossible: allow privacy and transparency to coexist.

Solving the Unsolvable

It was five years into his work in cryptography that Gentry’s quest truly began. 

The final step was figuring out how to actually fit a ciphertext into an FHE scheme, a process called “squashing the decryption circuit,” which Gentry compares to pushing down all your clothes to fit them into a suitcase.

He’d done it. Gentry had proved FHE was possible. But he still wasn’t satisfied.

Most mathematical breakthroughs turn out to be flawed, he says. So he prefers a cautious mentality. “[You think,] I've made this big breakthrough. I won't touch it tonight,” he says. “So I'll be happy and think that I've done it.” But usually, he says, when you wake up in the morning, you realize there’s a problem with that breakthrough. Sometimes the problem is fatal. Sometimes it leads to new directions.

So far, though, Gentry’s breakthrough has proven true, and it’s had massive implications not only for his own career but the future of FHE. His thesis won the Best Dissertation Award from the Association for Computing Machinery, and just five years after it was published, Gentry received a Genius Grant from the MacArthur Foundation for his work. (Strangely, he’s not even sure how the MacArthur Foundation found out about him, he says, “but it’s nice to be honored in that way.”)

But even though Gentry had shown that FHE was more than theoretical, it still had a long way to go before it was truly usable. “It’s not like we were off to the races doing cases immediately,” he says, explaining that FHE’s efficiency still needs to radically improve.

And so Gentry took off on the next leg of his journey. He’d proven that the holy grail existed, and not just in theory. Now, he had to find it in reality.

That was 2009. Since then, Gentry’s quest has led him to make further contributions to FHE that have dramatically increased its speed. Today, as the chief scientist of algorithms at intelligent computing company Cornami, Inc., he hopes to use a combination of well engineered hardware accelerators and algorithmic techniques to get it over the finish line.

He’s not the only one. As word of FHE’s potential has spread over the years, a number of cottage industry startups have emerged who are also pursuing the technology, creating a race to see who will reach the grail first.

Black Magic

One of those startups: CipherSonic Labs, a company that aims to use FHE to make sharing data on the cloud secure.

Rashmi Agrawal, founder and chief technology officer of CipherSonic, also started working on FHE during her Ph.D. thesis, wanting to tackle FHE’s efficiency conundrum for herself. “I kind of like picking up the problems nobody would want to pick up,” she says.

Raised in a family of engineers, Agrawal felt pressure from her family to become one, too, even though her passion has always been for healthcare. She realized she could still have an impact in the medical field as an engineer, though, if she worked on technology that could be useful in medicine. FHE, with its wide-ranging applicability, seemed a perfect opportunity.

When she started looking into FHE in 2019, nobody quite understood why it was still so inefficient. There were “hardly four papers” investigating the problem, she says. “There was not much work done on optimizing the algorithms to meet the performance.”

The math was complex, and it was especially hard to understand because each paper had “different symbols for the same thing.” There’d been some work on implementing FHE on general purpose CPUs, and people were also looking at designing custom hardware accelerators to try and make the technology efficient. But it was hard to make real progress without knowing why the technology was so slow.

“The performance was really bad,” says Agrawal. “Performing an operation on encrypted data was super, super slow, in the order of 10 to the power of five or six.”

It was an open challenge she was intent on solving. Beyond the impact she knew FHE could have on security if it was honed, she was also fascinated by it.

“It’s a kind of black magic,” says Agrawal. “[The] beauty of this technology is that you never decrypt the data to operate on it. You keep the data encrypted at all times and still perform the operations.” She wanted to find a way to make “such a wonderful technology practical and visible for real-world application.”

Like many burgeoning technologies, FHE has to crawl — extremely slowly — before it can walk. In the ’50s, it took half a room to store 4 megabytes of data. Today, most people carry hundreds of gigabytes in their pocket.

To make FHE work, you have to enlist processes that slow it down to the point of unusability. It can’t work without those processes, but in another way, it also can’t work with them.

The bootstrapping process Gentry discovered is exactly what slows FHE down, says Agrawal. Lattice-based cryptography adds random noise to the data, which keeps accumulating every time you perform an operation on it. The bootstrapping process required to refresh the data and remove the noise works, but it “made everyone’s life difficult,” says Agrawal.

To tackle the problem, she thoroughly analyzed every operation used in an FHE scheme. In that process, she realized something essential: The problem wasn’t compute-bound, meaning it wasn’t limited by computing power. It was memory-bound. No custom hardware accelerator was going to help. The answer was more memory.

Agrawal’s solution: Field Programmable Gate Arrays (FPGAs). More flexible for custom compute operations, FPGAs are like “reconfigurable hardware chips,” says Agrawal, that can allow “enough time to bring data from the main memory to the chip for processing.”

It was “a complete game changer,” she says. She published a paper on the topic in the 2023 IEEE International Symposium on High-Performance Computer Architecture and received hundreds of citations. Her paper showed that FPGAs could speed up performance dramatically — by 456x for CPUs and 9.6x for GPUs. For Agrawal, it was the first time she’d solved a problem where so many others had thrown up their hands. “That felt great,” she says.

Even with the efficiency advances FPGAs provided, FHE still isn’t fast enough to make large-scale encrypted computations truly practical. But Agrawal has high hopes for the future of the technology — and what it could mean for data sharing around the world.

Security Reinvented

Imagine never worrying about data breaches again.

As an individual, it could mean never having to worry about your passwords or accounts being hacked or your digital identity being stolen. As an enterprise, it could mean never having to face another lawsuit or scandal as a result of leaked sensitive data.

The viability of this technology is increasingly important as “companies are getting more and more dependent on cloud services,” Agrawal says. “When you share data with a third party, there are all sorts of attacks which can happen on the cloud.” But if that data is still “encrypted in transit,” those types of attacks would be virtually impossible.

FHE would also allow organizations to share data more safely, which could speed up their research. It could also help detect money laundering, fraud or even human trafficking. But Agrawal is particularly excited about one potential use case: helping hospitals share patient data that could lead to new drug discoveries.

Sharing patient data may be one of the most useful applications of FHE, but also the most challenging. While that data is vital for improving patient care and accelerating medical research, sharing it without compromising patient privacy is very difficult.

Say you’re “trying to cure cancer or something like that,” says Gentry. There are two problems. First, you have to protect the data before feeding it into an algorithm. “You have to encrypt the data. You might create a shared key under which all the data is encrypted, so at the end you can sort of collaboratively decrypt,” Gentry adds, explaining that with an FHE scheme, no one person would be able to decrypt the data on their own.

The second problem comes when you have to share data with other organizations. But Gentry says multi-key FHE schemes make this possible to do securely. Data can be encrypted under multiple keys while still undergoing different functions in the FHE scheme. “It’s a little less efficient,” says Gentry, but it’s possible.

While efficiency is still a problem for real-world applications of FHE, Gentry says the improvements to its speed have been enormous. Compute speed for FHE has even outpaced Moore’s Law, which dictates that compute power doubles with each year a technology is in existence. Both algorithmic and hardware improvements have been “tremendous” over the last decade and a half, he adds.

“The dream of cryptography is really that it's the ultimate way of handling data safely. So whatever secret input you have, whatever function you want to compute, you can do it,” he says. “And you don't have to reveal anything more than the final output of that computation.” A classic example of this in action, Gentry says, is the “millionaire problem”: Let’s say you want to figure out who has the most money among a group of millionaires without revealing anyone’s actual financial situation. You don’t want numbers. You just want to know who makes the most. FHE can do that.

Without FHE, as Gentry wrote in an article in 2010, “To put everything online ‘in the cloud,’ unencrypted, is to risk an Orwellian future. For certain types of data, such as medical records, storing them off-site unencrypted may be illegal. On the other hand, encrypting one’s data seems to nullify the benefits of cloud computing.”

FHE solves both these problems. And as people like Gentry and Agrawal continue to chip away at making the technology increasingly efficient, we get closer to a world that isn’t only safer, but more open. And that really does sound like the holy grail.