# Anonymous Certificate-Based Inner Product Broadcast Encryption

Authors: Shuang Yao; Dawei Zhang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Broadcast encryption scheme enables a sender distribute the confidential content to a certain set of intended recipients. It has been applied in cloud computing, TV broadcasts, and many other scenarios. Inner product broadcast encryption takes merits of both broadcast encryption and inner product encryption. However, it is crucial to reduce the computation cost and to take the recipient’s privacy into consideration in the inner product broadcast encryption scheme. In order to address these problems, we focus on constructing a secure and practical inner product broadcast encryption scheme in this paper. First, we build an anonymous certificate-based inner product broadcast encryption scheme. Especially, we give the concrete construction and security analysis. Second, compared with the existing inner product broadcast encryption schemes, the proposed scheme has an advantage of anonymity. Security proofs show that the proposed scheme achieves confidentiality and anonymity against adaptive chosen-ciphertext attacks. Finally, we implement the proposed anonymous inner product broadcast encryption scheme and evaluate its performance. Test results show that the proposed scheme supports faster decryption operations and has higher efficiency.


---

## Body

## 1. Introduction

Broadcast encryption is an efficient way to make secure group-oriented communication by distributing confidential information in an open channel to a certain set of intended recipients that are selected by the sender. In a broadcast encryption scheme, the sender sends a ciphertext containing secret messages, and the ciphertext is only readable by privileged users. Broadcast encryption has been applied to various scenarios such as GPS, TV broadcasts, and radio broadcasts and may be potentially applied to the blockchain to perform one-to-many information exchange in some scenarios.There are two types of broadcast encryption schemes in the literature: one is symmetric key broadcast encryption [1] and the other is public key broadcast encryption [2]. In terms of symmetric key broadcast encryption, it generates private keys for all users through a trusted center which also broadcasts messages to the intended recipients. It is obvious that the symmetric key broadcast encryption is infeasible to most of broadcast scenarios due to its possibility of single-point failure. In contrast, any user can be a sender in the public key broadcast encryption scheme. It overcomes the shortcoming of single-point failure in the symmetric key scheme. However, there are certificate management problems in the public key broadcast encryption scheme.Function encryption (FE) [3] is different from traditional encryption. Only owners of legitimated keys are able to learn the whole underlying data through the decryption of the ciphertext, while others obtain nothing in traditional encryption. Function encryption can control information amount in the ciphertext transmitted to recipients. Furthermore, the functional encryption for inner product (IPFE) enables the recipient to decrypt the ciphertext related to the vector x⟶ with the private key related to the vector y⟶. It will only obtain inner product x⟶,y⟶ and nothing else. Inner product encryption is simple, but it can provide powerful function. IPFE has been suggested to be applied in many scenarios such as delegation of sensitive computation and biometric authentication [4–6]. In some application scenarios, besides focusing on the privacy of encrypted messages, it is also significant to consider the privacy of the function being computed. Function hiding is an essential property of function encryption which means that the secret key can also hide the function f, and no one could learn any unnecessary information about f [7].In recent years, the notion of inner product broadcast encryption has been proposed [8]. One might think a trivial solution which encrypts the message under the inner product encryption first and then encrypts the ciphertext with a broadcast encryption. However, this trivial solution has a security threat that if a recipient exposes its result obtained from the decryption of broadcast encryption no matter on purpose or not, all users in the inner product encryption system would be able to calculate their inner product values with their private keys. The broadcast encryption for inner product avoids this security threat. It takes merits of both broadcast encryption and inner product encryption. In the inner product broadcast encryption scheme, the recipient can only obtain the inner product associated with the encrypted message by providing their secret keys in the decryption period. The sender determines who can obtain the corresponding inner product value.With the rapid development of information technology and the continuous upgrading of new techniques such as the Internet of Things (IoTs) and blockchain, broadcast encryption has been applied to these new scenarios to provide data security and to guarantee user privacy. In smart communities, it has been used for the information management center to send the encrypted information to some units and individuals that guarantees the secure transmission of information within the community [9]. In the blockchain, it has been applied to achieve group communication and protect the privacy of transaction data in the system [10]. As for the inner product broadcast encryption, it can determine who is able to obtain the plaintext and can give further protection to the plaintext. We pay attention to a personal skill evaluation system which was introduced and described in [8]. For instance, a student gets grades of mathematics 90, communication 80, and programming 60 that are represented by private vector y⟶=90,80,60. If a company wants to know whether a student is suitable for an occupation, it can evaluate the student by computing the weighted average of the scores y⟶,x⟶=90∗50%+80∗30%+60∗20%=81. x⟶=50%,30%,20% represents weights to each of the above scores.


### 1.1. Motivation

Broadcast encryption for the inner product has quite huge application potential. There are some research works that have been undertaken to provide inner product broadcast encryption schemes, and there also exist some shortcomings in the present schemes. First, to the best of our knowledge, the existing schemes do not take the recipient’s identity privacy into consideration. Second, the existing scheme achieves selective CPA security. Third, the heavy decryption cost and large public parameters’ size in the present schemes can bring down the efficiency for those applications in that recipients’ computing ability is limited, and they do not implement their proposed schemes for performance evaluation. At last, the existing scheme constructed in the identity-based cryptosystem has key escrow problems that the key generation center has the ability to decrypt all the encrypted messages in the system compared to certificate-based schemes [11]. Certificate-based broadcast encryption has attracted more and more attention [12, 13]. It has the feature of decentralization which makes it more suitable to be applied in the blockchain, so we build our scheme in the certificate-based cryptosystem. The motivation of this paper is to build a more feasible inner product broadcast encryption scheme with anonymity property. This new construction is also more suitable to be applied to those scenarios whose broadcast plaintext needs further protection. The goals of our scheme can be summarized as the following:In terms of security, we aim to provide adaptive CCA security in the random oracle modelIn the aspect of recipient privacy, we aim to provide anonymity that an encrypted broadcast message should hide who can access its contents; even users in the intended recipient set are not able to recognize other users’ identitiesIn terms of efficiency, we aim to have lower computational overhead in the proposed scheme


### 1.2. Contribution

To summarize, we make the following contributions in this paper:We design an efficient certificate-based inner product broadcast encryption (CBBE-IP) with anonymity property. Compared with the existing construction, the proposed anonymous scheme takes the recipient’s identity privacy into consideration. A user cannot obtain other recipients’ identities, even from each other in the set of authorized recipients in the proposed scheme. It achieves stronger privacy protection.We give the formal proofs under the random oracle model to claim that our construction is confidential and anonymous. It is secure under the adaptive chosen-ciphertext attack.We give the theoretical analysis of our proposed scheme’s efficiency. We also implement both our scheme and the IBBE-IP scheme in Python and evaluate their performance. Experimental and theoretical analysis results show that the proposed scheme has higher efficiency, which enables faster decryption. In addition, our scheme has no restriction that the recipient number has to be less than vector lengthn<d.


### 1.3. Related Work

In recent years, great efforts have been devoted to construct inner product encryption and broadcast encryption.As for inner product encryption, Boneh et al. [3] took the formal study of functional encryption and gave precise definitions of the concept and security about functional encryption. Abdalla et al. [4] showed how to efficiently construct function encryption for the inner product under the standard assumption. Chotard et al. [14] introduced a primitive decentralized multiclient functional encryption (DMCFE) which combined techniques from private stream aggregation (PSA) and functional encryption for the inner product. The scheme can be applied in situations where multiple parties noninteractively share and update data.Considering the function privacy, the notion of predicate privacy was first proposed by Shen et al. [15]. Since then, function-hiding inner product encryption has been deeply researched in numerous proposed papers. Bishop et al. [7] gave us the construction of secret-key function-hiding inner product encryption under the symmetric external Diffie–Hellman (SXDH) assumption in a quite weak and unrealistic security model. Datta et al. [16] proposed a simple and efficient private key IPE that has the strongest indistinguishability-based notion based on the SXDH assumption. Benhamouda et al. [17] proposed a generic construction of IND-CCA inner-product functional encryption from projective hash functions with homomorphic properties. Zhang et al. [18] proposed a generic construction of functional encryption for inner products that is IND-CCA secure. Abdalla et al. [19] proposed a novel methodology which is surprisingly simple and efficient to convert single-input IPE schemes into multi-input functional encryption (MIFE) schemes with the same functionality. Datta et al. [20] developed two nongeneric and practically efficient private key inner product MIFE schemes that first simultaneously achieved message and function privacy. Wang et al. [21] proposed two adaptively CCA-secure functional encryptions in the PKE and SKE settings, respectively. Kim et al. [5] focused on the practical applications of the above schemes; they proposed a fully secure, function-hiding inner product encryption scheme which has obvious shorter secret key and ciphertext compared with the existing schemes.As for broadcast encryption, Fiat and Naor [1] gave the primitive formal definition of broadcast encryption which was a kind of symmetric key broadcast encryption. Naor and Pinkas [2] proposed the first public key broadcast encryption. Gay et al. [22] constructed a new scheme which was the first public key broadcast encryption scheme with constant size of the ciphertext and secret keys.There have been considerable efforts devoted to build broadcast encryption such as identity-based broadcast encryption (IBBE), attribute-based broadcast encryption (ABBE), and certificate-based broadcast encryption (CBBE) with various functions. Delerablee [23] gave the first constant size of private keys and ciphertext. It is an identity-based broadcast encryption scheme with selective CPA security. Jiang et al. [24] proposed a keyword search identity-based broadcast encryption against insider attacks for cloud database systems. Lubicz and Sirvent [25] put forward the concept of attribute-based broadcast encryption by describing the group of privileged users through attributes. It allows one to select or revoke users. Xiong et al. [26] proposed a ciphertext-policy attribute-based encryption (CP-ABE) that, for the first time, realized partial policy hiding, direct revocation, and secure delegation simultaneously in edge computing. There have also been many more recent studies considering the case of ABBE in many fields [27, 28]. Barth et al. [29] took the user anonymity into consideration in broadcast encryption and put forward the concept of privacy in the broadcast encryption scheme. There is no reveal of intended recipients’ identities in this scheme. Sur et al. [30] constructed the first certificate-based multireceiver encryption without formal definitions and proofs to the security. Then, Fan et al. [12] proposed an anonymous CBBE which defined the security models and offered formal proofs to all properties including anonymity. However, it only achieves CPA security and has expensive decryption cost. Zhu et al. [31] proposed adaptive security in the multichallenge setting with constant-size ciphertext header which is a strong security notion for broadcast encryption. Li et al. [32] put forward an anonymous CBBE scheme with constant decryption cost and adaptive CCA security. The CBBE construction avoids key escrow problems of identity-based broadcast encryption. Deng [9] constructed an anonymous certificateless multireceiver encryption scheme for smart community management systems.Jin and Yu-pu [33] proposed the notion of broadcast encryption for inner product predicate encryption under the standard model in 2012. The intended recipients output the plaintext via decryption in the scheme. Then, Lai et al. [8] constructed the first broadcast encryption for inner product scheme (IBBE-IP) under the random oracle model in 2018. It combines the IBBE [23] scheme and the inner product encryption (IPE) [4] scheme which outputs the real value of the inner product via decryption to the user and is a special functional encryption that has potential practical applications. However, these existing inner product broadcast encryption scheme and the inner product predicate broadcast encryption scheme do not take users’ identity privacy into consideration. In this paper, we explore how to construct a more efficient and secure scheme of inner product broadcast encryption in order to extend its application scenarios.


### 1.4. Organization

We first recall some necessary preliminaries in Section2, and then in Section 3, we describe the formal definitions and security model of our broadcast encryption scheme. In Section 4, we give the concrete construction of our scheme. We give the detailed security proof in Section 5. We then implement our broadcast encryption scheme and analyze its performance in Section 6. Conclusions are drawn in Section 7 where we also suggest further work.


## 1.1. Motivation

Broadcast encryption for the inner product has quite huge application potential. There are some research works that have been undertaken to provide inner product broadcast encryption schemes, and there also exist some shortcomings in the present schemes. First, to the best of our knowledge, the existing schemes do not take the recipient’s identity privacy into consideration. Second, the existing scheme achieves selective CPA security. Third, the heavy decryption cost and large public parameters’ size in the present schemes can bring down the efficiency for those applications in that recipients’ computing ability is limited, and they do not implement their proposed schemes for performance evaluation. At last, the existing scheme constructed in the identity-based cryptosystem has key escrow problems that the key generation center has the ability to decrypt all the encrypted messages in the system compared to certificate-based schemes [11]. Certificate-based broadcast encryption has attracted more and more attention [12, 13]. It has the feature of decentralization which makes it more suitable to be applied in the blockchain, so we build our scheme in the certificate-based cryptosystem. The motivation of this paper is to build a more feasible inner product broadcast encryption scheme with anonymity property. This new construction is also more suitable to be applied to those scenarios whose broadcast plaintext needs further protection. The goals of our scheme can be summarized as the following:In terms of security, we aim to provide adaptive CCA security in the random oracle modelIn the aspect of recipient privacy, we aim to provide anonymity that an encrypted broadcast message should hide who can access its contents; even users in the intended recipient set are not able to recognize other users’ identitiesIn terms of efficiency, we aim to have lower computational overhead in the proposed scheme


## 1.2. Contribution

To summarize, we make the following contributions in this paper:We design an efficient certificate-based inner product broadcast encryption (CBBE-IP) with anonymity property. Compared with the existing construction, the proposed anonymous scheme takes the recipient’s identity privacy into consideration. A user cannot obtain other recipients’ identities, even from each other in the set of authorized recipients in the proposed scheme. It achieves stronger privacy protection.We give the formal proofs under the random oracle model to claim that our construction is confidential and anonymous. It is secure under the adaptive chosen-ciphertext attack.We give the theoretical analysis of our proposed scheme’s efficiency. We also implement both our scheme and the IBBE-IP scheme in Python and evaluate their performance. Experimental and theoretical analysis results show that the proposed scheme has higher efficiency, which enables faster decryption. In addition, our scheme has no restriction that the recipient number has to be less than vector lengthn<d.


## 1.3. Related Work

