Paper 2013/516

Algebraic MACs and Keyed-Verification Anonymous Credentials

Melissa Chase, Sarah Meiklejohn, and Gregory M. Zaverucha


We consider the problem of constructing anonymous credentials for use in a setting where the issuer of credentials is also the verifier, or more generally where the issuer and verifier have a shared key. In this setting we can use message authentication codes (MACs) instead of public key signatures as the basis for the credential system. To this end, we construct two algebraic MACs in prime-order groups, along with efficient protocols for issuing credentials, asserting possession a credential, and proving statements about hidden attributes (e.g., the age of the credential owner). We prove the security of the first scheme in the generic group model, and prove the security of the second scheme -- using a dual-system-based approach -- under decisional Diffie-Hellman (DDH). Our MACs are of independent interest, as they are the only uf-cmva-secure MACs with efficient proofs of knowledge. Finally, we compare the efficiency of our new systems to two existing constructions of anonymous credentials: U-Prove and Idemix. We show that the performance of the new schemes is competitive with U-Prove (which is not provably secure, whereas ours is based on DDH), and many times faster than Idemix.

Note: This is the full version

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM CCS 2014
anonymous credentials
Contact author(s)
gregz @ microsoft com
2014-09-08: last of 2 revisions
2013-08-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Melissa Chase and Sarah Meiklejohn and Gregory M.  Zaverucha},
      title = {Algebraic MACs and Keyed-Verification Anonymous Credentials},
      howpublished = {Cryptology ePrint Archive, Paper 2013/516},
      year = {2013},
      doi = {10.1145/2660267.2660328},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.