Revisiting Keyed-Verification Credentials [CAW 2025]

Talk 3 at the Cryptographic Applications Workshop (CAW) 2025 affiliated with Eurocrypt 2025. Website: https://caw.cryptanalysis.fun/previous/2025.html Presenter: Michele Orrù Slides: https://caw.cryptanalysis.fun/assets/pdf/2025/Revisiting_Keyed-Verification_Anonymous_Credentials.pdf Talk abstract: Keyed-verification anonymous credentials (KVACs) are now deployed in large-scale, privacy-critical systems like Signal and Tor. However, the existing theoretical framework lacks the adaptability to meet the diverse security requirements of various applications. For example, rate-limiting credentials can suffice with a weaker one-more unforgeability, while identity-based applications demand stronger extractability properties to ensure security when adversaries observe other users' credentials. In this talk, we address these limitations by introducing novel notions of extractability and one-more unforgeability for KVACs. We present significant improvements to two foundational KVAC schemes: - We demonstrate how the Chase et al. (CMZ/PS MAC) scheme can achieve statistical anonymity and a reduced issuance cost (from two to one group element). We also provide an updated security proof within the algebraic group model. - We introduce a more efficient issuance process (requiring one less group element) for the Barki et al. (BBDT/BBS MAC) scheme. Furthermore, we leverage the inherent designated-verifier nature of KVACs, where the verifier is known in advance. To this end, we introduce the concept of designated-verifier polynomial commitment schemes and present a pairing-free instantiation based on the popular KZG commitment scheme. This allows us to construct designated-verifier fully-succinct zk-SNARKs without pairings for algebraic groups by combining our commitment scheme with any interactive oracle proof. Our enhanced model for KVACs has the potential to significantly improve the deployment of larger protocols relying on these primitives. We will illustrate these benefits with concrete examples. Finally, we will dive into the ongoing concrete standardization efforts within the anonymous credentials ecosystem and discuss the wider landscape of privacy-enhancing credential technologies. This talk aims to provide a comprehensive overview of our advancements and their implications for the future of anonymous credentials.