# Existential Unforgeability of signature scheme against Adaptive Chosen Message Attack

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?

• 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 ;) – DrLecter Oct 17 '14 at 5:13
• – user991 Oct 17 '14 at 5:19
• (Also: Have you seen "the concept of" Strong "Unforgeability of signature" schemes "against Adaptive Chosen Message Attack"?) $\;$ – user991 Oct 17 '14 at 5:22
• 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 – Holmes.Sherlock Oct 17 '14 at 6:00
• No; I'm just making sure you're aware that EUF-CMA is not the strongest notion. $\;$ – user991 Oct 17 '14 at 6:03

## 1 Answer

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.