In recent years, great efforts have been devoted to construct inner product encryption and broadcast encryption.As for inner product encryption, Boneh et al. [3] took the formal study of functional encryption and gave precise definitions of the concept and security about functional encryption. Abdalla et al. [4] showed how to efficiently construct function encryption for the inner product under the standard assumption. Chotard et al. [14] introduced a primitive decentralized multiclient functional encryption (DMCFE) which combined techniques from private stream aggregation (PSA) and functional encryption for the inner product. The scheme can be applied in situations where multiple parties noninteractively share and update data.Considering the function privacy, the notion of predicate privacy was first proposed by Shen et al. [15]. Since then, function-hiding inner product encryption has been deeply researched in numerous proposed papers. Bishop et al. [7] gave us the construction of secret-key function-hiding inner product encryption under the symmetric external Diffie–Hellman (SXDH) assumption in a quite weak and unrealistic security model. Datta et al. [16] proposed a simple and efficient private key IPE that has the strongest indistinguishability-based notion based on the SXDH assumption. Benhamouda et al. [17] proposed a generic construction of IND-CCA inner-product functional encryption from projective hash functions with homomorphic properties. Zhang et al. [18] proposed a generic construction of functional encryption for inner products that is IND-CCA secure. Abdalla et al. [19] proposed a novel methodology which is surprisingly simple and efficient to convert single-input IPE schemes into multi-input functional encryption (MIFE) schemes with the same functionality. Datta et al. [20] developed two nongeneric and practically efficient private key inner product MIFE schemes that first simultaneously achieved message and function privacy. Wang et al. [21] proposed two adaptively CCA-secure functional encryptions in the PKE and SKE settings, respectively. Kim et al. [5] focused on the practical applications of the above schemes; they proposed a fully secure, function-hiding inner product encryption scheme which has obvious shorter secret key and ciphertext compared with the existing schemes.As for broadcast encryption, Fiat and Naor [1] gave the primitive formal definition of broadcast encryption which was a kind of symmetric key broadcast encryption. Naor and Pinkas [2] proposed the first public key broadcast encryption. Gay et al. [22] constructed a new scheme which was the first public key broadcast encryption scheme with constant size of the ciphertext and secret keys.There have been considerable efforts devoted to build broadcast encryption such as identity-based broadcast encryption (IBBE), attribute-based broadcast encryption (ABBE), and certificate-based broadcast encryption (CBBE) with various functions. Delerablee [23] gave the first constant size of private keys and ciphertext. It is an identity-based broadcast encryption scheme with selective CPA security. Jiang et al. [24] proposed a keyword search identity-based broadcast encryption against insider attacks for cloud database systems. Lubicz and Sirvent [25] put forward the concept of attribute-based broadcast encryption by describing the group of privileged users through attributes. It allows one to select or revoke users. Xiong et al. [26] proposed a ciphertext-policy attribute-based encryption (CP-ABE) that, for the first time, realized partial policy hiding, direct revocation, and secure delegation simultaneously in edge computing. There have also been many more recent studies considering the case of ABBE in many fields [27, 28]. Barth et al. [29] took the user anonymity into consideration in broadcast encryption and put forward the concept of privacy in the broadcast encryption scheme. There is no reveal of intended recipients’ identities in this scheme. Sur et al. [30] constructed the first certificate-based multireceiver encryption without formal definitions and proofs to the security. Then, Fan et al. [12] proposed an anonymous CBBE which defined the security models and offered formal proofs to all properties including anonymity. However, it only achieves CPA security and has expensive decryption cost. Zhu et al. [31] proposed adaptive security in the multichallenge setting with constant-size ciphertext header which is a strong security notion for broadcast encryption. Li et al. [32] put forward an anonymous CBBE scheme with constant decryption cost and adaptive CCA security. The CBBE construction avoids key escrow problems of identity-based broadcast encryption. Deng [9] constructed an anonymous certificateless multireceiver encryption scheme for smart community management systems.Jin and Yu-pu [33] proposed the notion of broadcast encryption for inner product predicate encryption under the standard model in 2012. The intended recipients output the plaintext via decryption in the scheme. Then, Lai et al. [8] constructed the first broadcast encryption for inner product scheme (IBBE-IP) under the random oracle model in 2018. It combines the IBBE [23] scheme and the inner product encryption (IPE) [4] scheme which outputs the real value of the inner product via decryption to the user and is a special functional encryption that has potential practical applications. However, these existing inner product broadcast encryption scheme and the inner product predicate broadcast encryption scheme do not take users’ identity privacy into consideration. In this paper, we explore how to construct a more efficient and secure scheme of inner product broadcast encryption in order to extend its application scenarios.


## 1.4. Organization

We first recall some necessary preliminaries in Section2, and then in Section 3, we describe the formal definitions and security model of our broadcast encryption scheme. In Section 4, we give the concrete construction of our scheme. We give the detailed security proof in Section 5. We then implement our broadcast encryption scheme and analyze its performance in Section 6. Conclusions are drawn in Section 7 where we also suggest further work.


## 2. Preliminaries

### 2.1. Notations

Notations in this paper are presented in Table1.Table 1
Notations.
SymbolMeaningλSystem security parameterNMaximal amount of recipientsNUser index spaceN=1,2,…,NIDiThe user’s identitySIntended recipient setID1,ID2,…,IDnppPublic parameterMSKMaster secret keyK1i,K2iPublic keys ofIDiS1i,S2iSecret keys ofIDidLength of vectorsx⟶ and y⟶nNumber of intended recipients inSPBilinear pairing computationEExponentiation computation inGETExponentiation computation inGTMTMultiplication operation inGTSuppose that the sender distributes secret messages to a certain set of recipients. Letn denote the number of intended recipients in set S, and let vector length d denote the length of vectors x⟶ and y⟶.


### 2.2. Bilinear Groups

LetG and GT be two cyclic groups with prime order q. g∈G is the generator of group G, and e:G×G⟶GT. The symmetric bilinear group G,GT,q,e has the following properties:(1)
The mape is bilinear: for all a,b∈Zq and u,v∈G, we have that eua,vb=eu,vab(2)
The mape is nondegenerate:eg,g≠1(3)
There exists an efficient algorithm to computeeu,v, for any u,v∈GWe also briefly review the definition of vectors of group elements [34]. Let G be a cyclic group of prime order q, g∈G be an element of group G, and vector x⟶=x1,...,xd∈Zqd, where d is a natural number. Let gx⟶ denote the vector of group elements gx1,…,gxd. For any scalar t∈N and x⟶,y⟶, let(1)gx⟶t=gtx⟶,gx⟶⋅gy⟶=gx⟶+y⟶,eg1x⟶,g2y⟶=∏i∈deg1xi,g2yi=eg1,g2x⟶,y⟶.


### 2.3. Security Assumption

Definition 1.
(discrete logarithm (DL) problem). Giveng,h∈G, the DL problem in G is to find x (if it exists) such that gx=h. The advantage of any probabilistic polynomial-time (PPT) algorithm ℬ in solving the DL problem in G is defined as AdvℬDL. The DL assumption is that, for any PPT algorithm ℬ,AdvℬDL is negligible.Definition 2.
(computational bilinear Diffie–Hellman (CBDH) problem). Giveng,ga,gb,gc∈G for unknown a,b,c∈Zp∗, the CBDH problem in G,GT is to compute eg,gabc∈GT. The advantage of any probabilistic polynomial-time (PPT) algorithm ℬ in solving the CBDH problem in G,GT is defined as AdvℬCBDH=Prℬg,ga,gb,gc=eg,gabc|a,b,c∈Zp∗. The CBDH assumption is that, for any PPT algorithm ℬ,AdvℬCBDH is negligible.


### 2.4. IND-CCA Security of Inner Product Encryption

We review the IND-CCA security of inner product encryption [18]. The security against chosen-ciphertext attacks is defined via a game played by an adversary A and a challenger C. An inner product encryption scheme is indistinguishable under adaptive chosen-ciphertext attacks if AdvAIND−CCA is negligible for all adversary A winning Game 1 in polynomial time. The advantage of A winning Game 1 is AdvAIND−CCA=Prb=b′|<x⟶,y0⟶>=<x⟶,y1⟶>. Game 1 is described as the following:(1)
The challengerC runs the Setup 1λ,S to generate public parameters pp and master secret key MSK. Then, it sends pp to the adversary A.(2)
The adversaryA adaptively queries the key generation oracle for the functional secret key skx⟶ with the restriction that A can only query the secret key in that x⟶,y⟶0=x⟶,y⟶1, where y0⟶ and y1⟶ are the target plaintexts. A can also ask C to decrypt a ciphertext cty⟶′ to obtain x⟶,y⟶ via the decryption oracle.(3)
The adversaryA outputs two target plaintexts y⟶0 and y⟶1.(4)
The challengerC randomly selects a bit b∈0,1 and generates a target ciphertext ct. Then, C passes ct to the adversary A.(5)
The adversaryA can continue to query the key generation oracle with the same restriction as before. A can also query the decryption oracle with the restriction that A cannot query the target ciphertext ct.(6)
The adversaryA outputs a bit b′, and A wins if b=b′.


### 2.5. Certificate-Based Broadcast Encryption

The certificate-based broadcast encryption scheme [12, 32] contains the following algorithms:(i)
Setup1λ: it inputs the security parameter λ and outputs the public parameters params and the master secret key msk.(ii)
KeyGenparams,IDi: it inputs the public parameters params and identity information IDi. This algorithm outputs a key pair pki,ski.(iii)
Certifyparams,msk,IDi,pki: it inputs the public parameters params, master secret key msk, identity information IDi, and public key pki. The algorithm outputs a certificate Certi.(iv)
Encryptparams,S,pki,M: it inputs the public parameters params, an intended recipient set S, a public key pki, and a message M. The algorithm outputs a ciphertext ct.(v)
Decryptpp,ski,ct,IDi,Certi: it inputs the public parameters pp, a secret key ski, a ciphertext ct, identity information IDi, and a certificate Certi. The user in the intended recipient set outputs the message M.


### 2.6. Inner Product Encryption

We briefly recall the definition of the secret-key inner product encryption scheme [5]. It is shown as follows:(i)
Setup1λ,S: it inputs a security parameter λ and a set S. Setup 1λ,S outputs the public parameters pp and the master secret key msk.(ii)
KeyGenmsk,x⟶: it inputs the master secret key msk and a vector x⟶∈Zqd. KeyGen msk,x⟶ outputs the functional secret key skx⟶.(iii)
Encryptmsk,y⟶: it inputs the secret key skx⟶, a vector y⟶∈Zqd, and β∈Zq. Encrypt msk,y⟶ outputs a ciphertext cty⟶.(iv)
Decryptpp,skx⟶,ct: it inputs the public parameters pp, a secret key skx⟶, and a ciphertext ct. Decrypt pp,skx⟶,ct outputs a message z∈Zq or ⊥.As we can see from the above definition of the inner product encryption scheme, secret keys are associated with the vectorx⟶, and the encrypted message is associated with the vector y⟶. Given a secret key for x⟶ and the ciphertext for y⟶, the recipient obtains the inner product value x⟶,y⟶ via decryption. Especially, the above inner product encryption used in our scheme is different from the inner product predicate encryption scheme proposed by Okamoto and Takashima [35]. In the inner product predicate encryption scheme, a message m is encrypted with a tag y⟶, and the decryption key is associated with vector x⟶. The recipient can recover the message m only if x⟶,y⟶=0.


## 2.1. Notations

Notations in this paper are presented in Table1.Table 1
Notations.
SymbolMeaningλSystem security parameterNMaximal amount of recipientsNUser index spaceN=1,2,…,NIDiThe user’s identitySIntended recipient setID1,ID2,…,IDnppPublic parameterMSKMaster secret keyK1i,K2iPublic keys ofIDiS1i,S2iSecret keys ofIDidLength of vectorsx⟶ and y⟶nNumber of intended recipients inSPBilinear pairing computationEExponentiation computation inGETExponentiation computation inGTMTMultiplication operation inGTSuppose that the sender distributes secret messages to a certain set of recipients. Letn denote the number of intended recipients in set S, and let vector length d denote the length of vectors x⟶ and y⟶.


## 2.2. Bilinear Groups

LetG and GT be two cyclic groups with prime order q. g∈G is the generator of group G, and e:G×G⟶GT. The symmetric bilinear group G,GT,q,e has the following properties:(1)
The mape is bilinear: for all a,b∈Zq and u,v∈G, we have that eua,vb=eu,vab(2)
The mape is nondegenerate:eg,g≠1(3)
There exists an efficient algorithm to computeeu,v, for any u,v∈GWe also briefly review the definition of vectors of group elements [34]. Let G be a cyclic group of prime order q, g∈G be an element of group G, and vector x⟶=x1,...,xd∈Zqd, where d is a natural number. Let gx⟶ denote the vector of group elements gx1,…,gxd. For any scalar t∈N and x⟶,y⟶, let(1)gx⟶t=gtx⟶,gx⟶⋅gy⟶=gx⟶+y⟶,eg1x⟶,g2y⟶=∏i∈deg1xi,g2yi=eg1,g2x⟶,y⟶.


## 2.3. Security Assumption

Definition 1.
(discrete logarithm (DL) problem). Giveng,h∈G, the DL problem in G is to find x (if it exists) such that gx=h. The advantage of any probabilistic polynomial-time (PPT) algorithm ℬ in solving the DL problem in G is defined as AdvℬDL. The DL assumption is that, for any PPT algorithm ℬ,AdvℬDL is negligible.Definition 2.
(computational bilinear Diffie–Hellman (CBDH) problem). Giveng,ga,gb,gc∈G for unknown a,b,c∈Zp∗, the CBDH problem in G,GT is to compute eg,gabc∈GT. The advantage of any probabilistic polynomial-time (PPT) algorithm ℬ in solving the CBDH problem in G,GT is defined as AdvℬCBDH=Prℬg,ga,gb,gc=eg,gabc|a,b,c∈Zp∗. The CBDH assumption is that, for any PPT algorithm ℬ,AdvℬCBDH is negligible.


## 2.4. IND-CCA Security of Inner Product Encryption

We review the IND-CCA security of inner product encryption [18]. The security against chosen-ciphertext attacks is defined via a game played by an adversary A and a challenger C. An inner product encryption scheme is indistinguishable under adaptive chosen-ciphertext attacks if AdvAIND−CCA is negligible for all adversary A winning Game 1 in polynomial time. The advantage of A winning Game 1 is AdvAIND−CCA=Prb=b′|<x⟶,y0⟶>=<x⟶,y1⟶>. Game 1 is described as the following:(1)
The challengerC runs the Setup 1λ,S to generate public parameters pp and master secret key MSK. Then, it sends pp to the adversary A.(2)
The adversaryA adaptively queries the key generation oracle for the functional secret key skx⟶ with the restriction that A can only query the secret key in that x⟶,y⟶0=x⟶,y⟶1, where y0⟶ and y1⟶ are the target plaintexts. A can also ask C to decrypt a ciphertext cty⟶′ to obtain x⟶,y⟶ via the decryption oracle.(3)
The adversaryA outputs two target plaintexts y⟶0 and y⟶1.(4)
The challengerC randomly selects a bit b∈0,1 and generates a target ciphertext ct. Then, C passes ct to the adversary A.(5)
The adversaryA can continue to query the key generation oracle with the same restriction as before. A can also query the decryption oracle with the restriction that A cannot query the target ciphertext ct.(6)
The adversaryA outputs a bit b′, and A wins if b=b′.


