Ciphertext-Policy Attribute-Based Broadcast Encryption with Small Keys

Abstract

Broadcasting is a very efficient way to securely transmit information to a large set of geographically scattered receivers, and in practice, it is often the case that these receivers can be grouped in sets sharing common characteristics (or attributes). We describe in this paper an efficient ciphertext-policy attribute-based broadcast encryption scheme (CP-ABBE) supporting negative attributes and able to handle access policies in conjunctive normal form (CNF). Essentially, our scheme is a combination of the Boneh-Gentry-Waters broadcast encryption and of the Lewko-Sahai-Waters revocation schemes; the former is used to express attribute-based access policies while the latter is dedicated to the revocation of individual receivers. Our scheme is the first one that involves a public key and private keys having a size that is independent of the number of receivers registered in the system. Its selective security is proven with respect to the Generalized Diffie-Hellman Exponent (GDHE) problem on bilinear groups.

This work was supported by the EUREKA-Celtic+ H2B2VS project and by the University of Applied Sciences and Arts Western Switzerland (HES-SO). It was performed while the first author was working at HES-SO/HEIG-VD.

1 Introduction

Broadcast channels allow transmitting information to a large set of geographically scattered receivers in a very efficient way. When this information is of high value, such as a high-definition Pay-TV stream or when delivered by a military geolocation system, for instance, one needs technical ways to enforce the signal reception by authorized receivers only. More than twenty years ago, the problem of securing a broadcast channel has began to attract cryptographers: the first works were the ones of Berkovits [2] and of Fiat and Naor [15], who coined the term “broadcast encryption”. The underlying idea is that the broadcasting center sends an encrypted message to a set of non-revoked receivers, which is a subset of all receivers. Obviously, revoked receivers (or other entities) spying the broadcast channel must not be able to decrypt a ciphertext, even if they collude together by sharing their private key material.

Precisely, if we denote by $\mathcal {U}$, with $n = |\mathcal {U}|$, the set of users (or receivers) and by $\mathcal {R}$, with $\ell = |\mathcal {R}|$, the set of revoked receivers, respectively, a broadcast encryption scheme is often meant to allow the secure transmission of information to an arbitrary set of receivers, i.e., when $n-\ell \ll n$, while revocation systems are designed to exclude a small set of rogue receivers, i.e. when $\ell \ll n$.

A key characteristic of broadcast encryption and revocation schemes is the fact that no synchronism is assumed between the broadcasting center and the receivers, besides the initial key setup procedure: one speaks from stateless receivers. It means that, once each receiver is provisioned with its decryption key material, all the information required to decrypt a ciphertext must be contained in that ciphertext. Many stateless broadcast encryption schemes have been proposed in the past, being in the secret-key [18, 20, 34]) or in the public-key settings [6–8, 12, 13, 17, 27, 37], while a large body of literature tackling the same problem, but for stateful receivers, this time, is available; we refer the reader to [9] and the references therein.

Attribute-Based Encryption. In practice, it is often the case that the receivers in a system can be grouped by common characteristics (or attributes). If we stick to a scenario around Pay-TV, receivers could be categorized by geographical location (“receivers located in California”, “receivers located in a rural zone”), by technical capabilities (“receivers supporting HD content”, “receivers supporting 4 K content”, “receivers having an OS with patch level 3.14.159”), by subscription type (“receivers having access to the XYZ sport channels package”, “receivers having access to the FGH adult channels package”), etc. Ideally, a broadcaster might then be willing to grant access to receivers according to a complicated access equation, such as to all “receivers having access to XYZ sport channels package, having an OS with patch level 3.14.159, but not located in California”.

The idea of attribute-based encryption (ABE) has been proposed by Sahai and Waters in [41], as a generalization of identity-based encryption [5, 42]; it was then formalized by Goyal and his co-authors in [19], who proposed the concepts of ciphertext-policy (CP-ABE) and key-policy (KP-ABE) encryption schemes. In the CP-ABE and KP-ABE models, the access policies are embedded in the ciphertext and in the private key, respectively. Since then, numerous variants of CP- and KP-ABE schemes have been published; see for instance [3, 10, 16, 21, 22, 26, 28, 29, 35, 38, 40, 43].

Attribute-Based Broadcast Encryption. Transforming an ABE encryption scheme for using it in a broadcast scenario is a natural question, as in practice, broadcasters are most of the time addressing sets of receivers sharing the same characteristics, instead of individual ones. An exception where a receiver might be addressed individually is when a key update is necessary, for example. This operation is rather costly in terms of bandwidth, as synchronism comes into play. It means that the individual key update messages have to be broadcast sufficiently many times on a sufficiently long period to guarantee their reception with high probability. This explains why addressing individual receivers is not possible in practice to enforce access equations in a broadcast setting and why efficient stateless broadcast encryption schemes are so useful.

The key difference between an attributed-based broadcast encryption (ABBE) scheme and an ABE one is the additional possibility to revoke individual receivers in an efficient way. Given an ABE scheme, it is possible to create a revocation system by defining a dedicated unique attribute for each receiver and to specify an access policy which rejects the revoked receivers. Unfortunately, this is in general not efficient, since in an ABE scheme, the length of the keys or ciphertexts depend often in a linear way from the number of attributes. This can become unpractical when the number of receivers is large. Concretely, one could use an ABE supporting negative attributes, such as [35], and assign individual attributes to each receivers. A ciphertext can then be sent to the non-revoked receiver identities by conjunctively adding the AND of negations of revoked receivers attributes to the access policy. Implementing this idea with [35], this would imply an acceptable overhead of $O(\ell )$ group elements in the ciphertext, with $\ell = |\mathcal {R}|$, but the private key would involve O(n) attributes, where n is the total number of receivers. Furthermore, this scheme would not be dynamic in the sense of [12], i.e., one cannot easily add receivers in the system without sending individual messages to the receivers, which is, as mentionned above, costly in terms of bandwidth in a broadcast setting.

