Special Signature Schemes

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 article [BCDP91] also contains a theoretical construction from any one-way function. 

Invisibility was not defined formally in the first publications about invisible signature schemes. Sketches of computational and information-theoretic invisibihty are contained in [BCDP91, CBDP91] and [ChHP92], respectively. Neither is completely satisfactory yet. 

A rather principal question about whether the current schemes, and any others, achieved satisfactory invisibility was raised in [DeYu91] and a sentence in [Chau91] (not present in the preproceedings version) however, it was answered quite satisfactorily in [Chau91a, CBDP91] (see also Section 5.2.12). 

Batch signing or batch verification [Fiat90, NRVR95, YeLa95] are additional algorithms to produce or verify several signatures together faster than separately. 

---

Heij92 Eugene van Heijst Special Signature Schemes Proefschrift (Ph. D. Thesis), Techni-sche Universiteit Eindhoven, 6.7.1992. 

In the theoretical treatment of digital signature schemes, one simply assumes that a reliable broadcast network can be used during a special key-distribution phase. Only the real messages, later on, are sent over arbitrary channels. 

If one considers machines that react on many interface inputs, as they are needed in a general definition of signature schemes, one can choose to measure complexity as a function of the sum of the lengths of the interface inputs that occurred so far, or still of the initial state only. In particular situations, one might even make more special requirements, such as considering the time needed until the next output as a function of the most recent input only. ... 

This section defines both the minimal service that is common to all signature schemes and special service properties that can be used to classify signature schemes. Section 5.2.1 discusses what kind of specification is used and why. Section 5.2.2 gives a brief informal overview of the actual service specification. Sections 5.2.3 to 5.2.7 contain details about the minimal service and about formalization in general. Additional service properties are considered in Sections 5.2.8 to 5.2.12. 

Now, valid inputs are defined. Inputs are invahd if they are ignored because they try to start a new transaction before the previous transaction at the same access point has ended (see Section 5.1.2). All transactions described so far, and all those that will be added for special classes of signature schemes, have exactly one input and one output at each access point concerned. Hence an input is valid if there has been no other input since the last output or since the start of the system. This is expressed as follows ... 

The only requirement ever made in the interest of the signer if she has in fact authenticated the message, i.e., in the lower half of Table 5.2, is the one from invisible signature schemes There, the recipient should not be able to convince a third party, i.e., a court, that the message had been authenticated, unless the signer cooperates. However, the requirement one could make here is only a special case of invisibility, which also deals with dishonest third parties. 

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 idea is that there may be special users who are held responsible if the output broken occurs. Such people are called risk bearers. For instance, an insurance may have to pay up in this case, or the party that has introduced the signature scheme, or always the recipient and not the signer. In this case, the correctness of broken is only required in the interest of the court in that dispute plus at least one risk bearer, and the original requirements of the signer and the recipient are relaxed so as to allow the output broken even for the degree low. 

This section contains criteria that characterize signature schemes whose structure is less complex than the general case. Moreover, all the familiar notions of signatures, signing and test algorithms, secret keys, test keys, and public keys, are redefined for special classes of signature schemes. All the properties are described in terms of the systems derived firom the schemes. 

In contrast to Sections 5.2 and 5.3, there are no special subsections for minimal and stronger security properties. The criteria introduced in Sections 5.4.1 and 5.4.2 are almost identical for all signature schemes (and many other cryptologic transaction schemes), and Section 5.4.3 is a classification all over. 

So far, degrees of security have been defined for individual requirements. As there are several minimal requirements on signature schemes (and more for special types of service), many different combinations are possible. This subsection considers some important combinations. 

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. 

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 special problem with the degree of security is due to the fact that the entities of recipients and courts have secret information and divulge some of it in authentication and disputes, in contrast to all other existing signature schemes. Hence not only the signer, but also recipients and courts are vulnerable to active attacks, as described at the end of Section 5.4.2. This seems to be a more difficult problem than active attacks on signers, because each signature is issued only once, whereas it may be tested very often. ... 

