Fully Homomorphic Encryption and the Dawn of A Truly Private Internet

2025-07-16   fhe programming essay

This article is archived at mirror.xyz

Imagine sending Google an encrypted question and getting back the exact results you wanted — without them having any way of knowing what your question was or what result they returned. The technique to do that is called Fully Homomorphic Encryption (FHE).

The first time I heard about what FHE does, I didn't believe it was possible. But it is — an it works in real-world systems today.

It allows arbitrary computations on ciphertext (encrypted data) — without needing to decrypt it first. The result of the computation, once decrypted, matches the result as if it had been performed on plaintext (unencrypted data).

• From Craig Gentry's slides
  

Moore's Law of FHE

As FHE allows encrypted computation, users can keep their data encrypted all the time on the internet (sending, server computing, receiving back). This prevents any chance of data breach. Full Privacy.

But then, why isn't it the default like HTTPS? Why isn't everyone using it? And why haven't most people even heard of?

Because it is still not practical for most applications, as it is very slow. But this is changing fast as I'll explain below.

Current FHE has 1,000x to 10,000x computational overhead compared to plaintext operations. On the storage side, ciphertexts can be 40 to 1,000 times larger than the original. It's like the internet in 1990—technically awesome, but limited in practice.

Here's where it gets interesting: FHE algorithms are getting 8x faster each year. Operations that took 30 minutes per bit in 2011 now take milliseconds. See the graph below showing its dramatic speed improvement.

ref

The graph shows 10^12 times improvement until 2014. The pace of improvement continued over the last decade too. I will go deeper on that later in this article.

The Inflection Point

If this dramatic improvement continues, we're approaching a computational inflection point. In not too distant future, FHE could be fast enough for:

• Encrypted cloud computing
  

• Encrypted LLM inference
  

• Confidential blockchain smart contracts
  

The implications are big. The entire business model built on harvesting user data could become obsolete. Why send your plaintext when another service can compute on your ciphertext?

Internet's "Spy by default" can become "Privacy by default".

ref

Dive Deeper

Below sections go deeper into each aspect of the claim of this article. You can jump into any if you are particularly curious about those sections. You can also read them in order, as they are in a logical sequence:

• The problem: Achilles' Heel of Security
  

• The solution: Defining Full-Privacy Computing
  

• Technical Deep dive: How FHE Actually Works
  

• More on performance improvements: The Moore's Law of FHE: 8x Faster Every Year
  

• Connecting the dots: Future of computation is encrypted
  

Achilles' Heel of Security

All data exists in one of three states:

1. At Rest (stored on disk)
   

2. In Transit (moving over a network)
   

3. In Use (being processed in memory)
   

We have robust solutions for the first two:

• At Rest: Disk encryption, file system encryption.
  

• In Transit: TLS/SSL, VPNs, end-to-end encryption.
  

But in use—when data is loaded into RAM and processed by CPUs—it is decrypted. This is the Achilles’ heel of modern security. Cloud providers, insiders, attackers, or compromised CPUs can read your plaintext data.

Think about every major data breach you've heard of:

• The 2014 celebrity photo leak (Apple iCloud)
  

• The 23andMe genetic data theft
  

• The Capital One hack
  

They were failures of encryption-in-use or at rest. The moment data gets loaded into memory for processing, it becomes vulnerable.

FHE fixes this. Data can stay encrypted through its entire lifecycle on the cloud, which we can call "Full-Privacy Computing".

Defining Full-Privacy Computing

Picture an internet where your data is always encrypted:

• Encrypted at rest
  

• Encrypted in transit
  

• Encrypted in use
  

This means:

• Your device never sends plaintext to any server
  

• Servers process only encrypted data
  

• Only you can decrypt the results
  

Here's what a private ChatGPT session might look like:

# Your device
pk, sk = keygen() # pk: public key, sk: secret (private) key
enc_prompt = encrypt("Why did the dev go to therapy?", pk)
server.send(enc_prompt, pk)

# OpenAI's servers (they can never decrypt and see your prompt)
enc_prompt, pk = client.receive()
enc_llm = encrypt(LLM_MODEL, pk)
enc_answer = enc_llm.run(enc_prompt)
client.send(enc_answer)

# Your device again
enc_answer = server.receive()
answer = decrypt(enc_answer, sk)
print(answer)
"""Because of too many unresolved dependencies!"""

OpenAI computes the correct response, but can never see your question or their answer in plaintext.

Privacy as a computational invariant.

How FHE Works

The term "homomorphic" comes from Greek: "homo" (same) + "morphe" (form). It means having a structure-preserving map between two algebraic structures. FHE is homomorphic because operations on encrypted data can be mapped (i.e. mirrored) onto those on the original data.

