# Biblio

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.

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.