Breaking and Fixing Anonymous Credentials for the Cloud

Abstract

In an attribute-based credential (ABC) system, users obtain a digital certificate on their personal attributes, and can later prove possession of such a certificate in an unlinkable way, thereby selectively disclosing chosen attributes to the service provider. Recently, the concept of encrypted ABCs (EABCs) was introduced by Krenn et al. at CANS 2017, where virtually all computation is outsourced to a semi-trusted cloud-provider called wallet, thereby overcoming existing efficiency limitations on the user’s side, and for the first time enabling “privacy-preserving identity management as a service”.

While their approach is highly relevant for bringing ABCs into the real world, we present a simple attack fully breaking privacy of their construction if the wallet colludes with other users – a scenario which is not excluded in their analysis and needs to be considered in any realistic modeling. We then revise the construction of Krenn et al. in various ways, such that the above attack is no longer possible. Furthermore, we also remove existing non-collusion assumptions between wallet and service provider or issuer from their construction. Our protocols are still highly efficient in the sense that the computational effort on the end user side consists of a single exponentiation only, and otherwise efficiency is comparable to the original work of Krenn et al.

1 Introduction

Anonymous attribute-based credential systems (ABCs) – first envisioned by Chaum [11, 12] and extended in a large body of work [5,6,7,8,9,10, 15, 20,21,22] – are a cryptographic primitive enabling user-centric identity management. In ABC systems, a user receives a certificate on his personal data such as name, nationality, or date of birth from an issuer. Later, the user can present this certificate to service providers (or relying parties), thereby deciding which attributes to reveal or to keep private, in a way that makes different authentication processes unlinkable to each other. While the service provider receives strong authenticity guarantees on the received attributes, the user’s privacy is maintained, even against colluding issuers and service providers.

However, despite of their obvious benefits, ABC systems have not yet found their way into relevant real-world applications. One main reason for this are computational costs, which make them unsuitable for resource-constraint devices.

This drawback was recently addressed by Krenn et al. [18], who proposed a scheme dubbed EABC, where virtually all computations can be outsourced to a semi-trusted wallet. The underlying idea was that users get signatures on their attributes, encrypted under some proxy re-encryption [3] scheme, from the issuer, and upload signature and ciphertexts to the wallet, together with a re-encryption key from their own public key to the intended service provider’s public key. For presentation, the wallet re-encrypts the ciphertexts of the revealed attributes for the service provider, randomizes the remaining ciphertexts, and attaches a zero-knowledge proof of knowledge of a signature on the underlying ciphertexts. By the privacy property of the proxy re-encryption scheme, the wallet can translate encryptions from users to service providers, without ever learning any information about the underlying plaintexts. However, while solving the efficiency drawbacks of previous ABC systems, the attacker model underlying [18] is unrealistic, as they make very strong non-collusion assumptions between the wallet on the one hand, and service providers or issuers on the other hand. Even worse, we point out a trivial attack which fully breaks privacy in their construction. That is, their security analysis would only hold true if in addition also any collusion between wallet and other users is forbidden, which is clearly unrealistic, e.g., in the case of malicious administrators.

The Attack on Krenn et al. [18]. The fundamental problem of [18] is that for efficiency reasons their construction makes use of bi-directional multi-hop proxy re-encryption schemes. That is, having a re-encryption key $rk_{A\rightarrow B}$ that allows a proxy to translates a ciphertext $c_A$ encrypted under $pk_A$ to a ciphertext $c_B$ under $pk_B$ without learning the plaintext, and a re-encryption key $rk_{B\rightarrow C}$, the proxy can also translate $c_A$ to $c_C$ under $pk_C$ (multi-hop); furthermore, $rk_{A\rightarrow B}$ can efficiently be turned into $rk_{B\rightarrow A}$ (bi-directionality).

Assume now that Alice A wants to authenticate herself towards some service provider SP and thus stores $rk_{A\rightarrow SP}$ and encryptions $c_A$ of her personal attributes on the wallet. Let the malicious administrator M also sign up for SP and compute $rk_{M\rightarrow SP}$. Using the bi-directionality of the proxy re-encryption scheme, this directly gives $rk_{SP\rightarrow M}$, and using the multi-hop functionality, M can now translate all of A’s ciphertexts for herself, thereby fully breaking Alice’s privacy. Even more, because of the concrete choice of the deployed re-encryption scheme, the attacker could even recover Alice’s secret key as $sk_A=rk_{A\rightarrow SP}^{-1}\cdot sk_{M\rightarrow SP}\cdot sk_{M}^{-1}$ without having to assume a corrupt service provider. Actually, also the secret key of the service provider can be recovered as $sk_{SP}=sk_{M\rightarrow SP}\cdot sk_{M}^{-1}$.

Note that this attack is not specific to the deployed scheme of Blaze et al. [3], but arises in any multi-hop proxy re-encryption scheme that is used for outsourced data sharing application using long-term keys for the relying parties.

Mitigation Strategies. A straightforward solution to this problem might be to replace the deployed proxy re-encryption scheme by a single-hop and/or uni-directional encryption scheme. However, it turns out that the algebraic structures of existing signature and encryption schemes (with the required properties) would then no longer allow for efficient zero-knowledge proofs or knowledge, and the benefits of [18] would dissolve. Very informally speaking, the reason for this is that all such potential schemes would “consume” the one available pairing in the system. Furthermore, the other limitations of [18] (i.e., non-collusion assumptions) would not be addressed by such a modification.

Our Contribution. The main contribution of this paper is to overcome the security limitations of [18] without harming the efficiency of the scheme. That is, we provide an instantiation of an EABC system that does not require any artificial non-collusion assumptions, at the cost of only a single exponentiation on the user’s side. Furthermore, in contrast to [18], our system also gives metadata-privacy guarantees in the sense that the wallet only learns the policy for which it is computing the presentation tokens (i.e., which attributes are revealed and which remain undisclosed), but does no longer learn for which service provider it is computing the presentation, such that reliably tracking users becomes virtually impossible. Hiding the presentation policy within a set of policies could be achieved by the techniques of Krenn et al. [18, Sect. 6.1] for a linear overhead.

In a bit more detail, our contribution is multifold.

