Ternary subset difference revocation in public key framework supporting outsider anonymity

Abstract

Broadcast encryption (BE) is a cryptographic primitive which sends encrypted message to the users securely. The BE scheme proposed by Naor, Naor, and Lotspiech (NNL) in 2001 is a popular BE scheme which uses a binary tree. The advanced access content system standard suggested to use it for digital right management in Blue-ray and DVD-discs. This paper puts forward an efficient broadcast encryption in public key setting employing ternary tree subset difference method for revocation. Our approach utilizes composite order bilinear group setting to achieve the tree based construction in public key setting. Our second construction is an extension of our first construction and provides outsider-anonymity by disabling the revoked users from getting any information of message and concealing the set of subscribed users from the revoked users. The construction of Fazio and Perera is the closest one to that of our second scheme (as both of these construction are in public key setting and provides outsider-anonymity). We have reduced the ciphertext size from $r\log N/r$ to min$\{N/3,N-r,2r-1\}.$ Thus reduces the communication bandwidth. We have also reduced the public key size. Our constructions enjoy the revocation property. Both of our constructions achieve selective semantic security in the standard model under reasonable assumptions and new users can join without updating the pre-existing setup.

1 Introduction

Broadcast encryption has received much attention from both the network and cryptography community. It is a cryptographic mechanism that provides the encrypted message to a group of users in such a way that the non-members are unable to get the message. Broadcast encryption was formally introduced by Fiat and Naor (1994), followed by subsequent works in various flavours- revocation scheme (Boneh et al. 2005; Dodis and Fazio 2003; Halevy and Shamir 2002; Lewko et al. 2010), identity based scheme (Delerablée 2007; Li et al. 2018b; Sakai and Furukawa 2007), bilinear map based scheme (Acharya and Dutta 2018a; Acharya 2020; Boneh et al. 2005; Chen et al. 2020; Ge and Wei 2019; Gentry and Waters 2009; Li et al. 2018a; Phan et al. 2013a), multilinear map based scheme (Boneh et al. 2014). Broadcast encryption is widely used in daily life, expanding from pay-TV to digital right management.

The Advanced Access Content System (AACS 2005) is a standard for digital rights management and content protection of the post-DVD generation of optical discs. The AACS standard build upon the basics of the work of Naor et al. (2001b). Since its public release in 2005, it has been adopted for content protection in HD DVD and Blu-ray Disc. Thus tree based broadcast encryption is a popular broadcast encryption mechanism. Followed by Naor et al. (2001b) various tree based schemes developed. Halevy and Shamir (2002) proposed a layered based tree structure. Dodis and Fazio (2003) proposed a generic technique to convert tree based structure (Halevy and Shamir 2002; Naor et al. 2001b) into public key setting. Bhattacherjee and Sarkar (2015) further studied on this. Most of these tree based constructions are in private key setting. In private key broadcast encryption, both the broadcaster and the private key generation center are the same. The broadcaster needs to know the secret information for encryption. Therefore the same setup cannot be applicable in two different private key broadcast encryption systems. In public key setting, the broadcaster and the private key generation center are different and the broadcaster encrypts the message without using any secret information. Thus the public key setup is more flexible to use.

Basic security property of public key encryption is data secrecy, whereby no information about the original message gets leaked. It can reveal the set of recipients who will receive the message. In modern world of digital technology, hiding the recipient set from the non-recipient users is of crucial importance. For instance, in satellite TV subscription service, a customer usually expects his identity should not get revealed when ordering a sensitive TV channel. It is required that the subscribed user’s identity should remain secret from the other subscribers and outsiders. Barth et al. (2006) introduced an anonymous broadcast encryption scheme to address the privacy issue in broadcast encryption.

Outsider anonymous broadcast encryption is another exciting variant of broadcast encryption that achieves security and privacy of the receivers. Consider following application: Suppose a group of scientists is working on a secret project. They need to share the documents among themselves. However, the documents and the identities of the involved scientists should be kept secret from the outsiders.

In this type of applications, subscribed user’s identity should be kept secret from the outsiders although it need not be concealed from the other subscribers. This notion of anonymity is termed as outsider-anonymity by Fazio and Perera (2012). Most of the broadcast encryption schemes do not support privacy property and decryption algorithms in these schemes take the recipient set S or the non-recipient set ${\mathbb {R}}$ as input (see Fig. 1).

Fig. 1

Broadcast encryption

Table 1 Comparison of various tree based broadcast encryption schemes

Our contribution Our goal is to devise new tree-based public key broadcast encryption which supports revocation as well as outsider-anonymity. We summarize below the main findings of this work:

• (i) Our public key broadcast encryption (PKBE) employs ternary tree subset difference method of Fukushima et al. (2009) to partition subscribed users into groups. For each group, broadcaster generates ciphertext using anonymous hierarchical identity based encryption of Seo et al. (2009). The most related work to our tree based construction OAnoBE, which supports outsider-anonymity in public key setting is the scheme of Fazio and Perera (2012). We have compared the efficiency in ciphertext size with Fazio and Perera (2012) in Fig.  2. Integrating the ternary SD revocation method, we reduce the size of partition, and consequently the ciphertext size, leading to a significant improvement over (Fazio and Perera 2012). A comparative summary of tree based broadcast encryption schemes are outlined in Table 1.

• (ii) Construction of Seo et al. (2009) sends one message to one user. Thus sending message to a group of users needs huge computation cost and communication bandwidth. We have used the construction of Seo et al. (2009) to generate a broadcast encryption scheme. Thus one encryption can send different messages to different group of users. Thus both of our constructions are different from Seo et al. (2009).

• (iii) Broadcast encryption can be broadly classified into two: public key BE and private key BE. In private key BE, the broadcaster plays the role of the private key generation center and consequently, knows sensitive information such as master secret key whose disclosure may compromise the security. The same setup cannot be used by different broadcasters in private key setting. The encrypter either stores the secret keys or computes them during the encryption. On the other hand, public key BE considers the private key generation center and the broadcaster as different entities and performs encryption with the help of public parameters. It reduces the workload of the broadcaster by employing a private key generation center, which is required in many broadcast mechanism. Existing tree based broadcast encryption (Bhattacherjee and Sarkar 2015; Halevy and Shamir 2002; Naor et al. 2001b) are in private key setting where the broadcaster and the private key generation center are same. The public key broadcast encryption of Dodis and Fazio (2003) is in generic model. Both of our tree based constructions are in public key setting.

• (iv) Achieving anonymity is another task in the modern era of digital technology. Most of the tree based constructions do not achieve it. Our second construction OAnoBE achieves outsider-anonymity by disabling the outsiders to know about the recipient set. Outsider-anonymity is weaker than full anonymity in the sense that the user identities are not secret to any user of the group. But there are some applications where it is required to share the message among the subscribers (as discussed in page 2) and thus practical to use.

• (v) More interestingly, our scheme enjoys the revocation property which is one of the most significant requirement in the broadcast encryption setting. To facilitate revocation, subscribed user uses the set of secret keys in such a way that he will capable to recover the message. None of the existing anonymous constructions discusses the revocation process.

• (vi) Furthermore, new users can join any time without updating the pre-existing public key and secret key, provided the number of subscribed users in the system does not exceed the maximum number of users allowed in the system.

Fig. 2

Comparison of cover size (l) against revoked user (r) [number of users N =2000]

Discussion on Tree-based Schemes of Table 1 Naor et al. (2001b) proposed two construction using binary complete subtree and subset difference method respectively. Halevy and Shamir (2002) proposed a scheme using layered subset difference method. Bhattacherjee and Sarkar (2015) proposed a scheme using k-ary tree. Fukushima et al. (2009) proposed a scheme using Ternary subset difference method. All of these schemes are private key broadcast encryption scheme. Thus, these schemes send message to group of users. But, these schemes do not provide any kind of anonymity and not in public key setting. Now we will discuss some public key tree based broadcast encryption schemes. In public key setting, we can use the same Setup for different broadcast encryption schemes as the broadcaster does not need any secure information for encryption. Dodis and Fazio (2003) proposed a public key variant of Naor et al. (2001b). Fazio and Perera (2012) proposed outsider-anonymous broadcast encryption in public key setting. We have provided two constructions. First one reduces ciphertext size compare to the scheme of Fazio and Perera (2012). The second one provides outsider-anonymity by hiding the set of subscribed users from revoked users and also reduces ciphertext size.

Organization The rest of the paper is organized as follows. We discuss related works in Sect.  2. Section  3 provides necessary definitions and background materials. We describe our main constructions in Sect.  4. Section  5 gives the implementation results. We finally conclude in Sect.  6.

2 Related works

Cryptography is a way of sending the message (data) securely to a receiver in such a way that a third party cannot understand the message. In general, cryptographic encryption schemes (e.g., ElGamal 1985; Hu et al. 2016; Liu and Ke 2019; Xu et al. 2020) are one to one where a message is communicated between a sender and a receiver. The broadcast encryption protocols helps to send a message to a group of users. The concept of broadcast encryption was proposed by Fiat and Naor (1994), following which a wide variety of schemes have been proposed. In this section, we discuss various type of broadcast encryption schemes such as revocation based construction, algebraic construction using bilinear and multilinear map, identity based construction, anonymous construction, and others. Depending on size of subscribed and revoked users, BE can be divided into- Subscription based broadcast encryption (e.g., Boneh et al. 2005, 2014; Gentry and Waters 2009; Phan et al. 2013a) and revocation based broadcast encryption (e.g., Delerablée et al. 2007; Dodis and Fazio 2003; Halevy and Shamir 2002; Lewko et al. 2010; Naor et al. 2001b). Revocation based broadcast encryption schemes are useful where $r \ll N$ as smaller revocation set reduces the computation overhead. Here r is the number of revoked users and N is the total number of users supported by the system. Subscription based broadcast encryption schemes are useful where $N-r \ll N$ i.e., subscriber’s set is smaller.

2.1 BE depending on applications

Depending on application BE can be classified into following like- Identity based BE, Traitor Tracing, Distributed BE, Hierarchical BE, Broadcast Encryption with dealership, Recipient Revocable BE, Anonymous BE, Broadcast encryption with personalised messages, Multi-channel BE etc.

• 1. Identity Based Scheme Identity based encryption scheme was introduced by Shamir (1985). Delerablée (2007) proposed first identity based broadcast encryption scheme in Asiacrypt 2007. The scheme is secure under chosen plaintext attack in selective ID model under the GDDHE assumption. Sakai and Furukawa (2007) came up with an identity based broadcast encryption scheme on additive bilinear group with constant private key and ciphertext size. In Asiacrypt 2008, Boneh and Hamburg (2008) proposed generalised identity based encryption scheme. The scheme is key indistinguishable under adaptive key exchange attack in generic bilinear group model with random oracle.

• 2. Traitor Tracing Scheme An important property on broadcast encryption scheme is the traceability. Traitor tracing scheme was introduced by Chor et al. (1994) on Crypto 1994. Boneh et al. (2006) proposed first collision resistance scheme using private linear broadcast encryption. The scheme is secure under the bilinear subgroup decision and subgroup decision assumption. Trace and revoke scheme is a combination of broadcast encryption and tracing scheme. Boneh and Waters (2006) proposed a scheme which is secure under decisional three party Diffie–Hellman assumption. Boneh and Zhandry (2014) proposed a scheme using indistinguishability obfuscation. Security of this scheme lies on security of underlying pseudo random function.

• 3. Distributed Broadcast Encryption Scheme In ProvSec 2014, Wu et al. (2011) proposed another variant of broadcast encryption called as distributed broadcast encryption system in which instead of key generation centre, users creates secret key for themselves. Boneh and Zhandry (2014) proposed several schemes using indistinguishability obfuscation in Crypto 2014. One of them is distributed broadcast encryption and achieves IND-CCA security under the existence of multiparty key exchange protocol.

• 4. Hierarchical Broadcast Encryption Scheme In ACISP 2014, Liu et al. (2014) proposed a new primitive called as hierarchical identity based broadcast encryption scheme where user can delegate their decryption capability to their descendent users. They proposed a CCA secure version Liu et al. (2015) in IJIS 2015.

• 5. Broadcast Encryption with Dealership Scheme Gritti et al. (2015) proposed broadcast encryption with dealership scheme in which instead of broadcaster, a dealer selects a set of subscribed users. The scheme is semi-static IND-CPA secure under N-DBDHE assumption. In this construction broadcaster need to rely on user response to detect a dishonest dealer. Acharya and Dutta (2016) has solved the problem and proposed a scheme with constant communication.

• 6. Recipient Revocable Broadcast Encryption Susilo et al. (2016) introduced recipient revocable broadcast encryption (RRBE) in AsiaCCS 2016. The scheme provides selective security under the $(\hat{f},\phi ,F)$-General Decisional Diffie–Hellman Exponent ($(\hat{f},\phi ,F)$-GDDHE) assumption. The security proof uses random oracles. Lai et al. (2016) proposed an adaptively secure scheme with constant storage. The scheme achieves adaptive security under the Bilinear Diffie–Hellman Exponent problem in the random oracle model. Recently, Lai et al. (2017) proposed another scheme which has similar security property. Schemes Lai et al. (2016), Lai et al. (2017) achieve anonymity property which provides user privacy. Acharya and Dutta (2018b) proposed two constructions in standard model with comparable parameter sizes.

