Group Signatures with Linking-Based Revocation: A Pragmatic Approach for Efficient Revocation Checks


Group Signatures with Linking-Based Revocation: A Pragmatic Approach for Efficient Revocation Checks


Daniel Slamanig, Raphael Spreitzer, Thomas Unterluggauer (IAIK, Graz University of Technology).


Group signatures represent an important mechanism for privacy-preserving applications. However, their practical applicability is restricted due to inefficiencies of existing membership revocation mechanisms that place a computational burden and communication overhead on signers and verifiers. In particular, it seems that the general belief (or unwritten law) of avoiding online authorities by all means artificially and unnecessarily restricts the efficiency and practicality of revocation mechanisms in group signature schemes. While a mindset of preventing online authorities might have been appropriate more than 10 years ago, today the availability of highly reliable cloud computing infrastructures could be employed to solve open challenges. More specifically, in order to overcome the inefficiencies of existing revocation mechanisms, we propose an alternative approach denoted as linking-based revocation (LBR). The novelty of LBR is its transparency for signers and verifiers that spares additional computations as well as updates. We introduce dedicated revocation authorities (RAs) that can be contacted for efficient (constant time) revocation checks. In order to protect these RAs and to reduce the trust in these authorities, we also introduce distributed controllable linkability such that RAs need to cooperate with multiple authorities to compute the required linking/revocation tokens. Besides efficiency, an appealing benefit of LBR is its generic applicability to pairing-based group signature schemes (PB-GSSs), including the popular BBS and XSGS schemes, and schemes from the recent ISO 20008-2 standard.


International Conference on Cryptology & Malicious Security hosted in Malaysia (Mycrypt 2016)

Place and Date

Kuala Lumpur, Malaysia,  December 1st-2nd 2016.