Improved Anonymous Broadcast Encryptions

Abstract

We investigate anonymous broadcast encryptions (ANOBE) in which a ciphertext hides not only the message but also the target recipients associated with it. Following Libert et al.’s generic construction [PKC, 2012], we propose two concrete ANOBE schemes with tight reduction and better space efficiency.

• The IND-CCA security and anonymity of our two ANOBE schemes can be tightly reduced to standard k-Linear assumption (and the existence of other primitives). For a broadcast system with n users, Libert et al.’s security analysis suffers from $O(n^3)$ loss while our security loss is constant.

• Our first ANOBE supports fast decryption and has a shorter ciphertext than the fast-decryption version of Libert et al.’s concrete ANOBE. Our second ANOBE is adapted from the first one. We sacrifice the fast decryption feature and achieve shorter ciphertexts than Libert et al.’s concrete ANOBE with the help of bilinear groups.

Technically, we start from an instantiation of Libert et al.’s generic ANOBE [PKC, 2012], but we work out all our proofs from scratch instead of relying on their generic security result. This intuitively allows our optimizations in the concrete setting.

J. Li—Shanghai Key Laboratory of Trustworthy Computing, School of Computer Science and Software Engineering. Supported by the National Key R&D program of China (No. 2017YFB0802000) and NSF of China (Nos. 61572198, 61632012, 61672239). Part of this work was done while the author was visiting ENS de Lyon.

J. Gong—Supported by the French ANR ALAMBIC project (ANR-16-CE39-0006).

1 Introduction

Broadcast Encryption. Broadcast encryption [Ber91, FN94] (BE) is a public-key cryptosystem designed for securely sending information to multiple users via a public channel. In a BE system, we may index each user by integers $1,\ldots ,n$ and name set $U :=\{1,\ldots ,n\}$ the universe. It would be convenient to describe BE in the framework of Functional Encryption [BSW11]. An authority publishes a set of public parameters generated by the $\mathsf {Setup}$ algorithm. Each user’s secret key is then created by the $\mathsf {KeyGen}$ algorithm from the master secret key which is the output of $\mathsf {Setup}$. By invoking the encryption algorithm $\mathsf {Enc}$, a sender can create a ciphertext for users specified by a target set $S \subseteq U$. Any user with an index $i \in S$ is able to decrypt the ciphertext using the $\mathsf {Dec}$ algorithm.

The basic security requirement is collusion-resistance which ensures that a ciphertext leaks no information about the message even when multiple users outside the target set S decide to cooperate. More formally, it is required that

$$ \{ \mathsf {ct}\leftarrow _{\textsc {r}}\mathsf {Enc}(\mathsf {mpk},S,m_0) \} \approx _c \{ \mathsf {ct}\leftarrow _{\textsc {r}}\mathsf {Enc}(\mathsf {mpk},S,m_1) \} $$

where $\mathsf {mpk}$ is the public parameters, $(S \subseteq U,m_0,m_1)$ are chosen by the adversary; and we allow the adversary to adaptively learn secret keys for all $i \notin S$.

With more powerful functional encryptions such as attribute-based encryptions [SW05, GPSW06, OT10, LOS+10, CGW15], we can securely broadcast information in a structural way which is more efficient and much easier to manage. However the classical BE still serves as the most general tool for broadcasting information in the systems where users are not well-organized, e.g., a country-wide pay-TV system.

Anonymity. Since been introduced, a series of BE schemes have been published [FN94, NNL01, YFDL04, BGW05, DPP07, GW09, Wee16], but they only ensure the confidentiality of the message while the target set S is entirely exposed to the public. In fact, the description of S will be directly transmitted through the insecure channel for decryption. However in many applications, the confidentiality of the target set is also crucial. For instance, in the pay-TV setting, everyone has access to the full list of subscribers, which is not acceptable. Therefore, it is desirable and non-trivial to build a BE system taking both the message and the target set into account in terms of confidentiality. In this paper, we call the latter feature anonymity and name such a BE as anonymous broadcast encryption [LPQ12] (ANOBE). More formally, it is required that

$$ \{ \mathsf {ct}\leftarrow _{\textsc {r}}\mathsf {Enc}(\mathsf {mpk},S_0,m_0) \} \approx _c \{ \mathsf {ct}\leftarrow _{\textsc {r}}\mathsf {Enc}(\mathsf {mpk},S_1,m_1) \} $$

where $(m_0,m_1,S_0,S_1)$ are chosen by the adversary and secret keys for all $i \notin (S_0\setminus S_1) \cup (S_1\setminus S_0)$ can be revealed. The subtlety is that any secret key for $i \in S_0 \cap S_1$ will give an adversary the power to correctly decrypt both ciphertexts above. In this case, $m_0 \ne m_1$ is disallowed in order to avoid the trivial attack.

State of the Art. Although anonymity is crucial for BE, it has not received much attentions to construct ANOBE with the proper security guarantee.

In 2006, Barth et al. [BBW06] first identified the anonymity (i.e., recipient privacy in their work) in the context of encrypted file system. They introduced the notion of ANOBE in the name of private broadcast encryption. In their work, two constructions were described. The first one is a generic construction from an IND-CCA secure PKE with key-privacy and a strongly unforgeable signature scheme. They claimed that it achieves IND-CCA security and anonymity but in the selective (or static) model which means that the adversary must commit the challenge target sets $(S_0,S_1)$ in advance. Basically, a BE ciphertext there is a set of PKE ciphertexts intended for every recipient in S bound together via a signature. One drawback of this construction is that the decryption time is proportional to |S| since each receiver has to try to decrypt each PKE ciphertext one by one. In their second construction, they introduced a method helping a receiver to find the right PKE ciphertext and reduced the decryption cost to constant. However, it unfortunately relies on the random oracle model.

At PKC 2012, Libert et al. [LPQ12] formally revisited Barth et al.’s results. They described the adaptive security for ANOBE where the adversary can choose the challenge target sets $(S_0,S_1)$ at any time (i.e., the security notation we have reviewed), and showed that it can be achieved from IND-CCA secure PKE (plus strongly secure signatures). Note that this result is quite strong in that the underlying PKE is not necessarily key-private. Moreover, the receiver can decrypt in a constant time. However, the size of ciphertext depends on n, the size of universe. They then demonstrated that Barth et al.’s first BE is actually IND-CCA secure and anonymous in an adaptive sense and provided an alternative construction from IBE [Sha84, CHK04]. This ANOBE has shorter ciphertext (of size O(|S|)) but requires the underlying PKE to be weakly robust [ABN10, Moh10] and key-private, and the decryption cost increases to O(|S|). They also formalized the method helping to reduce the decryption cost in Barth et al.’s second construction [BBW06] as anonymous hint system, which can be viewed as a variant of extractable hash proof systems [Wee10]. The classical randomness-reuse technique [Kur02, BBS03] was then formally studied to reduce the ciphertext size. Finally, a concrete ANOBE based on the Kurosawa-Desmedt PKE [KD04] was proposed. Having their generic ANOBE, they showed that the Kurosawa-Desmedt PKE can be adapted to be key-private and robust, and also support randomness-reuse technique.

Also at PKC 2012, Fazio and Perera [FP12] proposed an ANOBE scheme with sublinear-size ciphertexts but with a much weaker outsider-anonymity where users identified by $S_0 \cap S_1$ are not considered to be malicious. More formally, the adversary is forbidden to get any secret key for $i \in S_0 \cap S_1$. However Barth et al.’s early work [BBW06] has actually recognized such an inside attacker as a hazard and illustrated how serious the issue is under a chosen-ciphertext attack. In the end, we want to note that Libert et al.’s results [LPQ12] are still the best in the sense that they achieve (1) IND-CCA security, (2) fully anonymity and (3) random-oracle-freeness. To our best knowledge, there is no follow-up result with all these features simultaneously even when taking the identity-based variant into account (see recent work [HWL+16] for more details).

1.1 Contributions

In this paper, we propose two concrete ANOBE schemes. Both of them are obtained by optimizing an instantiation of Libert et al.’s generic construction [LPQ12] with Cramer-Shoup PKE [CS98, CS02]. We prove, from scratch, that they are secure in the sense of [LPQ12] from the standard k-Linear (k-Lin) assumption and the existence of several other cryptographic primitives (such as strongly unforgeable signature and collision-resistant hash function).

Although our proposals do not deviate from Libert et al.’s generic framework [LPQ12], our new start point and customized security proof allow us to gain shorter ciphertexts and tighter reduction than the concrete instantiation in [LPQ12]. (Recall that it is based on Kurosawa-Desmedt PKE [KD04] and the security result follows the generic construction directly.) A comparison between them is shown in Table 1 where we consider instantiations of our two ANOBE under DDH = 1-Lin (or SXDH = 1-Lin) assumption¹. We note that these two instantiations are the most efficient ones.

