One-time signature

This scheme is called a one-time signature scheme because each part of the secret key can be used only once, here for only one bit. (Later the term one-time will also be used for schemes where a complete message can be signed with each part of the secret key.) The most impractical feature of this scheme is the tremendous length of the public keys, because public keys have to be broadcast reliably at the beginning, whereas signatures need only be sent to one person and secret keys are simply stored. 

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. 

It was already explained in a footnote to Section 5.2.5 that it is useful to have signature schemes with restricted message bounds. In particular, pure one-time signature schemes, where only one message can be authenticated, are interesting building blocks for more general schemes. 

This is not proven to be the only possible construction. The only known related theorem is the lower bound in Section 11.3, which says that the number of secret random bits a signer needs grows linearly with the number of messages she can sign. It is therefore quite natural to use schemes where each signature depends on its own random bits, so that it can be computed quickly, and one can see this as an operation from a one-time signature scheme. However, a rather impractical scheme exists which is not of this type, see Remark 10.24. 

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

With one-time signature schemes, slightly simplified notation can be used ... 

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. 

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 the tree is constructed by repeatedly hashing pairs of values. Values skjemp are abbreviated as sk. 

Test To test a new signature s of the form described above, one first tests the one-time signature sj with respect to the claimed value mkj. Then one reconstructs the values on the path to the root and tests if this path ends at the correct main public key mk. (That is, one starts by hashing mkj and its claimed neighbour, and iteratively hashes each intermediate result with its claimed neighbour until one obtains a value mk that should be the root value this is compared with mk. )... 

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. 

The same hash function can be used for message hashing within the underlying one-time signature scheme and in the tree. 

If the hash function and the one-time signature scheme are based on the same assumption, the same prekey can be used for them. 

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. 

Test (test ) Given a signature of the form described above, all the one-time main public keys in it are tested with mk test and then the one-time signatures with test, where the top one-time signature is tested with respect to the correct main public key mk. (The form of the path is known from j.)... 

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. 

Moreover, the new scheme is polynomial-time in the interface inputs alone if the underlying one-time signature scheme is. ... 

Hence it suffices to show that the two probabilities are equal. This is clear, because the new probabilities par,prek defined by the independent random generation of many one-time key pairs and can therefore be partitioned, and the additional information that is given in the condition in the first probability, but not in the second one, does not concern the one-time key pair (skp mki). (The only point where one might expect a problem is the one-time signature immediately above Node I, because there, mk is a part of the message. But even that does not restrict the possible values skp) ... 

In Construction 10.13, all the information that is generated is also stored in skjemp for simplicity, i.e., the one-time key pairs, the one-time signatures at the nodes, and the real messages. The next lemma shows how much of this information can be deleted. 

In the long run, only the one-time temporary secret key skjempi is stored at a Node I, but neither the one-time main public key mki nor the one-time signature sp More precisely, mki / t>e deleted when they are no longer needed in the path of any future signature. Hence, when the coimter j is updated toy + 1, and ify denotes the common prefix ofy andy + 1 (as strings), the values at the nodes below Node y 0 and Sj Q are deleted (but mkj Q not yet). 

If a concrete one-time signature scheme is given, there may be fiuther efficiency improvements. 

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

In signing One-time key pairs, one-time signatures, and complete signatures are generated as in Construction 10.13. The rules for storing them are as follows ... 

Lemma 9.6b guarantees that this one-time forgery is provable unless j/ is the correct one-time signature on m/ at Node 1. Intuitively, it remains to be shown that the additional information in auth does not make it easier for an attacker to guess this correct signature. Formally, it suffices to show that... 

In contrast to the proof of Theorem 10.14, the probability cannot simply be partitioned into those for the individual one-time keys, because there is the encryption with the same key e. Hence the possible secret keys are counted as in the proof of Lemma 9.7. Only the worst case is considered where the attacker has maximal information about the secret key, i.e., where m is of maximal length N and hence a one-time signature s on a message m has already been issued at every... 

Secondly, one needs to know for how many possible secret keys the forged one-time signature j/ is correct, i.e., how many of them satisfy the equation sign iski, fh i) = si from ( ). This is just a one-time signature at Node / and equivalent to Equation (5) in the proof of Lemma 9.7. Hence the number of... 

It can be combined with message hashing so that messages of arbitrary length can be signed. (Recall that Construction 10.1 was not only for one-time signature schemes.)... 

Testing On input a message nij and a supposed signature s = (mk,. j, j,), the new one-time main public key is tested with mkjtest and then the new one-time signature with test(mki, mi, mfc,+i), s,), where the current one-time main public key rnkf is taken from locaJ memory. If the result is TRUE, the overall result is TRUE, too, and mki is replaced by as the current one-time main public key. 

---