Attribute-Based Credentials With Verifiable Human Binding: Toward Compactness and Revocability

Digital and physical identity authentications are often implemented concurrently to meet strict access control for online services. Although privacy-preserving digital credentials provide strong guarantees such as anonymity and minimal disclosure, these benefits are compromised if holders must simultaneously present physical identification (e.g., government issued IDs) to establish ownership. To securely bind digital credentials to their physical holders while preserving privacy, a new protocol called card-based anonymous credentials (cbAC) was proposed by Hesse et al. (USENIX Security'23). However, this approach faces two significant drawbacks: the size of the communication during credential presentation scales linearly with the number of disclosed attributes, and it lacks revocability, which is essential for internal governance, including identity management and accountability. In this paper, we bridge the above gap by first introducing a constant-size two-party proof of knowledge protocol in asymmetry settings, where there exists a disparity in storage and computational resources between the two parties. Furthermore, building upon this two-party proof of knowledge protocol and utilizing signatures with randomizable keys, we meticulously design a cbAC scheme that is both efficient and capable of supporting revocation. We formalize all notions and conduct a rigorous security proof of the proposed construction. Finally, we present benchmarks from our implementation to illustrate the better than-state-of-the-art performance and features of our solutions.