Post-quantum digital signatures & the lattice city - what is a lattice and how does ML-DSA work?

Almost everything we trust online is guarded by digital signatures. Your browser accepts a website as being legitimate because a certificate chain verifies the site's digital signature. Your phone installs an update because the package was signed. You can authorize the transfer of cryptocurrencies by proving you own those assets via a digital signature. 

Today, these signatures are usually generated via elliptic curve cryptography (ECC). Two of the most common algorithms are ECDSA and EdDSA. However, a large enough quantum computer, known as a Cryptographically Relevant Quantum Computer (CRQC), breaks the mathematics and thus the trust in these signatures by making it possible to derive a private key from a corresponding public key via Shor’s algorithm.

These machines do not exist yet. But they are coming, and the shift to post-quantum signature schemes is already underway. Waiting until a CRQC shows up, the moment people call Q-Day, is not an option. By the time such a machine exists, many systems will already be exposed because their past signatures can be broken, and those signatures cannot be retroactively fixed.

In August 2024, NIST finalized three post-quantum algorithms: one key-exchange algorithm, Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM), and two digital signature algorithms, Module-Lattice-Based Digital Signature Algorithm (ML-DSA) and Stateless Hash-Based Digital Signature Algorithm (SLH-DSA). Out of the standardized digital signatures, ML-DSA looks set to achieve the widest adoption.

This post shows how, and why, ML-DSA works at the protocol level, how this maps to the actual algorithm under the hood, and gives just enough math without getting lost in complex formulae and lattice mathematics.

Most cryptographers like to think about things in terms of attack vectors. What parts of my system or protocol are subject to an attack? What is the impact of that attack on said system? What can I do to mitigate or fully remove that attack vector? Generally speaking, when it comes to the impact quantum computers will have on cryptography, there are two major attack vectors; harvest-now-decrypt-later and harvest-now-forge-later.

Harvest-now-decrypt-later attacks store classically encrypted data today such that once a CRQC comes online, an adversary can decrypt that data and read the plaintext. For example, imagine a TLS connection between a user and their bank’s server. Once the TLS connection is established, messages between the user and the server are encrypted such that only the user and the bank can read these messages. This is needed so that users can safely pass sensitive information such as passwords and account information. In a harvest-now-decrypt-later attack, an attacker would collect these classically encrypted data packets in order to decrypt them in the future and gain access to a user's account. This attack vector is solved by ensuring that post-quantum algorithms are used in order to establish and encrypt this communication channel. In TLS, ML-KEM is already being widely rolled out today to secure client-server communication. For a great post explaining how ML-KEM works, see here.

A harvest-now-forge-later attack is similar in that an attacker collects data today such as signatures and public keys, in order to forge those signatures with a CRQC later. With a CRQC, an attacker can derive your ECDSA private key from a public key and forge software updates allowing systems to install malicious code, pretend to be your bank so that you send sensitive information they can use to access your account, or authorize the movement of your cryptocurrency to an address they control.

To stay secure against a quantum computer running Shor’s algorithm, we need a new digital signature scheme built on math that quantum attacks can’t solve. ML-DSA is one of those schemes.

It behaves just like the classical signatures we use today. You still generate a key pair, sign messages, and verify signatures, but the math underneath is completely different. The key advantage is that ML-DSA remains safe even if a large-scale quantum computer is built.

The trade-offs are size and speed. ML-DSA keys and signatures are much larger than those from elliptic-curve cryptography, measured in kilobytes instead of bytes, and it takes much longer to create signatures. The NIST standard defines three parameter sets with fixed sizes:

• ML-DSA-44: 1312-byte public key, 2420-byte signature
• ML-DSA-65: 1952-byte public key, 3309-byte signature
• ML-DSA-87: 2592-byte public key, 4627-byte signature

A digital signature convinces a verifier that the holder of a specific private key signed some message, without anyone else being able to fake it. It’s the mathematical version of a handwritten signature or a wax seal, but it’s built so that anyone can check it, and no one can copy it.

When you sign a message digitally, you use a private key that only you know. That private key transforms the message into a short block of data called a signature. Anyone can then use your public key, which doesn’t reveal your secret, to verify that the signature fits the message perfectly. If even one bit of the message changes, the signature stops working.

