Secure standard fail-stop signature scheme

It was sketched in Section 5.4.4 that unforgeability is a consequence of the other requirements. This will be proved formally for standard fail-stop signature schemes below. Unforgeability is therefore not a part of the definition of a secure standard fail-stop signature scheme, but it will be formalized in Definition 7.22. 

This section contains the proof that secure standard fail-stop signature schemes also provide unforgeability. According to Section 7.1.3, restricted attacker strategies of the following type are considered ... 

Theorem 7.37. From every secure standard fail-stop signature scheme, a secure standard ordinary digital signature scheme can be constructed as follows. Without loss of generality, a scheme with one risk bearer can be used — if a scheme with several risk bearers is given, let R = 1 constantly. 

Construction 7.38. Let the components of a secure standard fail-stop signature scheme with one risk bearer be given. The components of a scheme with an arbitrary number of risk bearers (for the same message space and the same message bounds) are constructed as follows. They are written with an asterisk to distinguish them from the components of the underlying scheme. 

Theorem 7.39. Construction 7.38 is a secure standard fail-stop signature scheme if the underlying scheme with one risk bearer is secure. Moreover, effectiveness of authentication is error-free if it is error-free in the underlying scheme. ... 

Theorem 9.9. Construction 9.4 yields a secure standard fail-stop signature scheme with prekey for signing one message block if the following condition holds for the parameters BundFam, MFam, and tau (i.e., the family of bundling homo-morphisms, the message-block spaces, and the function that determines the bun-... 

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. 

Lemma 7.8. A secure full standard fail-stop signature scheme, i.e., one that fulfils all the minimal requirements, also fulfils the strong requirement of the signer on disputes computationally. ... 

Definition 7.11. A standard fail-stop signature scheme is secure for risk bearers iff for all probabilistic polynomial-time interactive algorithms Aj and non-interactive A2 (the two parts of the attacker strategy) and all polynomials Qsig, Qn (determining the growth of a and N as functions of k) ... 

Definition 7.14. A standard fail-stop signature scheme is secure for the signer forwards iff for all probabilistic interactive functions B and F (representing a cheating risk bearer colluding with a forger) and all parameters par as in Definition 7.1 or 7.2, respectively,... 

Definition 7.15. A standard fail-stop signature scheme is called secure iff it fulfils Definitions 7.9, 7.10, 7.11, and 7.14. ... 

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

Theorem 7.19 (Security backwards and forwards). In standard fail-stop signature schemes, security for the signer backwards implies security for the signer forwards. ... 

As the zero-knowledge proof scheme in a standard fail-stop signature scheme with prekey is required to be secure in itself, and alljtest decides membership in All correctly, it is natural to reduce the security of such a scheme to criteria that only deal with the remaining components.. This is done in the following theorem. The criteria are considerably simpler than the original definitions, because interaction in key generation no longer has to be considered. The constructions in Chapters 9 and 10 only have to be proved with respect to these criteria. 

Theorem 7.34 (Simplified security criteria). If a standard fail-stop signature scheme with prekey fulfils the following three criteria, then... 

It was sketched under Figure 5.12 and at the end of Section 5.4.3 that fail-stop security is stronger than ordinary security. This is now shown formally for the conventional definition of standard fail-stop signature schemes. Actually, two statements are shown ... 

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 this section, an efficient standard fail-stop signature scheme with prekey for signing one message block is shown where the security for the risk bearer can be proved on the abstract discrete-logarithm assumption. Recall that this scheme (for subgroups of prime fields) is due to [HePe93]. 

The construction in this section is formalized so that it yields one-time standard fail-stop signature schemes with prekey that fiilfil the simplified security criteria for such schemes from Theorem 7.34, because the constructions in Sections 10.2 to... 

Theorem 10.10 (Bottom-up tree authentication). Construction 10.9 defines the components of a standard fail-stop signature scheme with prekey for signing an arbitrary number of messages. If the underlying signature scheme fulfils the simplified security criteria from Theorem 7.34, the new scheme fulfils them, too, and is therefore secure. 

Actually, not arbitrary signature schemes with fail-stop security according to Chapter 5 are considered at present, but only standard fail-stop signature schemes as defined in Chapter 7, and security for the signer backwards and error-free effectiveness of authentication, at least in the case where all parties carry out key generation correctly, are assumed. ... 

The abbreviated names of the constructions mean bottom-up tree authentication (10.9), top-down tree authentication (10.13), top-down tree authentication with a small amount of private storage (10.19), the discrete-logarithm scheme with minimized secret key (10.22) without combination with tree authentication, and the construction with a list-shaped tree for a fixed recipient from Section 10.6. The first column of lower bounds is for standard fail-stop signature schemes (Sections 11.3 and 11.4), the second one for standard information-theoretically secure signature schemes (Section 11.5) here the length of a test key has been entered in the row with the public keys. 

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. 

In this section, information-theoretically secure signature schemes are considered — at least a standard class of them in a conventional definition. The main goal of this section in the given context is to find out the price to pay for better security than that offered by fail-stop signature schemes. It turns out that this price is very high. 

---