## 2.5. Certificate-Based Broadcast Encryption

The certificate-based broadcast encryption scheme [12, 32] contains the following algorithms:(i)
Setup1λ: it inputs the security parameter λ and outputs the public parameters params and the master secret key msk.(ii)
KeyGenparams,IDi: it inputs the public parameters params and identity information IDi. This algorithm outputs a key pair pki,ski.(iii)
Certifyparams,msk,IDi,pki: it inputs the public parameters params, master secret key msk, identity information IDi, and public key pki. The algorithm outputs a certificate Certi.(iv)
Encryptparams,S,pki,M: it inputs the public parameters params, an intended recipient set S, a public key pki, and a message M. The algorithm outputs a ciphertext ct.(v)
Decryptpp,ski,ct,IDi,Certi: it inputs the public parameters pp, a secret key ski, a ciphertext ct, identity information IDi, and a certificate Certi. The user in the intended recipient set outputs the message M.


## 2.6. Inner Product Encryption

We briefly recall the definition of the secret-key inner product encryption scheme [5]. It is shown as follows:(i)
Setup1λ,S: it inputs a security parameter λ and a set S. Setup 1λ,S outputs the public parameters pp and the master secret key msk.(ii)
KeyGenmsk,x⟶: it inputs the master secret key msk and a vector x⟶∈Zqd. KeyGen msk,x⟶ outputs the functional secret key skx⟶.(iii)
Encryptmsk,y⟶: it inputs the secret key skx⟶, a vector y⟶∈Zqd, and β∈Zq. Encrypt msk,y⟶ outputs a ciphertext cty⟶.(iv)
Decryptpp,skx⟶,ct: it inputs the public parameters pp, a secret key skx⟶, and a ciphertext ct. Decrypt pp,skx⟶,ct outputs a message z∈Zq or ⊥.As we can see from the above definition of the inner product encryption scheme, secret keys are associated with the vectorx⟶, and the encrypted message is associated with the vector y⟶. Given a secret key for x⟶ and the ciphertext for y⟶, the recipient obtains the inner product value x⟶,y⟶ via decryption. Especially, the above inner product encryption used in our scheme is different from the inner product predicate encryption scheme proposed by Okamoto and Takashima [35]. In the inner product predicate encryption scheme, a message m is encrypted with a tag y⟶, and the decryption key is associated with vector x⟶. The recipient can recover the message m only if x⟶,y⟶=0.


## 3. Formal Definition and Security Model

### 3.1. Formal Definition

The system model of our proposed scheme is shown in Figure1. The formal definition of our scheme is shown as follows:(i)
Setup1λ,d: it inputs a security parameter λ and vector length d. This algorithm outputs public parameters pp and master secret key MSK. Certificate authority (CA) runs this algorithm. It publishes pp and keeps MSK.(ii)
KeyGenpp,IDi,x⟶i: it inputs public parameters pp, a vector x⟶i, and an identity IDi. x⟶i is kept secretly, and it is not allowed to be known by others. It outputs secret keys SKi=SK1i,SK2i in addition to public keys Ki=K1i,K2i. This algorithm is executed by users.(iii)
CertGenpp,MSK,IDi,Ki: it inputs public parameters pp, a master secret key MSK, a user’s identity IDi, and public keys K1i and K2i. It outputs certificate Certi. This algorithm is executed by CA. Users obtain their certificates from the CA. The certificate is anonymous for the reason that no one is able to obtain the user identity by its certificate except the CA. The certificate plays a role as a portion of the user’s keys. Though the CA generates the certificate for each user, it is not able to decrypt the ciphertext.(iv)
Encryptpp,y⟶,S,Ki: it inputs public parameters pp, a vector y⟶∈Zqd as the plaintext, the intended recipient set S, and public keys K1i and K2i. It outputs ciphertext CT. This algorithm is executed by the sender.(v)
Decryptpp,CT,IDi,SKi,Certi: it inputs public parameters pp, a ciphertext CT, a user identity IDi, a certificate Certi, and secret keys SK1i and SK2i. If IDi is an intended recipient, it will obtain the corresponding inner product value of the related message. Otherwise, it outputs ⊥.Figure 1
System model of the proposed scheme.


### 3.2. Security Model

The security of our proposed scheme requires confidentiality and anonymity. As for the confidentiality, it means that, for an encrypted message which is associated withy⟶, only the intended recipients in S can obtain x⟶,y⟶ through the decryption using their secret keys that are associated with x⟶. We give the definition for confidentiality of our proposed scheme via IND-CBIP-CCA Game 1 and IND-CBIP-CCA Game 2. As for the anonymity, all users, even users in S, are not able to recognize who is the intended recipient. In our scheme, the vector x⟶i is kept secretly by users, and it cannot be known by others though it may have implied relationship with user identity information; we do not consider x⟶i in anonymity games. On the contrary, the user identifier IDi is public, so we considered the user identifier IDi in anonymity games. We give the definition for anonymity of our proposed scheme via ANO-CBIP-CCA Game 1 and ANO-CBIP-CCA Game 2.The security model of our proposed scheme contains two adversariesA1 and A2. A1 is an uncertified user with no access to the master key. It can replace any user’s public key and query any user’s secret key. A1 can also query any user’s certificate except the target user’s certificate. A1 can make the decryption query of any broadcast ciphertext except the target broadcast ciphertext. A2 is a malicious certifier that has a master key. It can generate any user’s certificate. A2 is not able to replace any user’s public key, but it can query any user’s secret key except the target user. A2 can also perform the broadcast ciphertext’s decryption query except the target broadcast ciphertext.IND-CBIP-CCA Game 1 is played by a challengerC and an adversary A1.Setup:C runs the Setup 1λ,d algorithm, gives A1 the generated public parameters pp, and keeps the generated master secret key MSK with itself.Phase 1:A1 adaptively launches the following queries to C. C maintains a list L1=IDi,Ki,SKi,Ti in order to answer queries. We denote public key Ki=K1i,K2i and secret key SKi=SK1i,SK2i. If Ti=0, it represents that Ki has not been replaced by A1, while Ti=1 means that A1 has made a replacement of Ki. L1 was empty when it was initialized.OPublicKeyIDi: public keys’ query: on inputting IDi, C retrieves L1. If there is an item IDi,Ki,SKi,Ti related to IDi in L1, C returns corresponding Ki to A1. Otherwise, C runs KeyGenpp,IDi,x⟶i and generates Ki and SKi for IDi. It adds the new item IDi,Ki,SKi,0 to L1 and returns Ki to A1.OPublicKeyReplaceIDi,Ki′: public keys’ replacing query: on inputting IDi and a public key Ki′ randomly chosen by A1, C updates the item IDi,Ki′,⊥,1 which is related to IDi in L1.OSecretKeyIDi: secret keys’ query: on inputting IDi, C does the following things to answer the query. It searches the item IDi,Ki,SKi,Ti related to IDi in L1. If Ti=1, C returns ⊥. Otherwise, it returns SKi to A1.OCertificateIDi: certificate query: on inputting IDi, in order to make a response to the query, C searches the item IDi,Ki,SKi,Ti in L1. Then, it executes CertGenpp,MSK,IDi,Ki and returns the generated Certi to A1.ODecryptIDi,CT: decrypt query: on inputting IDi and ciphertext CT, C searches the item IDi,Ki,SKi,Ti in L1. If Ti=1, A1 has made replacement of Ki, and it should give corresponding SKi of Ki. C executes CertGenpp,MSK,IDi,Ki and generates Certi of IDi. Then, C executes Decryptpp,CT,IDi,SKi,Certi to decrypt CT. It sends the decryption result to A1.Challenge:A1 sends a challenge recipient set S∗=ID1,…,IDn, two distinct messages M0,M1 and M0=y⟶0andM1=y⟶1, and then x⟶,y⟶0=x⟶,y⟶1. It sends M0,M1 to C with the constraint that A1 neither queried Certi of IDi in S∗ nor made replacement of Ki for IDi in S∗ in Phase 1. C selects a bit μ∈0,1 at random. Then, it executes Encryptpp,Mμ,S∗,Ki and returns the generated challenge ciphertext CT∗ to A1.Phase 2:A1 issues a set of queries adaptively as in Phase 1. However, it is forbidden to query Certi of IDi in S∗ or decryption of IDi in S∗.Guess:A1 outputs a guess μ∈0,1. It wins the game if μ′=μ. We define A1’s advantage in attacking the scheme to win IND-CBIP-CCA Game 1 as AdvA1IND−CBIP−CCAλ=Prμ′=μ−1/2.Definition 3.
We say that our proposed scheme is IND-CBIP-CCA secure ifAdvA1IND−CBIP−CCAλ<ε is satisfied for any PPT adversary A1.
IND-CBIP-CCA Game 2 is played by a challengerC and an adversary A2.Setup:C runs the Setup 1λ,d algorithm and gives A2 the generated public parameters pp and the generated master secret key MSK.Phase 1:A2 adaptively launches the following queries to C. C maintains list L2=IDi,Ki,SKi for answering queries. We denote Ki=K1i,K2i and SKi=SK1i,SK2i. L2 was empty when it was initialized.OPublicKeyIDi:public keys’ query: on inputting IDi, C retrieves L2. If there is an item IDi,Ki,SKi related to IDi in L2, C returns corresponding Ki to A2. Else, it runs KeyGenpp,IDi,xi⟶ and generates Ki and SKi for IDi. Then, it adds the new item IDi,Ki,SKi to L2 and returns Ki to A2.OSecretKeyIDi: secret keys’ query: on inputting IDi, in order to make a response to the query, C searches item IDi,Ki,SKi related to IDi in L2 and returns SKi to A2.ODecryptIDi,CT: decrypt query: on inputting IDi and ciphertext CT, C does the following things to answer the query. It searches the item IDi,Ki,SKi in L2, executes CertGenpp,MSK,IDi,Ki, and generates Certi of IDi. Then, C executes Decryptpp,CT,IDi,SKi,Certi to decrypt CT. It sends the decryption result to A2.Challenge:A2 sends a challenge recipient set S∗=ID1,…,IDn, two distinct messages M0,M1 and M0=y⟶0andM1=y⟶1, and then x⟶,y⟶0=x⟶,y⟶1. It sends M0,M1 to C with the constraint that A2 has not queried SKi of IDi in S∗ in Phase 1. C selects a bit μ∈0,1 at random. Then, it executes Encryptpp,Mμ,S∗,Ki and returns the generated challenge ciphertext CT∗ to A2.Phase 2:A2 issues a set of queries adaptively as in Phase 1. However, it is forbidden to query SKi of IDi in S∗ or decryption of IDi in S∗.Guess:A2 outputs a guess μ∈0,1. It wins the game if μ′=μ. We define A2’s advantage in attacking the scheme to win IND-CBIP-CCA Game 2 as AdvA2IND−CBIP−CCAλ=Prμ′=μ−1/2.Definition 4.
We say that our proposed scheme is IND-CBIP-CCA secure ifAdvA2IND−CBIP−CCAλ<ε is satisfied for any PPT adversary A2.
ANO-CBIP-CCA Game 1 is played by a challengerC and an adversary A1.Setup:C runs the Setup 1λ,d algorithm, gives A1 the generated public parameters pp, and keeps the generated master secret key MSK with itself.Phase 1:A1 adaptively launches the following queries to C. C maintains a list L1=IDi,Ki,SKi,Ti in order to answer queries. We denote public key Ki=K1i,K2i and secret key SKi=SK1i,SK2i. If Ti=0, it represents that Ki has not been replaced by A1, while Ti=1 means that A1 has made replacement of Ki. L1 was empty when it was initialized.OPublicKeyIDi: public keys’ query: on inputting IDi, C retrieves L1. If there is an item IDi,Ki,SKi,Ti related to IDi in L1, C returns the corresponding public key Ki to A1. Otherwise, C runs KeyGenpp,IDi,x⟶i and generates Ki and SKi for IDi. It adds the new item IDi,Ki,SKi,0 to L1 and returns Ki to A1.OPublicKeyReplaceIDi,Ki′: public keys’ replacing query: on inputting IDi and a public key Ki′ randomly chosen by A1, C updates the item IDi,Ki′,⊥,1 which is related to IDi in L1.OSecretKeyIDi: secret keys’ query: on inputting IDi, C does the following things to answer the query. It searches the item IDi,Ki,SKi,Ti related to IDi in L1. If Ti=1, C returns ⊥. Otherwise, it returns SKi to A1.OCertificateIDi: certificate query: on inputting IDi, C searches the item IDi,Ki,SKi,Ti in L1. Then, it executes CertGenpp,MSK,IDi,Ki and returns the generated certificate Certi to A1.ODecryptIDi,CT: decrypt query: on inputting IDi and ciphertext CT, C searches the item IDi,Ki,SKi,Ti in L1. If Ti=1, A1 has made replacement of Ki, and it should give corresponding SKi of Ki to C. C executes CertGenpp,MSK,IDi,Ki and generates Certi of IDi. Then, it runs Decryptpp,CT,IDi,SKi,Certi to decrypt CT and sends the decryption result to A1.Challenge:A1 sends a challenge recipient set S=ID1,…,IDn, two user identities ID0∗,ID1∗, and a message M=y⟶ to C with the constraint that A1 neither queried Certi of IDi in S∪ID0∗,ID1∗ nor replaced Ki of IDi in S∪ID0∗,ID1∗ in Phase 1. C selects a bit μ∈0,1 and set Sμ∗=IDμ∗∪S at random. Then, it executes Encryptpp,M,Sμ∗,Ki and returns the generated challenge ciphertext CT∗ to A1.Phase 2:A1 issues a set of queries adaptively as in Phase 1 with the constraint that it is not able to query Certi of IDi in S∪ID0∗,ID1∗ or decryption of IDi in S∪ID0∗,ID1∗.Guess:A1 outputs a guess μ′∈0,1. It wins the game if μ′=μ. We define A1’s advantage in attacking the scheme to win ANO-CBIP-CCA Game 1 as AdvA1ANO−CBIP−CCAλ=Prμ′=μ−1/2.Definition 5.
We say that our proposed scheme is ANO-CBIP-CCA secure ifAdvA1ANO−CBIP−CCAλ<ε is satisfied for any PPT adversary A1.
ANO-CBIP-CCA Game 2 is played by a challengerC and an adversary A2.Setup:C runs the Setup 1λ,d algorithm and gives A2 the generated public parameters pp and the generated master secret key MSK.Phase 1:A2 adaptively launches the following queries to C. C maintains list L2=IDi,Ki,SKi for answering queries. We denote Ki=K1i,K2i and SKi=SK1i,SK2i. L2 was empty when it was initialized.OPublicKeyIDi: public keys’ query: on inputting IDi, C retrieves L2. If there is an item IDi,Ki,SKi related to IDi in L2, C returns corresponding Ki to A2. Otherwise, C runs KeyGenpp,IDi,x⟶i and generates Ki and SKi for IDi. It adds the new item IDi,Ki,SKi to L2 and returns Ki to A2.OSecretKeyIDi: secret keys’ query: on inputting IDi, C searches the item IDi,Ki,SKi related to IDi in L2 and returns SKi to A2.ODecryptIDi,CT: decrypt query: on inputting IDi and ciphertext CT, C searches the item IDi,Ki,SKi in L2. It executes CertGenpp,MSK,IDi,Ki and generates Certi for IDi. Then, C executes Decryptpp,CT,IDi,SKi,Certi to decrypt CT. It sends the decryption result to A2.Challenge:A2 sends a challenge recipient set S=ID1,…,IDn, two user identities ID0∗,ID1∗, and a message M=y⟶ to C with the constraint that A2 has not queried SKi of IDi in S∪ID0∗,ID1∗ in Phase 1. C selects a bit μ∈0,1 at random and set Sμ∗=IDμ∗∪S. Then, it executes Encryptpp,M,Sμ∗,Ki and returns the generated challenge ciphertext CT∗ to A2.Phase 2:A2 issues a set of queries adaptively as in Phase 1 with the constraint that it is not able to query SKi of IDi in S∪ID0∗,ID1∗ or decryption of IDi in S∪ID0∗,ID1∗.Guess:A2 outputs a guess μ′∈0,1. It wins the game if μ′=μ. We define A2’s advantage in attacking the scheme to win ANO-CBIP-CCA Game 2 as AdvA2ANO−CBIP−CCAλ=Prμ′=μ−1/2.Definition 6.
We say that our proposed scheme is ANO-CBIP-CCA secure ifAdvA2ANO−CBIP−CCAλ<ε is satisfied for any PPT adversary A2.


