Part 1. 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.
Mathematically, an encryption scheme is fully homomorphic if, for any function $f$, there is a corresponding operation $\textsf{Eval}_f$ on ciphertexts such that
$$ \textsf{Dec}_\mathrm{sk}(\textsf{Eval}_f(\textsf{Enc}_\mathrm{pk}(m))) = f(m). $$In other words, computation on the ciphertext produces the same result as computation on the plaintext, just encrypted.
In this section, we'll cover:
- FHE from its origins to today's libraries (1.1),
- a taste of what 0xPARC is currently capable of building with FHE (1.2),
- a comparison to similar technologies (1.3), and
- an honest look at what FHE struggles to do (1.4).