Authentication in a post-quantum world

Digital authentication rests on a simple premise: proving you are who you claim to be. In the physical world, we rely on faces, voices, or trusted introductions. Online, the problem is harder. When you connect to your bank, TLS uses digitally signed certificates to assure you that you are talking to the bank—not an impostor. DNSSEC uses the same idea to prevent forged DNS data and cache poisoning.

A digital signature scheme is built from three algorithms:

  1. Generate—produces a public verification key and a private signing key.
  2. Sign—takes the private key and a message, and outputs a signature.
  3. Verify—takes the public key, the signature, and the message, and decides whether the signature is valid.

In TLS, authentication happens at connection setup. This makes the move to post-quantum signatures less urgent than the switch to post-quantum key exchange, since an attacker would need a powerful quantum computer to forge signatures today. That window will close eventually, and the transition will become necessary.

Post-quantum signature candidates come from several families: hash-based, lattice-based, multivariate, and multi-party computation. Key Encapsulation Mechanisms (KEMs) can also be repurposed for authentication. As a concrete example of a lattice-based design, CRYSTALS-Dilithium is a finalist in the NIST post-quantum cryptography standardization process. Its construction is instructive because it follows a standard recipe: a hard mathematical problem, an identification scheme built on it, and a transform that converts the interactive protocol into a non-interactive signature.

Blogpost around what is a post-quantum signature scheme.

The mathematical foundation: SIS and lattices

Dilithium's security rests on two hard problems: a variant of Learning with Errors (LWE) and the Short Integer Solution (SIS) problem. LWE is familiar from post-quantum KEM designs. SIS deserves a closer look.

A lattice is a periodic arrangement of points in n-dimensional space. The SIS problem asks: given a matrix A of dimension n x m with entries between 0 and q, find a non-zero vector r—bounded in size—such that Ar = 0. For large n, this is believed to be hard even for quantum computers. The problem is dual to LWE, which asks for a vector s such that As + e = b for a small error e.

Over a lattice, SIS becomes the Short Vector Problem (SVP): find the shortest non-zero vectors in a lattice L(A). In two dimensions this is trivial to visualize and solve; in higher dimensions it becomes computationally infeasible. SIS underpins one-way functions, collision-resistant hashes, and digital signatures.

picture of a lattice.

Identification schemes

Before a signature, there is an identification scheme. This is an interactive protocol between a prover P and a verifier V. The prover holds a key pair; the verifier only sees the public key. Through a series of messages, the prover demonstrates knowledge of the private key without revealing it.

A three-move identification scheme works like this:

  • The prover runs Generate to obtain a key pair.
  • The prover runs Commit, producing a commitment Y tied to the private key, and sends it to the verifier.
  • The verifier runs Challenge, outputting a challenge c—a question testing whether the prover truly holds the key.
  • The prover runs Response, producing an answer z.
  • The verifier runs Verify, accepting or rejecting based on z.

If the cyclops had asked Odysseus for such a proof, the story might have ended differently.

How Dilithium works

Dilithium operates on polynomial rings. A ring R allows addition and multiplication; the size of polynomial coefficients matters for security.

The Generate algorithm creates a k x l matrix A, where each entry is a polynomial in R. It also samples random private vectors s1 and s2. The public key is the pair (A, t), where t = As1 + s2. Recovering the private values from this public data is the Module-LWE (MLWE) problem.

The identification scheme proceeds as follows:

  1. The prover samples a random nonce y with small coefficients, computes Ay, and sets w1 to the high-order bits of the result.
  2. The verifier accepts the commitment and issues a challenge c.
  3. The prover computes z = y + cs1 and performs rejection-sampling checks to keep the scheme secure.
  4. The verifier computes high-order bits of Az − ct and accepts if the coefficients of z stay below the security bound and the result matches w1.

The public key shares this decomposition trick: splitting values into high- and low-order bits reduces the key size.

From interactive to non-interactive

An identification scheme requires both parties to be online. A signature scheme does not. The Fiat–Shamir transformation bridges the gap. Instead of the verifier sending a random challenge c, the prover derives it as a hash H(M || w1) of the message M and the commitment value w1. The interactive protocol collapses into a single message that anyone can verify with the public key.

This constructs a lattice problem instance that only the signer can solve. A signature becomes evidence that the signer possessed the private key at signing time. The proof of security ties back to Module-SIS and the decisional LWE problem.

Alternatives to Dilithium

Dilithium is a strong candidate, but not the only one. Two other families stand out in the NIST process:

  • Falcon—another lattice-based scheme built on NTRU lattices.
  • Rainbow—a multivariate polynomial scheme.

Each offers different trade-offs in key size, signature size, and speed.

Assembling the pieces

Post-quantum signatures and KEMs give us the raw tools. The harder problem is weaving them into existing protocols like TLS. The trade-offs post-quantum algorithms present—larger keys, larger signatures, more computation—mean that careful composition is required. The same way Dilithium layers a hard problem, an identification scheme, and a transform to produce a signature, protocol designers must layer algorithms carefully to build the secure connections we rely on.