Digital signatures

A signature scheme has three algorithms. KeyGen outputs a public verification key and a secret signing key. Sign uses the secret key to produce a signature on a message. Verify uses the public key to accept or reject a message–signature pair, and honestly generated signatures must be accepted. The standard security notion is existential unforgeability under adaptive chosen-message attack (EUF-CMA): an adversary that may request signatures on messages of its choice cannot output a valid signature on any message it did not query ([GMR88]). RSA gave the first public-key signature construction ([RSA78]), but unpadded RSA signatures are not EUF-CMA secure.

• EUF-CMA and SUF-CMA: strong unforgeability (SUF-CMA) also forbids a new signature on a message that was already signed.
• One-time and many-time: a one-time signature is secure for a single message; Lamport's scheme needs only a one-way function ([Lamport79]).
• Stateful versus stateless: a Merkle tree authenticates many one-time keys under one root, but the signer must remember which keys it has used ([Merkle89]); a stateless scheme needs no such memory ([HKB+19]).
• Proof model: standard model; random-oracle model (ROM), where a hash function is modelled as a random function; quantum ROM (QROM), where the adversary may query the hash in superposition.
• Hash-and-sign versus Fiat–Shamir: hash-and-sign applies a trapdoor function to a hash of the message ([BR96], [GPV08]). Fiat–Shamir turns an identification protocol into a signature by hashing the commitment and the message into the challenge ([FS86]).
• Nonces and sampling: randomized signing must keep its per-signature randomness secret and well distributed; deterministic nonces remove a common failure ([BDLSY11]). Lattice signers must also avoid leaking the key through the signature distribution, by rejection sampling or trapdoor Gaussian sampling.
• Tightness: how much security a reduction loses relative to the underlying assumption.

• RSA and factoring: the randomized PSS encoding in the ROM ([BR96]) and standard-model signatures under strong RSA ([CS99]).
• Discrete logarithms: Schnorr signatures via Fiat–Shamir ([Schnorr91]) and Ed25519 ([BDLSY11]). ECDSA is not a Fiat–Shamir scheme; its proofs idealize part of the conversion function ([FKP16]) or the group ([GS22]). FIPS 186-5 specifies RSA, ECDSA, and EdDSA and keeps DSA for verification only ([NIST23]).
• Pairings: signatures of one group element in the ROM ([BLS01]) and short signatures without random oracles under q-SDH ([BB04]).
• Hash-based: from Lamport and Merkle to the stateless SPHINCS+ hypertree ([HKB+19]), standardized as SLH-DSA ([NIST24/FIPS205]). They rest on hash functions alone, but SLH-DSA signatures are 7,856 bytes or more.
• Lattice hash-and-sign: GPV trapdoor preimage sampling ([GPV08]), instantiated over NTRU lattices in Falcon ([FHK+20]).
• Lattice Fiat–Shamir with aborts: rejection sampling hides the secret without a trapdoor ([Lyubashevsky09]); Gaussian rejection sampling then gives SIS- and LWE-based signatures of norm $\tilde{O}(n)$ ([Lyubashevsky12]), leading to Dilithium ([DKL+18]), standardized as ML-DSA ([NIST24/FIPS204]).