Decentralized Policy-Hiding ABE with Receiver Privacy

Abstract

Attribute-based encryption (ABE) enables limiting access to encrypted data to users with certain attributes. Different aspects of ABE were studied, such as the multi-authority setting (MA-ABE), and policy hiding, meaning the access policy is unknown to unauthorized parties. However, no practical scheme so far provably provides both properties, which are often desirable in real-world applications: supporting decentralization while hiding the access policy. We present the first practical decentralized ABE scheme with a proof of being policy-hiding. Our construction is based on a decentralized inner-product predicate encryption scheme, introduced in this paper, which hides the encryption policy. It results in an ABE scheme supporting conjunctions, disjunctions and threshold policies, that protects the access policy from parties that are not authorized to decrypt the content. Further, we address the issue of receiver privacy. By using our scheme in combination with vector commitments, we hide the overall set of attributes possessed by the receiver from individual authorities, only revealing the attribute that the authority is controlling. Finally, we propose randomizing-polynomial encodings that immunize the scheme in the presence of corrupt authorities.

1 Introduction

Attribute-based encryption (ABE), first proposed by Sahai and Waters [25], addresses the need to provide fine-grained access control to data according to some policy. In contrast to traditional public-key encryption, data is encrypted not under a public key associated with the identity of the intended recipient, but rather under a set of attributes that can be possessed by one or more entities.

This concept falls into the more general paradigm of functional encryption (FE) [6, 24]. In functional encryption, a setup algorithm produces a matching pair of public/secret keys $( mpk , msk )$. The master public key $mpk$ enables anyone to encrypt data and the master secret key $msk$ enables its holder to issue functional keys—for example, a secret key $sk _{\!f}$ for a certain function f. Given a ciphertext $ct = \mathop {\mathsf {Encrypt}}\nolimits ( mpk ,x)$ of some message x, anyone who has $sk _{\!f}$ can obtain f(x). An important subclass of functional encryption is Predicate Encryption (PE) [7, 16], and in particular Inner-Product Predicate Encryption (IPPE), where data can be accessed if and only if the ciphertext $ct$ and the key $sk$ satisfy a certain predicate $P( sk , ct )$ (namely, orthogonality).

To illustrate ABE, suppose we want to encrypt data stored on the university server such that it is accessible to anyone who “is a network administrator, or a university student and is taking the class Introduction to Cryptography”. In single-authority ABE, an authority associated with the university can be in charge of verifying a user’s identity and providing a key that certifies all her attributes. However, it is often impractical to rely on a single authority to verify and certify all possible attributes. Consider this example: different university departments are in charge of protecting their own data independently, while also being supported by the IT department. In this case a policy can be “is network administrator or computer science department staff”. The university IT and the computer science department are, in this case, two independent authorities that verify and issue keys for their own attributes.

Multiple works addressed this issue, starting with the ones by Chase [9], Chase and Chow [10], and Müller et al. [18] on multi-authority ABE, and following with a decentralized ABE scheme by Lewko and Waters [17]. This last construction enables to encrypt a ciphertext under a general access structure, while the corresponding secret keys are issued by independent authorities that do not need to communicate with each other, or with any central authority, and only refer to common parameters generated by a one-time trusted setup. Another construction with similar properties is by Okamoto and Takashima [20].¹

Those schemes, however, do not address the often desirable property of hiding the encryption policy. Attribute-hiding means that the ciphertext policy is protected and remains unknown under inspection of the ciphertext. There is a weaker notion, called weakly attribute-hiding, which guarantees that the policy is hidden from anyone but a party that is capable of decrypting the ciphertext; i.e., information about it is leaked only upon successful decryption. It is important to be able to hide the access policy since it can contain sensitive meta-data. One example is messaging or emails addressed to a group of users with certain attributes. In addition to protecting the content we may want to hide the target group. In the full paper, we show that an adversary can reveal the encryption policy in Lewko-Waters’ scheme, even when it is not explicitly given. While it is yet to be studied whether there is a policy inference attack on the scheme in [20] or whether it can be proved to be weakly attribute-hiding for inner-products, the paper neither claims, nor proves this property. In this work we set out to provide this important property in a decentralized setting.

While we previously illustrated the use of decentralized ABE with a simple toy example, it has practical real-world applications. Prior work on multi-authority ABE mentions supporting multiple authorities authorizing access to DRM-protected content [18], where hiding the policy is important to protect meta-data that can reveal potentially sensitive information about the content. To mention another example, ABE has recently been explored in the context of access-control for blockchains [22, 23]. Indeed, in a blockchain setting, both decentralization and policy protection are desirable. Attribute-based encryption or signatures can be an extension of the naïve multi-signature implementations in early blockchain-based crypto-currencies like Bitcoin [19], while policy-hiding can serve to preserve the recipient’s privacy.

Our Contributions. We propose a decentralized, policy-hiding ABE scheme that supports several very useful classes of access policies. To the best of our knowledge, this is the first practical scheme with a proof of the attribute-hiding property. We instantiate ABE from a decentralized inner-product predicate encryption for which we provide a construction and a proof of security in the random oracle model, under the k-linear assumption. The decryption procedure of the underlying inner-product predicate scheme is very efficient, and requires only two pairing operations. Based on it, we devise attribute-hiding multi-authority ABE schemes supporting conjunctions, disjunctions, hidden-vector encryption, and threshold policies. On top of that, we add receiver privacy, by preventing individual authorities from knowing the full set of attributes possessed by the recipient when issuing keys.

Achieving security for a decentralized inner-product PE is not trivial since corrupt authorities can assist an adversary to satisfy the predicate by issuing illegitimate keys for specific vector elements. We mitigate it by proposing secure policy encodings. This contribution is of independent interest, as it can be applied to any decentralized PE scheme, and is not particular to the construction used in this paper. It is important to note that while [16] proposes several policy encodings in terms of inner-product predicates, it is a single-authority scheme that does not face the problems that arise in a decentralized setting with some corrupt authorities. Our policy encodings specifically address this challenge, and as such constitute a novel contribution.

Decentralization of a PE scheme, that is naturally single-authority, comes at a certain price, and our scheme has two drawbacks: the first is that we require each authority to publish a Diffie-Hellman public key that is visible to other authorities, and the second is that a change of attributes on the receiver’s side requires requesting new keys from all participating authorities and not only from the one that controls the changed attribute. However, those are affordable in an on-line setting where requesting a new key for an unchanged attribute may only require presenting a certificate (or key) that has been previously obtained from the authority.

Paper Structure. In Sect. 2, we briefly present required preliminaries and state our computational assumptions. In Sect. 3, we formally define decentralized inner-product predicate encryption and the corresponding security game. Section 3.3 describes an important enhancement to the key request procedure, which relieves the receiver from disclosing all its attributes to each authority. Section 4 explains how to turn the decentralized inner-product predicate encryption into an attribute-hiding ABE scheme. In Sect. 5, we address the presence of corrupt authorities, colluding with the adversary, by introducing randomizing-polynomial encodings. We formally define the security game in this new setting, and suggest several encodings that immunize the underlying predicate encryption scheme from corrupt authorities. Finally, we state related prior work and outline related open problems.

2 Background and Preliminaries

2.1 Inner-Product Predicate Encryption

