D. J. Bernstein
Authenticators and signatures
A state-of-the-art public-key signature system
The design of this signature system evolved as follows:
I'll take the blame for any problems with the current parameters
(1537-bit moduli; H0; H1).
- 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.