Hash then Sign approaches

Question

I am learning about digital signature. For performance, we normally do hash then sign.

One approach is to sign $H(m)$ where $H(\cdot)$ is collision resistant, but under chosen message attack, this approach only has security level of $n/2$ because of birthday attack.

Another approach is to sign $H(m \oplus r)$ where $H(\cdot)$ is a second-preimage resistant hash function and send $r$ along with the signature, but this is not efficient.

is there a different approach? can we do better on the second approach?

Answer 1

One approach is to sign $H(m)$ where $H(\cdot)$ is collision resistant, but this approach only has security level of $n/2$ because of birthday attack.

I would argue that this is not susceptible to the birthday attack but requires a second preimage attack. The adversary may be able to use the birthday attack to find two messages such that $H(m_1) = H(m_2)$ but this is not sufficient to break a digital signature. The adversary must also know the corresponding signature for either $m_1$ or $m_2$, and if it can generate these for arbitrary messages (as would be required for the birthday attack) then using a collision to forge a signature is moot (it can already generate arbitrary signatures).

Thus a reasonable assumption is the adversary can only intercept valid message / signature pairs (which is generally a fair model to use) and has to be able to find a collision for a fixed message (i.e. the message that was intercepted), which would require a second preimage attack. So I would argue that $H(m)$ is fine in this context (note that this is what schemes like ECDSA do).

Answer 2

Your approach is not an improvement since you still have to transmit $r$. Otherwise it will be impossible to compute $H(H(m) \oplus r)$ for verification.

Which of course doesn't mean that no improved approach exists. On the other hand just using a collision resistant hash function makes this improvement obsolete.