## 3.1. Formal Definition

The system model of our proposed scheme is shown in Figure1. The formal definition of our scheme is shown as follows:(i)
Setup1λ,d: it inputs a security parameter λ and vector length d. This algorithm outputs public parameters pp and master secret key MSK. Certificate authority (CA) runs this algorithm. It publishes pp and keeps MSK.(ii)
KeyGenpp,IDi,x⟶i: it inputs public parameters pp, a vector x⟶i, and an identity IDi. x⟶i is kept secretly, and it is not allowed to be known by others. It outputs secret keys SKi=SK1i,SK2i in addition to public keys Ki=K1i,K2i. This algorithm is executed by users.(iii)
CertGenpp,MSK,IDi,Ki: it inputs public parameters pp, a master secret key MSK, a user’s identity IDi, and public keys K1i and K2i. It outputs certificate Certi. This algorithm is executed by CA. Users obtain their certificates from the CA. The certificate is anonymous for the reason that no one is able to obtain the user identity by its certificate except the CA. The certificate plays a role as a portion of the user’s keys. Though the CA generates the certificate for each user, it is not able to decrypt the ciphertext.(iv)
Encryptpp,y⟶,S,Ki: it inputs public parameters pp, a vector y⟶∈Zqd as the plaintext, the intended recipient set S, and public keys K1i and K2i. It outputs ciphertext CT. This algorithm is executed by the sender.(v)
Decryptpp,CT,IDi,SKi,Certi: it inputs public parameters pp, a ciphertext CT, a user identity IDi, a certificate Certi, and secret keys SK1i and SK2i. If IDi is an intended recipient, it will obtain the corresponding inner product value of the related message. Otherwise, it outputs ⊥.Figure 1
System model of the proposed scheme.


## 3.2. Security Model

The security of our proposed scheme requires confidentiality and anonymity. As for the confidentiality, it means that, for an encrypted message which is associated withy⟶, only the intended recipients in S can obtain x⟶,y⟶ through the decryption using their secret keys that are associated with x⟶. We give the definition for confidentiality of our proposed scheme via IND-CBIP-CCA Game 1 and IND-CBIP-CCA Game 2. As for the anonymity, all users, even users in S, are not able to recognize who is the intended recipient. In our scheme, the vector x⟶i is kept secretly by users, and it cannot be known by others though it may have implied relationship with user identity information; we do not consider x⟶i in anonymity games. On the contrary, the user identifier IDi is public, so we considered the user identifier IDi in anonymity games. We give the definition for anonymity of our proposed scheme via ANO-CBIP-CCA Game 1 and ANO-CBIP-CCA Game 2.The security model of our proposed scheme contains two adversariesA1 and A2. A1 is an uncertified user with no access to the master key. It can replace any user’s public key and query any user’s secret key. A1 can also query any user’s certificate except the target user’s certificate. A1 can make the decryption query of any broadcast ciphertext except the target broadcast ciphertext. A2 is a malicious certifier that has a master key. It can generate any user’s certificate. A2 is not able to replace any user’s public key, but it can query any user’s secret key except the target user. A2 can also perform the broadcast ciphertext’s decryption query except the target broadcast ciphertext.IND-CBIP-CCA Game 1 is played by a challengerC and an adversary A1.Setup:C runs the Setup 1λ,d algorithm, gives A1 the generated public parameters pp, and keeps the generated master secret key MSK with itself.Phase 1:A1 adaptively launches the following queries to C. C maintains a list L1=IDi,Ki,SKi,Ti in order to answer queries. We denote public key Ki=K1i,K2i and secret key SKi=SK1i,SK2i. If Ti=0, it represents that Ki has not been replaced by A1, while Ti=1 means that A1 has made a replacement of Ki. L1 was empty when it was initialized.OPublicKeyIDi: public keys’ query: on inputting IDi, C retrieves L1. If there is an item IDi,Ki,SKi,Ti related to IDi in L1, C returns corresponding Ki to A1. Otherwise, C runs KeyGenpp,IDi,x⟶i and generates Ki and SKi for IDi. It adds the new item IDi,Ki,SKi,0 to L1 and returns Ki to A1.OPublicKeyReplaceIDi,Ki′: public keys’ replacing query: on inputting IDi and a public key Ki′ randomly chosen by A1, C updates the item IDi,Ki′,⊥,1 which is related to IDi in L1.OSecretKeyIDi: secret keys’ query: on inputting IDi, C does the following things to answer the query. It searches the item IDi,Ki,SKi,Ti related to IDi in L1. If Ti=1, C returns ⊥. Otherwise, it returns SKi to A1.OCertificateIDi: certificate query: on inputting IDi, in order to make a response to the query, C searches the item IDi,Ki,SKi,Ti in L1. Then, it executes CertGenpp,MSK,IDi,Ki and returns the generated Certi to A1.ODecryptIDi,CT: decrypt query: on inputting IDi and ciphertext CT, C searches the item IDi,Ki,SKi,Ti in L1. If Ti=1, A1 has made replacement of Ki, and it should give corresponding SKi of Ki. C executes CertGenpp,MSK,IDi,Ki and generates Certi of IDi. Then, C executes Decryptpp,CT,IDi,SKi,Certi to decrypt CT. It sends the decryption result to A1.Challenge:A1 sends a challenge recipient set S∗=ID1,…,IDn, two distinct messages M0,M1 and M0=y⟶0andM1=y⟶1, and then x⟶,y⟶0=x⟶,y⟶1. It sends M0,M1 to C with the constraint that A1 neither queried Certi of IDi in S∗ nor made replacement of Ki for IDi in S∗ in Phase 1. C selects a bit μ∈0,1 at random. Then, it executes Encryptpp,Mμ,S∗,Ki and returns the generated challenge ciphertext CT∗ to A1.Phase 2:A1 issues a set of queries adaptively as in Phase 1. However, it is forbidden to query Certi of IDi in S∗ or decryption of IDi in S∗.Guess:A1 outputs a guess μ∈0,1. It wins the game if μ′=μ. We define A1’s advantage in attacking the scheme to win IND-CBIP-CCA Game 1 as AdvA1IND−CBIP−CCAλ=Prμ′=μ−1/2.Definition 3.
We say that our proposed scheme is IND-CBIP-CCA secure ifAdvA1IND−CBIP−CCAλ<ε is satisfied for any PPT adversary A1.
IND-CBIP-CCA Game 2 is played by a challengerC and an adversary A2.Setup:C runs the Setup 1λ,d algorithm and gives A2 the generated public parameters pp and the generated master secret key MSK.Phase 1:A2 adaptively launches the following queries to C. C maintains list L2=IDi,Ki,SKi for answering queries. We denote Ki=K1i,K2i and SKi=SK1i,SK2i. L2 was empty when it was initialized.OPublicKeyIDi:public keys’ query: on inputting IDi, C retrieves L2. If there is an item IDi,Ki,SKi related to IDi in L2, C returns corresponding Ki to A2. Else, it runs KeyGenpp,IDi,xi⟶ and generates Ki and SKi for IDi. Then, it adds the new item IDi,Ki,SKi to L2 and returns Ki to A2.OSecretKeyIDi: secret keys’ query: on inputting IDi, in order to make a response to the query, C searches item IDi,Ki,SKi related to IDi in L2 and returns SKi to A2.ODecryptIDi,CT: decrypt query: on inputting IDi and ciphertext CT, C does the following things to answer the query. It searches the item IDi,Ki,SKi in L2, executes CertGenpp,MSK,IDi,Ki, and generates Certi of IDi. Then, C executes Decryptpp,CT,IDi,SKi,Certi to decrypt CT. It sends the decryption result to A2.Challenge:A2 sends a challenge recipient set S∗=ID1,…,IDn, two distinct messages M0,M1 and M0=y⟶0andM1=y⟶1, and then x⟶,y⟶0=x⟶,y⟶1. It sends M0,M1 to C with the constraint that A2 has not queried SKi of IDi in S∗ in Phase 1. C selects a bit μ∈0,1 at random. Then, it executes Encryptpp,Mμ,S∗,Ki and returns the generated challenge ciphertext CT∗ to A2.Phase 2:A2 issues a set of queries adaptively as in Phase 1. However, it is forbidden to query SKi of IDi in S∗ or decryption of IDi in S∗.Guess:A2 outputs a guess μ∈0,1. It wins the game if μ′=μ. We define A2’s advantage in attacking the scheme to win IND-CBIP-CCA Game 2 as AdvA2IND−CBIP−CCAλ=Prμ′=μ−1/2.Definition 4.
We say that our proposed scheme is IND-CBIP-CCA secure ifAdvA2IND−CBIP−CCAλ<ε is satisfied for any PPT adversary A2.
ANO-CBIP-CCA Game 1 is played by a challengerC and an adversary A1.Setup:C runs the Setup 1λ,d algorithm, gives A1 the generated public parameters pp, and keeps the generated master secret key MSK with itself.Phase 1:A1 adaptively launches the following queries to C. C maintains a list L1=IDi,Ki,SKi,Ti in order to answer queries. We denote public key Ki=K1i,K2i and secret key SKi=SK1i,SK2i. If Ti=0, it represents that Ki has not been replaced by A1, while Ti=1 means that A1 has made replacement of Ki. L1 was empty when it was initialized.OPublicKeyIDi: public keys’ query: on inputting IDi, C retrieves L1. If there is an item IDi,Ki,SKi,Ti related to IDi in L1, C returns the corresponding public key Ki to A1. Otherwise, C runs KeyGenpp,IDi,x⟶i and generates Ki and SKi for IDi. It adds the new item IDi,Ki,SKi,0 to L1 and returns Ki to A1.OPublicKeyReplaceIDi,Ki′: public keys’ replacing query: on inputting IDi and a public key Ki′ randomly chosen by A1, C updates the item IDi,Ki′,⊥,1 which is related to IDi in L1.OSecretKeyIDi: secret keys’ query: on inputting IDi, C does the following things to answer the query. It searches the item IDi,Ki,SKi,Ti related to IDi in L1. If Ti=1, C returns ⊥. Otherwise, it returns SKi to A1.OCertificateIDi: certificate query: on inputting IDi, C searches the item IDi,Ki,SKi,Ti in L1. Then, it executes CertGenpp,MSK,IDi,Ki and returns the generated certificate Certi to A1.ODecryptIDi,CT: decrypt query: on inputting IDi and ciphertext CT, C searches the item IDi,Ki,SKi,Ti in L1. If Ti=1, A1 has made replacement of Ki, and it should give corresponding SKi of Ki to C. C executes CertGenpp,MSK,IDi,Ki and generates Certi of IDi. Then, it runs Decryptpp,CT,IDi,SKi,Certi to decrypt CT and sends the decryption result to A1.Challenge:A1 sends a challenge recipient set S=ID1,…,IDn, two user identities ID0∗,ID1∗, and a message M=y⟶ to C with the constraint that A1 neither queried Certi of IDi in S∪ID0∗,ID1∗ nor replaced Ki of IDi in S∪ID0∗,ID1∗ in Phase 1. C selects a bit μ∈0,1 and set Sμ∗=IDμ∗∪S at random. Then, it executes Encryptpp,M,Sμ∗,Ki and returns the generated challenge ciphertext CT∗ to A1.Phase 2:A1 issues a set of queries adaptively as in Phase 1 with the constraint that it is not able to query Certi of IDi in S∪ID0∗,ID1∗ or decryption of IDi in S∪ID0∗,ID1∗.Guess:A1 outputs a guess μ′∈0,1. It wins the game if μ′=μ. We define A1’s advantage in attacking the scheme to win ANO-CBIP-CCA Game 1 as AdvA1ANO−CBIP−CCAλ=Prμ′=μ−1/2.Definition 5.
We say that our proposed scheme is ANO-CBIP-CCA secure ifAdvA1ANO−CBIP−CCAλ<ε is satisfied for any PPT adversary A1.
ANO-CBIP-CCA Game 2 is played by a challengerC and an adversary A2.Setup:C runs the Setup 1λ,d algorithm and gives A2 the generated public parameters pp and the generated master secret key MSK.Phase 1:A2 adaptively launches the following queries to C. C maintains list L2=IDi,Ki,SKi for answering queries. We denote Ki=K1i,K2i and SKi=SK1i,SK2i. L2 was empty when it was initialized.OPublicKeyIDi: public keys’ query: on inputting IDi, C retrieves L2. If there is an item IDi,Ki,SKi related to IDi in L2, C returns corresponding Ki to A2. Otherwise, C runs KeyGenpp,IDi,x⟶i and generates Ki and SKi for IDi. It adds the new item IDi,Ki,SKi to L2 and returns Ki to A2.OSecretKeyIDi: secret keys’ query: on inputting IDi, C searches the item IDi,Ki,SKi related to IDi in L2 and returns SKi to A2.ODecryptIDi,CT: decrypt query: on inputting IDi and ciphertext CT, C searches the item IDi,Ki,SKi in L2. It executes CertGenpp,MSK,IDi,Ki and generates Certi for IDi. Then, C executes Decryptpp,CT,IDi,SKi,Certi to decrypt CT. It sends the decryption result to A2.Challenge:A2 sends a challenge recipient set S=ID1,…,IDn, two user identities ID0∗,ID1∗, and a message M=y⟶ to C with the constraint that A2 has not queried SKi of IDi in S∪ID0∗,ID1∗ in Phase 1. C selects a bit μ∈0,1 at random and set Sμ∗=IDμ∗∪S. Then, it executes Encryptpp,M,Sμ∗,Ki and returns the generated challenge ciphertext CT∗ to A2.Phase 2:A2 issues a set of queries adaptively as in Phase 1 with the constraint that it is not able to query SKi of IDi in S∪ID0∗,ID1∗ or decryption of IDi in S∪ID0∗,ID1∗.Guess:A2 outputs a guess μ′∈0,1. It wins the game if μ′=μ. We define A2’s advantage in attacking the scheme to win ANO-CBIP-CCA Game 2 as AdvA2ANO−CBIP−CCAλ=Prμ′=μ−1/2.Definition 6.
We say that our proposed scheme is ANO-CBIP-CCA secure ifAdvA2ANO−CBIP−CCAλ<ε is satisfied for any PPT adversary A2.


