Fail-stop signature scheme with top-down tree authentication

Thin black arrows denote the relation between a one-time secret key and the corresponding one-time main public key, broad grey arrows denote one-time signatures, and normal lines only indicate a tree, but are not related to a computation. The values sk temp are abbreviated as sk. 

The figure shows the temporary secret key after the first real message, mq q, has been signed. The complete new signature on wq o consists of the encircled nodes. 

A complete signature in the new scheme is one branch of this tree. More precisely, the correct signature on itij is 

Note that if there is time, the one-time key pairs that are needed next and the one-time signatures at inner nodes can be precomputed. 

Finally, the algorithm tries to compute a proof of forgery in the one-time scheme as proofs prove(sk tempi, ml, sj) and outputs the result. 

---

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. 

Figure 10.2. Fail-stop signature scheme with top-down tree authentication.

The corresponding standard fail-stop signature scheme with top-down tree authentication and a small amount of private storage (with prekey and with a distinction between private and authentic storage) is constructed by using the given one-time scheme in top-down tree authentication (Construction 10.13) with the following modifications ... 

---