• Firstly, we replace the static long-term keys used by the service providers in [18] by ephemeral keys which are only used for a single authentication. This is achieved through an interactive key agreement protocol between the two parties, which guarantees freshness of the agreed keys. By this, a malicious administrator can no longer run the attack described above, as the $rk_{A\rightarrow SP}$ and $rk_{M\rightarrow SP}$ will no longer be bound to the same key of the service provider.

• Next, by using independent keys for the individual user attributes, even a collusion of service provider and wallet may only reveal the information that the user was willing to share with the service provider in any case.

• Thirdly, by replacing the signature scheme deployed in the issuance phase by a blinded version of the same scheme, our construction achieves high unlinkability guarantees even in the case of wallet-issuer collusions. Our blinded version of the structure-preserving signature scheme of Abe et al. [2] may be also of independent interest beyond the scope of this paper.

• Finally, by having a separate identity key that is not stored on the wallet but locally on the user’s device, the service provider is guaranteed that the user is actively participating in the protocol. While Krenn et al. [18] considered it undesirable that users need to carry secret key material with them, we believe that having no information stored locally results in unrealistic trust assumptions as there the wallet could impersonate a user towards any service provider that the user ever signed up for.

Outline. This paper is organized as follows. In Sect. 2 we discuss the building blocks of EABC systems, and in particular the schemes needed for our concrete instantiation. Then, in Sect. 3 we give a high-level description of EABC systems, its revised adversary model and security notions. Finally, Sect. 4 presents the concrete EABC instantiation, including security statements, the proofs of which are given in the full version of the paper.

2 Preliminaries

In the following we introduce the necessary background needed in the rest of the paper. In particular, we recap the notions of proxy re-encryption and structure-preserving signatures. We then present a transformation of the AGHO signature scheme [2] into a blinded version, which combines both features, blindness and structure-preservation, needed to efficiently instantiate EABC systems.

2.1 Notation

We denote the security parameter by $\lambda$. All probabilistic, polynomial time () algorithms are denoted by sans-serif letters ($\mathsf A, \mathsf B, \ldots$), and their combination in two-party or three party protocols by $\langle \mathsf A, \mathsf B\rangle$ and $\langle \mathsf A, \mathsf B, \mathsf C\rangle$, respectively. Whenever we sample a random element m uniformly from a finite set M, we denote this by . We write $\mathbb {Z}_q$ for the integers modulo a prime number $q, \mathbb {Z}_q^*$ for its multiplicative group, and for the modular inverses. We shall make extensive use of non-interactive zero-knowledge proofs of knowledge, where we use the Camenisch-Stadler notation to specify the proof goal. For example,

denotes a non-interactive zero-knowledge proof of knowledge proving knowledge of values $\alpha$, $\beta$, $\varGamma$ such that the expression on the right-hand side is satisfied. In most situations, extractability of zero-knowledge proofs will be sufficient. However, in a single case we will require simulation-sound extractability [17].

2.2 Anonymous and Re-randomizable Proxy Re-encryption

A proxy re-encryption (PRE) scheme is an asymmetric encryption scheme which allows a third party (the proxy) to transform ciphertexts encrypted for one party into ciphertexts encrypted for another one, without learning the underlying plaintext. As in [18], we instantiate our EABC system by using the scheme by Blaze et al. [3] (BBS); the associated issues in [18] are mitigated by a different use of the scheme. It possesses all the security properties needed for proving our system secure, yet it yields algebraic simple relations for encryption, re-encryption and re-randomization, altogether allowing for efficient zero-knowledge proofs of statements which involve these operations.

The BBS scheme consists of six algorithms,

where $\mathsf {Par}(\lambda )$ outputs the system parameters $pp= (\mathbb G, q, g)$, where $\langle g\rangle =\mathbb G$ is a group of prime order q. $\mathsf {Gen}(pp)$ generates a key pair (sk, pk) by and $pk=(pp, g^{sk})$. Encryption and decryption works as for ElGamal [16], i.e.,

where $m\in \mathbb G$ is the message, , and .

Given two key pairs $(pk_1,sk_1)$, $(pk_2,sk_2)$, their re-encryption key $rk=rk_{pk_1\rightarrow pk_2}$ is derived by $\mathsf {ReKey}(sk_1,pk_1, sk_2,pk_2) =sk_1\cdot sk_2^{-1}$, and

$$ \mathsf {ReEnc}(rk,c) = (c_1^{rk}, c_2) $$

transforms a ciphertext $c=(c_1,c_2)$ for $pk_1$ to one with respect to $pk_2$.

The relevant properties of the BBS scheme are summarized next.

Proposition 1

([3]). Under the DDH assumption in the message space $\mathbb G$, the BBS scheme is PRE-IND-CPA secure. That is,it is IND-CPA secure even under knowledge of (polynomially many) re-encryption keys that do not allow the adversary to trivially decrypt the challenge ciphertext.

Proposition 2

([18]). The BBS PRE scheme with re-randomization function , has the ciphertext re-randomization property. That is, given pk, a message m and its ciphertext c, then the output distribution of is computationally indistinguishable from that of .

Proposition 3

([18]). Under the DDH assumption in $\mathbb G$, the BBS proxy-re-encryption scheme is anonymous. That is, for any adversary $\mathsf {Adv}$ there exists a negligible function $\nu$ such that

2.3 Structure-Preserving Blind Signatures

The structure-preserving signature scheme of Abe et al. [1, 2] is based on asymmetric bilinear groups $(\mathbb G, \mathbb H, \mathbb T, e)$ with the feature that messages, signatures and verification keys consist of elements from $\mathbb G$ and/or $\mathbb H$, and verification is realized by pairing-product equations over the key, the message and the signature. This allows for efficient zero-knowledge proofs of claims involving the message and the signature, which is why they apply to various cryptographic protocols, e.g., [1, 14, 15, 18]. Similarly, our construction relies on the scheme in [2] (AGHO), since it allows to sign vectors of group elements. The AGHO scheme

