Improving the Exact Security of Digital Signature Schemes

by Silvio Micali and Leonid Reyzin

We put forward a new method of constructing Fiat-Shamir-like signature schemes that yields better "exact security" than the original Fiat-Shamir method. (We also point out, however, that such tight security does not make our modified schemes always preferable to the original ones. Indeed, there exist particularly efficient Fiat-Shamir-like schemes that, though only enjoying "loose security," by using longer keys may provably provide more security at a lower computational cost than their "tight-security" counterparts.)

A condensed version of this work appears in the Journal of Cryptology, Volume 15, Number 1, Winter 2002.
A prior version appeared in the proceedings of Secure Networking - CQRE [Secure] '99, R. Baumgart, editor, Lecture Notes in Computer Science 1740, Springer Verlag, 1999.