This simple idea underpins almost everything online. It proves that a software update really came from Apple, that a website really belongs to your bank, or that a blockchain transaction really came from the wallet that owns those coins.

ECC, ECDSA and EdDSA create and verify these signatures using elliptic curves. The signer mixes a one-time value (deterministic or random, depending on the algorithm) with a hash of the message to be signed and their private key. The output from this operation is called the digital signature. All a verifier needs is the signature, your public key, and the message to verify that it was in fact you who signed the message.

ML-DSA accomplishes the same goal without using vulnerable elliptic curves, and instead using lattices. It keeps this Schnorr-style flow of commit, challenge, respond, then verify, but changes how each part is represented and checked. The full reference implementation can be found in FIPS 204.

There are no two ways about it; modern cryptography is hard. It’s built on complex mathematics, never-ending jargon, and formal language that makes it difficult to understand and explain. Older schemes like RSA are relatively easy to teach with some basic mathematics and code, but more modern systems like elliptic curves and lattices get abstract quite quickly and rely heavily on complex mathematics beyond most people's comfort level. 

As such, I will introduce lattices and ML-DSA without (much) math and jargon. However, I will add some math throughout to keep things grounded. It can be skimmed over as needed.

For an excellent piece on how elliptic curves work with minimal mathematics see this post by Nic Carter.

Picture a huge city laid out as a grid, similar to Manhattan. Instead of two directions like north or east, this city has 256 independent directions. You can move north/south, east/west, and 254 other perpendicular directions in order to reach different points. So rather than a location being defined as 3 blocks south from the city center and one block east, directions in our lattice city require 256 directions to define a specific apartment. Inhabitants of our city speak in terms of routes, locations, and skyline photos:

• A route, called a vector in the algorithm, is a list of 256 steps in each direction.
• A location, called a lattice point in the algorithm, is where that route ends.
• A skyline photo from a location is a rough summary of that location that hides the exact coordinates. It is the blurred, simplified view you get when you look out from that spot in the city. Only this skyline photo is ever shared, so the exact coordinates remain hidden. In technical terms, this is a cryptographic hash of a rounded location. A hash function turns any data into a short, fixed-size tag. You can’t reverse it, and even small changes to the input produce a completely different tag. It’s a safe, irreversible summary of the location.

Two puzzles define life in this city:

• Learning with errors (LWE): you get directions that almost follow the grid but include small and purposeful errors. For shorter routes cleaning up these errors is relatively easy but becomes extremely difficult for long routes across our megacity. For an excellent post explaining LWE see this post by Sophie Schmieg.
• Short Integer Solution (SIS): you try to find a short loop that brings you right back to where you started, but under the city’s full map A the streets don’t line up the way you expect. The map quietly twists and stretches directions, so most loops don’t close cleanly. Finding one that does, a perfectly balanced set of steps that cancels out, is incredibly hard unless you already know the local layout in detail.

Short routes are easy to reason about but longer routes are harder to reconstruct and verify. Neither of these puzzles feel relevant right now but the goal is that by the end of this post, it’s clear why each is important.

Everyone in this city uses the same public map A. The map defines how to convert a route into a location. If you know the route, you apply A and get the coordinates of the location you reach.

Each resident, say Bob, chooses a home location on the map that only he knows precisely. That location is described by a short route, or vector, s1, which lists a short route to reach his home from the city center. The vector is short because it only involves small moves. A few blocks here, a few there, rather than a long, sprawling journey.

If Bob exposed A.s1 directly, Alice or anyone else could easily find exactly where Bob lives. To avoid this, Bob adds some noise, s2, whenever he shares his address. This is called Bob’s public key:

t = A.s1 + s2

If you are Alice, looking at that noisy location is like knowing “Bob lives somewhere in this part of the city”, but you don’t know which exact building or floor. The small noise makes it too difficult to use the map to discover his exact address. In Manhattan, this is the equivalent of Bob telling Alice “I live a couple of blocks north and a few blocks west of the Empire State Building”. It’s enough to know roughly where Bob lives, but impossible to work out his exact address.