In a predicate encryption scheme, access to encrypted data is controlled by a certain predicate defined over the attributes included in the ciphertext policy. In particular, in inner-product predicate encryption, ciphertexts and secret keys are associated with vectors. In order to decrypt, the secret key has to be associated with a vector that is orthogonal to the vector associated with the ciphertext. The works of Katz et al. [16] and Chen et al. [11] are examples of such cryptosystems.

2.2 Pairing Groups

Let $\mathcal {G}$ be an algorithm that on input a security parameter $\lambda$ generates three groups $\mathbb {G}_1 = \langle g_1 \rangle$, $\mathbb {G}_2 = \langle g_2 \rangle$ and $\mathbb {G}_T$ of prime order p, admitting a pairing $\mathop {\hat{e}}:\mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T$ that has the following properties:

• 1. Bilinearity: for all $a, b \in \mathbb {Z}$, $\mathop {\hat{e}}({g_1}^{\!a}, {g_2}^{\!b}) = \mathop {\hat{e}}(g_1, g_2)^{ab}$;

• 2. Non-degeneracy: $\mathop {\hat{e}}(g_1, g_2) \ne 1$.

We write $(p, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, \mathop {\hat{e}}) \leftarrow \mathcal {G}(1^\lambda )$. Groups $\mathbb {G}_1$ and $\mathbb {G}_2$ are called the source groups while $\mathbb {G}_T$ is called the target group.

2.3 Complexity Assumptions

The Symmetric External Diffie-Hellman (SXDH) assumption states that the DDH assumption holds in both source groups $\mathbb {G}_1$ and $\mathbb {G}_2$. Formally, we have:

Assumption 1

(SXDH). Given $(p, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, \mathop {\hat{e}}) \leftarrow \mathcal {G}(1^\lambda )$, there exists no polynomial-time distinguisher that can decide with a non-negligible advantage between the distributions $\mathscr {D}_0 = (g_1, g_2, {g_1}^{\!a}, {g_1}^{\!b}, {g_1}^{\!ab}) \text { and } \mathscr {D}_1 = (g_1, g_2, {g_1}^{\!a}, {g_1}^{\!b}, {g_1}^{\!r})$ where $a,b,r {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\smash {\$}}}}}\mathbb {Z}_p$, and symmetrically, exchanging the roles of $\mathbb {G}_1$ and $\mathbb {G}_2$, between the distributions $\mathscr {D}_0 = (g_1, g_2, {g_2}^{\!a}, {g_2}^{\!b}, {g_2}^{\!ab}) \text { and } \mathscr {D}_1 = (g_1, g_2, {g_2}^{\!a}, {g_2}^{\!b}, {g_2}^{\!r})$.

The SXDH assumption can be weakened using higher-rank matrices [13]. It is useful to introduce some notation. For $a_1, a_2, \cdots , a_k {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\smash {\$}}}}}{\mathbb {Z}_p}^{\!*}$, consider

Then, $\mathbf {A}^{{^{\!\intercal }}} \varvec{a}^\perp = \varvec{0}$. We let $\mathfrak {D}_{k}(\mathbb {Z}_p)$ denote the distribution induced by the previous sampling.

Assumption 2

(k-Lin in $\mathbb {G}_1$). Given $(p, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, \mathop {\hat{e}}) \leftarrow \mathcal {G}(1^\lambda )$, there exists no polynomial-time distinguisher that can decide with a non-negligible advantage between the distributions $\mathscr {D}_0 = (g_1, g_2, {g_1}^{\!\mathbf {A}}, {g_1}^{\!\mathbf {A}\varvec{s}})$ and $\mathscr {D}_1 = (g_1, g_2, {g_1}^{\!\mathbf {A}}, {g_1}^{\!\varvec{z}})$ where $(\mathbf {A}, \varvec{a}^\perp ) {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\smash {\$}}}}}\mathfrak {D}_{k}(\mathbb {Z}_p)$, $\varvec{s} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\smash {\$}}}}}{\mathbb {Z}_p}^{\!k}$, and $\varvec{z} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\smash {\$}}}}}{\mathbb {Z}_p}^{\!k+1}$.

The k-Lin assumption in $\mathbb {G}_2$ is defined similarly. By abuse of language, the k-Lin assumption will refer to the k-Lin assumption in both $\mathbb {G}_1$ and $\mathbb {G}_2$.

3 Decentralized Inner-Product Predicate Encryption

Our goal is supporting a multi-authority setting, where keys for different attributes can be requested from n independent authorities, that do not need to communicate with each other or with a central authority. In inner-product predicate encryption, keys are issued by a central authority, given a vector $\varvec{v}$, to eligible parties. We decentralize the key generation algorithm, such that key-parts are issued separately for different vector elements $v_i$, by n independent authorities. Without loss of generality, we assume that authority i issues keys for attribute number i. Those key-parts are then combined to form a secret key corresponding to the vector $\varvec{v} = (v_1,\cdots ,v_n)$.

For simplicity, we first construct a scheme that is weakly attribute-hiding in the absence of corrupt authorities. It is mostly useful as a stepping-stone, to understand how, in combination with special policy encodings, it becomes secure in the presence of corrupt authorities.

Definition 1

A decentralized inner-product predicate encryption scheme consists of a tuple of PPT algorithms, $(\mathop {\mathsf {Setup}}\nolimits , \mathop {\mathsf {AuthSetup}}\nolimits , \mathop {\mathsf {KeyGen}}\nolimits , \mathop {\mathsf {Encrypt}}\nolimits ,\mathop {\mathsf {Decrypt}}\nolimits )$, such that

• $\mathop {\mathsf {Setup}}\nolimits$ takes as input the security parameter $\lambda$ and outputs the master public parameters ${ pp }$.

• $\mathop {\mathsf {AuthSetup}}\nolimits$ takes as input the public parameters ${ pp }$ and the authority index i, and outputs the authority’s secret key $SK _i$ and public key $PK _i$.

• $\mathop {\mathsf {KeyGen}}\nolimits$ takes as input the master public parameters ${ pp }$, the authority index i, its secret key $SK _i$, the public parameters $\left\{ PK _j\right\} _{j\ne i}$ of other authorities, a user’s global identifier $\mathsf {GID}$ and the attribute vector $\varvec{v}$, and outputs a secret key part $sk _{i,\mathsf {GID},\varvec{v}}$.

• $\mathop {\mathsf {Encrypt}}\nolimits$ takes as input the master public parameters ${ pp }$, the public parameters of the authorities $\{ PK _i\}$, the ciphertext policy vector $\varvec{x}$ and a message M in the message space, and outputs a ciphertext $ct$.

  We express it as $ct {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\smash {\$}}}}}\mathop {\mathsf {Encrypt}}\nolimits _{ pp }(\varvec{x},M)$.

• $\mathop {\mathsf {Decrypt}}\nolimits$ takes as input the collection of obtained secret keys $\{ sk _{i,\mathsf {GID},\varvec{v}} \} _{i=1}^{n}$ and the ciphertext $ct$, and outputs either the message M or the special symbol $\bot$.

  We express it as $M \leftarrow \mathop {\mathsf {Decrypt}}\nolimits \bigl (\{ sk _{i,\mathsf {GID},\varvec{v}}\}, ct \bigr )$.

For correctness we require that for all ${ pp }, \varvec{x}, \varvec{v}, sk _{i,\mathsf {GID},\varvec{v}}$:

