Attribute-Based Signatures with User-Controlled Linkability Without Random Oracles

© 2017, Springer International Publishing AG. Attribute-Based Signatures (ABS) are a versatile cryptographic primitive and have many applications. They are a generalization of many widely-used signature-related notions such as group, ring and mesh signatures. Attribute-Based Signatures with User-Controlled Linkability (ABS-UCL) add the notion of user-controlled linkability to ABS thus allowing users to anonymously and at will maintain a session with a verifier. In this work, we provide the first constructions of ABS-UCL dispensing with heuristic assumptions such as random oracles. We start by providing a generic construction which avoids some of the inefficiency pitfalls of existing constructions. We then provide efficient instantiations supporting expressive signing policies. We also give a concrete construction for threshold policies yielding constant-size signatures. Some of the building blocks we construct might be of independent interest.