What is FHE?

Today, encryption is ubiquitous: it's used to privately send messages, store sensitive data, and secure online transactions. Yet in traditional cryptography, in order to use the encrypted data to do something useful, it must be decrypted first. It seems obvious that it shouldn't be possible to compute on encrypted data: after all, how could data possibly be used without first decrypting it? Encryption should destroy structure.

Fully homomorphic encryption (FHE) breaks this assumption. It decouples the ownership of data from the infrastructure that processes it: computation in transit, rather than computation at rest. Using a fully homomorphic encryption scheme, it is possible for:

medical researchers to draw conclusions from encrypted patient data,
banks to detect money laundering without sharing transaction data,
servers to perform biometric verification while preserving user privacy, and
buyers of bulk data to verify its quality before they purchase it.

More broadly, FHE unlocks computations that previously couldn't happen at all, because they would have required data sharing that no party was willing to do.

Definition

Mathematically, fix a plaintext space $\mathcal{M}$, the set of values the scheme operates on. An encryption scheme is fully homomorphic if, for any function $f : \mathcal{M}^n \to \mathcal{M}$ of any number of inputs, there is a corresponding operation $\textsf{Eval}_f$ that transforms ciphertexts such that

$$ \textsf{Dec}_\mathrm{sk}\bigl(\textsf{Eval}_f(\textsf{Enc}_\mathrm{pk}(m_1), \ldots, \textsf{Enc}_\mathrm{pk}(m_n))\bigr) = f(m_1, \ldots, m_n) $$

for all plaintexts $m_1, \ldots, m_n \in \mathcal{M}$. In other words, computing on the ciphertexts produces the same result as computing on the plaintexts, just encrypted.

The plaintext space $\mathcal{M}$ can take many forms. Some examples that real schemes use are:

a single bit, $\mathcal{M} = \{0, 1\}$ (or a small integer modulo $p$);
a vector of $k$ integers modulo a prime $p$, with $k$ typically a few thousand, $\mathcal{M} = (\mathbb{Z}/p\mathbb{Z})^k$;
a vector of $k$ real or complex numbers, with $k$ again typically a few thousand, $\mathcal{M} = \mathbb{C}^k$ — in which case the equality above typically holds only approximately, with decryption recovering the result up to a small rounding error, much like ordinary floating-point arithmetic.

This definition is informal, and glosses over details such as how keys are generated, what security the scheme provides, and how the approximate case behaves precisely.

Exercise: attempt to formalize this definition so that it rules out “trivial” constructions, such as a scheme that isn't really homomorphic, one whose ciphertexts hide nothing, or one that simply defers all of the computation to decryption.

Single vs. multiparty

Whether a deployment is single-party or multiparty comes down to who holds the secret key.

In single-party FHE, one party owns both the data and the secret key. It encrypts its data, sends the ciphertexts to an untrusted server to compute on, and decrypts the result the server returns. The server does the work but never sees anything in the clear. This is the classic setting of outsourcing a computation to a party you don't trust with the data.

In multiparty FHE, the secret key is split across several parties so that no single party ever holds the entire key; as a result, no one can decrypt on their own. Several parties, each wanting to keep their own data private, can contribute their encrypted data, have a server compute jointly over all of it, and recover the result only once enough of them agree that releasing it preserves their privacy. This makes it possible to compute over the combined data of parties who are unwilling to reveal their inputs to one another.

Both setups run the same underlying scheme and differ only in how keys are generated and how decryption works.