• 7. Anonymous Scheme In FCDS 2006, Barth et al. (2006) proposed a new variant of broadcast encryption, called as private broadcast encryption or anonymous broadcast encryption (AnoBE). The scheme is selective IND-CCA secure in the random oracle model. An adaptive IND-CCA secure scheme with the same parameters and standard security model was developed by Libert et al. (2012) in PKC 2012. In IJNS 2014, Ren et al. (2014) came up with the first identity based anonymous broadcast encryption scheme. The scheme is adaptive IND-CPA secure under asymmetric decisional Bilinear Diffie–Hellman assumption. Fazio and Perera (2012) proposed an anonymous scheme with sublinear ciphertext size in PKC 2012. It achieves outsider-anonymity where no revoked user achieve any information about the subscribed users. Both the schemes (Barth et al. 2006; Libert et al. 2012) are generic. Recipient Revocable Broadcast Encryption Scheme (Lai et al. 2016, 2017 also achieves anonymity (we have discussed in the previous paragraph).

• 8. Broadcast Encryption with Personalized Messages Ohtake et al. (2010) proposed the first broadcast encryption with personalized messages (BEPM) scheme. Security is proven in the selective semantic security model under the Decisional Bilinear Diffie-Hellman Exponent (DBDHE) assumption. Xu et al. (2015) attempted to reduce the public parameter size using multilinear maps (Boneh and Silverberg 2003; Coron et al. 2013; Garg et al. 2013a, b) which is unfortunately flawed. Acharya and Dutta (2017) proposed three constructions. Their first construction achieves similiar security property but second one archives adaptive security. Third construction reduces public parameter size using the multilinear map and achieves selective semantic security under Decisional Hybrid Diffie–Hellman Exponent (DHDHE) assumption.

• 9. Multi-Channel Broadcast Encryption Phan et al. (2013b) developed first multi-channel broadcast encryption (MCBE) scheme in private key setting. The scheme achieves selective indistinguishability against chosen plaintext attack under the decisional bilinear Diffie–Hellman exponent (DBDHE) assumption. Later, Zhao and Li (2013) improved this work and provided an MCBE scheme with short public parameter by reducing the number of exponentiations in the public parameters of the MCBE of Phan et al. (2013b). It gives similar security.

2.2 BE depending on key generation process

Depending upon key generation process, BE can be divided into public key and private key setting.

• 1. Private key BE Private key BE uses same key for encryption and decryption. In private key setting, both the private key generation center and broadcaster are the same. In Crypto 2001, Naor et al. (2001b) suggested two private key broadcast encryption schemes. These schemes are indistinguishable under chosen ciphertext attack (IND-CCA) on “key indistinguishability” assumption. A layer-based subset difference scheme was proposed by Halevy and Shamir (2002) in Crypto 2002. It achieves similar security. Ke et al. (2015) proposed constructions based on balanced incomplete block design and strong partially balanced incomplete block design. Moreover, it enhances the security level.

• 2. Public key BE Private key BE uses same keys for encryption and decryption. More specifically, broadcaster needs some secure information for encryption.Hence, the same Setup cannot be used in different private key BE constructions. Public key BE solves the issue and uses different keys for encryption and decryption purpose. There are various public key constructions like- Acharya and Dutta (2016), Boneh and Zhandry (2014), Boneh et al. (2005), Delerablée (2007), Lewko et al. (2010). We have discussed these in subsection  2.1.

3 Preliminaries

Notation Throughout the paper, we will follow notations and abbreviations of Table  2.

Table 2 Notations and abbreviations

3.1 Public key broadcast encryption

A public key broadcast encryption scheme PKBE= (Setup, KeyGeneration, Encrypt, Decrypt) consists of 3 probabilistic polynomial time (PPT) algorithms Setup, KeyGeneration, Encrypt and 1 deterministic polynomial time algorithm Decrypt.

Setup($N,\lambda$)::

The private key generation centre (PKGC) takes the total number of users N and security parameter $\lambda$ and constructs a public key $\textsf {PK}$ and a master key $\textsf {MK}$.

KeyGeneration(${\textsf {PK}},{\textsf {MK}},i$)::

Receiving the public key $\textsf {PK}$, master key $\textsf {MK}$ and a subscribed user i, the PKGC outputs secret key $sk_i$ of user i.

Encrypt(${\mathbb {R}},{\textsf {PK}},m$)::

The broadcaster takes the set of revoked users $\mathbb {R}$, the public key $\textsf {PK}$ and a message m as input and outputs a ciphertext C.

Decrypt(${\textsf {PK}},sk_i,{\mathbb {R}},C$)::

On input secret key $sk_i$, set of revoked users $\mathbb {R}$, ciphertext C encrypting message m and public key $\textsf {PK}$, a subscribed user i outputs message m.

Correctness The correctness of the scheme lies in the fact that m can be retrieved from C if the user is outside of the revoked set ${\mathbb {R}}$, i.e.,

$$\begin{aligned} {\textsf {Decrypt}}({\textsf { PK}},{\textsf {KeyGeneration}}({\textsf {PK}},{\textsf {MK}},i),{\mathbb {R}}, {\textsf {Encrypt}}({\mathbb {R}},{\textsf {PK}},m))=m, \end{aligned}$$

for every revoked set ${\mathbb {R}}$, every message m.

Security game We define below selective semantic security of PKBE= (Setup, KeyGeneration, Encrypt, Decrypt) following Gentry and Waters (2009) in the form of an indistinguishability game played between a challenger ${\mathcal {C}}$ and an adversary ${\mathcal {A}}$.

Initialization:

The adversary ${\mathcal {A}}$ gives revoked set (i.e., the set of non-subscribed users) ${\mathbb {R}}$ to the challenger ${\mathcal {C}}$.

Setup:

The challenger ${\mathcal {C}}$ runs $({\textsf {PK,MK}})\leftarrow {\textsf {Setup}}(N,\lambda )$. It keeps MK secret to itself and makes PK public.

Phase 1:

The adversary ${\mathcal {A}}$ sends key generation query for $i_1,\ldots ,i_m \in {\mathbb {R}}$ to $\mathcal {C}$ and receives the secret key $sk_i\leftarrow {\textsf {KeyGeneration(PK,MK}},i)$.

Challenge:

The adversary ${\mathcal {A}}$ sends two equal length messages $m_0$, $m_1$ to $\mathcal {C}$. The challenger $\mathcal {C}$ chooses a random $b\in \{0,1\}$, makes $C_b\leftarrow {\textsf {Encrypt}}({\mathbb {R}},{\textsf {PK}},m_b)$ and sends $C_b$ as challenge ciphertext to ${\mathcal {A}}$.

Phase 2:

This is similar to Phase 1 key generation query. The adversary ${\mathcal {A}}$ sends key generation query for $i_{m+1},\ldots ,i_q \in {\mathbb {R}}$ to $\mathcal {C}$ and receives secret key $sk_i\leftarrow {\textsf {KeyGeneration(PK,MK}},i)$.

Guess:

The adversary ${\mathcal {A}}$ output a guess $b^{'}\in \{0,1\}$ of b.

The adversary ${\mathcal {A}}$ wins the game if $b^{'}$= b and its advantage is defined as $Adv_{\mathcal {A}}^{\textsf {PKBE-IND-CPA}} =|Pr(b^{'}=b) - \frac{1}{2}|.$ The probability is over random bits used by $\mathcal {C}$ and ${\mathcal {A}}$.

Definition 1

Broadcast encryption scheme PKBE is $(t,q,\epsilon )$ -IND-CPA secure if $Adv_{\mathcal {A}}^{\textsf {PKBE-IND-CPA}}\le \epsilon$ for every adversary ${\mathcal {A}}$ running for at most t time and making at most q key generation queries.

As our public key broadcast encryption supports outsider-anonymity, we will explain outsider anonymous public key broadcast encryption and its security proof.

$\bullet$ Outsider-anonymous broadcast encryption

In contrast to usual broadcast encryption, the decryption algorithm in OAnoBE does not require the set of subscribers or the set of revoked users as input. Other algorithms are identical to public key broadcast encryption.

Security game

We define below selective semantic security of OAnoBE= (Setup, KeyGeneration, Encrypt, Decrypt) following outsider anonymous scheme of Fazio and Perera (2012) and revocation scheme of Naor et al. (2001b) in the form of an indistinguishability game played between a challenger ${\mathcal {C}}$ and an adversary ${\mathcal {A}}$.

Initialization:

The adversary ${\mathcal {A}}$ gives two revoked sets (i.e., the set of non-subscribed users) ${\mathbb {R}}_0,{\mathbb {R}}_1$ to the challenger ${\mathcal {C}}$, where $\mathbb {{R}}_0,{\mathbb {R}}_1$ contain equal number of revoked users.

Setup:

This is similar to PKBE.

Phase 1:

The adversary ${\mathcal {A}}$ sends key generation query for $i_1,\ldots ,i_m \in {\mathbb {R}}_0 \cap {\mathbb {R}}_1$ to ${\mathcal {C}}$ and receives the secret key $sk_i\leftarrow {\textsf {KeyGeneration(PK,MK}},i)$.

Challenge:

The adversary ${\mathcal {A}}$ sends two equal length messages $m_0$, $m_1$ to ${\mathcal {C}}$. The challenger ${\mathcal {C}}$ chooses a random $b\in \{0,1\}$, makes $C_b\leftarrow {\textsf {Encrypt}}({\mathbb {R}}_b,PK,m_b)$ and sends $C_b$ as challenge ciphertext to ${\mathcal {A}}$.

Phase 2:

This is similar to Phase 1 key generation query. The adversary ${\mathcal {A}}$ sends key generation query for $i_{m+1},\ldots ,i_q \in {\mathbb {R}}_0 \cap {\mathbb {R}}_1$ to ${\mathcal {C}}$ and receives secret key $sk_i\leftarrow {\textsf {KeyGeneration(PK,MK}},i)$.

Guess:

The adversary ${\mathcal {A}}$ output a guess $b^{'}\in \{0,1\}$ of b.

The adversary ${\mathcal {A}}$ wins the game if $b^{'}$= b and its advantage is defined as $Adv_{\mathcal {A}}^{\textsf {OAnoBE-IND-CPA}} =|Pr(b^{'}=b) - \frac{1}{2}|.$ The probability is over random bits used by ${\mathcal {C}}$ and ${\mathcal {A}}$.

Definition 2

Broadcast encryption scheme OAnoBE is $(t,q,\epsilon )$ -IND-CPA secure if $Adv_{{\mathcal{A}}}^{{OAnoBE - IND - CPA}} \le \epsilon$ for every adversary $\mathcal {A}$ running for at most t time and making at most q key generation queries.

3.2 Complexity assumptions

Definition 3

Let ${\mathbb {G}}$ and ${\mathbb {G}}_T$ be two multiplicative groups of order $n=pq$, where bit length of n is $|n|=\lambda$ and p, q are prime. Let g be a generator of ${\mathbb {G}}$. A bilinear map $e:{\mathbb {G}}\times {\mathbb {G}}\longrightarrow {\mathbb {G}}_T$ is a function having the following properties:

• 1. $e(u^a,v^b)=e(u,v)^{ab}$, $\forall ~ u,v\in {\mathbb {G}}$ and $\forall ~ a,b\in {\mathbb {Z}}$.

• 2. The map is non degenerate, i.e., e(g, g) is generator of ${\mathbb {G}}_T$.

The tuple ${\mathbb {S}}=(n,{\mathbb {G}},{\mathbb {G}}_T,e$) is said to be a composite order bilinear group system.

Let ${\mathbb {G}}_p, {\mathbb {G}}_q$ stand for subgroups of ${\mathbb {G}}$ of order p, q respectively, ${\mathbb {G}}_{T,p}, {\mathbb {G}}_{T,q}$ denote subgroups of ${\mathbb {G_T}}$ of order p, q respectively and $g_p,g_q$ are generators of ${\mathbb {G}}_p$ and ${\mathbb {G}}_q$ respectively. We use the notation $x\in _R S$ to denote x is a random element of S. Let $\mathrm{N,R}$ be sets of natural and real numbers respectively. The function $\epsilon (\lambda )$ is said to be a negligible function if for every positive integer c,  $\exists$ an integer $N_c$ such that for every $\lambda > N_c$, $\epsilon (\lambda ) \le \frac{1}{{\lambda } ^c}.$Let $\epsilon :\mathrm{N}\rightarrow \mathrm{R}$ be a function. If $\exists ~ d \in \mathrm{N}$ such that $\epsilon (\lambda ) \le \frac{1}{{\lambda } ^d}$ then $\epsilon$ is negligible function.

• l-Weak decisional bilinear Deffie–Hellman inversion(l-wDBDHI$^{*}$) Assumption (Seo et al. 2009):

  input: $Z=({\mathbb {S}},h,g_q,g_p,g_p^\alpha ,\ldots ,g_p^{\alpha ^l}),T$, where $h \in _R {\mathbb {G}}_p, \alpha \in _R \mathbb {Z}_n,T\in _R {\mathbb {G}}_{T,p}.$

  output: Yes if $T=e(g_p,h)^{\alpha ^{l+1}}$; No otherwise.

  The advantage of adversary ${\mathcal {A}}$ in solving the above problem is $Adv_{\mathcal {A}}^{l-wDBDHI^{*}}$=$|Pr[{\mathcal {A}}(Z, e(g_p,h)^{\alpha ^{l+1}})=1]-Pr[{\mathcal {A}}(Z,T)=1]|$.

  l-wDBDHI$^{*}$ Assumption: For any PPT algorithm ${\mathcal {A}}$ above advantage is negligible, i.e., $Adv_{\mathcal {A}}^{l-wDBDHI^{*}} \le \epsilon (\lambda )$, where $\epsilon (\lambda )$ is a negligible function in security parameter $\lambda$.

• l-Composite decisional Deffie Hellman (l-cDDH) Assumption (Seo et al. 2009):

  input $Z= ({\mathbb {S}},h,g_q,g_p,g_p^\alpha ,\ldots ,g_p^{\alpha ^{l+1}}.R_1,(g_p^{\alpha ^{l+1}})^\beta .R_2),T$, where $R_1,R_2 \in _R {\mathbb {G}}_q, \alpha ,\beta \in _R \mathbb {Z}_n,$ $T\in _R {\mathbb {G}}.$

  output: Yes if $T= g_p^\beta .R_3$, for some $R_3 \in _R {\mathbb {G}}_q$; No otherwise. The advantage of ${\mathcal {A}}$ in solving the above problem is $Adv_{\mathcal {A}}^{l-cDDH}$=$|Pr[{\mathcal {A}}(Z,g_p^\beta .R_3)=1]-Pr[{\mathcal {A}}(Z,T)$ $=1]|$

  l-cDDH Assumption: For any PPT algorithm ${\mathcal {A}}$, $Adv_{\mathcal {A}}^{l-cDDH}$ is negligible.

• Bilinear Subset Decision (BSD) Assumption Seo et al. 2009:

  input: $Z= ({\mathbb {S}},g_q,g_p),T$, where $T\in _R {\mathbb {G}}_{T}$.

  output: Yes if $T\in {\mathbb {G}}_{T,p}$; No otherwise. The advantage of adversary ${\mathcal {A}}$ in solving the above problem is $Adv_{\mathcal {A}}^{BSD}$=$|Pr[{\mathcal {A}}(Z, T)=1]-Pr[{\mathcal {A}}(Z,T^{*})=1]|$, where $T\in {\mathbb {G}}_{T,p}$, $T^{*}\in _R {\mathbb {G}}_{T}$.

  BSD Assumption: For any PPT algorithm ${\mathcal {A}}$, $Adv_{\mathcal {A}}^{BSD}$ is negligible.

Fig. 3

Labeling of nodes of a complete ternary tree with revoked users $R=\{v_{4}^{(2)},v_{4}^{(3)},v_{4}^{(10)}$}, where double-thick lines represent a path from the root node $v_{1}^{(1)}$ to the user u at $v_{4}^{(16)}$, thick lines denote the edges just hanging off this path, circular nodes represent the internal nodes, rectangular nodes are the revoked users and double circular nodes stand for the subscribed users

3.3 Ternary subset difference framework

Our scheme is based on ternary tree SD method as introduced in Fukushima et al. (2009). Consider a complete ternary tree T in which the users lie at the leaf nodes. This system can accommodate at most N users, where N is a power of 3. We level the nodes as in Fig.  3. The root node $v_{1}^{(1)}$ of T is at level 1. The left, middle, right child of $v_i^{(l_i)}$ are $v_{i+1}^{(l_{i+1})}, l_{ i+1}=3{l_i}-2,3{l_i}-1,3{l_i}$ respectively. We denote by $T_{v_i^{(l_i)}}$, the complete subtree rooted at $v_i^{(l_i)}$. For a set of revoked users R, ${\textsf {ST}}(R)$ denotes the Steiner tree, i.e., the minimal subtree of $T(=T_{v_1^{(1)}})$ connecting all the members of the set of revoked users R with the root. For a node $v_i^{(l_i)}$, its parent node is defined as

$$\begin{aligned} {\textsf { parent}}({v_i^{(l_i)}})= {\left\{ \begin{array}{ll} v_ {i-1}^ {\left( \left\lceil {\frac{l_i}{3}}\right\rceil \right) } &{} \text { if it is a left or a middle child}\\ v_{i-1}^{(\frac{l_i}{3})} &{} \text {~if it is a right child}\\ \end{array}\right. } \end{aligned}$$

Path connecting the root to the user u at a leaf node $v_L^{(l_L)}$ is denoted by ${\textsf {path}}(v_L^{(l_L)})$. The nodes on ${\textsf {path}}(v_L^{(l_L)})$ are referred as ${\textsf {PN}}(v_L^{(l_L)})$ and the nodes just hanging of the nodes in ${\textsf {PN}}(v_L^{(l_L)})$ are defined as ${\textsf { HN}}(v_L^{(l_L)})$.

Definition 4

A chain is a sequence of nodes $v_i^{(l_i)}$, $v_{i+1}^{(l_{i+1})}$, $\ldots ,v_j^{(l_j)}$ or $v_i^{(l_i)}$, $v_{i+1}^{(l_{i+1})}$, $\ldots ,v_j^{(l_{j_1})};$ $v_j^{(l_{j_2})}$($v_j^{(l_{j_1})};$ $v_j^{(l_{j_2})}$are siblings) having the following properties in ${\textsf {ST}}(R)$:

• (i) $v_i^{(l_i)}$, $v_{i+1}^{(l_{i+1})}$, $\ldots ,v_{j-2}^{(l_{j-2})}$ have one child each.

• (ii) $v_{j-1}^{(l_{j-1})}$ is either a node with one child or two children.

• (iii) Each of $v_j^{(l_{j_1})},v_j^{(l_{j_2})}$ is either a node with three children or leaf node.

• (iv) $v_i^{(l_i)}$ is the root node or parent($v_i^{(l_i)})$ is a node with two or three children.

We use the notation $S_{{v_i^{(l_i)}} ,{v_j^{(l_j)}}}$ to represent the set of users in $T_{v_i^{(l_i)}}$ minus that in $T_{v_j^{(l_j)}}$ and $S_{{v_i^{(l_i)}} ,{v_j^{(l_{j_1})}}+{v_j^{(l_{j_2})}}}$ to represent the set of users in $T_{v_i^{(l_i)}}$ minus that in $T_{v_j^{(l_{j_1})}}$ and $T_{v_j^{(l_{j_2})}}$. We say that $S_{{v_i^{(l_i)}} ,{v_j^{(l_j)}}}$ is the subset cover generated by the chain $v_i^{(l_i)}$, $v_{i+1}^{(l_{i+1})}$, $\ldots ,v_j^{(l_j)}$ and $S_{{v_i^{(l_i)}} ,{v_j^{(l_{j_1})}}+{v_j^{(l_{j_2})}}}$ is the subset cover generated by the chain $v_i^{(l_i)}$, $v_{i+1}^{(l_{i+1})}$, $\ldots ,v_j^{(l_{j_1})};v_j^{(l_{j_2})}$, where $v_j^{(l_{j_1})};v_j^{(l_{j_2})}$ are siblings.

We assign node identity $I_i^{(l_i)}\in \mathbb {Z}_n$ to each level i node ${v_i^{(l_i)}}$, where $1 \le i \le \log _3N+1,1\le l_i\le 3^{i-1}$. At level i, the hierarchial identity of a node ${v_i^{(l_i)}}$ is ${\textsf {ID}}|_{v_i^{(l_i)}}=(I_1^{(l_1)},I_2^{(l_2)},\ldots ,I_i^{(l_i)})\in ({\mathbb Z}_n)^{i}$, where $I_1^{(l_1)},I_2^{(l_2)},\ldots ,I_i^{(l_i)}$ are the identities of nodes in the path from the root $v_1^{(1)}$ to node ${v_i^{(l_i)}}$. All the nodes in the same level are assigned different hierarchial identities.

Definition 5

Let the node $v_j^{(l_j)}$ be in the subtree $T_{v_i^{(l_i)}}$ rooted at $v_i^{(l_i)}$ and the hierarchial identity of the node $v_j^{(l_j)}$ be $(I_1^{(l_1)},I_2^{(l_2)},\ldots ,I_j^{(l_j)})$. The modified hierarchial identity of a node $v_j^{(l_j)}$ in $T_{v_i^{(l_i)}}$ is defined to be $(I_i^{(l_i)},I_{i+1}^{(l_{i+1})},\ldots ,I_j^{(l_j)})$, i.e., the hierarchial identity from i-th position to rest in ${\textsf {ID}}|_{v_j^{(l_j)}}$.

Cover finding Algorithm Cover finding Algorithm FindCover invokes procedure FindChain to generate chain corresponding to a given set R of revoked users and partitions the subscribed users into collection of disjoint subset covers. Different subset covers are generated from different chains. Algorithm  2 formally describes FindCover.

Lemma 1

The cover size for ternary SD is at most min{$\frac{N}{3},N-r,2r-1$}, where N is maximum number of users, r is number of revoked users.

Proof

For each chain $v_i^{(l_i)}$, $v_{i+1}^{(l_{i+1})}$, $\ldots ,v_j^{(l_j)}$ or $v_i^{(l_i)}$, $v_{i+1}^{(l_{i+1})}$,$\ldots ,v_j^{(l_{j_1})};v_j^{(l_{j_2})},$ parent($v_{i}^{(l_i)}$) is either the root node or a node with 2 or 3 children in ${\textsf {ST}}(R)$. We define $v_i^{(l_i)}$ as the head node. If b is the number of children of parent of a head node and r is the number of revoked users in ${\textsf {ST}}(R)$, then the maximum number of parent node is given by $\frac{r}{b}$ as each child belongs to a chain which contain at least one revoked user. Thus the number of chain at most $b\frac{r}{b}$. As each chain provides one subset cover, the number of cover is $b\frac{r}{b}$. Head of these chain will be new revoked users. This provides the maximum number of parent node to be $\frac{r}{b^2}$ as each branch from parent will contain at least one of the previous $\frac{r}{b}$ parent node (head of new revoked users). This generates cover size at most $b\frac{r}{b^2}$. Continue upto x th stage where $b^x=r$. So, we have an upper bound of the total number of subset cover as $b\frac{r}{b}+b\frac{r}{b^2}+\ldots +b\frac{r}{b^x}(b^x=r)=b(\frac{r}{b} +\frac{r}{b^2}+\ldots +\frac{r}{b^x}) =b\frac{r-1}{b-1}.$ The root is an additional head vertex which provides one more to the cover, so total number of cover becomes $b\frac{r-1}{b-1}+1$. This takes the maximum value at $b=2$ and the value is $2r-1$.

In terms of the total number of users N, the number of subsets will be at most $\frac{N}{3}$. This happens when all the subscribed users are covered by ternary tree of height 1. Again there are $N-r$ subscribers and cover partition subscribers into groups. Therefore cover size should not exceed $N-r$. So, cover size = min$\{\frac{N}{3},N-r,2r-1$}. $\square$

Example

Fig. 4

Steiner Tree ${\textsf {ST}}(R)$ for Fig.  3 where $R=\{v_{4}^{(2)},v_{4}^{(3)},v_{4}^{(10)}\}$

We illustrate below the working of FindCover algorithm for the set of revoked users $R=\{v_{4}^{(2)},v_{4}^{(3)},v_{4}^{(10)}\}$. In Figure  3, ${\textsf {PN}}(v_{4}^{(16)})=\{v_1^{(1)},v_2^{(2)},v_{3}^{(6)},v_4^{(16)}\}$ and ${\textsf {HN}}(v_{4}^{(16)})=\{v_2^{(1)},v_2^{(3)},v_3^{(4)},v_{3}^{(5)},$ $v_{4}^{(17)},v_{4}^{(18)}\}$. For the set of revoked users $R=\{v_{4}^{(2)},v_{4}^{(3)},v_{4}^{(10)}\}$, the Steiner tree ${\textsf {ST}}(R)$ is depicted in Fig.  4. The Cover with respect to R is determined as follows:

• (i) The chain $C_1$ corresponding to the revoked user $v_{4}^{(2)}$ (or $v_{4}^{(3)}$) is $v_2^{(1)},v_3^{(1)},v_{4}^{(2)};v_{4}^{(3)}$, yielding the subset cover $S_{v_2^{(1)},v_4^{(2)}+v_4^{(3)}}$.

• (ii) The chain $C_2$ corresponding to the revoked user $v_4^{(10)}$ is $v_2^{(2)},v_3^{(4)},v_4^{(10)}$, yielding the subset cover $S_{v_2^{(2)},v_4^{(10)}}$.

• (iii) The head nodes $v_2^{(1)}$ and $v_2^{(2)}$ of the chains $C_1,C_2$ are then added to R. The nodes $v_4^{(2)},v_4^{(3)},v_4^{(10)}$ are removed from R and the chain corresponding to $v_2^{(1)}$ (or $v_2^{(2)}$) is $v_1^{(1)},v_2^{(1)};v_2^{(2)}$, yielding the set $S_{v_1^{(1)},v_2^{(1)}+v_2^{(2)}}$.

• (iv) Hence, Cover = $S_{v_2^{(1)},v_4^{(2)}+v_4^{(3)}} \cup S_{v_2^{(2)},v_4^{(10)}}$ $\cup$ $S_{v_1^{(1)} ,v_2^{(1)}+v_2^{(2)}}$.

Note that Cover is essentially a partition of the set of subscribed users into collection of disjoint subsets

$$\begin{aligned} S_{v_2^{(1)},v_4^{(2)}+v_4^{(3)}}= & {} \left\{ v_{4}^{(1)},v_{4}^{(4)},v_{4}^{(5)},v_{4}^{(6)},v_{4}^{(7)},v_{4}^{(8)},v_{4}^{(9)} \right\} ,\\ S_{v_2^{(2)},v_4^{(10)}}= & {} \left\{ v_{4}^{(11)},v_{4}^{(12)},v_{4}^{(13)},v_{4}^{(14)},v_{4}^{(15)},v_{4}^{(16)},v_{4}^{(17)},v_{4}^{(18)}\right\} , \\ S_{v_1^{(1)},v_2^{(1)}+v_2^{(2)}}= & {} \left\{ v_{4}^{(19)},v_{4}^{(20)},v_{4}^{(21)},v_{4}^{(22)},v_{4}^{(23)},v_{4}^{(24)},v_{4}^{(25)},v_{4}^{(26)},v_{4}^{(27)} \right\} . \end{aligned}$$

4 Constructions

4.1 PKBE

Our public key broadcast encryption scheme PKBE= (Setup, KeyGeneration, Encrypt, Decrypt) enables a broadcaster to broadcast a message to a set of N users placed at the leaves of a complete ternary tree T. Let L be the level of the leaf nodes. The ${\textsf { Setup}}$ and ${\textsf {Key Generation}}$ algorithms are run by a trusted third party, called the Private Key Generation Center (PKGC), ${\textsf {Encrypt}}$ algorithm is invoked by the broadcaster and ${\textsf {Decrypt}}$ algorithm is carried out by the subscribed users. Formal description of these algorithms are provided in Algorithm 3–6.

High-level description Using the Setup algorithm, the PKGC generates the public and the master key. The PKGC keeps the master key private to itself and publishes the public key. A user at a leaf node receives the secret keys corresponding to all hanging node with respect to each path node from the PKGC by KeyGeneration algorithm through a secure communication channel between the PKGC and the subscribed user. The broadcaster runs FindCover procedure in Algorithm 2 and generates Cover (a partition of the subscribed users into disjoint subsets with respect to the set of revoked users). The KeyGeneration algorithm has a subroutine Derive which has 2 parts delegation and re-randomization. Delegation procedure helps to compute secret key of children using the secret key of its parent. Re-randomization helps to randomize the computed secret key. The broadcaster invokes ${\textsf {Encrypt}}$ algorithm and forms the ciphertext components for each subset in Cover. The subscribed user u recovers the message from ciphertext components using the corresponding secret key.

Observe that public key and master key both are of size O(L).

KeyGeneration algorithm (Algorithm 4) works as follows:

The PKGC generates the secret keys for all nodes in ${\textsf {HN}}(v_L^{(l_L)})$ with respect to each node in ${\textsf {PN}}(v_L^{(l_L)})$ and issues these keys to the subscribed user u at $v_L^{(l_L)}$. Let $sk_{u,v_i^{(l_i)},v_j^{(l_j)}}$ denotes the secret key of the user u with respect to $v_j^{(l_j)}\in {\textsf {HN}}(v_L^{(l_L)})$, $v_i^{(l_i)}\in {\textsf {PN}}(v_L^{(l_L)})$, which corresponds to the identities $(I_i^{(l_i)},\ldots ,I_{j-1}^{(l_{j-1})},$ $I_{j}^{(l_{j})})$. Let $sk_{u,v_i^{(l_i)},v_j^{(l_{j_1})}+v_j^{(l_{j_2})}}$ be the secret keys of the user u corresponding to the identities $(I_i^{(l_i)},\ldots ,I_{j-1}^{(l_{j-1})},$ $I_{j}^{(l_{j_1})}+I_{j}^{(l_{j_2})})$. Consider level 1 node $v_{1}^{({1})} \in {\textsf {PN}}(v_L^{(l_L)})$. The PKGC uses step 2(a)i$\rangle$ of Algorithm 4 to assign the secret keys corresponding to the nodes which are children of $v_1^{(1)}$. In this process, it gets the secret key of $v_{2}^{(l_{2})} \in {\textsf {PN}}(v_L^{(l_L)})$. The PKGC uses 2(a)ii$\rangle$ to generate the combined secret key $sk_{u,v_1^{(1)},v_2^{(l_{j_1})}+v_2^{(l_{j_2})}}$, where $v_2^{(l_{j_1})}, v_2^{(l_{j_2})}\in {\textsf {HN}}(v_L^{(l_L)})$. The PKGC uses Derive algorithm to derive the secret keys for nodes in ${\textsf {HN}}(v_L^{(l_L)})$, that are not children of the initial path node $v_{1}^{({1})} \in {\textsf {PN}}(v_L^{(l_L)})$. For example, the PKGC uses the secret key of $v_{2}^{(l_2)}$ to derive the secret keys for the children of $v_2^{(l_2)}$ (as in step 2(b)i$\rangle$ of Algorithm 4). In this process, it gets secret key of $v_{3}^{(l_{3})}\in {\textsf {PN}}(v_L^{(l_L)})$. It uses 2(b)ii$\rangle$ to generate the third level combined secret key of the form $sk_{u,v_1^{(1)},v_3^{(l_{j_1})}+v_3^{(l_{j_2})}}$, where $v_3^{(l_{j_1})}, v_3^{(l_{j_2})}\in {\textsf {HN}}(v_L^{(l_L)})$. The PKGC uses the secret key of $v_{3}^{(l_{3})}\in {\textsf {PN}}(v_L^{(l_L)})$ to derive secret keys for the children of $v_3^{(l_3)}$ and continue up to level L-1 to obtain the secret key at leaf level. Next, consider level 2 node $v_{2}^{(l_{2})} \in {\textsf {PN}}(v_L^{(l_L)})$ and repeat the above process. Continue upto L-1 level node $v_{L-1}^{(l_{L-1})}\in {\textsf {PN}}(v_L^{(l_L)})$. Finally, the user u at $v_L^{(l_L)}$ is issued the secret keys corresponding to all nodes in ${\textsf {HN}}(v_L^{(l_L)})$ with respect to all nodes in ${\textsf {PN}}(v_L^{(l_L)})$. The secret keys of user u is $sk_u= \{ sk_{u,v_i^{(l_i)},v_j^{(l_{j_1})}}, sk_{u,v_i^{(l_i)},v_j^{(l_{j_2})}}, sk_{u,v_i^{(l_i)},v_j^{(l_{j_1})}+v_j^{(l_{j_2})}}| 1\le i\le L-1,i+1\le j \le L,v_i^{(l_i)}\in {\textsf {PN}}(v_L^{(l_L)}),v_j^{(l_{j_1})},v_j^{(l_{j_2})}\in {\textsf {HN}}(v_L^{(l_L)}) \}$. As an example, in Fig.  3, user at $v_4^{(16)}$, will receive the secret key $sk_u= \Big \{\{sk_{u,v_1^{(1)},v_2^{(x)}}| v_2^{(x)}=v_2^{(1)},v_2^{(3)},v_2^{(1)}+v_2^{(3)}\},\{sk_{u,v_1^{(1)},v_3^{(y)}}|v_3^{(y)}=v_3^{(4)},v_3^{(5)},v_3^{(4)}+v_3^{(5)} \} , \{sk_{u,v_1^{(1)},v_4^{(z)}}|$ $v_4^{(z)}=v_4^{(17)},v_4^{(18)},v_4^{(17)}+v_4^{(18)}\}, \{sk_{u,v_2^{(2)},v_3^{(y)}}| v_3^{(y)}=v_3^{(4)},v_3^{(5)},v_3^{(4)}+v_3^{(5)}\} , \{sk_{u,v_2^{(2)},v_4^{(z)}}|v_4^{(z)} =v_4^{(17)},v_4^{(18)},v_4^{(17)}+v_4^{(18)}\},\{ sk_{u,v_3^{(6)},v_4^{(z)}}|v_4^{(z)}=v_4^{(17)},v_4^{(18)},v_4^{(17)}+v_4^{(18)}\}\Big \}.$

Secret key size The subscribed user at a leaf node gets the secret keys for all hanging node with respect to each path node. It gets 3 secret keys for height 1 path node, $3\cdot 2$ secret keys for height 2 path node, $3\cdot 3$ secret keys for height 3 path node and so on. Total number of secret keys of user u is given by $\sum\nolimits_{{k = 1}}^{{\log _{3} N}} {3i}$ = $O(\log {_3}^2 N)$. Derive algorithm is a subroutine of KeyGeneration algorithm and used to derive secret key of child using the secret key of its parent. We have discussed this algorithm in appendix.

In encryption phase, the broadcaster divides the subscribed users into disjoint partitions using Find Cover and generates ciphertext components for each part.

Remark

Broadcaster can take $Z_1=g_q^{r_1},Z_2=g_q^{r_2},Z_3=g_q^{r_3}, r_1,r_2,r_3\in _R{\mathbb {Z}}_n$. Components involving $Z_1,Z_2,Z_3$ are element of ${\mathbb {G}}$, so he can compute $Z_1,Z_2,Z_3$ on modulo n.

Ciphertext size Here ciphertext size = m, where m is the cover size.

Example

In Fig.  3, ${\textsf {PN}}(v_{4}^{(16)})=\{v_1^{(1)},v_2^{(2)},v_{3}^{(6)},v_4^{(16)}\}$ and ${\textsf {HN}}(v_{4}^{(16)})=\{v_2^{(1)},v_2^{(3)},v_3^{(4)},v_{3}^{(5)},$ $v_{4}^{(17)},v_{4}^{(18)}\}$, where the set of revoked user $R=\{v_{4}^{(2)},v_{4}^{(3)},v_{4}^{(10)}$}. The user u at $v_4^{(16)}$, has the secret key $sk_u= \Big \{\{sk_{u,v_1^{(1)},v_2^{(x)}}| v_2^{(x)}=v_2^{(1)},v_2^{(3)},v_2^{(1)}+v_2^{(3)}\},\{sk_{u,v_1^{(1)},v_3^{(y)}}|v_3^{(y)}=v_3^{(4)},v_3^{(5)},v_3^{(4)}+v_3^{(5)} \} , \{sk_{u,v_1^{(1)},v_4^{(z)}}|$ $v_4^{(z)}=v_4^{(17)},v_4^{(18)},v_4^{(17)}+v_4^{(18)}\}, \{sk_{u,v_2^{(2)},v_3^{(y)}}| v_3^{(y)}= v_3^{(4)},v_3^{(5)},v_3^{(4)}+v_3^{(5)}\} , \{sk_{u,v_2^{(2)},v_4^{(z)}}|v_4^{(z)} =v_4^{(17)},v_4^{(18)},$ $v_4^{(17)}+v_4^{(18)}\},\{ sk_{u,v_3^{(6)},v_4^{(z)}}|v_4^{(z)}=v_4^{(17)},v_4^{(18)},v_4^{(17)}+v_4^{(18)}\}\Big \}.$ According to the Decrypt algorithm, the user will find cover $S_{v_1^{(1)},v_4^{(2)}+v_4^{(3)}}$, in which it belongs to. It will derive corresponding secret key $sk_{u,v_2^{(2)},v_4^{(10)}}$ and decrypt the ciphertext.

Correctnes: Using the fact that $e(h_p,h_q)=1, h_p\in {\mathbb G}_p,h_q\in {\mathbb G}_q,$ we show that ciphertext component $C_i=(\widehat{C}_1,\widehat{C}_2,\widehat{C}_3, \widehat{C}_4)$ generated for subset cover $S_{v_i^{(l_i)},v_j^{(l_j)}}$, will be decrypted using corresponding secret key $sk_{u,v_i^{(l_i)},v_j^{(l_j)}}$. Let $a_0,a_1,a_2$ are first 3 components of $sk_{u,v_i^{(l_i)},v_j^{(l_j)}}^{(d)}$ extracted from $sk_{u,v_i^{(l_i)},v_j^{(l_j)}}$. Hence,

$$\begin{aligned}&\widehat{C}_1 \frac{e(a_1,\widehat{C}_4)e(a_2,\widehat{C}_3)}{e(a_0,\widehat{C}_2)}\\= \,& {} M.E^s\frac{e\left( g^{r_1},(V.\prod _ {k=i}^{j}H_k^{I_k^{(l_k)}})^s.Z_3\right) . e(g^{r_2},F^s.Z_2)}{e\left( w.\left( v\prod _ {k=i}^{j}h_k^{I_k^{(l_k)}}\right) ^{r_1}f^{r_2},G^s.Z_1\right) }\\=\, & {} M.E^s\frac{e\left( g^{r_1},(V.\prod _ {k=i}^{j}H_k^{I_k^{(l_k)}})^s\right) . e(g^{r_1},Z_3).e(g^{r_2},f^s) .e(g^{r_2},{R_f}^s.Z_2)}{e\left( w.(v \prod _ {k=i}^{j}h_k^{I_k^{(l_k)}})^{r_1}f^{r_2},g^s\right) e(w.\left( v \prod _ {k=i}^{j}h_k^{I_k^{(l_k)}})^{r_1}f^{r_2},{R_g}^s.Z_1\right) }\\=\, & {} M.E^s\frac{e\left( g^{r_1},\left( v.\prod _ {k=i}^{j}h_k^{I_k^{(l_k)}}\right) ^s\right) . e(g^{r_2},f^s)}{e(w.(v \prod _ {k=i}^{j}h_k^{I_k^{(l_k)}})^{r_1}.f^{r_2},g^s)}\\= \,& {} (M).E^s\frac{e\left( g^{r_1},\left( v.\prod _ {k=i}^{j}h_k^{I_k^{(l_k)}}\right) ^s\right) . e(g^{r_2},f^s)}{e\left( w.\left( v \prod _ {k=i}^{j}h_k^{I_k^{(l_k)}}\right) ^{r_1},g^s\right) e(f^{r_2},g^s)}\\=\, & {} M.E^s\frac{e\left( g^{r_1},\left( v.\prod _ {k=i}^{j}h_k^{I_k^{(l_k)}}\right) ^s\right) }{e\left( \left( v\prod _ {k=i}^{j}h_k^{I_k^{(l_k)}}\right) ^{r_1},g^s\right) e(w,g^s)}=M. \end{aligned}$$

Similarly, ciphertext component generated for the subset cover $S_{v_i^{(l_i)},v_j^{(l_{j_1})}+v_j^{(l_{j_2})}}$, can be decrypted by secret key $sk_{u,v_i^{(l_i)},v_j^{(l_{j_1})}+v_j^{(l_{j_2})}}$. In this case, $H_j^{I_j^{(l_j)}}$ is replaced by $H_j^{I_j^{(l_{j_1})}+I_j^{(l_{j_2})}}$.

Lemma 2

The scheme PKBE attains revocation property.

Proof

When a user u at $v_L^{(l_L)}$ gets revoked, the cover changes. Let $v_L^{(l_L)}\in$ $T_{v_i^{(l_i)}}\setminus S_{{v_i^{(l_i)}} ,{v_j^{(l_j)}}}$. Then $v_i^{(l_i)}$ will be ancestor of the node $v_L^{(l_L)}$ and $v_j^{(l_j)}$ will either itself be $v_L^{(l_L)}$ or will be an ancestor of $v_L^{(l_L)}$. If $v_j^{(l_j)}$ is not an ancestor of $v_L^{(l_L)}$, then $v_L^{(l_L)}$ cannot be a revoked user as in $S_{v_i^{(l_i)},v_j^{(l_j)}}$, users at the leaf of the complete subtree rooted at $v_j^{(l_j)}$ are the revoked users. Thus both $v_i^{(l_i)},v_j^{(l_j)}\in {\textsf {PN}}(v_L^{(l_L)})$. As the user has the secret keys $sk_{u,v_i^{(l_i)},v_j^{(l_j)}}$, where $v_j^{(l_j)}\in {\textsf {HN}}(v_L^{(l_L)})$, it will be unable to recover the message from the ciphertext generated corresponding to new Cover. $\square$

Lemma  2 shows that users who have not subscribed (i.e., revoked users) should not be able to recover the message. It is true for any number of revoked users thus independent of cover size. Hence independent of communication bandwidth and computation cost.

Example

In Fig.  3, $R=\{v_4^{(2)}, v_4^{(3)}, v_4^{(10)}\}$ is the set of revoked users. Revoked user $v_4^{(10)}$ has secret key $sk_u= \Big \{\{sk_{u,v_1^{(1)},v_2^{(x)}}| v_2^{(x)}=v_2^{(1)},v_2^{(3)},v_2^{(1)}+v_2^{(3)}\},\{sk_{u,v_1^{(1)},v_3^{(y)}}|v_3^{(y)}=v_3^{(6)},v_3^{(5)}, v_3^{(6)}+v_3^{(5)} \} , \{sk_{u,v_1^{(1)},v_4^{(z)}}|$ $v_4^{(z)}=v_4^{(11)},v_4^{(12)},v_4^{(11)}+v_4^{(12)}\}, \{sk_{u,v_2^{(2)},v_3^{(y)}}| v_3^{(y)}=v_3^{(6)},v_3^{(5)},v_3^{(6)}+v_3^{(5)}\} , \{sk_{u,v_2^{(2)},v_4^{(z)}}|$ $v_4^{(z)} =v_4^{(11)},v_4^{(12)},v_4^{(11)}+v_4^{(12)}\}, \{sk_{u,v_3^{(4)},v_4^{(z)}}|v_4^{(z)}=v_4^{(11)},v_4^{(12)},v_4^{(11)}+v_4^{(12)}\}\Big \}.$ The set of revoked users $R=\{v_4^{(2)}, v_4^{(3)}, v_4^{(10)}\}$ generates subset difference Cover = $S_{v_2^{(1)},v_4^{(2)}+v_4^{(3)}} \cup S_{v_2^{(2)},v_4^{(10)}}$ $\cup$ $S_{v_1^{(1)} ,v_2^{(1)}+v_2^{(2)}}$. Secret key required for decryption are $sk_{u,v_2^{(1)},v_4^{(2)}+v_4^{(3)}} ,sk_{u,v_2^{(2)},v_4^{(10)}}$ $,sk_{u,v_1^{(1)} ,v_2^{(1)}+v_2^{(2)}}$ respectively. ${\textsf {Derive}}$ algorithm (see Appendix) only helps to derive secret key of child using the secret key of its parent. As the revoked user does not have decryption key corresponding to the ciphertext components, will not able to recover the message.

$\bullet$ Security analysis

Theorem 1

The construction PKBE achieves selective semantic security under L-wDBDHI* assumptions.

Proof

Let there is an adversary ${\mathcal {A}}$ that can distinguish win the game with an advantage $\epsilon$. We show that ${\mathcal {C}}$ can solve L-wDBDHI* problem with advantage $\epsilon$. Challenger ${\mathcal {C}}$ has input L-wDBDHI* instance $Z=({\mathbb {S}},h,g_q,g_p,g_p^\alpha ,\ldots ,g_p^{\alpha ^L}),T$, where $h \in _R {\mathbb {G}}_p, \alpha \in _R {\mathbb {Z}}_n,T\in _R {\mathbb {G}}_{T,p}$, ${\mathbb {S}}=(n,{\mathbb {G}},{\mathbb {G}}_T, e$).

• 1. Initialization: ${\mathcal {A}}$ submits the challenge revoked sets ${\mathbb {R}}$ to ${\mathcal {C}}$.

• 2. Setup: ${\mathcal {C}}$ chooses $\gamma , x,y,z,x_1,\ldots ,x_L \in _R {\mathbb {Z}}_n$ and $R_g,R_f,R_v,R_{h,1},\ldots ,R_{h,L}\in _R {\mathbb {G}}_q$. Let us consider a cover $S_{{v_i^{(\bar{l}_i)}} ,{v_j^{(\bar{l}_j)}}}$ generated by the chain $({v_i^{(\bar{l}_i)}},{v_{i+1}^{(\bar{l}_{i+1})}},\ldots ,{v_j^{(\bar{l}_j)}})$, using the revoked set ${\mathbb {R}}_0$. Let modified hierarchial identity of the end node ${v_j^{(\bar{l}_j)}}$ with respect to the head node ${v_i^{(\bar{l}_i)}}$ as

  $$\begin{aligned}&\left( 0,\ldots ,0,{I_i^{(\bar{l}_i)}},{I_{i+1}^{(\bar{l}_{i+1})}},\ldots ,{I_j^{(\bar{l}_j)}},0,\ldots ,0\right) \\= & {} \left( {I_1^{(\bar{l}_1)}},{I_2^{(\bar{l}_2)}},\ldots ,{I_L^{(\bar{l}_L)}}\right) . \end{aligned}$$

  So, some ${I_k^{(\bar{l}_k)}}$ may be 0 at the beginning and end. Compute $G=g_p.R_g, F=g_p^z.R_f, V=g_p^y.\displaystyle \prod _{k=1}^{L}({A_{L-k+1}})^{I_k^{(\bar{l}_k)}} R_v,H_k=g_p^{x_k}/A_{L-k+1} R_{h,k}~ (1\le k \le L)$, $E=e(A_1,A_Lg_p^{\gamma })$, where $A_k=g_p^{{\alpha }^k}$. Set public key as ${\textsf {PK}}=(g_p,g_q,G,F,V,H_1,\ldots ,H_L,E,N,{\mathbb {S}})$ and $w={(A_{L}g_p^{\gamma })}^{\alpha }=A_{L+1}A_1^{\gamma }$. Challenger does not have $A_{L+1}$, so he cannot compute w explicitly.

• 3. Phase 1: Let ${\mathcal {A}}$ wants to get secret keys for revoked user $i\in {\mathbb {R}}$. Let i be in $T_{{v_j^{(l_j)}}}$ of cover $S_{{v_i^{(l_i)}} ,{v_j^{(l_j)}}}$ and it queries for a secret key component corresponding to modified hierarchial identity $({{I_1^{(l_1)}}}^*,{I_2^{(l_2)}}^*,\ldots ,{I_L^{(l_L)}}^*)$. Let s be the least identity such that ${I_s^{(\bar{l}_s)}}\ne {I_s^{(l_s)}}^*$.

  i.:

  Take $r_1,r_2 \in _R {\mathbb {Z}}_n$ and implicitly set $\overline{r}_1=r_1+\frac{\alpha ^s}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}}}$. Secret key $g,f,v,h_1,\ldots ,h_L$ can be obtained by removing the blinding factors $R_g,R_f,R_v,R_{h,1},\ldots ,R_{h,L}$ from $G,F,V,H_1,\ldots ,H_L$ respectively.

  ii.:

  Next, ${\mathcal {C}}$ tries to compute

  $$\begin{aligned} w.\left( v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*}\right) ^{\overline{r}_1} f^{r_2}=w.\left( v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*}\right) ^{{r_1}} f^{r_2}.\left( v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*}\right) ^\frac{\alpha ^s}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}}}. \end{aligned}$$

  Using secret keys $v,h_k ~(1\le k\le s), f$ and public value ${I_k^{(l_k)}}^*$ $(1\le k\le s)$, $(v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*})^{{r_1}} f^{r_2}$ is computable. Now,

  $$\begin{aligned}&w.\left( v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*}\right) ^\frac{\alpha ^s}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}}}\\= \,& {} A_{L+1}A_1^{\gamma }\left( g_p^y.\prod _{k=1}^{L}({A_{L-k+1}})^{I_k^{(\bar{l}_k)}}\displaystyle \prod _ {k=1}^{s} {(g_p^{x_k}/A_{L-k+1})}^{{I_k^{(l_k)}}^*}\right) ^\frac{\alpha ^s}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}}}\\= \,& {} A_{L+1}A_1^{\gamma }\left( {A_{L+1}}^{ {I_s^{(\bar{l}_s)}}-{I_s^{(l_s)}}^*}.A_s^y.\prod _{k=s+1}^{L}{(A_{L+s-k+1})}^{I_k^{(\bar{l}_k)}}\displaystyle \prod _ {k=1}^{s} A_s^{x_k.{I_k^{(l_k)}}^{*}}\right) ^\frac{1}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}} }\\= \,& {} A_1^{\gamma }\left( A_s^y.\prod _{k=s+1}^{L}{(A_{L+s-k+1})}^{I_k^{(\bar{l}_k)}}\displaystyle \prod _ {k=1}^{s} A_s^{x_k.{I_k^{(l_k)}}^*}\right) ^\frac{1}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}}}. \end{aligned}$$

  As $A_k,{ I_k^{(l_k)}}^*,x_k$ values are available, $w.(v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*})^\frac{\alpha ^s}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}}}$ is computable, so $w.(v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*})^{\overline{r}_1}.$ $f^{r_2}$ is also computable.

  iii.:

  Now using Derive algorithm as stated in Algorithm 9, ${\mathcal {C}}$ computes first component of $sk_{i,v_i^{(l_i)},v_j^{(l_j)}}^{(d)}$ as $w.(v\displaystyle \prod _ {k=1}^{j} h_k^{{I_k^{(l_k)}}^*})^{\overline{r}_1} f^{r_2}$. Other components $(g^{\overline{r}_1},g^{r_2},h_{j+1}^{\overline{r}_1},\ldots ,h_L^{\overline{r}_1})$ of $sk_{i,v_i^{(l_i)},v_j^{(l_j)}}^{(d)}$ are easily computable using secret key components.

  iv.:

  Challenger need to choose $s_1^{(1)},s_2^{(1)},s_1^{(2)},s_2^{(2)}\in _R {\mathbb {Z}}_n$ such that $s_1^{(1)}s_2^{(2)}-s_2^{(1)}s_1^{(2)}\not \equiv 0 \pmod q$, $s_1^{(1)}s_2^{(2)}-s_2^{(1)}s_1^{(2)}\not \equiv 0 \pmod p$, for this it check the equation $g_p^{s_1^{(1)}s_2^{(2)}-s_2^{(1)}s_1^{(2)}}\not \equiv 1$ and $g_q^{s_1^{(1)}s_2^{(2)}-s_2^{(1)}s_1^{(2)}}$ $\not \equiv 1$. Components of $sk_{i,v_i^{(l_i)},v_j^{(l_j)}}^{(r)}$ are almost same with $sk_{i,v_i^{(l_i)},v_j^{(l_j)}}^{(d)}$ except first component does not contain w. So, $\mathcal {C}$ computes $sk_{i,v_i^{(l_i)},v_j^{(l_j)}}^{(r)}$ as previous. Similarly, it can generate secret key $sk_{i,v_i^{(l_i)},v_j^{(l_{j_1})}+v_j^{(l_{j_2})}}$.

  v.:

  Adversary gets $sk_i= \{ sk_{i,v_i^{(l_i)},v_j^{(l_{j_1})}}, sk_{i,v_i^{(l_i)},v_j^{(l_{j_2})}}, sk_{i,v_i^{(l_i)},v_j^{(l_{j_1})}+v_j^{(l_{j_2})}}\}$, where user i is at $v_L^{(l_L)}$ and $v_i^{(l_i)}\in {\textsf {PN}}(v_L^{(l_L)}),v_j^{(l_{j_1})},v_j^{(l_{j_2})}\in {\textsf {HN}}(v_L^{(l_L)})$.

