Standard fail-stop signature scheme

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

Figure 7.1. Components and parameters of a correct initialization in a conventional definition of standard fail-stop signature schemes with one risk bearer...

According to Section 6.1.2, standard fail-stop signature schemes are with non-interactive authentication. Hence, as described in Section 5.3.2, one can identify two non-interactive algorithms sign and test. Moreover, there is no dependence on the recipient. 

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

Before the components of standard fail-stop signature schemes (in a conventional definition) are summarized in Definition 7.1, the specification parameters from Section 5.2.5 must be considered. Several of them have already been fixed for all standard fail-stop signature schemes, e.g., the set Dispute jresults and everything to do with sets of identities of recipients, because no dependence on the recipient is prescribed. Others cannot be seen in a conventional definition, such as Sign results. Two parameters remain, the message space and the set of message bounds. 

Definition 7.1. The components of a standard fail-stop signature scheme with one risk bearer for a non-empty message space Af c 0,1 " and a non-empty set Message bounds c IN u > are a 5-tuple Gen, sign, test, prove, verify) where... 

Lemma 7.4. The fail-back requirement of the recipient on disputes is fulfilled information-theoretically without error probability purely by the structure assumed for standard fail-stop signature schemes. ... 

Moreover, active attacks have to be considered, i.e., the attacker may induce the signer and the court to perform an arbitrary number of authentications and disputes. However, only a restricted active attack has been considered formally in previous conventional definitions The attacker only initiates authentications before the one dispute where he tries to achieve the result acc = TRUE. It is now shown that this restriction is in fact without loss of generality for standard fail-stop signature schemes. However, the restriction restr is used, which was not made explicitly in previous definitions. 

Lemma 7.5. If a standard fail-stop signature scheme guarantees the fall-back requirement of the signer on disputes against attackers that only initiate authentications and then one dispute, it also guarantees this requirement against general active attacks. ... 

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. 

In previous definitions, this requirement has been considered almost without active attacks, i.e., the attacker only takes part in one initialization (where he may try to cheat, of course) and then immediately tries to compute a valid proof of forgery. It is now shown that this is without loss of generality in standard fail-stop signature schemes. 

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

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. 

Consistency of initialization is achieved automatically in standard fail-stop signature schemes because the result is a deterministic function of broadcast messages. 

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. 

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.9. A standard fail-stop signature scheme provides correctness of initialization if it has the following properties. For all probabilistic interactive functions A and B and all parameters par according to Definition 7.1 or 7.2, respectively ... 

Definition 7.10, Let a standard fail-stop signature scheme be given. 

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

Deflnition 7.13. Let a standard fail-stop signature scheme and an attacker strategy B, F), consisting of two probabilistic interactive functions of the appropriate type, be given. 

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

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

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

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

Additiondly, as zero-knowledge proof schemes have error probabilities, but some properties of standard fail-stop signature schemes were required without an error probability, one sometimes has to consider all prekeys that a signer s entity may possibly accept. They are represented by a set All. 

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. 

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. 

Signing and testing work as in the given standard fail-stop signature scheme. 

Effectiveness of authentication follows immediately from Definition 7.10. Usually, error-free effectiveness of authentication is required with standard ordinary digital signature schemes. This is guaranteed if effectiveness of authentication is error-free in the underlying standard fail-stop signature scheme, or at least in the case of correct execution of Gen, i.e., with B = B. In particular, this is the case if a standard fail-stop signature scheme with prekey is used (Theorem 7.34b). 

---