consists of four algorithms. The setup algorithm $\mathsf {Par}$ generates the scheme’s parameters $pp=\left( \mathbb G,\mathbb H,\mathbb T, q,e, G, H\right)$ which are comprised of groups $\mathbb G$, $\mathbb H$, $\mathbb T$ of prime order q, a bilinear mapping $e: \mathbb G\times \mathbb H\longrightarrow \mathbb T$, and their respective generators G, H, e(G, H). $\mathsf {Gen}(pp)$ produces a private-public key pair (sk, vk),

$$ sk =\left( v,(w_i)_{i=1}^l,z\right) \quad \text {and}\quad vk = \left( V, (W_i)_{i=1}^l, Z) = (H^v, (H^{w_i}), H^z\right) , $$

where all the secret components v, z, and $w_i$ are randomly sampled from $\mathbb {Z}_q$. Given $m=(g_i)_{i=1}^l$ from $\mathbb G^l$, we have that , where

for . The verification condition of $\sigma =(R,S,T)$ is given by the two bilinear equations $e(S,H)\cdot e(R,V)\cdot \prod _i e(g_i,W_i)$ and $e(R,T)=e(G,H)$.

Theorem 1

([2]). In the generic group model, the AGHO signature scheme is strongly existentially unforgeable under adaptive chosen message attacks (sEUF-CMA). That is, for every adversary $\mathsf {Adv}$ there exists a negligible function $\nu$ such that

where $\mathsf {Adv}$ has access to a signing oracle , which on input m computes a valid signature $\sigma$, adds $(m,\sigma )$ to the initially empty list Q, and returns $\sigma$.

Blind signatures allow a user to obtain signatures in a way such that both the message as well as the resulting signature remain hidden from the signer. Restrictive blind schemes additionally allow the signer to encode information into the message, while still preserving the unlinkability of the resulting message-signature pair to the issuance session. The notion of restrictiveness goes back to Brands [4], and various adaptions have been made since then, e.g., [5, 13, 19]. In the context of anonymous credentials, and for the first time done in [5], such restricted message is typically a commitment on a value defined by the issuer. As such, we consider a restrictive blind signature scheme

being based on a blind signature scheme and a commitment scheme

for values x such that its output is in the message space of the signature. $\mathsf {Par}$, on input the security parameter $\lambda$, sets up the scheme’s parameters pp, including a compliant setting of $\mathsf {COM}$, and $\mathsf {Gen}(pp)$ generates a private-public key pair (sk, vk). The interactive algorithms $\mathsf {User}$ and $\mathsf {Signer}$ define the issuance protocol

between a user and a signer with private-public key pair (sk, pk), which on input a commonly agreed value $x\in X$ outputs to the user a certificate $(w,com,\sigma )$ which consists of a commitment com of x together with an opening w and a valid signature $\sigma$ on com. The verification is a separate validity check of the commitment com on (x, w) and the signature $\sigma$ on com.

The notions of unforgeability and blindness adapted to our setting of restrictive blind signatures are as follows.

Definition 1

A restrictive blind signature scheme is strongly unforgeable if for any adversary $\mathsf {Adv}$ there exists a negligible function $\nu$ such that

where $\mathsf {Adv}$ has access to a signing oracle which logs every successful query x in an initially empty list Q, and $mult(x^*)$ denotes the multiplicity of successful queries with $x=x^*$.

Definition 2

A restrictive blind signature scheme satisfies blindness, if for any adversary $\mathsf {Adv}$ there exists a negligible function $\nu$ such that

Blind AGHO Scheme. Our structure-preserving restrictive blind signature scheme is based on the AGHO scheme $\mathsf {SIG}_{AGHO}$, a compatible commitment scheme $\mathsf {COM}$, and two non-interactive extractable zero-knowledge proof systems, to both of which we refer to as without causing confusion. $\mathsf {Par}$, $\mathsf {Gen}$, and are the corresponding algorithms from $\mathsf {SIG}_{AGHO}$, besides that $\mathsf {Par}$ also queries $\mathsf {Par}_{COM}$ so that the commitments are elements of the messages space $\mathbb G^l$ of the AGHO scheme, and furthermore generates a common reference string for the zero-knowledge proof systems. We stress that our scheme is not merely based on a structure-preserving signature (as the ones from, e.g., [1, 14, 15]) but is structure-preserving by itself, which is an essential feature for our EABC instantiation.

Definition 3 (Blind AGHO signature on commited values)

The issuance protocol runs between a signer S with AGHO signing keys $sk=(v, (w_i)_{i=1}^l, z)$, vk, and a user U who wishes to receive a certificate $(w, com, \sigma )$ on the commonly agreed value x from the signer.

• 1. U computes com on x with opening w by using $\mathsf {Comm}_{COM}$. By our assumption on $\mathsf {COM}$, $m=com$ is from the message space of the signature, i.e. $m = (m_i)_{i=1}^l\in \mathbb G^l$.

• 2. U blinds m using a random pad , and obtains $\overline{m}=\left( \overline{m}_i\right) _{i=1}^l = \left( m_i\cdot P_i^{-1}\right) _{i=1}^l$. It further chooses , a random decomposition $f=f_1 + f_2$ of f, and sets $\overline{P} = \left( P_i^{e}\right) _{i=1}^l$, $(G_1, G_2,G_3) = (G^e,G^{f_1}, G^{e\cdot f_2})$. U then sends $\overline{m}$, $\overline{P}$, $(G_1,G_2,G_3)$ to S and gives a zero knowledge of wellformedness

  

  using the witnesses .

• 3. S verifies $\pi _U$, and returns $\bot$ if not valid. Otherwise it generates a random decomposition $z=z_1+z_2$ of its signing key’s z, and computes the ‘signatures’ $\overline{\sigma }= \left( \overline{R}, \overline{S}_1, \overline{S}_2, \overline{T}\right)$, with $\overline{R} = G^r$, , $\overline{S}_1 = G^{z_1} \cdot G_2^{-r\cdot v} \cdot \prod _{i=1}^l \overline{m}_i^{-w_i}$, $\overline{S}_2 = G_1^{z_2} \cdot G_3^{-r\cdot v} \cdot \prod _{i=1}^l \overline{P}_i^{-w_i}$, where . It then returns $\overline{\sigma }$ to U supplemented by a proof of wellformedness

  

  by using the witnesses $(\rho , \tau , (\omega _i)_i, \zeta _1, \zeta _2) = (r, r\cdot v, (w_i)_i, z_1, z_2)$.

