What a Signature Must Guarantee: EUF-CMA and the Two Roads to It

Comparing signature schemes is meaningless without first fixing what a signature is supposed to guarantee, because the whole point of the comparison is which scheme meets that guarantee at what cost. A digital signature must let anyone holding a public key confirm that a message was authorized by the holder of the matching secret key and was not altered — and it must do so even against an adversary who has watched many legitimate signatures and can request more. This article makes that requirement precise as a formal game, distinguishes its standard and strengthened forms, and then sets up the two philosophies the post-quantum standards pursue to satisfy it.

The three algorithms

A signature scheme is a triple of algorithms. Key generation produces a matched pair: a secret signing key and a public verification key, with the public key safe to publish. Signing takes the secret key and a message and outputs a signature. Verification takes the public key, a message, and a candidate signature, and returns accept or reject. Correctness requires that signatures produced honestly always verify — signing then verifying the same message under the matched keys accepts with certainty.

Correctness alone is trivial to achieve and says nothing about security; a scheme that accepts every signature is perfectly correct and perfectly useless. The content is in what verification rejects: it must reject any signature not produced by the secret key, even one crafted by an adversary who has studied the public key and a pile of legitimate signatures. Capturing that requirement precisely is the purpose of the security definition, and everything about a scheme's trustworthiness is measured against it.

It is worth separating the two things a signature provides, because both fall out of the same definition. Authenticity — the message came from the key holder — and integrity — the message was not modified — are jointly guaranteed, because any change to the message or the signer would require producing a valid signature the adversary is not able to produce. The definition therefore does not need to mention integrity separately; it follows from unforgeability.

The security game: EUF-CMA

The standard target is existential unforgeability under adaptive chosen-message attack, abbreviated EUF-CMA. It is defined as a game between a challenger, who runs the scheme, and an adversary, who tries to break it. The challenger generates a key pair and hands the adversary the public key. The adversary is then given access to a signing oracle: it may submit messages of its choosing and receive valid signatures on them, adaptively, meaning each query may depend on the answers to previous ones. This models an attacker who can induce the legitimate signer to sign things.

After as many queries as it likes, the adversary outputs a message and a candidate signature. It wins the game if that signature verifies under the public key and the message is one it never submitted to the oracle — a genuine forgery on a fresh message, existential meaning the adversary may choose which new message to forge on rather than being handed a target. The scheme is EUF-CMA secure if no efficient adversary wins with more than negligible probability, where negligible means shrinking faster than any inverse polynomial in the security parameter.

Each qualifier in the name earns its place. Existential sets a low bar for the attacker — forging on any new message counts — which makes the security guarantee correspondingly strong. Chosen-message and adaptive give the attacker the realistic power to obtain signatures on messages it selects as it learns. Unforgeability is the property being denied to that empowered attacker. A scheme meeting this definition resists a genuinely capable adversary, not merely a passive observer.

Strong unforgeability and why adaptivity matters

A strengthened version, strong unforgeability under chosen-message attack, tightens the winning condition. Plain EUF-CMA lets the adversary win only by forging on a message never queried; strong unforgeability also counts a win if the adversary produces a new, different valid signature on a message it did query. In other words, strong unforgeability forbids not just forging on new messages but also mauling an existing signature into a different valid one for the same message. Some applications — for instance where a signature serves as a unique token — need this stronger property, and several standardized schemes provide it.

The adaptivity of the queries is not a technicality; it is what makes the definition realistic. In deployment, signers are often willing to sign many things — timestamps, certificates, protocol messages — and an attacker can frequently influence what gets signed and observe the results before choosing its next move. A definition that only allowed a fixed, pre-committed list of queries would model a weaker attacker than reality provides. Adaptive chosen-message attack grants the adversary exactly the interactive power a real signer exposes, so a proof against it is a proof against a realistic threat.

Post-quantum proofs add one more framing wrinkle worth naming now. Many efficient signature schemes are proved secure in the random oracle model, which idealizes a hash function as a truly random function the adversary can only evaluate by querying. Against quantum adversaries this becomes the quantum random oracle model, which additionally allows the adversary to query the idealized hash in superposition. Whether a scheme's proof holds in this stronger quantum model is part of judging its post-quantum assurance, a point that recurs when the concrete schemes are examined.

