Device Binding for Anonymous Credentials on Legacy Phones
Sofía Celi (Brave Software), Anja Lehmann (Hasso Plattner Institute, University of Potsdam), Shai Levin (Chalmers University of Technology, University of Gothenburg), Alexandros Zacharakis (Hasso Plattner Institute, University of Potsdam) | Security, Cryptography
Digital identity systems are being deployed worldwide to enable secure, privacy-preserving authentication. In this regards, Europe’s EUDI Wallet mandates selective attribute disclosure and unlinkable authentication, effectively requiring anonymous credentials. Yet current proposed solutions omit them because they lack device binding: tying a credential to a secure hardware element on the user’s device to prevent cloning or sharing. Device binding encodes a device public key in the credential and, at presentation time, produces a fresh signature under the hardware-protected secret key – a proof-of-possession (PoP). While academic solutions for device binding exist, they require pairing-friendly curves, whereas consumer phones are restricted to ECDSA over P-256.
In this work, we bridge this gap by enabling device binding of pairing-based credentials using the device’s standard ECDSA signature as the PoP. To explore the efficiency–complexity trade-off of such solution, we present three constructions. Our most efficient solution generates unlinkable binding proofs of size ~1.5kB in under ~400ms using a simple arithmetic circuit, whereas the most conservative circuit-free approach matches this proving time at ~122kB. All solutions follow a common blueprint expressed in the reductions of knowledge framework (Crypto 2023), which enables modular composition of zero-knowledge proofs and eases both security analysis and implementation. This framework has previously been mainly used in a theoretical context, and our work demonstrates that it is a powerful tool to design, analyze and implement advanced real-world systems.