• 4. U checks if $\pi _S$ is valid. If so, she outputs $\sigma = (R,S,T)$, where . (Otherwise she outputs $\bot$).

Corrrectness of the blind AGHO scheme is straightforward, the proof of the following theorem is given in the full version of the paper.

Theorem 2

Suppose that both in Definition 3 are extractable. If the commitment scheme $\mathsf {COM}$ is computationally hiding, then under the DDH assumption in $\mathbb G$ the restrictive blind signature scheme satisfies blindness. Furthermore, if $\mathsf {COM}$ is computationally binding, is strongly unforgeable in the generic group model.

3 EABC: High-Level Description

An encrypted attribute-based credential (EABC) system, introduced in [18], allows the delegation of selective disclosure to a third party in a privacy-preserving manner by means of proxy re-encryption and redactable signatures.

There are four types of players in an EABC system: issuers, users, services, and the central wallet. Each user U holds an identity key $sk_U$ proving her identity and which is securely stored on her trusted device (e.g., a smart card or TPM). U engages in an issuance protocol with an issuer I to receive an encrypted credential C on certain attributes only readable to her such that C is bound to her identity key $sk_U$. U further owns an account managed by the wallet W, a typically cloud-based identity provider, to which she uploads all of her encrypted credentials C while not providing it the encryption keys k(C). At any time later, when U wants to access a service S she is asked to attest some of her attributes. To convince S of the requested attributes without revealing any further testified information, U chooses one (or several) of her credentials from her account, selects a subset of attributes contained therein, and instructs W to engage in a presentation protocol with S, which serves the latter re-encryptions of the requested attributes together with a proof of validity. In this protocol, the wallet W undertakes (almost) all costly operations while reducing U’s effort to a possible minimum, requiring her only to supply the re-encryption keys for the selected attributes, and a proof of her consent (via her $sk_U$) to the presentation process. This last proof is also how the overall model of EABCs differs from that in [18], where no computation is required on the user’s side at all; however, as discussed earlier, we believe this is needed for a realistic attacker scenario, as otherwise the wallet could arbitrarily impersonate the user towards any service provider that the user ever signed up for.

3.1 Formal Definition

An EABC system with attribute space $\mathbb A$ is built on a structure-preserving blind signature scheme in the sense of Sect. 2.3, an anonymous re-randomizable proxy re-encryption scheme $\mathsf {PRE}$ (cf. Sect. 2.2) which acts on the message space of , and two zero-knowledge proof systems to which we both refer as $\mathsf {ZKP}$ without causing confusion. Formally, an EABC system

$$ \mathsf {EABC}=(\mathsf {Par}, \mathsf {Gen}_{I}, \mathsf {Gen}_{U}, \mathsf {Iss}, \mathsf {User}_I, \mathsf {User}_P, \mathsf {Wall}, \mathsf {Serv}) $$

consists of the () algorithms $\mathsf {Par}$, $\mathsf {Gen}_{I}$, and $\mathsf {Gen}_{U}$ for setup and key generation, and the interactive () algorithms $\mathsf {Iss}$, $\mathsf {User}_I$, $\mathsf {User}_P$, $\mathsf {Wall}$, $\mathsf {Serv}$ which are the components of the issuance and presentation protocol described below. Given the security parameter $\lambda$, $\mathsf {Par}\left( \lambda \right)$ generates the system parameters sp. These are comprised of the parameters for , $\mathsf {PRE}$, and a common reference string for $\mathsf {ZKP}$. Every user U holds a PRE secret-public key pair $(sk_U,pk_U)$ generated by $\mathsf {Gen}_{U}(sp)=\mathsf {Gen}_{PRE}(sp)$, her identity key, which is used to generate her certificate pseudonyms. On demand, a user repeatedly queries $\mathsf {Gen}_U(sp)$ to generate the encryption keys k(C) of her credentials. Each issuer I is holder of a key pair for the blind signature scheme $(sk_I,vk_I)\leftarrow \mathsf {Gen}_I(sp)$, $\mathsf {Gen}_{I}=\mathsf {Gen}_{BSIG}$, where $sk_I$ denotes the secret signing key and $vk_I$ its public verification key. Note that, unlike in [18] a service has no permanent key material for the proxy re-encryption scheme. Its PRE key will be an ephemeral one-time key, one for each presentation. Both the issuance and the presentation protocol run over server-side authenticated, integrity protected and confidential connections (associated with some random session identifier sid) and are as follows.

• Issuance. The issuance protocol

  $$ \big \langle \mathsf {User}_I\left( sid, sk_U, A, vk_I\right) , \mathsf {Iss}\left( sid, A, sk_I [, pk_U]\right) \big \rangle $$

  is performed between a user U with identity keys $(sk_U,pk_U)$ and an issuer I with signature key pair $(sk_I,vk_I)$ who is the supplier of the random session identifier sid. Both user and issuer agreed on the unencrypted content, the attributes $A=(a_i)_{i=1}^l\in \mathbb A^l$ beforehand. Depending on the type of issuance, it might be mandatory that U authenticates with its identity key, hence we leave it optional whether $pk_U$ is supplied to I or not, denoted by $[, pk_U]$. If successful, the protocol outputs to U an encrypted attribute-based credential $(C,vk_I)$ together with it’s (secret) key material $sk=sk(C)$, the latter of which U keeps on her device (and never provides it to a third party). In all other cases, the user receives $\bot$.

• Presentation. The presentation protocol is a three party protocol

  $$\begin{aligned} \Big \langle \mathsf {User}_P\left( sid, sk_U,sk(C) , D\right) , \mathsf {Wall}\left( sid, C,D, vk_I\right) , \mathsf {Serv}\left( sid, D, vk_I\right) \Big \rangle \end{aligned}$$

  and involves a user U with identity key $sk_U$, the wallet W which hosts U’s credential $(C,vk_I)$, and a service S, who provides the random session identifier sid. As before, sk(C) is the user’s secret key material for C. The user decides the attributes in C to be disclosed to S beforehand, associated with some index subset $D\subseteq \{1,\ldots ,l\}$. At the end of the protocol the service receives a presentation $C^*$ of C, which is comprised of the requested attributes, re-encrypted to a random one-time key $sk'$ of S, together with a proof of validity. The service verifies the proof by help of the issuer’s public key $vk_I$. If valid, the service accepts and decrypts the attributes using $sk'$. Otherwise it rejects and outputs $\bot$ to both U and W.