$$ \mathop {\mathsf {Decrypt}}\nolimits \bigl (\{ sk _{i,\mathsf {GID},\varvec{v}}\}_{i=1}^{n}, \mathop {\mathsf {Encrypt}}\nolimits _{ pp }(\varvec{x},M)\bigr ) = {\left\{ \begin{array}{ll} M &{} \text {if} \langle \varvec{x},\varvec{v}\rangle = 0 \\ \bot &{} \text {otherwise} \end{array}\right. } $$

with all but negligible probability.

Definition 2 captures security in the absence of corrupt authorities.

Definition 2

A decentralized inner-product predicate encryption scheme is weakly attribute-hiding, with respect to a set of attributes $\varSigma$, if for all PPT adversaries $\mathcal {A}$, the advantage of $\mathcal {A}$ in winning the following game against a challenger $\mathcal {S}$ is negligible in the security parameter:

• 1. $\mathcal {S}$ runs $\mathop {\mathsf {Setup}}\nolimits$ to generate ${ pp }$ and hands it to $\mathcal {A}$.

• 2. $\mathcal {S}$ runs $\mathop {\mathsf {AuthSetup}}\nolimits ({ pp },i)$ for each authority i, and gives $\{PK_i\}$ to $\mathcal {A}$.

• 3. $\mathcal {A}$ may request keys for vectors $\varvec{v}$, indicating possession of attributes in $\varSigma$. In response, $\mathcal {S}$ gives $\mathcal {A}$ the corresponding keys $sk _{i,\mathsf {GID},\varvec{v}}$ produced by $\mathop {\mathsf {KeyGen}}\nolimits _{ pp }(i, SK _i,\mathsf {GID},\varvec{v})$. $\mathsf {GID}$ is the global identifier of the requesting user; its role is explained in Sect. 3.1.

• 4. $\mathcal {A}$ outputs two policy vectors $\varvec{x_0},\varvec{x_1}$ and two equal-length messages $M_0,M_1$. $\mathcal {S}$ checks that none of the previously queried attribute vectors $\varvec{v}$ are orthogonal to $\varvec{x_0}$ or $\varvec{x_1}$; i.e., $\langle \varvec{x_0},\varvec{v}\rangle \ne 0 \wedge \langle \varvec{x_1},\varvec{v}\rangle \ne 0$ for all previously requested $\varvec{v}$. The challenger chooses a random bit b and gives $\mathcal {A}$ the ciphertext $ct {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\smash {\$}}}}}\mathop {\mathsf {Encrypt}}\nolimits _{ pp }(\varvec{x_b},M_b)$.

• 5. $\mathcal {A}$ may request more keys for vectors $\varvec{v}$ as they are not orthogonal to $\varvec{x_0},\varvec{x_1}$.

• 6. $\mathcal {A}$ outputs a bit $b'$ and wins if $b'=b$.

The advantage of $\mathcal {A}$ is defined as $adv(\mathcal {A})=\left| \Pr [b=b']-\frac{1}{2}\right|$.

Note 1

The way attribute possession is encoded in the vector $\varvec{v}$ is explained further, when we discuss instantiations of ABE schemes using predicate encryption.

Definition 3 captures security in the presence of corrupt authorities. Here, the adversary does not know $\varvec{x_0},\varvec{x_1}$ explicitly, as opposed to Definition 2. It provides the policies in the form of a boolean formula, or a threshold t-out-of-n over a set of admissible attributes, or a matching pattern, etc.

Definition 3

We define a game between an adversary $\mathcal {A}$ and a challenger $\mathcal {S}$:

• 1. $\mathcal {S}$ picks a random bit $b\in \{0,1\}$ and outputs the public parameters ${ pp }$.

• 2. $\mathcal {A}$ outputs the set of corrupt authorities $\mathcal {A}^\star$, and provides $\mathcal {S}$ with their public parameters.

• 3. $\mathcal {S}$ runs $\mathop {\mathsf {AuthSetup}}\nolimits$ for each one of the non-corrupt authorities, and gives the public parameters to $\mathcal {A}$.

• 4. $\mathcal {A}$ outputs two policies $\pi _0,\pi _1$ and two equal-length messages $M_0,M_1$. The policies require attributes controlled by non-corrupt authorities, and must agree on the attributes controlled by the corrupt authorities $\mathcal {A}^\star$.

• 5. $\mathcal {S}$ outputs a challenge ciphertext $ct {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\smash {\$}}}}}\mathop {\mathsf {Encrypt}}\nolimits _{ pp }(\varvec{x_b}, M_b)$, where $\varvec{x_b}$ is the encoding vector of policy $\pi _b$.

• 6. $\mathcal {A}$ generates key requests for the different authorities. $\mathcal {S}$ checks that the set of attributes, controlled by the authorities for which a non-zero key has been requested, cannot satisfy either of the two policies $\pi _0,\pi _1$.

• 7. $\mathcal {A}$ outputs a guess $b'$. If $b' = b$ it wins the game.

Definition 4

(Security). The scheme is secure (against static corruption of authorities) if any PPT adversary $\mathcal {A}$ has only negligible advantage in winning the game in Sect. 3 against a challenger $\mathcal {S}$.

3.1 Collusion Prevention and Protection Against Corrupt Authorities

A fundamental requirement from an ABE scheme is to prevent collusion between users. Let $u_{1}$ and $u_{2}$ be two users, possessing sets of key-parts $K_{1},K_{2}$. $K_{1}$ contains key-parts that enable obtaining a secret key to any $\varvec{v_1} \in V_{1}$, and $K_{2}$ contains key-parts that enable obtaining a secret key to any $\varvec{v_2} \in V_{2}$. $u_1$ and $u_2$ must not be able to mix their key-parts in a way that gives them a secret key to a new vector $\varvec{v}$ such that $\varvec{v}\notin V_1$ and $\varvec{v}\notin V_2$. For example, to enforce the policy “is a university student, and taking Introduction to Cryptography,” it is not enough to secret share the message, and encrypt it under the public-keys of the two authorities. Otherwise, two users having only one of the attributes each, can collude to decrypt the ciphertext. Therefore, all works on multi-authority ABE, including ours, address collusion prevention as one of the main challenges.

Prior works on multi-authority ABE [9, 10, 17] assign a global identifier ($\mathsf {GID}$) to each user. It is used to associate every secret key with an identity by incorporating it into the decryption keys issued by the authorities. In our setting, it is not sufficient to restrict combination of keys to the same $\mathsf {GID}$. Depending on the policy encoding, we may have to ensure that keys are issued for a well-formed attribute-vector $\varvec{v}$. For instance, in a threshold scheme, if a corrupt authority issues a key for a value $v_i > 1$, the user may be able to decrypt despite not having sufficient attributes to satisfy the policy. For our basic scheme, we require the user to supply its attribute vector $\varvec{v}$ when requesting a key, and tie the issued keys to the tuple $(\mathsf {GID},\varvec{v})$. This imposes the already mentioned requirement, on part of the receiver, to update keys when attributes change.

We use hash functions $\mathsf {H}_1(\mathsf {GID},\varvec{v}),\cdots ,\mathsf {H}_{k+1}(\mathsf {GID},\varvec{v})$, modeled as random oracles, to map $(\mathsf {GID},\varvec{v})$ to random elements. This ensures that different authorities issue keys that correspond to some common parameter. As we show in Sect. 3.3, we can replace the attribute vector with a commitment. The binding property, in composition with the random oracle, guarantees that the authorities issue keys for a common attribute vector. This modular combination enables us to extend the scheme with receiver privacy, without changing the core construction or its proof of security.