The homomorphism in category theory is often shown by a commutative diagram, where you can go from a point to another by interchanging the order of operations. In the below diagram for FHE, you can go from (a, b) to E(a*b) in two separate ways.

ref

Let's look at an equivalent diagram with client/server perspective and f(x) function.

ref

One helpful analogy to FHE is the Fourier transform, which converts a signal from the time domain into the frequency domain. Computations performed on the frequency domain are equivalent to those in the time domain and vice versa. Meaning that you can compute in either domain and still get the same result. In a similar way, FHE operates between plaintext and ciphertext domains. Transformations done in plaintext domain are equivalent to those in the ciphertext domain, and vice versa.

The Lattice-Based Cryptography

To do the above mentioned transformation, FHE uses lattice-based cryptography—imagine a multidimensional grid of points extending infinitely in all directions.

• [ref](lattice-based cryptography)
  

At the heart of lattice-based cryptography are problems that are believed to be extremely hard to solve—even for quantum computers. Two of the most well-known examples are ¹::

• Shortest Vector Problem (SVP): Find the shortest path between lattice points
  

• Closest Vector Problem (CVP): Find the lattice point nearest to any given point
  

In 2D, these look trivial. But add 1,000,000 dimensions? Then it becomes extremely hard, so that it is believed that even quantum computers can't crack them efficiently. This makes FHE inherently quantum-resistant. A very important property to prepare for the possible quantum computing future.

Bonus: Lattice operations are highly parallelizable, which means they benefit enormously from modern GPUs and specialized hardware acceleration.

Learning With Errors (LWE)

Lattice-based FHE schemes rely on the Learning With Errors (LWE) or Ring-LWE problem. At a high level, LWE looks like this:

A -> a known matrix

s -> secret key

e -> random small noise

Calculate b = A*s + e (i.e. b is a noisy linear combination)

Generate public key = (A, b)

The hard problem: Given the public key (A, b), find the secret key s

ref