In a context where the number of receivers is way larger than the number of attributes, one is therefore interested in splitting the revocation system from the access structure. Motivated by this fact, a line of research has focused on designing ABE schemes allowing to efficiently revoke individual receivers. In other words, revoking a receiver is implemented conjunctively, meaning that even if that receiver possesses compatible attributes for a given access equation, but it belongs to the revoked receivers set $\mathcal {R}$, it will not be able to correctly decrypt the ciphertext.

Lubicz and Sirvent [33] have proposed a scheme allowing to express access policies in disjunctive normal form (DNF), i.e., with disjunctions (OR) of conjunctions (AND), and able to handle negative attributes (NOT). Then, Attrapadung and Imai [1] proposed another approach, namely using a separate broadcast encryption scheme on the top of an ABE scheme, and they constructed both ciphertext-policy and key-policy variants. Since then, other designs have been published as well, see e.g. [24, 32, 45].

Finally, we note that attribute-based broadcast encryption schemes have numerous applications besides the Pay-TV or the geolocation satellites scenarios mentionned above. For instance, applications involving ABBE have been proposed in the context of secure storage of personal health records [31], of securing smart grids [14], and, more generally, in any data outsourcing systems requiring privacy [23].

Our Contributions. In this paper, we describe an efficient ciphertext-policy attribute-based broadcast encryption scheme (CP-ABBE) able to handle access policies in conjunctive normal form (CNF), i.e., as conjunctions of disjunctions of attributes, and supporting negative attributes. Essentially, our scheme is a combination of the Boneh-Gentry-Waters broadcast encryption scheme [6] and of the Lewko-Sahai-Waters revocation system [27]. The former is used to express attribute-based access policies while the latter is dedicated to the revocation of individual receivers.

Denoting by $\mathcal {B}$ the set of attributes, our scheme requires a public key and private keys of size O(N), where $N = |\mathcal {B}|$ is the total number of attributes. Ciphertexts are of size $O(\bar{\nu } + \ell )$, where $\ell = |\mathcal {R}|$ is the number of revoked receivers and $\bar{\nu }$ is the number of clauses in the access policy. We note that $\bar{\nu }$, N and $\ell$ are quantities independent of the number n of receivers registered in the system. As a consequence, and to the best of our knowledge, our proposal is the first ABBE scheme whose public and private key sizes do not depend on the number of receivers in the system, while the ciphertext length keeps linear in the size of the access policy and in the number of revoked receivers. This property is especially important in scenarios involving large numbers of users, such as large-scale Pay-TV or cloud-based storage systems, for instance.

Eventually, we prove the selective security of our scheme with respect to the Generalized Diffie-Hellman Exponent (GDHE) problem on bilinear groups [4], and we derive security bounds in the generic group model.

This paper is organized as follows: in Sect. 2, we recall the formal definition of attribute-based broadcast encryption schemes, their underlying security model as well as other mathematical preliminaries. Then, we describe our new scheme Sect. 3 and we prove its security in Sect. 4. Finally, we compare its characteristics to other existing ABBE schemes and we discuss some of its practical aspects in Sect. 6.

2 Mathematical Preliminaries

Let $\mathcal U$ denote a set of receivers (or users), $\mathcal {R} \subset \mathcal {U}$ the set of revoked receivers and $\mathcal B$ a set of attributes. Furthermore, let $\lambda$ be a security parameter. A ciphertext-policy attribute-based broadcast encryption (CP-ABBE) scheme consists of the following four algorithms:

• $\mathsf {Setup}(\lambda ) \rightarrow (\mathsf {pk}, \mathsf {msk})$ is a randomized algorithm which takes a security parameter $\lambda$ as input and outputs the public key $\mathsf {pk}$ and a master key $\mathsf {msk}$.

• $\mathsf {KeyGen}(u, \omega , \mathsf {msk}, \mathsf {pk}) \rightarrow \mathsf {dk}_u$ is a randomized algorithm that takes as input a receiver $u \in \mathcal {U}$, a set of attributes $\omega \subset \mathcal {B}$, the master key $\mathsf {msk}$ and the public key $\mathsf {pk}$. It outputs a private, individual decryption key $\mathsf {dk}_{(u,\omega )}$ for the receiver u. $\mathsf {dk}_{(u,\omega )}$ will be simply denoted $\mathsf {dk}_u$ if it is clear from the context that u has set of attributes $\omega$.

• $\mathsf {Encrypt}(\mathcal R, \mathbb A, \mathsf {pk}) \rightarrow (\mathsf {hdr}, \mathsf {k})$ is a randomized algorithm that takes as input a set of revoked receivers $\mathcal {R} \subset \mathcal {U}$, a Boolean access policy $\mathbb {A}$ expressed in conjonctive normal form and the public key $\mathsf {pk}$. It outputs a header $\mathsf {hdr}$ as well as a session key $\mathsf {k}$.

• $\mathsf {Decrypt}(\mathsf {hdr}, (\mathcal R, \mathbb A), \mathsf {dk}_{(u,\omega )}, (u,\omega ), \mathsf {pk}) \rightarrow \mathsf {k}\text { or } \perp$ is an algorithm taking as input a header $\mathsf {hdr}$, a set of revoked receivers $\mathcal {R}$, an access policy $\mathbb {A}$, a decryption key $\mathsf {dk}_{(u,\omega )}$ for receiver u equipped with attributes $\omega$ as well as the public key $\mathsf {pk}$. It outputs the session key $\mathsf {k}$ if and only if $\omega$ satisfies $\mathbb {A}$ and u is not in $\mathcal R$; otherwise, it outputs $\perp$.