3.2 EABC Security Notions

We widen the adversary model from [18] to a setting which does not impose any trust assumption on the wallet. An attacker who controls several players of the EABC system, i.e. the central wallet, some of its users, service providers and issuers, should not be able to compromise the system in a more than obvious manner. That is, the adversary should not be able to

• 1. efficiently generate valid presentations which do not match any of the adversary’s credentials (unforgeability),

• 2. alter the statement of a presentation successfully without knowledge of the user (non-deceivability),

• 3. learn anything from the encrypted credentials besides the information disclosed under full control of the owner (privacy), and

• 4. distinguish presentations with the same disclosed content when the underlying encrypted credentials are not known to the adversary (unlinkability).

All security notions are given in a game-based manner, and we assume server-authenticated, confidential and integrity protected connections between the protocol participants.

Unforgeability for EABC. The unforgeability experiment paraphrases a malicious wallet and (adaptively many) malicious users, who altogether try to trick an honest service into accepting a presentation which does not match any of the adversary’s queries to an honest issuer. The experiment manages a list L which records the key material of all honest system participants during the entire lifetime of the system, i.e. the honest user’s identity keys $(pk_U,sk_U)$ and honest issuer keys $(vk_I,sk_I)$. The list L is also used to log all honest user’s credentials $(C, vk_I, sk_U, sk(C))$ under a unique handle h.

At any time the adversary $\mathsf {Adv}$ is given access to all public information contained in L, i.e. the public keys $pk_U$, $vk_I$ and the handles h, and as wallet $W^*$ it may retrieve the encrypted credentials $(C, vk_I)$ of every handle h contained in L.

Besides L, the experiment maintains another list $Q_\mathsf {Adv}$ used for logging all adversaries queries to honest issuers of the system. At first, the experiment initializes the system by running $sp\leftarrow \mathsf {Par}(\lambda )$, setting $L=\emptyset$, $Q_\mathsf {Adv}=\emptyset$, and returns sp to the adversary $\mathsf {Adv}$. The adversary may then generate and control adaptively many (malicious) players, and interact with the honest ones by use of the following oracles:

• Issuer oracle $\mathsf {I}(vk_I, A ~[, pk_U^*])$. This oracle, on input an issuer’s $vk_I$, attributes $A=(a_i)_i$, and optionally a public identity key $pk_U^*$, provides the adversary a (stateful) interface to an honest issuer’s $\mathsf {Iss}(A, sk_I ~[, pk_U^*])$ in the issuance protocol, provided that $vk_I$ is listed in L. If not, then the oracle generates a fresh pair of issuer keys $(sk_I, vk_I)\leftarrow \mathsf {Gen}_I(sp)$, adds it to L, and returns $vk_I$ to the caller $\mathsf {Adv}$. Whenever the protocol execution is successful from the issuer’s point of view, the oracle adds $(vk_I, (a_i)_i ~[, pk_U^*])$ to $Q_\mathsf {Adv}$.

• User-issuance oracle $\mathsf {U}_I(pk_U, A, vk_I^*)$. This oracle provides the interface to an honest user’s $\mathsf {User}_I(sk_U, A, vk_I^*)$ in an adversarily triggered issuance session. If $vk_I^*$ belongs to an honest issuer (being listed in L) the oracle aborts. As above, if $pk_U$ is not in L, the oracle adds fresh $(sk_U,pk_U)\leftarrow \mathsf {Gen}_U(pp)$ to L, and informs adversary about the new $pk_U$. Whenever the session yields a valid credential C for the user, the oracle adds $(C, vk_I^*, sk_U, sk(C))$ together with a fresh handle h to L, and outputs $(h, C,vk_I^*)$ to the adversary.

• Issuance oracle $\mathsf {UI}(pk_U, A, vk_I)$. This oracle performs a full issuance session between an honest user $pk_U$ and an honest issuer $vk_I$ on the attributes A, logs the resulting credential $(C, vk_I, sk_U, sk(C))$ in L and outputs $(C,vk_I)$, its handle h and the protocol transcript to the caller. Again, if either $pk_U$ or $vk_I$ are not in L the oracle generates the required identities, adds them to L and returns their new public keys before running the issuance.

• User-presentation oracle $\mathsf {U}_P(h,D)$. The user-presentation oracle initiates a presentation session for an existing handle h, and provides both interfaces of $\mathsf {User}_P(sk_U,sk(C),D)$, where $(sk_U, sk(C))$ belong to h, to the caller. If the handle h is not listed in L, the oracle aborts.

Eventually the adversary $\mathsf {Adv}$ runs a presentation session claiming credentials of some honest, but adversarily chosen $vk_I$. The experiment is successful if $\mathsf {Adv}$ manages to make $\mathsf {Serv}[vk_I]$ accept the presentation but the disclosed attributes $o_S^*= (a_i^*)_{i\in D^*}$ do not correspond to any of the adversary’s credentials issued by $vk_I$, which we denote by $o_S^* \notin Q_\mathsf {Adv}|_{D^*}$.

Definition 4

An EABC system $\mathsf {EABC}$ is unforgeable, if for any adversary $\mathsf {Adv}$ the success probability in the following experiment is bounded by a negligible function in $\lambda$.

In this experiment, $\mathsf {Adv}=\mathsf {Adv}^{\mathsf {I},\mathsf {U}_I, \mathsf {UI},\mathsf {U}_P}$ has access to the above defined (interactive) oracles, $o_U$ denotes the service’s verdict (output to the user-side), and $o_S^*$ are the disclosed attributes $(a_i^*)_{i\in D^{*}}$ (output on the service-side).

