Cryptology ePrint Archive: Report 2016/1073

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

Daniel Slamanig and Raphael Spreitzer and Thomas Unterluggauer

Abstract: 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.

Category / Keywords: cryptographic protocols / Group signatures, controllable linkability, linking-based revocation, efficient revocation mechanism

Original Publication (with minor differences): International Conference on Cryptology & Malicious Security 2016 (Mycrypt 2016)

Date: received 16 Nov 2016, last revised 19 Jul 2017

Contact author: raphael spreitzer at iaik tugraz at

Available format(s): PDF | BibTeX Citation

Version: 20170719:134309 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]