1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for your answer. I should have mentioned that the adversary can request to sign any message of his/her choice before output new valid pair $(m,\sigma)$ $\endgroup$ – DiamondDuck Jun 22 '17 at 18:24
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ yes. thanks for pointing out. It's just my naive example. $\endgroup$ – DiamondDuck Jun 23 '17 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.