Fully Homomorphic Encryption (FHE) is a form of encryption which uses a bunch of addition and multiplication on lattices and really high order polynomials with random noise and rounding to perform actions on encrypted data without ever decrypting it.

The concept of homomorphic encryption was first theorized in the late 1970s with “privacy homomorphisms” which could enable untrusted computers to perform operations on sensitive data without needing to reveal it in plaintext. However, homomorphic encryption would remain an open problem until 2009, when cryptographer Craig Gentry described a feasible homomorphic encryption scheme using lattices to express arbitrary circuits—a fully homomorphic encryption scheme.

However, a core challenge in implementing this scheme came from the randomly distributed noise that enabled Gentry’s implementation of homomorphic addition and multiplication operations. Specifically, homomorphic additions add small amounts of randomly generated noise to the noise accumulated over a circuit’s execution, while homomorphic multiplications multiply the same accumulated noise. Critically, when an FHE program’s noise accumulates past a certain threshold in binary, it becomes indistinguishable from the encrypted data used for the underlying computation. Simply put, adding too much noise will corrupt the encrypted data, and homomorphic multiplication will do this faster than homomorphic addition.

To mitigate this, Gentry proposed bootstrapping, a process that “refreshes” ciphertexts by homomorphically re-encrypting them using a different private key, effectively resetting a program’s noise before it can bleed into the critical data and corrupt it. However, bootstrapping came at the cost of speed and computational resources—it made FHE theoretically limitless but enshrined a structural tradeoff between security and usability for complicated programs. With the rate of noise accumulation and the computational overhead in bootstrapping, this tradeoff was initially massive, as Gentry’s initial scheme needed 30 minutes to evaluate each bit operation when it was finally implemented two years later.

Given all of this, early FHE research largely focused on improving efficiency by way of noise management, both by increasing the separation between noise and information to reduce the number of bootstrapping operations and by speeding up the actual process of managing noise. The 2013 Gentry-Sahai-Waters (GSW) scheme was a prime example of this as it accelerated FHE operations from minutes to milliseconds via “leveled” circuits. However, like some of the FHE schemes that followed, such as BGV and CKKS, it fragmented FHE into standards based on differing compilers and problem spaces. This fragmentation ultimately forced developers to trade a single standard of FHE for lower levels of friction. That being said, at this stage homomorphic millisecond-level logic gates remained a million times slower than traditional computing’s nanosecond-level operations, and as such, these early schemes were impractical for use in crypto.

Another caveat with practically applying FHE to shared state lies in decrypting outputs for use in non-FHE applications—to do so one naturally needs a decryption key. This decryption key becomes a limiter of trust assumptions and, in practice, is either controlled by a single party or a set of nodes in an MPC setting, which brings FHE back to the trust assumptions of MPC whilst being slower.