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 '14 at 5:13
  • 2
    $\begingroup$ csee.wvu.edu/~xinl/library/papers/comp/goldwasser1988.pdf $\;$ $\endgroup$ – user991 Oct 17 '14 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 '14 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$ – Holmes.Sherlock Oct 17 '14 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 '14 at 6:03

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, privacy policy and cookie policy

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