## 4. Our Certificate-Based Inner Product Broadcast Encryption Scheme

In this section, we present the concrete construction of our proposed scheme as follows.Setup1λ,d: taking the security parameter λ and vector length d as the input, the CA performs the following tasks:(1)
Generate symmetric cyclic bilinear groupsG and GT with order q. The large prime q is λ bits. g is a generator of group Ge:G×G⟶GT is a bilinear map, and gT=eg,g.(2)
Chooseγ∈Zq∗ randomly. Calculate g1=gγ.(3)
Select four cryptographic hash functions with forms asH1:=0,1∗×G×G⟶G, H2:=0,1∗×G×G×G⟶G, H3:=GT×GT⟶Zp∗, and H4:=GT⟶Zp∗.(4)
Keep theMSK=γ secretly and publish the public parameters pp=G,GT,d,q,g,e,gT,g1,H1,H2,H3,\\H4.KeyGenpp,IDi,x⟶i: taking the public parameters pp, a vector x⟶i, and an identity IDi as the input, the user IDi randomly chooses αi∈Zq. It has x⟶i∈Zqd. It generates secret keys SKi=SK1i,SK2i and public keys Ki=K1i,K2i by the following steps:(1)
CalculateSK1i=αi and SK2i=αix⟶i as secret keys(2)
ComputeK1i=gSK1i and K2i=gSK2i as public keysCertGenpp,MSK,IDi,Ki: taking public parameters pp, a master secret key MSK, a user’s identity IDi, and public keys K1i and K2i as the input, the CA computes Qi=H1IDi,K1i,K2i and Certi=Qiγ. The user IDi checks whether its Certi is valid. If eg,Certi = eg1, Qi, Certi is valid.Encryptpp,y⟶,S,K: taking the public parameters pp, a vector y⟶∈Zqd, the intended recipient set S, and public keys K1i and K2i as the input, the sender executes the algorithm to output a ciphertext CT. We suppose S = {ID1, ID2,..., IDn}.First, the sender computesQi = H1 (IDi, K1i, K2i) and Ri = H2 (IDi, K1i, K2i, g1) for every intended recipient IDi.Next, the sender choosesk∈GT and β∈Zq∗ at random. It selects ri∈Zq∗ at random and computes χi=eg,Qi−ri⋅eK1i,Ri−ri.Then, the sender computes ciphertextCT as shown in equations:(2)Ci_0=gri,(3)Ci_1=Di_1⋅eg1,Qi−ri=eK1i,gβ⋅eg1,Qi−ri,(4)Ci_2=Di_2⋅eK1i,Ri−ri=eK2i,gβy⟶⋅eK1i,Ri−ri,(5)Ci_3=ri⊕H3Di_1,Di_2,(6)Ci=H4χi,Ci_0,Ci_1,Ci_2,Ci_3,(7)CT=C1,C2,…,Cn.Decryptpp,CT,IDi,SKiCerti: taking the public parameters pp, a ciphertext CT, a user’s identity IDi, a certificate Certi, and secret keys SK1i and SK2i as the input, the user performs the following steps.First, the user calculatesχi′=eCi_0,Certi−1⋅eCi_0,Ri−SK1i.Next, the user computesH4χi′. If the user is not an intended recipient, it is not able to find the same value H4χi in CT and is not able to determine the corresponding Ci_1 and Ci_2 of H4χi′. Then, it outputs ⊥. Otherwise, the user utilizes H4χi′ to locate its associated Ci by relationships among H4χi′, Ci_1, and Ci_2 in Ci.Then, the user computesDi_1=Ci_1⋅eCi_0,Certi and Di_2=Ci_2⋅eCi_0,RiSK1i.Then, the user calculatesCi_0′ as the following:(8)ri′=Ci_3′⊕H3Di_1,Di_2,Ci_0′=gri′.Finally, ifCi_0′=Ci_0, the user calculates z∈T which satisfies Di_1z=Di_2. Let T be a polynomial-sized subset of Zq. If there exists z∈T, the algorithm outputs z. Otherwise, it outputs ⊥.Correctness: our proposed scheme is said to satisfy the correct condition if the following equation holds:(9)χi′=eCi_0,Certi−1⋅eCi_0,Ri−SK1i=egri,Qiγ−1⋅egri,Ri−SK1i=eg1,Qi−ri⋅eK1i,Ri−ri=χi.Meanwhile, it requires the plaintext vectors to satisfy<x⟶i,y⟶>∈T, for polynomially sized T.For anySK1i,SK2i and K1i,K2i, we have(10)Di_1=Ci_1⋅eCi_0,Certi=eK1i,gβ⋅eg1,Qi−ri⋅eCi_0,Certi=egαi,gβ=eg,gαiβ,Di_2=Ci_2⋅eCi_0,RiSK1i=eK2i,gβ⋅y⟶⋅eK1i,Ri−ri⋅eCi_0,RiSK1i=egαixi⟶,gβy⟶=eg,gαiβ⋅x⟶iy⟶T=eg,gαiβ⋅x⟶i,y⟶.Ifx⟶i,y⟶∈T, the decryption algorithm outputs inner product value x⟶i,y⟶ by the baby-step giant-step algorithm. It is efficient since T=polyλ.


## 5. Security Analysis

