What a Signature Is

01.The contract

A digital signature scheme is a triple:

$\textsf{KeyGen}()$ outputs a verification key $pk$ and a signing key $sk$.

$\textsf{Sign}(sk, m)$ outputs a signature $\sigma$.

$\textsf{Verify}(pk, m, \sigma)$ outputs accept or reject.

Correctness: an honestly produced signature always verifies.

Compare that with the KEM contract from Chapter 5 and note the reversal. In encryption, the public key operates on data and the private key undoes it. In signing, the private key operates on data and the public key checks it.

That reversal is what makes a signature useful. Anybody can verify, only one party can produce, so a valid signature is evidence about who produced it.

02.What it is for

Three jobs, and all three are running constantly on any machine connected to a network.

Software updates. Your operating system will only install an update carrying a valid signature from the vendor. Without that, anybody able to intercept the download could substitute their own code.

Certificates. When a browser connects to a site, the site presents a certificate signed by an authority the browser already trusts. That chain of signatures is what connects a domain name to a public key, and it is what stops an attacker from simply presenting their own key.

Anything that must not be repudiated. Signed commits, signed legal documents, signed transactions. The signer cannot later claim they did not produce it, because nobody else could have.

Note that the first two of those protect the distribution of software and keys. A break in signatures does not merely expose data. It lets an attacker impersonate a vendor.

03.The attacker model

The standard requirement is called EUF-CMA, existential unforgeability under chosen message attack, and it is worth unpacking because it is aggressive.

The attacker gets the public key. Then they get to ask the legitimate signer to sign any messages they like, as many as they like, chosen adaptively after seeing previous answers. They win if they can produce a valid signature on any message that was not one of the ones they asked for.

Two things about that are stronger than they might appear.

The attacker chooses the messages, so they can look for inputs that make the signer behave unusually. And they only have to forge one signature on one message of their choosing, which need not be meaningful. Producing a valid signature on a random string still counts as a break.

04.Why this is harder than encryption

Here is the difference that shapes the entire chapter.

In ML-KEM, the secret key $\mathbf{s}$ is used only inside decryption, and the result never leaves the machine. An attacker sees ciphertexts, which were produced without $\mathbf{s}$ at all.

In a signature scheme, the secret key is used to produce the output, and the output is published. Every signature is a value computed from $sk$ and handed to the adversary. Under EUF-CMA they can request as many as they want.

So the design problem is not merely "make it hard to compute a signature without the key". It is "make it hard even after seeing a million signatures made with the key".

That constraint has no analogue in the KEM, and meeting it is what the rest of this chapter is about. The historical record is unkind here: signature schemes that leaked their key over many signatures are a recurring failure. The most famous is the Sony PlayStation 3 break in 2010, where an ECDSA implementation reused its per-signature randomness and the private key fell out of two signatures by simple algebra.

The next note introduces the construction ML-DSA descends from, which solves this problem in a group setting before we try to move it to lattices.