Paper 2013/179

Malleable Signatures: Complex Unary Transformations and Delegatable Anonymous Credentials

Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, and Sarah Meiklejohn


A signature scheme is malleable if, on input a message m and a signature $\sigma$, it is possible to efficiently compute a signature $\sigma'$ on a related message $m' = T(m)$, for a transformation T that is allowable with respect to this signature scheme. Previous work considered various useful flavors of allowable transformations, such as quoting and sanitizing messages. In this paper, we explore a connection between malleable signatures and anonymous credentials, and give the following contributions: -We define and construct malleable signatures for a broad category of allowable transformation classes, with security properties that are stronger than those that have been achieved previously. Our construction of malleable signatures is generically based on malleable zero-knowledge proofs, and we show how to instantiate it under the Decision Linear assumption. -We construct delegatable anonymous credentials from signatures that are malleable with respect to an appropriate class of transformations; we also show that our construction of malleable signatures works for this class of transformations. The resulting concrete instantiation is the first to achieve security under a standard assumption (Decision Linear) while also scaling linearly with the number of delegations.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
smeiklej @ cs ucsd edu
2013-04-01: received
Short URL
Creative Commons Attribution


      author = {Melissa Chase and Markulf Kohlweiss and Anna Lysyanskaya and Sarah Meiklejohn},
      title = {Malleable Signatures: Complex Unary Transformations and Delegatable Anonymous Credentials},
      howpublished = {Cryptology ePrint Archive, Paper 2013/179},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.