If you’re interested in learning about the basics of FHE before reading this article, take a look at our FHE 101 series.
In 1934, Switzerland passed Article 47 of its Federal Banking Act, making it a criminal offense for a banker to reveal a client's identity or account contents. The law gave depositors something they could not get elsewhere: a counter-party that would custody their assets, transact on their behalf, and operate at scale, without learning who they were or what they held.
The system worked. It also created decades of confusion about what, exactly, it protected against. A Swiss bank under Article 47 could not read your ledger. But it could still execute a forged transfer if the forgery was good enough. It could not tell tax authorities about you. But it could be compelled, under sufficient legal pressure, to freeze the account. It could not see the contents of your safe deposit box. But it could lose the building to a fire, and the contents with it. The system’s guarantee was real, narrow, and easily mistaken for something larger.
Fully homomorphic encryption (FHE) bears a striking resemblance to Swiss banking (though we certainly hope that FHE processors don’t catch on fire). As a result, FHE invites the same kind of confusion and then some, given the increasing interest in it. Let’s take a minute or two to talk about what FHE does for security, what it doesn't, and why it matters.
Telling a Security Story
The Swiss Banking story, like every good security story, starts with a cast of characters (clients, banks, adversaries of various kinds), their assets, actions they can take, and limitations that the system imposes on those actions.
The FHE story is no different. In this story, clients hold data assets on which they want computation performed. Those assets might be medical records, financial positions, or queries to be answered.
In our story, we’ll call the bank the server. That’s an odd name with a history: “server” entered computing from queueing theory in about 1953, first appeared in ARPANET’s RFC 4 and RFC 5 in about 1969, and it survives to this day. In our story, the server takes data from one client (or more) and runs a program that the client requested on that data, providing the result of the program back to the client. The server may have data assets of its own to contribute to the computation.
A quick aside: often, the key management sub-plot can be confusing. In our story, there are several cryptography keys:
- The public key allows both the client(s) and the server to encrypt data to be used in the program that the server runs.
- The computation key(s) (often there are a whole set of these keys) are used by the server to run the program correctly.
- The star of our sub-plot, the private key, is held only by the client. It is the only key that allows decryption of any input, intermediate program data, or output of the program that the server runs. Security depends strongly on the client keeping that private key to themselves.
Finally, in our story adversaries abound. We as cryptographers are a paranoid bunch, so we assume:
- that the server (or someone with inappropriate access to it) may try to see the assets of the client, or try to perform transactions incorrectly.
- that there are observers listening on the network between client and server.
- that the client may provide intentionally bad data to confuse the server or learn the assets of some other client to the computation.
What does this cast of characters want guaranteed?
- The client wants a guarantee that neither the server or any network observer can see their sensitive inputs to the program run by the server.
- The server wants a guarantee that any sensitive asset it contributes to the program cannot be seen by any client or unauthorized observer.
- The client also wants the server to perform computation faithfully — that is, according to the program the client specified.
- In turn, the server wants the client to give it genuine assets that do not spoil the computation for other clients, or reveal other client data in some way.
What FHE Can and Cannot Do
Now the stage is set, and we can examine what FHE can and cannot do to provide the above guarantees.
FHE guarantees only one thing. Cryptographers describe that thing through a game called Indistinguishability under Chosen-Plaintext Attack (IND-CPA): any data encrypted using FHE is mathematically indistinguishable from the encryption under the same FHE scheme of any other arbitrary data of the same length, unless you hold the decryption key, even if someone gets to choose and encrypt their own sample messages and study how the encryption behaves.
Hmm…try again. In Shakespearean quatrain, maybe?
The ciphertext, to a prying eye,
Resembles noise, though plaintext lies within;
No chosen sample, howsoe'er they try,
Reveals which message hides beneath the skin.
Ok, I admit it. Explaining IND-CPA is a bit like Feynman explaining quantum electrodynamics. So, let’s try an analogy: I'm going to tell you what IND-CPA means by way of the Swiss bank, you're going to nod along, and at the end you'll have a working intuition that is approximately correct and deeply unsatisfying.
The bank has a vault where every safe deposit box (we call the box a ciphertext) is the exact same size and shape. Assets are stored in each box: a jeweler stores a diamond in one; a stamp collector stores an envelope in another; an attorney stores documents in a third. (We call these assets client data). From the outside — looking at the boxes, weighing them, observing which ones get opened and when — you cannot tell them apart. Even if you rent your own box and fill it with anything you choose, and even if you watch other people's boxes for years, the boxes themselves reveal nothing about their contents.
Even with this guarantee, client data isn’t entirely safe. For one thing, an adversary who can modify ciphertexts, hand them to the server, and observe results can learn things it shouldn’t. That’s a deliberate, necessary feature of FHE: without it, you can’t compute on ciphertexts. In the bank analogy, we might say that if the bank allowed you to hand them a safe deposit box that you built yourself, you’d learn things you shouldn’t.
For another thing, FHE cannot prevent the adversary from learning things from the decrypted output of the computation. If you open the box and hand it to someone, of course they get to see what’s in it.
In addition, an adversary can learn things about client data from how long the computation takes, how much power it uses, and even what memory access patterns are used.
All of these vulnerabilities can be addressed, but to do so takes other security techniques alongside FHE. Ditto FHE’s shortcomings on the other guarantees we mentioned earlier:
- The server wanted a guarantee that its sensitive data remains private, but because FHE programs allow plaintext server data as input, anyone with access to the server might see its data. Now, yes, FHE does provide for server assets to be stored and used as input in FHE-encrypted form, but FHE doesn’t insist on it.
- The client wanted a guarantee that the server would compute faithfully, and FHE has nothing at all to say about that.
- Finally, the server wanted a guarantee that the client would provide genuine inputs, for example not engineered to reveal something about someone else’s inputs. FHE has nothing to say about that either: in fact, if the server could check the data for malicious intent, the encryption would be broken.
What FHE Does Guarantee
The Swiss banking system worked because depositors understood what they were buying. They were buying confidentiality from the bank itself, and from anyone the bank wasn't compelled to talk to such as tax authorities in other jurisdictions. In other words, they were buying a banker’s plausible deniability. They were not buying integrity, availability, or protection from their own mistakes. The system was useful precisely because its guarantees were narrow enough to be reliable.
FHE is the same. It buys you insurance that a compute provider can’t learn or disclose your encrypted data assets – not by force, nor choice, nor incompetence, nor gloom of night. That loss of privacy is the central obstacle to running sensitive workloads on third-party infrastructure, and FHE removes it. But "removes one obstacle" is not the same as "removes all obstacles," and a deployment that treats FHE as a single-shot solution to cloud security will find the gaps the hard way.
The set of properties that FHE does NOT guarantee is something worth exploring together. In my next post, we’ll look at those concepts and discuss how a system’s approach using specific other technologies alongside FHE can achieve the full picture of security we outlined here.
If you’re interested in learning more about FHE and how to use it in practice, check out some of my other posts:
To learn more about FHE, hardware acceleration, and Niobium’s encrypted cloud platform, The Fog™, contact us or sign up to join our beta!
