Paper 2016/1073

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

Daniel Slamanig, Raphael Spreitzer, and Thomas Unterluggauer


Group signature schemes (GSS) represent an important privacy-enhancing technology. However, their practical applicability is restricted due to inefficiencies of existing membership revocation mechanisms that often place a too large computational burden and communication overhead on the involved parties. Moreover, 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 GSSs. 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 used 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) which is based on the concept of controllable linkability. The novelty of LBR is its transparency for signers and verifiers that spares additional computations as well as updates. We therefore 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 involved online authorities, we additionally introduce distributed controllable linkability. Using latter, RAs cooperate with multiple authorities to compute the required linking information, thus reducing the required trust. Besides efficiency, an appealing benefit of LBR is its generic applicability to pairing-based GSSs secure in the BSZ model as well as GSSs with controllable linkability. This includes the XSGS scheme, and the GSSs proposed by Hwang et al., one of which has been standardized in the recent ISO 20008-2 standard.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. International Conference on Cryptology & Malicious Security 2016 (Mycrypt 2016)
Group signaturescontrollable linkabilitylinking-based revocationefficient revocation mechanism
Contact author(s)
raphael spreitzer @ iaik tugraz at
2017-07-19: revised
2016-11-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Slamanig and Raphael Spreitzer and Thomas Unterluggauer},
      title = {Linking-Based Revocation for Group Signatures: A Pragmatic Approach for Efficient Revocation Checks},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1073},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.