Table 1. Comparison of our two proposals and the concrete ANOBE from [LPQ12] in terms of ciphertext size and reduction tightness. Table (a) is for the schemes supporting fast decryption while we tolerate linear decryption cost in Table (b). In our comparison, the system has n users and $\ell$ is the size of target set S. We let ${\mathbb {G}}$ be a finite group where DDH holds while ${\mathbb {G}}_1$ denotes the first source group of a bilinear group where SXDH holds. The column “Reduction” shows the security loss.

Shorter Ciphertext. Our first ANOBE scheme supports fast decryption. Compared with the concrete ANOBE in [LPQ12] equipped with their DDH-based anonymous hint system², our ANOBE can save roughly 50% bandwidth. Our second ANOBE is derived from the first one. We sacrifice fast decryption and peruse shorter ciphertext. Compared with concrete ANOBE in [LPQ12], our second ANOBE works with bilinear groups and roughly saves 50% bandwidth³. We highlight that this construction almost touches the lower bound of ciphertext size in an anonymous broadcast encryption [KS12]. It is quite surprising that we start from a less efficient basic PKE scheme but finally achieves better space efficiency. We note that the Cramer-Shoup PKE [CS98, CS02] is indeed less efficient than Kurosawa-Desmedt PKE [KD04], but it permits us to use some customized method to optimize the system.

Tighter Reduction. In [LPQ12], their security reduction suffers from $O(n^3)$ loss where n is the size of the universe. This makes it infeasible for large-scale systems such as aforementioned pay-TV application. In particular, we need to use a larger group to compensate the loss, which of course increases the bandwidth and computation costs. In our work, we prove the security of two ANOBE from basic assumption and only suffer constant security loss, which is of both theoretical and practical interest. We argue that the result is non-trivial: A potential solution is to employ an IND-CCA secure PKE with tight reduction for multiple users (like [GHKW16, Hof17]) in Libert et al.’s generic construction [LPQ12]. However, the simulator still needs to guess which public keys will be associated with target set which is chosen adversarially and causes significant security loss.

1.2 Technical Overview

Our starting point is an instantiation of Libert et al.’s generic construction with Cramer-Shoup PKE [CS98, CS02]. In this overview, we first give this instantiation and describe how to derive our two ANOBE schemes from it.

Starting Point. Assume a prime-order group $(p,{\mathbb {G}},g)$. We let $[a]:=g^a \in {\mathbb {G}}$ for all $a \in \mathbb {Z}_p$ and extend it to matrix over $\mathbb {Z}_p$. Assume $S:=\{i_1,\dots , i_\ell \}$. We can instantiate Libert et al.’s construction using Cramer-Shoup PKE under k-Lin assumption as below:

where $\mathbf {A}\leftarrow _{\textsc {r}}\mathbb {Z}_p^{(k+1)\times k}$, $\mathbf {k}_i, \mathbf {x}_i, \mathbf {y}_i \leftarrow _{\textsc {r}}\mathbb {Z}_p^{k+1}$ for $i\in [n]$ and $\mathbf {r}\leftarrow _{\textsc {r}}\mathbb {Z}_p^{k}$. The public parameter $\mathsf {mpk}$ is basically n public keys of Cramer-Shoup PKE⁴ sharing $[\mathbf {A}]$ which is a common technique in the multi-user setting. The ciphertext for S contains $\ell$ ciphertexts of Cramer-Shoup PKE with randomness $[\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}]$ reused as [LPQ12]. Following Libert et al.’s suggestion, they are then bound together via a strongly unforgeable signature $\sigma$ under fresh verification key $\mathsf {pk_{ots}}$ instead of encrypting $m||\mathsf {pk_{ots}}$.

The above BE is IND-CCA secure and anonymous according to Libert et al.’s generic result. However, we can do better by showing a tighter reduction for this concrete ANOBE. The security loss of Libert et al.’s reduction (which is $O(n^3)$) is mainly caused by black-box-reduction to the underlying PKE where the simulation need to guess some information about challenge target set. We prove our security result from scratch. In particular, we employ the proof technique for IND-CCA PKE in the multi-user setting [GHKW16, Hof17] but adapt it to our broadcast encryption case. We found that we can now avoid guessing adversary’s behavior and also corresponding reduction loss.

Our First ANOBE: Shorter Ciphertext for Fast Decryption. The above instantiation has not been equipped with anonymous hint system [LPQ12], so the decryption cost should be $O(\ell )$. (Recall that, intuitively, an anonymous hint system can help the decryptor to find the right ciphertext component intended for him and avoid $O(\ell )$ factor.) However we observe that $\{[\mathbf {r}^{{\!\scriptscriptstyle {\top }}}\mathbf {A}^{{\!\scriptscriptstyle {\top }}}(\mathbf {x}_{i_j}+ \alpha \cdot \mathbf {y}_{i_j})] \}_{j\in [\ell ]}$ can serve as the hints for fast decryption. This benefits from the fact that tag $\alpha$ is shared by all users in S. In the decryption procedure, a user with secret key $\mathbf {k}_i,\mathbf {x}_i,\mathbf {y}_i$ can recover $v=[\mathbf {r}^{{\!\scriptscriptstyle {\top }}}\mathbf {A}^{{\!\scriptscriptstyle {\top }}}(\mathbf {x}_{i}+ \alpha \cdot \mathbf {y}_{i})]$ and try to find the index $j^*$ such that $v = [\mathbf {r}^{{\!\scriptscriptstyle {\top }}}\mathbf {A}^{{\!\scriptscriptstyle {\top }}}(\mathbf {x}_{i_{j^*}}+ \alpha \cdot \mathbf {y}_{i_{j^*}})]$, which indicates the right ciphertext.

This already saves the bandwidth since we need the DDH-based anonymous hint system in [LPQ12] to upgrade Libert et al.’s concrete ANOBE in order to achieve fast decryption. Even with randomness reuse technique, this will introduce $2 \cdot |S|$ additional group elements to the ciphertext. The perspective here is that $\{[\mathbf {r}^{{\!\scriptscriptstyle {\top }}}\mathbf {A}^{{\!\scriptscriptstyle {\top }}}(\mathbf {x}_{i_j}+ \alpha \cdot \mathbf {y}_{i_j})]\, \}_{j\in [\ell ]}$ act as crucial components for achieving IND-CCA security and hints for fast decryption at the same time while they are realized separately in Libert et al.’s concrete ANOBE.

Our Second ANOBE: Compressing Ciphertext Again. We now ask:

Can we reduce the ciphertext size if we can tolerate slower decryption?

Observe that we have $\ell$ group elements (i.e., $\{[\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}(\mathbf {x}_{i_j} + \alpha \cdot \mathbf {y}_{i_j})]\}_{j\in [\ell ]}$) for consistency check (which is necessary for IND-CCA security) in our first ANOBE. If we assume that each recipient can correctly guess which part is intended for him/her, we can see that only one of these $\ell$ elements will be used in the decryption procedure. Therefore a promising idea is to ask all recipients to share the consistency check process. A direct way to do so is to

$$\begin{aligned} \mathrm{replace}\quad \{[\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}( \mathbf {x}_{i_j} + \alpha \cdot \mathbf {y}_{i_j})]\}_{j\in [\ell ]}\quad \mathrm{with}\quad [\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}(\mathbf {x}+ \alpha \cdot \mathbf {y})] \end{aligned}$$

and publish $[\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {x}]$ and $[\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {y}]$ in $\mathsf {mpk}$. Unfortunately, there is a fatal issue. To do the consistency check, we should give each user $\mathbf {x}$ and $\mathbf {y}$ directly and they will be leaked to an adversary through any corrupted user. This totally breaks the IND-CCA security. We circumvent the difficulty by making the consistency check public using the technique by Kiltz and Wee [KW15]. In particular, we adapt our first ANOBE to ${\mathbb {G}}_1$ of a pairing group $(p,{\mathbb {G}}_1,{\mathbb {G}}_2,{\mathbb {G}}_T,e)$ and

$$\begin{aligned} \mathrm{replace}\quad [\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}(\mathbf {x}+ \alpha \cdot \mathbf {y})]_1 \quad \mathrm{with}\quad [\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}(\mathbf {X}+ \alpha \cdot \mathbf {Y})]_1 \end{aligned}$$

