Paper 2013/516

MAC Schemes with Efficient Protocols and Keyed-Verification Anonymous Credentials

Melissa Chase 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 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 of the credential system. To this end, we construct two algebraic MAC schemes in prime order groups, along with efficient protocols for issuing credentials, asserting possession a credential, and proving statements about the attributes.Security of the first scheme is proven in the generic group model, and we show that the second is secure under the decisional Diffie-Hellman (DDH) assumption, using a dual system-based approach. Finally, we compare the efficiency of our new systems to two traditional credential systems, U-Prove and Idemix. We show that performance of the new schemes are competitive with U-Prove, and many times faster than Idemix. This brings together the best aspects of these two existing systems: the efficiency of U-Prove combined with the multi-show unlinkability of Idemix.