Note that it does not prevent corrupted authorities from computing a key for a different value than that appearing in $\varvec{v}$. However, in the absence of corrupted authorities, it prevents an adversary from obtaining a key to an invalid attribute vector, as well as collusion between multiple adversaries.

Minimal Trust Requirement. Given a set of l attributes (and l corresponding controlling authorities), we require one special authority (we refer to it as the $l+1$ authority) to be trusted to issue keys only for $v_{l+1} \ne 0$. Note that the authority does not get to learn the policy, or the paylod. This requirement becomes clear once we explain the way policies are encoded. It also ensures that no keys for $\varvec{v} = \varvec{0}$ are ever issued.

3.2 Construction

We build on the elegant predicate encodings framework by Chen and Wee [12], and the single-authority ZIPE scheme by Chen et al. [11]. They use dual-system groups instantiated with prime-order bilinear groups, based on the k-linear computational hardness assumption. In particular, the choice of $k=1$ corresponds to the External Diffie-Hellman (XDH) assumption, and choosing $k=2$ corresponds to the decision-linear (DLIN) assumption. Essentially, we achieve decentralization by substituting the randomness, chosen by the sender in their framework, with a publicly computable hash function, modeled as a random oracle, that can be computed by all parties. We also introduce masking terms that force the receiver to combine the key parts received from various authorities, prior to using them in any way. We use a random oracle $\mathcal {H}:\mathbb {G}_2 \times \{0,1\}^\lambda \times {\mathbb {Z}_p}^{\!l+1} \rightarrow {\mathbb {Z}_p}^{\!k+1}$, to generate masking terms that depend on a combination of an authority, the $\mathsf {GID}$, and the attribute vector $\varvec{v}$ (or a commitment to it). It is a simple way to ensure that the receiver cannot use the key parts obtained from the different authorities prior to combining them as specified in the construction. It implies a requirement for certain minimal coordination between authorities. Each one of them publishes a Diffie-Hellman public key, visible to the others. In this sense, our scheme misses the desirable property of full-decentralization, that doesn’t require any coordination between authorities whatsoever beyond referring to common public parameters published on setup.

The scheme is as follows:

• $\mathop {\mathsf {Setup}}\nolimits (\lambda )$: On input a security parameter $\lambda$, the algorithm outputs (p, $\mathbb {G}_1$, $\mathbb {G}_2$, $\mathbb {G}_T$, $\mathop {\hat{e}})$. Let $g_1,g_2$ be two generators of $\mathbb {G}_1,\mathbb {G}_2$ respectively. It picks a random matrix $\mathbf {A} \in {\mathbb {Z}_p}^{\!(k+1)\times k}$ and a random matrix $\mathbf {U} \in {\mathbb {Z}_p}^{\!(k+1)\times (k+1)}$, and publishes the public parameters

  $$ { pp } = \bigl \{ g_1, g_2, {g_1}^{\!\mathbf {A}}, {g_1}^{\!\mathbf {U}^{{^{\!\intercal }}} \mathbf {A}} \bigr \}. $$

• $\mathop {\mathsf {AuthSetup}}\nolimits ({ pp },i)$: The algorithm samples a random matrix $\mathbf {W_i} \in _{p}^{\!(k+1)\times (k+1)}$, a vector $\varvec{\alpha _i} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\smash {\$}}}}}{\mathbb {Z}_p}^{\!k+1}$ and a random $\sigma _i \in \mathbb {Z}_p$. The authority stores the secret key $SK _i=\{ \mathbf {W_i}, \varvec{\alpha _i}, \sigma _i \}$ and publishes the public key

  $$ PK _i = \bigl \{ {g_1}^{\!\mathbf {W_i}^{{^{\!\intercal }}} \mathbf {A}}, \mathop {\hat{e}}(g_1,g_2)^{\varvec{\alpha _i}^{{^{\!\intercal }}} \mathbf {A}}, y_i = {g_2}^{\!\sigma _i} \bigr \}. $$

• $\mathop {\mathsf {Encrypt}}\nolimits _{ pp }( \{ PK _i\}, \varvec{x}, m)$: Let $\varvec{x} = (x_1,\cdots ,x_n) \in {\mathbb {Z}_p}^{\!n}$. The algorithm chooses a random vector $\varvec{s} \in {\mathbb {Z}_p}^{\!k}$ and outputs the ciphertext $\varvec{C}$ consisting of the components

  $$\begin{aligned} C_0 = {g_1}^{\!\mathbf {A}\varvec{s}} \qquad \quad C_i = {g_1}^{\!(x_i \mathbf {U}^{{^{\!\intercal }}} + \mathbf {W_i}^{{^{\!\intercal }})} \mathbf {A}\varvec{s}}\\ C' = m \cdot \prod _{i=1}^n \mathop {\hat{e}}(g_1,g_2)^{{\varvec{\alpha _i}}^{{^{\!\intercal }}} \mathbf {A} \varvec{s}} = m \cdot \mathop {\hat{e}}(g_1,g_2)^{\varvec{\alpha }^{{^{\!\intercal }}} \mathbf {A} \varvec{s}} \end{aligned}$$

  where $\varvec{\alpha } = \sum _{i=1}^n \varvec{\alpha _i}$.

• $\mathop {\mathsf {KeyGen}}\nolimits _{ pp }(\{PK_i\}, SK _i,\mathsf {GID},\varvec{v})$: The authority takes the public keys of all other authorities, and computes a masking value $\varvec{\mu _i} \in \mathbb {Z}_p$

  $$ \varvec{\mu _i} = {\sum _{j=1}^{i-1} \mathcal {H}({y_j}^{\!\sigma _i},\mathsf {GID},\varvec{v}) - \sum _{j=i+1}^n \mathcal {H}({y_j}^{\!\sigma _i},\mathsf {GID},\varvec{v})}. $$

  It is easy to check that $\sum _{i=1}^n \varvec{\mu _i} = \varvec{0}$.

  We use $\mathsf {H}_1(\mathsf {GID},\varvec{v}),\cdots ,\mathsf {H}_{k+1}(\mathsf {GID},\varvec{v})$ to generate ${g_2}^{\!\varvec{h}}$ where $\varvec{h}\in {\mathbb {Z}_p}^{\!k+1}$. Note that the exponent $\varvec{h}$ is unknown and is defined implicitly by the hash functions. We denote

  $$ \mathsf {H}(\mathsf {GID},\varvec{v}) = \bigl (\mathsf {H}_1(\mathsf {GID},\varvec{v}),\cdots ,\mathsf {H}_{k+1}(\mathsf {GID},\varvec{v})\bigr )^{{^{\!\intercal }}}. $$

  The algorithm outputs the key $sk _{i,\mathsf {GID},\varvec{v}}$ which consists of

  $$ K_i = {g_2}^{\!\varvec{\alpha _i} - v_i \mathbf {W_i} \varvec{h} + \varvec{\mu _i}}. $$