In more technical terms, without this noise the relationship between t and s1 would be exact. In the noise-free case A.s1 = t, anyone could solve this linear equation directly and recover s1. The fact that s1 happens to be short does not give it any special protection, because the system isn’t asking you to search among many short vectors or pick the one that fits best. It is giving you one precise target, and solving the equation simply returns s1 directly. Once the noise s2 is added, the equation becomes t = A.s1 + s2. Now the public value t no longer points cleanly back to one exact s1. Instead, it is “blurred” by a small error. Recovering s1 from t now means separating the true signal from the added noise. This is exactly the LWE problem: given A, a noisy output t, and the promise that both s1 and s2 are small, recover the original secret. Despite the shortness of the vectors, cleaning up this noise in a large, high-dimensional lattice is believed to be infeasible, even for a quantum computer.

Now imagine Alice sends Bob a message, M, she wants signed: “Approve this transaction”. In this city, signing means proving you know how to navigate from the center of the city to your own home, but crucially, without ever revealing your home address.

To create this signature Bob does not use his secret immediately. First he walks a fresh random short route y from the city center. He applies the map to reach a temporary location:

w = A.y

He never reveals w, instead only which neighborhood it’s in. He does this by taking a photo of the skyline from where he is standing, called H(w). You can think of it as Bob saying “I’ve walked somewhere in the city. I won’t tell you the exact corner, but I’ll give you a photo of the skyline from where I am standing. Later, you can use this photo to check that I was really there”. This is his commitment. It fixes him to a specific neighborhood without showing the exact coordinates.

So far, Bob has committed to a location w in the city and can safely share his skyline photo, H(w). But there’s still a problem: what if Bob picked w in a way that lets him cheat later? For example, he might be able to adjust his story slightly to make a different route also fit that same skyline. Alice needs a way to lock him to one exact corner inside that neighborhood so he can’t change his story after seeing her message.

The solution is a coordinate challenge. Both Alice and Bob need to derive the same challenge from public data. They hash together the message M, the commitment H(w), Bob’s fuzzy landmark t, and the map A. The result is a small pattern of nudges:

c = H(M, H(w), t, A)

You can think of c as Alice pointing at one very specific nearby corner in the neighborhood Bob committed to. Because c depends on the message and the commitment, Bob cannot predict it beforehand or change it afterwards. This ties the signature Bob is about to create to the exact message M and locks Bob to the temporary location he already committed to H(w). The challenge itself is small. You can think of it as a short list of nudge instructions, telling Bob to adjust his route in specific directions. Technically, we would describe this as a sparse vector of tiny steps in {−1, 0, 1} spread across the 256 directions of the city.

Let’s recap what we have so far:

• Bob knows his private home location: s1.
• Bob has revealed his public key t, which is a rough approximation of where he lives.
• Bob has created a temporary route, y, to some random location, w, and has taken a photo of the skyline at w called his commitment H(w) which he can share with Alice.
• Alice has sent Bob a message she wants signed, M.

Using both Bob’s commitment H(w) and Alice’s message M, they each derive the same coordinate challenge c. This challenge defines one specific nearby corner in Bob’s neighborhood, and once the commitment and message are fixed, neither side can change it.

This is the moment Bob actually creates the signature. Everything before this was set up: publishing a fuzzy landmark t, choosing a temporary walk y, committing to the skyline photo H(w) of where that walk ended, and agreeing on a challenge c he cannot influence. None of that used his secret.

Bob must take the temporary walk y he committed to and adjust it using both the challenge c and his hidden home s1. The adjusted route z is the core of the signature:

z = y + c.s1

We have seen a few of these route, or vector, additions already. Vector addition is straightforward. If you imagine a 2D grid, y is one arrow and c.s1 is another. Place them head-to-tail and the combined arrow from the city center is z. The same idea holds in 256 dimensions. z is simply a new route from the city center that reflects both the randomness of y and Bob’s secret home s1.

Vector Addition

A key detail is that z needs to remain short. The security of the scheme depends on all published z values looking similar in size. Because y is sampled from a distribution of short routes and c.s1 is small, z is usually short as well. If it isn’t, Bob discards that attempt and walks a new y route. This retry process is called rejection sampling. This does not break the commitment challenge flow. Each new y produces a new w, a new commitment H(w), and a new challenge c. Bob only moves forward with the attempt when everything fits within the required bounds. The verifier only ever sees the final valid attempt, so nothing leaks.

