Cryptology ePrint Archive: Report 2015/580

Composable & Modular Anonymous Credentials: Definitions and Practical Constructions

Jan Camenisch and Maria Dubovitskaya and Kristiyan Haralambiev and Markulf Kohlweiss

Abstract: It takes time for theoretical advances to get used in practical schemes. Anonymous credential schemes are no exception. For instance, existing schemes suited for real-world use lack formal, composable definitions, partly because they do not support straight-line extraction and rely on random oracles for their security arguments.

To address this gap, we propose unlinkable redactable signatures (URS), a new building block for privacy-enhancing protocols, which we use to construct the first efficient UC-secure anonymous credential system that supports multiple issuers, selective disclosure of attributes, and pseudonyms. Our scheme is one of the first such systems for which both the size of a credential and its presentation proof are independent of the number of attributes issued in a credential. Moreover, our new credential scheme does not rely on random oracles.

As an important intermediary step, we address the problem of building a functionality for a complex credential system that can cover many different features. Namely, we design a core building block for a single issuer that supports credential issuance and presentation with respect to pseudonyms and then show how to construct a full-fledged credential system with multiple issuers in a modular way. We expect this flexible definitional approach to be of independent interest.

Category / Keywords: cryptographic protocols / (Fully) structure preserving signatures, vector commitments, anonymous credentials, universal composability, Groth-Sahai proofs

Date: received 11 Jun 2015

Contact author: markulf at microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20150621:080045 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]