Anonymous Credentials from ECDSA

Anonymous digital credentials allow a user to prove possession of an attribute that has been asserted by an identity issuer without the user revealing any extra information about themselves. For example, a user who has received a digital passport credential can prove their “age is > 18 ” without revealing any other attributes such as their name or date of birth. Despite their clear application to privacy-preserving authentication, anonymous credential schemes have been difficult to deploy at scale. Part of the difficulty arises because schemes in the literature, such as BBS+, use new cryptographic primitives that require system-wide changes to existing issuer infrastructure. In addition, 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+ require updates to the hardware on every user's device. We propose new ZK techniques which enable the construction of an anonymous credential scheme for the legacy Elliptic Curve Digital Signature Algorithm (ECDSA) signature scheme. By adding efficient ZK arguments for statements about SHA-256 and document parsing for ISO-standardized identity formats, we construct the first ZK proof of posession of a credential that can be deployed without changing any issuer processes, without changes to mobile devices, and without requiring non-standard cryptographic assumptions. Furthermore, our proof system itself only relies on SHA-256 as its complexity assumption. Producing ZK proofs about ECDSA signatures has 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 this bottleneck by designing a ZK proof system around sumcheck and the Ligero argument system, by designing efficient methods for Reed-Solomon encoding over the required fields, and by designing specialized circuits for ECDSA. Our proofs for ECDSA can be generated in as little as ≈ 20 ms. When incorporated into a fully standardized identity protocol such as the ISO MDOC standard, our system can generate a zero-knowledge proof for the MDOC presentation flow in a few hundred ms on mobile devices. These advantages make our scheme a promising candidate for privacy-preserving digital identity applications.