Now, we prove the confidentiality and anonymity of our scheme through the security models defined in Section3. Our proof strategy draws inspiration from the CBBE scheme [32]. First, the confidentiality of our scheme will be proved through IND-CBIP-CCA Game 1 and IND-CBIP-CCA Game 2 defined in Section 3.Theorem 1.
Suppose that hash functionsHii=1,2,3,4 are random oracles and A1 is able to launch qcert queries to OCertificate, qdec queries to ODecrypt, and qHii=1,2,3,4 queries to Hii=1,2,3,4, respectively. It has advantage ε over our proposed scheme in IND-CBIP-CCA Game 1. Then, there exists an PPT algorithm ℬ to solve the CBDH problem with the advantage at least nε/qH3N1−qdec/2λqH1−1/qH1qcert.Proof.
Suppose that there exists an adversaryA1 that can break the proposed scheme in IND-CBIP-CCA Game 1 with advantage ε. We build an algorithm ℬ to solve the CBDH problem by running A1. Given as the input a problem instance g,ga,gb,gc, ℬ needs to simulate a challenger C and all oracles. It works as follows.
Setup:ℬ executes the Setup1λ,d algorithm and outputs q,G,GT,e. We note that g is the generator of G, and g1=gγ. Then, ℬ computes gT=eg,g and picks index ℓ∈1,2,…,qH1 at random. ℬ controls random oracles Hii=1,2,3,4. It also publishes system public parameters pp=G,GT,d,q,g,e,gT,g1,H1,H2,H3,\\H4 and keeps master secret key MSK=γ.
H1 query: A1 makes the H1 query adaptively. ℬ responds to A1’s query on IDi,Ki as shown below. ℬ maintains the list LH1=IDi,Ki,Qi,Certi. If the query IDi appears on LH1 in an item IDi,Ki,Qi,Certi, it returns corresponding Qi to A1. Otherwise, if the query is on IDℓ, ℬ sets Qℓ=gb, returns Qℓ to A1, and adds IDℓ,Kℓ,Qℓ,⊥ to LH1. Note that Kℓ=K1ℓ,K2ℓ. Otherwise, ℬ does the following things:(1)
Selectti∈Zp∗ at random. Let Qi=gti and Certi=gati.(2)
Add the tupleIDi,Ki,Qi,Certi to LH1 and respond with Qi to A1.
H2 query: A1 makes H2 query adaptively. ℬ makes a response to A1’s query on IDi,Ki,g1 as shown below. ℬ maintains the list LH2=IDi,Ki,vi,Ri. If the query IDi,Ki appears on LH2 in an item IDi,Ki,vi,Ri, it returns corresponding Ri to A1. Else, ℬ picks vi∈Zp∗ at random and calculates Ri=gvi, and then ℬ adds IDi,Ki,vi,Ri to LH2 and responds to A1 with Ri.
H3 query: A1 makes the H3 query adaptively. ℬ responds to A1’s query on Di_1,Di_2 as shown below. ℬ maintains the list LH3=Di_1,Di_2,h3. If the query Di_1,Di_2 appears on LH3 in an item Di_1,Di_2,h3, ℬ returns corresponding h3 to A1. Otherwise, ℬ picks h3∈Zp∗ at random, adds Di_1,Di_2,h3 to LH3, and responds to A1 with h3.
H4 query: A1 makes the H4 query adaptively. ℬ responds to A1’s query on IDi as shown below. ℬ maintains the list LH4=IDi,h4. If the query IDi appears on LH4 in an item IDi,h4, ℬ returns corresponding h4 to A1. Otherwise, ℬ picks h4∈Zp∗ at random, adds IDi,h4 to LH4, and returns h4 to A1.
OPublicKey query: A1 makes the OPublicKey query adaptively. ℬ responds to A1’s query on IDi as shown below. If the query IDi is already on L1 in an item IDi,Ki,SKi,Ti, ℬ returns corresponding Ki to A1. Otherwise, ℬ randomly picks αi′∈Zp and x⟶i′∈Zqd, and then it computes SK1i=αi′ and SK2i=αix⟶i′ as secret keys. It computes K1i=gSK1i and K2i=gSK2i as public keys, and then it adds IDi,Ki,SKi,Ti to L1 and responds to A1 with Ki.
OPublicKeyReplace query: A1 makes the OPublicKeyReplace query adaptively. On receiving the query on IDi,Ki,SKi,Ti, ℬ retrieves items related to IDi in L1 and updates the item IDi,Ki,SKi,Ti to IDi,Ki′,⊥,1.
OSecretKey query: A1 makes the OSecretKey query adaptively. On receiving the query on IDi, ℬ searches the entry IDi,Ki,SKi,Ti of IDi. If Ti=0, ℬ returns SKi to A1. Otherwise, ℬ aborts.
OCertificate query: A1 makes the OCertificate query adaptively. On receiving the query on IDi, if IDi=IDℓ, ℬ aborts. Otherwise, ℬ searches the item IDi,Ki,Qi,Certi of IDi and responds to A1 with Certi.
ODecrypt query: A1 makes the ODecrypt query adaptively by submitting CT and IDi to ℬ. We note that CT=C1,C2,…,Cn and n≤N. ℬ responds to the query from A1 on IDi,CT as shown in the following:(1)
ℬ searches item IDi,Ki,SKi,Ti of list L1. If the user of IDi is not an intended recipient, it rejects the query.(2)
IfIDℓ is in the intended recipient set and Ti=0, ℬ searches the list LH3 to find the entry Di_1,Di_2,h3 that satisfies Ci_0=gri and Ci_3=ri⊕H3Di_1,Di_2. If there is no item that satisfies the condition, ℬ discards CT and aborts. Else, ℬ responds to A1 with Di_1,Di_2.(3)
IfIDℓ is not in the intended recipient set and Ti=1, A1 should give SKi corresponding to Ki of IDi. Then, ℬ checks whether K1i=gSK1i and K2i=gSK2i hold. If not so, ℬ aborts. Otherwise, ℬ searches LH3 to find the entry Di_1,Di_2,h3 that satisfies Ci_0=gri and Ci_3=ri⊕H3Di_1,Di_2. If there is no item that satisfies the condition, ℬ rejects the query. Otherwise, it returns Di_1,Di_2 to the adversary A1.(4)
Otherwise,ℬ obtains SKi and Certi which are related to IDi, and then ℬ executes Decryptpp,CT,IDi,SKi,Certi and responds to A1 with the result.
Phase 1: during this phase,ℬ issues the above queries launched by A1 adaptively. For responding to the queries, ℬ maintains a list L1=IDi,Ki,SKi,Ti. This list was initially empty. Ti=0 represents that Ki has not been replaced by A1. Otherwise, Ti=1 means that A1 has made replacement of Ki.
Challenge:A1 submits the intended recipient set S∗=ID1,ID2,ID3,…,IDn,n≤N, two distinct messages M0,M1 and M0=y⟶0andM1=y⟶1, and then x⟶,y⟶0=x⟶,y⟶1. It sends M0,M1 to the challenger C, with the requirement that, in Phase 1, it neither obtained certificates of users in S∗ nor made replacement of Ki for IDi in S∗. Then, ℬ randomly selects a value Mμ,μ∈0,1. If IDℓ is not in S∗, ℬ aborts. Else, ℬ sets Ci_0∗=gc and chooses H4χi∗∈Zp∗, Ci_1∗∈GT, Ci_2∗∈GT, and Ci_3∗∈GT at random. Then, the challenge broadcast ciphertext CT∗=C1∗,C2∗,…,Cn∗ is returned to A1.
Phase 2:A1 issues a serious of queries adaptively. However, it cannot issue queries for certificates or decryption of IDi in S∗.
Guess:A1 outputs a guess μ′∈0,1 for μ. It wins the game if μ′=μ. For IDℓ, the description of CT∗ is shown as follows. To produce the result, ℬ should calculate Di_1 and Di_2 correctly. ℬ chooses an item from LH3 at random and searches vℓ from the item IDℓ,Kℓ,vℓ,Rℓ. To solve the CBDH problem, ℬ computes Ts=Di_1⋅Di_2/Cℓ_1∗⋅Cℓ_2∗⋅eKℓ,Cℓ_0∗vℓ as the solution.
IfDi_1=C1ℓ_1∗⋅eCℓ_0∗,Certℓ and Di_2=Cℓ_2∗⋅eCℓ_0∗,RℓSK1ℓ, then Cℓ_1∗=Di_1/eCℓ_0∗,Certℓ and Cℓ_2∗=Di_2/eCℓ_0∗,RℓSK1ℓ. ℬ can extract the solution Ts=Di_1⋅Di_2/Cℓ_1∗⋅Cℓ_2∗⋅eKℓ,Cℓ_0∗vℓ=eg,gabc.
Analysis: then, we analyze the probability that the given CBDH problem can be solved by the challengerC.
Ifℬ does not abort during the game, then A1’s view is identical to its view in the real scheme. Furthermore, we have Prμ′=μ−1/2≥ϵ. The game may be aborted before it finishes. Let Abort denote the game is aborted before it finishes. Then, event Abort occurs under any of the following occasions. 1Ab1:IDℓ is not in S∗ during the Challenge phase. We have PrAb1=N−n/N. 2Ab2:ℬ aborts in the period that CT is given to ODecrypt. We have PrAb2=qdec/2λ. 3Ab3:A1 issues OCertificate query on PrAb2=qdec/2λ. We have Pr¬Ab3=qH1−1/qH1qcert. 4Ab4:A1 issues OSecret query on IDi, and A1 has made replacement of Ki for IDi. If ¬Ab2 occurs, then ¬Ab4 also occurs. So, Pr¬Abort=Pr¬Ab1∧¬Ab2∧¬Ab3∧¬Ab4≥n/N1−qdec/2λqH1−1/qH1qcert.
Let Oca denoteH3Query|¬Abort. So, we have Prμ′=μ|¬Oca=1/2 and Prμ′=μ≤1/2PrOca+1. By the definition of the probability for A1 in IND-CBIP-CCA Game 1, we have ε≤2|Prμ′=μ−1/2|≤PrOca≤PrH3Query/Pr¬Abort. So, we have PrH3Query≥εPr¬Abort≥nε/N1−qdec/2λqH1−1/qH1qcert. Finally, ℬ selects the correct item from LH3 with probability 1/qH3. Consequently, ℬ’s advantage is at least nε/qH3N1−qdec/2λqH1−1/qH1qcert as required.Theorem 2.
Suppose that hash functionsHii=1,2,3,4 are random oracles and A1 is able to launch qpubkey queries to OPublicKey, qseckey queries to OSecretKey, qdec queries to ODecrypt, and qHii=1,2,3,4 to functions Hii=1,2,3,4, respectively. It has advantage ε over our proposed scheme in IND-CBIP-CCA Game 2. Then, there exists a PPT algorithm ℬ to solve the CBDH problem with the advantage at least nε/qH3N1−qdec/2λqpubkey−1/qpubkeyqseckey.Proof.
Suppose that there exists an adversaryA2 that can break the proposed scheme in IND-CBIP-CCA Game 2 with advantage ε. We build an algorithm ℬ to solve the CBDH problem by running A2. Given as the input a problem instance g,ga,gb,gc, ℬ needs to simulate a challenger C and all oracles. It works as follows.
Setup:ℬ executes the Setup1λ,d algorithm and outputs q,G,GT,e. We note that g is the generator of G and g1=gγ. Then, ℬ computes gT=eg,g and picks index ℓ∈1,2,…,q at random. ℬ controls random oracles Hii=1,2,3,4. It also publishes system public parameters pp=G,GT,d,q,g,e,gT,g1,H1,H2,H3,H4 and gives master secret key MSK=γ to A2. Random oracles Hii=1,2,3,4 are controlled by ℬ.
H1 query: A2 makes the H1 query adaptively. ℬ makes a response to A2’s query on IDi,Ki as shown below. It maintains the list LH1=IDi,Ki,Qi. If the query IDi appears on LH1 in an item IDi,Ki,Qi, it returns corresponding Qi to A2. Else, ℬ chooses Qi∈G at random. Then, it adds IDi,Ki,Qi to LH1 and responds with Qi to A2.
H2 query: A2 makes the H2 query adaptively. ℬ makes a response to A2’s query on IDi,Ki,g1 as shown below. ℬ maintains the list LH2=IDi,Ki,Ri. If the query IDi,Ki appears on LH2 in an item IDi,Ki,Ri, it returns corresponding Ri to A2. Else, if IDi=IDℓ, it sets Rℓ=ga, returns Rℓ to A2, and adds IDi,Ki,Ri to LH2. Note that Kℓ=K1ℓ,K2ℓ. Otherwise, ℬ randomly selects Ri∈G. It adds IDi,Ki,Ri to the list LH2 and responds with Ri to A2.
H3 query: A2 makes the H3 query adaptively. ℬ responds to A2’s query on Di_1,Di_2 as shown below. ℬ maintains the list LH3=Di_1,Di_2,h3. If the query Di_1,Di_2 appears on LH3 in an item Di_1,Di_2,h3, ℬ returns corresponding h3 to A2. Otherwise, ℬ picks h3∈Zp∗ at random, adds Di_1,Di_2,h3 to LH3, and responds to A2 with h3.
H4 query: A2 makes the H4 query adaptively. ℬ makes a response to A2’s query on IDi as shown below. ℬ has the list LH4=IDi,h4. If the query IDi appears on LH4 in an item IDi,h4, ℬ returns corresponding h4 to A2. Otherwise, ℬ picks h4∈Zp∗ at random, adds IDi,h4 to LH4, and returns h4 to A2.
OPublicKey query: A2 makes the OPublicKey query adaptively. ℬ makes a response to A2’s query on IDi as shown below. If the query IDi appears on LH2 in an item IDi,Ki,Ri, ℬ returns related Ki to A2. Otherwise, if the query is on IDℓ, ℬ randomly selects x⟶i′∈Zqd. Then, it returns K1ℓ=gb and K2ℓ=gb⋅x⟶i′ to A2 and adds IDℓ,Kℓ,⊥ to L2, while Kℓ=K1ℓ,K2ℓ. The secret key SK1ℓ=b is unknown to ℬ. Else, ℬ randomly picks αi′∈Zp and x⟶i′∈Zqd, and then ℬ computes SK1i=αi′ and SK2i=αix⟶i′ as secret keys. It computes K1i=gSK1i and K2i=gSK2i as public keys, and then it adds IDi,Ki,SKi to L2 and returns Ki to A2.
OSecretKey query: A2 makes the OSecretKey query adaptively. On receiving the query on IDi, if IDi=IDℓ, ℬ aborts. Otherwise, ℬ searches the entry IDi,Ki,SKi of IDi in L2 and returns SKi to A2.
ODecrypt query: A2 makes the ODecrypt query adaptively by submitting CT and IDi to ℬ. We note that CT=C1,C2,…,Cn and n≤N. ℬ makes a response to the query from A2 on IDi,CT as shown in the following:(1)
ℬ searches item IDi,Ki,SKi of list L2. If the user of IDi is not an intended recipient, it rejects the query.(2)
IfIDℓ is in the intended recipient set, ℬ searches LH3 to find the entry Di_1,Di_2,h3 that satisfies Ci_0=gri and Ci_3=ri⊕H3Di_1,Di_2. If there is no item that satisfies the condition, ℬ rejects the query. Otherwise, it returns Di_1andDi_2 to the adversary A2.(3)
Otherwise,ℬ obtains SKi and Certi which are related to IDi, and then ℬ executes Decryptpp,CT,IDi,SKi,Certi and responds to A2 with the result.
Phase 1: during this phase,ℬ issues the above queries launched by A2 adaptively. For responding to the queries, ℬ maintains a list L2=IDi,Ki,SKi. This list was initially empty.
Challenge: whenA2 decides that Phase 1 is over, it submits the intended recipient set S∗=ID1,ID2,ID3,…,IDn,n≤N, two distinct messages M0,M1 and M0=y⟶0andM1=y⟶1, and then x⟶,y⟶0=x⟶,y⟶1. It sends M0,M1 to the challenger C, with the requirement that, in Phase 1, it has not obtained SKi of IDi in S∗. Then, ℬ selects a random value Mμ,μ∈0,1. If IDℓ is not in S∗, ℬ aborts. Else, it sets Ci_0∗=gc and chooses H4χi∗∈Zp∗, Ci_1∗∈GT, Ci_2∗∈GT, and Ci_3∗∈GT at random. Then, the challenge broadcast ciphertext CT∗=C1∗,C2∗,…,Cn∗ is returned to the adversary A2.
Phase 2:A2 issues a set of queries adaptively. However, it cannot issue queries for SKi of IDi in S∗ or decryption of IDi in S∗.
Guess:A2 outputs a guess μ′∈0,1 for μ. It wins the game if μ′=μ. For IDℓ, the description of CT∗ is shown as follows. To produce the result, ℬ should calculate Di_1 and Di_2 correctly. ℬ chooses an item from LH3 at random and searches vℓ from the item IDℓ,Kℓ,vℓ,Rℓ. To solve the CBDH problem, ℬ computes T=Di_1⋅Di_2/Cℓ_1∗⋅Cℓ_2∗⋅eKℓ,Cℓ_0∗vℓ as the solution.
IfDi_1=C1ℓ_1∗⋅eCℓ_0∗,Certℓ and Di_2=Cℓ_2∗⋅eCℓ_0∗,RℓSK1ℓ, then Cℓ_1∗=Di_1/eCℓ_0∗,Certℓ and Cℓ_2∗=Di_2/eCℓ_0∗,RℓSK1ℓ. ℬ can extract the solution T=Di_1⋅Di_2/Cℓ_1∗⋅Cℓ_2∗⋅eCℓ_0∗α,Qℓ=eg,gabc.
Analysis: then, we analyze the probability that the given CBDH problem can be solved by the challengerC.
Ifℬ does not abort during the game, then A2’s view is identical to its view in the real scheme. Furthermore, we have Prμ′=μ−1/2≥ϵ. The game may be aborted before it finishes. Let Abort denote the game is aborted before it finishes. Then, event Abort occurs under any of the following occasions. 1Ab1: the adversary A2 queries the oracle OSecretKey on the user IDℓ. We have Pr¬Ab1=qpubkey−1/qpubkeyqseckey. 2Ab2:ℬ aborts in the period that CT is given to ODecrypt. We have PrAb2=qdec/2λ. 3Ab3:IDℓ is not in S∗ during the Challenge phase. We have PrAb3=N−n/N. So, we have that Pr¬Abort=Pr¬Ab1∧¬Ab2∧¬Ab3≥n/N1−qdec/2λqpubkey−1/qpubkeyqseckey.
Let Oca denoteH3Query|¬Abort. So, we have Prμ′=μ|¬Oca=1/2 and Prμ′=μ=1/2PrOca+1. By the definition of the advantage for A2 in IND-CBIP-CCA Game 2, we have ε≤2|Prμ′=μ−1/2|≤PrOca≤PrH3Query/Pr¬Abort. So, we have PrH3Query≥εPr¬Abort≥nε/N1−qdec/2λqpubkey−1/qpubkeyqseckey. Finally, ℬ selects the correct item from LH3 with probability 1/qH3. Consequently, ℬ’s advantage is at least nε/qH3N1−qdec/2λqpubkey−1/qpubkeyqseckey as required.Next, the anonymity of our scheme will be proved through ANO-CBIP-CCA Game 1 and ANO-CBIP-CCA Game 2 defined in Section3.Theorem 3.
Suppose that hash functionsHii=1,2,3,4 are random oracles and A1 is able to launch qcert queries to OCertificate and qHii=1,2,3,4 queries to functions Hii=1,2,3,4, respectively. It has advantage ε over our proposed scheme in ANO-CBIP-CCA Game 1. Then, there exists aPPT algorithm ℬ to solve the CBDH problem with the advantage at least nε/qH3N1−qdec/2λqH1−1/qH1qcert.Proof.
Suppose that there exists an adversaryA1 that can break the proposed scheme in ANO-CBIP-CCA Game 1 with advantage ε. We build an algorithm ℬ to solve the CBDH problem by running A1. Given as the input a problem instance g,ga,gb,gc, ℬ needs to simulate a challenger C and all oracles. It works as follows.
Setup:ℬ executes the Setup1λ,d algorithm and outputs q,G,GT,e. We note that g is the generator of G and g1=gγ. Then, ℬ computes gT=eg,g and picks index ℓ∈1,2,…,qH1 at random. ℬ controls random oracles Hii=1,2,3,4. It also publishes system public parameters pp=G,GT,d,q,g,e,gT,g1,H1,H2,H3,H4 and keeps master secret key MSK=γ.
H1 query: A1 makes the H1 query adaptively. ℬ responds to A1’s query on ℬ as shown below. ℬ maintains the list LH1=IDi,Ki,Qi,Certi. If the query IDi appears on LH1 in an item IDi,Ki,Qi,Certi, it returns corresponding Qi to A1. Otherwise, if the query is on IDℓ, ℬ sets Qℓ=gb, returns Qℓ to A1, and adds IDℓ,Kℓ,Qℓ,⊥ to LH1. Note that Kℓ=K1ℓ,K2ℓ. Otherwise, ℬ does the following things:(1)
Selectti∈Zp∗ at random. Let Qi=gti and Certi=gati.(2)
Add the tupleIDi,Ki,Qi,Certi to LH1 and respond with Qi to A1.
H2 query: A1 makes the H2 query adaptively. ℬ makes a response to A1’s query on IDi,Ki,g1 as shown below. ℬ maintains the list LH2=IDi,Ki,vi,Ri. If the query IDi,Ki appears on LH2 in an item IDi,Ki,vi,Ri, it returns corresponding Ri to A1. Else, ℬ picks vi∈Zp∗ at random and calculates Ri=gvi, and then ℬ adds IDi,Ki,vi,Ri to LH2 and responds to A1 with Ri.
H3 query: A1 makes the H3 query adaptively. ℬ responds to A1’s query on Di_1,Di_2 as shown below. ℬ maintains the list LH3=Di_1,Di_2,h3. If the query Di_1,Di_2 appears on LH3 in an item Di_1,Di_2,h3, ℬ returns corresponding h3 to A1. Otherwise, ℬ picks h3∈Zp∗ at random, adds Di_1,Di_2,h3 to LH3, and responds to A1 with h3.
H4 query: A1 makes the H4 query adaptively. ℬ responds to A1’s query on IDi as shown below. ℬ maintains the list LH4=IDi,h4. If the query IDi appears on LH4 in an item IDi,h4, ℬ returns corresponding h4 to A1. Otherwise, ℬ picks h4∈Zp∗ at random, adds IDi,h4 to LH4, and returns h4 to A1.
OPublicKey query: A1 makes the OPublicKey query adaptively. ℬ responds to A1’s query on IDi as shown below. If the query IDi is already on L1 in an item IDi,Ki,SKi,Ti, ℬ returns corresponding Ki to A1. Otherwise, ℬ randomly picks αi′∈Zp and x⟶i′∈Zqd, and then it computes SK1i=αi′ and SK2i=αixi, as secret keys. It computes K1i=gSK1i and K2i=gSK2i as public keys, and then it adds IDi,Ki,SKi,Ti to L1 and responds to A1 with Ki.
OPublicKeyReplace query: A1 makes the OPublicKeyReplace query adaptively. On receiving the query on IDi,Ki′,SKi,Ti, ℬ retrieves items related to IDi in L1 and updates the item IDi,Ki,SKi,Ti to IDi,Ki′,⊥,1.
OSecretKey query: A1 makes the OSecretKey query adaptively. On receiving the query on IDi, ℬ searches the entry IDi,Ki,SKi,Ti of IDi. If Ti=0, ℬ returns SKi to A1. Otherwise, ℬ aborts.
OCertificate query: A1 makes the OCertificate query adaptively. On receiving the query on IDi, if IDi=IDl, ℬ aborts. Otherwise, ℬ searches the item IDi,Ki,Qi,Certi of IDi and responds to A1 with Certi.
ODecryptquery:A1makes theODecryptquery adaptively by submittingCTandIDitoℬ. We note thatCT=C1,C2,…,Cnandn≤N.ℬresponds to the query fromA1onIDi,CTas shown in the following:(1)
ℬ searches item IDi,Ki,SKi,Ti of list L1. If the user of IDi is not an intended recipient, it rejects the query.(2)
IfIDℓ is in the intended recipient set and Ti=0, ℬ searches list LH3 to find the entry Di_1,Di_2,h3 that satisfies Ci_0=gri and Ci_3=ri⊕H3Di_1,Di_2. If there is no item that satisfies the condition, ℬ discards CT and aborts. Else, ℬ responds to A1 with Di_1,Di_2.(3)
IfIDℓ is not in the intended recipient set and Ti=1,A1should give SKi corresponding to Ki of IDi. Then, ℬ checks whether K1i=gSK1i and K2i=gSK2i hold. If not so, ℬ aborts. Otherwise, ℬ searches LH3 to find the entry Di_1,Di_2,h3 that satisfies Ci_0=gri and Ci_3=ri⊕H3Di_1,Di_2. If there is no item that satisfies the condition, ℬ rejects the query. Otherwise, it returns Di_1,Di_2 to the adversary A1.(4)
Otherwise,ℬ obtains SKi and Certi which are related to IDi, and then ℬ executes Decryptpp,CT,IDi,SKi,Certi and responds to A1 with the result.
Phase 1: during this phase,ℬ issues the above queries launched by A1 adaptively. For responding to the queries, ℬ maintains a list L1=IDi,Ki,SKi,Ti. This list was initially empty. Ti=0 represents that Ki has not been replaced by A1. Otherwise, Ti=1 means that A1 has made replacement of Ki.
Challenge:A1 submits the intended recipient set S=ID1,ID2,ID3,…,IDn,n≤N, message M=y⟶, and two user identities ID0∗,ID1∗ to the challenger C, with the requirement that, in Phase 1, it neither obtained certificates of users in S∪ID0∗,ID1∗ nor made replacement of Ki for IDi in S∪ID0∗,ID1∗. Then, ℬ randomly selects a value μ∈0,1 and sets Sμ∗=S∪IDμ∗. If IDℓ is not in S∗, ℬ aborts. Else, ℬ sets Ci_0∗=gc and chooses H4χi∗∈Zp∗, Ci_1∗∈GT, Ci_2∗∈GT, and Ci_3∗∈GT at random. Then, the challenge broadcast ciphertext CT∗=C1∗,C2∗,…,Cn∗ is returned to A1.
Phase 2:A1 issues a serious of queries adaptively. However, it cannot issue queries for certificates or decryption of IDi in S∗∪ID0∗,ID1∗.
Guess:A1 outputs a guess μ′∈0,1 for μ. It wins the game if μ′=μ. For IDℓ, the description of CT∗ is shown as follows. To produce the result, ℬ should calculate Di_1 and Di_2 correctly.ℬ chooses an item from LH3 at random and searches vℓ from the item IDℓ,Kℓ,vℓ,Rℓ. To solve the CBDH problem, ℬ computes Ts=Di_1⋅Di_2/Cℓ_1∗⋅Cℓ_2∗⋅eKℓ,Cℓ_0∗vℓ as the solution.
IfDi_1=C1ℓ_1∗⋅eCℓ_0∗,Certℓ and Di_2=Cℓ_2∗⋅eCℓ_0∗,RℓSK1ℓ, then Cℓ_1∗=Di_1/eCℓ_0∗,Certℓ and Cℓ_2∗=Di_2/eCℓ_0∗,RℓSK1ℓ.ℬ can extract the solution Ts=Di_1⋅Di_2/Cℓ_1∗⋅Cℓ_2∗⋅eKℓ,Cℓ_0∗vℓ=eg,gabc.
Analysis: then, we analyze the probability that the given CBDH problem can be solved by the challengerC.
Ifℬ does not abort during the game, then A1’s view is identical to its view in the real scheme. Furthermore, we have Prμ′=μ−1/2≥ϵ. The game may be aborted before it finishes. Let Abort denote the game is aborted before it finishes. Then, event Abort occurs under any of the following occasions. 1Ab1:IDℓ is not in S∗ during the Challenge phase. We have PrAb1=N−n/N.2Ab2:ℬ aborts in the period that CT is given to ODecrypt. We have PrAb2=qdec/2λ.3Ab3:A1 issues OCertificate query on IDℓ. We have Pr¬Ab3=qH1−1/qH1qcert.4Ab4:A1 issues OSecret query on IDi, and A1 has made replacement of Ki for IDi. If ¬Ab2 occurs, then ¬Ab4 also occurs. So, Pr¬Abort=Pr¬Ab1∧¬Ab2∧¬Ab3∧¬Ab4≥n/N1−qdec/2λqH1−1/qH1qcert.
Let Oca denoteH3Query|¬Abort. So, we have Prμ′=μ|¬Oca=1/2 and Prμ′=μ≤1/2PrOca+1. By the definition of the probability for A1 in ANO-CBIP-CCA Game 1, we have ε≤2|Prμ′=μ−1/2|≤PrOca≤PrH3Query/Pr¬Abort. So, we have PrH3Query≥εPr¬Abort≥nε/N1−qdec/2λqH1−1/qH1qcert. Finally, ℬ selects the correct item from LH3 with probability 1/qH3. Consequently, ℬ’s advantage is at least nε/qH3N1−qdec/2λqH1−1/qH1qcert as required.Theorem 4.
Suppose that hash functionsHii=1,2,3,4 are random oracles and A1 is able to launch qpubkey queries toOPublicKey , qseckey queries to OSecretKey, qdec queries to ODecrypt, and qHii=1,2,3,4 to functions Hii=1,2,3,4, respectively. It has advantage ε over our proposed scheme in ANO-CBIP-CCA Game 2. Then, there exists a PPT algorithm ℬ to solve the CBDH problem with the advantage at least nε/qH3N1−qdec/2λqpubkey−1/qpubkeyqseckey.Proof.
Suppose that there exists an adversaryA2 that can break the proposed scheme in ANO-CBIP-CCA Game 2 with advantage ε. We build an algorithm ℬ to solve the CBDH problem by running A2. Given as the input a problem instance g,ga,gb,gc, A2 needs to simulate a challenger C and all oracles. It works as follows.
Setup:ℬ executes the Setup1λ,d algorithm and outputs q,G,GT,e. We note that g is the generator of G and g1=gγ. Then, ℬ computes gT=eg,g and picks index ℓ∈1,2,…,q at random. ℬ controls random oracles Hii=1,2,3,4. It also publishes system public parameters pp=G,GT,d,q,g,e,gT,g1,H1,H2,H3,H4 and gives master secret key MSK=γ to A2. Random oracles Hii=1,2,3,4 are controlled by ℬ.
H1 query: A2 makes the H1 query adaptively. ℬ makes a response to A2’s query on IDi,Ki as shown below. It maintains the list LH1=IDi,Ki,Qi. If the query IDi appears on LH1 in an item IDi,Ki,Qi, it returns corresponding Qi to A2. Else, ℬ chooses Qi∈G at random. Then, it adds IDi,Ki,Qi to LH1 and responds with Qi to A2.
H2 query: A2 makes the H2 query adaptively. ℬ makes a response to A2’s query on IDi,Ki,g1 as shown below. ℬ maintains the list LH2=IDi,Ki,Ri. If the query IDi,Ki appears on LH2 in an item IDi,Ki,Ri, it returns corresponding Ri to A2. Else, if IDi=IDℓ, it sets Rℓ=ga, returns Rℓ to A2, and adds IDℓ,Kℓ,Rℓ to LH2. Note that Kℓ=K1ℓ,K2ℓ. Otherwise, ℬ randomly selects Ri∈G. It adds IDi,Ki,Ri to the list LH2 and responds with Ri to A2.
H3 query: A2 makes the H3 query adaptively. H3 responds to A2’s query on Di_1,Di_2 as shown below. H3 maintains the list LH3=Di_1,Di_2,h3. If the query Di_1,Di_2 appears on LH3 in an item Di_1,Di_2,h3, ℬ returns corresponding h3 to A2. Otherwise, ℬ picks h3∈Zp∗ at random, adds Di_1,Di_2,h3 to LH3 and responds to A2 with h3.
H4 query: A2makes theH4query adaptively.ℬmakes a response toA2’s query onIDias shown below.ℬhas the listLH4=IDi,h4. If the query IDi appears on LH4 in an item IDi,h4, ℬ returns corresponding h4 to A2. Otherwise, ℬ picks h4∈Zp∗ at random, adds IDi,h4 to LH4, and returns h4 to A2.
OPublicKey query: A2 makes the OPublicKey query adaptively. ℬ makes a response to A2’s query on IDi as shown below. If the query IDi appears on LH2 in an item IDi,Ki,Ri, ℬ returns related Ki to A2. Otherwise, if the query is on IDℓ, ℬ randomly selects x⟶i′∈Zqd. Then, it returns K1ℓ=gb and K2ℓ=gb⋅x⟶i′ to A2 and adds IDℓ,Kℓ,⊥ to L2 while Kℓ=K1ℓ,K2ℓ. The secret key SK1ℓ=b is unknown to ℬ. Else, ℬ randomly picks αi′∈Zp and x⟶i′∈Zqd, and then ℬ computes SK1i=αi′ and SK2i=αix⟶i′ as secret keys. It computes K1i=gSK1i and K2i=gSK2i as public keys, and then it adds IDi,Ki,SKi to L2 and returns Ki to A2.
OSecretKey query: A2 makes the OSecretKey query adaptively. On receiving the query on IDi, if IDi=IDℓ, ℬ aborts. Otherwise, ℬ searches the entry IDi,Ki,SKi of IDi in L2 and returns SKi to A2.
ODecrypt query: A2 makes the ODecrypt query adaptively by submitting CT and IDi to ℬ. We note that CT=C1,C2,…,Cn and n≤N. ℬ makes a response to the query from A2 on IDi,CT as shown in the following:(1)
ℬ searches item IDi,Ki,SKi of list L2. If the user of IDi is not an intended recipient, it rejects the query.(2)
IfIDℓ is in the intended recipient set, ℬ searches LH3 to find the entry Di_1,Di_2,h3 that satisfies Ci_0=gri and Ci_3=ri⊕H3Di_1,Di_2. If there is no item that satisfies the condition, ℬ rejects the query. Otherwise, it returns Di_1,Di_2 to the adversary A2.(3)
Otherwise,ℬ obtains SKi and Certi which are related to IDi, and then ℬ executes Decryptpp,CT,IDi,SKi,Certi and responds to A2 with the result.
Phase 1: during this phase,ℬ issues the above queries launched by A2 adaptively. For responding to the queries, ℬ maintains a list L2=IDi,Ki,SKi. This list was initially empty.
Challenge: whenA2 decides that Phase 1 is over, it submits the intended recipient set S∗=ID1,ID2,ID3,…,IDn,n≤N, two distinct messages M0,M1 and M0=y⟶0,M1=y⟶1, and then x⟶,y⟶0=x⟶,y⟶1. It sends M0,M1 to the challenger C, with the requirement that, in Phase 1, it has not obtained SKi of IDi in S∗. Then, ℬ selects a random value Mμ,μ∈0,1. If IDℓ is not in S∗, ℬ aborts. Else, it sets Ci_0∗=gc and chooses H4χi∗∈Zp∗, Ci_1∗∈GT, Ci_2∗∈GT and Ci_3∗∈GT at random. Then, the challenge broadcast ciphertext CT∗=C1∗,C2∗,…,Cn∗ is returned to the adversary A2.
Phase 2:A2 issues a set of queries adaptively. However, it cannot issue queries for SKi of IDi in S∗ or decryption of IDi in S∗.
Guess:A2 outputs a guess μ′∈0,1 for μ. It wins the game if μ′=μ. For IDℓ, the description of CT∗ is shown as follows. To produce the result, ℬ should calculate Di_1 and Di_2 correctly. ℬ chooses an item from LH3 at random and searches vℓ from the item IDℓ,Kℓ,vℓ,Rℓ. To solve the CBDH problem, ℬ computes T=Di_1⋅Di_2/Cℓ_1∗⋅Cℓ_2∗⋅eKℓ,Cℓ_0∗vℓ as the solution.
IfDi_1=C1ℓ_1∗⋅eCℓ_0∗,Certℓ and Di_2=Cℓ_2∗⋅eCℓ_0∗,RℓSK1ℓ, then Cℓ_1∗=Di_1/eCℓ_0∗,Certℓ and Cℓ_2∗=Di_2/eCℓ_0∗,RℓSK1ℓ. ℬ can extract the solution T=Di_1⋅Di_2/Cℓ_1∗⋅Cℓ_2∗⋅eCℓ_0∗α,Qℓ=eg,gabc.
Analysis: then, we analyze the probability that the given CBDH problem can be solved by the challengerC.
Ifℬ does not abort during the game, then A2’s view is identical to its view in the real scheme. Furthermore, we have Prμ′=μ−1/2≥ϵ. The game may be aborted before it finishes. Let Abort denote the game is aborted before it finishes. Then, event Abort occurs under any of the following occasions. 1Ab1: the adversary A2 queries the oracle OSecretKey on the user IDℓ. We have Pr¬Ab1=qpubkey−1/qpubkeyqseckey. 2Ab2:ℬ aborts in the period that CT is given to ODecrypt. We have PrAb2=qdec/2λ. 3Ab3:IDℓ is not in S∗ during the Challenge phase. We have PrAb3=N−n/N. So, we have that Pr¬Abort=Pr¬Ab1∧¬Ab2∧¬Ab3≥n/N1−qdec/2λqpubkey−1/qpubkeyqseckey.
Let Oca denoteH3Query|¬Abort. So, we have Prμ′=μ|¬Oca=1/2 and Prμ′=μ=1/2PrOca+1. By the definition of the advantage for A2 in ANO-CBIP-CCA Game 2, we have ε≤2|Prμ′=μ−1/2|≤PrOca≤PrH3Query/Pr¬Abort. So, we have PrH3Query≥εPr¬Abort≥nε/N1−qdec/2λqpubkey−1/qpubkeyqseckey. Finally, ℬ selects the correct item from LH3 with probability 1/qH3. Consequently, ℬ’s advantage is at least nε/qH3N1−qdec/2λqpubkey−1/qpubkeyqseckey as required.


