3
$\begingroup$

I am Reading "Security Arguments for Digital Signatures and Blind Signatures "

Providing a new message-signature pair. This is called existential forgery. In many cases this attack is not dangerous, because the output message is likely to be meaningless. Nevertheless, a signature scheme which is not existentially unforgeable does not guarantee by itself the identity of the signer. For example, it cannot be used to certify randomly looking elements, such as keys.

I am trying find an example of a signature that is not existentially unforgeable and does not guarantee by itself the identity of the signer. Could you help me please?

$\endgroup$

1 Answer 1

1
$\begingroup$

The goal in this context is to guarantee that given a signature, or a set of signatures, you can confidently determine the public key that made them.

For a trivial example of how this might break down, consider an Ed25519 signature under a public key $A$, namely is a pair $(R, s)$ of curve point $R$ and scalar $s$ such that $[8 s] B = [8] R + [8 H(R, A, m)] A$, where $B$ is the standard base point and $m$ is the message. If we didn't hash $A$ in with $R$ and $m$, the verification equation would be $[8 s] B = [8] R + [8 H(R, m)] A$. There are several other public keys under which the same signature satisfies that verification equation: $A' = A + P$ where $P$ is a point of order dividing 8, since $[8] P = \mathcal O$.

That doesn't mean, given a target public key for which you don't know the corresponding scalar, you have any hope of finding a message/signature pair you didn't already have—i.e., it does not violate existential unforgeability. It just means that you can find another public key under which a message/signature pair you already have is also valid.

One of the basic ideas of Chaum's ecash was to anonymize transactions except fraudulent double-spending transactions, so given one signature neither you nor the bank could determine who made it (but you could still confirm its legitimacy), whereas given two signatures the bank can deanonymize the fraudster. However, rather than drop spoilers in your lap, I will leave you now to learn the thrilling details from the paper you are no doubt enjoying!

$\endgroup$
2
  • $\begingroup$ please could you rephrase this " That doesn't mean you can find any message/signature pair for a target public key, however—i.e., it does not violate existential unforgeability." I do not understand $\endgroup$
    – juaninf
    Dec 20, 2017 at 12:47
  • $\begingroup$ Does that help? $\endgroup$ Dec 20, 2017 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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