Lattice Cryptography: LWE in Practice

Implement a toy LWE-based key exchange to understand post-quantum security.

Lattice Cryptography: LWE in Practice

Learning With Errors (LWE) is the mathematical foundation of CRYSTALS-Kyber, the NIST post-quantum key encapsulation standard. Understanding LWE from the ground up reveals why it is hard for both classical and quantum computers.

The LWE Problem

Given:

•A public random matrix A (n × n integers mod q)
•A secret vector s (n integers mod q)
•A vector b = A·s + e (mod q), where e is a small "error" vector

LWE problem: Find s, given only A and b.

If $e = 0$ , this is just linear algebra: $s = A^{- 1} b (mod q)$ , solvable in $O (n^{3})$ time. The error vector e, each component drawn from a small Gaussian distribution, makes the problem computationally hard. The error "perturbs" b away from the nearest lattice point, making lattice reduction algorithms struggle.

Why LWE Is Hard

The security reduction: breaking LWE (even with quantum computers) is as hard as solving worst-case lattice problems like GapSVP (approximating the shortest vector in a random lattice). These lattice problems have been studied for 40+ years with no polynomial-time algorithms found classically or quantum mechanically.

Intuition: b looks like random noise. Distinguishing A·s + e from a uniformly random vector is computationally indistinguishable, this is the "decision LWE" hardness assumption.

LWE-Based Encryption

Simple LWE public-key encryption:

Key generation:

•Secret: s (small random vector)
•Public: (A, b) where b = A·s + e

Encryption of bit m:

•Choose random vector r
•Ciphertext: $(c_{1}, c_{2}) = (A^{T} \cdot r, b^{T} \cdot r + m \times ⌊ q /2 ⌋)$

Decryption:

•Compute $v = c_{2} - s^{T} \cdot c_{1} = m \times ⌊ q /2 ⌋ + small error$
•Round to 0 or ⌊q/2⌋ to recover m

The small error from both the LWE noise and the random vector r cancels in the decryption formula, but the product is still close enough to round correctly.

This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.

How this lesson works

A hands-on coding challenge. You write Qiskit-compatible Python in the browser editor, run it instantly via WebAssembly, watch the circuit and Bloch sphere react, and pass automatic output checks. The AI tutor Qubitus gives Socratic hints if you get stuck.

Part of: Quantum Cryptography

Master quantum key distribution, the threat quantum computers pose to classical cryptography, and post-quantum cryptographic standards.

Previous lessonPost-Quantum Cryptography Standards Next lessonQuantum-Safe Hash Functions

This lesson is part of Pro

Unlock Quantum Cryptography and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.

Create account Try the Playground