Non-deceivability of Honest Users. Non-deceivability (of honest users) is the infeasibility of successfully altering the presentation goal without being exposed to the honest user. Note that this property is not automatically covered by Definition 4, since such a change of goal might be just between two $vk_I$-credentials of one and the same user. We formulate this property by means of the non-deceivability experiment, which is almost identical to the unforgeability experiment, except that in the last step the adversary $\mathsf {Adv}$ opens a presentation session on behalf of an honest user for a credential C and index set D chosen by the adversary.

Definition 5

An EABC system $\mathsf {EABC}$ is non-deceivable towards a user, if for any adversary $\mathsf {Adv}$ the success probability in the following experiment is bounded by a negligible function in $\lambda$.

As in Definition 4, $\mathsf {Adv}= \mathsf {Adv}^{\mathsf {I},\mathsf {U}_I, \mathsf {UI},\mathsf {U}_P}$ has access to the oracles described in Sect. 3.2, $o_U^*$ denotes the serivce’s verdict (ouput to the user-side), and $o_S^*$ are the disclosed attributes $(a_i^*)_{i\in D^*}$ (output on the service-side).

Privacy for EABC. The adversary’s environment in ${{\,\mathrm{\mathsf {Exp}_{\mathsf {Adv}}^{priv}}\,}}$ is as in the unforgeability experiment from Sect. 3.2. That is, the experiment maintains a list L for the public and secret data of all honest participants, and the adversary is given access to the same honest participant oracles $\mathsf {I}$, $\mathsf {U}_I$, $\mathsf {UI}$, $\mathsf {U}_P$. First, the experiment generates the system parameters pp and a (random) subset $D\subseteq \{1,\ldots ,n\}$, and lets the adversary choose one of its issuance keys $vk_I^*$, two honest (not necessarily different) user identities $pk_{U_1}$, $pk_{U_2}$ and their queries $A_0$, $A_0$ being compliant on D, i.e. $A_1|_D=A_2|_D =(a_i)_{i\in D}$. Then the experiment performs issuance sessions with $vk_I^*$ on $A_0$ and $A_1$ (but does not log the resulting credentials $C_0$ and $C_1$ in the list L). It chooses a random bit b, tells the adversary $C_b$ and lets $\mathsf {Adv}$ participate in a presentation session for $C_b$ as many times as wanted. Based on its experience during all these interactions, the adversary tries to guess the random bit b.

Definition 6

An EABC system $\mathsf {EABC}$ satisfies privacy, if for any adversary $\mathsf {Adv}$ the advantage in the following experiment is bounded by a negligible function in $\lambda$.

Again, the adversary $\mathsf {Adv}= \mathsf {Adv}^{\mathsf {I},\mathsf {U}_I, \mathsf {UI},\mathsf {U}_P}$ is given access to the oracles as described in Sect. 3.2.

Unlinkability of Presentations. Unlinkability of presentations is the infeasability for a malicious service to link any two presentation sessions with the user or the credentials hidden behind the presentation. Here, the service may collude with issuers (in practice both can be even one and the same entity), but in contrast to the above experiments, the wallet W is assumed to be honest. We express this property by means of the unlinkability experiment which essentially is as ${{\,\mathrm{\mathsf {Exp}_{\mathsf {Adv}}^{priv}}\,}}$ from Sect. 3.2, but the adversary is not given access to the $\mathsf {U}_P$ oracle, and it is forbidden to retrieve any credential C from L. In return it is given access to the following honest wallet oracles:

• Wallet oracle $\mathsf {W}[h,D]$. This oracle provides the interfaces to an honest wallet’s $\mathsf {Wall}[C,D,vk_I]$, where C and $vk_I$ belong to the handle h listed in L. If the handle does not exist, the oracle aborts.

• User-wallet oracle $\mathsf {UW}[h,D]$. This oracle, on input the handle h and index subset D, looks up the corresponding credential C and key material $sk_U$, $sk=sk(C)$ in L and provides the caller the interfaces to the presentation session $\langle \mathsf {User}_P[sk_U, sk(C), vk_I], \mathsf {Wall}[C,D,vk_I], ~.~\rangle$. As above, if the handle does not exist the oracle aborts.

Definition 7

An EABC system $\mathsf {EABC}$ is unlinkable, if for any adversary $\mathsf {Adv}$ the advantage in the following experiment is bounded by a negligible function in $\lambda$.

In the experiment the adversary $\mathsf {Adv}=\mathsf {Adv}^\mathsf {I,U_1, UI, W, UW}$ is given access to all the honest-participant oracles from Sect. 3.2, and the above defined honest wallet oracle $\mathsf {W}$ and $\mathsf {UW}$.

4 Instantiating EABCs

We instantiate $\mathsf {EABC}=(\mathsf {Par}, \mathsf {Gen}_{I}, \mathsf {Gen}_{U}, \mathsf {User}_I,\mathsf {Iss}, \mathsf {User}_P,$ $\mathsf {Wall}, \mathsf {Serv})$ using the structure-preserving blind signature scheme from Sect. 2.3, the anonymous re-randomizable proxy re-encryption scheme $\mathsf {PRE}=\mathsf {PRE}_{BBS}$ by Blaze, Bleumer, and Strauss (BBS, cf. Sect. 2.2), and two non-interactive zero-knowledge proof systems (cf. Sect. 2.1), one of which is simulation extractable. For notational convenience, we shall refer to both as without causing confusion.

4.1 System Parameters and Key Generation

Given the security parameter $\lambda$, a trusted¹ third party generates the system parameters by $sp\leftarrow \mathsf {Par}(\lambda )$, which internally queries $\mathsf {Par}_{BSIG}$ and $\mathsf {Par}_{PRE}$ in such a way that the message space for and the ciphertext space of $\mathsf {PRE}$ is the same group $\mathbb G$ of prime order q. Furthermore, it uses $\mathsf {Gen}_{ZKP}$ to set up a common reference string for the . Specifically, the system parameters are

$$ sp=\left( L, \mathbb G,\mathbb H,\mathbb T, q, e, G, H, g, crs\right) , $$

whereas L is the maximum number of attributes allowed in a credential, $\mathbb G$, $\mathbb H$, $\mathbb T$ are the AGHO pairing groups of prime order q, with bilinear mapping $e: \mathbb G\times \mathbb H\longrightarrow \mathbb T$ and respective generators G, H, and e(G, H), $g\in \mathbb G$ is the generator for the BBS encryption scheme, and crs is the common reference string for the NIZK proof systems. We further assume that all attributes $a\in \mathbb A$ are represented by group elements from $\mathbb G$.

