What I Found Trying to Build FHE from One-Time Pads

Table of Contents

• Table of Contents
• Overview
• Fully Homomorphic Encryption (FHE) Background
• Intuitive Walkthrough (Shift Cipher)
  • Caesar Cipher Recap
  • Caesar Cipher Addition
  • Caesar Cipher Naive Multiplication
  • Caesar Cipher Multiplication Lookup
  • One-Time Pad (OTP) Addition
• Resources

Overview

Every time you send data to an LLM provider to be processed (OpenAI, Anthropic, etc.) you are trusting that your data isn’t being leaked, trained on without your permission or otherwise misappropriated. This is a growing concern as tools such as Claude Code are now beginning to produce a significant amount of the worlds sofware.

There is also a real possibility that these tools could be compromised in the future if these providers become co-opted by other forces, for a further discussion refer to this post.

So our options are currently to either run local models which are less capable and still require $1000s of dollars in hardware (either Macs with at least 32GB RAM, or GPUs with 24GB RAM+ running quantized models) or to purchase hardware in the $10,000+ range to run open-source frontier models (e.g. high-end Mac Studio which can run GPT OSS 120B or Kimi k2.5, etc.).

Or we go with the default option of using Claude, GPT, Gemini and other frontier models straight from the providers and opt-out of their training / data collection and pray they actually obey this. This also requires ignoring how OpenAI has shared information with law enforcement for prosecutions, Anthropic’s relationships with Palantir and the CCP’s history of being heavily “entangled” with China’s tech giants. Not to mention PRISM and the Edward Snowden era leaks, Elon Musk releasing the Twitter files not least of which involved suppressing opinions counter to the COVID narrative.

Another alternative would be if LLM specific processors such as Google’s TPUs, Apple’s unified memory architecture and ANE (Apple Neural Engine) units becoming cheaper, LPUs (Language Processing Units which are LLM optimised devices from Groq) and AWS’s Inferentia hardware become more affordable and mainstream.

However, there is another option which is emerging, Fully Homomorphic Encryption (FHE).

Fully Homomorphic Encryption (FHE) Background

FHE allows you to perform computations on encrypted data without ever needing to decrypt the data first. This naturally lends itself to use cases where the person performing the compute has an advantage in either compute or access to certain data which is private or proprietary. This makes it a natural fit for deploying LLMs in a way that is private for both parties, so whats the catch?

The issue with current FHE implementations is that they are slow, painfully slow. Firstly modern FHE implementations require representing data using x10,000 more data than the original data requires. So for instance if you have a text prompt for an LLM which is 100 tokens long (and let’s assume each token) requires 4 bytes to represent. Then the prompt would require:

That doesn’t seem to bad? Well remember that it applies to all data which is being processed. So if we’re passing that through even a 1B parameter model which is represented in bfloat16 format, then the numbers look more like:

However we are able to multiply an encrypted value by a constant which means that we can keep the model weights in plaintext.

Intuitive Walkthrough (Shift Cipher)

Caesar Cipher Recap

So how does it work? Let’s start with a simplified example. Anyone who has studied computer science before is likely familiar with the Caesar Cipher.

The idea is to convert some text into its integer representation, shift it along by some fixed amount, transmit the shifted text, and the receiver will unshift the text by the same amount decrypting the text and ensuring private communication between the two parties.

The sender, lets say Alice, would send KHOOR to Bob, who would already know to shift the message back by 3 letters. However what happens if the letter goes past the last letter of the alphabet?

What happens is that we take the letter position, add the shift and crucially we divide by 26 and take the remainder as the new letter. So in this case:

Caesar Cipher Addition

Great we can now scramble messages and if someone has an accompanying key they will be able to decrypt it. But can it be used for anything else?

Notice how the cipher uses addition and subtraction for encryption and decryption respectively? Well what if instead we represented numbers instead of letters?

Ok now we’re able to encrypt and decrypt numbers. But we if we could send this data to a third-party to process and have them return the new data without ever having to reveal the original information? This would be a crucial first building block towards allowing for secure LLM provisioning!

It turns out that this is quite easy to do, we can simply just add the numbers together!

You’ll notice above that the Ciphertext sum, 13, is exactly 10 higher than the real sum of the two numbers, 3.

That is because the ciphertext sum is actually a sum of:

Where:

• $a$ and $b$ are the original plaintext values,
• $k_a$ and $k_b$ are the secret shifts used to encrypt them.

In our toy example:

• $a = 1$
• $b = 2$
• $k_a = 5$
• $k_b = 5$

So the encrypted sum is:

Bob can then decrypt the result by subtracting off the combined shift:

So even though the third party never saw the original numbers, it was still able to compute on the encrypted data and return a useful encrypted result. This is the core homomorphic idea: operations on ciphertext correspond to operations on plaintext.

Crucially this relies on the sender, Alice, knowing the compute graph which the data is being processed on. Otherwise we’re not able to correctly decrypt the results. This also means we get subtraction for free, since subtraction is just addition with a negative number.