• $\mathop {\mathsf {Decrypt}}\nolimits _{ pp }(\{ sk _{i,\mathsf {GID},\varvec{v}}\}, \varvec{C}, \varvec{v})$: Compute

  $$ \mathop {\hat{e}}\bigl (C_0,{\textstyle \prod _{i=1}^n K_i}\bigr ) \cdot \mathop {\hat{e}}\bigl ({\textstyle \prod _{i=1}^n {C_i}^{\!v_i}}, \mathsf {H}(\mathsf {GID},\varvec{v})\bigr ) = \mathop {\hat{e}}(g_1,g_2)^{\varvec{\alpha }^{{^{\!\intercal }}} \mathbf {A}\varvec{s}} $$

  and recover the message by computing

  $$ C' / \mathop {\hat{e}}(g_1,g_2)^{\varvec{\alpha }{{^{\!\intercal }}} \mathbf {A}\varvec{s}} = m. $$

Correctness. Let $\varvec{C} = \bigl (C_0, \{C_i\}_{i=1}^n, C'\bigr )$ and $\{ K_i := sk _{i,\mathsf {GID},\varvec{v}}\} _{i=1}^n$ be as described above. Then

If $\langle \varvec{x},\varvec{v}\rangle = 0$, we obtain $\mathop {\hat{e}}(g_1,g_2)^{\varvec{\alpha }^{{^{\!\intercal }}} \mathbf {A}\varvec{s}}$ and can recover the message.

Note 2

Looking at the key format it is easy to see why this construction, in general, requires the masking terms $\varvec{\mu _i}$, and why their generation requires taking $\varvec{v}$ as input. Without it, an adversary can ask for keys corresponding to $v_i = 0$ for $\forall {i}=1..n$, obtaining ${g_2}^{\!\varvec{\alpha }}$. That, in turn, enables to decrypt any ciphertext by pairing with $C_0$. By examining the vector $\varvec{v}$, and tying the generated key to it, the authorities ensure that the adversary doesn’t obtain a key to an all-zeros vector ($\varvec{v} = \varvec{0}$).

It also becomes clear why we need to trust the $l+1$ authority to refuse issuing keys for $v_{l+1} = 0$. If that would have been the case, an adversary colluding with a corrupt i-th authority would request keys from all other authorities presenting $\varvec{v} = \varvec{e_i}$ in the request, while in fact obtaining a key for $v_i = 0$ from the corrupt authority. A sketch of the security proof for this construction is provided in Appendix B, and a formal proof of security is provided in the full paper.

3.3 Improving Receiver Privacy

So far, the receiver has to provide its attribute vector $\varvec{v}$ to each authority it requests a key from. As a result, the authority learns not only whether the user has the attribute which it controls, but also all other attributes it possesses. This is an apparent violation of the user’s privacy in a decentralized setting.

We propose an enhancement that provides this additional privacy protection. While we want to ensure consistency of the keys issued by different authorities, and some properties of the vector they were issued for, we can avoid providing $\varvec{v}$ in the clear. We satisfy consistency and privacy using commitments. Proving possession of attributes and certain properties of $\varvec{v}$ is done by partial openings.

First, we propose to provide a vector $\varvec{c} \in {\mathbb {Z}_p}^{\!n}$, consisting of one-bit Pedersen commitments [21] to the values $\{v_i\}_{i=1}^n$, instead of $\varvec{v}$ itself, when requesting a key. This method is useful when we do not use randomizing-polynomial encodings (discussed in Sect. 5) in the ciphertext, relying on honest authorities. In this case, valid receiver attribute vectors are binary, consisting of 0 and 1 elements, and authorities need to verify this property. This property is enforced by one-bit Pedersen commitments, with each element checked by a different authority. For encodings that require the receiver to request keys for arbitrary values, generalized Pedersen commitments can be used. In both cases, the input to the hash is the sequence of commitments.

Second, we propose to reduce the communication between the receiver and the authority by compressing the commitment vector into a single value using an accumulation technique. Catalano and Fiore [8] defined and constructed a Vector Commitment scheme. It enables committing to an ordered sequence of values, and later on opening the commitment in a certain position, proving that no other value would have resulted in the previously supplied commitment. This is called position-binding. The authors propose two different constructions—one based on the Computational Diffie-Hellman assumption (CDH), and another one based on the RSA assumption. Both constructions result in a constant size commitment. A formal definition of a VC scheme and of the position-binding property is provided in Appendix A.

We use it to hide the set of receiver attributes ($\varvec{v}$) from the authorities, while guaranteeing that only key parts issued for the same $\varvec{v}$ can be combined to a valid key. Concretely, we use the vector commitment C as an input to the hash functions $\mathsf {H}_1,\cdots ,\mathsf {H}_{k+1}$. To request a key from authority i, the receiver send C, along with an opening in position i. The authority verifies the proof, and generates the key using $\mathsf {H}(\mathsf {GID},C)$. Former security guarantees are maintained by the fact that the commitment is binding, while attribute-privacy is achieved by the fact that the commitment is hiding. We note that applying this enhancement for threshold schemes is impossible in the presence of corrupt authorities, that are willing to issue keys for $v_i > 1$.

Application to Our Scheme. The modified $\mathop {\mathsf {Setup}}\nolimits$ algorithm of our ABE scheme uses $\mathsf {VC.Setup}$ in order to generate the public parameters for the vector commitments. Prior to requesting keys, the user executes $\mathsf {VC.Commit}$ to produce a commitment to $\varvec{v}$. Upon requesting a key-part from authority i, it executes $\mathsf {VC.Open}$ to produce a proof for the values at the i-th position, and supplies C and $P_i$ along with the key request. The authority runs $\mathsf {VC.Verify}$ to verify the proof against the commitment C, and uses $\mathsf {H}(\mathsf {GID},C)$ to generate the key.

Security. We argue that an adversary cannot mix-and-match keys issued for different attribute vectors. Since the commitment to the vector (using either of the proposed methods) is binding, the adversary is unable, with high-probability, to find two inputs that would yield the same commitment. Therefore, every different attribute vector results in a different input to the random oracle that is used by $\mathop {\mathsf {KeyGen}}\nolimits$ to generate the keys $K_i$.

4 Decentralized Policy-Hiding ABE

We use the constructed inner-product predicate encryption to build policy-hiding multi-authority ABE. The naïve encodings are simple, assuming the authorities are trusted to issue keys as specified below. In the following, we explain how the sender encodes the policy, and how the receiver issues key requests to the authorities.

We begin with describing how to build an attribute-based encryption from inner-product predicate encryption. We use an inner-product predicate encryption scheme as a building block, and demonstrate encodings for conjunctions, threshold policies, and hidden-vector encryption (HVE).

Exact Threshold ABE. Let $A=\{ 1,\cdots ,l\}$ be the enumeration of all supported attributes. Let S be the subset of attributes in the ciphertext policy. Let $S'$ be the subset of attributes possessed by a party attempting to decrypt the ciphertext. We require that it would be possible for a party to decrypt the ciphertext if it possesses exactly t of those attributes; i.e., if $\left| S\cap S'\right| =t$.

We instantiate a $l+1$ dimensional inner-product predicate encryption scheme. To encrypt a messages under such policy we construct a vector $\varvec{x}\in \mathbb {Z}_p^{l+1}$ as follows

• 1. Set the first l entries such that $x_{i}={\left\{ \begin{array}{ll} 1 &{} i\in S\\ 0 &{} i\not \in S \end{array}\right. }$.

• 2. Set the $l+1$ entry to $-t$; i.e., $x_{l+1}=-t\pmod p$

and output the ciphertext $CT_{\varvec{x}}=\mathsf {Encrypt}_{PK}\left( \varvec{x},M\right)$. To obtain a decryption key for the attributes in $S'$, the receiver constructs a vector $\varvec{v}\in \mathbb {Z}_{N}^{l+1}$ as follows

• 1. Set the first l entries such that $v_{i}={\left\{ \begin{array}{ll} 1 &{} i\in S'\\ 0 &{} i\not \in S' \end{array}\right. }$.

• 2. Set the $l+1$ entry to 1; i.e., $v_{l+1}=1$.

and execute $\mathsf {GenKey}\left( \varvec{v}\right)$ to obtain $SK_{\varvec{v}}$. Since $\left| S\cup S'\right| =t$ we have exactly t matching entries with the value 1 that cancel out with $-t$, yielding $\left\langle \varvec{x},\varvec{v}\right\rangle =0$, thereby satisfying the predicate and enabling decryption.

This encoding is only secure in the absence of corrupt authorities. An adversary, that does not have enough required attributes to satisfy the policy, may collude with a corrupt authority and ask it to provide it with a key for a value $v_i > 1$ such that $\langle \varvec{v},\varvec{x}\rangle = 0$. In Sect. 5 we suggest another, less straightforward encoding, that immunizes the scheme against corrupt authorities that are willing to generate keys for arbitrary values.

Threshold ABE. A general threshold algorithm requires $l-t+1$ invocations of the exact threshold decryption in the worst case, or $O\left( l\right)$ invocations if t is small compared to l. The receiver starts with the subset of its first t attributes, denoted $S'_{t}$ and constructs the corresponding vector $\varvec{v}_{t}$. It requests the corresponding secret key, and attempts decryption. If decryption fails, it knows that it did not hit the exact threshold of common attributes. It adds another attribute, forming the set $S'_{t+1}$, and constructs the corresponding vector $\varvec{v}_{t+1}$. Once again, it requests the corresponding secret key and attempts to decrypt. It continues until it hits the exact threshold, or until all possessed attributes are included.

Corrupt Authorities. Matters become more complicated in the presence of corrupt authorities colluding with the adversary. In case the encryption policy includes an attribute controlled by a corrupted authority, the adversary can use it to issue a secret key for any value $v_{i}$ and break the naïve construction.

Let us consider a threshold-policy t-out-of-n, and let the sender include attribute i in the ciphertext policy; i.e., $x_{i}=1$. If the adversary has some prior knowledge that this attribute is included in the ciphertext policy, it can request a key component corresponding to $v_{i}=t$. Then it combines it with key components corresponding to $v_{j}=0$ for all $j\ne i$ and the key component corresponding to the threshold entry $v_{l+1}=1$. In the inner product, $\sum _{i=1}^l x_{i}v_{i}=t$ and $x_{l+1}v_{l+1}=-t$ cancel out, resulting in $\left\langle \varvec{x},\varvec{v}\right\rangle =0$ and thus successful decryption despite not possessing enough attributes. The attack stems from the ability to request key components for arbitrary inputs.

The $l+1$ authority has to be honest since it controls the threshold setting. If this authority is corrupt, it can issue a secret key component corresponding to a lower (or a zero) threshold - a condition that is much easier (or trivial) for the adversary to satisfy.

In Sect. 5, we propose a threshold encoding that is secure in the presence of corrupt authorities. However, this scheme, while more restrictive, requires linear decoding time, and in certain cases may be preferable to the scheme in Sect. 5.

Conjunctions. Conjunctions are an important class of policies that state that the receiver must possess a certain set of attributes in order to decrypt the message. They are one of the most useful policies in real-world scenarios, since access policies would often specify a combination of several properties that the receiver must have. Suppose we have a total set of attributes $\varSigma$, indexed from 1 to l, and we require possession of a subset S. We encode it as a vector $\varvec{x}\in {\mathbb {Z}_p}^{\!l+1}$ as follows:

• 1. Set the first l entries such that $x_i = {\left\{ \begin{array}{ll} r_i {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\smash {\$}}}}}\mathbb {Z}_p &{} i \in S \\ 0 &{} i \not \in S \\ \end{array}\right. }$.

• 2. Set the $l+1$ entry to $-\sum _{i=1}^l r_i \pmod {p}$.

Given the receiver’s set of attributes R, the vector $\varvec{v}$ is set as follows:

• 1. Set the first l entries such that $v_i = {\left\{ \begin{array}{ll} 1 &{} i \in R \\ 0 &{} i \not \in R \\ \end{array}\right. }$.

• 2. Set the $l+1$ entry to 1.

We set the elements corresponding to attributes in S to random values, and the last element to minus their sum. Thus, an inner-product with a vector that has 1-s in all indices corresponding to the required attributes, yields 0, resolving the policy, as illustrated below:

$$ \begin{array}{|c|c|c|c|c|c|c|} \hline v_1 &{} v_2 &{} v_3 &{} \dots &{} v_l &{} v_{l+1} \\ \hline 1 &{} 1 &{} 0 &{} \dots &{} 0 &{} 1 \\ \hline \end{array} \quad \cdot \quad \begin{array}{|c|c|c|c|c|c|} \hline x_1 &{} x_2 &{} x_3 &{} \dots &{} x_l &{} x_{l+1} \\ \hline r_1 &{} r_2 &{} 0 &{} \dots &{} 0 &{} -(r_1 + r_2) \\ \hline \end{array} \quad = \quad 0 $$

Note that in this case the encoding itself immunizes the scheme against corrupted authorities. Normally, an honest authority should only issue keys for values $v_i = 0$ or $v_i = 1$, indicating absence or possession of attribute i. However, a corrupt authority can provide an adversary with a key issued for an adversarially chosen value $v_i$, in an attempt to satisfy the policy without actually having all necessary attributes. By encoding the required attributes using randomly sampled $r_i$-s over a large field, we provide information theoretic security against an attempt to craft a key by adversarially picking a value $v_i$ that would result in a zero inner-product. Security of this encoding is captured by Definition 3. It readily follows from the probability that the adversary correctly guesses which value it should craft to cancel out the last entry, which is negligible ($\frac{1}{p}$).

In Appendix C, we provide another example of a secure encoding for Hidden-Vector Encryption [7].

5 Randomizing-Polynomial Encodings

We propose encoding policies using polynomials with random coefficients as a way to protect the scheme against corrupt authorities that extend the adversary’s degrees of freedom in obtaining keys. Specifically, a corrupt authority i enables the adversary to obtain a key-part $K_i$ corresponding to an arbitrary value $v_i$, instead of being limited to 0 or 1.

By weak attribute-hiding, the adversary cannot infer the vector $\varvec{x}$ used to encode the access policy. The sender generates a randomized multivariate polynomial P expressing the policy, and sets $x_i$ to its coefficients, and $x_{l+1} = \pm P(0,\dots ,0)$, depending on the policy type.

The receiver does not know the polynomial, and in order to obtain 0 it has to evaluate P at $(0,\dots ,0)$. It requests keys from the authorities for either 0 (when it doesn’t have the corresponding attribute), or some non-zero value depending on the type of encoded policy (in case it has the attribute). The $l+1$ authority is special in that it only issues a key for $v_{l+1} = 1$. Attempting reconstruction using any other coefficients would result in a non-zero inner-product with high probability. In the following, we specify concrete encodings and receiver procedures for several useful access policies.

5.1 Examples of Encodings for Different Policies

Threshold Policy. Let S be the set of attributes that are considered admissible by the sender (out of the total l attributes), and $n = |S|$. To implement a threshold policy t-out-of-n ($n \le l$), the sender samples t random coefficients $a_i{\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\smash {\$}}}}}\mathbb {Z}_p$ that define a monic polynomial P(x) of degree t:

