International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Server-Aided Anonymous Credentials

Authors:
Rutchathon Chairattana-Apirom , University of Washington
Franklin Harding , Brown University
Anna Lysyanskaya , Brown University
Stefano Tessaro , University of Washington
Download:
Search ePrint
Search Google
Conference: CRYPTO 2025
Abstract: This paper formalizes the notion of server-aided anonymous credentials (SAACs), a new model for anonymous credentials (ACs) where, in the process of showing a credential, the holder is helped by additional auxiliary information generated in an earlier (anonymous) interaction with the issuer. This model enables lightweight instantiations of publicly verifiable and multi-use ACs from pairing-free elliptic curves, which is important for compliance with existing national standards. A recent candidate for the EU Digital Identity Wallet, BBS#, roughly adheres to the SAAC model we have developed; however, it lacks formal security definitions and proofs. In this paper, we provide rigorous definitions of security for SAACs, and show how to realize SAACs from the weaker notion of key-verification ACs (KVACs) and special types of oblivious issuance protocols for zero-knowledge proofs. We instantiate this paradigm to obtain two constructions: one achieves statistical anonymity with unforgeability under the Gap q-SDH assumption, and the other achieves computational anonymity and unforgeability under the DDH assumption.
BibTeX
@inproceedings{crypto-2025-35627,
  title={Server-Aided Anonymous Credentials},
  publisher={Springer-Verlag},
  author={Rutchathon Chairattana-Apirom and Franklin Harding and Anna Lysyanskaya and Stefano Tessaro},
  year=2025
}