An issuer I’s signing key generated by $\mathsf {Gen}_I(sp)=\mathsf {Gen}_{BSIG}(sp)$ consists of the AGHO keys $sk_I=(v, (w_i)_{i=1}^l, z)$ and $vk_I=(V,(W_i)_{i=1}^l, Z)$, where $l\le L$, and a user’s identity key consists of the BBS keys $(sk_U,pk_U)$ generated by $\mathsf {Gen}_U(sp)=\mathsf {Gen}_{PRE}(sp)$.

4.2 Issuance

The issuance protocol is the restrictive blind AGHO signature (Definition 3) based on the commitment

$$ \mathsf {Comm}(sk_U,(a_i)_i) = (c_0, (pk_i,c_i)_i), $$

which embodies the encrypted certificate to be signed, being comprised by U’s certificate pseudonym , and the attribute encryptions with respect to fresh proxy re-encryption keys $(pk_i)_i$. Although authentication of U is outside the scope of the blind AGHO scheme, we nevertheless integrate it into the issuance protocol by extending the wellformedness proof of the restrictive scheme by a proof of knowing the secret key belonging to $pk_U$. The protocol runs over a server-authenticated, confidential and integrity protected channel.

Definition 8 (Issuance Protocol)

$\big \langle \mathsf {User}_I(sid, sk_U, (a_i)_{i=1}^l, vk_I), \mathsf {Iss}(sid, {pk_U}$, $(a_i)_{i=1}^l, sk_I)\big \rangle$ is a protocol between a user U with identity key $(sk_U,pk_U)$ and an issuer I with AGHO keys $(sk_I,vk_I)$. Both user and issuer agreed on the unencrypted content, the attributes $A = (a_i)_{i=1}^l\in \mathbb A^l$, beforehand.

• 1. U computes $com = \left( c_0, (pk_i,c_i)_{i=1}^l\right)$ by generating a fresh pseudonym and attribute encryptions using a fresh set of attribute keys $(sk_i,pk_i)\leftarrow \mathsf {Gen}_{BBS}(sp)$, $1\le i \le l$. For notational convenience we write $m=(m_{i,j}) = ( pk_i,c_{i,1},c_{i,2})_{i=0}^l$ for com, where we set $(sk_0,pk_0)=(sk_U,1)$ and $a_0=1$.

• 2. With the above described commitment scheme, U engages the restrictive blind signing session with I (Definition 3) to receive an encrypted credential

  $$\begin{aligned} C= \left\{ \left( c_0, \left( pk_i, c_i\right) _{i=1}^l\right) , \sigma = (R,S,T)\right\} , \end{aligned}$$

  with $\sigma$ being a valid AGHO signature by I on com, and with $(sk_i)_{i=0}^l$ as the opening of com. Demanding additional authentication of the user U by means of her identity key $sk_U$, the zero-knowledge proof $\pi _U$ as described in Definition 3, is explicitly described by

  

  which is bound to the unique session identifier sid. Here, the user U chooses , and , $0\le i\le l$, as witnesses.

Remark 1

In some situations a user might be allowed to stay anonymous towards the issuer. In such case the user’s public identity $pk_U$ is not part of the commited x and hence not provided to I, the term $g^{\kappa _0}=pk_U$ in $\pi _{U}$ is omitted. In another setting similar to [5, 7] a user might be known to I under a pseudonym of her. Here, U proves to I that the same secret key $sk_U$ is used in both $P_U=(P_{U,1},P_{U,2})$ and the certificate pseudonym, replacing $g^{\kappa _0}=pk_U$ by $c_{0,1}^{\kappa _0} = c_{0,2} ~\wedge ~ P_{U,1}^{\kappa _0} = P_{U,2}$.

4.3 Presentation

The presentation of a credential C, as described in full detail by Definition 10, is essentially based on re-encrypting a re-randomization of C into a selective readable version $\overline{C}$ for the service S, supplemented by two linked zero-knowledge proofs: the computationally costly presentation proof $\pi _P$, which is performed by the wallet W and which relates the transformed $\overline{C}$ to the original C (the latter, including its signature is hidden from S), and the ownership proof $\pi _O$ on the pseudonym of $\overline{C}$, proving knowledge of the secret identity key belonging to the pseudonym. The first proof is efficiently instantiated by help of the structure-preservation property of the blind AGHO scheme, the ownership proof supplied by the user is a simple proof of knowledge of a single exponent.

For the sake of readability, we gather the establishment of the service’s session keys and its corresponding transformation information in a separate subprotocol, the $\mathsf {ReKey}$ protocol. Both Protocols from Defintions 9 and 10 run over a server-authenticated, confidential and integrity protected channel, and are associated with the same random session identifier sid supplied by the service. Furthermore, the non-interactive proofs ($\pi _O$ and $\pi _S$ below) are bound to the context of the presentation, in particular the common public parameters sid, $vk_I$ and D.

Definition 9

($\mathsf {ReKey}$ protocol). This protocol between the user U and the service S is a subprotocol of the presentation protocol from Defintion 10.

• 1. U chooses a random one-time key , and forwards $sk'$ and D to S.

• 2. U re-randomizes² her pseudonym $c_0$ by , $\overline{c}_0 = \left( \overline{c}_{0,1}, \overline{c}_{0,2}\right) = \left( c_{0,1}^{e}, c_{0,2}^{e}\right)$ and proves to S that she is in posession of its secret key, by supplying a simulation extractable zero-knowledge proof

  

  in which she uses $\kappa = sk_U$ as witness.

• 3. S verifies $\pi _O$, and if valid it keeps $\overline{c}_0$ and $sk'$. Otherwise, S aborts the protocol. On the user side, U takes the secret attribute keys $(sk_i)_i$ belonging to C and determines and the re-encryption keys , $i\in D$.

Definition 10 (Presentation Protocol)

