8
$\begingroup$

In the article https://crypto.stanford.edu/~dabo/pubs/papers/strongsigs.pdf there are two definitions for the security of a digital signature scheme: existential unforgeability and strong unforgeability. The difference is that while in the "existential" condition is fulfiled only if the attacker cannot forge a signature on a message he did not ask the signature for. in the case of "strong" he even cannot generate another signature for a message he already ask for. So, is there an example to a signature scheme which is "existential" unforgable but not strong unforgeble?

$\endgroup$
14
$\begingroup$

It is easy to construct a signature scheme that is existentially unforgeable but not strong. All you have to do is add a bit to the end of a strong scheme, and ignore it upon verification. This enables an attacker to flip a bit and have the new signature accepted. In some "real" settings this arises as well. For example, with ECDSA, a signature $(r,s)$ can be modified to $(r,q-s)$ and it will still be accepted (where $q$ is the group order). This can be prevented by forcing $s<q/2$, but the original signature is indeed not strong.

| improve this answer | |
$\endgroup$
  • $\begingroup$ As another example, I'd add that all re-randomizable signatures are essentially existenially unforgeable, but not strongly unforgeable. Anyone can create new (re-randomize) signature, sometimes even unlinkable to the original one, but it's still hard to create new signatures under new messages. $\endgroup$ – Marandil Feb 7 at 17:02
  • $\begingroup$ Is there an application for which existentially unforgeable is not secure enough and for which strong unforgeability is required? $\endgroup$ – Evgeni Vaknin Feb 7 at 20:16
  • $\begingroup$ In cryptocurrency circles, the ECDSA issue mentioned is called "transaction malleability". It caused complications for implementation of Lightning Network. Whether "caused complications" is equivalent to requiring strong unforgeability is the subject of many flame wars in Bitcoin land. $\endgroup$ – James_pic Feb 10 at 14:15
  • $\begingroup$ I understand that it can cause a problem if one searches via the signature. However, it actually makes no sense to implement this way; one can always search via the hash of the message. Building it by searching for the signature shows a lack of understanding that the signature is not necessarily strong. $\endgroup$ – Yehuda Lindell Feb 11 at 7:19

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.