Invention of Digital Signature Schemes

The idea that digital signature schemes might exist was first published in the directive article [DiHe76]. 

In the example, Alice has chosen a key pair (sk, pk) and published pk. In particidar, Bob and the court know pk. Now, only Alice can sign her message with sk. Bob and the court accept a message as signed by Alice if and only if it passes the test with pk. 

Such a scheme is intended to be used as follows Everybody who may want to sign messages generates such a key pair. She keeps the signing key secret and publishes the test key. (For simplicity, signers will always be assumed to be female and recipients male, corresponding to the names used in the figures.) Alternatively, the two keys are therefore called secret key (or private key) and public key, respectively. 

Everybody can now sign messages with their own signing keys, whereas all the other participants can test these signatures with the correspondng test key. 

The main security requirement on such a digital signature scheme is, roughly speaking, that one cannot forge signatures although one knows the public key. A necessary (but not sufficient) condition for this is that one cannot compute the secret key from the public key. 

---

Ever since the invention of digital signature schemes, it had been accepted that signers can only be secure in the computational sense and on cryptologic assumptions (see [DiHe76] and Section 2.3). One purpose of this work is to show that this need not be so, and to present several alternatives, in particular fail-stop signature schemes. 

---