Digital signature scheme

A digital signature scheme is a public-key primitive that binds a message to the holder of a private key. KeyGen produces a key pair, Sign uses the private key to compute a signature over a message, and Verify checks the signature against the message and the public key. Signatures provide authentication and integrity for software updates, certificates, transactions, and documents.

#Security notion

The standard goal is EUF-CMA (existential unforgeability under chosen-message attack): an attacker who can request signatures on messages of its choice still cannot produce a valid signature on any new message.

#Classical and post-quantum schemes

Widely deployed classical schemes include RSA signatures, ECDSA (FIPS 186-5), and Ed25519 (RFC 8032). All rest on factoring or discrete logarithms, which a large quantum computer running Shor's algorithm solves efficiently (see quantum threat to ECDSA). NIST published post-quantum replacements in August 2024: the lattice-based ML-DSA (FIPS 204) and the hash-based SLH-DSA. A third scheme, FN-DSA / Falcon, derived from Falcon, remained unfinalized as of early 2026. Post-quantum signatures are larger than classical ones, typically kilobytes rather than 64 to 72 bytes, which drives much of the migration effort.