โ† Wiki Index / Computation & Algorithms / Schnorr Signature
๐Ÿ’ป Computation & Algorithms

Schnorr Signature

The Schnorr signature is a digital signature scheme based on discrete logarithms that provides provable security in the random oracle model and exhibits linear algebraic properties enabling multi-signature aggregation and batch verification.

Schnorr Signature is an asymmetric digital signature algorithm in computation and algorithms that provides message authentication, non-repudiation, and cryptographic integrity through modular arithmetic over cyclic groups. Developed and patented in 1989 by German mathematician and cryptographer Claus-Peter Schnorr, the scheme is celebrated for its mathematical minimalism, its formal reduction to the Discrete Logarithm Problem in the Random Oracle Model, and its linear algebraic structure, which enables multi-signature key aggregation, threshold signing, and high-throughput batch verification.

Despite its theoretical advantages over the Digital Signature Algorithm, commercial adoption of Schnorr signatures was delayed for two decades by Schnorr's United States Patent 4,995,082 (filed in 1990). This patent prompted NIST to design DSA with subtle mathematical modifications (such as inverting the nonce in the signature equation) to circumvent patent restrictions. Following the patent's expiration in February 2008, Schnorr signatures were standardized in Edwards-curve digital signatures (Ed25519) and Bitcoin Improvement Proposal 340 (BIP-340).

Mathematical Structure and Protocol Mechanics

Let G be a cyclic group of prime order q generated by element g (which can be instantiated as a subgroup of integers modulo a prime or as points on an elliptic curve), and let H be a cryptographic hash function mapping arbitrary bit strings to integers in โ„คq.

Key Generation

To participate in the signature scheme, an entity establishes a private and public key pair through the following sequence:

  1. A private signing key x is chosen uniformly at random from the multiplicative group โ„คqร— using a cryptographically secure random number generator.
  2. The corresponding public verification key y is computed by raising the base generator g to the power of the private key:

y = gx

The private key x must be preserved in confidential hardware storage, while the public key y is distributed to potential verifiers as an authentic identity credential.

Signature Generation

To sign a message m using private key x:

  1. The signer generates a secret ephemeral nonce k sampled uniformly at random from โ„คqร—.
  2. The signer computes the public commitment R:

R = gk

  1. The signer computes the challenge scalar e by hashing the concatenation of the commitment, public key, and message:

e = H(R || y || m)

  1. The signer computes the response scalar s using the linear algebraic relation:

s = k + e ยท x mod q

The signature is the compact ordered pair (R, s). In elliptic curve implementations such as BIP-340, R is encoded using only its 32-byte x-coordinate, yielding a 64-byte signature.

Signature Verification

Upon receiving a purported signature (R, s) associated with message m and public key y, the verifier confirms authenticity through the following procedure:

  1. The verifier verifies that R is a valid non-identity element in the group G and that s lies in the valid scalar range 0 โ‰ค s < q.
  2. The verifier computes the challenge scalar e = H(R || y || m) using the identical cryptographic hash function.
  3. The verifier evaluates the single group exponentiation verification equation:

gs = R ยท ye

The verifier accepts the signature as valid if and only if both sides of the equation evaluate to identical group elements, confirming that the signer possessed the private key x.

Mathematical Correctness

The correctness of verification follows directly from the linearity of exponents:

gs = gk + eยทx = gk ยท (gx)e = R ยท ye

Because the signature equation s = k + ex involves pure linear addition without modular inversion of the nonce k, Schnorr signatures avoid the non-linear inversions that complicate DSA and ECDSA.

Provable Security and the Forking Lemma

In 1996, David Pointcheval and Jacques Stern formalized the security of the Schnorr signature scheme using the Forking Lemma, proving that the construction achieves Existential Unforgeability under Chosen-Message Attacks (EUF-CMA) in the Random Oracle Model under the Discrete Logarithm assumption.

The proof establishes that if a probabilistic polynomial-time adversary can forge a valid signature (R, s) with non-negligible probability, a simulator can execute the adversary twice with the identical random tape but with a "forked" hash response e' โ‰  e at the challenge step. The adversary will output two valid signatures (R, s) and (R, s') satisfying:

s = k + e ยท x mod q s' = k + e' ยท x mod q

Subtracting the two equations yields s โˆ’ s' = (e โˆ’ e') ยท x mod q, allowing the simulator to compute the secret key x as:

x = (s โˆ’ s') ยท (e โˆ’ e')โˆ’1 mod q

This polynomial-time reduction establishes that forging a Schnorr signature is strictly as difficult as solving the underlying Discrete Logarithm Problem.

Linear Aggregation: MuSig and Batch Verification

The linearity of the Schnorr verification equation provides two computational capabilities absent in ECDSA:

1. Multi-Signature Key Aggregation (MuSig)

In collaborative multi-party settings, n independent signers possessing private keys x1, ..., xn and public keys yi = gxi can combine their keys into a single joint aggregate public key yagg. During signing:

  • Each participant chooses an ephemeral nonce ki and broadcasts their commitment Ri = gki.
  • The joint commitment is the product Ragg = โˆ Ri.
  • Each participant computes their partial signature si = ki + e ยท xi mod q.
  • The partial signatures are summed: sagg = โˆ‘ si mod q.

The resulting aggregate signature (Ragg, sagg) is verified against yagg using the standard single-key verification equation gsagg = Ragg ยท yagge. To an external observer, the multi-signature is indistinguishable from a standard single-signer signature, enhancing confidentiality while dramatically reducing transaction size on distributed ledgers.

2. High-Speed Batch Verification

Verifying n independent signatures normally requires 2n group exponentiations. Using Schnorr batch verification, a verifier checks all n signatures simultaneously using random linear combinations. Choosing random non-zero scalars z1, ..., zn โˆˆ โ„คq:

gโˆ‘ ziยทsi = (โˆ Rizi) ยท (โˆ yiziยทei)

This multi-exponentiation reduces the dominant computational cost from 2n individual exponentiations to a single combined multi-scalar multiplication, achieving a two- to three-fold speedup in high-volume transaction verification.

Comparison of Digital Signature Paradigms

FeatureSchnorr (BIP-340 / Ed25519)ECDSA (secp256k1)RSA-PSS
Mathematical StructureLinear exponent addition: s = k + exNon-linear inversion: s = kโˆ’1(z + xr)Modular root extraction: s = md mod n
Security ProofTight reduction via Forking LemmaNon-standard assumptions requiredStrong reduction in Random Oracle Model
Multi-Signature AggregationNative; compact single-signature outputComplex; requires heavy threshold protocolsInefficient; linear signature growth
Batch VerificationSupported; substantial throughput gainsNot supported nativelyNot supported
Malleability ResistanceComplete; BIP-340 enforces uniquenessSusceptible to low-s signature malleabilitySupported with PSS padding

References

  1. Schnorr, C. P. (1991). Efficient signature generation by smart cards. Journal of Cryptology, 4(3), 161-174.
  2. Pointcheval, D., & Stern, J. (2000). Security arguments for digital signatures and blind signatures. Journal of Cryptology, 13(3), 361-396.
  3. Maxwell, G., Poelstra, A., Seurin, Y., & Wuille, P. (2019). Simple Schnorr multi-signatures with applications to Bitcoin. Designs, Codes and Cryptography, 87(9), 2139-2164.
  4. Wuille, P., Nick, J., & Ruffing, T. (2020). Schnorr Signatures for secp256k1. Bitcoin Improvement Proposal 340.
๐Ÿงฌ Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
๐Ÿ’ก Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision