Credits

• 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.