Homomorphic Encryption — Hands-on Intro (Toy LWE)
A short interactive tutorial that demonstrates the core idea of homomorphic encryption using a simple LWE-style toy scheme. This is pedagogical — not secure. Use it to learn concepts: keys, encryption, noise growth, and homomorphic addition.
What is FHE (in one sentence)?
Fully Homomorphic Encryption (FHE) lets you compute on encrypted data and obtain an encrypted result which, when decrypted, matches the result of performing the same computation on the plaintexts. In practice, FHE schemes are complex — this page shows a simplified toy LWE-style construction to build intuition.
Contents
1. What is LWE
The Learning With Errors (LWE) problem is the mathematical foundation of many lattice-based cryptographic schemes, including modern FHE. It is believed to be hard even for quantum computers [1].
In LWE, we assume there exists a secret vector \( s \), and we observe many samples of the form:
\[ (a, b = \langle a, s \rangle + e \bmod q) \]
where \( a \) is random, and \( e \) is a small noise term. The challenge is to recover \( s \) from these noisy linear equations — a problem known to be computationally hard.
Most FHE schemes build on variants of LWE, such as Ring-LWE (RLWE), where operations take place in polynomial rings for efficiency.
Public Key vs. Secret Key (A Practical Note)
The toy example below uses a single secret key (s) for both encryption and decryption. This is called a symmetric-key scheme, and we use it here to keep the math simple and build intuition.
However, practical, real-world FHE schemes (like BFV and CKKS) are public-key (or asymmetric) systems. In that model:
- A Public Key (pk) is generated and shared with everyone. Anyone can use this key to encrypt messages (e.g.,
Encrypt(pk, message)). - A Secret Key (sk) is kept completely private by the data owner. Only this key can decrypt the messages (e.g.,
Decrypt(sk, ciphertext)).
This is powerful because a server can receive encrypted data from many different people (who all used the public key) and compute on it, all without ever being able to decrypt the underlying data.
Toy scheme (LWE-style) — mathematics (short)
We define small parameters to illustrate encryption:
\[ \text{modulus: } q = 97, \quad \text{secret key: } s = 17, \quad \text{noise: } e = \text{small random value (e.g., ±1)} \]
To encrypt a message \( m \) with key \( s \):
\[ a \text{ — random integer } 0 \le a < q \]
\[ Enc(m) = (a, b = (a \cdot s + m + e) \bmod q) \]
To decrypt using \( s \):
\[ Dec(a, b) = (b - a \cdot s) \bmod q \approx m + e \]
Since \( e \) is small, the result is approximately \( m \).
Homomorphic addition works naturally:
\[ Enc(m_1) + Enc(m_2) = (a_1 + a_2, b_1 + b_2) \bmod q \;\;\rightarrow\;\; m_1 + m_2 + (e_1 + e_2) \]
Noise accumulates with operations — a key limitation and motivation for advanced schemes like BFV and CKKS.
Example: Encrypting and Decrypting a Small Message
Encrypt \( m = 5 \) using \( q = 97 \), \( s = 17 \), and \( e = 1 \).
- Choose \( a = 23 \)
- Compute ciphertext: \[ b = (23 \cdot 17 + 5 + 1) \bmod 97 = 12 \]
- Encrypted message: \( Enc(5) = (23, 12) \)
- Decrypt: \[ Dec(23, 12) = (12 - 23 \cdot 17) \bmod 97 = 5 \approx m \]
Noise is tiny, so decryption recovers the original message.
Example: Homomorphic Addition and Noise Accumulation
Encrypt two messages \( m_1 = 5 \) and \( m_2 = 7 \):
| Message | Random a | Noise e | Ciphertext b = (a·s + m + e) mod q |
|---|---|---|---|
| 5 | 23 | 1 | 12 |
| 7 | 17 | -1 | 15 |
Homomorphic addition of ciphertexts:
\[ Enc(m_1) + Enc(m_2) = (23 + 17, 12 + 15) \bmod 97 = (40, 27) \]
Decrypting the sum:
\[ Dec(40, 27) = (27 - 40 \cdot 17) \bmod 97 = 12 \approx m_1 + m_2 + (e_1 + e_2) \]
This shows how noise accumulates and motivates advanced noise management in FHE.
Interactive playground
Try encrypting two small integers, add them homomorphically, and decrypt to see how noise behaves.
Notes about this toy demo
- Because noise accumulates, repeated operations eventually produce incorrect results.
- Real FHE schemes include relinearization, modulus switching, and bootstrapping to manage noise for deeper circuits.
2. FHE Scheme Timeline
The concept of computing on encrypted data—once a theoretical dream from the 1970s known as "privacy homomorphisms"—took decades to become a practical reality. This timeline charts the pivotal moments in that journey.
It begins with early partially homomorphic schemes (like RSA, which could only perform multiplication) and moves to the watershed 2009 breakthrough by Craig Gentry, which finally proved FHE was possible. From there, it follows the rapid innovation that gave us today's powerful and specialized schemes, paving the way for secure cloud computing and machine learning.
Key milestones in FHE history, based on information from FHE.org [2].
Key Milestones in FHE History
- 1977 (RSA): This foundational public-key cryptosystem was the first major scheme to exhibit a partial homomorphic property. It allows for the multiplication of ciphertexts (e.g.,
Enc(m1) * Enc(m2) = Enc(m1 * m2)), proving that computation on encrypted data was possible, even if limited to a single operation. - 2009 (Gentry's Breakthrough): Craig Gentry's doctoral thesis provided the first plausible construction for a Fully Homomorphic Encryption scheme. It solved the critical problem of noise accumulation by introducing "bootstrapping," a revolutionary technique to refresh a ciphertext, theoretically allowing for an unlimited number of computations.
- 2011-2012 (BGV / BFV): These "second-generation" schemes (named for Brakerski, Gentry, Vaikuntanathan, and Fan-Vercauteren) made FHE more practical. Based on the Ring-LWE problem, they introduced new noise-management techniques (like modulus switching) and are optimized for exact integer arithmetic—ideal for private database queries and financial applications.
- 2016 (CKKS): A revolutionary scheme (from Cheon, Kim, Kim, Song) designed for approximate arithmetic. By treating the noise as part of the calculation, CKKS can efficiently perform computations on encrypted real or complex numbers. This breakthrough unlocked the use of FHE for data science and privacy-preserving machine learning.
- 2016 (TFHE): This scheme (Fast Fully Homomorphic Encryption over the Torus) takes a different approach by operating on individual bits. It excels at evaluating boolean circuits (logic gates like AND, OR, NOT) and is notable for its incredibly fast and efficient bootstrapping, allowing for complex programs to be run on encrypted data.
BGV Scheme
The BGV scheme (named for its authors: Brakerski, Gentry, and Vaikuntanathan) is a foundational "second-generation" FHE scheme, often grouped with BFV. It is based on the Ring-LWE problem and is designed for efficient and exact arithmetic on integers.
Its primary innovation was a new modulus switching technique, which effectively "shrinks" the ciphertext and its noise in a controlled way after each multiplication. This allows for deeper computational circuits before bootstrapping is required.
CKKS Scheme
The CKKS scheme (named for its authors: Cheon, Kim, Kim, and Song) is a breakthrough FHE scheme optimized for approximate arithmetic. Unlike BFV or BGV which handle exact integers, CKKS works on encrypted real or complex numbers.
It achieves this by treating the "noise" as part of the approximation error, similar to floating-point arithmetic. It uses a special rescaling procedure to manage the magnitude of the encrypted values, making it the standard for privacy-preserving machine learning and data analysis.
TFHE Scheme
TFHE (Fast Fully Homomorphic Encryption over the Torus) is a unique FHE scheme that operates at the bit level. Instead of encrypting large numbers, it is optimized for encrypting individual bits and performing boolean operations (like AND, OR, NOT).
Its most famous feature is its extremely fast bootstrapping, which can "refresh" an encrypted bit in milliseconds. This allows for the evaluation of any arbitrary circuit or function, including running complex conditional logic (like "if" statements) on encrypted data.
Polynomial Rings in FHE (Why They Matter)
Modern FHE schemes are built on the Ring-LWE (RLWE) problem. Instead of encrypting large vectors of integers (as in standard LWE), RLWE works with polynomials whose coefficients are integers modulo a large number \(q\). This polynomial structure is key to efficiency:
- Efficiency: Polynomial multiplication is used for homomorphic multiplication and can be accelerated using the Number Theoretic Transform (NTT), a fast, polynomial-based analogue of the FFT.
- Packing (Batching): A single RLWE ciphertext can encrypt hundreds or thousands of messages (called slots), improving throughput.
The standard polynomial ring in FHE is:
\[ R_q = \mathbb{Z}_q[x] / (x^N + 1) \]
Here \(N\) is a power-of-two degree and \(q\) is the coefficient modulus. Different FHE schemes use variations of this ring depending on their computational goals.
Which scheme uses which ring?
| Scheme | Underlying Ring / Domain | Purpose |
|---|---|---|
| BFV / BGV | \( \mathbb{Z}_q[x]/(x^N + 1) \) (Integer coefficients mod \(q\)) | Exact integer arithmetic (private databases, sums) |
| CKKS | \( \mathbb{Z}_q[x]/(x^N + 1) \) (Integer coefficients mod \(q\)) | Approximate real/complex arithmetic (ML, data science) |
| TFHE | \( \mathbb{T}[x]/(x^N + 1) \) (Torus coefficients mod 1) | Boolean circuits and ultra-fast bootstrapping |
Key Distinction: BFV, BGV, and CKKS are RLWE schemes using integer polynomial rings. TFHE uses TLWE/TRLWE (Torus LWE / RLWE), algebraically similar but with the torus \(\mathbb{T} = \mathbb{R}/\mathbb{Z}\), enabling very fast bootstrapping.
Intuition: What do these rings look like?
1. Integer Polynomial Rings (BFV, BGV, CKKS)
A “number” is a polynomial:
\[ a(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_{N-1} x^{N-1} \]
Operations:
• Coefficients \(a_i\) are integers mod \(q\)
• Polynomial arithmetic wraps mod \(x^N + 1\)
Messages are usually embedded into low-order coefficients. This allows a single ciphertext to pack many integer or approximate values into its \(N\) slots.
2. Torus Polynomial Ring (TFHE)
TRLWE = \( \mathbb{T}[x] / (x^N + 1) \)
TFHE encodes binary messages \(m \in \{0,1\}\) as \(m/2\) (0 or 0.5) in the torus. Noise is a small fractional value. Values wrap around like points on a unit circle. This fractional-noise encoding enables ultra-fast, table-lookup-based bootstrapping.
Visual Comparison of Coefficients
BFV / BGV / CKKS (RLWE)
Integer coefficients modulo a large \(q\) (e.g., \(2^{60}\))
Example:
\( a(x) = [1203, 9931, 8123, …] \mod q \)
TFHE (TRLWE)
Coefficients on the torus (real numbers modulo 1)
Example:
\( a(x) = [0.13, 0.92, 0.51, …] \mod 1 \)
Why different rings?
- BFV / BGV → Exact integer arithmetic → integer rings.
- CKKS → Approximate real arithmetic → same integer ring, but messages are scaled; noise is acceptable approximation error.
- TFHE → Fast boolean logic → torus domain enables FFT-based bootstrapping for single-bit operations.
RLWE Ciphertext = Polynomial + Noise (BFV/CKKS)
RLWE generalizes LWE from vectors to polynomials. Each ciphertext component is a polynomial whose coefficients contain small noise modulo \(q\), enabling homomorphic operations.
Encryption Example (Conceptual)
\( m(x) \) : plaintext polynomial
\( s(x) \) : secret key polynomial
\( a(x) \) : randomly sampled public polynomial
\( e(x) \) : small noise polynomial
Ciphertext components:
\( c_0(x) = a(x) \mod (x^N+1, q) \)
\( c_1(x) = a(x) \cdot s(x) + m(x) + e(x) \mod (x^N+1, q) \)
Example with \(N=4\):
\( m(x) = 12 + 3x + 7x^2 \)
Coefficients: \( [12, 3, 7, 0] \)
Noise: \( e(x) = [0, -1, 2, 0] \)
Ciphertext \( c_1(x) = [b_0, b_1, b_2, b_3] \mod q \) (polynomial coefficients with small noise)
Noise grows with operations and is controlled via modulus switching (BFV/BGV) or rescaling (CKKS).
Torus Representation (TFHE)
TFHE uses the torus \(\mathbb{T} = \mathbb{R}/\mathbb{Z}\), so values wrap around in [0,1). For example, \(0.9 + 0.3 \equiv 0.2 \pmod 1\). Binary messages \(m \in \{0,1\}\) are encoded as \(m/2\).
Diagram: Values on the Torus
Each coefficient is a fractional value modulo 1.
TRLWE Sample
Where \( \mu(x) \) is the encoded message polynomial.
LWE → RLWE → TLWE → TRLWE: How They Relate
| Type | Sample Form | Space | Used in |
|---|---|---|---|
| LWE | \((\mathbf{a}, b = \langle \mathbf{a}, \mathbf{s} \rangle + e) \pmod q\) | \(\mathbb{Z}_q^n\) (vectors of integers) | FHEW, GSW |
| RLWE | \((\mathbf{a}(x), \mathbf{b}(x) = \mathbf{a}(x)\mathbf{s}(x) + \mathbf{e}(x)) \pmod{x^N+1, q}\) | \(\mathbb{Z}_q[x]/(x^N+1)\) | BFV, BGV, CKKS |
| TLWE | \((\mathbf{a}, b = \langle \mathbf{a}, \mathbf{s} \rangle + e) \pmod 1\) | \(\mathbb{T}^n\) (vectors on torus) | TFHE |
| TRLWE | \((\mathbf{a}(x), \mathbf{b}(x) = \mathbf{a}(x)\mathbf{s}(x) + \mathbf{e}(x)) \pmod{x^N+1,1}\) | \(\mathbb{T}[x]/(x^N+1)\) | TFHE |
Summary
LWE → Integer vectors mod q RLWE → Integer polynomials mod q TLWE → Torus vectors mod 1 TRLWE → Torus polynomials mod 1
Playground: Visualizing Polynomial Multiplication & Noise
Static example showing polynomial multiplication and noise accumulation in RLWE.
Input Polynomials:
\( a(x) = 3 + 1x + 4x^2 + 0x^3 \)
\( b(x) = 2 + 0x + 1x^2 + 5x^3 \)
Multiplication mod \(x^4+1\):
\( a(x)\cdot b(x) = 6 + 2x + 11x^2 + 15x^3 + 4x^4 + 5x^5 \)
Reduce mod \(x^4+1\) (since \(x^4 \equiv -1\)):
\( a(x)\cdot b(x) \equiv 11 + 22x + 11x^2 + 16x^3 \) (vector: \([11, 22, 11, 16]\))
Add noise:
\( e(x) = 1 + 0x - 1x^2 + 2x^3 \)
Resulting ciphertext component:
\( c(x) = a(x)\cdot b(x) + e(x) \equiv 12 + 22x + 10x^2 + 18x^3 \mod q \)
RLWE ciphertexts accumulate noise with each operation. Modulus switching (BFV/BGV) or rescaling (CKKS) is used to control this growth.