Cryptology ePrint Archive: Report 2013/516

Algebraic MACs and Keyed-Verification Anonymous Credentials

Melissa Chase and Sarah Meiklejohn and Gregory M. Zaverucha

Abstract: 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.

Category / Keywords: cryptographic protocols / anonymous credentials

Original Publication (with major differences): ACM CCS 2014

Date: received 19 Aug 2013, last revised 8 Sep 2014

Contact author: gregz at microsoft com

Available format(s): PDF | BibTeX Citation

Note: This is the full version

Version: 20140908:193925 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]