Tree authentication

Subsequently, one tried to find constructions on possibly weaker abstract assumptions. In [BeMiSS, BeMi92], the assumption is the existence of a trap-door one-way family of permutations. This assumption was used for the efficient construction in [DiHe76] (see Section 2.4) however, a much more complicated construction was needed to avoid the problems mentioned in Section 2.5. It has a lot in common with one-time signatures and tree authentication. The constructions could be extended to arbitrary one-way permutations, i.e., not necessarily with trapdoors, in [NaYu89]. In a sense, this is not too surprising because no trap-doors were needed in the informal constructions of one-time signatures md tree authentication (see Section 2.4) either. Finally, the result was extended to any oneway function [Romp90]. The main problem in the last two cases was to construct appropriate hash functions. 

One could even define that MessageJjounds is either ) or M itself, i.e., either no input N is needed or any number is possible. All known signature schemes have a variant that works for one of these cases. However, it is simpler if one can, for instance, restrict MessageJjounds to powers of 2 in schemes with tree authentication. 

One basic idea for these constructions is tree authentication. If one starts with the type sketched in Section 2.4, the same addition is needed as with message hashing The hash functions used must be collision-intractable, and their collisions count as proofs of forgery. 

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 scheme that does not need tree authentication is presented in [Pfit94]. This leads to very short signatures, but it has computational disadvantages. Furthermore, it relies on stronger cryptologic assumptions than the other schemes. 

Many variations and combinations of the basic types of tree authentication are conceivable. Some are presented and compared in [Wilh94]. Furthermore, efficiency improvements exist that exploit special properties of the underlying scheme for signing one message block, see Section 10.5. 

If one uses such a fast hash function in bottom-up tree authentication for a fail-stop signature scheme, the overhead for the tree part (for trees of reasonable size, such as depth 20) is small in comparison with the actual signature, at least in time complexity. (This is why one-time signature schemes with tree authentication are still considered in practice, see Section 2.4.)... 

As mentioned in Section 6.1.2, more efficient constructions exist for the case of a fixed recipient, which is rather important in practice (see Section 6.2). They can be seen as special variants of tree authentication that exploit the fact that the recipient s entity can store information about the current tree. Hence only one new leaf, instead of one complete branch, has to be sent and tested during each authentication, see Section 10.6. The complexity of fail-stop signature schemes with fixed recipient is therefore comparable to that of ordinary digital signature schemes. 

Recall that the recipient is fixed hence his entity can store the counter i. Furthermore, the notion of the i-th fail-stop signature is clearly defined in the fail-stop signature schemes that would be used here (and any fail-stop signature scheme could be modified in this way) Either a scheme with tree authentication would be used or the theoretical construction from [DaPP94], where as many keys have to be prepared as one intends to sign messages. 

Prekey generation and main key generation have been considered separately, because in the subsequent constructions with tree authentication, main key generation from the underlying one-time signature scheme will be used very often, but prekey generation only once. 

As a conclusion, it will usually be optimal to sign each hash value as one message block and to use primes q°, p°, q, and p of approximately equal size, because signing is so much more efficient than testing that its exact complexity does not seem to matter in most applications, whereas longer main public keys are a disadvantage in the following constructions with tree authentication. 

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. 

The corresponding standard fail-stop signature scheme with hottom-up tree authentication (also with prekey) for the same message space has the following components, which are written with an asterisk (see Figure 10.1) The set Message bounds is the set of powers of 2. 

Figure 10.1. Fail-stop signature scheme with bottom-up tree authentication.

Theorem 10.10 (Bottom-up tree authentication). Construction 10.9 defines the components of a standard fail-stop signature scheme with prekey for signing an arbitrary number of messages. If the underlying signature scheme fulfils the simplified security criteria from Theorem 7.34, the new scheme fulfils them, too, and is therefore secure. 

Remark 10.12 (Optimization). Bottom-up tree authentication can be optimized in several ways. 

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. 

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 bottom-up tree authentication so that the public key is short. (This does not follow from Theorem 10.10, but it is easy to see.)... 

---