Paper 2026/965

Device Binding for Anonymous Credentials on Legacy Phones

Abstract

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.

Note: Added optimizations for the Schnorr-type construction. Restructured document layout.