A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks

We present a digital signature scheme based on the computational difficulty of integer factorization. The scheme possesses the novel property of being robust against an adaptive chosen-message attack: an adversary who receives signatures for messages of his choice (where each message may be chosen i...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1988-04, Vol.17 (2), p.281
Main Authors: Goldwasser, Shafi, Micali, Silvio, Rivest, Ronald L
Format: Article
Language:English
Subjects:
Algorithms
Cryptography
Digital signatures
Forgery
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a digital signature scheme based on the computational difficulty of integer factorization. The scheme possesses the novel property of being robust against an adaptive chosen-message attack: an adversary who receives signatures for messages of his choice (where each message may be chosen in a way that depends on the signatures of previously chosen messages) cannot later forge the signature of even a single additional message. This may be somewhat surprising, since in the folklore the properties of having forgery being equivalent to factoring and being invulnerable to an adaptive chosen-message attack were considered to be contradictory. More generally, we show how to construct a signature scheme with such properties based on the existence of a "claw-free" pair of permutations--a potentially weaker assumption than the intractibility of integer factorization. The new scheme is potentially practical: signing and verifying signatures are reasonably fast, and signatures are compact.
ISSN:0097-5397
1095-7111
DOI:10.1137/0217017