Alright, so I’ve been diving deep into the mathematical foundations behind modern FHE schemes, and honestly, the more I understand the underlying algebra, the more elegant this whole thing becomes. In my previous blog on LWE cryptanalysis, I touched on the basic Learning With Errors problem, but now I want to get into the real mathematical meat of Ring-LWE and the CKKS scheme.
This is gonna be pretty heavy on the math - we’re talking cyclotomic polynomials, Galois theory, Chinese Remainder Theorem, and some serious algebraic number theory. But stick with me, cuz understanding this foundation is crucial for grasping how modern FHE schemes actually work under the hood.
I’m writing this as a mathematical foundation piece because I realized that in my upcoming blogs on automorphisms and key switching, I keep having to explain these core concepts. So here’s the deep mathematical dive that’ll serve as the foundation for those more specialized topics.
Table of Contents
- From LWE to Ring-LWE: Why Rings?
- Cyclotomic Polynomials and Algebraic Structure
- The Chinese Remainder Theorem Perspective
- CKKS Encoding: Complex Numbers in Polynomials
- Discrete Gaussian Distributions and Noise
- Security Foundations: Ideal Lattices
- Parameter Selection and Trade-offs
- Implementation Considerations
- References
From LWE to Ring-LWE: Why Rings?
So we all know that standard LWE works with vectors in $\mathbb{Z}_q^n$. An LWE sample looks like $(\mathbf{a}, b)$ where $b = \langle \mathbf{a}, \mathbf{s} \rangle + e + \Delta m$. This is great and all, but there are some serious practical issues:
- Key Size: The secret key $\mathbf{s}$ has $n$ elements
- Ciphertext Size: Each ciphertext is $(n+1)$ elements
- Operations: Matrix-vector multiplications are expensive
Ring-LWE fixes this by moving from vectors to polynomials. Instead of working in $\mathbb{Z}_q^n$, we work in the polynomial ring $R_q = \mathbb{Z}_q[X]/(f(X))$ for some polynomial $f(X)$.
Now here’s the key insight: a polynomial of degree $n-1$ can be represented by $n$ coefficients, just like a vector of length $n$. But polynomial arithmetic gives us way more structure to work with.
A Ring-LWE sample looks like:
$(a(X), b(X)) \text{ where } b(X) = a(X) \cdot s(X) + e(X) + \Delta \cdot m(X) \bmod f(X)$
The magic happens because polynomial multiplication in $R_q$ can be done super efficiently using Number Theoretic Transform (NTT), which is basically FFT over finite fields.
Cyclotomic Polynomials and Algebraic Structure
Now, the choice of $f(X)$ is crucial. We typically use $f(X) = X^n + 1$ where $n$ is a power of 2. This isn’t random - $X^n + 1$ is the $2n$-th cyclotomic polynomial $\Phi_{2n}(X)$.
What are Cyclotomic Polynomials?
Think of cyclotomic polynomials as the “primes” of polynomial rings. Just like how prime numbers are the indivisible building blocks of integers, cyclotomic polynomials are irreducible polynomials that can’t be factored further over the rationals.
But here’s the cool part - while prime numbers feel abstract and random, cyclotomic polynomials have this beautiful geometric interpretation. The $m$-th cyclotomic polynomial $\Phi_m(X)$ “knows about” the $m$-sided regular polygon!
Visualizing the Geometric Picture
Imagine you’re standing at the center of a circle, looking at the vertices of a regular $2n$-sided polygon inscribed in that circle. Each vertex corresponds to a $2n$-th root of unity - a complex number $\zeta_{2n}^k = e^{2\pi i k / 2n}$.
Now, most of these vertices are “derived” - if you know where vertex 1 is, you can get vertex 2 by just squaring it, vertex 3 by cubing it, etc. But some vertices are primitive - they can’t be obtained as powers of vertices from smaller polygons.
The cyclotomic polynomial $\Phi_{2n}(X)$ is exactly the polynomial whose roots are these primitive vertices!
For our specific case where $m = 2n$ and $n$ is a power of 2:
$\Phi_{2n}(X) = X^n + 1$
The primitive $2n$-th roots of unity are exactly the odd powers: ${\zeta_{2n}, \zeta_{2n}^3, \zeta_{2n}^5, \ldots, \zeta_{2n}^{2n-1}}$.
Why odd powers? Because if $k$ is even, then $\zeta_{2n}^k = (\zeta_{n})^{k/2}$ is actually an $n$-th root of unity, so it “belongs” to a smaller polygon!
The Ring Structure: Why $X^n = -1$ is Magic
Working in $R = \mathbb{Z}[X]/(X^n + 1)$ means we’re doing polynomial arithmetic with the rule that $X^n = -1$. This seems weird at first, but it’s actually brilliant!
Think of it this way: in regular polynomial multiplication, if you multiply two polynomials of degree $d$, you get a polynomial of degree $2d$. That’s annoying for storage - your polynomials keep getting bigger.
But with the rule $X^n = -1$, any polynomial automatically “wraps around” to stay within degree $n-1$. It’s like doing arithmetic on a clock, but instead of $12 + 1 = 1$, we have $X^n = -1$.
Here’s the intuition for why it’s $-1$ and not $0$: remember those primitive $2n$-th roots of unity? They satisfy $\zeta^{2n} = 1$, which means $(\zeta^n)^2 = 1$. Since $\zeta^n \neq 1$ (that would make it an $n$-th root), we must have $\zeta^n = -1$.
The beautiful structure we get:
- Wrapping Multiplication: $X^i \cdot X^j = X^{(i+j) \bmod n}$ if $i+j < n$, otherwise $X^i \cdot X^j = -X^{(i+j) \bmod n}$
- FFT-Friendly: The Number Theoretic Transform works perfectly because our roots of unity are evenly spaced around the circle
- Lattice Structure: The ring elements correspond to lattice points with special geometric properties
The automorphism group is isomorphic to $(\mathbb{Z}/2n\mathbb{Z})^*$, which has order $n$. Each automorphism $\sigma_k$ is defined by $\sigma_k: X \mapsto X^k$ where $\gcd(k, 2n) = 1$.
The Chinese Remainder Theorem Perspective
This is where the magic really happens, and it’s the key insight that makes CKKS so powerful. Let me give you the intuition first, then the math.
The “Multiple Personalities” View
Imagine you have a polynomial $p(X)$. Instead of thinking of it as a single mathematical object, the Chinese Remainder Theorem says you can think of it as having $n$ different “personalities” - one for each root of $X^n + 1$.
It’s like how Clark Kent and Superman are the same person, just in different contexts. Your polynomial $p(X)$ is “the same” as the vector $(p(\zeta_1), p(\zeta_2), \ldots, p(\zeta_n))$ where the $\zeta_i$ are the roots of $X^n + 1$.
Mathematically, this gives us an isomorphism:
$\mathbb{C}[X]/(X^n + 1) \cong \mathbb{C}^n$
Any polynomial $p(X) \in \mathbb{C}[X]/(X^n + 1)$ is uniquely determined by its evaluations:
$p(X) \leftrightarrow (p(\zeta_{2n}), p(\zeta_{2n}^3), \ldots, p(\zeta_{2n}^{2n-1}))$
Why This is Revolutionary for Computation
Here’s the killer insight: polynomial operations become pointwise vector operations!
Want to add two polynomials? Just add their evaluation vectors component-wise. Want to multiply? Multiply component-wise. This is called SIMD (Single Instruction, Multiple Data) - you get $n$ operations for the price of one.
Complex Conjugate Pairs: The CKKS Packing Trick
Here’s where CKKS gets really clever. Remember our $2n$-sided polygon? The vertices come in conjugate pairs - if you have a vertex at angle $\theta$, you also have one at angle $-\theta$.
This means if $\zeta$ is a root of $X^n + 1$, then so is $\overline{\zeta}$ (its complex conjugate).
Now here’s the packing magic: if we restrict to polynomials with real coefficients (which is what we do in practice), then evaluating our polynomial at conjugate pairs gives conjugate values:
$p(\zeta) = \overline{p(\overline{\zeta})}$
This means we only need to store half the evaluation vector! If we know $p(\zeta)$, we automatically know $p(\overline{\zeta}) = \overline{p(\zeta)}$.
Result: We can pack $n/2$ complex numbers into a single polynomial of degree $n-1$. It’s like getting a 2x compression for free, just by exploiting the symmetry of the roots!
CKKS Encoding: Complex Numbers in Polynomials
The CKKS scheme exploits this conjugate structure beautifully. Think of it as a universal translator between two languages: the language of polynomials and the language of complex vectors.
The Encoding Intuition
Imagine you have $n/2$ complex numbers that represent, say, the pixels of an image or the coefficients of a Fourier transform. You want to encrypt them homomorphically, but Ring-LWE only knows how to encrypt polynomials.
CKKS says: “No problem! I’ll convert your complex vector into a polynomial, encrypt that polynomial, and when you do operations on the polynomial, they’ll automatically happen to your original complex numbers.”
It’s like having a magical box where you put in a complex vector, it gets converted to a polynomial, encrypted, and when you add two such boxes, the encrypted polynomials add in a way that makes the underlying complex vectors add too.
Canonical Embedding: The Universal Translator
The canonical embedding $\sigma$ is our universal translator. It takes a polynomial $p(X) = \sum_{i=0}^{n-1} p_i X^i$ and evaluates it at all our special roots:
$\sigma(p) = (p(\zeta_{2n}), p(\zeta_{2n}^3), \ldots, p(\zeta_{2n}^{2n-1}))$
This is like asking: “If this polynomial were a person, what would it say when you ask it about each of these $n$ roots?”
Encoding Complex Vectors
To encode a vector $\mathbf{z} = (z_0, z_1, \ldots, z_{n/2-1}) \in \mathbb{C}^{n/2}$, we:
- Extend to Conjugates: Create $\tilde{\mathbf{z}} = (z_0, \ldots, z_{n/2-1}, \overline{z_{n/2-1}}, \ldots, \overline{z_0}) \in \mathbb{C}^n$
- Inverse Canonical Embedding: Compute $p = \sigma^{-1}(\tilde{\mathbf{z}})$
- Scaling and Rounding: Scale by $\Delta$ and round to get integer coefficients
The inverse canonical embedding can be computed efficiently using the Vandermonde matrix:
$V = \begin{pmatrix} 1 & \zeta_{2n} & \zeta_{2n}^2 & \cdots & \zeta_{2n}^{n-1} \\ 1 & \zeta_{2n}^3 & (\zeta_{2n}^3)^2 & \cdots & (\zeta_{2n}^3)^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \zeta_{2n}^{2n-1} & (\zeta_{2n}^{2n-1})^2 & \cdots & (\zeta_{2n}^{2n-1})^{n-1} \end{pmatrix}$
Then $\mathbf{p} = V^{-1} \tilde{\mathbf{z}}$, which can be computed using FFT in $O(n \log n)$ time.
Homomorphic Operations
Once we have polynomials encoding our complex vectors, homomorphic operations correspond to:
- Addition: $\text{Enc}(\mathbf{z}_1) + \text{Enc}(\mathbf{z}_2) = \text{Enc}(\mathbf{z}_1 + \mathbf{z}_2)$
- Multiplication: $\text{Enc}(\mathbf{z}_1) \cdot \text{Enc}(\mathbf{z}_2) = \text{Enc}(\mathbf{z}_1 \odot \mathbf{z}_2)$
where $\odot$ is component-wise multiplication.
Discrete Gaussian Distributions and Noise
Here’s where we get into the “why is this secure?” part. The whole security of Ring-LWE comes down to adding the right kind of noise to our encryptions.
The Noise Intuition
Think of noise in encryption like static on a radio. If you’re trying to eavesdrop on a radio transmission, a little bit of static makes it hard to understand, but the intended recipient (who knows what to listen for) can still decode the message.
But here’s the crucial insight: not all noise is created equal. Random uniform noise would work, but it turns out that Gaussian noise is optimal for lattice-based cryptography. Why? Because it plays nicely with the geometric structure of lattices.
Discrete Gaussian Distribution: Nature’s Favorite Noise
The discrete Gaussian distribution $D_{\mathbb{Z}, \sigma}$ is like a bell curve, but restricted to integers. Picture a normal distribution centered at 0, and then only keep the probability mass at integer points.
The parameter $\sigma$ controls the “width” of the bell curve:
- Small $\sigma$: Noise is concentrated near 0 (good for correctness, bad for security)
- Large $\sigma$: Noise is spread out (good for security, bad for correctness)
Mathematically: $\Pr[x] \approx \frac{1}{\sigma} \exp(-\pi x^2 / \sigma^2)$
Why Gaussian? The Geometric Intuition
Here’s the deep reason why Gaussian noise is special: it’s the “most round” distribution.
When we add Gaussian noise to each coefficient of our polynomial, we’re essentially placing our secret in a “fuzzy cloud” that looks the same from every direction. This isotropy (rotational symmetry) is exactly what we need to make lattice problems hard.
If we used, say, uniform noise on ${-B, \ldots, B}$, our noise cloud would be cube-shaped, and cubes have corners where an attacker might find patterns. Gaussian clouds are perfectly round - no corners to exploit!
Error Polynomial Sampling
For Ring-LWE, we sample error polynomials $e(X) = \sum_{i=0}^{n-1} e_i X^i$ where each coefficient $e_i \leftarrow D_{\mathbb{Z}, \sigma}$ independently.
The norm of the error polynomial in the canonical embedding is:
$\|\sigma(e)\|_{\infty} = \max_{i} |e(\zeta_{2n}^{2i+1})|$
By concentration inequalities, with high probability:
$\|\sigma(e)\|_{\infty} \leq \sigma \sqrt{n \log n}$
This bound is crucial for correctness - we need the noise to be small enough that decryption works, but large enough for security.
Security Foundations: Ideal Lattices
Now for the million-dollar question: why is Ring-LWE hard to break? The answer lies in geometry - specifically, the geometry of high-dimensional lattices.
The Lattice Intuition
Think of a lattice as a regular arrangement of points in space, like the integer grid $\mathbb{Z}^2$ in the plane. But instead of 2D, we’re working in $n$-dimensional space where $n$ might be 1024 or 4096.
When we use Ring-LWE, we’re essentially hiding our secret in the lattice structure. The Ring-LWE samples give an adversary some information about which lattice we’re using, but not enough to reconstruct the secret.
From Polynomials to Geometric Points
Here’s the key connection: every polynomial $p(X) = \sum p_i X^i$ corresponds to a point $(p_0, p_1, \ldots, p_{n-1})$ in $n$-dimensional space via the coefficient embedding.
The polynomial ring structure gives us a lattice with special properties - it’s not just any random lattice, but an ideal lattice with tons of symmetry. This extra structure is both a blessing (it makes things efficient) and potentially a curse (it might make attacks easier).
The Fundamental Lattice Problems
Breaking Ring-LWE is equivalent to solving one of these problems on ideal lattices:
- Shortest Vector Problem (SVP): Given a lattice, find the shortest non-zero vector
- Closest Vector Problem (CVP): Given a lattice and a target point, find the closest lattice point
In 2D, these problems are easy - you can just look at the lattice and see the answer. But in 1024-dimensional space? Good luck! The number of lattice points to check grows exponentially with dimension.
Worst-Case to Average-Case Reduction
Here’s the beautiful part: Lyubashevsky, Peikert, and Regev showed that solving Ring-LWE on average is as hard as solving worst-case problems on ideal lattices.
Specifically, there’s a quantum reduction from:
- Worst-case: $\gamma$-approximate Shortest Vector Problem (SVP) on ideal lattices in $\mathbb{Z}[X]/(X^n + 1)$
- Average-case: Ring-LWE with Gaussian error width $\sigma = \gamma \cdot \text{poly}(n)$
This gives us confidence that Ring-LWE is hard even against quantum adversaries (though the reduction is quantum).
Geometry of the Canonical Embedding
The canonical embedding $\sigma$ maps the ring to $\mathbb{C}^n$, but we can view this as $\mathbb{R}^{2n}$ by separating real and imaginary parts.
The key insight is that $\sigma$ is an isometry up to scaling: for any $p \in R$:
$\|\sigma(p)\|_2^2 = n \cdot \|p\|_2^2$
where $|p|2^2 = \sum{i=0}^{n-1} p_i^2$ is the coefficient norm.
This geometric structure is what makes lattice algorithms like LLL and BKZ work on ideal lattices.
Parameter Selection and Trade-offs
Choosing parameters for Ring-LWE schemes involves balancing security, correctness, and efficiency.
Security Level
The security level depends on the root Hermite factor $\gamma$ of the best known lattice attacks. For $\lambda$-bit security, we need:
$\gamma^{2n} \geq 2^{\lambda / 2}$
Current estimates give $\gamma \approx 1.0045$ for BKZ attacks, so for 128-bit security:
$n \geq \frac{\lambda}{2 \log_2(\gamma)} \approx \frac{128}{2 \cdot 0.0065} \approx 10000$
But this is overly conservative. Practical parameter sets like those in Microsoft SEAL use $n \in {1024, 2048, 4096, 8192}$ with carefully chosen moduli.
Modulus Selection
The ciphertext modulus $q$ needs to be large enough to:
- Avoid Modular Reduction Errors: $q > \sigma \sqrt{n} \cdot 2^{\text{depth}}$
- Enable NTT: $q \equiv 1 \pmod{2n}$ for efficient polynomial multiplication
- Resist Attacks: Not too small relative to $n$
A common approach is to use a product of primes: $q = \prod_{i=1}^k q_i$ where each $q_i \equiv 1 \pmod{2n}$.
Noise Growth Analysis
In CKKS, after $d$ levels of multiplication, the noise magnitude grows roughly as:
$\text{Noise} \approx \sigma \cdot n^{d/2} \cdot B^d$
where $B$ is the bound on message coefficients. This exponential growth limits the multiplicative depth.
Implementation Considerations
Number Theoretic Transform
Polynomial multiplication in $\mathbb{Z}_q[X]/(X^n + 1)$ can be done efficiently using NTT. For this to work, we need:
- $q \equiv 1 \pmod{2n}$
- A primitive $2n$-th root of unity $\omega$ in $\mathbb{Z}_q$
Then NTT is just FFT over $\mathbb{Z}_q$, giving us $O(n \log n)$ polynomial multiplication.
Memory and Bandwidth
Ciphertext size is a practical concern. A Ring-LWE ciphertext consists of two polynomials, so $2n \log q$ bits. For $n = 4096$ and $\log q = 200$, that’s about 200KB per ciphertext.
Techniques like ciphertext packing and batching help amortize this cost across multiple plaintexts.
Precision and Scaling
CKKS uses fixed-point arithmetic, so precision loss accumulates. The precision budget determines how many operations you can perform before precision becomes unacceptable.
After each multiplication, you typically need to rescale by dividing by some factor (and rounding), which reduces the ciphertext modulus but maintains precision.
The math here gets pretty involved, but basically you’re managing a trade-off between precision, noise, and remaining multiplicative depth.
Looking Ahead
This foundation sets us up perfectly for understanding more advanced topics like:
- Automorphisms: How to rotate encrypted data using Galois theory
- Key Switching: Converting between different key representations
- Bootstrapping: Refreshing noise to enable unlimited computation
- Multi-Party Computation: Distributed computation on encrypted data
The algebraic structure we’ve explored - cyclotomic rings, canonical embeddings, discrete Gaussians - forms the mathematical backbone of all these techniques.
I have to say, working through this math really drives home how elegant modern cryptography is. Like, the fact that we can pack complex numbers into polynomials, perform arithmetic homomorphically, and base security on lattice problems - it’s just beautiful mathematics serving practical ends.
In my next post, I’ll dive into automorphisms and key switching, building directly on these foundations. The Galois group action on cyclotomic rings gives us this incredible ability to rotate encrypted data, but it comes with the price of changing the encryption key. Key switching is the technique that lets us convert back to the original key, and the math behind it is pretty wild.
Anyway, hope this gives you a solid mathematical foundation for understanding modern FHE schemes. There’s obviously way more depth here - ideal lattices, algebraic number theory, concrete security analysis - but this should be enough to follow the more advanced techniques.
peace. da1729
References
[1] Lyubashevsky, V., Peikert, C., & Regev, O. (2010). On ideal lattices and learning with errors over rings. In Annual international conference on the theory and applications of cryptographic techniques (pp. 1-23). Springer.
[2] Cheon, J. H., Kim, A., Kim, M., & Song, Y. (2017). Homomorphic encryption for arithmetic of approximate numbers. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 409-437). Springer.
[3] Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2012). (Leveled) fully homomorphic encryption without bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (pp. 309-325).
[4] Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6), 1-40.
[5] Peikert, C. (2016). A decade of lattice cryptography. Foundations and Trends in Theoretical Computer Science, 10(4), 283-424.
[6] Micciancio, D., & Regev, O. (2009). Lattice-based cryptography. In Post-quantum cryptography (pp. 147-191). Springer.
[7] Smart, N. P., & Vercauteren, F. (2014). Fully homomorphic SIMD operations. Designs, codes and cryptography, 71(1), 57-81.
[8] Halevi, S., & Shoup, V. (2014). Algorithms in HElib. In Annual Cryptology Conference (pp. 554-571). Springer.