## 6. Implementation and Evaluation

### 6.1. Theoretical Analysis

In Table2, we give analytical measurements for public parameters’ size, user secret keys’ size, ciphertext size, encryption cost, and decryption cost of the IBBE-IP scheme [8] and the proposed scheme.Table 2
Efficiency comparison.
IBBE-IP [8]Our schemePublic parameters’ sizeO (n)O (1)User secret keys’ sizeO (1)O (d)Ciphertext sizeO (d)O (n)Encryption costn+5d+7E+2P+dMT+1+3dET4nP+2+dE+3nMT+2nETDecryption cost3P+2n+d+3E+2n+dET+4MT3P+3E+3ET+5MTTable2 shows that our scheme has a significant advantage over the IBBE-IP scheme on decryption cost. The decryption cost of our scheme is 3P+3E+3ET+5MT which is constant, while the decryption cost of the IBBE-IP scheme is 3P+2n+d+3E+2n+dET+4MT which grows multiplicatively in n and d. Our scheme also optimizes the public parameters’ size for the reason that our public parameters’ size is constant, while the IBBE-IP scheme is linear with n.As for the ciphertext size, the ciphertext size of our scheme is linear with the number of recipientsn, while the ciphertext size of the IBBE-IP scheme is linear with the vector length d. However, there is a restriction in IBBE-IP that the recipient number has to be less than vector length (n < d). So, the increasing recipient number will lead to the growth of vector length, and the ciphertext size is also increasing as a result.It is obvious that our scheme achieves better performance than the existing scheme in the aspects of public parameters’ size and decryption time according to the analytical measurements.


