Paper 2026/965

Device Binding for Anonymous Credentials on Legacy Phones

Alexandros Zacharakis, Hasso Plattner Institute, University of Potsdam

Abstract

Digital identity systems are currently build around the globe, aiming to enable secure, usable, but also privacy-preserving user authentication. Concretely, the EUDI Wallet developed in Europe requires to ensure selective attribute disclosure and unlinkable authentication. This essentially mandates the use of anonymous credentials, that have been developed for this exact purpose over the last 20 years. However, they are not integrated in the current solutions as they lack an essential feature: device binding. That is, binding credentials stored on the users' phones to a secure hardware element therein, in order to prevent credential cloning or sharing. Device binding is typically done through encoding a device public key into the user's credential and requiring a fresh signature under the corresponding and hardware-protected secret key - the proof-of-possession (PoP) - when presenting the credential. While academic solutions exist that realize efficient device binding for anonymous credentials, they are not compatible with the secure hardware currently available in consumer phones. The main challenge lies in the underlying curves: all efficient anonymous credentials, (and their native device binding protocols) require the use of pairing-friendly curves, whereas existing phones are essentially restricted to ECDSA signatures and classic P256 curves. In this work, we show how to bridge these two systems, enabling device-binding for pairing-based credentials on legacy phones, i.e., relying solely on standard ECDSA signatures for the PoP. We present three different constructions with different trade-offs in efficiency and in protocol complexity. Our most efficient solution generates unlinkable bridging proofs of size ~1.5KB in less than ~500ms by relying on a (very simple) arithmetic circuit, whereas the most conservative approach (without circuits) takes as well ~500ms and comes with proof size of ~175KB. All our solutions share a common blueprint, and we express them in the reductions of knowledge framework (Crypto 2023) to reflect this is in our protocols' design. This framework allows to modularly construct complex zero-knowledge proofs in an elegant and intuitive manner, greatly facilitating the security analysis and the 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 complex real-world systems.