Paper 2018/015

On Composable Security for Digital Signatures

Christian Badertscher, Ueli Maurer, and Björn Tackmann


A digital signature scheme (DSS), which consists of a key-generation, a signing, and a verification algorithm, is an invaluable tool in cryptography. The first and still most widely used security definition for a DSS, existential unforgeability under chosen-message attack, was introduced by Goldwasser, Micali, and Rivest in 1988. As DSSs serve as a building block in numerous complex cryptographic protocols, a security definition that specifies the guarantees of a DSS under composition is needed. Canetti (FOCS 2001, CSFW 2004) as well as Backes, Pfitzmann, and Waidner (CCS 2003) have described ideal functionalities for signatures in their respective composable-security frameworks. While several variants of these functionalities exist, they all share that the verification key and signature values appear explicitly. In this paper, we describe digital signature schemes from a different, more abstract perspective. Instead of modeling all aspects of a DSS in a monolithic ideal functionality, our approach characterizes a DSS as a construction of a repository for authentically reading values written by a certain party from certain assumed repositories, e.g., for transmitting verification key and signature values. This approach resolves several technical complications of previous simulation-based approaches, captures the security of signature schemes in an abstract way, and allows for modular proofs. We show that our definition is equivalent to existential unforgeability. We then model two example applications: (1) the certification of values via a signature from a specific entity, which with public keys as values is the core functionality of public-key infrastructures, and (2) the authentication of a session between a client and a server with the help of a digitally signed assertion from an identity provider. Single-sign-on mechanisms such as SAML rely on the soundness of the latter approach.

Note: Some corrections.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2018
Digital SignaturesComposable Security
Contact author(s)
christian badertscher @ inf ethz ch
2021-04-28: last of 4 revisions
2018-01-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christian Badertscher and Ueli Maurer and Björn Tackmann},
      title = {On Composable Security for Digital Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2018/015},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.