Biblio

Group signatures are a central tool in privacy-enhancing cryptography, which allow members of a group to anonymously produce signatures on behalf of the group. Consequently, they are an attractive means to implement privacy-friendly authentication mechanisms. Ideally, group signatures are dynamic and thus allow to dynamically and concurrently enroll new members to a group. For such schemes, Bellare et al. (CT-RSA»05) proposed the currently strongest security model (BSZ model). This model, in particular, ensures desirable anonymity guarantees. Given the prevalence of the resource asymmetry in current computing scenarios, i.e., a multitude of (highly) resource-constrained devices are communicating with powerful (cloud-powered) services, it is of utmost importance to have group signatures that are highly-efficient and can be deployed in such scenarios. Satisfying these requirements in particular means that the signing (client) operations are lightweight. We propose a novel, generic approach to construct dynamic group signature schemes, being provably secure in the BSZ model and particularly suitable for resource-constrained devices. Our results are interesting for various reasons: We can prove our construction secure without requiring random oracles. Moreover, when opting for an instantiation in the random oracle model (ROM) the so obtained scheme is extremely efficient and outperforms the fastest constructions providing anonymity in the BSZ model - which also rely on the ROM - known to date. Regarding constructions providing a weaker anonymity notion than BSZ, we surprisingly outperform the popular short BBS group signature scheme (CRYPTO»04; also proven secure in the ROM) and thereby even obtain shorter signatures. We provide a rigorous comparison with existing schemes that highlights the benefits of our scheme. On a more theoretical side, we provide the first construction following the "without encryption" paradigm introduced by Bichsel et al. (SCN»10) in the strong BSZ model.

The paper deals with the implementation aspects of the bilinear pairing operation over an elliptic curve on constrained devices, such as smart cards, embedded devices, smart meters and similar devices. Although cryptographic constructions, such as group signatures, anonymous credentials or identity-based encryption schemes, often rely on the pairing operation, the implementation of such schemes into practical applications is not straightforward, in fact, it may become very difficult. In this paper, we show that the implementation is difficult not only due to the high computational complexity, but also due to the lack of cryptographic libraries and programming interfaces. In particular, we show how difficult it is to implement pairing-based schemes on constrained devices and show the performance of various libraries on different platforms. Furthermore, we show the performance estimates of fundamental cryptographic constructions, the group signatures. The purpose of this paper is to reduce the gap between the cryptographic designers and developers and give performance results that can be used for the estimation of the implementability and performance of novel, upcoming schemes.

Chu et al. (ASIACCS 2012) proposed group signature with time-bound keys (GS-TBK) where each signing key is associated to an expiry time τ. In addition to prove the membership of the group, a signer needs to prove that the expiry time has not passed, i.e., t\textbackslashtextlessτ where t is the current time. A signer whose expiry time has passed is automatically revoked, and this revocation is called natural revocation. Simultaneously, signers can be revoked before their expiry times have passed due to the compromise of the credential. This revocation is called premature revocation. A nice property of the Chu et al. proposal is that the size of revocation lists can be reduced compared to those of Verifier-Local Revocation (VLR) group signature schemes, by assuming that natural revocation accounts for most of signer revocations in practice, and prematurely revoked signers are only a small fraction. In this paper, we point out that the definition of traceability of Chu et al. did not capture unforgeability of expiry time of signing keys which guarantees that no adversary who has a signing key associated to an expiry time τ can compute a valid signature after τ has passed. We introduce a security model that captures unforgeability, and propose a GS-TBK scheme secure in the new model. Our scheme also provides the constant signing costs whereas those of the previous schemes depend on the bit-length of the time representation. Finally, we give implementation results, and show that our scheme is feasible in practical settings.

Digital signatures are perhaps the most important base for authentication and trust relationships in large scale systems. More specifically, various applications of signatures provide privacy and anonymity preserving mechanisms and protocols, and these, in turn, are becoming critical (due to the recently recognized need to protect individuals according to national rules and regulations). A specific type of signatures called "signatures with efficient protocols", as introduced by Camenisch and Lysyanskaya (CL), efficiently accommodates various basic protocols and extensions like zero-knowledge proofs, signing committed messages, or re-randomizability. These are, in fact, typical operations associated with signatures used in typical anonymity and privacy-preserving scenarios. To date there are no "signatures with efficient protocols" which are based on simple assumptions and truly practical. These two properties assure us a robust primitive: First, simple assumptions are needed for ensuring that this basic primitive is mathematically robust and does not require special ad hoc assumptions that are more risky, imply less efficiency, are more tuned to the protocol itself, and are perhaps less trusted. In the other dimension, efficiency is a must given the anonymity applications of the protocol, since without proper level of efficiency the future adoption of the primitives is always questionable (in spite of their need). In this work, we present a new CL-type signature scheme that is re-randomizable under a simple, well-studied, and by now standard, assumption (SXDH). The signature is efficient (built on the recent QA-NIZK constructions), and is, by design, suitable to work in extended contexts that typify privacy settings (like anonymous credentials, group signature, and offline e-cash). We demonstrate its power by presenting practical protocols based on it.