← Index fig. 5

Quantum-Resistant Encryption over Polynomial Rings

how Ring-LWE turns polynomial arithmetic into a quantum-resistant hardness assumption

Year
2025
Kind
Research
Role
research project
With
Stanford SUMaC
Tools
Abstract Algebra, Lattices, LaTeX
A two-dimensional lattice of orange points with two different pairs of basis vectors, one short and one skewed, generating the same lattice

Most of the encryption on the internet today (RSA, elliptic curves) rests on problems like factoring big numbers. Those are hard for normal computers and easy for a big enough quantum computer, thanks to Shor’s algorithm. So there’s a race to replace them with problems that stay hard either way. One of the main candidates comes out of abstract algebra: Ring Learning with Errors.

I spent my research project at Stanford’s SUMaC in July 2025 working through how it works, from the ring arithmetic up to why breaking it means solving a hard lattice problem, and then presented what I’d found.

TLDR: Ring-LWE hides a secret polynomial by multiplying it with a public one and adding a little noise. Without the secret, the noise makes it look random; with it, the noise can be rounded away. I wrote up the scheme, worked a full encrypt–decrypt example by hand in a tiny ring, compared it with plain LWE, and traced the security back to lattices.

The ring

Everything happens with polynomials whose coefficients wrap around mod a prime q, and where xⁿ wraps around to −1. That second rule (the ring is 𝔽q[x]/(xⁿ + 1)) means multiplying two polynomials never makes the degree grow, so every key and ciphertext is just a list of n numbers.

Page one of typeset LaTeX notes titled SUMaC Research Project Notes, describing key generation, encryption and decryption
Page one of my notes: the whole scheme in one page.

The scheme, in words

Keys. Pick a secret polynomial s with small coefficients. Pick a random public polynomial a, and a small error e. Publish a and b = a·s + e. Anyone can see b, but separating a·s from e is the hard problem.

Encrypting. Scale the message up by Δ = ⌊q/k⌋ so it sits far away from the noise. Pick fresh small polynomials u, e₁, e₂ and send two pieces: c₀ = b·u + e₁ + Δm and c₁ = a·u + e₂.

Decrypting. Compute c₀ − c₁·s. The two big a·s·u terms cancel exactly, and what’s left is Δm plus a pile of small noise: e·u + e₁ − e₂·s. Round each coefficient to the nearest multiple of Δ and divide, and the message falls out.

Someone without s can’t make the a·s·u terms cancel. Plug in any other polynomial and a large, random-looking term survives, and rounding gives garbage.

Working it by hand

The notes have a full example in the smallest ring that still shows everything: n = 4, q = 17, Δ = 8. The message is the four bits 0101, written as the polynomial x² + 1.

Here it is re-run in a few lines of Python, to check every step of the arithmetic.

Terminal output listing the ring, public key, two ciphertext polynomials, the decrypted polynomial and the recovered bits 0101
The toy example, re-run. c₀ − c₁·s = x³ + 8x² + 7; round each coefficient to a multiple of 8 and you get 8x² + 8, which is x² + 1, which is 0101.

How much noise is too much

Decryption only works if the leftover noise stays under Δ/2 in every coefficient. If every small polynomial has coefficients between −η and η, then each coefficient of a product like e·u is a sum of n terms of size at most η². So the noise is at most η + 2nη², and that has to stay below Δ/2.

That’s also why the toy example is a toy. With n = 4 and η = 1 the bound is 9, more than Δ/2 = 4, so nothing guarantees it decrypts. This particular noise came out small. Real parameters pick q large enough that the bound always holds.

Ring-LWE against plain LWE

Plain LWE does the same thing with vectors and a big random matrix. It’s well understood, but the keys are huge: an n×n matrix is O(n²) numbers. The ring version replaces the matrix with one polynomial, O(n) numbers, and multiplies with the number-theoretic transform in O(n log n). That’s why the schemes being standardised now, like Kyber, use ring and module variants. The cost is more algebraic structure, which is more for an attacker to work with.

Where the hardness comes from

A lattice is every integer combination of a few basis vectors. The same lattice can have a nice basis (short, nearly perpendicular vectors) or a terrible one (long, skewed ones), and both generate exactly the same points. That’s the cover image: green and blue are two bases of one lattice.

The closest vector problem asks: given a point that isn’t on the lattice, which lattice point is nearest? With a good basis it’s easy. With a bad basis in hundreds of dimensions, nobody knows how to do it efficiently, classically or with a quantum computer.

A lattice of points with a target point circled; two long pink vectors miss it and a green vector reaches the nearest lattice point
The closest vector problem: find the lattice point nearest the circled target.

The link back to Ring-LWE is a lemma from the notes. Every ideal of the ring ℤ[x]/(f), with f of degree n, is isomorphic to a full-rank lattice in ℤⁿ. Recovering the secret from b = a·s + e is a noisy closest-vector problem on one of those ideal lattices, and that’s a problem believed to be hard even for quantum computers.