A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks

TLDR

The folklore suggests that forgery equivalence to factoring and resistance to adaptive chosen‑message attacks are contradictory, making this result surprising. The authors propose a digital signature scheme grounded in integer factorization. They construct the scheme using integer factorization and, more generally, a claw‑free pair of permutations, a potentially weaker assumption. The scheme resists adaptive chosen‑message attacks, is practical with fast signing and verification, and produces compact signatures.

Abstract

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.