Signature-Related Schemes

The following schemes are in many respects similar to signature schemes, but have particular properties so that they do not correspond to the informal requirements on replacements for handwritten signatures from Chapter 1. Of course, this is no criticism, because most of these schemes were deliberately invented for other applications. The original names containing signature schemes were retained. In the literature, the word signature scheme was also sometimes applied to symmetric authentication schemes such schemes are not listed here. 

Other differences are whether a group center is needed, to what extent it must be trusted, and how actively it has to take part whether it is explicitly required that the 

Other schemes do not have specific group keys, they only let a number of people who all have their own key pairs sign a message such that the result is shorter than the list of individual signatures would be, e.g., [Okam88, OhOk93]. 

Furthermore, signing is not the only operation that can be shared, see, e.g., [Pede91]. 

Arbitrated signature schemes involve a kind of notary public in the process of signing [Akl82, MeMa82]. 

---

The picture of research about digital signature schemes is rounded off by a sketch of digital signature schemes with additional properties and modifications to the notion of signatures. Those that essentially fiilfil the informal requirements from Chapter 1 will be called special signature schemes, the others signature-related schemes. Many of the properties can be combined. 

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

Three related types of cryptologic schemes are not always precisely distinguished from digital signature schemes ... 

Moreover, the history of digital signature schemes is so closely linked to the history of the related types of schemes mentioned in Section 1.5 that parts of the history of those also have to be outlined. 

An access point of a recipient or a court handles all the identities of signers. With simple signature schemes, this means that an entity of a recipient or a court handles all the public keys. This has the advantage that the administration of the relation between identities of signers and public keys is hidden inside the system. 

In contrast, I do not provide a parameter for the identities of the desired courts. This is related to the informal requirement Assessment by the Public in Section 1.3, i.e., every user should technically be able to assess the authenticity of anybody s messages. A signature scheme cannot guarantee this alone, because it seems necessary that all future courts take part in initialization (e.g., so that their entities can receive public keys), and only the rqjplication determines who takes part. However, there is at least no need to provide a parameter restricting the participating courts explicitly. 

The domains of the parameters idsp (Item d)) have not been given names yet, because a signature scheme may restrict some of these parameters in relation to others and to the actual participants in transactions. For concreteness, it is assumed that any subset other than Any is described by an enumeration of its elements, i.e., the domains are subsets of the power set T(Jdf. If the relations between the parameters were fixed once and for all, they could be formulated in the requirements and all the domains could be Idp>). However, it is more general to treat these relations as specification parameters, i.e., the designers of signature schemes can choose what relations their schemes support. 

Relations that are so stringent that the resulting signature schemes are uninteresting should be excluded. For instance, it should not happen that one can never authenticate a message because no suitable parameter idsj ig exists. 

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. 

Similar relations hold in schemes with a more complex structure. Furthermore, the term public information can be extended to all the information that an attacker may know . In particular, this includes all the signatures that the signer s entity has already produced. 

Of course, a many-one relation between secret and public information is not sufficient for security but once one has a formal definition, one can formally prove that it is necessary. However, this is not completely trivial The security for the signer need not be violated in every single case where the secret information in her entity can be guessed. A formal treatment for a standard case of fail-stop signature schemes can be seen in Section 11.3. 

This is not proven to be the only possible construction. The only known related theorem is the lower bound in Section 11.3, which says that the number of secret random bits a signer needs grows linearly with the number of messages she can sign. It is therefore quite natural to use schemes where each signature depends on its own random bits, so that it can be computed quickly, and one can see this as an operation from a one-time signature scheme. However, a rather impractical scheme exists which is not of this type, see Remark 10.24. 

The actual definition of so-called standard fail-stop signature schemes is contained in Section 7.1. In Section 7.2, relations to alternative or additional security properties are shown. Section 7.3 presents fail-stop signature schemes with prekey, an important subclass, and proves simplified security criteria for them. Section 7.4 shows the relation between standard fail-stop signature schemes and ordinary digital signature schemes. Section 7.5 contains constructions of schemes with many risk bearers from schemes with one risk bearer. 

The other reason is that, as mentioned in Section 5.2.9, a fiill fail-stop signature scheme is closely related to a scheme with special risk bearers where each user who acts as a signer, recipient, or court, also has a risk bearer s access point available. In fact, if a scheme is given where an arbitrary number of risk bearers can take part, one can constract a fiill fail-stop signature scheme as follows Each entity of the new scheme consists of two parts one part acts like a risk bearer s entity and the other like an entity of a signer, recipient, or court, respectively, from the underlying scheme. As risk bearers entities only take part in initialization, this only concerns the program parts for initialization (if those can be identified statically). The outer parts of all entities must handle the fact that the two parts share their ports. 

The case with one risk bearer is given special attention. First, it is particularly simple. Secondly, as mentioned in Section 6.1.2, all existing fail-stop signature schemes are based on constructions with only one risk bearer hence a special definition simplifies the proofs of these constructions. Thirdly, only this case was treated in previous definitions, and it should become clear how those definitions are related to the ones given here. 

This section contains additional definition of security properties and proofs of their relations to the defining properties of standard fail-stop signature schemes ... 

---