• 4. Challenge: ${\mathcal {A}}$ sends two messages $m_0, m_1$ to ${\mathcal {C}}$. ${\mathcal {C}}$ computes ciphertext components $\{C_{1},\ldots ,C_{l_0}\}$ following Algorithm 5 as follows.

  $$\begin{aligned} C_i= & {} \left( m_0.T.e(A_1,h^{\gamma }), h.Z_1, h^z.Z_2, h^{y+\sum _{k=1}^{L} { I_k^{(l_k)}. x_k}}.Z_3 \right) ,\\&1\le i \le l_0\\&{\text {where~}} Z_1,Z_2,Z_3\in _R {\mathbb {G}}_q, s\in _R {\mathbb {Z}}_n, T \in _R {\mathbb {G}}_{T,p}. \end{aligned}$$

  ${\mathcal {C}}$ sends ciphertext $\{C_{1},\ldots ,C_{l_0}\}$ to ${\mathcal {A}}.$ As $g_p$ is generator for ${\mathbb {G}}_p$, let us consider $h={g_p}^c$, for some integer c. If $T=e(g_p,{g_p}^c)^{\alpha ^{L+1}}$ then ciphertext component

  $$\begin{aligned} C_{i}= & {} \Big (m_0. e(g_p,{g_p}^c)^{\alpha ^{L+1}}. e(A_1, h^{\gamma }),\\&h.Z_1, h^z.Z_2, h^{y+\sum _{k=1}^{L} { I_k^{(l_k)}. x_k}}.Z_3\Big )\\&{\text {where~}} Z_1,Z_2,Z_3\in {\mathbb {G}}_q.\\= & {} \Big (m_0.E^c, G^c.Z_1', F^c.Z_2',(V\displaystyle \prod _{k=1}^{L} {H_k}^{I_k^{(l_k)}})^{c}.Z_3' \Big ) \end{aligned}$$

  This implies, if $T=e(g_p,{g_p}^c)^{\alpha ^{L+1}}$ then ciphertext $\{C_{1},\ldots ,C_{l_0}\}$ is identical with original.

• 5. Phase 2: Same as Phase 1.

• 6. Guess: ${\mathcal {A}}$ predicts $b'$ for b and wins the game if $b'=b$.

Adversary’s advantage of winning the game is same as deciding $T=e(g_p,{g_p}^c)^{\alpha ^{L+1}}$ or not, i.e., solving L-wDBDHI* problem. $\square$

4.2 OAnoBE

In this section, we will discuss our outsider anonymous broadcast encryption scheme OAnoBE which is an extension of our PKBE. In PKBE each user gets a set of keys. The keys are helpful to recover secret key corresponding to the subset cover in which it belongs. Thus a user can try to decrypt the ciphertext by using the possible subset cover in which it belongs without knowing the set of subscribers or revoked users. Hence PKBE can be extended to develop an anonymous construction, namely OAnoBE. OAnoBE works similar to PKBE, except encryption and decryption. We will explain these two algorithms as follows:

The encryption algorithm works as follows: The broadcaster encrypts $M\Vert K$ instead of M in encryption algorithm. Here K is the verification component. It computes l components where components $\{C_x\}_{x=m+1}^{l}$ are random and $\{C_x\}_{x=1}^{m}$ are same as PKBE. Here l is the theoretical upper bound of cover size and m is cover size. The detail description as follows:

Remark

Broadcaster can take $Z_1=g_q^{r_1},Z_2=g_q^{r_2},Z_3=g_q^{r_3}, r_1,r_2,r_3\in _R{\mathbb {Z}}_n$. Components involving $Z_1,Z_2,Z_3$ are element of ${\mathbb {G}}$, so he can compute $Z_1,Z_2,Z_3$ on modulo n.

Ciphertext size Here ciphertext size = l=$\hbox {min}\{\frac{N}{3},N-r, 2r-1\}$.

The broadcaster invokes ${\textsf {Encrypt}}$ algorithm and forms the ciphertext components for each subset in Cover. To preserve the anonymity, the broadcaster also generates $(l-|Cover|)$ many dummy ciphertext components, where l is theoretical bound of cover size. The decryption algorithm works as follows:

Decryption attempt To recover the message using Decrypt algorithm, user u tries to decrypt $\{C_i\}_{i=1}^{l}$ values with secret key corresponds to all possible subsets in which it can belong to. For height k, there are at most $2\cdot 3$ subsets of depth 1, $2\cdot 3^2$ of depth 2 and so on. So, total $2\cdot 3+2\cdot 3^2+\cdots +2\cdot 3^k$ subsets. But, the user does not belong to 3k subsets of the form $S_{{v_i^{(l_i)}}, {v_j^{(l_j)}}}$,$S_{{v_i^{(l_i)}} ,{v_j^{(l_j)}+v_j^{(l_j')}}}$, where $v_j^{(l_j)}$ lies on the path joining the user and the root. So, for height k, the user can belong to $2\cdot 3+2\cdot 3^2+\cdots +2\cdot 3^k -3k=3\cdot (3^k-1)-3k\le 3^{k+1}-3k$ subset difference sets. This gives the maximum number of subsets in which it can belong, is $\displaystyle \sum _{k=1}^{\log _3N}(3^{k+1}-3k)=O(N)$. The user generates or derive secret keys for each subsets and decrypt l ciphertext components one by one until it recover message M. So, total number of decryption attempt is O(Nl).

Example

In Fig.  3, ${\textsf {PN}}(v_{4}^{(16)})=\{v_1^{(1)},v_2^{(2)},v_{3}^{(6)},v_4^{(16)}\}$ and ${\textsf {HN}}(v_{4}^{(16)})=\{v_2^{(1)},v_2^{(3)},v_3^{(4)},v_{3}^{(5)},$ $v_{4}^{(17)},v_{4}^{(18)}\}$, where the set of revoked user $R=\{v_{4}^{(2)},v_{4}^{(3)},v_{4}^{(10)}$}. The user u at $v_4^{(16)}$, has the secret key $sk_u= \Big \{\{sk_{u,v_1^{(1)},v_2^{(x)}}| v_2^{(x)}=v_2^{(1)},v_2^{(3)},v_2^{(1)}+v_2^{(3)}\}, \{sk_{u,v_1^{(1)},v_3^{(y)}}|v_3^{(y)}=v_3^{(4)},v_3^{(5)},v_3^{(4)}+v_3^{(5)} \} , \{sk_{u,v_1^{(1)},v_4^{(z)}}|$ $v_4^{(z)}=v_4^{(17)},v_4^{(18)},v_4^{(17)}+v_4^{(18)}\}, \{sk_{u,v_2^{(2)},v_3^{(y)}}| v_3^{(y)}=v_3^{(4)},v_3^{(5)},v_3^{(4)}+v_3^{(5)}\} , \{sk_{u,v_2^{(2)},v_4^{(z)}}|v_4^{(z)}$ $=v_4^{(17)},v_4^{(18)},$ $v_4^{(17)}+v_4^{(18)}\},\{sk_{u,v_3^{(6)},v_4^{(z)}}|v_4^{(z)}=v_4^{(17)},v_4^{(18)},v_4^{(17)}+v_4^{(18)}\}\Big \}.$ According to the Decrypt algorithm, the user will try to decrypt the ciphertext using the secret keys $sk_{u,v_1^{(1)},v_2^{(1)}+v_2^{(3)}}$, $sk_{u,v_1^{(1)},v_2^{(1)}}$ respectively and will fail to recover the message as no ciphertext components corresponding to the subset cover $S_{v_1^{(1)},J},J=v_2^{(1)}, v_2^{(1)}+v_2^{(3)}$. If user has the secret key $sk_{u,v_i^{(l_i)},v_{j-1}^{(l_{j-1})}}$ for $(I_i^{(l_i)},\ldots ,I_{j-1}^{(l_{j-1})})$, then it can compute the secretkeys $sk_{u,v_i^{(l_i)},v_j^{(l_j)}},$ $sk_{u,v_i^{(l_i)},v_j^{(l_{j_1})}+v_j^{(l_{j_2})}}$ for $(I_i^{(l_i)},\ldots ,I_{j-1}^{(l_{j-1})}$ $,I_{j}^{(l_{j})})$, $(I_i^{(l_i)},\ldots ,I_{j-1}^{(l_{j-1})},I_{j}^{(l_{j_1})}+I_{j}^{(l_{j_2})})$ by the delegation mechanism of Derive. Using this mechanism, subscribed user u will compute the following 3-rd level keys which belong to $T_{v_2^{(1)}}$: the individual secret keys $sk_{u,v_1^{(1)},v_3^{(1)}}$, $sk_{u,v_1^{(1)},v_3^{(2)}}$, $sk_{u,v_1^{(1)},v_3^{(3)}}$ and the combined secret keys $sk_{u,v_1^{(1)},v_3^{(1)}+v_3^{(2)}}$, $sk_{u,v_1^{(1)},v_3^{(2)}+v_3^{(3)}}$, $sk_{u,v_1^{(1)},v_3^{(1)}+v_3^{(3)}}$. User u will try with these keys and and fail to recover the message. User u will compute the following fourth level individual secret keys in $T_{v_2^{(1)}}$: $sk_{u,v_1^{(1)},v_4^{(1)}}$, $sk_{u,v_1^{(1)},v_4^{(2)}}$, $sk_{u,v_1^{(1)},v_4^{(3)}}$ and still be unable to recover the message. It succeeds with the combined secret key $sk_{u,v_1^{(1)},v_4^{(2)}+v_4^{(3)}}$ as there is a ciphertext component generated for $S_{v_1^{(1)},v_4^{(2)}+v_4^{(3)}}$.

• Security analysis The security works similar to the PKBE scheme. We explain the security in detail.

Theorem 2

The scheme OAnoBE scheme described in Sect.  4is selective secure against CPA under L-wDBDHI*, BSD and L-cDDH assumptions, where L is the level of leaf nodes.

Proof

We will organize the proof in a sequence of games: ${\textsf {Game}}_h^{0}$ $(0\le h < l_0)$,${\textsf {Game}}_{l_0}^0, {\textsf {Game}}_{l_1}^1$,$\textsf {Game}_k^{1}$ $(l_1 > k \ge 1)$ played between challenger ${\mathcal {C}}$ and adversary ${\mathcal {A}}$, where $l_i$, $(i=0,1)$ is the cover size generated for the revoked set ${\mathbb {R}}_i$. Let the i-th chain of ${\textsf {ST}}({\mathbb {R}}_0)$ contains nodes $({v_i^{(l_i)}},{v_{i+1}^{(l_{i+1})}},\ldots ,{v_j^{(l_j)}})$. As ${\mathbb {R}}_0$, ${\mathbb {R}}_1$ has equal number of revoked users, theoretical bound of cover size $l_1=l_2=l$ (say). Let $({I_i^{(l_i)}},{I_{i+1}^{(l_{i+1})}},\ldots ,$ ${I_j^{(l_j)}})$ be the modified hierarchial identity of the last node $v_j^{(l_j)}$ of i-th chain with respect to its head node $v_i^{(l_i)}$. If the i-th chain of ${\textsf {ST}}({\mathbb {R}}_0)$ contains nodes $({v_i^{(l_i)}},{v_{i+1}^{(l_{i+1})}},\ldots ,{v_j^{(l_{j_1})};}{v_j^{(l_{j_2})}})$, then the modified hierarchial identity is $({I_i^{(l_i)}},{I_{i+1}^{(l_{i+1})}},\ldots ,$ ${I_j^{(l_{j_1})}}+{I_j^{(l_{j_2})}}).$ Let

$$\begin{aligned} {\textsf {ID}}_{i,0}= & {} \left( 0,\ldots ,0,{I_i^{(l_i)}},{I_{i+1}^{(l_{i+1})}},\ldots ,{I_j^{(l_j)}},0, \ldots ,0\right) \\= & {} \left( {I_1^{(l_1)}},{I_2^{(l_2)}},\ldots ,{I_L^{(l_L)}}\right) . \end{aligned}$$

We start with the first game ${\textsf {Game}}_0^{0}$ where the challenger encrypts $m_0=(M_0||K)$ for the adversary’s challenge revoked set ${\mathbb {R}}_0$. We then gradually change the encryption through multiple games into encryption of $m_1=(M_1||K)$ for the revoked set ${\mathbb {R}}_1$. We show that each game is indistinguishable from its previous one. Thus showing our OAnoBE scheme to have selective security against CPA.

• ${\textsf {Game}}_h^{0}$ $(0\le h < l_0)$:

  • 1. Initialization: Adversary ${\mathcal {A}}$ sends the challenge sets ${\mathbb {R}}_0,{\mathbb {R}}_1$ to ${\mathcal {C}}$, where ${\mathbb {R}}_0,{\mathbb {R}}_1$ have equal number of revoked users.

  • 2. Setup: ${\mathcal {C}}$ runs $({\textsf {PK,MK}})\leftarrow {\textsf {Setup}}(N,\lambda )$. It keeps MK secret to itself and makes PK public.

  • 3. Phase 1: ${\mathcal {A}}$ takes an user $i \in \mathbb { R}_0 \cap \mathbb { R}_1$ and requests for the secret keys to ${\mathcal {C}}$. ${\mathcal {C}}$ generates the secret key $sk_i\leftarrow {\textsf {KeyGeneration(PK,MK}},i)$ and sends to ${\mathcal {A}}$.

  • 4. Challenge: ${\mathcal {A}}$ sends two equal length messages $m_0=(M_0||K),$ $m_1=(M_1||K)$, where last k bits of each message is K. ${\mathcal {C}}$ computes following ciphertext components: $C_i$, $1\le i \le l_0-h$ as encryption of $m_0$ for identity $\textsf {ID}_{i,0}$ and $C_i$, $l_0-h+1\le i \le l$ as $(R_1,R_2,R_3,R_4) \in _{R} {\mathbb {G}}_T \times {\mathbb {G}}^3$ following Algorithm 7. ${\mathcal {C}}$ permutes the $C_i$ values using some permutation $\mu$ and sends $\{k,K,C_{\mu (1)},\ldots ,C_{\mu (l)}\}$ to ${\mathcal {A}}.$

  • 5. Phase 2: Phase 2 is similar to Phase 1.

  • 6. Guess: ${\mathcal {A}}$ wins the game if he can predict $b=0$.

• ${\textsf {Game}}_{l_0}^0$: This game is similar to above except that challenge ciphertext component $C_i,1\le i\le l$ as $(R_1,R_2,R_3,R_4) \in _{R} {\mathbb {G}}_T \times {\mathbb {G}}^3$ following Algorithm  7. Let us now consider that the i-th chain of ${\textsf {ST}}({\mathbb {R}}_1)$ contains nodes $({v_i^{(l_i)}},{v_{i+1}^{(l_{i+1})}},\ldots ,{v_j^{(l_j)}})$ and $({I_i^{(l_i)}},{I_{i+1}^{(l_{i+1})}},$ $\ldots ,{I_j^{(l_j)}})$ be the modified hierarchial identity of the last node $v_j^{(l_j)}$ of this chain with respect to its head node $v_i^{(l_i)}$. Let ${\textsf {ID}}_{i,1}=(0,\ldots ,0,{I_i^{(l_i)}},{I_{i+1}^{l_{(i+1)}}},\ldots ,{I_j^{(l_j)}},0,\ldots ,0)=({I_1^{(l_1)}},{I_2^{(l_2)}},\ldots ,{I_L^{(l_L)}}).$

• ${\textsf {Game}}_{l_1}^1$: This game is identical to ${\textsf {Game}}_{l_0}^{0}$.

• ${\textsf {Game}}_k^{1}$ $(l_1 > k\ge 1)$: This game continues as in ${\textsf {Game}}_{l_1}^{1}$ except that the challenge ciphertext components. ${\mathcal {A}}$ sends two equal length messages $m_0=(M_0||K),m_1=(M_1||K)$. ${\mathcal {C}}$ computes following ciphertext components: $C_i$, $1\le i \le l_1-k$ as encryption of $m_1$ for identity $\textsf {ID}_{i,1}$ and $C_i$, $l_1-k+1\le i \le l$ as $(R_1,R_2,R_3,R_4) \in _{R} {\mathbb {G}}_T \times {\mathbb {G}}^3$ following Algorithm 7. ${\mathcal {C}}$ permutes the $C_i$ values using some permutation $\mu$ and sends $\{k,K,C_{\mu (1)},\ldots ,C_{\mu (l)}\}$ to ${\mathcal {A}}.$

We now present a sequence of lemmas which will demonstrate that no PPT adversary can distinguish with non-negligible advantage between any two consecutive game described above. In Lemma  3, we show that ${\textsf {Game}}_{h-1}^0$ and ${\textsf {Game}}_h^0$, $1\le h\le l_0$ are indistinguishable if L-wDBDHI*, BSD and L-cDDH assumption holds. ${\textsf {Game}}_{k-1}^1$ and ${\textsf {Game}}_k^1$, $2\le k\le l_1$ are indistinguishable by Lemma  4 under the same assumptions. Let the adversary’s advantage of winning ${\textsf {Game}}_h^0$ is ${\textsf {Adv}}_h^0$, and that of ${\textsf {Game}}_k^1$ is ${\textsf {Adv}}_k^1$. Let the adversary’s advantage of distinguishing ${\textsf {Game}}_h^0$, ${\textsf {Game}}_{h-1}^0$ and ${\textsf {Game}}_k^0$, ${\textsf {Game}}_{k-1}^0$ is at most $\epsilon$. Then advantage of distinguishing ${\textsf {Game}}_0^0$, ${\textsf {Game}}_1^1$ is given by

$$\begin{aligned} |{\textsf {Adv}}_{0}^0 -{\textsf {Adv}}_{1}^1|\le & {} \displaystyle \sum _{h=1}^{l_0} |{\textsf {Adv}}_{h-1}^0 -{\textsf {Adv}}_{h}^0|\nonumber \\&+|{\textsf {Adv}}_{l_0}^0 -{\textsf {Adv}}_{l_1}^1|+\displaystyle \sum _{k=2}^{l_1} |{\textsf {Adv}}_{k}^1-{\textsf {Adv}}_{k-1}^1|\nonumber \\\le & {} \epsilon (l_0+l_1)\le \epsilon (l+l)\le 2\epsilon (l). \end{aligned}$$

$\square$

Lemma 3

${\textsf {Game}}_{h-1}^0$ and ${\textsf {Game}}_h^0$ are indistinguishable under L-wDBDHI*, BSD and L-cDDH assumptions.

Proof

To prove the indistinguishability of ${\textsf {Game}}_{h-1}^0$ and ${\textsf {Game}}_h^0$, we define $\overline{\textsf {Game}}_h^0$ in slightly different way from ${\textsf {Game}}_h^0$ and prove the indistinguishability of $\overline{\textsf {Game}}_{h-1}^0$ and $\overline{\textsf {Game}}_h^0$. For $i = l_0-h+1$ to l, the generated challenged ciphertext in $\overline{{\textsf {{Game}}}}_h^0$ is of the form $(\widehat{C}_1.R_p,\widehat{C}_2,\widehat{C}_3,\widehat{C}_4)$ instead of $(R_1,R_2,R_3,R_4)\in _R\mathbb { G}_T\times {\mathbb {G}}^3$, where $(\widehat{C}_1,\widehat{C}_2,\widehat{C}_3,\widehat{C}_4)$ is the encryption of the message $m_0$ using ${\textsf {ID}}_{i,0}$ and $R_p\in _R {\mathbb {G}}_{T,p}$. Claim. $\overline{{\textsf {Game}}}_{h-1}^0$ and $\overline{{\textsf {Game}}}_{h}^0$ are indistinguishable under L-wDBDHI* assumptions.

Proof. Let there is an adversary ${\mathcal {A}}$ that can distinguish $\overline{{\textsf {Game}}}_{h-1}^0$ and $\overline{{\textsf {Game}}}_{h}^0$ with an advantage $\epsilon$. We show that ${\mathcal {C}}$ can solve L-wDBDHI* problem with advantage $\epsilon$. Challenger ${\mathcal {C}}$ has input L-wDBDHI* instance $Z=({\mathbb {S}},h,g_q,g_p,g_p^\alpha , \ldots ,g_p^{\alpha ^L}),T$, where $h \in _R {\mathbb {G}}_p, \alpha \in _R {\mathbb {Z}}_n,T\in _R {\mathbb {G}}_{T,p}$, ${\mathbb {S}}=(n,{\mathbb {G}},{\mathbb {G}}_T, e$).

• 1. Initialization: ${\mathcal {A}}$ submits the challenge revoked sets ${\mathbb {R}}_0,{\mathbb {R}}_1$ to ${\mathcal {C}}$, where ${\mathbb {R}}_0,{\mathbb {R}}_1$ has equal number of revoked users.

• 2. Setup: ${\mathcal {C}}$ chooses $\gamma , x,y,z,x_1,\ldots ,x_L \in _R {\mathbb {Z}}_n$ and $R_g,R_f,R_v,R_{h,1},\ldots ,R_{h,L}\in _R {\mathbb {G}}_q$. Let us consider a cover $S_{{v_i^{(\bar{l}_i)}} ,{v_j^{(\bar{l}_j)}}}$ generated by the chain $({v_i^{(\bar{l}_i)}},{v_{i+1}^{(\bar{l}_{i+1})}},\ldots ,{v_j^{(\bar{l}_j)}})$, using the revoked set ${\mathbb {R}}_0$. Let modified hierarchial identity of the end node ${v_j^{(\bar{l}_j)}}$ with respect to the head node ${v_i^{(\bar{l}_i)}}$ as

  $$\begin{aligned} \left( 0,\ldots ,0,{I_i^{(\bar{l}_i)}},{I_{i+1}^{(\bar{l}_{i+1})}},\ldots ,{I_j^{(\bar{l}_j)}},0,\ldots ,0\right) = \left( {I_1^{(\bar{l}_1)}},{I_2^{(\bar{l}_2)}},\ldots ,{I_L^{(\bar{l}_L)}}\right) . \end{aligned}$$

  So, some ${I_k^{(\bar{l}_k)}}$ may be 0 at the beginning and end. Compute $G=g_p.R_g, F=g_p^z.R_f, V=g_p^y.\displaystyle \prod _{k=1}^{L}({A_{L-k+1}})^{I_k^{(\bar{l}_k)}} R_v,H_k=g_p^{x_k}/A_{L-k+1} R_{h,k}~ (1\le k \le L)$, $E=e(A_1,A_Lg_p^{\gamma })$, where $A_k=g_p^{{\alpha }^k}$. Set public key as ${\textsf {PK}}=(g_p,g_q,G,F,V,H_1,\ldots ,H_L,E,N,{\mathbb {S}})$ and $w={(A_{L}g_p^{\gamma })}^{\alpha }=A_{L+1}A_1^{\gamma }$. Challenger does not have $A_{L+1}$, so he cannot compute w explicitly.

• 3. Phase 1: Let ${\mathcal {A}}$ wants to get secret keys for revoked user $i\in {\mathbb {R}}_0 \cap {\mathbb {R}}_1$. Let i be in $T_{{v_j^{(l_j)}}}$ of cover $S_{{v_i^{(l_i)}} ,{v_j^{(l_j)}}}$ and it queries for a secret key component corresponding to modified hierarchial identity $({{I_1^{(l_1)}}}^*,{I_2^{(l_2)}}^*,\ldots ,{I_L^{(l_L)}}^*)$. Let s be the least identity such that ${I_s^{(\bar{l}_s)}}\ne {I_s^{(l_s)}}^*$.

  • i. Take $r_1,r_2 \in _R {\mathbb {Z}}_n$ and implicitly set $\overline{r}_1=r_1+\frac{\alpha ^s}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}}}$. Secret key $g,f,v,h_1,\ldots ,h_L$ can be obtained by removing the blinding factors $R_g,R_f,R_v,R_{h,1},\ldots ,R_{h,L}$ from $G,F,V,H_1,\ldots ,H_L$ respectively.

  • ii. Next, ${\mathcal {C}}$ tries to compute

    $$\begin{aligned} w.\left( v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*}\right) ^{\overline{r}_1} f^{r_2}=w.\left( v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*}\right) ^{{r_1}} f^{r_2}.\left( v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*}\right) ^\frac{\alpha ^s}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}}}. \end{aligned}$$

    Using secret keys $v,h_k ~(1\le k\le s), f$ and public value ${I_k^{(l_k)}}^*$ $(1\le k\le s)$, $(v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*})^{{r_1}} f^{r_2}$ is computable. Now,

    $$\begin{aligned}&w.\left( v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*}\right) ^\frac{\alpha ^s}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}}}\\= & {} A_{L+1}A_1^{\gamma }\Big (g_p^y.\prod _{k=1}^{L}({A_{L-k+1}})^{I_k^{(\bar{l}_k)}}\displaystyle \prod _ {k=1}^{s} {(g_p^{x_k}/A_{L-k+1})}^{{I_k^{(l_k)}}^*}\Big )^\frac{\alpha ^s}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}}}\\= & {} A_{L+1}A_1^{\gamma }\Big ({A_{L+1}}^{ {I_s^{(\bar{l}_s)}}-{I_s^{(l_s)}}^*}.A_s^y.\prod _{k=s+1}^{L}{(A_{L+s-k+1})}^{I_k^{(\bar{l}_k)}}\displaystyle \prod _ {k=1}^{s} A_s^{x_k.{I_k^{(l_k)}}^{*}}\Big )^\frac{1}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}} }\\= & {} A_1^{\gamma }\Big (A_s^y.\prod _{k=s+1}^{L}{(A_{L+s-k+1})}^{I_k^{(\bar{l}_k)}}\displaystyle \prod _ {k=1}^{s} A_s^{x_k.{I_k^{(l_k)}}^*}\Big )^\frac{1}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}}}. \end{aligned}$$

    As $A_k,{ I_k^{(l_k)}}^*,x_k$ values are available, $w.(v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*})^\frac{\alpha ^s}{ {I_s^{(l_s)}}^*-{I_s^{(\bar{l}_s)}}}$ is computable, so $w.(v\displaystyle \prod _ {k=1}^{s} h_k^{{I_k^{(l_k)}}^*})^{\overline{r}_1}.$ $f^{r_2}$ is also computable.

  • iii. Now using Derive algorithm as stated in Algorithm 9, ${\mathcal {C}}$ computes first component of $sk_{i,v_i^{(l_i)},v_j^{(l_j)}}^{(d)}$ as $w.(v\displaystyle \prod _ {k=1}^{j} h_k^{{I_k^{(l_k)}}^*})^{\overline{r}_1} f^{r_2}$. Other components $(g^{\overline{r}_1},g^{r_2},h_{j+1}^{\overline{r}_1},\ldots ,h_L^{\overline{r}_1})$ of $sk_{i,v_i^{(l_i)},v_j^{(l_j)}}^{(d)}$ are easily computable using secret key components.

  • iv. Challenger need to choose $s_1^{(1)},s_2^{(1)},s_1^{(2)},s_2^{(2)}\in _R {\mathbb {Z}}_n$ such that $s_1^{(1)}s_2^{(2)}-s_2^{(1)}s_1^{(2)}\not \equiv 0 \pmod q$, $s_1^{(1)}s_2^{(2)}-s_2^{(1)}s_1^{(2)}\not \equiv 0 \pmod p$, for this it check the equation $g_p^{s_1^{(1)}s_2^{(2)}-s_2^{(1)}s_1^{(2)}}\not \equiv 1$ and $g_q^{s_1^{(1)}s_2^{(2)}-s_2^{(1)}s_1^{(2)}}$ $\not \equiv 1$. Components of $sk_{i,v_i^{(l_i)},v_j^{(l_j)}}^{(r)}$ are almost same with $sk_{i,v_i^{(l_i)},v_j^{(l_j)}}^{(d)}$ except first component does not contain w. So, ${\mathcal {C}}$ computes $sk_{i,v_i^{(l_i)},v_j^{(l_j)}}^{(r)}$ as previous. Similarly, it can generate secret key $sk_{i,v_i^{(l_i)},v_j^{(l_{j_1})}+v_j^{(l_{j_2})}}$.

  • v. Adversary gets $sk_i= \{ sk_{i,v_i^{(l_i)},v_j^{(l_{j_1})}}, sk_{i,v_i^{(l_i)},v_j^{(l_{j_2})}}, sk_{i,v_i^{(l_i)},v_j^{(l_{j_1})}+v_j^{(l_{j_2})}}\}$, where user i is at $v_L^{(l_L)}$ and $v_i^{(l_i)}\in {\textsf {PN}}(v_L^{(l_L)}),v_j^{(l_{j_1})},v_j^{(l_{j_2})}\in {\textsf {HN}}(v_L^{(l_L)})$.

