Breakfast Bytes Blogs

Do you know what Fully Homomorphic Encryption (FHE) is? When I first heard about it a few years ago, I thought it was something of minor academic interest, like those schemes for giving keys to a group where any 3 of them can decrypt the message but not fewer. It is starting to become practical, so I predict that you will hear a lot more about it in the future.

Homomorphic Encryption

Let's start with how you operate on data that is encrypted the regular way. Let's take a trivially simple example. You have two numbers on disk that have been encrypted, and you want to add them. You read the numbers off the disk, you use the decryption keys to get the original numbers, you add them, then you encrypt the sum and write it back to disk. Or in an EDA context, perhaps in the cloud, you read encrypted RTL from disk, decrypt it, synthesize it to a netlist, encrypt the netlist and write it back to disk.

Homomorphic encryption allows you to do this (for some operations anyway) without ever decrypting the data, or even knowing the key. So you read the encrypted numbers off the disk, you "add" them by doing some special operations, then you write the result back to disk, already encrypted with the key you don't even know. The result is the same as if you had gone through the process as in the preceding paragraph. Or you can imagine synthesizing RTL to netlist without ever decrypting it.

It sounds like this might be impossible. In fact, the idea was proposed in the late 1970s. Like public key encryption, the basic concept was proposed long before there were any implementations. The first proposed implementations were restricted—you could only do, say, additions. Fully Homomorphic Encryption (FHE) allows you to perform arbitrary operations. A first implementation was proposed in 2009 by Craig Gentry (in his PhD dissertation!). However, it would be a couple of years later that the first practical implementations were developed, and 2013 before so-called third-generation FHE that improved the efficiency enough to start to be practical in some applications.

Fully Homomorphic Encryption

There are two big reasons that you might want to use FHE. In Bruce Schneier's book Applied Cryptography, he points out that:

There are two kinds of cryptography in this world: cryptography that will stop your kid sister from reading your files, and cryptography that will stop major governments from reading your files.

We are concerned with the second type. Major governments assume that all data centers have been compromised. In a compromised data center, adding the numbers the traditional way (not using FHE) means that the decrypted data exists in the server and the bad guys can maybe read it (or perhaps alter it). The only solution to this is to protect the data instead of the data center, which is what FHE does. So that's reason number one, that you can securely process data in an insecure data center.

The second reason is that you can process data while keeping it confidential. We've all been repeatedly told that "data is the new oil" in this age of AI and training. FHE means that you can let people use your data without giving it away, and so you can realize its full value. For example, you can license your data for someone to train a neural net with it, but without them being able to do anything else.

Here's an easy-to-understand example. Let's say you have a valuable mailing list (maybe you are DAC or IEEE). You want to be able to rent your mailing list and let other people use it. How do you stop them from just stealing it? Today, this problem is solved in two main ways. The first way is that the owner of the mailing list does the mailing. The customer provides the email to be sent, and the owner (DAC or NYT) sends out the mail. Since the list never leaves the building, it can't be stolen by the client. The second way is to give the list to the client and, at some level, trust them to follow all the terms in the legal agreement. But that assumes you trust the customer and the legal system. Plus, there is a certain amount of closing the stable-door after the horse has bolted, since the worst-case scenario is that the mailing list is put in a public place so anyone can use it, so it becomes valueless. You can do a certain amount to detect abuse, but not stop it, by adding dummy email addresses to the list and seeing if they receive unauthorized mailings.

With FHE, you can provide the mailing list and the mail program and the customer can run it themselves. Of course, sending out emails isn't that big of a deal so sledgehammers and nuts spring to mind. But allowing someone to train a self-driving-car network on your petabytes of driving data is the same idea at scale.

IBM

IBM is one of the companies doing research on trying to make FHE practical. Just recently on June 4, it released a fully homomorphic encryption toolkit (surprisingly just for iOS and macOS in this first release). There are other toolkits around, too.

IBM's description of the history says:

In the past, cryptographic schemes that allowed processing on encrypted data were limited to partial homomorphic schemes that could support only one fundamental operation, namely either addition or multiplication but not both. Then in 2009 IBM invented Fully Homomorphic Encryption, which supports both fundamental operations, thus enabling the processing of data without giving access to it, however at this time it was too slow for practical use.

From a practical point of view, IBM feels that:

It was no small feat to synthesize 11 years of top-notch cryptography research into a streamlined developer experience that is accessible and freely available to anyone in the time most people would spend to brew a pot of coffee or de-clutter a desk.

But these are by no means the last words. This is an active area of research on both the theoretical and practical sides. As IBM's Flavio Bergamaschi says in the announcement linked above:

I should point out that these are not perfect or final. We wanted to quickly put them out to get the technology into the hands of early adopters who want to make these concepts less abstract and more concrete as we look to build up a community of users and use cases.

Cornami

The other thing that happened recently that made me think that FHE might be on the cusp of something big is that Wally Rhines came out of his semi-retirement to become the CEO at FHE fabless semiconductor startup Cornami. Of course, Wally is well-known in EDA and semiconductor having been CEO of Mentor (and before that ran Texas Instruments' semiconductor business).

I contacted Wally to find out more.

This post is too long already so I'll tell you what Wally told me in a second post in a few days. But here's the brief summary of how Wally got involved with the company:

I encountered them because I was doing a gig to investigate whether the industry was developing chips to make "fully homomorphic encryption" (FHE) possible. DoD sees this as a critical development because it's well accepted that they must assume every data center has been compromised; therefore, their strategic plan dictates securing the data rather than the data center and FHE is the only known, provable approach to quantum-resistant security. When I talked with half a dozen semiconductor companies, the answer was universal—no interest for at least ten years because it would require one million times the performance of current GPUs and CPUs. When I met the Cornami folks, they showed me their order-of-magnitude advantage in machine learning versus everyone else, and then casually mentioned that, because of their architecture, they have this application called FHE that they could do in real time for nearly the same cost as today's servers. They were amazed that I had even heard of FHE.

Learn More

You can learn more about FHE starting from the IBM announcement. There is also a Wikipedia page on Homomorphic Encryption with a lot of history.

This video (1 hour) is from Eurocrypt 2019, in which Daniele Micciancio of UCSD presents an invited talk Fully Homomorphic Encryption from the Ground Up. The first part is fairly general, and then it dives deeper into what can currently be implemented.

There is also a community standard for homomorphic encryption maintained by the HomomorphicEncryption.orgngroup, an open industry/government/academia consortium.

Sign up for Sunday Brunch, the weekly Breakfast Bytes email.