Fail signature scheme

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. 

It is clear from the description of the fail-stop property that fail-stop signature schemes contain at least two new components, in addition to those from Figure 2.2 ... 

The need for such a framework arose as follows in the context of a work whose original purpose was only to present fail-stop signature schemes and related schemes ... 

Secondly, so far, any new type of signature scheme that had a formal definition at all needed a completely new one, as explained with fail-stop signature schemes at the end of Section 3.2. This is unsatisfactory First, if they are all called signature schemes, they should have something in common, and secondly, new definitions in cryptology have turned out to be just as error-prone as new constructions. 

Hence the goal was one common definition that should at least cover the GMR definition, the schemes invented as ordinary digital signature schemes but not exactly fitting the GMR definition, and all the existing variants of fail-stop and invisible signature schemes, where existing means that a concrete construction has been proposed in the literature. Such a definition is sketched here. 

Multiple speciHcations, i.e., different specifications intended for different degrees of security, which would be redundant otherwise. For instance, with fail-stop signature schemes one first requires that no forgeries occur, but secondly, if a forgery occurs nevertheless, it should be provable. This makes sense because the second requirement is to hold on weaker assumptions than the first... 

First, in the service of fail-stop signature schemes, the fact that a proof of forgery has occurred in the system is represented at the interface by acc= broken . 

A beautiful, but unrealistic variant would be that the court finds out exactly who has produced a forgery. Realistically, with implementations of fail-stop signature schemes where different parts rely on different assumptions, there can be an output parameter which assumption that distinguishes which assumption was broken. 

This combination occurs in some versions of fail-stop and dual signature schemes, see below. 

In this subsection, a weaker version of the fail-stop property is explained. In the notation of Section 5.2.3, it yields a signature-like scheme with accountable centres. Such schemes are called fail-stop signature schemes with special risk hearers. Where a distinction is necessary, the real signature schemes with a fail-stop property as described above are called full fail-stop signature schemes, and their property a full fail-stop property. 

The following requirements are stronger than the minimal ones for signature-like schemes with accountable centres. In particular, effectiveness of authentication is required even if all risk bearers are dishonest this is needed when schemes with one risk bearer are used as building blocks for full fail-stop signature schemes. 

Particularly efficient implementations of fail-stop and dual signature schemes (see Figure 5.12) and of the ordinary digital signature scheme GMR (see [FoPf91]) exist in this case. 

If a scheme has 2-party disputes, they are often non-interactive. However, no non-interactive 3-party dispute is known, i.e., none where the entities of the signer and the recipient each send a message to the court s entity in the first round and the court s entity immediately decides. Instead, as with fail-stop signature schemes, the... 

An example of this distinction in fail-stop signature schemes is given in Section 10.4. The related distinction between authentic and untrusted storage was made for incremental signature schemes [BeGG95]. One can also regard server-aided computation as related if the server is a larger untrusted device of the same user. 

Ordinary security is the type of security that ordinary digital signature schemes offer The requirement of the signer on disputes is fulfilled computationally only, that of the recipient information-theoretically, and there is no fail-stop property. If transferability is required, the effectiveness of transfers also holds information-theoretically. 

Fail-Stop Signature Schemes with Special Risk Bearers... 

In Section 5.2.9, it was mentioned that effectiveness of initialization need not be required explicitly for fail-stop signature schemes with special risk bearers. It is now sketched that correctness of initialization indeed implies effectiveness of initialization in these schemes. 

In the following, these properties are taken for granted hence the name fail-stop signature scheme is restricted to schemes with these properties. ... 

It would be more systematic to use this name for all signature schemes with fail-stop security. But it would be awkward to list all additional properties in the name of each type of scheme, and this use of the term is nearer to previous formal definitions of fail-stop signature schemes. 

If there are many risk bearers, initialization can be much more complex. However, all existing fail-stop signature schemes are based on a construction with only one risk bearer, and the additional measures to accommodate several risk bearers are very similar for aU these constructions, see Section 7.5. (Sketches were contained in [Pfit89, PfWa90].)... 

In particular, a constraction exists that transforms any fail-stop signature scheme for a fixed risk bearer with 2-message initialization into one for many risk bearers where initialization only needs two rounds In the first round, the entity of each risk bearer broadcasts a separate prekey in the second round, the signer s entity broadcasts a public key. More generally, one can use parallel replications of the initialization of any fail-stop signature scheme for a fixed risk bearer, see Section 7.5.1. This soimds quite efficient however, it has so far implied that the complexity of the other transactions grows linearly with the number of risk bearers. In contrast, versions with more complex initialization exist where the complexity of the other transactions is not larger than in the case with one risk bearer, see Section 7.5.2. 

Figure 6.2. Existing fail-stop signature schemes, classified according to risk bearers...

Note that according to the description above, the entities of courts and recipients do not send any messages in the initialization of existing fail-stop signature schemes with special risk bearers they only receive messages that are broadcast by the entities of the signer and the risk bearers. 

The second service property in which existing fail-stop signature schemes differ is the dependence of authentication on the recipients (see Section 5.2.10). This classification is independent of that according to risk bearers. However, the cases... 

Similar to the convention with risk bearers, a fail-stop signature scheme without further attributes is assumed to provide the most general service, i.e., no dependence on the recipient, but more restricted schemes can be more efficient, in particular in their test algorithms. The two most common cases are (see Figure 6.3) ... 

---