LWE Cipher — Learning With Errors: Post-Quantum Cryptography

1 2 3 4 5 6 7

difficulty levels — click green to claim

> LWE CIPHER — LEARNING WITH ERRORS

lwe difficulty: 3–7 field: post-quantum cryptography

The idea in plain English: Imagine you're trying to solve a system of equations like the ones you learned in school — but each equation has a small mistake (error) added to it. You know the answers (the right side of each equation) are slightly wrong, but the error is small. Given enough equations, statistics can average out the errors and recover the true solution. LWE does this with modular arithmetic — wrapping around like a clock.

Why this really exists: LWE is THE foundation of post-quantum cryptography. In 2024, NIST (the US standards body) selected Kyber (encryption) and Dilithium (signatures) as the official post-quantum algorithms — both based on LWE and its variant. When quantum computers arrive, they'll break RSA and ECC instantly, but LWE-based systems will remain secure. Your messaging apps and bank will need to switch to these within the next decade.

▸ Concrete Example

Say we have a secret s = [72, 69] (the letters "HE").

Equations without errors:
2×72 + 3×69 = 144 + 207 = 351 ≡ 62 (mod 97)
5×72 + 1×69 = 360 + 69 = 429 ≡ 41 (mod 97)
7×72 + 2×69 = 504 + 138 = 642 ≡ 60 (mod 97)

With small errors (LWE):
2×72 + 3×69 + 1 = 63 (mod 97) ← error +1
5×72 + 1×69 - 1 = 40 (mod 97) ← error -1
7×72 + 2×69 + 0 = 60 (mod 97) ← error 0

Solve using least-squares → approximate → round → "HE"

With enough equations (more than unknowns), the errors cancel out statistically.

▸ How to Solve (Step by Step)

1. Get matrix A and vector b from puzzle data. Modulus Q is a small prime

2. If error_scale = 0 (no noise): do Gaussian elimination over Z_Q (exact solve)

3. If noise is present: use least-squares over real numbers, then round modulo Q

4. Convert each entry of s to ASCII → join → the answer word

import numpy as np

if error_scale == 0:
  # Exact Gaussian elimination over Z_Q
  A_sq = np.array(A[:n])
  b_sq = np.array(b[:n])
  s = (np.linalg.inv(A_sq) @ b_sq) % Q
else:
  # Least-squares + round
  s_float, _, _, _ = np.linalg.lstsq(A, b, rcond=None)
  s = np.round(s_float).astype(int) % Q

word = ''.join(chr(int(v)) for v in s)

▸ Real-World Applications

Kyber (ML-KEM): NIST's chosen post-quantum encryption standard
Dilithium (ML-DSA): NIST's chosen post-quantum signature standard
Homomorphic encryption: Allows computation on encrypted data — also built on LWE
Fully homomorphic encryption (FHE): Cloud computing on encrypted data without decryption

← Back to all ciphers