Message hashing

If one combines message hashing with fail-stop signature schemes, the following conditions have to be fulfilled  

In the following, first a general theorem about combinations of hash functions and standard fail-stop signature schemes with prekey is presented formally. If a concrete fail-stop signature scheme based on a factoring or discrete-logarithm assumption is used, it is natural to combine it with a family of hash functions based on the same assumption. These special cases are considered afterwards. 

The construction in this section is formalized so that it yields one-time standard fail-stop signature schemes with prekey that fiilfil the simplified security criteria for such schemes from Theorem 7.34, because the constructions in Sections 10.2 to 

4 are based on such schemes. Hence it is assumed that the underlying scheme for signing message blocks is with prekey, too. This comprises all the constructions in Chapter 9. A similar construction for schemes with arbitrary key generation would not be difficult. Remember that schemes with prekey were tacitly assumed to be with only one risk bearer see Section 7.5 for generalizations. However, a restriction to one-time schemes is not made. 

In addition to a family of hash functions in the sense of Definition 8.35, one needs a method to verify that keys are acceptable before they are used. As no difference between good and all acceptable keys had to be made with hash fimctions, local verifiability is assumed. 

---

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. 

The complexity of the most efficient schemes for signing one message block is almost as low as that of efficient ordinary digital signature schemes. The same holds if message hashing is added. (Note that this subsection assumes a fixed risk bearer or any other version that has the same effect on the efficiency of authentication, cf. Figure 6.2.)... 

This property, which will guarantee availability of service in the chosen model, is only defined here, but not always required, because that would exclude the general abstract construction with message hashing, unless the notion of hash functions were modified significantly. However, the constructions with concrete collision-intractable families of hash functions can be modified to have this property (see Section 10.1). 

Theorem 10.2 (Message hashing). Construction 10.1 defines components of a standard fail-stop signature scheme with prekey for the message space 0, 1 . If... 

If one combines the standard fail-stop signature schemes for signing one message block from Definition 9.17 with message hashing, there are no particular problems, because the function rho can be used to adapt the message-block spaces. 

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

Construction 10.19. Let a one-time fail-stop signature scheme be given that is a combination of the general construction framework (Construction 9.4) and message hashing (Construction 10.1). 

Proof, a) The only really interesting part of the proof is that the additional information stored non-secretly does not weaken the security for the signer — the requirements from Definitions 7.1 and 7.31 are easy to see, and effectiveness of authentication and the security for the risk bearer are unchanged in comparison with Theorem 10.14. (Recall from Theorem 10.2 that the security of the underlying scheme according to Definition 9.1 implies that in combination with message hashing, it fulfils the criteria of Theorem 7.34, and hence Theorem 10.14 can be applied.)... 

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

---