### Mercurial Signatures for Variable-Length Messages

Elizabeth C. Crites and Anna Lysyanskaya

##### Abstract

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
Preprint.
Keywords
Signature schemesanonymous credentials.
Contact author(s)
elizabeth_crites @ alumni brown edu
anna_lysyanskaya @ brown edu
History
Short URL
https://ia.cr/2020/979

CC BY

BibTeX

@misc{cryptoeprint:2020/979,
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{https://eprint.iacr.org/2020/979}},
url = {https://eprint.iacr.org/2020/979}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.