Wikipedia describes the word “signature” from the Latin origin signāre, meaning “to sign/mark.” A signature is a handwritten (often stylized) rendering of a person’s name, nickname, or a specialized mark placed on a document to indicate identity and intent. People have tried to prove who they are for millennia. Indeed, the origins of signatures trace back to the ancient world: some of the earliest recorded personal marks and seals come from Mesopotamia around 3100 BC well before pens or paper existed.
Fast-forward 5,000 years and we have digital signatures. A digital signature is a mathematical scheme for verifying the authenticity and integrity of digital messages or documents. Like a physical signature, a valid digital signature gives the recipient confidence that the message came from a known sender. Unlike most physical signatures, well-implemented digital signatures are computationally infeasible to forge without access to the signer’s private key (you can’t just sign a digital signature on your friend's behalf in his absence). Note that digital signatures are different from electronic signatures. An electronic signature is any electronic process that indicates acceptance—such as typing your name or drawing a squiggle on a screen. A digital signature is a specific cryptographic mechanism that provides verifiable security properties.
The most prominent work on digital signatures began in the late 1970s. In 1976, Whitfield Diffie and Martin Hellman laid key foundations for public-key cryptography by developing the famous Diffie–Hellman key-exchange protocol, where two parties can exchange secure secret keys even in the presence of an eavesdropper. Shortly after, in 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman introduced RSA, which enables digital signatures based on the presumed hardness of integer factorization of the modulus N (forging a signature would essentially require factoring N). Even though the signatures were secure, they required relatively large key sizes, so efficiency and bandwidth were concerns. Later in 1985 elliptic curves over finite fields was proposed for public-key primitives. On elliptic curves, the relevant hard problem is the elliptic-curve discrete logarithm problem (ECDLP); for well-chosen curves there are no known sub-exponential attacks (running time grows faster than any polynomial but slower than pure exponential in the size of the input), and the best-known general attack is Pollard’s rho, which is exponential. This allows comparable security with much smaller parameters (e.g., ~160–200-bit EC groups were comparable to ~1024-bit finite-field DLP circa 2000). Since then, several EC-based signature schemes have appeared—to name a few ,ElGamal signatures (1985), Schnorr signatures (1991), ECDSA (Elliptic Curve Digital Signature Algorithm) (proposed 1992; standardized late 1990s–2000s), and EdDSA (Edwards-curve Digital Signature Algorithm) (2011). In the rest of this blog, we will focus solely on Schnorr signatures.