The presentation protocol of encrypted ABCs $\big \langle \mathsf {User}_P(sid, sk_U, (sk_i)_{i\in D}), \mathsf {Wall}(sid, C, D,vk_I), \mathsf {Serv}(sid, D, vk_I)\big \rangle$ is between a user U with identity key $sk_U$ who owns the credential C issued by I, the wallet W, and the service S (the supplier of the random session identifier sid). Here, $D\subseteq \{1,\ldots ,l\}$ denotes the index set of the attributes to be disclosed, and $(sk_i)_{i\in D}$ are U’s corresponding attribute keys.

• 1. U performs Protocol from Definition 9 with S, and if successful it sends the re-randomized one-time pseudonym $\overline{c}_0$ together with the re-encryption keys $rk_0'$, $\left( rk'_i\right) _{i\in D}$ and D to W.

  From now on we proceed similar to [18]:

• 2. (Randomization and re-encryption) For $i\in D$, the wallet W re-randomizes the ciphertexts $c_i$ to $\overline{c}_i = \left( c_{i,1}\cdot g^{f_i}, c_{i,2}\cdot pk_i^{f_i}\right)$, with . All other attributes are randomized inconsistently, by choosing $v_{i,0}$, $v_{i,1}$, and setting $\overline{pk}_i = pk_i \cdot g^{v_{i,0}}$, $\overline{c}_i = \left( c_{i,1} \cdot g^{v_{i,1}}, c_{i,2}\cdot g^{v_{i,3}}\right)$ for all $i\not \in D$. Using the re-encryption keys $\left( rk_i'\right) _{i\in D}$ the wallet translates the attributes belonging to $i\in D$ by $d_i =\mathsf {ReEnc}_{BBS}\left( rk_i', \overline{c}_i\right) =\left( \overline{c}_{i,1}^{rk_i'}, \overline{c}_{i,2}\right)$.

• 3. (Presentation) W randomizes T by $\overline{T} = T^x$, , forwards $\left( d_i \right) _{i\in D}$, $\left( \overline{pk}_i, \overline{c}_i\right) _{i \notin D}$, and $\overline{T}$ to S, and provides a wellformedness proof of these elements via

  

  which is defined by the relations (1) and (2) below.

• 4. S verifies $\pi _P$ using the verified one-time pseudonym received in Protocol 9. If valid, it decrypts the attributes $\left( d_i\right) _{i\in D}$ with its one-time key $sk'$. (Otherwise S outputs $\bot$).

Remark 2

Showing more than one credential is efficiently implemented by merging their ownership proofs to a single which simultaneously proves knowledge of $sk_U$ on all used pseudonyms, .

Equations (1) and (2) mentioned in Protocol 10, state that is a valid signature for a quadratic derivative of the above group elements $\left( \overline{c}_{0,1}, \overline{c}_{0,2}\right)$, $(d_{i,1}, d_{i,2})_{i\in D}$ and $(\overline{pk}_i,\overline{c}_{i,1},\overline{c}_{i,2})_{i\not \in D}$, i.e.

(1)

where V, Z, and $(W_{i,0}, W_{i,1}, W_{i,2})_{i=0}^l$ are the components of the issuers verification key, and

$$\begin{aligned} e(P, \overline{T}) \cdot e(G,H)^{-\xi }&= 1. \end{aligned}$$

(2)

Linearization of the quadratic terms in (1) is accomplished by standard techniques and given in the full version of the paper. An honest prover chooses $(P,\varSigma , \xi ) = (R,S,x)$, and uses the parameters from step 2 of Protocol 10, i.e. $\eta = rk_0'$, for $i\in D$, and $\left( \nu _{i,0},\nu _{i,1},\nu _{i,2}\right) = \left( v_{i,0}, v_{i,1}, v_{i,2}\right)$ for all $i\not \in D$.

Theorem 3

Suppose that the AGHO signature scheme is EUF-CMA secure, and that the from Definition 9 is simulation extractable. Then, under the DDH-assumption in $\mathbb G$,

• 1. the proxy re-encryption scheme $\mathsf {PRE}_{BBS}$ is PRE-IND-CPA secure, anonymous, and has the ciphertext re-randomization property,

• 2. the structure-preserving blind signature scheme $\mathsf {BSIG}_{AGHO}$ is unforgeable and has the blinding property,

hence our EABC system satisfies unforgeability, non-deceivability, privacy and unlinkability in the sense of Sect. 3.2.

The proof of Theorem 3 is given in the full version of the paper.

5 Conclusions

In this paper, we pointed out a problem in Krenn et al.’s cloud-based attribute-based credential system [18] by presenting a simple and efficient attack fully breaking the privacy guarantees of their construction in the real world. We then provided a revised, provably secure construction which not only solves this issue, but also reduces the trust assumptions stated in [18] with regards to collusions between the central wallet and other entities in the system. As a building block of potentially independent interest we presented a blind variant of the Abe et al. structure-preserving signature scheme [2].

While we did not provide a concrete implementation of our construction, we expect only very minor performance drawbacks with respect to [18], while correcting all the deficiencies in their work. There, for a security parameter of $\lambda =112$, all computations on all parties’ sides were between 50ms and 440ms when presenting 12 out of 25 attributes. By inspecting the computational efforts needed in our protocol and theirs, one can see only negligible differences, except for the proof of knowledge of a single exponent which is required on the user’s side in our construction. However, such computations are efficiently doable, and thus our protocol still provides a significant performance improvement compared to fully locally hosted “conventional” attribute-based credential systems. Finally, we leave a full-fledged implementation, not only of the cryptographic algorithms but of the full system, as open work to demonstrate the real-world applicability of EABCs in general and our construction in particular, and to help ABC systems to finally pave their way into the real world. For this, several approaches can be envisioned, in particular for the presentation protocol, where the optimal choice may depend on external constraints as well as requirements of the specific application domain. Firstly, using the wallet also as a communication proxy, would not require further network anonymisation layers, yet leak metadata to the wallet. Alternatively, by merely outsourcing the computational effort to the wallet and routing the traffic through the user, one could reach the same privacy guarantees as in conventional systems, at the cost of increased bandwidth requirements compared to the first approach; furthermore, the responsibility of transport layer anonymity would be with the user. Finally, an approach close to OpenID Connect could be achieved by combining these two approaches.