In the two signature schemes just discussed, the signature can be longer than the message. This is a disadvantage when the message is long. To remedy the situation, a hash function is used. The signature scheme is then applied to the hash of the message, rather than to the message itself.

The hash function $h$ is made public. Starting with a message $m$, Alice calculates the hash $h(m)$. This output $h(m)$ is significantly smaller, and hence signing the hash may be done more quickly than signing the entire message. Alice calculates the signed message $\text{sig}(h(m))$ for the hash function and uses it as the signature of the message. The pair $(m\text{,}sig(h(m)))$ now conveys basically the same knowledge as the original signature scheme did. It has the advantages that it is faster to create (under the reasonable assumption that the hash operation is quick) and requires less resources for transmission or storage.

Is this method secure? Suppose Eve has possession of Alice’s signed message $(m\text{,}\text{sig}(h(m))$. She has another message $m^{\prime }$ to which she wants to add Alice’s signature. This means that she needs $\text{sig}(h(m^{\prime }))$ = $\text{sig}(h(m))$; in particular, she needs $h(m^{\prime })=h(m)$. If the hash function is one-way, Eve will find it hard to find any such $m^{\prime }$. The chance that her desired $m^{\prime }$ will work is very small. Moreover, since we require our hash function to be strongly collision-resistant, it is unlikely that Eve can find two messages $m_1\ne m_2$ with the same signatures. Of course, if she did, she could have Alice sign $m_1$, then transfer her signature to $m_2$. But Alice would get suspicious since $m_1$ (and $m_2$) would very likely be meaningless messages.

In the next section, however, we’ll see how Eve can trick Alice if the size of the message digest is too small (and we’ll see that the hash function will not be strongly collision-resistant, either).