Flaws in Applying Proof Methodologies to Signature Schemes

J Stern, D Pointcheval, J Malone-Lee, NP Smart

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

58 Citations (Scopus)


Methods from provable security, developed over the last twenty years, have been recently extensively used to support emerging standards. However, the fact that proofs also need time to be validated through public discussion was somehow overlooked. This became clear when Shoup found that there was a gap in the widely believed security proof of OAEP against adaptive chosen-ciphertext attacks. We give more examples, showing that provable security is more subtle than it at first appears. Our examples are in the area of signature schemes: one is related to the security proof of ESIGN and the other two to the security proof of ECDSA. We found that the ESIGN proof does not hold in the usual model of security, but in a more restricted one. Concerning ECDSA, both examples are based on the concept of duplication: one shows how to manufacture ECDSA keys that allow for two distinct messages with identical signatures, a duplicate signature; the other shows that from any message-signature pair, one can derive a second signature of the same message, the malleability. The security proof provided by Brown does not account for our first example while it surprisingly rules out malleability, thus offering a proof of a property, non-malleability, that the actual scheme does not possess.
Translated title of the contributionFlaws in Applying Proof Methodologies to Signature Schemes
Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2002
EditorsMoti Yung
PublisherSpringer Berlin Heidelberg
Pages93 - 110
Number of pages17
ISBN (Print)354044050X
Publication statusPublished - Aug 2002

Bibliographical note

Conference Proceedings/Title of Journal: Advances in Cryptology - Proceedings of CRYPTO '02

Fingerprint Dive into the research topics of 'Flaws in Applying Proof Methodologies to Signature Schemes'. Together they form a unique fingerprint.

Cite this