Cryptology ePrint Archive: Report 2020/979

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.

Category / Keywords: Signature schemes, anonymous credentials.

Date: received 12 Aug 2020, last revised 15 Aug 2020

Contact author: elizabeth_crites at alumni brown edu,anna_lysyanskaya@brown edu

Available format(s): PDF | BibTeX Citation

Version: 20200818:083029 (All versions of this report)

Short URL: ia.cr/2020/979


[ Cryptology ePrint archive ]