Two roads to the guarantee

NIST standardized two philosophically different routes to EUF-CMA security, and the contrast between them organizes the rest of this series. The first road is structured hardness: build the signature so that a forgery would solve a structured lattice problem, and inherit unforgeability from the believed hardness of that problem. The module-lattice signature standard takes this road, reducing forgery to the module versions of the learning-with-errors and short-integer-solution problems. The payoff is efficiency — moderate signature and key sizes and fast operations — and the price is that security rests on the lattice assumptions the first series examined.

The second road is hash-only: build the signature so that a forgery would violate nothing more than a standard property of a hash function, such as resistance to finding second preimages. The stateless hash-based signature standard takes this road, using only hashing as its cryptographic ingredient. The payoff is minimal, conservative assumptions — if the hash function is sound, the signature is secure, with no appeal to number-theoretic or lattice hardness — and the price is size: hash-only signatures are far larger and often slower than their lattice counterparts.

Between and beside these sit the stateful hash-based schemes, which achieve small signatures from hashing alone but require the signer to maintain state that must never be misused. The three articles that follow take each road in turn, and the final article builds a decision framework across them. The spine of every comparison is the same trade this section introduces: how conservative an assumption to demand, against how much size and speed to pay for it.

Assumption diversity as a design value

The existence of two roads is itself a security asset, and this reframes why one might deliberately keep both. If every deployed signature rested on lattice hardness and a surprising advance weakened that assumption, the entire signing infrastructure would fall at once. Maintaining a hash-only alternative — whose security depends on entirely different mathematics — means a break in one family does not compromise the other. This assumption diversity is a hedge at the ecosystem level, not a statement that either road is currently in doubt.

Reading the two roads through the single EUF-CMA definition also clarifies what a security proof actually delivers. In both cases the proof is a reduction: it shows that any efficient adversary winning the unforgeability game could be turned into an efficient algorithm solving the underlying hard problem — lattice problems on one road, hash-inversion on the other. The definition is the fixed contract; the reduction is the argument that the contract holds; and the hard problem is the load-bearing assumption whose failure would void it. The schemes differ only in that final ingredient.

For autonomous AI systems the choice is consequential precisely because their signing keys are long-lived and their signatures are load-bearing. An agent that signs model artifacts, issues capability tokens, or authorizes actions on behalf of a principal is minting evidence that may need to remain unforgeable for many years. The prudent posture mirrors the ecosystem hedge: prefer standardized post-quantum signatures, and for the most durable or high-stakes keys weigh the conservative hash-only road, whose security does not depend on the lattice assumptions holding for decades. The chapters ahead give the detail needed to make that call.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

signature_scheme:
  target_definition: EUF-CMA      # or SUF-CMA if strong needed
  oracle_model: adaptive_chosen_message
  hardness_road: structured_or_hash_only
  proof_model: quantum_random_oracle
  assumption: recorded            # lattice or hash property
key_lifetime:
  years: recorded
  assumption_diversity_hedge: considered

Glossary

Signing / verification key

The secret key used to produce signatures and the public key used to check them, output as a matched pair by key generation.

EUF-CMA

Existential unforgeability under adaptive chosen-message attack: no efficient adversary with a signing oracle can forge a valid signature on a fresh message except with negligible probability.

Signing oracle

In the security game, the challenger's service that returns valid signatures on adversary-chosen messages, modeling an attacker who can induce signing.

Strong unforgeability (SUF-CMA)

A tightened target that also forbids producing a new valid signature on a message that was already queried.

Negligible probability

A success probability shrinking faster than any inverse polynomial in the security parameter; the threshold below which an attack is deemed infeasible.

(Quantum) random oracle model

A proof framework idealizing a hash function as a random function; the quantum version allows superposition queries, testing post-quantum assurance.

References

1. NIST FIPS 204, Module-Lattice-Based Digital Signature Standard (2024)
2. NIST FIPS 205, Stateless Hash-Based Digital Signature Standard (2024)
3. NIST SP 800-208, Recommendation for Stateful Hash-Based Signature Schemes (2020)
4. Ducas et al., CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme (IACR TCHES, 2018)
5. Bernstein et al., The SPHINCS+ Signature Framework (ACM CCS, 2019)