International Association
for Cryptologic Research

Anonymous credentials are a type of digital credential that allow a user to prove possession of an attribute that has been asserted by an identity issuer without revealing any extra information about themselves. For example, a user who has received a passport credential can prove their “age is >18” without revealing any other attributes such as their date of birth. Despite their inherent value towards privacy-preserving authentication and authorization, anonymous credential schemes have been difficult to deploy and have therefore seen little use in large-scale applications. Part of the difficulty stems from the fact that efficient anonymous credential schemes in the literature, such as the popular BBS+ scheme use pairing-friendly elliptic curve cryptography, and therefore require changes to existing security infrastructure used by issuers before it can be deployed. In addition, state-level identity issuers often require digital identity credentials to be device-bound by incorporating the device’s secure element into the presentation flow. As a result, schemes like BBS+ also require new hardware secure elements on mobile phones to be securely deployed. In this paper, we propose a new anonymous credential scheme for the widely deployed Elliptic Curve Digital Signature Algorithm (ECDSA) signature scheme. Producing ZK proofs about ECDSA signatures has traditionally been a bottleneck for other ZK proof systems because standardized curves such as P256 use finite fields which do not support efficient number theoretic transforms. We overcome part of this bottleneck by designing a ZK proof system around sumcheck and the Ligero ZKargument system, by designing efficient methods for Reed-Solomon encoding over the required fields, and by designing specialized circuits for ECDSA and SHA that are more efficient for sumcheck. Our scheme is roughly 50x more efficient than prior work: proofs for ECDSA can be generated in 140ms on mobile phones. By building an efficient NARG for statements about ECDSA signatures, SHA256 hashing, and document format parsing for standardized identity formats such as MDOC, our anonymous credential scheme can be deployed without changing any issuer processes or without requiring any changes to mobile devices. When incorporated into a fully standardized identity protocol such as the ISO MDOC standard, we can generate a zero-knowledge proof for the MDOC presentation flow in 0.7–1.3 seconds on mobile devices depending on the credential size. These advantages make our scheme a promising candidate for privacy-preserving digital identity applications.