Post-Quantum Cryptography in Python: Learning With Errors (LWE), Regev Encryption, and Why It Resists Quantum Computers

Introduction

https://yuhi-sa.github.io/en/posts/20260614_cryptography_roadmap/1/ listed “Post-Quantum Cryptography (CRYSTALS-Kyber / Dilithium)” as the final placeholder for a future article. This article implements it. The factoring problem behind https://yuhi-sa.github.io/en/posts/20260225_rsa/1/ and the discrete-log problems behind https://yuhi-sa.github.io/en/posts/20260614_diffie_hellman/1/ and https://yuhi-sa.github.io/en/posts/20260702_elliptic_curve_cryptography/1/ are all known to be solvable in polynomial time on a quantum computer via Shor’s algorithm. This article examines why the Learning With Errors (LWE) problem is believed to resist quantum computers too, by implementing Regev encryption (an LWE-based public-key cryptosystem) from scratch and running numerical experiments.

Why Quantum Computers Are a Threat: Shor’s Algorithm

RSA, Diffie-Hellman, and ECC all derive their security from the assumption that certain number-theoretic problems (factoring, discrete logarithm) cannot be solved efficiently on a classical computer. What Peter Shor showed in 1994 was that efficient (polynomial-time) algorithms for these problems exist on a quantum computer. This means that once a sufficiently large quantum computer exists, RSA-, DH-, and ECC-based cryptography currently in use would in principle all become breakable. This is why the transition to Post-Quantum Cryptography (PQC), designed to resist quantum computers, is underway. NIST finalized lattice-based CRYSTALS-Kyber (key encapsulation, standardized as FIPS 203) and CRYSTALS-Dilithium (signatures, FIPS 204) as standards in 2024.

The Learning With Errors (LWE) Problem

The foundation of many post-quantum schemes, including Kyber, is the LWE problem, proposed by Oded Regev in 2005. Intuitively, it exploits the property that “mixing a small amount of noise into a system of linear equations makes solving it dramatically harder.”

LWE problem definition: given a secret vector \(\mathbf{s} \in \mathbb{Z}_q^n\) , a random matrix \(A \in \mathbb{Z}_q^{m \times n}\) , and a small error vector \(\mathbf{e} \in \mathbb{Z}_q^m\) (each component drawn from, e.g., a normal distribution), compute

Given \((A, \mathbf{b})\) , find \(\mathbf{s}\) . Without the error term \(\mathbf{e}\) , for \(m \geq n\) this is trivial: just solve the linear system (modular linear algebra) to find \(\mathbf{s}\) uniquely. With the error added, this simple approach breaks down, and the problem is instead shown to reduce to a hard lattice problem (such as the shortest vector problem). No known quantum algorithm — including Shor’s — is believed to solve this lattice problem efficiently.

Regev Encryption: LWE-Based Public-Key Encryption (Single-Bit Version)

The LWE problem’s hardness can be used to construct a public-key cryptosystem, as follows (a simplified version of Regev, 2005).

Key generation: choose a secret key \(\mathbf{s} \in \mathbb{Z}_q^n\) at random. The public key is the LWE instance \((A, \mathbf{b} = A\mathbf{s} + \mathbf{e})\) .

Encryption (encrypting a single bit \(b \in \{0,1\}\) ): choose a random subset \(\mathbf{r} \in \{0,1\}^m\) , and compute

as the ciphertext.

Decryption: compute

Since \(\mathbf{r}^\top\mathbf{e}\) is small (a sum of error terms), the result is close to \(0\) if \(b=0\) and close to \(q/2\) if \(b=1\) .

Python Implementation

import numpy as np

n, q, m, sigma = 32, 3329, 128, 2.0  # toy parameters (q matches Kyber's modulus)

def sample_error(size, sigma, q):
    e = np.round(rng.normal(0, sigma, size)).astype(np.int64) % q
    return e

def keygen():
    s = rng.integers(0, q, size=n)
    A = rng.integers(0, q, size=(m, n))
    e = sample_error(m, sigma, q)
    b = (A @ s + e) % q
    return (A, b), s

