[GMR88] A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks

Authors: Shafi Goldwasser, Silvio Micali, Ronald L. Rivest | Venue: SIAM Journal on Computing 1988 | Source

Abstract

We introduce the notion of a digital signature scheme that is secure against adaptive chosen-message attacks — the definition now known as existential unforgeability under chosen-message attacks (EUF-CMA). In this attack model, the adversary may request signatures on arbitrarily chosen messages before attempting to forge a signature on a new message. We prove that if factoring is hard, there exists a digital signature scheme secure against adaptive chosen-message attacks. Our scheme combines a one-time signature scheme with a tree-based authentication structure and a trapdoor permutation. This paper established the standard security definition for digital signatures used throughout modern cryptography.