• 4. Challenge: ${\mathcal {A}}$ sends two messages $m_0=(M_0||K), m_1=(M_1||K)$ to ${\mathcal {C}}$, where last k bits of each message is K. ${\mathcal {C}}$ computes ciphertext components following Algorithm 7 as follows. For $1\le i \le l_0-h+1$, $C_i$’s are encryption of $m_0$ for identity ${\textsf {ID}}_{i,0}=({I_1^{(l_1)}},{I_2^{(l_2)}},\ldots ,{I_L^{(l_L)}})$ and for $l_0-h+2\le i \le l$, $C_i$’s are encryption of $m_0$ for some random identity $({I_1^{(l_1)}},{I_2^{(l_2)}},\ldots ,{I_L^{(l_L)}})$ as

  $$\begin{aligned} C_i= & {} \Big (m_o.E^s,G^s.Z_1,F^s.Z_2,(V\displaystyle \prod _{k=1}^{L} {H_k}^{I_k^{(l_k)}})^{s}.Z_3\Big ),\\&1\le i \le l_0-h\\ C_i= & {} \Big (m_0.E^s.T,G^s.Z_1,F^s.Z_2,(V\displaystyle \prod _{k=1}^{L} {H_k}^{I_k^{(l_k)}})^{s}.Z_3\Big ),\\&l_0-h+2\le i \le l \\ {C_{l_0-h+1}}= & {} \Big (m_0.T.e(A_1,h^{\gamma }), h.Z_1, h^z.Z_2, h^{y+\sum _{k=1}^{L} { I_k^{(l_k)}. x_k}}.Z_3 \Big ),\\&{\text {where~}} Z_1,Z_2,Z_3\in _R {\mathbb {G}}_q, s\in _R {\mathbb {Z}}_n, T \in _R {\mathbb {G}}_{T,p}. \end{aligned}$$

  ${\mathcal {C}}$ permutes the $C_i$ values using permutation $\mu$ and sends ciphertext $\{k,K,C_{\mu (1)},\ldots ,C_{\mu (l)}\}$ to ${\mathcal {A}}.$ As $g_p$ is generator for ${\mathbb {G}}_p$, let us consider $h={g_p}^c$, for some integer c. If $T=e(g_p,{g_p}^c)^{\alpha ^{L+1}}$ then ciphertext component

  $$\begin{aligned} C_{l_0-h+1}= & {} \Big (m_0. e(g_p,{g_p}^c)^{\alpha ^{L+1}}. e(A_1, h^{\gamma }), h.Z_1, h^z.Z_2, h^{y+\sum _{k=1}^{L} { I_k^{(l_k)}. x_k}}.Z_3\Big )\\= & {} \Big (m_0.E^c, G^c.Z_1', F^c.Z_2',(V\displaystyle \prod _{k=1}^{L} {H_k}^{I_k^{(l_k)}})^{c}.Z_3' \Big )\\&{\text {where~}} Z_1,Z_2,Z_3\in {\mathbb {G}}_q. \end{aligned}$$

  This implies, if $T=e(g_p,{g_p}^c)^{\alpha ^{L+1}}$ then ciphertext $\{k,K,C_{\mu (1)},\ldots ,C_{\mu (l)}\}$ is for $\overline{{\textsf {Game}}}_{h-1}^0$ else it is for $\overline{{\textsf {Game}}}_{h}^0$.

• 5. Phase 2: Same as Phase 1.

• 6. Guess: ${\mathcal {A}}$ wins the game if he can predict that ciphertext is for $\overline{{\textsf {Game}}}_{h-1}^0$ or $\overline{{\textsf {Game}}}_{h}^0$.

Adversary’s advantage of distinguishing $\overline{{\textsf {Game}}}_{h-1}^0$ and $\overline{{\textsf {Game}}}_{h}^0$ is same as deciding $T=e(g_p,{g_p}^c)^{\alpha ^{L+1}}$ or not, i.e., solving L-wDBDHI* problem.

In $\overline{{\textsf {Game}}}_{h}^0$, for $i=l_0-h+1$ to l, ciphertext is of the form $(\widehat{C}_1.R_p,\widehat{C}_2,\widehat{C}_3,\widehat{C}_4)$, where $R_p\in _R {\mathbb {G}}_{T,p}$. Let R be a random element from ${\mathbb {G}}_T$. Seo et al. (2009) has proved indistinguishability of $(\widehat{C}_1.R_p,\widehat{C}_2,$ $\widehat{C}_3,\widehat{C}_4)$ from $(\widehat{C}_1.R = R_1,\widehat{C}_2,\widehat{C}_3,\widehat{C}_4)$ under BSD assumption. Again $(\widehat{C}_1.R = R_1,\widehat{C}_2,\widehat{C}_3,\widehat{C}_4)$ are indistinguishable from $(R_1,R_2,R_3,R_4)$ under L-cDDH assumption (Seo et al. 2009). So, $(\widehat{C}_1.R_p,\widehat{C}_2,\widehat{C}_3,\widehat{C}_4)$ and $(R_1,R_2,R_3,R_4)$ are indistinguishable under L-wDBDHI*, BSD and L-cDDH assumption. This implies that ${\textsf {Game}}_{h-1}^0$ and ${\textsf {Game}}_h^0$ are indistinguishable under same assumptions. $\square$

Lemma 4

${\textsf {Game}}_{k-1}^1$ and ${\textsf {Game}}_k^1$ are indistinguishable under L-wDBDHI*, BSD and L-cDDH assumptions.

The proof of this Lemma is analogous to that of Lemma  3.

$\bullet$ Special Variant of OAnoBE

Let $\{v_L^{(l_i)}|1\le l_i\le N\}$ be leaf nodes of a tree. We fix $\{v_L^{(l_i)}|$ $l_i=1,9i,9i+1,1 \le i \le \lfloor N/9 \rfloor \}$ as revoked users for our improved varient. Let $l_i'=\big \lceil \frac{l_i}{3}\big \rceil$, $l_i''=\big \lceil \frac{l_i}{9}\big \rceil$. All subsets in cover can be found as follows:

• 1. If $v_{L-1}^{(l_i')}$ has less than 3 children in ST(R), and head has 3 children, then add $S_{u,v_{L-1}^{{(l_i')}},v_{L}^{(l_{j_1})}}$ or $S_{u,v_{L-1}^{{(l_i')}},v_{L}^{(l_{j_1})}+v_{L}^{(l_{j_2})}}$ to the cover.

• 2. If $v_{L-2}^{(l_i'')}$ has 2 children in ST(R), add $S_{u,v_{L-2}^{(l_i'')},v_{L-1}^{(l_{j_1})}+v_{L-1}^{(l_{j_2})}}$ to the cover.

For each tree with height 3, head node and its ancestor has at least 3 children in ST(R), so cover finding algorithm ensures that on this construction, no height 3 tree will be added into the cover.

The secret keys of user u is $sk_u= \{ sk_{u,v_i^{(l_i)},v_j^{(l_{j_1})}}, sk_{u,v_i^{(l_i)},v_j^{(l_{j_2})}}, sk_{u,v_i^{(l_i)},v_j^{(l_{j_1})}+v_j^{(l_{j_2})}}| L-2\le i\le L-1,i+1\le j \le L,v_i^{(l_i)}\in {\textsf {PN}}(v_L^{(l_L)}),v_j^{(l_{j_1})},v_j^{(l_{j_2})}\in {\textsf {HN}}(v_L^{(l_L)}) \}$. On decryption time user uses these secret keys to decrypt l ciphertext component. So decryption attempt is at most O(l).

Fig. 5

First 9 nodes in a tree with revoked user at $\{v_{4}^{(1)},v_{4}^{(9)}\}$

Example For Fig.  5, the Cover with respect to revoked users is determined as follows:

• (i) The chain $C_1$ corresponding to the revoked user $v_{4}^{(1)}$ is $v_3^{(1)},v_4^{(1)}$, yielding the subset cover $S_{v_3^{(1)},v_4^{(1)}}$.

• (ii) The chain $C_2$ corresponding to the revoked user $v_4^{(9)}$ is $v_3^{(3)},v_4^{(9)}$, yielding the subset cover $S_{v_3^{(3)},v_4^{(9)}}$.

• (iii) The head nodes $v_3^{(1)}$ and $v_3^{(3)}$ of the chains $C_1,C_2$ are then added to R. The nodes $v_4^{(1)},v_4^{(9)}$ are removed from R and the chain corresponding to $v_3^{(1)}$ (or $v_3^{(3)}$) is $v_2^{(1)},v_3^{(1)};v_3^{(3)}$, yielding the set $S_{v_2^{(1)},v_3^{(1)}+v_3^{(3)}}$.

• (iv) Subtree at $v_3^{(1)},v_3^{(3)},v_2^{(1)}$, will be added in cover.

• (v) Taking $v_1^{(1)}$ as head we can not find any chain, so no new cover will be added.

5 Implementation and evaluation

We have implemented our PKBE in a desktop with the following specification: Dell with Intel(R) Core(TM) i7-7700, 3.60GHz processor, 8GB memory, and Ubuntu 18.04 operating system with the assistance of Pairing-Based Cryptography library (Lynn et al. 2006), version 0.5.12. PBC library is a C library which is built above GNU Math Precision library. We use elliptic curve group on the super singular curve $y^2=x^3+x$ and type A1 pairing with composite order group order (consists of 256 bit primes) (see Table 3).

Table 3 Encryption, decryption time (in s) and storage (in bytes) for different number of subscribers

Our OAnoBE has encryption cost similar to PKBE as both encryption are similar except some extra random component which needs negligible time. We have also compared the increase of encryption and decryption cost in percentage (refereed to previous encryption cost). Our OAnoBE has decryption cost more than PKBE as it need to decrypt the ciphertext without knowing the revoked set.

In Table  1, we have given the comparison results with existing similar works. As the constructions are in generic model or in symmetric key setting, therefore we have not implemented their schemes as it would be an unfair comparison.

Future direction The ciphertext size of our constructions can be reduced min$\{N/k, N- r,2r-1\}$ using k-ary subset-difference (Bhattacherjee and Sarkar 2015) scheme in a similar manner. However, the decryption cost will be increased. Traitor tracing is a variant of broadcast encryption which helps to trace the leakage of security information by using a tracing algorithm. Another open problem is to extend our OAnoBE construction to a tracing scheme. It would be more exciting if our construction can be extended to provide full anonymity.

6 Conclusion

We have designed broadcast encryption namely PKBE in public key setting employing ternary tree subset difference method. It achieves the revocation property which is one of the most significant requirement in broadcast encryption setting. Our scheme is based on composite order bilinear group and is proven to have selective semantic security in a standard model under reasonable standard assumptions. The extended version of the scheme namely OAnoBE provides outsider-anonymity. Draw back of our construction is that it uses composite order group system. To achieve the security similar to a prime order scheme, it needs to use a composite order group of larger order. We can extend our construction using k-ary SD (Bhattacherjee and Sarkar 2015) scheme in a similar manner as in this work and can further reduce the ciphertext size to min$\{\frac{N}{k},N-r, 2r-1\}$. However, the decryption cost will be increased. Moreover, it will be interesting to check whether our schemes provide tracing or not.

Appendix

Derive The Derive algorithm works as follows:

Remark

${\widetilde{sk}}_{u,v_i^{(l_i)},v_j^{(l_j)}}^{(d)}$ can be used to decrypt the ciphertext. Re-randomization is used to re-randomize the secret key obtained in delegation procedure. Note that, the delegation procedure does not need MK and consequently can be run by any entity, who knows the upper level secret key $sk_{u,v_i^{(l_i)},v_{j-1}^{(l_{j-1})}}$ to derive secret key $\{sk_{u,v_i^{(l_i)},J}|J=v_{j}^{(l_{j_1})},v_{j}^{(l_{j_2})}, v_{j}^{(l_{j_1})}+v_{j}^{(l_{j_2})}\}$. If we don’t use re-randomization procedure then every secret key $\{sk_{u,v_i^{(l_i)},J}|J=v_{j}^{(l_{j_1})},v_{j}^{(l_{j_2})}, v_{j}^{(l_{j_1})}+v_{j}^{(l_{j_2})}\}$ generated from $sk_{u,v_i^{(l_i)},v_{j-1}^{(l_{j-1})}}$, will have same randomization exponents $r_1,r_2$. Dividing first component of $sk_{u,v_i^{(l_i)},v_{j}^{(l_{j_1})}+v_{j}^{(l_{j_2})}}^{(d)}$ by that of $sk_{u,v_i^{(l_i)},v_{j}^{(l_{j_2})}}^{(d)}$, we obtain ${\Big (h_j^{I_j^{(l_j)}}\Big )}^{r_1}$. Dividing first component of $sk_{u,v_i^{(l_i)},v_{j}^{(l_{j_1})}}^{(d)}$ by ${\Big (h_j^{I_j^{(l_j)}}\Big )}^{r_1}$, we can get first component of $sk_{u,v_i^{(l_i)},v_{j-1}^{(l_{j-1})}}^{(d)}$. If the hanging nodes are already revoked users and now u revoke, then $sk_{u,v_i^{(l_i)},v_{j-1}^{(l_{j-1})}}^{(d)}$ will decrypt the ciphertext (following Decrypt algorithm). Thus a revoked user is still able to recover the message. Re-randomization procedure solves the problem.

Correctness of re-randomization algorithm In Delegation procedure, we generate

$$\begin{aligned} {\widetilde{sk}}_{u,v_i^{(l_i)},v_j^{(l_j)}}^{(d)}= & {} \left( \zeta _0,\zeta _1,\zeta _2, \eta _{j+1}, \eta _{j+2}, \ldots , \eta _{L}\right) \\= & {} \Big (a_0 {(b_j)}^{I_j^{(l_j)}},a_1,a_2,b_{j+1},\ldots ,b_{L}\Big )\\= & {} \Big (w.(v\displaystyle \prod _ {k=i}^{j} h_k^{I_k^{(l_k)}})^{r_1} f^{r_2},g^{r_1},g^{r_2},h_{j+1}^{r_1},\ldots ,h_L^{r_1}\Big ). \\ {\widetilde{sk}}_{u,v_i^{(l_i)},v_j^{(l_j)}}^{(r)}= & {} \Big ( (\theta _0^{(x)}, \theta _1^{(x)}, \theta _2^{(x)}, \phi _{j+1}^{(x)}, \phi _{j+2}^{(x)}, \ldots , \phi _{L}^{(x)})_{x=1,2}\Big )\\= & {} \Big (\big (\alpha _0^{(x)}({\beta _j^{(x)}})^{I_j^{(l_j)}}, \alpha _1^{(x)}, \alpha _2^{(x)}, \beta _{j+1}^{(x)},\ldots ,\beta _L^{(x)}\big )_{x=1,2}\Big )\\= & {} \Big (\big ( (v\displaystyle \prod _ {k=i}^{j}h_k^{I_k^{(l_k)}})^{s_1^{(x)}}f^{s_2^{(x)}},g^{{s_1}^{(x)}},g^{{s_2}^{(x)}},h_{j+1}^{{s_1}^{(x)}},\ldots ,h_L^{{s_1}^{(x)}}\big )_{x=1,2}\Big ). \end{aligned}$$

In re-randomization procedure we set,

$$\begin{aligned} sk_{u,v_i^{(l_i)},v_j^{(l_j)}}^{(d)}= & {} \Big (\zeta _0 {(\theta _0^{(1)})}^{\gamma _1} ({\theta _0 ^{(2)}})^{\delta _1}, \zeta _1 ({\theta _1^{(1)}})^{\gamma _1} ({\theta _1 ^{(2)}})^{\delta _1}, \zeta _2 ({\theta _2^{(1)}})^{\gamma _1} ({\theta _2 ^{(2)}})^{\delta _1},\\&\eta _{j+1}({\phi _{j+1}^{(1)}})^{ \gamma _1}({\phi _{j+1}^{(2)}})^{ \delta _1}, \ldots , \eta _{L}({\phi _{L}^{(1)}})^{ \gamma _1}({\phi _{L}^{(2)}})^{ \delta _1}\Big )\\= & {} \Big (w.(v\displaystyle \prod _ {k=i}^{j} h_k^{I_k^{(l_k)}})^{\widetilde{r_1}} f^{\widetilde{r_2}},g^{\widetilde{r_1}}, g^{\widetilde{r_2}},h_{j+1}^{\widetilde{r_1}},\ldots ,h_L^{\widetilde{r_1}}\Big ), \end{aligned}$$

where $\widetilde{r_1}= r_1+s_1^{(1)}{\gamma }_ 1+ s_1^{(2)} {\delta }_1$ and $\widetilde{r_2}= r_2+s_2^{(1)}{\gamma }_ 1+ s_2^{(2)} {\delta }_1.$

$$\begin{aligned} sk_{u,v_i^{(l_i)},v_j^{(l_j)}}^{(r)}= & {} \Big (\big (({\theta _0^{(1)}})^{\gamma _x}({\theta _0 ^{(2)}})^{\delta _x} ,({\theta _1^{(1)}}) ^{\gamma _x}( {\theta _1 ^{(2)}})^{\delta _x},({\theta _2^{(1)}})^{\gamma _x}( {\theta _2 ^{(2)}})^{\delta _x},\\&({\phi _{j+1}^{(1)}})^{ \gamma _x}({\phi _{j+1}^{(2)}})^{ \delta _x},\ldots ,({\phi _{L}^{(1)}})^{ \gamma _x}({\phi _{L}^{(2)}})^{ \delta _x}\big )_{x=2,3}\Big ).\\= & {} \Big (\big ((v\displaystyle \prod _ {k=i}^{j}h_k^{I_k^{(l_k)}})^{\widetilde{s}_1^{(x)}}f^{\widetilde{s}_2^{(x)}},g^{\widetilde{s}_1^{(x)}}, g^{\widetilde{s}_2^{(x)}},h_{j+1}^{\widetilde{s}_1^{(x)}},\ldots ,h_L^{\widetilde{s}_1^{(x)}}\big )_{x=1,2}\Big ), \end{aligned}$$

where $\widetilde{s}_1^{(1)}= s_1^{(1)}{\gamma }_ 2+ s_1^{(2)} {\delta }_2,\widetilde{s}_1^{(2)}=s_1^{(1)}{\gamma }_ 3+ s_1^{(2)} {\delta }_3 , \widetilde{s}_2^{(1)}=s_2^{(1)}{\gamma }_ 2+ s_2^{(2)} {\delta }_2, \widetilde{s}_2^{(2)}=s_2^{(1)}{\gamma }_ 3+ s_2^{(2)} {\delta }_3.$