Top-Down Tree Authentication with Small Amount of Private Storage

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

In the constructions in the previous two sections, the length of the secret key is linear in the message bound, i.e., the number of messages to be signed. It is shown in Chapter 11 that this cannot be avoided if one defines secret key in the functional way of Definition 7.3a, i.e., including all the secret random bits that the signer s entity ever uses. 

However, it is now shown that a secret key of this size never needs to exist completely at the same time In the following construction, the signer s entity only needs a small amount of private storage, whereas the rest of its information can be stored in authentic, but not necessarily secret storage. As mentioned in Section 5.4.1, Some Special Properties , this can be an advantage in practice. 

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 

Values skjtemp are abbreviated as sk. The figure shows the situation after three real messages have been signed. Only the encircled values have to be in private storage. Values crossed out have been deleted. The remaining values are in authentic storage, where authi is the information stored in authentic storage instead of ski, i.e., (mi, si, in Construction 10.19. 

---

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

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. 

---