Melissa Chase

Algebraic MACs and Keyed-Verification 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 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.