A New Approach To Efficient Revocable Attribute-Based Anonymous Credentials

Authors

David Derler (IAIK, Graz University of Technology), Christian Hanser (IAIK, Graz University of Technology), and Daniel Slamanig (IAIK, Graz University of Technology)

Abstract

Recently, a new paradigm to construct very efficient multi-show attribute-based anonymous credential (ABC) systems has been introduced in Asiacrypt'14. Here, structure-preserving signatures on equivalence classes (SPS-EQ-R), a novel flavor of structure-preserving signatures (SPS), and randomizable polynomial commitments are elegantly combined to yield the first ABC systems with O(1) credential size and O(1) communication bandwidth during issuing and showing. It has, however, been left open to present a full-fledged revocable multi-show attribute-based anonymous credential (RABC) system based on the aforementioned paradigm. As revocation is a highly desired and important feature when deploying ABC systems in a practical setting, this is an interesting challenge. To this end, we propose an RABC system, which builds upon the aforementioned ABC system, preserves its nice asymptotic properties and is in particular entirely practical. Our approach is based on universal accumulators, which nicely fit to the underlying paradigm. Thereby, in contrast to existing accumulator-based revocation approaches, we do not require complex zero-knowledge proofs of knowledge (ZKPKs) to demonstrate the possession of a non-membership witness for the accumulator. This is in part due to the nice rerandomization properties of SPS-EQ-R. Thus, this makes the entire RABC system conceptually simple, efficient and represents a novel direction in credential revocation. We also propose a game-based security model for RABC systems, which explicitly considers backward-unlinkability, and prove the security of our construction in this model. Finally, to demonstrate the value of our novel approach, we carefully adapt an efficient existing universal accumulator approach (as applied within Microsoft's U-Prove) to our setting and compare the two revocation approaches when used with the same underlying ABC system.

Venue

15th IMA International Conference on Cryptography and Coding (http://www0.cs.ucl.ac.uk/staff/J.Groth/IMACC.html)

Place and Date

Oxford, UK, December 15th - 17th, 2015

Publication Reference

David Derler, Christian Hanser, and Daniel Slamanig. "A New Approach To Efficient Revocable Attribute-Based Anonymous Credentials". In Cryptography and Coding - 15th IMA International Conference, IMACC 2015, Oxford, UK, December 15-17, 2015.

Bibtex

@inproceedings{dhs15,
   Author    = {David Derler and Christian Hanser and Daniel Slamanig},
   Title     = {{A New Approach To Efficient Revocable Attribute-Based Anonymous Credentials}},
   Booktitle = {Cryptography and Coding - 15th IMA International Conference, IMACC 2015, Oxford, UK, December 15-17, 2015},   
   Year      = {2015}, 
   Publisher = {Springer}
}