$$P(x) = x^t + a_{t-1}x^{t-1} + \dots + a_1 x + a_0 \pmod {p} $$

The sender generates n shares of P at publicly known points $\{z_i : i\in S\}$ and sets

$$x_i = {\left\{ \begin{array}{ll} P(z_i) &{} i\in S \\ 0 &{} i \not \in S \end{array}\right. } : \forall i=1..l \quad \quad \text {and} \quad \quad x_{l+1} = -P(0) = - a_0$$

For example, a ciphertext policy vector can be

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline x_1 &{} x_2 &{} x_3 &{} \dots &{} x_l &{} x_{l+1} \\ \hline P(z_1) &{} P(z_2) &{} 0 &{} \dots &{} P(z_l) &{} -P(0) \\ \hline \end{array} $$

The receiver computes Lagrange polynomials $\lambda _i$ at 0, using $\{z_i\}$ corresponding to a subset of t attributes in its possession, and requests the corresponding keys from the attribute authorities:

$$ v_i = {\left\{ \begin{array}{ll} \lambda _i &{} i\in S \\ 0 &{} i \not \in S \end{array}\right. } : \forall i=1..l \quad \quad \text {and} \quad \quad v_{l+1} = 1. $$

The decryption procedure effectively performs Lagrange interpolation in the exponent, over the shares encoded in the ciphertext. If decryption fails, we form another subset of t attributes, recompute the Lagrange polynomials and request the corresponding keys, and retry decrypting. The receiver repeats this until it succeeds, or until it used all attributes in its possession. A receiver that is not able to decrypt does not learn the set of admissible attributes S. A drawback of this method, is that it requires attempting $O {l \atopwithdelims ()t} \le l^t$ attribute subsets. It is polynomial in the overall number of attributes, and exponential in the threshold parameter. Hence, it is practical for small thresholds.

CNF and DNF Formulas. Boolean CNF and DNF formulas can be represented by multivariate polynomials. We illustrate it with a simple example using three attributes $A_1, A_2$ and $A_3$. Any policy over this attribute set can be expressed using a polynomial in three variables x, y, z. In the general CNF case, the polynomial can have the terms xyz, xy, xz, yz, x, y, z and a free coefficient. Some terms may have a zero coefficient. For example, consider the CNF formula $(A_1 \vee A_2) \wedge A_3$, which can be expressed as

$$ P(x,y,z) = r_1(x - 1)(y - 1) + r_2(z - 1) = r_1 xy - r_1 x - r_1 y + r_2 z + (r_1 - r_2) $$

The corresponding ciphertext policy vector is given by

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline x_1 &{} x_2 &{} x_3 &{} x_4 &{} x_5 &{} x_6 &{} x_7 &{} x_ 8 \\ \hline x &{} y &{} z &{} xyz &{} xy &{} xz &{} yz &{} P(0,\dots ,0) \\ \hline -r_1 &{} -r_1 &{} r_2 &{} 0 &{} r_1 &{} 0 &{} 0 &{} r_1 - r_2 \\ \hline \end{array} $$

Regular authorities, controlling actual attributes, are responsible for issuing the keys corresponding to the terms x, y and z. In addition, special authorities are responsible for issuing keys corresponding to the cross-terms xyz, xy, xz, yz and the free coefficient. The authority corresponding to the free coefficient only issues keys for $v_{l+1} = 1$. The trusted authorities, given $\varvec{v}$, enforce that the values requested for the cross-terms are consistent with those requested for x, y and z.

The policy above can be written in its DNF form, namely $(A_1 \wedge A_3) \vee (A_2 \wedge A_3)$, which can be expressed as

$$ P(x,y,z) = [r_1(x-1) + r_3(z-1)] \cdot [r_2(y-1) + r_3(z-1)] $$

and encoded in a similar manner to the CNF representation.

Note that the encodings for CNF and DNF formulae can be seen as a randomized version of the encodings in [16]. Also, note that the authorities responsible for the cross-terms learn sensitive information about the attributes possessed by the receiver. To verify the values requested for the the cross-term, these authorities need to see the relevant inputs. It is possible to improve receiver privacy using commitments to the input values, and a zero-knowledge proof of the requested value being equal to the output of the corresponding boolean circuit. However, the cross-term value itself reveals considerable information and narrows down the solution space for possibile inputs.

5.2 Security of Randomizing-Polynomial Encodings

Essentially, security of randomizing-polynomial encodings relies on the negligible probability ($\frac{1}{p}$) that the adversary crafts an attribute vector $\varvec{v}'$ that is different from a valid attribute-vector satisfying the policy. With overwhelming probability, this reduces to the security of the underlying basic scheme. The formal proof of security is the same as for conjunctions and HVE, and is given in the full paper.

6 Related Work

ABE in a multi-authority setting was initially studied by Chase [9], who proposed to to prevent collusion by incorporating a global user identifier into the key-generation procedure. Further improvements were proposed by Müller et al. [18] and Chase and Chow [10]. A fully decentralized scheme was proposed by Lewko and Waters [17]. Those constructions do not hide the encryption policy.

Agrawal et al. constructed an inner-product PE [2] and a Fuzzy-IBE [1] based on the learning-with-errors assumption (LWE). Lattice-based constructions often naturally hide the encryption policy, and it would be interesting to construct a decentralized scheme, based on LWE. Katz et al. introduce a zero-inner-product PE scheme that is fully-hiding [16], meaning the policy remains hidden even for a receiver who can decrypt the ciphertext.

The notion of vector commitments is related to cryptographic accumulators, first introduced by Benaloh and de Mare [4]. Accumulators are compact representations of a set of values, enabling to verify that a given element was used to compute the representation. As an alternative to the VC scheme we used, vector commitments can also be constructed using commitments to polynomials [15], by setting the polynomial coefficients to the vector elements.

Wichs and Zirdelis [27] and Goyal et al. [14], independently introduced Lockable Obfuscation for Compute-and-Compare programs, based on LWE. A corollary of lockable obfuscation is a transformation of any ABE scheme into one that is weakly attribute-hiding. However, it requires obfuscating a circuit corresponding to the decryption procedure of the underlying ABE scheme. This is highly impractical for the currently known multi-authority ABE schemes, and is not nearly as efficient as our direct construction. However, it is worth mentioning that those constructions theoretically solve the problem of decentralized policy-hiding ABE in a setting where the authorities don’t need to know each other at all, and only refer to common public parameters.

Okamoto and Takashima constructed a decentralized ABE scheme, where the authorities do not need to be aware of one-another [20]. Their work claims payload-hiding, but not policy-hiding, and it is left to be studied whether their decentralized scheme can be proven weakly-hiding for the case of inner-product policies. In addition, our scheme enjoys a ciphertext that is at least two times shorter in the number of group elements, and a decryption algorithm that involves only two pairings instead of a number proportional to the vector size. Our scheme, however, requires the authorities to publish public keys that are visible to the other authorities, whereas the scheme in [20] does not require any coordination between authorities except for referring to the same public parameters.

7 Conclusion

We address the problem of decentralized attribute-hiding attribute-based encryption. Starting off the work of Chen et al. [11], we constructed a decentralized inner-product predicate encryption scheme. We use it to instantiate a decentralized ABE scheme that hides the ciphertext policy, and show that, in the presence of corrupted authorities, it is not enough to prove security of the underlying PE scheme, but also to properly encode policies. We provide encodings for multiple useful policies. Finally, we propose an extra measure to protect receiver privacy, by using commitments to the attribute vector.

Appendices

A Vector Commitments

A vector commitment scheme consists of the following algorithms:

• $\mathsf {VC.Setup}(1^\lambda , n)$: On input security parameter $\lambda$ and the vector size n, output the public parameters $\mathtt {pp}$ which implicitly define the message space $\mathcal {M}$.

• $\mathsf {VC.Commit}_{\mathtt {pp}}(\varvec{v})$: On input the public parameters and a sequence of values $\varvec{v} = (v_1,\dots ,v_n)$, where $v_1,\dots ,v_n\in \mathcal {M}$, output a commitment string C and auxiliary information $\mathtt {aux}$. The auxiliary information is simply a vector of the underlying hiding per-element commitments.

• $\mathsf {VC.Open}_{\mathtt {pp}}(v, i, \mathtt {aux})$: Run by the committer (that requests the keys in our setting) to produce a proof $P_i$ that v is the i-th committed value.

• $\mathsf {VC.Verify}_{\mathtt {pp}}(C, v, i, P_i)$: Outputs true only if $P_i$ is a valid proof that C was created to a sequence of values $v_1,\dots ,v_n$ s.t. $v_i = v$.

Definition 5

(Position-Binding). A vector commitment scheme $\mathsf {VC}$ is position-binding if $\forall i=1,\dots ,n$ and for every efficient adversary $\mathcal {A}$, $\mathcal {A}$ has negligible probability of producing a tuple $(C, v, v', i, P, P')$ where $v \ne v'$ s.t.

$$ \mathsf {VC.Verify}_{\mathtt {pp}}(C,v,i,P) \wedge \mathsf {VC.Verify}_{\mathtt {pp}}(C, v', i, P'). $$

While position-binding ensures that only key-parts issued for the same vector $\varvec{v}$ can be combined to obtain a functional decryption key, we require the vector-commitment scheme to be hiding. Note that the vector commitment scheme is hiding only when composed with a standard commitment scheme to generate a hiding commitment for each element, that are in turn input to the vector commitment scheme. As suggested in [8], we combine the generic VC scheme with a hiding commitment scheme. Depending on whether valid attribute vectors contain only 0 and 1 or arbitrary values, we can use Pedersen’s one-bit commitment scheme [21] or generalized Pedersen commitments.

B Proof Sketch for the Scheme in Sect. 3

We define a sequence of games, starting with the actual scheme and ending up with a challenge ciphertext that encodes a random message using a random predicate vector. We argue that the games are indistinguishable to the adversary, concluding that the scheme is attribute-hiding. The transition between the hybrids is based on switching to “semi-functional” keys, and a “semi-functional” challenge ciphertext that cannot be decrypted using those keys, and looks uniformly random to the adversary.

A semi-functional ciphertext is one where instead of $A\varvec{s}$ in the exponent, we have a random vector $\varvec{z}\in {\mathbb {Z}_p}^{\!k+1}$. A semi-functional key is one where $\varvec{\alpha }$ is replaced by $\varvec{\alpha } + \varvec{a}^\perp \hat{t}$ ($\hat{t}\in \mathbb {Z}_p$ and $\varvec{h} = \mathbf {B}\varvec{r}$, where $\varvec{r}\in {\mathbb {Z}_p}^{\!k}$). It is easy to check that a semi-functional key cannot decrypt a semi-functional ciphertext. That, in turn, enables to switch from a game where an actual message m is encrypted under an actual policy vector $\varvec{x}$, to one where a random message $m'$ is encrypted under a random policy vector $\varvec{x}^\star$. This sequence is similar to the one in the proof of the weak attribute-hiding scheme in [11], with certain additions, modifications and reordering of games.

For simplicity, we use the fact that the terms ${g_2}^{\varvec{\mu _i}}$ are random in $(\mathbb {G}_2)^n$, in the adversarial view, as long as there are at least 2 honest authorities, unless canceled by summation in the exponent. In fact, the key combining is similar to the technique for privacy-preserving aggregation, as proposed by Shi et al. [26]. We can therefore refer to their security proof to justify this step. Barthe et al. [3] also used a similar technique in their privacy-preserving aggregation protocol. A tighter security reduction, linear in the number of adversarial queries, can be achieved using Smooth Projective Hash Functions (SPHF), as in [5].

As a result, $K_i$ are only useful as a product $K = \prod _{i=1}^n K_i$. Therefore, we prove the security of a scheme where the challenger computes K directly and hands it to the adversary, since it can always split it to n random shares in $\mathbb {G}_2$. It is easy to show that if there is an efficient adversary $\mathcal {A}$ that wins the game in Definition 2 against $\mathcal {S}'$, $\mathcal {S}'$ can use it to win the modified game against $\mathcal {S}$. When $\mathcal {A}$ requests a key for $(\mathsf {GID}, i, \varvec{v})$, $\mathcal {S}'$ asks $\mathcal {S}$ for a key for the whole vector $\varvec{v}$, splits it to random multiplicative shares, and serves the correct share to $\mathcal {A}$. It can later use the other shares for subsequent requests corresponding to the same $\mathsf {GID}$ and $\varvec{v}$. It is therefore enough to prove security of this modified game.

C Hidden-Vector Encryption

Hidden-Vector Encryption (HVE) was first introduced by Boneh and Waters [7]. Given a set of attributes $\varSigma$, let $\varSigma _*= S \cup \{*\}$, and the HVE predicate is

$$ \mathtt {P}_{a_1,\cdots ,a_l}^{hve} (x_1,\cdots ,x_l) = {\left\{ \begin{array}{ll} 1 &{} \forall i : a_i = x_i \vee a_i = *\\ 0 &{} \text {otherwise}. \end{array}\right. } $$

Simply put, this is a pattern matching on an input, where $a_i = *$ denotes a wild-card (“don’t care”), indicating that at position i, the input vector is allowed to have an arbitrary value. For l attributes, we need to use vectors of size $l+1$. The ciphertext policy vector is constructed by sampling l random values $r_i{\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\smash {\$}}}}}\mathbb {Z}_p$, and setting

$$ x_i = {\left\{ \begin{array}{ll} r_i &{} X_i \ne *\\ 0 &{} X_i = *\end{array}\right. } : \forall i=1..l \qquad \text {and}\qquad x_{l+1} = -\sum _{i=1}^l r_i X_i \pmod {p}. $$

The receiver attribute vector is given by

$$ v_i = {\left\{ \begin{array}{ll} a_i &{} i \in S\\ 0 &{} i \not \in S \end{array}\right. } :\forall i=1..l $$

where S is the set of attributes possessed by the receiver, and $v_{l+1} = 1$.

As in the encoding for conjunctions, this encoding is secure even in the presence of corrupt authorities. The proof of security is similar to the one for conjunctions.