Fail-Stop Signature Schemes with Prekey

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

The primary benefit is not particularly low complexity, although that sometimes results, too, but that parts of the public key can be reused in several executions of key generation, and that security proofs become more modular. The former is an important precondition for the constructions of schemes for signing many messages from schemes for signing one message (see Section 6.3.1 and Chapter 10). Informally, this simpler key generation works as follows  

If the signer s entity does not need the help of the risk bearer s entity in this step, i.e., if it can test prek locally, one obtains the simplest form of key generation, the 2-message initialization from Section 6.1.2. 

For example, the prekey may be a number n=p q, and the risk bearer s entity may have to convince the signer s entity that n really has exactly two prime factors, but without showing it these factors, before the signer s entity generates the secret key and the main public key as certain numbers modulo n. 

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. 

---

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. 

Fail-Stop Signature Schemes with Prekey... 

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

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

Definition 9.1. A standard fail-stop signature scheme with prekey for signing message blocks is defined like a standard fail-stop signature scheme with prekey, except that there is no fixed message space M. Instead, there is a family of message-block spaces... 

In this section, a framework for constructing standard fail-stop signature schemes with prekey for signing one message block from a collision-intractable family of bundling homomorphisms is described. Two parameters (the exact family of... 

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

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

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. 

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.2 (Message hashing). Construction 10.1 defines components of a standard fail-stop signature scheme with prekey for the message space 0, 1 . If... 

Construction 10.13. Let a one-time standard fail-stop signature scheme with prekey for the message space M = 0, l +be given (see Definition 7.31). The corresponding standard fail-stop signature scheme with top-down tree authentication (also with prekey) is constructed as follows (see Figure 10.2) The set MessageJjoimds is the set of powers of 2. 

For fail-stop signature schemes with prekey (see Section 7.3), one obtains slightly stronger results. 

---