While reading a literature on signature schemes, I came across the concept of Existential Unforgeability of signature scheme against Adaptive Chosen Message Attack. Can anyone point me to the paper where this notion was introduced first? Otherwise, may I ask for a paper/reference where the above-mentioned game is properly defined?

  • 3
    $\begingroup$ This is the standard security property for secure digital signatures and you will find it in any modern textbook (e.g., Katz & Lindell). It has been introduced here and we will not do the googling for you ;) $\endgroup$
    – DrLecter
    Oct 17, 2014 at 5:13
  • 2
    $\begingroup$ csee.wvu.edu/~xinl/library/papers/comp/goldwasser1988.pdf $\;$ $\endgroup$
    – user991
    Oct 17, 2014 at 5:19
  • $\begingroup$ (Also: Have you seen "the concept of" Strong "Unforgeability of signature" schemes "against Adaptive Chosen Message Attack"?) $\;$ $\endgroup$
    – user991
    Oct 17, 2014 at 5:22
  • $\begingroup$ Thanks to both of you. I was not sure which paper the notion was introduced. @Ricky Demer Are you talking about this paper? crypto.stanford.edu/~dabo/papers/strongsigs.pdf $\endgroup$
    – sherlock
    Oct 17, 2014 at 6:00
  • 1
    $\begingroup$ No; I'm just making sure you're aware that EUF-CMA is not the strongest notion. $\;$ $\endgroup$
    – user991
    Oct 17, 2014 at 6:03

1 Answer 1


These are standard terms in the cryptographic literature. Refer to Goldwasser's Lecture Notes on Cryptography, particularly section 10.3.1 where the definitions of forgery of digital signatures are introduced:

  • Existential Forgery: The adversary succeeds in forging the signature of one message, not necessarily of his choice.

  • Selective Forgery: The adversary succeeds in forging the signature of some message of his choice.

  • Universal Forgery: The adversary, although unable to find the secret key of the The forger, is able to forge the signature of any message.

  • Total Break: The adversary can compute the signer’s secret key.

The exact use of these definitions can be seen later in the notes in which some proofs are discussed.


Your Answer

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

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