Paper 2024/1216

Delegatable Anonymous Credentials From Mercurial Signatures With Stronger Privacy

Abstract

Delegatable anonymous credentials (DACs) are anonymous credentials that allow a root issuer to delegate their credential-issuing power to secondary issuers who, in turn, can delegate further. This delegation, as well as credential showing, is carried out in a privacy-preserving manner, so that credential recipients and verifiers learn nothing about the issuers on the delegation chain. One particularly efficient approach to constructing DACs is due to Crites and Lysyanskaya (CT-RSA'19), based on mercurial signatures, which is a type of equivalence-class signatures. In contrast to previous approaches, this design is conceptually simple and does not require extensive use of non-interactive zero-knowledge proofs. Unfortunately, the ``CL-type'' DAC schemes proposed so far have a privacy limitation: if an adversarial issuer (even an honest-but-curious one) was part of an honest user's delegation chain, the adversary will be able to detect this fact (and identify the specific adversarial issuer) when an honest user shows its credential. This is because underlying mercurial signature schemes allow the owner of a secret key to detect when his key was used in a delegation chain. In this paper we show that it is possible to construct CL-type DACs that does not suffer from this privacy issue. We give a new mercurial signature scheme that provides adversarial public key class hiding; i.e. even if an adversarial signer participated in the delegation chain, the adversary won't be able to identify this fact. This is achieved by introducing structured public parameters which for each delegation level, enabling strong privacy features in DAC. Since the setup of these parameters also produces trapdoors that are problematic in privacy applications, we show how to overcome this problem by using techniques from updatable structured reference string in zero-knowledge proof systems (Groth et al. CRYPTO'18). In addition, we propose a simple way to realize revocation for CL-type DACs via the concept of revocation tokens. While we showcase this approach to revocation using our DAC scheme, it is generic and can be applied to any CL-type DAC system. Revocation is a feature that is largely unexplored and notoriously hard to achieve for DACs. However as it is a vital feature for any anonymous credential system, this can help to make DAC schemes more attractive for practical applications.