A from-scratch, didactic build of the CKKS Fully Homomorphic Encryption scheme. Every step is written for clarity over speed:
- no RNS (Residue Number System) — coefficients are plain Python big integers, so you can watch a single big number get added and multiplied instead of tracking a vector of residues;
- no NTT (Number Theoretic Transform) — polynomial multiplication is textbook schoolbook O(N²), exactly how you would do it on paper;
- small parameters — ring degree N = 512, 256 slots, chosen so the whole pipeline runs in seconds on a laptop;
- everything is inspectable — you can print
sk,pk,evk, any ciphertext, and the hidden noise polynomial.
This is not a production library. It exists to be read.
Intended audience: STEM students who may not have seen cryptography, lattices, polynomial rings, or modular arithmetic. The theory primer and glossary below are meant to get you oriented before you read the code.
Requires NumPy. Python 3.9 is the hard minimum, but please use the latest
stable CPython (3.14 at the time of writing) — this project plans to
adopt newer language features as they land, and keeping your local
interpreter current avoids surprises. .python-version pins 3.14 so
uv venv / uv run pick it automatically.
uv venv # creates .venv using the version in .python-version
uv pip install -e . # installs numpy per pyproject.toml
Then run examples with .venv/bin/python examples/01_encode_decode.py
(or activate: source .venv/bin/activate).
pip install numpy
There are five tutorial notebooks under notebooks/. They are the
recommended way to learn the material: each one interleaves prose,
LaTeX math, runnable code cells, plots, and an exercise.
notebooks/01_encode_decode.ipynb # encoding a vector into a polynomial
notebooks/02_encrypt_decrypt.ipynb # RLWE encryption / decryption
notebooks/03_hom_add.ipynb # homomorphic addition
notebooks/04_hom_mult.ipynb # tensor -> relinearize -> rescale
notebooks/05_noise_overflow.ipynb # the noise "cliff"
Install the [tutorials] extra (JupyterLab + matplotlib) and launch:
uv pip install -e '.[tutorials]'
uv run jupyter lab
The same material exists as plain Python scripts under examples/ for
anyone who prefers the command line — they print narrated output and
need no Jupyter installation.
python3 examples/01_encode_decode.py # encoding a vector into a polynomial
python3 examples/02_encrypt_decrypt.py # RLWE encryption / decryption
python3 examples/03_hom_add.py # homomorphic addition
python3 examples/04_hom_mult.py # tensor -> relinearize -> rescale
python3 examples/05_noise_overflow.py # the noise "cliff" — takes ~10 seconds
The .ipynb files are built from a Python source of truth at
tools/build_notebooks.py. Edit the prose or code there and run:
uv run python tools/build_notebooks.py
uv run jupyter nbconvert --to notebook --execute --inplace notebooks/*.ipynb
| File | What it is |
|---|---|
ckks/params.py |
All magic numbers in one place |
ckks/ring.py |
The polynomial ring R = Z[X]/(X^N + 1) |
ckks/encoder.py |
Encode a complex vector → plaintext polynomial |
ckks/sampling.py |
Random distributions (uniform / ternary / Gaussian) |
ckks/keygen.py |
Secret, public, and evaluation keys |
ckks/cipher.py |
The Ciphertext type; encrypt, decrypt |
ckks/ops.py |
add, mult, tensor, relinearize, rescale |
ckks/noise.py |
Peek at the hidden noise inside a ciphertext |
Every file opens with a plain-English block comment explaining the math. Read those first, code second.
A ring is any set of objects where you can add and multiply, following the usual rules (associative, distributive, there is a 0 and a 1, subtraction works). The integers Z are a ring. So are the rationals, the reals, and the polynomials with integer coefficients Z[X].
In CKKS we use a specific ring:
R = Z[X] / (X^N + 1)
Read that as "polynomials in X with integer coefficients, with the extra rule that X^N = −1". The "/ (X^N + 1)" means "pretend X^N + 1 is zero", which is the same as saying "X^N = −1". In practice this means every polynomial in R has at most N coefficients — whenever X^N or higher appears during a multiplication, you immediately rewrite it using the rule.
Let's multiply a = 1 + 2X + 3X²+ 4X³ by b = X² + X³ inside
Z[X] / (X⁴ + 1):
a * b
= X²(1 + 2X + 3X² + 4X³) + X³(1 + 2X + 3X² + 4X³)
= X² + 2X³ + 3X⁴ + 4X⁵ + X³ + 2X⁴ + 3X⁵ + 4X⁶
= X² + 3X³ + 5X⁴ + 7X⁵ + 4X⁶
Now apply the rule X⁴ = −1, which also gives X⁵ = X·X⁴ = −X and X⁶ = X²·X⁴ = −X²:
5 X⁴ -> −5
7 X⁵ -> −7 X
4 X⁶ -> −4 X²
Substituting:
a * b = −5 + (−7) X + (1 − 4) X² + 3 X³
= −5 − 7 X − 3 X² + 3 X³
The "fold-back with a sign flip" is what poly_mul does inside ring.py.
Three reasons.
- Compactness. Every element has at most N coefficients, regardless of how you got there. No runaway degree.
- Efficient arithmetic. For N a power of two, polynomial multiplication in this ring is amenable to a FFT-like transform (the NTT). We don't use the NTT in this implementation, but standard CKKS does.
- Security. The Ring Learning-With-Errors (RLWE) problem is conjectured hard in exactly this kind of ring. Security is the whole point.
The ciphertexts we store are not in R, but in R_q: the same ring but
with every coefficient taken modulo a big integer q. That is,
every coefficient is kept in the range [0, q). If a coefficient would
be negative, we add q; if it would be ≥ q, we subtract q.
Think of coefficients as the hands of a clock with q positions. Adding and multiplying as usual, then wrapping. Nothing exotic.
For display and for inspecting the noise, it is convenient to use the
balanced representation [−q/2, q/2) instead — same values, just a
different naming convention so that the number −3 appears as −3 rather
than q − 3.
Pick:
a: a uniformly random polynomial in R_q,s: a small secret polynomial (ternary: coefficients in {−1, 0, +1}),e: a small error polynomial (Gaussian, integer-rounded).
Form the pair
(a, b = -a * s + e mod q).
The conjecture — which underpins the security of CKKS and many other lattice cryptosystems — is that this pair is computationally indistinguishable from a uniformly random pair, even though b clearly depends on s. Anyone seeing (a, b) cannot separate the "signal" (a·s) from the "noise" (e).
That is the entire security backbone. Everything else is linear algebra on top.
Plaintext. A plaintext in CKKS is a polynomial m in R (or R_q,
same thing — it has coefficients ≪ q). It is what you get after
encoding a vector of complex numbers z using the canonical
embedding. Plaintexts are public — no secrecy.
Ciphertext. A ciphertext is a short tuple of polynomials (most of
the time just two, (c0, c1)) in R_q. It satisfies
c0 + c1 * s = m + noise (mod q)
for a small noise polynomial. Anyone with s can add up the left side
and recover m + noise ≈ m. Without s, the ciphertext looks like two
uniform random polynomials.
The key identity to keep in your head is that line above: ciphertext evaluated at s equals plaintext plus small noise. Every homomorphic operation is designed to preserve this shape.
A single plaintext polynomial m of degree < N carries N/2 complex numbers in parallel. These are called slots. Operations on ciphertexts act on all N/2 slots simultaneously ("SIMD"): one ciphertext add is N/2 complex additions; one ciphertext multiply is N/2 complex multiplications.
Why only N/2 slots and not N? Because the encoder forces the plaintext
polynomial to have real coefficients, which introduces a conjugate
symmetry in the N evaluation points, leaving only N/2 degrees of
freedom. See encoder.py for the full story.
Every fresh ciphertext carries a tiny bit of noise (about 2⁸ in absolute value for our parameters). Operations grow it:
- addition:
+ ≲ 1 bit - multiplication (tensor + relinearize + rescale): bigger jump, but rescaling also shrinks the modulus, which is the thing bounding the noise.
As long as |noise|_∞ < q_level / 2, decryption wraps correctly and
the plaintext is recovered. The moment that bound is crossed, the mod-q
wrap makes the output total nonsense.
We track this with a single number, the noise budget:
noise_budget = log2(q_level / 2) − log2(|noise|_∞).
When the budget is positive, the ciphertext is decryptable. When it crosses zero, it isn't. Example 5 demonstrates both ways it can happen.
| Term | Definition |
|---|---|
| Ring | A set with addition and multiplication obeying the usual rules. Here, Z[X]/(X^N + 1). |
| R_q | The ring R with coefficients taken modulo q. The world where ciphertexts live. |
| N | Ring degree. Every polynomial we store has ≤ N coefficients. Must be a power of 2. |
| Coefficient modulus q | The big integer that all ciphertext coefficients are reduced by. |
| Scaling factor Δ (delta) | Fixed-point multiplier used to turn real numbers into integers when encoding. |
| Slot | One of N/2 independent complex entries carried in parallel by a single plaintext. |
| Canonical embedding | The map that sends a polynomial to its values at the primitive 2N-th roots of unity. Building block of the encoder. |
| Plaintext | A polynomial in R representing the encoded message. |
| Ciphertext | A tuple of polynomials (c0, c1, ...) in R_q that decrypts to plaintext + noise. |
| Secret key (sk) | A small polynomial s. The ciphertext c0 + c1·s ≈ m (mod q) is how decryption works. |
| Public key (pk) | A pair (b, a) with b = −a·s + e. Anyone can use pk to encrypt without learning s. |
| Evaluation key (evk) | A "near-encryption of s²" used by relinearization to collapse three-component products. |
| RLWE | Ring Learning With Errors — the hardness assumption that makes the scheme secure. |
| Ternary | A distribution over {−1, 0, +1}. Used for small secrets and small masks. |
| Noise | The small error polynomial lurking inside every ciphertext. Added on encryption and amplified by operations. |
| Noise budget | log2(q_level / 2) − log2( |
| Tensor | The raw product of two ciphertexts. Produces a transient three-component ciphertext. |
| Relinearize | Collapse a three-component ciphertext back into two components using the evaluation key. |
| Rescale | Divide every coefficient by Δ (rounded) to bring the scaling factor back to Δ. Consumes a level. |
| Level | How many rescales we have left before the modulus is used up. |
| Bootstrapping | A technique for refreshing the noise and the level of an exhausted ciphertext. Not implemented here. |