Paper 2020/979

Mercurial Signatures for Variable-Length Messages

Elizabeth C. Crites and Anna Lysyanskaya


Mercurial signatures are a useful building block for privacy-preserving schemes, such as anonymous credentials, delegatable anonymous credentials, and related applications. They allow a signature $\sigma$ on a message $m$ under a public key $\mathsf{pk}$ to be transformed into a signature $\sigma'$ on an equivalent message $m'$ under an equivalent public key $\mathsf{pk}'$ for an appropriate notion of equivalence. For example, $\mathsf{pk}$ and $\mathsf{pk}'$ may be unlinkable pseudonyms of the same user, and $m$ and $m'$ may be unlinkable pseudonyms of a user to whom some capability is delegated. The only previously known construction of mercurial signatures suffers a severe limitation: in order to sign messages of length $n$, the signer's public key must also be of length $n$. In this paper, we eliminate this restriction and provide a signing protocol that admits messages of any length. This significantly improves the applicability of mercurial signatures to chains of anonymous credentials.

Available format(s)
Publication info
Signature schemesanonymous credentials.
Contact author(s)
elizabeth_crites @ alumni brown edu
anna_lysyanskaya @ brown edu
2020-08-18: received
Short URL
Creative Commons Attribution


      author = {Elizabeth C.  Crites and Anna Lysyanskaya},
      title = {Mercurial Signatures for Variable-Length Messages},
      howpublished = {Cryptology ePrint Archive, Paper 2020/979},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.