As mentioned in Section 6.1.2, more efficient constructions exist for the case of a fixed recipient, which is rather important in practice (see Section 6.2). They can be seen as special variants of tree authentication that exploit the fact that the recipient s entity can store information about the current tree. Hence only one new leaf, instead of one complete branch, has to be sent and tested during each authentication, see Section 10.6. The complexity of fail-stop signature schemes with fixed recipient is therefore comparable to that of ordinary digital signature schemes. 

The following sections concentrate on standard fail-stop signature schemes with special risk bearers. In particular, the formal versions of the definitions and constructions are only presented for such schemes. 

One reason is that the formal definitions of fiill fail-stop signature schemes can be derived from the informal discussions just like those with special risk bearers. 

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. 

The structure of disputes in standard fail-stop signature schemes was almost completely described in Section 6.1.2 (Subsection Number of Recipients and Complexity of Tests ) by the actions of the court s entity In Step 1, the court s entity tests the signature with the algorithm test defined above. (Now test is memory-less anyway, i.e., no special case is needed.) In Step 2, this signature is sent to the signer s entity, which can answer with a string called a proof of forgery. In Step 3, the court s entity verifies this proof... 

The requirements are now considered one by one. The two original requirements on disputes from Section 5.2.7 can be omitted According to Section 5.2.9, Combinations , they follow from the fall-back requirements on disputes and the correctness of broken in full fail-stop signature schemes, and in the case with special risk bearers as accountable centres, they were omitted on purpose. 

Correctness of broken means that a correct entity of a court should not produce the output broken in a dispute or a transfer of a proof of forgery. With the structure assumed for standard fail-stop signature schemes, this output depends on an application of verify, hence the requirement means that no valid proofs of forgery should occur. This requirement is fulfilled computationally only, and if there are special risk bearers, one of their entities is assumed to be correct. 

Proof sketch. The correct entities are those of the court that applies verify and, if special risk bearers are considered, one risk bearer. By the assumed structure of standard fail-stop signature schemes, the court s entity only applies the deterministic algorithms res, test, and verify to information that is known to the attacker. Hence an attacker can simulate all the actions of the court s entity on his own and does not need active attacks on it. (More formally, this could be written as a reduction, as in the previous proof sketch.) The risk bearer s entity only carries out initializations. By the precondition about correct use of initialization, cheating does not count if it involves more than one initialization for the same signer s identity id. Initializations for other identities are completely independent, hence an attacker can simulate them on his own. ... 

Before the requirements that remain from Section 7.1.3 are formalized, the additional service properties that standard fail-stop signature schemes should have according to Section 6.1.2 are considered. It turns out that most of these requirements are automatically fulfilled according to the assumed structure of the entities around the algorithms from Definition 7.1 or 7.2, respectively. The only remaining one, the strong requirement of the signer on disputes in the case with special risk bearers, can be fulfilled by similar structural measures. 

This section presents a special class of standard fail-stop signature schemes with one risk bearer, where the structure of the key-generation protocol is a rather special case of that allowed in Definition 7.1. Almost all existing constructions belong to this class. (The theoretical construction based on bit commitments or one-way families of permutations from pZ)aPP94] does not.)... 

Full standard fail-stop signature schemes themselves provide ordinary security if the output broken in disputes is replaced with TRUE. The same holds for schemes with special risk bearers if the signer plays the role of a risk bearer, too. 

In the following, first a general theorem about combinations of hash functions and standard fail-stop signature schemes with prekey is presented formally. If a concrete fail-stop signature scheme based on a factoring or discrete-logarithm assumption is used, it is natural to combine it with a family of hash functions based on the same assumption. These special cases are considered afterwards. 

It is now shown how this can be done when top-down tree-authentication is combined with the special one-time signature schemes derived from the general construction framework. Construction 9.4. One also has to take into account that an... 

A signature-like scheme vrith accountable centres (a special case of accountable third parties) has the usual three roles and an arbitrary number of others, which are collectively called centres. (For the same reasons as in Section 5.1.2, Granularity of Entities , combinations like centre and court and centre and recipient are not considered separately.) The three common transactions are adapted as follows. 

Some schemes may offer a special kind of initialization for new recipients who enter the system later andmissed the normal initialization of some signers. This is easy to realize if initialization within the system is non-interactive. In signature-like schemes with accountable centres, non-atomic initialization may even be the standard case. 

---