Many risk bearers

If there are many risk bearers, initialization can be much more complex. However, all existing fail-stop signature schemes are based on a construction with only one risk bearer, and the additional measures to accommodate several risk bearers are very similar for aU these constructions, see Section 7.5. (Sketches were contained in [Pfit89, PfWa90].)... 

In particular, a constraction exists that transforms any fail-stop signature scheme for a fixed risk bearer with 2-message initialization into one for many risk bearers where initialization only needs two rounds In the first round, the entity of each risk bearer broadcasts a separate prekey in the second round, the signer s entity broadcasts a public key. More generally, one can use parallel replications of the initialization of any fail-stop signature scheme for a fixed risk bearer, see Section 7.5.1. This soimds quite efficient however, it has so far implied that the complexity of the other transactions grows linearly with the number of risk bearers. In contrast, versions with more complex initialization exist where the complexity of the other transactions is not larger than in the case with one risk bearer, see Section 7.5.2. 

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. 

In the case with many risk bearers, three situations have to be considered ... 

This section sketches how standard fail-stop signature schemes with many risk bearers can be constructed from standard fail-stop signature schemes with only one risk bearer. Recall that this also yields constructions of full standard fail-stop signature schemes (see Section 7.1.1). 

The properties of the following two constructions were already mentioned in Section 6.1.2, Number of Risk Bearers and Complexity of Initialization and Cryptologic Assumptions and Efficiency . Both constructions are general, i.e., they can be applied to arbitrary schemes. More efficient constructions are possible in special cases see Section 7.5.2, Special Versions , and Remark 9.16. (It is not even necessary that schemes with many risk bearers are constructed from schemes with one risk bearer at all, although all existing constructions are.)... 

For the transformation of an arbitrary key-generation protocol Gen with one risk bearer into a protocol Gen that generates keys with the same distribution, but in a way that many risk bearers can trust them, a multi-party function evaluation protocol is used. 

Remark 9.16 (Many risk bearers). Extensions to many risk bearers are comparatively simple in the discrete-logarithm case, because prekey generation can be decomposed into the uniformly random choice of a string r of a certain length, where r need not be secret, and a deterministic algorithm that computes prek from r. This can be exploited as in Section 7.5.2, Special Versions , Item 2. 

The main variation is in the dependence on the recipients. Their role is similar to that of the risk bearers in fail-stop signature schemes To guarantee computational security for each recipient, even if many other participants are attacking, the entities of all recipients must take part in initialization. Hence initialization is much simpler if it is for a fixed recipient. 

The security for the risk bearer follows fiom the fact that valid proofs of forgery of the underlying one-time signature scheme and collisions of the hash fimctions are assumed to be infeasible to constmct. (Formally, the two infeasibility conditions are combined as in the proof of Theorem 10.2, but without parameter transformations.) Note that the fact that many one-time key pairs are based on the same prekey prek makes no formal difference at all in Criterion 2 of Theorem 7.34. 

---