Caesar Cipher Naive Multiplication

Addition worked nicely because the extra shifts simply added together, and Alice could remove them at the end. So the next obvious question is, can we also multiply encrypted numbers?

Let’s try the same setup as before. Suppose we encrypt:

If a third party multiplies the ciphertexts together, they get:

At first glance this looks promising: the plaintext product is $6$, and the ciphertext product is $56$. But unlike addition, the difference between these two values is not just a simple combined shift.

If we write the encrypted values as:

then multiplying them gives:

Expanding this out:

So the ciphertext product is not just the real product $ab$ with some simple offset added on top. Instead it contains three extra terms:

• $ak_b$
• $bk_a$
• $k_a k_b$

These are called cross terms. They are the main problem.

In our toy example:

• $a = 2$
• $b = 3$
• $k_a = 5$
• $k_b = 5$

So:

The issue is that removing these extra terms is much harder than in the addition case. For addition, Alice only had to subtract off the combined key:

which is easy to undo if she knows $k_a$ and $k_b$.

But for multiplication she has to somehow remove:

and this is non-trivial because the unwanted terms now depend on both the plaintext values and the keys. In other words, the noise is no longer just a simple offset: it is entangled with the computation itself.

This gets worse as computations become deeper. Each multiplication introduces new cross terms, and those cross terms interact with later operations to create even more complicated expressions. So while this shift-based scheme supports addition naturally, multiplication does not compose cleanly.

Crucially, if Alice knows the full computation graph in advance, she may be able to account for some of these extra terms in restricted cases. But in the general case the correction terms grow too messy, which is exactly why a simple shift cipher is not enough to build a practical fully homomorphic encryption scheme.

Caesar Cipher Multiplication Lookup

So does multiplication failing algebraically mean we are completely stuck? Not quite.

If the input space is small enough, Alice can pre-compute the answer to every possible multiplication ahead of time and store the results in a lookup table. Instead of trying to symbolically remove the cross terms

we simply treat the encrypted inputs as indices into a table.

For example, suppose Alice is using a shift of $+5$ and wants to support multiplication on small numbers. If we encrypt

then instead of asking the server to directly multiply the ciphertexts and hoping the result is easy to decrypt, we can define a table:

Here:

• encrypted value $6$ corresponds to plaintext $1$,
• encrypted value $7$ corresponds to plaintext $2$,
• encrypted value $8$ corresponds to plaintext $3$,
• and so on.

So if the server receives encrypted values $7$ and $8$, it does not compute

because that introduces the unwanted cross terms. Instead it looks up the pair $(7, 8)$ in the table and returns $11$, which is the encryption of the correct plaintext product:

This works because the table already “bakes in” the correction. Rather than undoing

we avoid producing those terms in the first place.

Conceptually, the lookup table is acting like a tiny precomputed program:

• take encrypted inputs,
• interpret them as table indices,
• return the encrypted result associated with the corresponding plaintext operation.

This is useful as a toy demonstration because it shows that even when the raw algebra becomes awkward, we may still be able to evaluate functions on encrypted data by replacing arithmetic with table lookup.

However, this comes with major limitations:

• the input space must be very small,
• Alice must know in advance which function is being evaluated,
• every supported operation needs its own table,
• table sizes grow rapidly as the domain gets larger,
• and chaining many such lookups becomes cumbersome.

So lookup tables can rescue multiplication in restricted cases, but only by trading algebraic elegance for brute-force precomputation. This is one of the main reasons that toy schemes like Caesar cipher do not scale into practical fully homomorphic encryption.

There is also another major issue, the Caesar Cipher is not actually cryptographically secure. The default version only has 25 possible keys, for each shift value, so it’s easy to brute force.

So do we have another option? It turns out that we actually do, the One-Time Pad (OTP).

One-Time Pad (OTP) Addition

An OTP is an unbreakable form of encryption, provided that the key is truly random, at least as long as the message, kept secret, and never reused.

On Unix-like systems, randomness is typically obtained from the operating system’s cryptographic random number generator, which is seeded using unpredictable system events such as interrupt timing, device activity and, sometimes, dedicated hardware random number generators.

For our toy numeric setting, the main difference from the Caesar cipher is that we no longer use one fixed shift for every value. Instead, each value gets its own fresh random pad. If we are working modulo $q$, we encrypt a plaintext value $a$ by sampling a random key $k_a \in {0, 1, \dots, q-1}$ and computing:

As long as $k_a$ is chosen uniformly at random and never reused, the ciphertext reveals nothing about the plaintext.

Crucially, we can still perform addition on encrypted values. If we encrypt two numbers as

then adding the ciphertexts gives:

So the result is still an encryption of the sum, just under the combined pad $k_a + k_b \bmod q$. To decrypt, Alice or Bob subtracts the combined key material from the final result.

Resources

• Notebook