The selective security notion for CP-ABBE is defined by the following probabilistic game:

• Setup. The adversary chooses a distribution of attributes $\mathfrak B : \mathcal U \rightarrow \mathcal P(\mathcal B)$, declares a set of revoked receivers $\mathcal R^* \subset \mathcal U$ and an access policy $\mathbb A^*$. The challenger runs the $\mathsf {Setup}$ algorithm and gives the public key $\mathsf {pk}$ to the adversary $\mathcal A$.

• Query phase 1. The adversary is allowed to (adaptively) issue queries to the challenger for private keys $\mathsf {dk}_u$ for receivers $u \in \mathcal U$ such that either $u \in \mathcal R^*$ or $\mathfrak B(u)$ does not satisfy the policy $\mathbb A^*$, i.e., receivers not able to decrypt a ciphertext.

• Challenge. After having run the encryption algorithm $\mathsf {Encrypt}(\mathcal R^*, \mathbb A^*, \mathsf {pk})$, the challenger gets a header $\mathsf {hdr}$ and a session key $\mathsf {k}$. Next, he draws a bit b uniformly at random, sets $\mathsf {k}_b = \mathsf {k}$ and picks $\mathsf {k}_{1-b}$ uniformly at random in the space of possible session keys. He finally gives the triple $(\mathsf {hdr}, \mathsf {k}_0, \mathsf {k}_1)$ to the adversary.

• Query phase 2. The adversary is again allowed to (adaptively) issue queries for private keys $\mathsf {dk}_u$ for receivers $u \in \mathcal U$ such that either $u \in \mathcal R^*$ or $\mathfrak B(u)$ does not satisfy the policy $\mathbb A^*$.

• Guess. The adversary outputs a guess bit $b'$.

The adversary wins the game if $b = b'$ and its advantage is defined as

