Reading the Crypto Classics

Goldwasser, Micali, Rivest: "A Digital Signature Scheme Secure Against Adaptive Chosen-message Attacks“

2022/12/13 10:00-12:00

Moderator: Dr. Christian Janson (TU Darmstadt, Cryptoplexity Group) | Location: online

Organizer: , TU Darmstadt, Cryptography and Information Security Group


This talk is the second session in the seminar series “Reading the Crypto Classics” for the winter term 2022/23. The idea of this seminar is to jointly read classical milestone papers in the area of cryptography, to discuss their impact and understand their relevance for current research areas. The seminar is running as an Oberseminar, but at the same time meant to be a joint reading group seminar of the CROSSING Special Interest Group on Advanced Cryptography with all interested CROSSING members being invited to participate.

This issue will cover the paper/talk

Goldwasser, Micali, Rivest: “A Digital Signature Scheme Secure Against Adaptive Chosen-message Attacks“ available at (opens in new tab)

with the following 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."


For participation in this virtual format, please write an e-mail to the organizer (see above).

More information