This adjustment step is what links the signature to Bob’s secret. Only someone who knows the real s1 can produce a route z that fits together with the map A, the fuzzy landmark t, the challenge c, and the original skyline photo H(w). A forger would have to guess a valid short z that satisfies all these constraints. In lattice terms, that means finding a short solution to a system of equations that is constrained by the map A and the public key t. This is exactly the kind of “find a short vector that satisfies a structured equation” task captured by the SIS hardness assumption, and it is believed to be infeasible even for a quantum computer.

Once Bob finds a valid z, he has everything needed for the signature. He sends Alice:

• the adjusted route z
• The challenge c
• A small hint to help her reproduce the skyline photo. You can think of this as Bob sending Alice a small list of instructions of how we took the photo; the angle of the camera when he took the photo, and some camera settings so she can reproduce the same view

These pieces together are the signature: the proof that Bob used the correct secret while never revealing it. We can write the signature explicitly as {z, c, hint}.

Now Alice can check everything Bob has sent her to see if his signature is valid and prove that he knows his secret home location s1 without Bob ever revealing it. In this section, I use some basic algebra to help demonstrate exactly how Alice does this. Stick with it, it’s not too complex.

Alice now knows:

• The public map A
• Bob’s fuzzy landmark, his public key, t
• The challenge c
• The adjusted route z
• Bob’s commitment H(w) where w is Bob’s temporary location he arrived at after walking route y.
• And the hints Bob sent her to retake the same skyline photo

Alice can now retrace what Bob must have done. She starts by applying the map to z:

A.z

This gives her the location Bob would reach if he followed z. She then removes the effect of the challenge using copies of Bob’s fuzzy landmark t:

A.z - c.t

She does this by plugging in z, and t:

z = y + c.s1

t = A.s1 + s2

So A.z - c.t becomes:

A(y + c.s1) - c(A.s1 + s2)

When we multiply this out we get:

A.y + A.c.s1 - c.A.s1 - c.s2

Conceptually, the middle terms involving s1 cancel inside the structure ML-DSA uses for these operations. What remains is:

A.y - c.s2

Recall that w = A.y, so this becomes:

w - c.s2

Alice has now reconstructed a point that rounds to the same region Bob was in when he took his skyline photo at location w, but blurred by a very small shift c.s2. In the analogy, it is as if she has walked to nearly the same street corner where Bob once stood, but the view is off by only a few inches. Because both the challenge c and the noise s2 are tiny, this small shift means she is in the same rounding region Bob was in when he took his skyline photo.

She now uses the small hint Bob included to recreate the skyline photo he would have taken at that spot. This gives her a reconstructed location we can call w', which should be the same location w Bob was in when he took the photo. She takes her own skyline photo, H(w'), and checks whether they match:

H(w’) == H(w)

If the photos, or hashes, match, Bob’s commitment H(w), the challenge c, and the adjusted route z all fit together. Only someone using the real s1 can make Alice’s reconstructed skyline photo match. If they do not match, the signature is rejected.

When we expand the expressions using z = y + c.s1 and t = A.s1 + s2, it may look like Alice somehow knows s1 and s2. She does not. These substitutions of s1 and s2 cancel out via algebra, so Alice never needs to know them. They describe the internal structure of the values Bob created, not information Alice has access to. In reality, Alice only sees z, c, t, and the map A. She applies the algebra using those public values. The reason we expand the equations is to show why the verification works: the hidden structure inside t and z ensures the expression A.z - c.t collapses back to a point that rounds to the same skyline photo Bob committed to earlier. Alice never learns s1 or s2; she only checks whether the public values she receives behave in a way that is consistent with someone using the correct hidden home.

LWE protects Bob’s private home in the public key t = A.s1 + s2. SIS protects the correctness of Bob’s response in z = y + c.s1. Rounding hides tiny differences. Rejection sampling prevents known forms of statistical leakage. The hash locks Bob to a commitment before the challenge is known. The algebra in the verification step ties together the public key t, the commitment H(w), the challenge c, and the response z in a way only the real secret key holder can satisfy. And importantly, LWE, SIS, and the hash-based binding used in the commitment-challenge step are all assumptions believed to remain secure even against large-scale quantum computers.

The analogy does not capture every detail, but the structure is correct: Bob hides his home with noise, commits to a temporary location, accepts a challenge he cannot influence, adjusts his route using his secret, and proves everything fits when Alice reconstructs the skyline view. This is the core of how ML-DSA keeps signatures safe in a post-quantum world.