def encrypt(pub, bit, q):
    A, b = pub
    r = rng.integers(0, 2, size=A.shape[0])
    u = (r @ A) % q
    v = (int(r @ b) + bit * (q // 2)) % q
    return u, v

def decrypt(sk, ct, q):
    u, v = ct
    raw = (v - int(u @ sk)) % q
    return 1 if abs(raw - q // 2) < q // 4 else 0

Experiment 1: Verifying Decryption Correctness

Using toy parameters \(n=32\) (lattice dimension), \(q=3329\) (the same modulus Kyber uses), \(m=128\) (LWE samples in the public key), and \(\sigma=2.0\) (error standard deviation), we ran 2000 trials of encrypting and decrypting a random bit.

correct decryptions: 2000/2000 (100.00%)

All 2000 trials decrypted correctly. With a small enough error, the legitimate recipient (who knows the secret key \(\mathbf{s}\) ) can always decrypt successfully.

Experiment 2: The Noise σ vs. Correctness Trade-Off

The central design dilemma in post-quantum cryptography is that “a larger error \(\mathbf{e}\) is more secure (the LWE problem gets harder), but too large and even the legitimate recipient fails to decrypt.” We swept \(\sigma\) and measured mean decryption accuracy over 5 key generations × 300 encrypt/decrypt trials each.

Decryption accuracy declines monotonically as \(\sigma\) grows, degrading to roughly 50% (equivalent to guessing a random bit) at \(\sigma=200\) . This quantitatively demonstrates the fundamental trade-off in LWE-based cryptosystem design: increasing the error to improve security destroys correctness. Real Kyber carefully tunes this trade-off, using a far more sophisticated error distribution and parameter selection than this toy implementation, to keep the decryption failure probability around \(2^{-140}\) while maintaining strong security.

Experiment 3: Without the Error, the Secret Key Is Recovered Instantly

To directly confirm that LWE’s hardness comes specifically from the error term, we tested whether the secret key could be recovered in the error-free case (\(\mathbf{b} = A\mathbf{s}\) , an ordinary linear system).

import sympy

A0 = np.array(rng.integers(1, q, size=(n, n)))
s_true = rng.integers(0, q, size=n)
b0 = (A0 @ s_true) % q  # no error term

A0_inv_mod = sympy.Matrix(A0.tolist()).inv_mod(q)  # matrix inverse mod q
s_recovered = np.array([int(x) for x in (A0_inv_mod * sympy.Matrix(b0.tolist())) % q]).flatten()

max |recovered - true| (should be 0): 0
s fully recovered: True

Computing the matrix inverse mod \(q\) recovered the secret key completely and instantly. This shows that an error-free system of equations is solvable by simple linear algebra (\(O(n^3)\) ). The error is essential to the LWE problem’s hardness — it’s exactly what enables the reduction to the “shortest vector problem on a lattice,” a problem with no known efficient solution, even on a quantum computer.

Relationship to CRYSTALS-Kyber

The Regev encryption in this article is a simplified, pedagogical version: it can only encrypt one bit at a time, and the public key grows as \(O(nm)\) . Real CRYSTALS-Kyber solves this by using LWE over a polynomial ring (Module-LWE). Instead of integer vectors, it uses elements of the polynomial ring \(\mathbb{Z}_q[x]/(x^n+1)\) , and instead of matrix operations, polynomial multiplication (which pairs well with fast NTT — Number Theoretic Transform — acceleration). This dramatically reduces key size and computation while allowing multiple bits to be encrypted at once. The core properties this toy implementation confirmed — that the error is the source of hardness, and that error size trades off against correctness — hold just as much for Module-LWE.

Related Articles

• Cryptography Roadmap: Classical Ciphers, Symmetric Keys, RSA, Diffie-Hellman, Elliptic Curves, Hashing, Signatures, and TLS in Python - This article implements the final one of this hub’s “planned for the future” placeholders.
• RSA in Python: theory, key generation, encryption, decryption - A factoring-based cryptosystem broken by Shor’s algorithm.
• Diffie-Hellman Key Exchange: Theory and Implementation - A discrete-log-based key exchange broken by Shor’s algorithm.
• Elliptic Curve Cryptography (ECC): Math and Python Implementation - Covers the elliptic-curve discrete-log problem (ECDLP), another target of Shor’s algorithm.
• Dissecting the TLS 1.3 Handshake in Python - Provides context for how today’s ECDHE-based handshake could eventually migrate to Kyber-based key exchange.

References

• Regev, O. (2005). On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC).
• Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484-1509.
• National Institute of Standards and Technology (2024). Module-Lattice-Based Key-Encapsulation Mechanism Standard. FIPS 203 (CRYSTALS-Kyber).
• National Institute of Standards and Technology (2024). Module-Lattice-Based Digital Signature Standard. FIPS 204 (CRYSTALS-Dilithium).