$$\mathrm {Adv}^{\mathrm {ind}}(\lambda , \mathcal U, \mathcal B, \mathcal A) = \left| 2\mathbb \Pr [b = b'] - 1\right| .$$

The set of receivers u for which $\mathcal A$ requested the private keys is the set of colluding receivers. Hence, selective security ensures semantic security against colluding receivers if the advantage of the adversary is negligible.

We note that in the selective security model, the attacker must output the access policy before seeing the public parameters. A stronger model, named full security, has been proposed in [30]. While selective security is not the strongest model one might hope for our scheme, we think that it is stronger than what one could expect in practice, as the list of revoked nodes and the access equations are typically defined by the broadcaster.

Now, let us recall the notion of bilinear group. Let $\mathbb G$ and $\mathbb G_T$ be two (multiplicative) cyclic groups, and g a generator of $\mathbb {G}$. A map $e : \mathbb G \times \mathbb G \rightarrow \mathbb G_T$ is a symmetric, non-degenerate pairing if it is bilinear, i.e. for any $u,v \in \mathbb G$ and $a,b \in \mathbb Z$, we have $e(u^a,v^b) = e(u,v)^{ab},$ and if it is non-degenerate, i.e. $e(g,g) \ne 1$. Endowed with such a pairing, $\mathbb G$ is called a bilinear group. For practical purposes, let us further assume that in a bilinear group $\mathbb G$, both the action of $\mathbb G$ and the pairing e are efficiently computable. Finally, we recall the Generalized Diffie-Hellman Exponent (GDHE) Problem [4].

Definition 1

(GDHE Decisional Problem). Let $\mathbb G$ and $\mathbb G_T$ be two groups of prime order p, g a generator of $\mathbb G$, and $e : \mathbb G \times \mathbb G \rightarrow \mathbb G_T$ a non-degenerate bilinear map. Let $f \in \mathbb F_{p}[X_1,\dots ,X_n]$ be a polynomial in n variables over $\mathbb F_p$, the finite field with p elements, and $P,Q \subset \mathbb F_{p}[X_1,\dots ,X_n]$ be two sets of polynomials, both containing 1. Choose $x_1,\ldots ,x_n \in \mathbb F_p$ and $U \in \mathbb G_T$ uniformly at random. Given the elements

$$g^{\pi (x_1,\ldots ,x_n)}\text { and }e(g,g)^{\rho (x_1,\ldots ,x_n)}$$

for each $\pi \in P$ and $\rho \in Q$, the Generalized Diffie-Hellman Exponent (GDHE) Decisional Problem is the problem of distinguishing $e(g,g)^{f(x_1,\ldots ,x_n)}$ from U.

Observe that in this setting, the classical Decisional Diffie-Hellman (DDH) problem reduces to an easy instance of the GDHE Decisional problem: let $P = \{1,a,b\}$, $Q = \{1\}$ and $f = ab$. Given $g^a$ and $g^b$, we can distinguish $g^{ab}$ from a uniform random element $h \in \mathbb G$ by observing that $e(g^a, g^b) = e(g^{ab},g)$. This fact justifies the following definition, as in this example, (P, Q) and f are dependent functions.

Definition 2

(Dependent Functions). A function f is said to be dependent on the sets P and Q if there exist constants $a_{\pi ,\pi '}$ with $\pi ,\pi ' \in P$ and $c_{\rho }$ with $\rho \in Q$ such that

$$f = \sum _{\pi ,\pi ' \in P}a_{\pi ,\pi '} \pi \pi ' + \sum _{\rho \in Q}c_\rho \rho .$$

With this independence notion, it is proven that the (P, Q, f)-GDHE Decisional Problem is difficult in the generic group model.

Theorem 1

(Boneh et al. [4, Theorem A.2]). Let

$$\begin{aligned} d = \max \left\{ 2\deg (\pi ), \deg (\rho ), \deg (f) \mid \pi \in P, \rho \in Q\right\} , \end{aligned}$$

and $s = \max \{|P|,|Q|\}$ If f is independent of P and Q, then for any adversary $\mathcal A$ that makes a total of at most q queries to the oracle computing the group operations in $\mathbb G$, $\mathbb G_T$ and the pairing e, we have

$$\begin{aligned} \left| 2\Pr \left[ \mathcal A \text { outputs } 0 \right] - 1\right| \le \frac{(q+2s + 2)^2\cdot d}{p}. \end{aligned}$$

3 The New Scheme

Basically, our new scheme is a secure combination of the Boneh-Gentry-Waters (BGW) broadcast encryption scheme [6] and the Lewko-Sahai-Waters (LSW) [27] revocation system. This design strategy, which is similar to the one of Junod and Karlov [24], is motivated as follows.

3.1 High-Level Description

The BGW scheme targets arbitrary sets of priviledged receivers and involves ciphertexts with a constant size, if, as customary, one omits bandwidth consumed by the description of the set of priviledged receivers to be addressed; its public and private keys have a size depending on the number of receivers; note that, with the BGW scheme, one needs the public key to decrypt. Hence, we use it to express arbitrary access equations, that typically depend on a small number of attributes when compared to the total number of receivers. On its side, the LSW revocation scheme has ciphertexts whose size depends on the number of revoked receivers; however, its encryption and decryption keys are independant of the total number of users in the system. In systems potentially involving millions of receivers, this is a decisive practical advantage.

Given an access structure in CNF form $\mathbb {A} = \beta _1 \wedge \dots \wedge \beta _N$ and a revocation set $\mathcal {R}$, our idea is to associate to each clause $\beta _i$ a fragment of the session key $\mathsf {k}_i$ which can be computed only by a receiver satisfying the corresponding clause, and a fragment $\mathsf {k}_0$ computable by non-revoked receivers. Then, the session key $\mathsf {k}$ can be derived out of the $\mathsf {k}_i$’s.

This alone would not resist to an attack from colluding receivers: if receiver u is revoked but satisfies $\mathbb {A}$, he can compute $\mathsf {k}_i$ for $i = 1,\ldots ,N$, and v is not revoked but does not satisfy $\mathbb {A}$, he can compute $\mathsf {k}_0$; together, u and v can compute $\mathsf {k}$. To prevent this, we do not allow a receiver u to compute $\mathsf {k}_i$ directly, but rather an blinded value $\mathsf {k}_i^{\varepsilon _u}$ thereof, where $\varepsilon _u$ is a secret exponent unique for each receiver u. Then, $\mathsf {k}$ can be derived from any collection $(\mathsf {k}_i^{\varepsilon _u})_{i=1}^n$. If u can compute $\mathsf {k}_i^{\varepsilon _u}$ for $i=1,\ldots ,N$ and v can compute $\mathsf {k}_0^{\varepsilon _v}$, they cannot derive $\mathsf {k}$.

3.2 Formal Definitions

Let us write $\mathcal {B}^* = \mathcal {B} \cup \lnot {\mathcal B}$ the set of all attributes $\mathcal {B}$ and their negations $\lnot {\mathcal B}$. Let $\mathfrak B : \mathcal U \rightarrow \mathcal P(\mathcal B^*)$ be a distribution of attributes, i.e., a map such that for any receiver $u \in \mathcal U$ and attribute $a \in \mathcal B$, either $a \in \mathfrak B(u)$ or $\lnot a \in \mathfrak B(u)$, but not both. Let $\mathrm {id}: \mathcal U \rightarrow \left( \mathbb {Z}/p\mathbb {Z}\right) ^*$ be a public injection, and $\imath :\mathcal B^* \rightarrow \{2, 4, 6,\ldots ,t-1\}$ be a public bijection where $t = 4N + 1$.

$\mathsf {Setup}(\lambda ) \rightarrow (\mathsf {pk}, \mathsf {msk})$ According to the security parameter $\lambda$, choose two groups $\mathbb G$ and $\mathbb G_T$ of prime order $p > 2^{\lambda }$ as well as a non-degenerate bilinear pairing $e: \mathbb G \times \mathbb G \rightarrow \mathbb G_T$. Additionnaly, choose two non-zero elements $g,h = g^{\xi } \in \mathbb G$ and seven random exponents $\alpha , \gamma , b, \beta , \delta , r$ and $r'$ in $\mathbb {Z}/p\mathbb {Z}$. Finally, let $g_i = g^{\alpha ^i}$. The public key $\mathsf {pk}$ consists of the elements of $\mathbb G$ g, $g_n^{\gamma r'}$, $g^{r}$, $g_{n+1}^{ r r'}$, $g_{n+1}^{ r r' b}$, $g_{n+1}^{r r' b^2}$, $h^{b \alpha ^{n+1} r' r}$, $g^{\delta r}$, $g_n, \left( g_{\imath (a)}^r\right) _{a\in \mathcal B^*},$ and the two elements of $\mathbb G_T$ $e(g_1,g_n)^{r r' \beta \gamma }$ and $e(g_1,g_n)^{r\beta }$. The authority keeps the exponents secret.

$\mathsf {KeyGen}(u, \mathfrak B(u), \mathsf {msk}, \mathsf {pk}) \rightarrow \mathsf {dk}_u$ Let $u \in \mathcal U$. Choose two random elements $\sigma _u, \varepsilon _u \in \mathbb {Z}/p\mathbb {Z}$. Define

$$\begin{aligned} D_{u,0} = \left( g^{\gamma }g^{b^2\sigma _u}\right) ^{\varepsilon _u}, D_{u,1} = \left( g^{b\cdot \mathrm {id}(u)}h\right) ^{\sigma _u\varepsilon _u}, D_{u,2} = g^{-\sigma _u\varepsilon _u}, D_{u,3} = g_{1}^{r(\beta + \varepsilon _u)}. \end{aligned}$$

The private key of receiver u is

$$\begin{aligned} \mathsf {dk}_u = \left( \left( D_{u,k}\right) _{k=0}^3, \left( g_{\imath (a)}^{\varepsilon _u}\right) _{a \in \mathcal B^*}, \left( g_{n+1+\imath (a)}^{\varepsilon _u}\right) _{a \in \mathcal B^*}, \left( g_{\imath (a)}^{\delta \varepsilon _u}\right) _{a \in \mathfrak {B}(u)}\right) . \end{aligned}$$

$\mathsf {Encrypt}(\mathcal R, \mathbb A, \mathsf {pk}) \rightarrow (\mathsf {hdr}, \mathsf {k})$ Given an access policy $\mathbb A = \beta _1 \wedge \ldots \wedge \beta _N$, with $\beta _i = \beta _{i,1} \vee \ldots \vee \beta _{i,M_i}$ (modeled as $\beta _{i,j} \subseteq \mathcal B \cup \lnot \mathcal B$) and a revocation set $\mathcal R \subset \mathcal U$, one chooses $s_0,\ldots ,s_N \in \mathbb {Z}/p\mathbb {Z}$ at random and one defines $s = \gamma r' s_0 + \sum _{i=1}^N s_i$ (which needs not be computed). Also, one splits $s_0 = \sum _{u \in \mathcal R} s_{u}$. Let us define

$$C = g_n^s = \left( g_n^{\gamma \cdot r'}\right) ^{s_0}g_n^{\left( \sum _{i=1}^N s_i\right) }.$$

For all $i = 1,\ldots ,N$, one defines the elements $C_{i,0} = g^{r s_i}$ and

$$C_{i,1} = \left( g^{r\delta } \prod _{a \in \beta _i}g^r_{n+1-\imath (a)}\right) ^{s_i},$$

as well as the corresponding N parts of the header $\mathsf {hdr}_i = (C_{i,0}, C_{i,1})$. One defines $C_{0} = g_{n+1}^{ r r' s_0}$, and for each $u \in \mathcal R$,

$$\begin{aligned} C_{u,1} =g_{n+1}^{r r' b s_{u}} \text { and } C_{u,2} = \left( g^{b^2 \mathrm {id}(u)}h^b\right) ^{\alpha ^{n+1} r r' s_{u}}. \end{aligned}$$

Let $\mathsf {hdr}_0 = (C_{0}, (C_{u,1})_{u\in \mathcal R}, (C_{u,2})_{u\in \mathcal R})$ and $\mathsf {hdr}= (C, \mathsf {hdr}_0, \ldots , \mathsf {hdr}_N)$. The global session key $\mathsf {k}$ is given by

$$\begin{aligned} \mathsf {k}= e(g_1,g_n)^{r \beta s} = \left( e(g_1,g_n)^{rr' \beta \gamma }\right) ^{s_0}\cdot e\left( g_1^{r},g_n^{\beta }\right) ^{\left( \sum _{i=1}^N s_i\right) } \end{aligned}$$

$\mathsf {Decrypt}(\mathsf {hdr}, (\mathcal R, \mathbb A), \mathsf {dk}_{u}, (u,\omega ), \mathsf {pk}) \rightarrow \mathsf {k}\text { or } \perp$ If $u\in \mathcal R$ or if there exists $i \in \{1,\ldots , N\}$, such that $\beta _i \cap \mathfrak B(u) = \emptyset$, return $\perp$. For $i = 1,\ldots , N$, choose one satisfying attribute $a \in \beta _i \cap \mathfrak B(u)$ and compute

$$\begin{aligned} \mathsf {k}_{i}^{\varepsilon _u} = \frac{e(g_{\imath (a)}^{\varepsilon _u},C_{i,1})}{e\left( g_{\imath (a)}^{\delta \varepsilon _u} \prod _{a'\in \beta _i \setminus \{a\}} g_{n+1-\imath (a')+\imath (a)}^{\varepsilon _u},C_{i,0}\right) }. \end{aligned}$$

Also compute $\mathsf {k}_{0}^{\varepsilon _u}$ as

$$\begin{aligned} e(D_{u,0},C_{0})e\left( D_{u,1},\prod _{u'\in \mathcal R}C_{u',1}^{1/(\mathrm {id}(u)-\mathrm {id}(u'))}\right) ^{-1} e\left( D_{u,2},\prod _{u'\in \mathcal R}C_{u',2}^{1/(\mathrm {id}(u)-\mathrm {id}(u'))}\right) ^{-1}. \end{aligned}$$

We have $\mathsf {k}_{0}^{\varepsilon _u} = e(g_1,g_n)^{r r' s_0 \varepsilon _u \gamma }$ and $\mathsf {k}_{i}^{\varepsilon _u} = e(g_1,g_n)^{r s_i \varepsilon _u}$ for $i = 1,...,N.$ Eventually, we can recover $\mathsf {k}$ as

$$\begin{aligned} \mathsf {k}= \frac{e(D_{u,3},C)}{\prod _{i = 0}^N \mathsf {k}_{i}^{\varepsilon _u}} = e(g_1,g_n)^{r \beta s}. \end{aligned}$$

One can observe that the public-key size depends only on the total number of attributes defined in the system, and that the same holds for the decryption keys. The header size linearly depends only on the number of revoked rogue receivers.

If the number of attributes does not change during the lifetime of the system, we note that our new ABBE scheme is fully dynamic in the sense of [12]. Indeed, the deployment of new receivers does not imply to change the encryption or the decryption keys of other receivers, which is a desirable property for a stateless scheme.

At first sight, the system of attributes might look a bit less flexible in the sense that all receivers decryption keys include elements depending on all positive and negative attributes defined in the system. It means that the definition of new attributes after the system start arrives with the necessity of transmitting them to all receivers in a individual way, which comes with significant bandwidth issues in a system involving millions of receivers. However, this burden keeps acceptable if one considers the fact that one can define sufficiently many attributes at the start of the system and thus easily keep the set of attributes completely static during the system lifetime.

4 Security Analysis

To prove the security of our scheme, and similarly to the approach taken in [12], we show that the CP-ABBE selective security of this scheme reduces to an instance of a (P, Q, f)-GDHE problem [4]. We then prove that (P, Q) and f are independent, which implies in particular that the corresponding problem is difficult in the generic group model. This leads to a security reduction in the standard model, and a proof of security in the generic group model. Thereafter, all the polynomials considered are from the polynomial ring

$$\mathbb F_p[\alpha , \beta , \gamma , \delta , \xi , b, r, r', s_i, s_{u}, \sigma _u, \varepsilon _u : i \in \mathbb N, u \in \mathcal U].$$

Let $\mathcal A$ be an adversary for the CP-ABBE selective security game. It declares a distribution of attributes $\mathfrak B : \mathcal U \rightarrow \mathcal P(\mathcal B^*)$, an access structure $\mathbb A$ and a set $\mathcal R$ of revoked receivers. Let $\mathcal C$ be the set of all receivers which do not satisfy the policy $\mathbb A$, and/or are revoked. Let P be the list of polynomials consisting of 1, and all the following elements corresponding to the information in $\mathsf {pk}$, $\mathsf {hdr}$, and $\mathsf {dk}_u$ for all the receivers $u \in \mathcal C$.

• 1. Contribution of $\mathsf {pk}$: the set $P_{\mathsf {pk}}$ of polynomials 1, $\alpha ^n \gamma r'$, r, $\alpha ^{n+1} r r'$, $\alpha ^{n+1} r r' b$, $\alpha ^{n+1} r r' b^2$, $\xi b \alpha ^{n+1} r r'$, $\delta r$, $\alpha ^{n}$ and for $a \in \mathcal B^*$, the element $\alpha ^{\imath (a)}r.$

• 2. Contribution of $\mathsf {dk}_u$, for any $u\in \mathcal C$: the set $P_{\mathsf {dk}_u}$ of polynomials $\varepsilon _u(\gamma + b^2 \sigma _u)$, $\sigma _u \varepsilon _u (b \cdot \mathrm {id}(u) + \xi )$, $\sigma _u \varepsilon _u$, $\alpha r (\beta + \varepsilon _u)$, for each $a \in \mathcal B^*$, $\alpha ^{\imath (a)} \varepsilon _u$, $\alpha ^{n+1+\imath (a)} \varepsilon _u$, and for each $a\in \mathfrak B(u)$, $\alpha ^{\imath (a)} \delta \varepsilon _u$;

• 3. Contribution of $\mathsf {hdr}$: the set $P_{\mathsf {hdr}}$ of polynomials $\alpha ^n s$, $\alpha ^{n+1}rr's_0$, for each $i = 1,\ldots , N$, $rs_i$, $r s_i \left( \delta + \sum _{a\in \beta _i} \alpha ^{n+1-\imath (a)}\right)$, and for each revoked receiver $u \in \mathcal {R}$, $\alpha ^{n+1} r r' b s_u$, $\alpha ^{n+1} r r' s_u (b^2\cdot \mathrm {id}(u) + \xi b)$.

The list Q is simply $(1,\alpha ^{n+1} r r' \beta \gamma , \alpha ^{n+1} r \beta )$ and $f = \alpha ^{n+1} r s \beta$.

Lemma 1

If the adversary $\mathcal A$ solves the CP-ABBE selective security game with advantage $\varepsilon$, then a simulator can be constructed to solve the (P, Q, f)-GDHE problem with advantage $\varepsilon$ in polynomial time, with one oracle call to $\mathcal A$.

Proof

The proof is available in the full version of this paper [44].

According to Lemma 1, an adversary for the CP-ABBE selective security game gives rise to an adversary for the (P, Q, f)-GDHE problem. It now needs to be justified that the (P, Q, f)-GDHE problem is difficult. The end of Sect. 2 explains that we can suppose this problem to be difficult when (P, Q) and f are independent: it is proven to be difficult in the generic group model, and assumed to remain difficult in cryptographic bilinear groups. Thus, it remains to show that (P, Q) and f are indeed independent.

Lemma 2

(P, Q) and f are independent.

Proof

The proof is available in the full version of this paper [44].

We are now able to derive a bound on the security of our new scheme in the generic group model.

Theorem 2

For any probabilistic algorithm $\mathcal A$ that totalizes at most q queries to the oracle performing group operations in $(\mathbb G, \mathbb G_T)$ and evaluations of $e(\cdot ,\cdot )$, and declaring a set of revoked receivers of size at most $\eta$, as well as an access policy with at most N clauses ($\mathbb A = \beta _1 \wedge \dots \wedge \beta _N$), then $\mathrm {Adv}^{\mathrm {ind}}(\lambda , \mathcal U, \mathcal B, \mathcal A)$ is smaller or equal to

$$\begin{aligned} \frac{(q + 4(N + N + \eta ) + 22 + |\mathcal U| (10N + 8))^2 (8N + 3)}{2^{\lambda -1}}. \end{aligned}$$

Proof

This is a direct consequence of Lemmas 1 and 2, and Theorem 1, with $|P_\mathsf {pk}| = 9 + 2N, |P_{\mathsf {dk}_u}| = 4 + 5N, |P_\mathsf {hdr}| = 2+2N + 2\ell \text { and } d = 16N + 6.$

5 Optimizing the Bandwidth and Computational Overheads

As the number of revoked receivers grows, the computation of $\mathsf {k}_0^{\varepsilon _u}$ can become expensive for the receivers. The heavy computations are the products

$$\prod _{u'\in \mathcal R}C_{u',i}^{1/(\mathrm {id}(u)-\mathrm {id}(u'))}$$

for $i = 1,2$, which require $O(\ell )$ exponentiations. This could be optimized if the $C_{u',1}$’s and $C_{u',2}$’s did not change from a message to another: those products could be computed the first time and reused, and any new revoked receiver would only require one exponentiation and multiplication for each of the receivers. To do so, the broadcaster chooses a random $s_{u'}$ for every revoked receiver $u' \in \mathcal R$, and reuses it for all the following communications, thus generating the same $C_{u',1}$’s and $C_{u',2}$’s.

This optimization requires a new proof of security. We can show that even if the adversary is given access to old ciphertexts $\mathsf {hdr}^{(1)}, \ldots , \mathsf {hdr}^{(m)}$, (in addition to the challenge $\mathsf {hdr}$) for which the sets of revoked receivers are subsets $\mathcal R^{(j)}$ of the set of revoked receivers $\mathcal R$ for $\mathsf {hdr}$, and the access policies have $N^{(j)}$ clauses denoted $\beta _i^{(j)}$, for each $j = 1,\ldots , m$, the underlying (P, Q, f)-GDHE is still difficult (i.e., (P, Q) and f are independent). We need to suppose $N^{(j)} > 0$ for each $j = 1,\ldots , m$.

This technique reduces the computational cost, but in a fully stateless situation, the broadcaster still needs to send all the $C_{u',1}$’s and $C_{u',2}$’s with each message. In a context where it is possible to maintain a synchronized state, via a two-way connection with a possibly very limited bandwidth, it is possible for the broadcaster to send with each ciphertext only the $C_{u',1}$’s and $C_{u',2}$’s for the newly revoked receivers. Then, the ciphertexts’ lengths drop from $O(N + \ell )$ to $O(N + |\Delta \mathcal R|)$ (where $\Delta \mathcal R$ is the set of newly revoked receivers, for example those revoked during the last day or the last week).

The only thing we have to change from the setting of the original security proof is to add to P the contribution of the ciphertexts $\mathsf {hdr}^{(1)},\ldots , \mathsf {hdr}^{(m)}$, where the secret exponents of $\mathsf {hdr}^{(j)}$ are denoted $s^{(j)}, s_0^{(j)}, s_i^{(j)}$ and $s_{u'}^{(j)}$ for $i = 1,\ldots , N^{(j)}$ and $u' \in \mathcal R^{(j)}$. This contribution consists, for each $j = 1,\ldots , m$, of the polynomials $\alpha ^n s^{(j)}, \alpha ^{n+1}rr's_0^{(j)}$ and for each $i = 1,\ldots , N^{(j)}$, the polynomials

$$rs_i^{(j)}, r s_i^{(j)} \left( \delta + \sum _{a\in \beta _i^{(j)}} \alpha ^{n+1-\imath (a)}\right) .$$

Only a few observations are needed to adapt the original security proof to this new setting. The first thing is to notice that we now have new terms with a factor $\alpha ^{n+1}\beta$. Those are, for any $j = 1,\ldots , M$ and $u \in \mathcal C$, $\alpha ^{n+1}r s^{(j)} (\beta + \varepsilon _u)$. But those terms cannot have a non-zero coefficient in the linear combination forming f, because for each j, $\alpha ^{n+1}r s^{(j)} (\beta + \varepsilon _u)$ is the only term containing the monomial $\alpha ^{n+1}r s_1^{(j)} (\beta + \varepsilon _u)$, thus the later could not be canceled by any other linear combination of terms (here we use our assumption that $N^{(j)} > 0$).

The second thing to notice is that the terms which can cancel the monomials $\alpha ^{n+1}r\varepsilon _u r' \gamma s_v$ for $v \in \mathcal R$ are now not only $\alpha ^{n+1}rr's_0\varepsilon _u(\gamma + b^2 \sigma _u)$, but also the terms $\alpha ^{n+1}rr's_0^{(j)}\varepsilon _u(\gamma + b^2 \sigma _u)$ for all the j’s such that $v \in \mathcal R^{(j)}$. We can then deduce that there is a linear combination of those terms such that the resulting coefficient of the monomial $\alpha ^{n+1}r\varepsilon _u r' \gamma s_v$ is non-zero, and this coefficient is the same as the one of $\alpha ^{n+1}rr's_v\varepsilon _u b^2 \sigma _u$, which therefore is also non-zero. The end of the proof, consisting in showing that this coefficient of $\alpha ^{n+1}rr's_v\varepsilon _u b^2 \sigma _u$ cannot be canceled, remains unchanged. In conclusion, one can safely reuse the secret exponents $s_u$.

6 Practical Aspects

In this section, we compare the practical properties of our scheme to the other existing ABBE schemes listed in Table 1.

Table 1. Bandwidth and key storage complexity comparison. Denoting the set of all receivers by $\mathcal U$, the set of all attributes by $\mathcal B$, the set of revoked receivers by $\mathcal R$, then $k_u$ is the number of attributes assigned to a receiver $u \in \mathcal U$, $\nu$ the length of the access structure, $\bar{\nu }$ the number of clauses in a CNF access structure, $N = |\mathcal B|$, $n = |\mathcal U|$ and $\ell = |\mathcal R|$.

Size of Keys. First, we observe that our scheme is the only one where the public and private key sizes do not depend on the total number of receivers $n = |\mathcal U|$ registered in the system. Except for the Zhou-Huang scheme, whose dependency is of logarithmic nature, this dependence in n is linear in the competing schemes, which is highly impractical for a large scale deployment potentially involving millions of receivers, such as a Pay-TV system, for instance. The length of the keys in our scheme only depends linearly on the total number of attributes $N = |\mathcal B|$ defined in the system. This allows high scalability: the broadcaster can initially decide on a large set of possible receivers $\mathcal U$ without affecting the length of the keys. Adding new receivers to the system can be done efficiently, whereas with a key size linear in n, the broadcaster should choose the smallest possible $\mathcal U$ and change all the settings and keys when there are too many new receivers. This is undesirable in practice, as changing all the keys is way too expensive, especially when they are so long. In a nutshell, from the point of view of the key lengths, the Zhou-Huang scheme and our scheme are the only really practical candidates for large-scale deployment, while the Lubicz-Sirvent scheme can also be considered as acceptable since only its public key size is large, the private keys being pretty small.

Ciphertexts Size. The overhead on the ciphertext is $O(N + \ell )$ for our scheme, which is the same as the Lubicz-Sirvent scheme. The three schemes presenting a smaller overhead of size O(N) have to compensate with private keys whose size is linear in n. The Zhou-Huang scheme can in theory reach an overhead as small as $O(\log n)$. This length relies on an optimization phase, which leads to an average length in $O(\log n)$ and a worst case length in O(n); the worst case however occurs with small probability. This optimization phase is a Sum-of-Product Expression (SOPE) minimization, which is known to be an NP-Hard problem, so we can only hope for approximations. Finally, we would like to emphasize that $\nu$ and $\bar{\nu }$ have a somewhat different cardinality in the case of access structures involving only AND and NOT gates or in the case of complete CNF formulas. In the first case, $\nu$ represents the number of atomic variables, i.e., the number of attributes or their negation, while in the case of a complete CNF formula, $\bar{\nu }$ represents the number of clauses, and it is independent of the number of atomic variables in the clauses. Hence, $\bar{\nu }$ is always smaller or equal, if not significantly smaller, than $\nu$.

Overall Comparison. As mentionned before large-scale deployments rule out the schemes with a private key of length linear in $n=|\mathcal U|$. Remain the Lubicz-Sirvent and the Zhou-Huang schemes, which we will compare to ours. Compared to the Lubicz-Sirvent scheme, our scheme allows a much shorter public key; our private keys can be slightly larger, but still bounded by O(N), which should not make a significant difference as long as the set of attributes remains reasonably small. The ciphertext overhead is the same. Our scheme allows a more flexible access control model via CNF formulas. The Lubicz-Sirvent only allows AND and NOT gates; one can also add OR gates, allowing access control by CNF formulas, via ciphertext concatenation, but the ciphertext overhead is then multiplied by the number of clauses. Note that, similarly to the Junod-Karlov scheme, our scheme allows to implement access policies in DNF form by concatenation as well. Overall, as long as $N=\mathcal B$ is of reasonable size, our scheme is more flexible and efficient than the Lubicz-Sirvent one. Compared to the Zhou-Huang scheme, the lengths of the public and private keys are similar; even though there is this additional term $\log n$ in the Zhou-Huang’s scheme, there is no difference under the reasonable assumption that $N = O(\log n)$. As for the Lubicz-Sirvent scheme, the Zhou-Huang scheme only allows AND and NOT gates, and OR gates via ciphertext concatenation and a ciphertext overhead multiplied by the number of clauses. Furthermore, as mentioned above, the ciphertext overhead depends on the SOPE minimization phase, which is a NP-hard problem.

Practical Performances. We have implemented our new scheme using the C programming language and with help of the PBC library¹ for the elliptic curve arithmetic and pairings. The curve used let us work in a group of 160-bit long order and a base field of 512-bit long order, suitable for cryptographic use (it is a Type A curve, in PBC’s classification). We ran an example with 5 attributes, on a 2.3 GHz Intel Core i7; the setup phase, including the generation of the public key takes 237 ms, generating the private key of a receiver takes 75 ms, the decryption of a message with 3 clauses, and without new revocations takes 25 ms, and each new revocation adds 4 ms to the first decryption after the revocation.

7 Conclusion

This paper describes, to the best of our knowledge, the first attribute-based broadcast encryption scheme for which the length of the encryption and decryption keys does not depend on the total number of users, but only on the number of attributes defined in the system. This property has been achieved by combining the Boneh-Gentry-Waters broadcast encryption scheme with the Lewko-Sahai-Waters revocation system in a secure way. Our scheme requires also a modest bandwidth, as the length of the header depends only of the number of revoked rogue receivers. The access equations can be defined in conjunctive normal form, i.e., as AND of clauses involving ORs of attributes, and it supports negative attributes. We have proven the security of this scheme relatively to a GDHE problem in the standard model, which additionnaly allows us to derive corresponding security bounds in the generic group model. In summary, we are convinced that our scheme is fully practical in a number of real-life scenarios, including Pay-TV or cloud-storage ones involving millions of users.