Paper 2025/2134

Non-Interactive Threshold Mercurial Signatures with Applications to Threshold DAC

Abstract

In a mercurial signature, a signer signs a representative $m$ of an equivalence class of messages on behalf of a representative $\mathsf{pk}$ of an equivalence class of public keys, receiving the signature $\sigma$. One can then transform $\sigma$ into a signature $\sigma'$ on an equivalent (to $m$) message $m'$ under an equivalent (to $\mathsf{pk}$) public key $\mathsf{pk}'$. Mercurial signatures are helpful in constructing delegatable anonymous credentials (DACs): their privacy properties enable straightforward randomization of a credential chain, hiding the identity of each signer while preserving the authenticity of the overall credential. Unfortunately, without trusted setup, known constructions of mercurial signatures satisfy only a weak form of this privacy property. Specifically, an adversary who is responsible for a link in a delegation chain—and thus knows its corresponding secret key—will be able to recognize this link even after the chain has been randomized. To address this issue, Abe et al. (Asiacrypt 2024) proposed (interactive) threshold mercurial signatures (TMS), which remove the reliance on a single trusted signer by distributing the signing capability among multiple parties, none of whom knows the signing key. However, this contribution was far from practical, as it required the signers to interact with each other during the signing process. In this work, we define and construct the first non-interactive TMS, where each signer computes its partial signature locally, and any $t$ of them combine into an ordinary mercurial signature. This is done using the mercurial signature of Mir et al. (CCS 2023) as a starting point. We also enable the Mir et al. construction to sign its own public keys, a property that is essential for DACs but had been left as an open question. Taking these two contributions together, we build the first non-interactive threshold delegatable anonymous credentials with non-transferable credentials.