ACE Seminar: Algebraic MACs and Lightweight Anonymous Credentials

Speaker: Dr Melissa Chase

Date/Time: 12-Nov-2015, 16:00 UTC

Venue: MPEB 1.02



A credential system allows a user to obtain credentials from an organization and then at some later point prove to that organization (or some other party) that she has been given appropriate credentials.  We say the system is anonymous if this proof does not reveal anything beyond this fact.  Here we are particularly interested in credentials which are reusable, in that the user can present the same credential many times, and the organization will not be able to distinguish this from many users each with her own credentials.
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 (e.g. U-Prove)  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.  Our goal here is to match the advantages of both; we can achieve this in a setting where the same organization issues and verifies credentials.
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 introduce a new 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 Sarah Meiklejohn and Greg Zaverucha.


Melissa Chase is a researcher in the Cryptography group at MSR Redmond, focusing on provably secure privacy.  Before joining Microsoft she received  a B.S. in Computer Science and Mathematics from Harvey Mudd College, and an M.S. and Ph.D. in Computer Science from Brown University.  She has worked in a number of different areas within cryptography, including anonymous credentials, electronic cash, attribute based encryption, and re-encryption, as well as more theoretical topics such as zero knowledge proofs and size-hiding computation.

Add to Calendar

This page was last modified on 27 Mar 2014.