Notice that A*s is linear, so visually forms a lattice. In other words, A*s is on a lattice point. The addition of noise e makes the resulting A*s + e = b drifting from the lattice point (Note that the noise is sampled from a narrow random distribution so that b doesn't drift too much from the lattice point so that it is closer to another lattice point).

So the problem becomes that: If an attacker wants to find secret key s from the public key (A, b), he needs to solve the problem of finding the closest lattice point = closest vector problem (CVP). And closest vector problem is believed to be NP-hard and even quantum-resistant.

To sum up, encryption works because of noise. And encryption remains secure because decoding a lattice point with noise is hard.

Noise management & Bootstrapping

While the noise is the trick here, it also causes the following problem during addition and multiplication operations. During homomorphic addition, the noises of each ciphertext is also added to each other, while during multiplications they are multiplied. This results in:

• Addition --> noise grows linearly (manageable)
  

• Multiplication --> noise grows multiplicatively (un-manageable)
  

If the noise gets too big, decryption fails — you get garbage instead of the result.

Since noise growth unmanageable with multiplication, the noise-based HE schemes before Craig Gentry 2009 allowed only a limited number of multiplications (hence not Turing-complete). For that reason, they were called Somewhat Homomorphic Encryption.

Craig Gentry invented in 2009 the first HE scheme that allows infinite number of additions and multiplications combined. Hence it is Turing Complete. Hence it is called Fully Homomorphic Encryption. Note that any kind of computation can be represented as additions and multiplications. Indeed, all computations are reduced to additions and multiplications on the CPU/GPU level.

The main piece that makes FHE work was the method called "bootstrapping". Bootstrapping reduces the noise whenever it gets too big. In that way, it guarantees that noise doesn't disrupt decryption, no matter how many multiplications are performed.

The way how bootstrapping work is very clever. It's probably called "bootstrapping", because it "refreshes" the cipher text under another public key. It cleverly switches the ciphertext from one public key to another, as follows:

1. Take the original public key pk_orig
   

2. Take the ciphertext ctx which was originally encrypted under pk_orig
   

3. Generate a whole new key pair pk_new, sk_new
   

4. Encrypt pk_orig under pk_new, obtaining pk_bootstrap (Yes! Encrypt the key with another key. Creative!)
   

5. Encrypt the ciphertext ctx under pk_new, obtaining ctx_new
   

6. Run (homomorphically) the decrypt operation on ctx_new with sk_new, obtaining ctx_bootstrap
   

Notice that, the decryption procedure of FHE is itself a computation. So it can be used for homomorphic computations too!

The new ctx_bootstrap is another new ciphertext, whose noise is reset. Note that, it gained some fixed noise as it went through additions and multiplications during the decryption computation. But this noise is bounded.

Another thing to keep in mind is, bootstrapping is the performance bottleneck of modern FHE schemes. Though its computational overhead gets better every year by new algorithms.

• From Craig Gentry's slides
  

There are many more details to that. I listed some resources going through at FHE Bootstrapping, though they also don't cover everything. One needs to read through FHE Reference Library. Other topics around bootstrapping are quite complicated, and as far as I understood, it is the focal point of FHE algorithmic innovations. It's really important to understand it conceptually at least, because it's the root of FHE slowness, while also the reason why FHE works.

Other topics around FHE you need to be aware are relinearization and modulus switching. I'll explain them only by intuition here. For deeper math, I suggest Vitalik's post as a starter.

Relinearization

A ciphertext is linear in the secret key -> a + b​⋅s

After multiplication, the result become quadratic in secret key. To show that:

Let's multiply below ciphertexts:

• ct1 = (a1, b1), whose decrypted form is a1 + b1*s
  

• ct2 = (a2, b2), whose decrypted form is a2 + b2*s
  

After multiplication:

• ct_mul = (a₁a₂, a₁b₂ + a₂b₁, b₁b₂), whose decrypted form is a₁a₂ + (a₁b₂ + a₂b₁)·s + b₁b₂·s²
  

• Notice the s² term, which makes ct_mul quadratic in the secret key.
  

Relinearization uses additional public key material called "relinearization keys" to eliminate the higher-degree terms. The process:

1. Takes the quadratic term b₁b₂·s²
   

2. Uses relinearization keys to "convert" this back into linear terms
   

3. Produces a new linear ciphertext (c₀', c₁') that decrypts to the same value
   

Modulus Switching

It's used to manage noise growth. It's a trick to reduce the noise by decreasing the modulus of the ciphertext.

I did couple of conversations with ChatGPT to understand some mathematical details of FHE better, and wrote down what I learned from them here.

Classification of HE Schemes

What do we mean by a Homomorphic Encryption (HE) Scheme?

A HE scheme is a cryptographic construction that defines how encryption, decryption, and homomorphic operations are performed (e.g. BGV, CKKS, TFHE).

Homomorphic Encryption schemes are classified by the types and number of operations they support.

Partial Homomorphic Encryption

Supports only one operation (e.g., addition in Paillier, multiplication in RSA).

(I will build a toy Pailler example below, whose code is short and intuitive)

Somewhat Homomorphic Encryption

Supports both addition and multiplication, but number of multiplications allowed is limited.

(I explained in previous section how noise growth limits number of multiplications possible)

Fully Homomorphic Encryption

Supports unlimited additions and multiplications. Turing Complete. Manages noise by periodically reducing via bootstrapping.

A toy example

One of the best ways to really understand a computational concept is building it from scratch, minimally.

For the purposes of this blog post, creating a Fully Homomorphic Encryption scheme would be very lengthy. Instead, we will write Paillier HE, which is shorter and easier to understand for getting an intuition. Paillier is a Partial HE, meaning that it doesn't support all operations (hence not Fully HE). It only supports additions (hence additive homomorphism). We'll follow a typical HE flow:

1. Key Generation (public-key + private-key)
   

2. Encryption of data (using public-key)
   

3. Computation (homomorphic operations)
   

4. Decryption of result (using private-key)
   

import sympy, random

def generate_keypair(bit_length=512):
    p = sympy.nextprime(random.getrandbits(bit_length))
    q = sympy.nextprime(random.getrandbits(bit_length))
    n = p * q
    g = n + 1
    lambda_ = (p - 1) * (q - 1)
    mu = sympy.mod_inverse(lambda_, n)
    return (n, g), (lambda_, mu)

def encrypt(m, public_key):
    n, g = public_key
    r = random.randint(1, n - 1)
    return (pow(g, m, n**2) * pow(r, n, n**2)) % (n**2)

def decrypt(c, private_key, public_key):
    lambda_, mu = private_key
    n, _ = public_key
    l = (pow(c, lambda_, n**2) - 1) // n
    return (l * mu) % n

def homomorphic_sum(a, b, public_key):
    return (a * b) % (public_key[0]**2)


public_key, private_key = generate_keypair(128)

enc1 = encrypt(5, public_key)
print(enc1) # 75042696080311881003721105285833023546234037256871189406054603593273414107194675808782154359890875636008219678257354647151456750847402457204123856890

enc2 = encrypt(3, public_key)
print(enc2) # 269297253929306291153284608946414491483346738328838888044406160105950588673820650688249910373352597049965491330298818622410901670587359945691000319758

enc_sum = homomorphic_sum(enc1, enc2, public_key)
print(enc_sum) # 232817745404365921249916946617154013580946738803385878188677616867767489473531493655408124901849935882016399498283109322848069064027287561237823608127

dec_sum = decrypt(enc_sum, private_key, public_key)
print(dec_sum) # 8

If we were to build a Fully HE, it could use a similar API with generate_keypair, encrypt, decrypt, and homomorphic_sum with an addition of homomorphic_multiply. But the code would be much longer. For such a code, see Vitalik's homomorphic_encryption.py and matrix_fhe.py. Also read his awesome deep dive.

Further reading:

• FHE time complexity
  

• Exploring Fully Homomorphic Encryption by Vitalik
  

• Build from scratch
  

  • FHE toy implementations
    

    • See Bit-wise FHE section of FHE toy implementations#Bit-wise Fully Homomorphic Encryption
      

  • Building Safe A.I., A Tutorial for Encrypted Deep Learning - i am trask
    

  • Fully Homomorphic Encryption from Scratch - daniellowebgrub
    

  • HN - Explained from scratch private information retrieval and homomorphic encryption (blintzbase.com)
    

  • TFHE toy implementation
    

• From the pioneers:
  

  • Craig Gentry (FHE inventor)
    

    • 2025, April. FHE inside out
      

    • 2024, June. FHE past, present, future
      

    • 2021, Oct. A decade (or so) of FHE
      

  • Jung-hee Cheon (CKKS inventor)
    

    • 2019, March. HE and blockchain
      

The Moore's Law of FHE: 8x Faster Every Year

ref

The Four Generations:

• 1978 (Pre-history): Rivest, Adleman, Dertouzos envisioned FHE by the name "privacy homomorphisms"
  

• 2009 (Gen 1): Gentry's 2009 PhD thesis constructing the first ever FHE scheme
  

• 2011 (Gen 1): First implementation of FHE–bootstrapping took 30 minutes per bit ²
  

• 2011-2012 (Gen 2): BGV/BFV schemes, lattice-based, still slow.
  

• 2013+ (Gen 3): Faster bootstrapping in milliseconds.
  

• 2017 (Gen 4): CKKS for approximate floats, enabling ML/AI.
  

For more, see FHE History.

Since 2011, FHE performance has improved 8× every year—from 10¹⁰× overhead down to ~10³× ~10^4× today.

• From Craig Gentry's slides
  

Recent breakthroughs are accelerating the timeline:

• A June 2025 paper by Dan Boneh & Jaehyung Kim claims 1,000× higher multiplication throughput and 10× lower latency (for large-integer ops)
  

• Hardware acceleration could add another 10³× speedup
  

Alongside with algorithm improvements, hardware improvements are also happening, compounding the effect. More on that in FHE Hardware

Here is Vitalik's thoughts on pace of progress:

Future of computation is encrypted

Let's connect the dots.

Data breaches are almost unavoidable.

The only way to protect data is to keep it always encrypted on servers, without the servers having the ability to decrypt.

This means data should be encrypted even when computations are performed on it.

FHE enables computation on encrypted data.

FHE is not practical yet for many applications because of its high computational overhead. But it's practical for some.

FHE algorithms are getting better each year, by 8x per year. The result is that feasible real-world applications are on the increase. FHE is eating computation, but it is still small.

If the trend continues, FHE will conquer many more real-world use cases to the point that most cloud computations can be done with FHE.

Privacy awareness of users is increasing. Privacy regulations are increasing.

If FHE is a possible option, people and institutions will demand it.

If people are demanding it, and the trends have made FHE practical for most computations, then most internet computations will be on FHE.

The future of internet computations will be encrypted. It is not if, it is when.

HTTPS by default --> 2010s
FHE by default   --> ?

Key References

Key Papers & Resources:

• FHE Reference Library - Comprehensive academic papers
  

• Craig Gentry's 2009 PhD Thesis - The foundational work
  

From the Pioneers:

• Craig Gentry: FHE inside out, FHE past, present, future, A decade (or so) of FHE
  

• Jung-hee Cheon (CKKS inventor): HE and blockchain
  

• Pascal Paillier: Introduction to FHE
  

• Daniele Micciancio: Fully Homomorphic Encryption from the Ground Up
  

Good reads:

• Vitalik Buterin: Exploring FHE
  

Improvements:

• Fully Homomorphic Encryption Just Became Practical
  

Implementation Examples:

• FHE for Genomics
  

• Encrypted Sentiment Analysis
  

• Encrypted Deep Learning
  

• Private Wikipedia
  

• More Production Examples
  

Community:

• FHE.org - The central hub for FHE development
  

Other:

• https://github.com/jonaschn/awesome-he