where $\mathbf {X},\mathbf {Y}\leftarrow _{\textsc {r}}\mathbb {Z}_p^{(k+1) \times (k+1)}$. In the public parameter $\mathsf {mpk}$, we publish

$$ ([\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {X}]_1,[\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {Y}]_1) \quad \text{ and }\quad ([\mathbf {B}]_2, [\mathbf {X}\mathbf {B}]_2, [\mathbf {Y}\mathbf {B}]_2) $$

where $\mathbf {B}\leftarrow _{\textsc {r}}\mathbb {Z}_p^{(k+1) \times k}$ and the right-hand side part allow anyone to publicly check the ciphertext consistency.

We have successfully compressed the ciphertext but lose the correctness of decryption since we do not have hint system now. It is easy to fix using key-binding symmetric encryption scheme $(\mathsf {E},\mathsf {D})$. That is we pick session key K from the key space of $(\mathsf {E},\mathsf {D})$ and

$$\begin{aligned} \mathrm{replace}\quad [\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {k}_{i_j}]_1 \cdot m \quad \mathrm{with}\quad [\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {k}_{i_j}]_1 \cdot K, \mathsf {E}_{K}(m). \end{aligned}$$

We note that we are not pursuing fast decryption now. We can further get rid of $\sigma$ by defining $\alpha$ as in Cramer-Shoup PKE [CS98, CS02]. We sketch our second ANOBE as follows:

where all terms in gray box are shared by all users/receivers. As our first ANOBE, the reduction loss is constant.

Compared with Libert et al.’s concrete ANOBE [LPQ12], our second ANOBE is based on weaker assumptions — we don’t require the existence of strongly one-time signature and $(\mathsf {E},\mathsf {D})$ is not necessarily authenticated encryption. Furthermore, in the ciphertext, we share as many components as possible among receivers in the target set, the remaining $\ell$ group elements seem to be inevitable by the lower bound [KS12].

Organization. Our paper is organized as follows. We review some basic notions in Sect. 2. Our two ANOBE constructions along with security analysis will be presented in Sects. 3 and  4, respectively. We finally conclude the paper in Sect. 5.

2 Preliminaries

Notations. For $n \in \mathbb {N}$, we define $[n] := \{1,2,\ldots ,n\}$. We use $a\leftarrow _{\textsc {r}}A$ to denote the process of uniformly sampling an element from set A and assigning it to variable a. For two sets $S_0,S_1$, define $S_0 \triangle S_1 := (S_0\setminus S_1) \cup (S_1\setminus S_0)$. “p.p.t.” stands for probabilistic polynomial time.

2.1 Anonymous Broadcast Encryption

Algorithms. Let $U:= [n]$ be the universe. A broadcast encryption (BE) scheme consists of four algorithms $(\mathsf {Setup},\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec})$: Algorithm $\mathsf {Setup}$ takes security parameter $1^\lambda$ and n as input and outputs a master public key $\mathsf {mpk}$ and a master secret key $\mathsf {msk}$; Algorithm $\mathsf {KeyGen}$ takes $\mathsf {mpk}$, $\mathsf {msk}$ and an index $i\in U$ as input and outputs a secret key $\mathsf {sk}_i$; Algorithm $\mathsf {Enc}$ takes $\mathsf {mpk}$, a message m and a subset $S\subseteq U$ as input and outputs a ciphertext $\mathsf {ct}_S$; Algorithm $\mathsf {Dec}$ takes $\mathsf {mpk}$, $\mathsf {ct}_S$ and $\mathsf {sk}_i$ as input and outputs m or a failure symbol $\bot$.

Correctness. For all $\lambda$, all $(\mathsf {mpk}, \mathsf {msk}) \leftarrow _{\textsc {r}}\mathsf {Setup}(1^\lambda ,n)$, all m, all $S\subseteq U$, and all $i \in S$, it is required that $\mathsf {Dec}(\mathsf {mpk},\mathsf {Enc}(\mathsf {mpk},m,S),\mathsf {KeyGen}(\mathsf {mpk}, \mathsf {msk},i)) = m.$

Chosen-Ciphertext Security and Anonymity. For any adversary $\mathcal {A}$ , define

$$ \mathsf {Adv}_{\mathcal {A}}^{\mathsf {BE}}(1^\lambda ):= \left| \Pr \left[ b=b' \left| \begin{array}{c} (\mathsf {mpk}, \mathsf {msk})\leftarrow _{\textsc {r}}\mathsf {Setup}(1^\lambda ,n),\ b \leftarrow _{\textsc {r}}\{0,1\} \\ (m_0,m_1,S_0,S_1) \leftarrow _{\textsc {r}}\mathcal {A}^{\mathsf {KeyO}(\cdot ),\mathsf {DecO}(\cdot ,\cdot )}(1^\lambda ,\mathsf {mpk})\\ \mathsf {ct}^* \leftarrow _{\textsc {r}}\mathsf {Enc}(\mathsf {mpk},m_b,S_b)\\ b' \leftarrow _{\textsc {r}}\mathcal {A}^{\mathsf {KeyO}(\cdot ),\mathsf {DecO}(\cdot ,\cdot )}(1^\lambda ,\mathsf {mpk}, \mathsf {ct}^*) \end{array}\right. \right] -\frac{1}{2}\right| $$

where oracles work as follows:

• $\mathsf {KeyO}$: on input i, key extraction oracle $\mathsf {KeyO}$ outputs $\mathsf {sk}_i\leftarrow _{\textsc {r}}\mathsf {KeyGen}( \mathsf {msk},\mathsf {mpk},i)$ and sets $Q_{ \mathsf {sk}} := Q_{ \mathsf {sk}}\cup \{i\}$ which is initialized to be $\emptyset$ at the beginning.

• $\mathsf {DecO}$: on input $( \mathsf {ct},i)$, decryption oracle $\mathsf {DecO}$ outputs $\mathsf {Dec}(\mathsf {mpk}, \mathsf {ct}, \mathsf {sk}_i)$ when $\mathsf {ct}^*$ (a.k.a. challenge ciphertext) has not been defined or $\mathsf {ct}\ne \mathsf {ct}^*$.

A broadcast encryption scheme achieves chosen-ciphertext security and anonymity (ANO-IND-CCA) if, for all p.p.t. adversary $\mathcal {A}$, $\mathsf {Adv}_{\mathcal {A}}^{\mathsf {BE}}(\lambda )$ is negligible in $\lambda$ under the restrictions that (1) $|m_0|=|m_1|$ and $|S_0|=|S_1|$; (2) $Q_{ \mathsf {sk}} \cap (S_0 \triangle S_1) = \emptyset$; (3) if $Q_{ \mathsf {sk}} \cap (S_0 \cap S_1) \ne \emptyset$, then $m_0=m_1$.

2.2 Prime-Order (Bilinear) Groups

Prime-Order Group. A group generator $\mathsf {GGen}$ is a p.p.t. algorithm which takes $1^\lambda$ as input and outputs a description $\mathcal {G}:=(p,{\mathbb {G}},g)$. Here ${\mathbb {G}}$ is a finite cyclic group of prime order p and g is a random generator of ${\mathbb {G}}$. Throughout the paper, we will use implicit representation [EHK+13]. We let $[a] := g^{a} \in {\mathbb {G}}$ for all $a \in \mathbb {Z}_p$. For a matrix $\mathbf {A}= (a_{ij}) \in \mathbb {Z}_p^{m \times n}$, we let $[\mathbf {A}] = (g^{a_{ij}})\in {\mathbb {G}}^{m \times n}$.

Prime-Order Bilinear Group. A group generator $\mathsf {PGGen}$ is a p.p.t. algorithm which takes $1^\lambda$ as input and outputs a description $\mathcal {PG}:= (p,{\mathbb {G}}_1,{\mathbb {G}}_2,{\mathbb {G}}_T,e,g_1,g_2)$ of (asymmetric) bilinear group. Here ${\mathbb {G}}_1,{\mathbb {G}}_2,{\mathbb {G}}_T$ are finite cyclic groups of prime order p and e is an admissible bilinear map. $g_1 \in {\mathbb {G}}_1$ and $g_2 \in {\mathbb {G}}_2$ are random generators of ${\mathbb {G}}_1$ and ${\mathbb {G}}_2$, and $g_T := e(g_1,g_2)$ will be a generator of group ${\mathbb {G}}_T$. The implicit representation is also be applied to prime-order bilinear groups: We let $[a]_s := g_s^{a} \in {\mathbb {G}}_s$ for all $a \in \mathbb {Z}_p$ and $s \in \{1,2,T\}$. The notation can be easily extended to matrices analogously and we let $e([\mathbf {A}]_1,[\mathbf {B}]_2) := [\mathbf {A}\mathbf {B}]_T$ for matrices $\mathbf {A}$ and $\mathbf {B}$ when the multiplication is well-defined.