### 6.2. Experimental Implementation

To evaluate the performance of the proposed scheme in practice, we give a reference implementation of our scheme and IBBE-IP scheme in Python language. We use the Charm library [36] to implement the pairing group operations and Flint library [37] for the finite field arithmetic in Zq. Our experiments are performed on a Linux desktop with 8 GB of RAM and an 8-core Intel Core i7-8550U 2.00 GHz processor to evaluate the above theoretical analysis illustration. In our implementation, we use the SS512 curve in the Charm library. We get the average result over ten runs.Figure2(a) shows that the encryption and key generation time of our scheme increase with the growing vector length given the certain number of recipients, while the decryption time remains constant at the same time. Figure 2(b) shows that encryption time is linear with the number of recipients in our scheme. Decryption time remains constant regardless of the number of recipients. Figure 3(a) shows that the ciphertext size of our scheme remains constant with the growing vector length given the certain number of recipients. Figure 3(b) shows that the ciphertext size is linear with the number of recipients given a certain vector length in our scheme.Figure 2
Our scheme’s computation time.
(a)(b)Figure 3
Our scheme’s ciphertext size.
(a)(b)In Table3, we give a more detailed computation time and ciphertext size of our scheme with the change of vector length and the intended recipient number. In order to achieve higher efficiency, we have precomputed eg1,Qi,eK1i,Ri,eK2i,Ri and have stored them in lists. We see that the ciphertext size rises from 1.0 KB to 5.8 KB when the recipient number grows from 3 to 19. Key generation time and encryption time grow from 3.3 ms to 48.2 ms and from 50.9 ms to 696.8 ms, respectively, as the recipient number and vector length grow. Decryption time is approximately 3.9 ms.Table 3
Performance of our scheme.
Vector lengthRecipient numberKeyGen time (ms)Enc time (ms)Dec time (ms)Ciphertext size (KB)d=10n=33.350.93.91.0n=67.2105.74.01.9n=910.4159.33.82.8d=20n=1327.7414.33.84.0n=1632.5475.63.94.9n=1948.2696.83.95.8Figure4(a) shows the ciphertext size difference between our scheme and IBBE-IP scheme. The ciphertext size of the IBBE-IP scheme is linear with the vector length with the restriction that the number of recipients is less than the vector length n<d, while our scheme has no restriction. Especially, as we can see from Figure 4(a), with the growing of recipient number n, the vector length d has to grow, and the ciphertext size is also increasing in the IBBE-IP scheme. As it is also shown in Table 3, the ciphertext size of our scheme is independent of the vector length. CT is linear with the number of recipients in our scheme because our scheme enables that different intended users in S obtain their corresponding inner product via the decryption of CT, and it achieves stronger plaintext protection. It avoids a security threat existing in a trivial solution that the sender encrypts a message under an inner product encryption first and then encrypts the ciphertext with a broadcast encryption. The threat is that once the decryption result of broadcast encryption is made public, all users in the inner product encryption system obtain the inner product ciphertext and are able to calculate their own inner product value. In our scheme, we avoid this threat. If there are users that maliciously expose the decryption result of broadcast encryption, others will not be able to obtain their corresponding inner product by the result. This leads to further protection to the plaintext.Figure 4
Comparison between the existing scheme and our scheme.
(a)(b)Figure4(b) shows our scheme’s significant advantage in decryption cost. In our implementation, this decryption time of IBBE-IP does not include the Pollard kangaroo algorithm runtime, while our scheme’s decryption time includes the baby-step giant-step algorithm runtime. Besides, the number of recipients needs to be less than the vector length (n < d) in IBBE-IP, so we let d = n + 1 in the measurement of decryption time. As we can see from Figure 4(b), the decryption time of IBBE-IP is linear with the recipient number and the vector length, while the decryption time of our scheme is constant. In our scheme, it is about 4.0 ms, and it is independent on the vector length and the recipient number.Obviously, our scheme is efficient according to the above analytical measurements and experimental evaluation because of its constant decryption cost. In addition, differing from our scheme, IBBE-IP scheme has the restriction that the number of recipients is less than the vector length [8]. Therefore, our scheme is applicable to those scenarios in that a number of recipients with limited computation capacity need to obtain the inner product values through decryption regularly.


## 6.1. Theoretical Analysis

In Table2, we give analytical measurements for public parameters’ size, user secret keys’ size, ciphertext size, encryption cost, and decryption cost of the IBBE-IP scheme [8] and the proposed scheme.Table 2
Efficiency comparison.
IBBE-IP [8]Our schemePublic parameters’ sizeO (n)O (1)User secret keys’ sizeO (1)O (d)Ciphertext sizeO (d)O (n)Encryption costn+5d+7E+2P+dMT+1+3dET4nP+2+dE+3nMT+2nETDecryption cost3P+2n+d+3E+2n+dET+4MT3P+3E+3ET+5MTTable2 shows that our scheme has a significant advantage over the IBBE-IP scheme on decryption cost. The decryption cost of our scheme is 3P+3E+3ET+5MT which is constant, while the decryption cost of the IBBE-IP scheme is 3P+2n+d+3E+2n+dET+4MT which grows multiplicatively in n and d. Our scheme also optimizes the public parameters’ size for the reason that our public parameters’ size is constant, while the IBBE-IP scheme is linear with n.As for the ciphertext size, the ciphertext size of our scheme is linear with the number of recipientsn, while the ciphertext size of the IBBE-IP scheme is linear with the vector length d. However, there is a restriction in IBBE-IP that the recipient number has to be less than vector length (n < d). So, the increasing recipient number will lead to the growth of vector length, and the ciphertext size is also increasing as a result.It is obvious that our scheme achieves better performance than the existing scheme in the aspects of public parameters’ size and decryption time according to the analytical measurements.


## 6.2. Experimental Implementation

To evaluate the performance of the proposed scheme in practice, we give a reference implementation of our scheme and IBBE-IP scheme in Python language. We use the Charm library [36] to implement the pairing group operations and Flint library [37] for the finite field arithmetic in Zq. Our experiments are performed on a Linux desktop with 8 GB of RAM and an 8-core Intel Core i7-8550U 2.00 GHz processor to evaluate the above theoretical analysis illustration. In our implementation, we use the SS512 curve in the Charm library. We get the average result over ten runs.Figure2(a) shows that the encryption and key generation time of our scheme increase with the growing vector length given the certain number of recipients, while the decryption time remains constant at the same time. Figure 2(b) shows that encryption time is linear with the number of recipients in our scheme. Decryption time remains constant regardless of the number of recipients. Figure 3(a) shows that the ciphertext size of our scheme remains constant with the growing vector length given the certain number of recipients. Figure 3(b) shows that the ciphertext size is linear with the number of recipients given a certain vector length in our scheme.Figure 2
Our scheme’s computation time.
(a)(b)Figure 3
Our scheme’s ciphertext size.
(a)(b)In Table3, we give a more detailed computation time and ciphertext size of our scheme with the change of vector length and the intended recipient number. In order to achieve higher efficiency, we have precomputed eg1,Qi,eK1i,Ri,eK2i,Ri and have stored them in lists. We see that the ciphertext size rises from 1.0 KB to 5.8 KB when the recipient number grows from 3 to 19. Key generation time and encryption time grow from 3.3 ms to 48.2 ms and from 50.9 ms to 696.8 ms, respectively, as the recipient number and vector length grow. Decryption time is approximately 3.9 ms.Table 3
Performance of our scheme.
Vector lengthRecipient numberKeyGen time (ms)Enc time (ms)Dec time (ms)Ciphertext size (KB)d=10n=33.350.93.91.0n=67.2105.74.01.9n=910.4159.33.82.8d=20n=1327.7414.33.84.0n=1632.5475.63.94.9n=1948.2696.83.95.8Figure4(a) shows the ciphertext size difference between our scheme and IBBE-IP scheme. The ciphertext size of the IBBE-IP scheme is linear with the vector length with the restriction that the number of recipients is less than the vector length n<d, while our scheme has no restriction. Especially, as we can see from Figure 4(a), with the growing of recipient number n, the vector length d has to grow, and the ciphertext size is also increasing in the IBBE-IP scheme. As it is also shown in Table 3, the ciphertext size of our scheme is independent of the vector length. CT is linear with the number of recipients in our scheme because our scheme enables that different intended users in S obtain their corresponding inner product via the decryption of CT, and it achieves stronger plaintext protection. It avoids a security threat existing in a trivial solution that the sender encrypts a message under an inner product encryption first and then encrypts the ciphertext with a broadcast encryption. The threat is that once the decryption result of broadcast encryption is made public, all users in the inner product encryption system obtain the inner product ciphertext and are able to calculate their own inner product value. In our scheme, we avoid this threat. If there are users that maliciously expose the decryption result of broadcast encryption, others will not be able to obtain their corresponding inner product by the result. This leads to further protection to the plaintext.Figure 4
Comparison between the existing scheme and our scheme.
(a)(b)Figure4(b) shows our scheme’s significant advantage in decryption cost. In our implementation, this decryption time of IBBE-IP does not include the Pollard kangaroo algorithm runtime, while our scheme’s decryption time includes the baby-step giant-step algorithm runtime. Besides, the number of recipients needs to be less than the vector length (n < d) in IBBE-IP, so we let d = n + 1 in the measurement of decryption time. As we can see from Figure 4(b), the decryption time of IBBE-IP is linear with the recipient number and the vector length, while the decryption time of our scheme is constant. In our scheme, it is about 4.0 ms, and it is independent on the vector length and the recipient number.Obviously, our scheme is efficient according to the above analytical measurements and experimental evaluation because of its constant decryption cost. In addition, differing from our scheme, IBBE-IP scheme has the restriction that the number of recipients is less than the vector length [8]. Therefore, our scheme is applicable to those scenarios in that a number of recipients with limited computation capacity need to obtain the inner product values through decryption regularly.


## 7. Conclusion and Future Work

In this paper, we propose a certificate-based inner product broadcast encryption with anonymity due to the limitation in efficiency and recipient privacy in the present broadcast encryption for inner product scheme. Concrete construction and formal security definitions are given in this paper. We show that our scheme is adaptively secure under the IND-CCA security model which is different from the previous inner product broadcast encryption under the IND-CPA security model. In addition, the identity of a user is anonymous to others in our scheme. Furthermore, analytical and experimental results show that our scheme enables faster decryption. Because of these good properties, our scheme may have some significant value in some practical applications such as enabling secure group communication in the consortium blockchain. However, the size of the ciphertext is linear with the number of recipients, and how to further reduce ciphertext size is still a challenging problem.



---

*Source: 6639835-2021-08-31.xml*