Computational cryptography › Public-key encryption and key exchange › Classical number theory › Elliptic-curve discrete log
SIGNATUREPrimitiveROM

Schnorr / EdDSA

In plain words

A simpler, cleaner signature scheme than ECDSA. Ed25519 is its popular modern form.

The idea: A Schnorr signature is a three-step proof squashed into one message. The signer commits to a random point R = k·G, takes a challenge e that is the hash of R and the message, and answers with s = k + e·x. Anyone can check that s·G equals R + e·(public key). The answer looks random because k is random, so it reveals nothing about x, yet only someone who knows x could answer an unpredictable challenge. Because everything is linear, signatures from several people can be added into one.

Why it matters: Used for SSH keys, software signing and Bitcoin's Taproot upgrade.

The details

On the map: Ed25519: SSH keys, Tor, package signing, XEdDSA variant in Signal

Schnorr signatures (1989)[1, 2] are simpler than ECDSA and have a clean security proof from discrete log in the random oracle model[3]. They were held back by a patent until 2008.

Ed25519 is the deterministic, fast variant[4, 5] used for SSH keys, Tor onion services and software signing. Signal uses XEdDSA[6], an EdDSA variant that works with its X25519 keys. Bitcoin added Schnorr signatures with Taproot in 2021[7]. They make multisignatures (MuSig)[8] and threshold signing (FROST)[9] easy.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

About the tags

ROM
Its security proof treats a hash function as a perfectly random function (the random oracle model). Real hashes aren't random functions, so this is a heuristic. For signatures and encryption no practical attack has exploited it. For multi-round proof systems, see the Fiat-Shamir box.

References

  1. C. P. Schnorr. Efficient Identification and Signatures for Smart Cards. Advances in Cryptology — EUROCRYPT ’89, 1989. doi:10.1007/3-540-46885-4_68
  2. C. P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 1991. doi:10.1007/bf00196725
  3. David Pointcheval and Jacques Stern. Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology, 2000. doi:10.1007/s001450010003
  4. Daniel J. Bernstein, Niels Duif, Tanja Lange et al. High-speed high-security signatures. Journal of Cryptographic Engineering, 2012. doi:10.1007/s13389-012-0027-1
  5. S. Josefsson and I. Liusvaara. Edwards-Curve Digital Signature Algorithm (EdDSA). RFC 8032, 2017. rfc-editor.org/rfc/rfc8032
  6. Trevor Perrin. The XEdDSA and VXEdDSA Signature Schemes. Signal specifications, 2016. signal.org/docs/specifications/xeddsa
  7. Pieter Wuille, Jonas Nick and Tim Ruffing. BIP 340: Schnorr Signatures for secp256k1. Bitcoin Improvement Proposals, 2020. github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
  8. Jonas Nick, Tim Ruffing and Yannick Seurin. MuSig2: Simple Two-Round Schnorr Multi-signatures. Advances in Cryptology – CRYPTO 2021. doi:10.1007/978-3-030-84242-0_8
  9. D. Connolly, C. Komlo, I. Goldberg and C. A. Wood. The Flexible Round-Optimized Schnorr Threshold (FROST) Protocol for Two-Round Schnorr Signatures. RFC 9591, 2024. rfc-editor.org/rfc/rfc9591