Skip to content
CryptoVault

Chapter IX

The frontier

Quantum computers, noisy lattices, proofs that reveal nothing, and computing on data you cannot see.

  1. IX.1The quantum threat
  2. IX.2Post-quantum standards
  3. IX.3Lattices and LWE
  4. IX.4Zero-knowledge proofs
  5. IX.5Secret sharing
  6. IX.6Computing on encrypted data

The quantum threat

Shor’s algorithm would break RSA, Diffie-Hellman and elliptic curves. Grover only halves symmetric strength, so AES-256 stays safe.

Public-key cryptography rests on factoring (RSA) and discrete logarithms (Diffie-Hellman, elliptic curves). Shor’s algorithm solves both in polynomial time; to factor N, it finds the period of ax mod N.

the quantum part: find the periodx0123456787ˣ mod 1517413174131r = 4r = 472 mod 15 = 4− 1+ 1gcd(3, 15) = 3gcd(5, 15) = 515 = 3 × 5
The quantum computer only finds the period; listing powers takes up to N steps, hopeless for a 617-digit N.
128 bits, the usual barGrover: square-root speed-upAES-128128 → 64AES-256256 → 128SHA-256 preimage256 → 128Shor: polynomial timeRSA-2048112 → brokenX25519, Ed25519, P-256128 → broken
Outline: bits of security today; filled: what is left against a large quantum computer.

Traffic recorded today can be decrypted once one exists (“harvest now, decrypt later”): key exchange migrates first.

Post-quantum standards

ML-KEM for key exchange, ML-DSA and SLH-DSA for signatures: NIST’s 2024 standards. Only ML-KEM is in wide use so far, beside X25519.

A KEM (key encapsulation mechanism) replaces Diffie-Hellman: your public key wraps a fresh secret only you can unwrap. TLS runs ML-KEM beside X25519: an attacker must break both. SLH-DSA, built only from hash functions, is the cautious backup.

public keyreply or signaturekey exchange: public key, then replyX255193232ML-KEM-7681,1841,088X25519MLKEM7681,2161,120signatures: public key, then signatureEd255193264RSA-2048256256ML-DSA-441,3122,420ML-DSA-651,9523,309SLH-DSA-128s327,856
Bytes on the wire, to scale: one ML-DSA-44 signature weighs as much as 38 Ed25519 signatures.
PitfallPost-quantum is not quantum cryptography: these algorithms run on ordinary computers.

Lattices and LWE

Linear equations are easy to solve. Add a little noise to each and they become hard, as far as we know even for quantum computers.

Given exact equations a·s = b, elimination finds s at once. Add a small error to each, modulo q, and with hundreds of unknowns every known algorithm, classical or quantum, takes exponential time. ML-KEM and ML-DSA rest on this.

Asebpublicsecretpublic11694+1252675039−193452353+155470251502357450190256352851+1367289424+1578851813043152853·+=mod 97encrypt 1: add rows 1, 3, 4, 7u = (47, 51, 89)v = Σb + 48 = 14decrypt, with s:v − u·s = 5104897bit 0bit 1bit 0
Without e, three rows would give s by elimination; with it, only the key holder can round 51 to 48, a 1.
Try it: turn the noise up and down
aeb = a·s + e
( 1, 6, 94)+125
(67, 50, 39)-19
(45, 23, 53)+155
(70, 25, 15)023
(74, 50, 19)025
(35, 28, 51)+136
(28, 94, 24)+157
(85, 18, 13)043

The secret is s = (15, 28, 53). Solving the first three equations as if they were exact gives (4, 38, 69): wrong, and nothing says by how much.

Decryption works for 510 of 510 possible encryptions.

Zero noise: plain linear algebra, broken. Small noise: hard for the attacker, harmless for the key holder. Too much: the errors add up past q/4 and decryption itself fails. Real schemes live in the middle, with hundreds of dimensions.

Noise is the whole trick: small enough for the key holder to round away, large enough to defeat linear algebra.

Zero-knowledge proofs

Convince someone that a statement is true, for instance that you know a secret, without revealing anything else.

Picture a ring-shaped cave whose two paths meet at a door only a magic word opens.

Try it: Ali Baba’s cave

The prover has walked in, out of sight, by path A or B. You stand at the entrance and shout which path to come back by.

ABdoor

Complete: the honest prover always passes. Sound: a bluffer fails half the rounds. Zero-knowledge: the verifier learns nothing it could not have faked. Schnorr’s protocol, with numbers:

AAliceBBobg = 2, p = 23, y = 13Alice claims to know x with gˣ = yx = 7r = 9t = 29 mod 23 = 6t = 6commitc = 4, randomc = 4challenges = 9 + 4·7 mod 11 = 4s = 4responseBob checks gˢ = t·yᶜ24 mod 23 = 166·134 mod 23 = 16equal: accepted
Exponents are reduced mod 11, the order of g; r must be fresh, since two answers to the same t would reveal x.

Hash t and a message to get c (Fiat-Shamir): the proof becomes a signature, as in Ed25519.

Secret sharing

Split a secret into n shares so that any k of them rebuild it, and k − 1 learn nothing at all.

Two points fix a line, three a parabola. To let any k of n trustees rebuild a key, hide it as f(0) of a random polynomial of degree k − 1; trustee i gets the point (i, f(i)).

012345f(x) = 40 + 90x − 12x2 mod 257dashed: through shares 2 and 4 only120?200?(1, 118)(2, 172)(3, 202)(4, 208)(5, 190)40the secret, f(0)
Three shares fix the parabola and so f(0); through only two, a parabola passes for every possible secret.
PitfallRebuilding the key on one machine brings back the single point of failure: threshold signatures never assemble it.

Computing on encrypted data

Homomorphic encryption lets a server compute on ciphertexts and return an encrypted result it never saw in the clear.

In Paillier’s scheme, multiplying two ciphertexts adds the plaintexts; textbook RSA (chapter V) multiplies them.

AAliceservern = 323multiplies mod n2 = 104,32920encrypt, r = 5E(20) = 2521722encrypt, r = 11E(22) = 4187×=E(42) = 2631decrypt42
The server worked on 25217 and 4187 only: it never saw 20, 22 or 42.

Fully homomorphic schemes, built on lattices, allow any computation, at orders of magnitude the cost.

PitfallHomomorphic means malleable: anyone can multiply in E(1000) and add 1000 to a sealed bid.

In one breath

  1. The quantum threat. Shor’s algorithm would break RSA, Diffie-Hellman and elliptic curves. Grover only halves symmetric strength, so AES-256 stays safe.
  2. Post-quantum standards. ML-KEM for key exchange, ML-DSA and SLH-DSA for signatures: NIST’s 2024 standards. Only ML-KEM is in wide use so far, beside X25519.
  3. Lattices and LWE. Linear equations are easy to solve. Add a little noise to each and they become hard, as far as we know even for quantum computers.
  4. Zero-knowledge proofs. Convince someone that a statement is true, for instance that you know a secret, without revealing anything else.
  5. Secret sharing. Split a secret into n shares so that any k of them rebuild it, and k − 1 learn nothing at all.
  6. Computing on encrypted data. Homomorphic encryption lets a server compute on ciphertexts and return an encrypted result it never saw in the clear.