Authenticators and signatures

A state-of-the-art public-key signature system

- The general idea of signature systems: 1976 Diffie Hellman.
- Roots modulo n as signatures: 1977 Rivest Shamir Adleman; independently Rabin, unpublished.
- Hashing: 1979 Rabin. Finally a system that was hard to break.
- Small exponent: 1979 Rabin. Fast verification.
- Exponent 2: 1979 Rabin. Faster verification.
- Message prefix r in signature: 1979 Rabin. In retrospect, allows tight security proofs.
- Extra factors e and f, so all r's work: 1980 Williams. Faster signing.
- Choosing r as a function of z and m: 1997 Barwood; independently 1997 Wigley. Deterministic signing.
- Signature expansion: 1997 Bernstein. Even faster verification. (Shamir stated in 2003 that he had come up with the idea earlier, and had announced it in a talk, but had not published it. So I originally said ``1997 Bernstein; independently Shamir, unpublished.'' But other people remember Shamir announcing a different idea. In response, Shamir promised to send me slides from his talk, and said that those slides actually included both ideas. I haven't received those slides. Is this another example of Shamir's well-known habit of misrepresenting his results? If not, why hasn't Shamir sent me those slides?)
- Signing without Euclid: 2000 Bernstein. Simpler signing.
- Signature compression to 1/2 size: 2003? Bleichenbacher.
- Key compression to 1/3 size: 2003 Coppersmith.
- Small r: 2003 Katz Wang. Shorter signatures.