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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Feb 6, 2020 at 15:14
-
$\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$– MarandilCommented Feb 7, 2020 at 17:02
-
$\begingroup$ Is there an application for which existentially unforgeable is not secure enough and for which strong unforgeability is required? $\endgroup$ Commented Feb 7, 2020 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$ Commented Feb 10, 2020 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$ Commented Feb 11, 2020 at 7:19