Cryptographic Assumption. For any $k \in \mathbb {N}$, we call $\mathcal {D}_{k}$ a matrix distribution if it outputs full-rank matrices in $\mathbb {Z}_p^{(k+1)\times k}$ in polynomial time. We may assume that for all $\mathbf {A}\leftarrow _{\textsc {r}}\mathcal {D}_{k}$, the first k rows of $\mathbf {A}$ form an invertible matrix.

We will use the $\mathcal {D}_{k}$-Matrix Diffie-Hellman ($\mathcal {D}_{k}$-$\mathsf {MDDH}$) assumption in ${\mathbb {G}}$ described as follows. The $\mathcal {D}_{k}$-$\mathsf {MDDH}$ assumption in ${\mathbb {G}}_1$ and ${\mathbb {G}}_2$ are analogous.

Assumption 1

($\mathcal {D}_{k}$-$\mathsf {MDDH}$). We say that the $\mathcal {D}_{k}$-Matrix Diffie-Hellman assumption holds relative to $\mathsf {GGen}$, if for any p.p.t. adversary $\mathcal {A}$, the following advantage function is negligible in $\lambda$.

$$ \mathsf {Adv}_{\mathcal {A},{\mathbb {G}}}^{\mathsf {mddh}}(\lambda ):= |\Pr [\mathcal {A}(\mathcal {G},[\mathbf {A}],[\mathbf {A}\mathbf {s}])=1]-\Pr [\mathcal {A}(\mathcal {G},[\mathbf {A}],[\mathbf {u}])=1]| $$

where $\mathcal {G}\leftarrow _{\textsc {r}}\mathsf {GGen}(1^{\lambda }),\ \mathbf {A}\leftarrow _{\textsc {r}}\mathcal {D}_{k},\ \mathbf {s}\leftarrow _{\textsc {r}}\mathbb {Z}_p^k$, and $\mathbf {u}\leftarrow _{\textsc {r}}\mathbb {Z}_p^{k+1}$.

The famous k-Linear (k-Lin) assumption is an instantiation of the $\mathcal {D}_k$-MDDH assumption. The classical decisional Diffie-Hellman (DDH) assumption (a.k.a symmetric external Diffie-Hellman (SXDH) assumption in asymmetric bilinear groups) is just the k-Lin assumption with $k=1$. See [EHK+13] for more details.

For bilinear groups, we also use the $\mathcal {D}_{k}$-Matrix Kernel Diffie-Hellman ($\mathcal {D}_{k}$-$\mathsf {KerMDH}$) Assumption [MRV16], which is implied by the $\mathcal {D}_{k}$-$\mathsf {MDDH}$ assumption.

Assumption 2

($\mathcal {D}_{k}$-$\mathsf {KerMDH}$). Let $s\in \{1,2\}$. We say that the $\mathcal {D}_{k}$-Kernel Matrix Diffie-Hellman Assumption holds relative to $\mathsf {PGGen}$, if for any p.p.t. adversary $\mathcal {A}$, the following advantage function is negligible in $\lambda$.

$$ \mathsf {Adv}_{\mathcal {A},{\mathbb {G}}_s}^{\mathsf {kmdh}}(\lambda ):= \Pr [\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {a}^\perp =\mathbf {0}\wedge \mathbf {a}^\perp \ne \mathbf {0}\ |\ [\mathbf {a}^\perp ]_{3-s}\leftarrow _{\textsc {r}}\mathcal {A}(\mathcal {PG},[\mathbf {A}]_s)] $$

where $\mathcal {PG}\leftarrow _{\textsc {r}}\mathsf {PGGen}(1^{\lambda }), \mathbf {A}\leftarrow _{\textsc {r}}\mathcal {D}_{k}$.

2.3 Cryptographic Primitives

Our constructions will use the following cryptographic primitives:

• A semantically secure and key-binding symmetric encryption scheme $(\mathsf {E},\mathsf {D})$ with key space $\mathcal {K}$. Let $\mathsf {E}_K(\cdot )$ and $\mathsf {D}_K(\cdot )$ denote the encryption and decryption procedures under secret key $K \in \mathcal {K}$. By key-binding [Fis99], we mean that, for any message m and any secret key $K \in \mathcal {K}$, there exists no $K'\in \mathcal {K}$ such that $K \ne K'$ and $\textsf {D}_{K'}(\textsf {E}_K(m))\ne \perp$ (Here $\perp$ indicates a decryption failure).

• A family of collision-resistant hash function $\mathcal {H}$. It ensures that, given $\mathsf {h}\leftarrow _{\textsc {r}}\mathcal {H}$, it is hard to find $x \ne y$ such that $\mathsf {h}(x) = \mathsf {h}(y)$ (i.e., a collision).

• A strongly unforgeable one-time signature scheme $(\mathsf {Gen_{ots}},\mathsf {Sign},\mathsf {Ver})$. Let $(\mathsf {pk_{ots}},\mathsf {sk_{ots}}) \leftarrow _{\textsc {r}}\mathsf {Gen_{ots}}(1^\lambda )$ be a verification key and a signing key. It is guaranteed that, given $\mathsf {pk_{ots}}$ and a signature $\sigma \leftarrow _{\textsc {r}}\mathsf {Sign}(\mathsf {sk_{ots}},m)$ for some adversarially chosen message m, it is infeasible to output another message-signature pair $(m^*,\sigma ^*)\ne (m,\sigma )$ satisfying $\mathsf {Ver}(\mathsf {pk_{ots}},m^*,\sigma ^*)=1$.

We will use $\mathsf {Adv}_{\mathcal {A}}^{\mathsf {se}}(\lambda )$, $\mathsf {Adv}_{\mathcal {A}}^{\mathsf {hash}}(\lambda )$ and $\mathsf {Adv}_{\mathcal {A}}^{\mathsf {ots}}(\lambda )$ to denote the advantage of adversary $\mathcal {A}$ in violating the security of above primitives under security parameter $\lambda$. Formal definitions can be found in the full version of the paper.

2.4 Core Lemma

We review the core lemma in [KW15].

Lemma 1

(Core lemma, [KW15]). Let $k \in \mathbb {N}$. For any $\mathbf {A},\mathbf {B}\in \mathbb {Z}_p^{(k+1)\times k}$ and any (possibly unbounded) adversary $\mathcal {A}$, we have

$$\begin{aligned} \Pr \left[ \begin{array}{l|l} \mathbf {u}\notin \mathsf {span}(\mathbf {A})\wedge \alpha \ne \alpha ^* &{}\mathbf {X},\mathbf {Y}\leftarrow _{\textsc {r}}\mathbb {Z}_p^{(k+1)\times (k+1)}\\ \wedge ~{\varvec{\pi }}^{\top } = \mathbf {u}^{{\!\scriptscriptstyle {\top }}}(\mathbf {X}+\alpha \cdot \mathbf {Y})&{}(\mathbf {u},\alpha ,{\varvec{\pi }})\leftarrow _{\textsc {r}}\mathcal {A}^{\mathcal {O}(\cdot )}(\mathbf {A}^{{\!\scriptscriptstyle {\top }}}\mathbf {X},\mathbf {A}^{{\!\scriptscriptstyle {\top }}}\mathbf {Y},\mathbf {X}\mathbf {B},\mathbf {Y}\mathbf {B})\\ \end{array} \right] \le \frac{1}{p} \end{aligned}$$

where $\mathcal {O}(\alpha ^*)\rightarrow \mathbf {X}+\alpha ^* \cdot \mathbf {Y}$ may only be called one time.

3 Tightly Secure ANOBE with Fast Decryption

3.1 Construction

Our first broadcast encryption scheme is described as follows.

• $\mathsf {Setup}(1^\lambda ,n)$: Run $\mathcal {G}:=(p,{\mathbb {G}},g) \leftarrow _{\textsc {r}}\mathsf {GGen}(1^{\lambda })$. Sample

  $$ \mathbf {A}\leftarrow _{\textsc {r}}\mathcal {D}_k \quad \text{ and }\quad \mathbf {k}_i, \mathbf {x}_i,\mathbf {y}_i \leftarrow _{\textsc {r}}\mathbb {Z}_p^{k+1}\ \text { for }\ i \in [n]. $$

  Select a strongly unforgeable one-time signature scheme $(\mathsf {Gen_{ots}, Sig, Ver})$ and a hash function $\mathsf {h}:\{0,1\}^*\rightarrow \mathbb {Z}_p$ from $\mathcal {H}$. The master public key is

  $$ \mathsf {mpk}:=(\mathcal {G},\mathsf {h},(\mathsf {Gen_{ots}, Sig, Ver}),[\mathbf {A}],\{[\mathbf {A}^{{\!\scriptscriptstyle {\top }}}\mathbf {k}_i],[\mathbf {A}^{{\!\scriptscriptstyle {\top }}}\mathbf {x}_i],[\mathbf {A}^{{\!\scriptscriptstyle {\top }}}\mathbf {y}_i]\}_{i=1}^n) $$

  and the master secret key is $\mathsf {msk}:=(\{\mathbf {k}_i, \mathbf {x}_i,\mathbf {y}_i\}_{i=1}^n)$.

• $\mathsf {KeyGen}( \mathsf {msk},\mathsf {mpk},i)$: Output the secret key $\mathsf {sk}_i=(\mathbf {k}_i, \mathbf {x}_i,\mathbf {y}_i)$.

• $\mathsf {Enc}(\mathsf {mpk},m,S)$: Let $\ell :=|S|$ and $S = \{i_1,\ldots ,i_\ell \} \subseteq U = [n]$. Sample $\mathbf {r}\leftarrow _{\textsc {r}}{\mathbb {Z}}_p^k$ and compute $[\mathbf {u}^{{\!\scriptscriptstyle {\top }}}]:=[\mathbf {r}^{{\!\scriptscriptstyle {\top }}}\mathbf {A}^{{\!\scriptscriptstyle {\top }}}].$ Generate $(\mathsf {sk_{ots},pk_{ots}}) \leftarrow _{\textsc {r}}\mathsf {Gen_{ots}}(1^\lambda )$, compute $\alpha := \mathsf {h}(\mathsf {pk_{ots}})$ and $c_1:=[\mathbf {r}^{{\!\scriptscriptstyle {\top }}}\mathbf {A}^{{\!\scriptscriptstyle {\top }}} \mathbf {k}_{i_1}] \cdot m, v_1:=[\mathbf {r}^{{\!\scriptscriptstyle {\top }}}\mathbf {A}^{{\!\scriptscriptstyle {\top }}}(\mathbf {x}_{i_1} + \alpha \cdot \mathbf {y}_{i_1})], \dots , c_\ell :=[\mathbf {r}^{{\!\scriptscriptstyle {\top }}}\mathbf {A}^{{\!\scriptscriptstyle {\top }}} \mathbf {k}_{i_\ell }] \cdot m,v_\ell :=[\mathbf {r}^{{\!\scriptscriptstyle {\top }}}\mathbf {A}^{{\!\scriptscriptstyle {\top }}}(\mathbf {x}_{i_\ell } + \alpha \cdot \mathbf {y}_{i_\ell })].$ Choose a random permutation $\tau$ over $[\ell ]$ and compute $\sigma := \mathsf {Sig}(\mathsf {sk_{ots}},([\mathbf {u}^{{\!\scriptscriptstyle {\top }}}],c_{\tau (1)},v_{\tau (1)},\dots ,c_{\tau (\ell )},v_{\tau (\ell )})).$ The ciphertext is 

  $$ \mathsf {ct}:=([\mathbf {u}^{{\!\scriptscriptstyle {\top }}}],c_{\tau (1)},v_{\tau (1)} ,\dots , c_{\tau (\ell )},v_{\tau (\ell )} ,\mathsf {pk_{ots}},\sigma ).$$

• $\mathsf {Dec}(\mathsf {mpk}, \mathsf {ct}, \mathsf {sk}_i)$: Parse the ciphertext $\mathsf {ct}$ as $([\mathbf {u}^{{\!\scriptscriptstyle {\top }}}], \bar{c}_{1},\bar{v}_{1},\dots ,\bar{c}_{\ell },\bar{v}_{\ell },\mathsf {pk_{ots}},\sigma )$ and the secret key $\mathsf {sk}_i$ as $(\mathbf {k}_i,\mathbf {x}_i,\mathbf {y}_i)$. Return $\bot$ if

  $$ \mathsf {Ver}(\mathsf {pk_{ots}},([\mathbf {u}^{{\!\scriptscriptstyle {\top }}}],\bar{c}_{1},\bar{v}_{1},\dots ,\bar{c}_{\ell },\bar{v}_{\ell }),\sigma )=0, $$

  otherwise, compute

  $$ v := [\mathbf {u}^{{\!\scriptscriptstyle {\top }}}(\mathbf {x}_i + \alpha \cdot \mathbf {y}_i)], $$

  where $\alpha =\mathsf {h}(\mathsf {pk_{ots}})$. If there exists $j \in [\ell ]$ such that $v = \bar{v}_j$, return $m' := \bar{c}_j/[\mathbf {u}^{{\!\scriptscriptstyle {\top }}}\mathbf {k}_i]$; otherwise, return $\bot$.

It is direct to check the correctness.

3.2 Security Result and Proof Overview

We prove the following theorem.

Theorem 1

Our broadcast encryption scheme in Sect. 3.1 is adaptively ANO-IND-CCA secure assuming that: (1) $\mathcal {H}$ is collision-resistant; (2) the $\mathcal {D}_k$-$\mathsf {MDDH}$ assumption holds in ${\mathbb {G}}$; (3) signature scheme $(\mathsf {Gen_{ots}, Sig, Ver})$ is strongly unforgeable under one-time chosen message attack. Concretely, for any adversary $\mathcal {A}$, there exist algorithms $\mathcal {B}_1,\mathcal {B}_2,\mathcal {B}_3$ such that

$$ \mathsf {Adv}^{\mathsf {BE}}_\mathcal {A}(\lambda ) \le \mathsf {Adv}^{\mathsf {mddh}}_{{\mathbb {G}},\mathcal {B}_1}(\lambda ) + \mathsf {Adv}^{\mathsf {ots}}_{\mathcal {B}_2}(\lambda )+\mathsf {Adv}^{\mathsf {hash}}_{\mathcal {B}_3}(\lambda ) + {O}(1/p) $$

and $\mathsf {Time}(\mathcal {B}_1), \mathsf {Time}(\mathcal {B}_2), \mathsf {Time}(\mathcal {B}_3) \approx \mathsf {Time}(\mathcal {A})$.

We prove the theorem via the following game sequence. A proof sketch for each step will be given and more details can be found in the full paper.

 

$\mathsf {Game}_0$.:

This game is identical to the real game described in Sect. 2.1. The challenge ciphertext for $(m_0,m_1,S_0,S_1)$ where $S_0 =\{i_{1,0},\ldots ,i_{\ell ,0}\}$ and $S_1 = \{i_{1,1},\ldots ,i_{\ell ,1}\}$ is of form

$$ \mathsf {ct}^*:=(\, \mathsf {ct}_1^*:=([\mathbf {u}^{*{\!\scriptscriptstyle {\top }}}],c^*_{1},v^*_{1},\dots ,c^*_{\ell },v^*_{\ell }),\,\mathsf {pk^*_{ots}},\, \sigma ^*:=\mathsf {Sig}(\mathsf {sk^*_{ots}}, \mathsf {ct}_1^*)\,) $$

where $\mathbf {u}^* \leftarrow _{\textsc {r}}\mathsf {span}(\mathbf {A})$, $(\mathsf {sk^*_{ots}},\mathsf {pk^*_{ots}})\leftarrow _{\textsc {r}}\mathsf {Gen_{ots}}(1^\lambda )$, and we compute

$$ c^*_j = [\mathbf {u}^{*{\!\scriptscriptstyle {\top }}}\mathbf {k}_{i_{\tau (j),b}}]\cdot m_b \quad \text{ and }\quad v^*_j = [\mathbf {u}^{*{\!\scriptscriptstyle {\top }}}(\mathbf {x}_{i_{\tau (j),b}}+\alpha ^*\cdot \mathbf {y}_{i_{\tau (j),b}})],\quad \forall j \in [\ell ] $$

with $b\leftarrow _{\textsc {r}}\{0,1\}$, $\alpha ^*=\mathsf {h}(\mathsf {pk^*_{ots}})$ and a random permutation $\tau$ over $[\ell ]$. On input $( \mathsf {ct},i)$, $\mathsf {DecO}$ parses

$$ \mathsf {ct}=( \mathsf {ct}_1=([\mathbf {u}^{{\!\scriptscriptstyle {\top }}}],c_{1},v_{1},\dots ,c_{\ell },v_{\ell }),\mathsf {pk_{ots}},\sigma ), $$

and rejects the query if

$$ (a) \quad \mathsf {ct}= \mathsf {ct}^*\quad \text { or }\quad (b) \quad \mathsf {Ver}(\mathsf {pk_{ots}}, \mathsf {ct}_1,\sigma )=0. $$

Then compute $v = [\mathbf {u}^{{\!\scriptscriptstyle {\top }}}(\mathbf {x}_i + \alpha \cdot \mathbf {y}_i)]$ with $\alpha =\mathsf {h}(\mathsf {pk_{ots}})$. If there exists $j \in [\ell ]$ such that $v = v_j$, return $m' := c_j/[\mathbf {u}^{{\!\scriptscriptstyle {\top }}}\mathbf {k}_i]$; otherwise, return $\bot$. Let $\mathsf {Win}_i$ denote the event that $\mathcal {A}$ in $\mathsf {Game}_i$ guesses b correctly. Since $\mathsf {Game}_0$ perfectly simulates the real game, we have $\mathsf {Adv}_{\mathcal {A}}^{\mathsf {BE}}(1^\lambda ) = |\Pr [\mathsf {Win}_0] - 1/2|$.

$\mathsf {Game}_1$.:

This game is identical to $\mathsf {Game}_0$ except that we sample $\mathbf {u}^* \leftarrow _{\textsc {r}}\mathbb {Z}^{k+1}_p$ when generating the challenge ciphertext $\mathsf {ct}^*$. It is easy to see that this game is indistinguishable from $\mathsf {Game}_0$ under the $\mathcal {D}_{k}$-$\mathsf {MDDH}$ assumption. Formally, we have the following lemma.

Lemma 2 ($\mathsf {Game}_1 \approx _c \mathsf {Game}_0$). There exists an adversary $\mathcal {B}_1$ such that

$$|\Pr [\mathsf {Win}_1]-\Pr [\mathsf {Win}_0]| \le \mathsf {Adv}^{\mathsf {mddh}}_{{\mathbb {G}},\mathcal {B}_1}(\lambda ).$$

$\mathsf {Game}_2$.:

This game is identical to $\mathsf {Game}_1$ except that $\mathsf {DecO}$, on input $( \mathsf {ct},i)$, rejects the query if (a) or (b) or

$$ (c)\quad \mathsf {pk_{ots}}=\mathsf {pk^*_{ots}}. $$

This game is identical to $\mathsf {Game}_1$ until $\mathcal {A}$ submits a query with $\mathsf {pk_{ots}}=\mathsf {pk^*_{ots}}$ which survives under condition (a) and (b). However $\sigma$ in such a query will violate the strong unforgeability of $(\mathsf {Gen_{ots}, Sig, Ver})$, and this game is indistinguishable from $\mathsf {Game}_1$. Formally, we have the following lemma.

Lemma 3 ($\mathsf {Game}_2 \approx _c \mathsf {Game}_1$). There exists an adversary $\mathcal {B}_2$ such that

$$|\Pr [\mathsf {Win}_2]-\Pr [\mathsf {Win}_1]| \le \mathsf {Adv}^{\mathsf {ots}}_{\mathcal {B}_2}(\lambda ).$$

$\mathsf {Game}_3$.:

This game is identical to $\mathsf {Game}_2$ except the following substitution:

$$ (c)\quad \mathsf {pk_{ots}}=\mathsf {pk^*_{ots}}\quad \longmapsto \quad (c')\quad \alpha = \alpha ^* $$

This game is identical to $\mathsf {Game}_2$ until $\mathcal {A}$ submits a query with $\mathsf {pk_{ots}}\ne \mathsf {pk^*_{ots}}$ but $\alpha = \alpha ^*$. This immediately violates the collision-resistance of $\mathcal {H}$, and this game is indistinguishable from $\mathsf {Game}_2$. Formally, we have the following lemma.

Lemma 4 ($\mathsf {Game}_3 \approx _c \mathsf {Game}_2$). There exists an algorithm $\mathcal {B}_3$ such that

$$|\Pr [\mathsf {Win}_3]-\Pr [\mathsf {Win}_2]| \le \mathsf {Adv}^{\mathsf {hash}}_{\mathcal {B}_3}(\lambda ).$$

$\mathsf {Game}_4$.:

This game is identical to $\mathsf {Game}_3$ except that except that $\mathsf {DecO}$, on input $( \mathsf {ct},i)$, rejects the query if (a) or (b) or $(c')$ or

$$ (d)\quad \mathbf {u}\notin \mathsf {span}(\mathbf {A}) $$

We have the following lemma stating that this game is statistically indistinguishable with $\mathsf {Game}_3$.

Lemma 5 ($\mathsf {Game}_4 \approx _s \mathsf {Game}_3$). $|\mathsf {Win}_4-\mathsf {Win}_3|\le {O}(1/p)$.

Let $q_D$ be the number of decryption queries. The lemma can be proved in $q_D$ steps. In the j-th step, assuming that the first $j-1$ decryption queries have been processed with condition (d), we demonstrate that the j-th query will finally be rejected if it survives under condition $(a),(b),(c')$ with $\mathbf {u}\notin \mathsf {span}(\mathbf {A})$. In other words, we can introduce condition (d) here without changing adversary’s view. The proof (for the j-th step) relies on the observation that we leak no more information than $\{\mathbf {A}^{{\!\scriptscriptstyle {\top }}}\mathbf {x}_\eta ,\mathbf {A}^{{\!\scriptscriptstyle {\top }}}\mathbf {y}_\eta \}_{\eta \in [n]}$ when answering the first $j-1$ queries to $\mathsf {DecO}$. With the help of condition $(c')$, which ensures that $\alpha \ne \alpha ^*$, we can claim that $\mathbf {u}^{\!\scriptscriptstyle {\top }}(\mathbf {x}_i + \alpha \cdot \mathbf {y}_i)$ is independently and uniformly distributed and thus hard to guess.

 

Finally, we have the following lemma which proves Theorem 1 when combining with all previous lemmas and claims.

Lemma 6

$\Pr [\mathsf {Win}_4] = 1/2$.

This follows from the fact that $(\mathbf {u}^*\mathbf {k}_i,\mathbf {u}^*(\mathbf {x}_i + \alpha \cdot \mathbf {y}_i))$ are uniformly distributed over ${\mathbb {G}}^2$, especially unrelated to b, for all $i \in S_b~(\text {resp. }i\in S_b/S_{1-b})$ when $Q_ \mathsf {sk}\cap (S_0 \cap S_1) = \emptyset$ (resp. $Q_ \mathsf {sk}\cap (S_0 \cap S_1) \ne \emptyset$), conditioned on $\mathsf {mpk},\mathsf {KeyO}$ and $\mathsf {DecO}$. The analysis is similar to that for Lemma 5.

Perspective. Lemmas 5 and 6 are at the core of our proof. Although our proofs still rely on the proof technique of underlying Cramer-Shoup PKE, we get rid of large reduction loss by carrying out the argument in the broadcast setting directly. In particular, we employ the technique beneath the core lemma from Kiltz and Wee [KW15] (see Lemma 1), which allows us to take all users into account in a non-adaptive way first and then upgrade to the adaptive setting for free. This avoids guessing adversary’s behaviour in the simulation which caused large security loss in Libert et al.’s work [LPQ12]. Furthermore, we note that our proof indeed involves robustness [ABN10, Moh10, LPQ12] but in an implicit manner since we are not working with generic PKE anymore.

4 Tightly Secure ANOBE with Shorter Ciphertext

4.1 Construction

• $\mathsf {Setup}~(1^\lambda ,n)$: Run $\mathcal {PG}:= (p,{\mathbb {G}}_1,{\mathbb {G}}_2,{\mathbb {G}}_T,e,g_1,g_2) \leftarrow _{\textsc {r}}\mathsf {PGGen}(1^{\lambda })$. Sample

  $$ \mathbf {A}, \mathbf {B}\leftarrow _{\textsc {r}}\mathcal {D}_k,\ \mathbf {X},\mathbf {Y}\leftarrow _{\textsc {r}}\mathbb {Z}_p^{(k+1)\times (k+1)},\ \mathbf {k}_i \leftarrow _{\textsc {r}}\mathbb {Z}_p^{k+1}\ \text { for } i \in [n]. $$

  Select a key-binding secure symmetric encryption scheme $(\mathsf {E},\mathsf {D})$ with the key space $\mathcal {K}:={\mathbb {G}}_1$ and a collision-resilient hash function $\mathsf {h}\leftarrow _{\textsc {r}}\mathcal {H}$ mapping from $\{0,1\}^*$ to $\mathbb {Z}_p$. The master public key is

  $$ \mathsf {mpk}:=\left( \mathcal {P}\mathcal {G}, (\mathsf {E},\mathsf {D}),\mathsf {h};\ \begin{array}{llll} [\mathbf {A}^{\!\scriptscriptstyle {\top }}]_1, &{}\{[\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {k}_i]_1\}_{i=1}^n, &{} [\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {X}]_1, &{} [\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {Y}]_1 \\ {[\mathbf {B}]_2}, &{} &{} [\mathbf {X}\mathbf {B}]_2, &{} [\mathbf {Y}\mathbf {B}]_2\\ \end{array}\right) $$

  and the master secret key is $\mathsf {msk}:=\{\mathbf {k}_i\}_{i=1}^n$.

• $\mathsf {KeyGen}~( \mathsf {msk},\mathsf {mpk},i)$: Output the secret key $\mathsf {sk}_i:=\mathbf {k}_i$.

• $\mathsf {Enc}~(\mathsf {mpk},m,S)$: Let $\ell :=|S|$ and $S = \{i_1,\ldots ,i_\ell \} \subseteq U$. Sample $\mathbf {r}\leftarrow _{\textsc {r}}\mathbb {Z}_p^{k}$ and compute $[\mathbf {u}^{\!\scriptscriptstyle {\top }}]_1 := [\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}]_1.$ Select session key $K \leftarrow _{\textsc {r}}{\mathbb {G}}_1$ and compute

  $$ c_0 := \mathsf {E}_{K}(m),\ c_1 := [\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {k}_{i_1}]_1 \cdot K,\ \ldots ,\ c_\ell := [\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {k}_{i_\ell }]_1 \cdot K $$

  Choose a random permutation $\tau$ over $[\ell ]$ and compute

  $$ [{\varvec{\pi }}]_1 := [\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}(\mathbf {X}+ \alpha \cdot \mathbf {Y})]_1 $$

  where $\alpha := \mathsf {h}([\mathbf {u}^{\!\scriptscriptstyle {\top }}]_1,c_0,c_{\tau (1)},\dots ,c_{\tau (\ell )})$. The ciphertext is

  $$ \mathsf {ct}:= (\;[\mathbf {u}^{\!\scriptscriptstyle {\top }}]_1,\,c_0,\,c_{\tau (1)},\,\dots ,\,c_{\tau (\ell )},,\,[{\varvec{\pi }}]_1\;). $$

• $\mathsf {Dec}(\mathsf {mpk}, \mathsf {ct}, \mathsf {sk}_i)$: Parse $\mathsf {ct}$ as $([\mathbf {u}^{\!\scriptscriptstyle {\top }}]_1,c_0, \bar{c}_{1},\dots ,\bar{c}_{\ell },[{\varvec{\pi }}]_1)$ and $\mathsf {sk}_i$ as $\mathbf {k}_i$. Compute $\alpha = \mathsf {h}([\mathbf {u}^{\!\scriptscriptstyle {\top }}]_1, c_0,\bar{c}_{1},\dots ,\bar{c}_{\ell })$ and check

  $$\begin{aligned} e([{\varvec{\pi }}]_1,[\mathbf {B}]_2)\,{\mathop {=}\limits ^{?}}\,e([\mathbf {u}^{\!\scriptscriptstyle {\top }}]_1, [(\mathbf {X}+ \alpha \cdot \mathbf {Y})\mathbf {B}]_2). \end{aligned}$$

  (1)

  If Eq. (1) does not hold, return $\perp$; otherwise, do the following two steps from $j := 1$.

  • 1. Compute $K' := \bar{c}_j/[\mathbf {u}^{\!\scriptscriptstyle {\top }}\mathbf {k}_i]_1$ and $m' := \mathsf {D}_{K'}(c_0)$. If $m' \ne \perp$, return $m'$ and halt; otherwise, go to the second step.

  • 2. If $j = \ell$, return $\perp$ and halt; otherwise, do the first step with $j := j+1$.

Correctness. For any ciphertext $\mathsf {ct}:= ( [\mathbf {u}^{\!\scriptscriptstyle {\top }}]_1,c_0,\bar{c}_{1},\dots ,\bar{c}_{\ell },[{\varvec{\pi }}]_1 )$ for set $S \subseteq U$ produced by $\mathsf {Enc}$, we have

$$ e([{\varvec{\pi }}]_1,[\mathbf {B}]_2) = e([\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}(\mathbf {X}+ \alpha \cdot \mathbf {Y})]_1,[\mathbf {B}]_2) =e([\mathbf {u}^{\!\scriptscriptstyle {\top }}]_1, [(\mathbf {X}+ \alpha \cdot \mathbf {Y})\mathbf {B}]_2) $$

where $\alpha = \mathsf {h}([\mathbf {u}^{\!\scriptscriptstyle {\top }}]_1, c_0,\bar{c}_{1},\dots ,\bar{c}_{\ell })$. That is the ciphertext always satisfies Eq. (1). Given a secret key $\mathsf {sk}_i = \mathbf {k}_i$ for $i \in S$, we know that there exists $i' \in [\ell ]$ such that $c_{i'} = [\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {k}_i]_1 \cdot K$. The correctness of our ANOBE then follows from the following two observations:

• 1. For each $j < i'$, we know that $c_j = [\mathbf {r}^{\!\scriptscriptstyle {\top }}\mathbf {A}^{\!\scriptscriptstyle {\top }}\mathbf {k}_{j'}]_1\cdot K \text { for some }\ j' \in S \setminus \{i\},$ and thus we have

  $$ c_j / [\mathbf {u}^{\!\scriptscriptstyle {\top }}\mathbf {k}_i]_1 \ne K $$

  with overwhelming probability. From the key-binding feature of $(\mathsf {E},\mathsf {D})$, the decryption algorithm $\mathsf {Dec}$ will return nothing before the $i'$-th iteration.

• 2. It is easy to see that

  $$ c_{i'} / [\mathbf {u}^{\!\scriptscriptstyle {\top }}\mathbf {k}_i]_1 = K. $$

  By the correctness of $(\mathsf {E},\mathsf {D})$, the decryption algorithm $\mathsf {Dec}$ will return m in the $i'$-th iteration.

4.2 Security Result and Proof Overview

We prove the following theorem.

Theorem 2

Our broadcast encryption described in Sect. 4.1 is ANO-IND-CCA secure assuming that: (1) $\mathcal {H}$ is collision-resistant; (2) the $\mathcal {D}_{k}$-$\mathsf {MDDH}$ assumption holds in ${\mathbb {G}}_1$; (3) the $\mathcal {D}_k$-$\mathsf {KerMDH}$ assumptions holds in ${\mathbb {G}}_2$; (4) $(\mathsf {E},\mathsf {D})$ is semantically secure. Concretely, for any adversary $\mathcal {A}$, there exist algorithms $\mathcal {B}_1,\mathcal {B}_2,\mathcal {B}_3,\mathcal {B}_4$, such that

$$ \mathsf {Adv}^{\mathsf {BE}}_\mathcal {A}(\lambda )\le \mathsf {Adv}^{\mathsf {mddh}}_{\mathcal {B}_1,{\mathbb {G}}_1}(\lambda ) + \mathsf {Adv}^{\mathsf {hash}}_{\mathcal {B}_2}(\lambda ) + \mathsf {Adv}^{\mathsf {kmdh}}_{\mathcal {B}_3,{\mathbb {G}}_2}(\lambda ) + 2 \cdot \mathsf {Adv}^{\mathsf {se}}_{\mathcal {B}_4}(\lambda ) + {O}(1/p) $$

and $\mathsf {Time}(\mathcal {B}_1), \mathsf {Time}(\mathcal {B}_2),\mathsf {Time}(\mathcal {B}_3), \mathsf {Time}(\mathcal {B}_4) \approx \mathsf {Time}(\mathcal {A})$.

We prove the theorem via the following game sequence. A proof sketch for each step will be given and more details can be found in the full paper.

 

$\mathsf {Game}_0$.:

This game is identical to the real game described in Sect. 2.1. The challenge ciphertext for $(m_0,m_1,S_0,S_1)$ where $S_0 =\{i_{1,0},\ldots ,i_{\ell ,0}\}$ and $S_1 = \{i_{1,1},\ldots ,i_{\ell ,1}\}$ is of form

$$ \mathsf {ct}^* := (\; \mathsf {ct}^*_1:= ([{\mathbf {u}^*}^{\!\scriptscriptstyle {\top }}]_1,c^*_0,c^*_{1},\dots ,c^*_{\ell }),\,[{\varvec{\pi }}^*]_1 := [{\mathbf {u}^*}^{\!\scriptscriptstyle {\top }}(\mathbf {X}+ \alpha ^* \cdot \mathbf {Y})]_1\;) $$

where $\mathbf {u}^*\leftarrow _{\textsc {r}}\mathsf {span}(\mathbf {A})$, $\alpha ^* = \mathsf {h}( \mathsf {ct}^*_1)$ and we compute

$$c_0^* = \mathsf {E}_{K^*}(m_b) \quad \text{ and }\quad c^*_{j} = [{\mathbf {u}^*}^{\!\scriptscriptstyle {\top }}\mathbf {k}_{i_{\tau (j),b}}]_1 \cdot K^*, \quad \forall j \in [\ell ] $$

with $K^* \leftarrow _{\textsc {r}}{\mathbb {G}}_1$ and random permutation $\tau$ over $[\ell ]$. On input $( \mathsf {ct},i)$, parse

$$ \mathsf {ct}= ( \mathsf {ct}_1=([\mathbf {u}^{\!\scriptscriptstyle {\top }}]_1,c_0, c_{1},\dots ,c_{\ell }),[{\varvec{\pi }}]_1), $$

compute $\alpha = \mathsf {h}( \mathsf {ct}_1)$ and reject the query if

$$ (a) \quad \mathsf {ct}= \mathsf {ct}^*\quad \text {or} \quad (b) \quad e([{\varvec{\pi }}]_1,[\mathbf {B}]_2) \ne e([\mathbf {u}^{\!\scriptscriptstyle {\top }}]_1, [(\mathbf {X}+ \alpha \cdot \mathbf {Y})\mathbf {B}]_2). $$

Then recover m using $\mathbf {k}_i$ as $\mathsf {Dec}$ and return m. We let $\mathsf {Win}_i$ denote the event that $\mathcal {A}$ guesses b correctly in $\mathsf {Game}_i$. Since $\mathsf {Game}_0$ perfectly simulates the real game, we have $\mathsf {Adv}_{\mathcal {A}}^{\mathsf {BE}}(1^\lambda ) = |\Pr [\mathsf {Win}_0] - 1/2|$.

$\mathsf {Game}_1$.:

This game is identical to $\mathsf {Game}_0$ except that we sample $\mathbf {u}^* \leftarrow _{\textsc {r}}\mathbb {Z}^{k+1}_p$ when generating the challenge ciphertext $\mathsf {ct}^*$. This game is indistinguishable from $\mathsf {Game}_0$ under the $\mathcal {D}_{k}$-$\mathsf {MDDH}$ assumption. Formally, we have the following lemma and the proof is analgous to that for Lemma 2.

Lemma 7 ($\mathsf {Game}_1 \approx _c \mathsf {Game}_0$). There exists an adversary $\mathcal {B}_1$ such that

$$|\Pr [\mathsf {Win}_1]-\Pr [\mathsf {Win}_0]| \le \mathsf {Adv}_{\mathcal {B}_1,{\mathbb {G}}_1}^{\mathsf {mddh}}(\lambda )$$

$\mathsf {Game}_2$.:

This game is identical to $\mathsf {Game}_1$ except that $\mathsf {DecO}$, on input $( \mathsf {ct},i)$, returns $\bot$ if (a) or (b) or

$$ (c)\quad \mathsf {ct}_1 \ne \mathsf {ct}^*_1 \text { but } \alpha = \alpha ^*. $$

By the collision-resilience of $\mathcal {H}$, this game is indistinguishable from $\mathsf {Game}_1$. Formally, we have the following lemma and the proof is similar to that for Lemma 4.

Lemma 8 ($\mathsf {Game}_2 \approx _c \mathsf {Game}_1$). There exists an algorithm $\mathcal {B}_2$ such that

$$ |\Pr [\mathsf {Win}_2]-\Pr [\mathsf {Win}_1]|\le \mathsf {Adv}^{\mathsf {hash}}_{\mathcal {B}_2}(\lambda ) $$

$\mathsf {Game}_3$.:

This game is identical to $\mathsf {Game}_2$ except the following substitution:

$$ (b) \, e([{\varvec{\pi }}]_1,[\mathbf {B}]_2) \ne e([\mathbf {u}^{\!\scriptscriptstyle {\top }}]_1, [(\mathbf {X}+ \alpha \cdot \mathbf {Y})\mathbf {B}]_2) \, \longmapsto \, (b') \, [{\varvec{\pi }}]_1 \ne [\mathbf {u}^{\!\scriptscriptstyle {\top }}(\mathbf {X}+ \alpha \cdot \mathbf {Y})]_1. $$

This game is the same as $\mathsf {Game}_2$ until $\mathcal {A}$ sends $\mathsf {DecO}$ a query which is rejected by condition $(b')$ but survives under condition (b). One can see that such a query immediately gives a solution to the $\mathcal {D}_k$-$\mathsf {KerMDH}$ problem w.r.t $[\mathbf {B}]_2$. Formally, we have the following lemma.

Lemma 9 ($\mathsf {Game}_3 \approx _c \mathsf {Game}_2$). There exists an algorithm $\mathcal {B}_3$ such that

$$ |\Pr [\mathsf {Win}_3]-\Pr [\mathsf {Win}_2]|\le \mathsf {Adv}_{\mathcal {B}_3,{\mathbb {G}}_2}^{\mathsf {kmdh}}(\lambda ) $$

$\mathsf {Game}_4$.:

This game is identical to $\mathsf {Game}_3$ except the following substitution

$$ (b') \, [{\varvec{\pi }}]_1 \ne [\mathbf {u}^{\!\scriptscriptstyle {\top }}(\mathbf {X}+ \alpha \cdot \mathbf {Y})]_1\, \longmapsto \, (b'')\, \mathbf {u}\notin \mathsf {span}(\mathbf {A})\ \Vert \ [{\varvec{\pi }}]_1 \ne [\mathbf {u}^{\!\scriptscriptstyle {\top }}(\mathbf {X}+ \alpha \cdot \mathbf {Y})]_1. $$

Here “$\Vert$” denotes the OR operation which neglects the second operand if the first one is satisfied. We have the following lemma stating that this game is statistically close to $\mathsf {Game}_3$.

Lemma 10 ($\mathsf {Game}_4 \approx _s \mathsf {Game}_3$). $|\Pr [\mathsf {Win}_4]-\Pr [\mathsf {Win}_3]|\le {O}(1/p)$. Let $q_D$ be the number of decryption queries. The lemma will be proved in $q_D$ steps. In the j-th step, assuming that the first $j-1$ decryption queries have been processed with condition $(b'')$, we demonstrate that the j-th query with $\mathbf {u}\notin \mathsf {span}(\mathbf {A})$ can be rejected by condition $(a),(b'),(c)$ with high probability. This simply follows from Lemma 1 (the core lemma).

 

To complete the proof of Theorem 2, we show the following lemma.

Lemma 11

(Bounding $\Pr [\mathsf {Win}_4]$). There exists an algorithm $\mathcal {B}_4$ such that

$$ \Pr [\mathsf {Win}_4] \le 1/2 + 2 \cdot \mathsf {Adv}^{\mathsf {se}}_{\mathcal {B}_4}(\lambda ) $$

To prove the lemma, we consider two cases: (1) when $Q_ \mathsf {sk}\cap (S_0 \cap S_1) = \emptyset$, we can prove that $[\mathbf {u}^{*{\!\scriptscriptstyle {\top }}}\mathbf {k}_i]_1$ for $i \in S_b$ are independently and uniformly distributed over ${\mathbb {G}}_1$, which hide both $S_b$ and $K^*$. The proof is similar to the proof of Lemma 6. Then the semantic security of $(\mathsf {E},\mathsf {D})$ allows us to hide $m_b$; (2) when $Q_ \mathsf {sk}\cap (S_0 \cap S_1) \ne \emptyset$, we can only prove that $[\mathbf {u}^{*{\!\scriptscriptstyle {\top }}}\mathbf {k}_i]_1$ for $i \in S_b \setminus S_{1-b}$ are randomly distributed, but it is sufficient for proving the lemma since $m_0=m_1$.

5 Conclusion

In this paper, we described two concrete ANOBE schemes. The first one is an instantiation of Libert et al.’s generic ANOBE. However, by working out the proof directly, we achieved a constantly tight reduction to standard assumptions. Furthermore, we pointed out that this scheme supports fast decryption for free and thus enjoys shorter ciphertexts. By the second scheme, we showed how to shorten the ciphertext again while preserving the tightness at the cost of slower decryption.