Cryptology ePrint Archive: Report 1999/020

Improving the Exact Security of Digital Signature Schemes

Silvio Micali and Leonid Reyzin

Abstract: We provide two contributions to exact security analysis of digital signatures: We put forward a new method of constructing Fiat-Shamir-like signature schemes that yields better "exact security" than the original Fiat-Shamir method; and we extend exact security analysis to "exact cost-security analysis" by showing that digital signature schemes with "loose security" may be preferable for reasonable measures of cost.

Category / Keywords: digital signatures, ID schemes, random oracles, exact security.

Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.

Date: received 27 August 1999, last revised 28 Feb 2006.

Contact author: reyzin at mit edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: This is a more complete version of the paper that appears in Journal of Cryptology, 15(1), 2002.

Short URL:

[ Cryptology ePrint archive ]