SPEAKER: Melissa Chase TITLE: Algebraic MACs and Keyed-Verification Credentials Abstract: Anonymous credentials were first proposed by Chaum in ‘85, but to date there are only two efficient approaches to constructing them. Systems based on the work of Brands are very efficient, but allow a verifier to link multiple presentations of the same credential; the Camenisch-Lysyanskaya approach is more costly but provides full anonymity. Here, we consider the problem of constructing anonymous credentials in a setting where the issuer of credentials is also the verifier, or where the issuer and verifier have a shared key. We will show that in this setting we can bring together the best aspects of the two previous approaches. Our approach is centered around the use of message authentication codes (MACs) instead of public key signatures as the basis of the credential system. To this end, we consider two algebraic MAC schemes in prime order groups. We first consider a selectively secure scheme proposed by Dodis et al, and show that it satisfies full unforgeability in the generic group model. We then consider a second scheme which increases costs by roughly a factor of two, and show that for this scheme we can prove security under the decisional Diffie-Hellman (DDH) assumption. Finally, we show how the structure of these MACs allows us to construct efficient protocols for issuing credentials and proving possession of credentials. This is joint work with Greg Zaverucha and Sarah Meiklejohn.