Top-down tree authentication

In Section 10.4, additional measures are added so that the amount of private storage is small all the time. Those measures are constructed specifically for the general construction framework from Section 9.2 and thus for the efficient schemes based on factoring and discrete logarithms. 

As in Section 10.2, only complete binary trees are considered formally, although one could use trees of any other shape. This time, one need not even fix the shape during key generation in particular, one can allow N = °° (see Remark 10.17). Moreover, the construction is first presented in a simple form (Construction 10.13), and then in a version with reduced storage (Lemma 10.15). 

As in Section 10.2, the words one-time and new are used to distinguish signatures and keys in the underlying scheme from those in the scheme to be constructed. 

however, that signing will be probabilistic, and hence the functional version sk of the secret key is longer. 

At the end, i.e., when the message bound has been reached, each Node / will be labeled with a one-time key pair sk tempi, mkj)-, all these pairs are based on prek. Initially, only the root is labeled with skjemp, mk). 

---

Two types of tree authentication exist. The one mentioned so far will be called bottom-up tree authentication, the other one top-down tree authentication... 

MerkSS, G0MR88]. The former leads to shorter signatures, the latter is more flexible. Its basic idea is that new public keys are authenticated using old keys. Fail-stop versions of both are presented in Sections 10.2 and 10.3, respectively. Section 10.4 contains a variant of top-down tree authentication that only needs a small amount of private storage. This may be important in practice, see the end of Section 5.4.1. 

A complete formal description and a proof of a special case of bottom-up tree authentication (an optimized construction from strong claw-intractable families of permutation pairs) can be found in [Pfit89, PfWa90]. Hence only a sketch is presented here, whereas top-down tree authentication is treated in more detail. 

For simplicity, only complete binary trees are considered. One could use trees of any other shape, but the shape must be fixed during main key generation (in contrast to the following top-down tree authentication), and it must be clear from the public key. 

What makes top-down tree authentication more flexible than bottom-up tree authentication is that the entity need not generate all the one-time key pairs in advance, in contrast to the basic idea described above. Instead, it can start with not much more than the leftmost branch of the tree. Details can be seen in Construction 10.13 and Figure 10.2. 

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.

Theorem 10.14 (Top-down tree authentication). Construction 10.13 defines the components of a standard fail-stop signature scheme with prekey for signing an arbitrary number of messages. If the underlying one-time signature scheme fulfils the simplified security criteria from Theorem 7.34, then the new scheme fulfils them, too, and is therefore secure. 

Top-Down Tree Authentication with Small Amount of Private Storage... 

It is now shown how this can be done when top-down tree-authentication is combined with the special one-time signature schemes derived from the general construction framework. Construction 9.4. One also has to take into account that an... 

Figure 10.3. Top-down tree authentication with small amount of private storage.

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

One can use subtrees of this form in top-down tree authentication in the place of individual one-time key pairs. ... 

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. 

---