Mercurial Signatures for Variable-Length Messages
Authors: Elizabeth C. Crites (IOHK), Anna Lysyanskaya (Brown University)
Volume: 2021
Issue: 4
Pages: 441–463
DOI: https://doi.org/10.2478/popets-2021-0079
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 σ on a message m under a public key pk to be transformed into a signature σ 0 on an equivalent message m0 under an equivalent public key pk0 for an appropriate notion of equivalence. For example, pk and pk0 may be unlinkable pseudonyms of the same user, and m and m0 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 `, the signer’s public key must also be of length `. In this paper, we eliminate this restriction and provide an interactive signing protocol that admits messages of any length. We prove our scheme existentially unforgeable under chosen open message attacks (EUF-CoMA) under a variant of the asymmetric bilinear decisional Diffie-Hellman assumption (ABDDH).
Keywords: Signature schemes, anonymous credentials.
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
