# Anonymous Multireceiver Identity-Based Encryption against Chosen-Ciphertext Attacks with Tight Reduction in the Standard Model

Authors: Yi-Fan Tseng; Chun-I Fan
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Multireceiver identity-based encryption is a cryptographic primitive, which allows a sender to encrypt a message for multiple receivers efficiently and securely. In some applications, the receivers may not want their identities to be revealed. Motivated by this issue, in 2010, Fan et al. first proposed the concept of anonymous multireceiver identity-based encryption (AMRIBE). Since then, lots of literature studies in this field have been proposed. After surveying the existing works, however, we found that most of them fail to achieve provable anonymity with tight reduction. A security proof with tight reduction means better quality of security and better efficiency of implementation. In this paper, we focus on solving the open problem in this field that is to achieve the ANON-IND-CCA security with tight reduction by giving an AMRIBE scheme. The proposed scheme is proven to be IND-MID-CCA and ANON-MID-CCA secure with tight reduction under a variant of the DBDH assumption. To the best of our knowledge, this is the first scheme proven with tight reducible full CCA security in the standard model.


---

## Body

## 1. Introduction

Identity-based encryption (IBE) is a large class of public key encryption in modern cryptography. The concept of IBE was first proposed by Shamir [1] in 1984, and the first practical construction was independently proposed by Boneh and Franklin [2] and Cocks [3] in 2001. In an IBE scheme, a user can use any string as her/his public key, such as national identifier number and e-mail address.It is a natural question to ask how to design a multireceiver IBE to encrypt a message with better efficiency compared with individually encrypting to each user in terms of either computation cost or communication cost. Such a cryptographic primitive is popular in advanced applications such as video conferencing, pay-per-view TV [4–8], and distance education. The notion of multireceiver identity-based encryption (MRIBE) was first considered by Beak et al. [9] in 2005. In an MRIBE scheme, the input of the encryption algorithm is a set of identities rather than a single identity. A user who is selected in the set is able to decrypt the ciphertext. MRIBE then drew the attention of the research community, and lots of results [10, 11] have been proposed.Another notion similar to MRIBE is identity-based broadcast encryption (IBBE) [12–14]. An IBBE scheme is usually designed in the sense of key encapsulation mechanism (KEM), where the encryption algorithm takes as input only a set of identities and outputs a header and an encryption key. To encrypt a message, one then uses the encryption key with a data encryption mechanism (DEM), such as DES and AES. A user whose identity is selected in the set can use her/his private key together with the header to recover the encryption key. On the other hand, an encryption scheme can be regarded as a key encapsulation mechanism by simply setting a ciphertext as the header and the corresponding plaintext as the encryption key. In this paper, we will treat MRIBE and IBBE as the identical notion.In some situations, such as ordering sensitive TV programs, the customers may expect that their identities are not revealed. In consideration of privacy-preserving, Fan et al. [15] first introduced the concept of anonymous multireceiver ID-based encryption (AMRIBE) in 2010. Anonymity is defined as that no one should know the identities of the receivers except the encryptor. They also proposed a multireceiver ID-based encryption scheme using Lagrange interpolating polynomials. Unfortunately, their scheme was pointed out to be flawed by Chien [16] in 2012. In Fan et al. scheme, anyone given a ciphertext is able to reveal the receivers. Chien further indicated that the security model defined in [15] does not cover all of the multireceiver scenarios. He also proposed an improved AMRIBE scheme in [16]. Since then, many results of AMRIBE have been proposed [17–25].After examining these AMRIBE schemes, we found that there is no AMRIBE scheme achieving full-ID security with tight reduction against chosen-ciphertext attacks. Filling the gap is significant for the researches of AMRIBE in terms of both theoretical and practical aspects.Most of the existing AMRIBEs are only proven to be secure in the weaker “selective-ID” model, where the attacker must commit a target receiver set that it will attack at the beginning of the security game. The selective-ID model might not be appropriate for the attack model in a realistic environment, since the attackers should be able to adaptively choose their target after learning some information of the system. This characteristic is captured by another stronger model called “full-ID” model, where the attacker chooses the target at the challenge phase rather than at the beginning. In [26, 27], Boneh and Boyen show that a selective-ID secure IBE can also be proven to be full-ID secure. Roughly speaking, a challenger can make a guess on which identity, said ID∗, will be targeted at the challenge phase before it starts the simulation. If the adversary makes a query with ID∗ or does not activate the challenge phase with ID∗, then the simulation is aborted. However, the proof strategy makes the reduction “lossy,” i.e., the reduction is not tight. Let N be the number of allowed identities, then the reduction will lose a factor of N. That is, if the adversary wins the security game with advantage ϵ, then the challenger only guarantees to solve the underlying hard problem with advantage ϵ′≤ϵ/N (actually the analysis should take the running times into consideration. Here, we simply assume that the running times of the adversary and the challenger are asymptotically equivalent). More details can be referred to [26, 28].A lossy reduction is not merely a theoretic problem; it also relates to the efficiency and efficacy of the entire system. We give a simple example for the (informal) analysis as follows. If we want to build an IBE system based on the DBDH assumption with 80-bit security level, and assumeN=2160, then we need to adopt a DBDH-hard group whose order is 2240 due to the lossiness. This will make the entire system inefficient since we need a longer bit representation for the group of larger order [29]. Therefore, achieving tight reduction is a significant goal for an encryption scheme, since it affects both security and efficiency. The tight reduction allows one to construct an encryption scheme with the same security level as the underlying hard assumption. We refer the readers to [30] for more detailed examples.The consequence of a lossy reduction will be much more worse when it comes to more complex primitives, such as AMRIBE. In the security game of AMRIBE, an adversary activates the challenge phase witht receivers, where t can be any positive number smaller than the number of the total possible identities. Assume that we set an identity to be an n-bits string, then a challenger needs to guess the target receiver set from ∑t=12n2nt=22n different combinations. This makes the scheme impractical, since either the bit length of the representation for the underlying group will be exponentially large, or the reduction will be successful only with negligible advantage in the security proof.


### 1.1. Contributions

For both practical and theoretical reasons mentioned above, in this paper, we propose the first AMRIBE scheme achieving full-ID security in confidentiality and anonymity with tight reduction. It is worth noting that the security of our scheme is proven in the standard model, i.e., without random oracles. The random oracle model [31] is a heuristic and idealized model used to help people to prove the security of cryptographic primitives. In the security proofs, one usually models a cryptographic hash function as a random oracle. However, there are schemes proven secure in the random oracle models while being insecure when implementing the random oracle with any hash function in the real world [32, 33]. To the best of our knowledge, our scheme is the first and only one to achieve IND-MID-CCA/ANON-MID-CCA security (the abbreviation of “Indistinguishability under full-multi-ID chosen-ciphertext attacks” and “Anonymity under full-multi-ID chosen-ciphertext attacks”) with tight reduction in the standard model. Besides, compared with other existing schemes, the encryption cost is low. Therefore, our scheme fits the scenario that a sender needs frequently to send messages for large amount of users, such as e-mail systems with receiver anonymity.


### 1.2. Organization

The remainder of this paper is organized as follows. Section2 presents some preliminaries, specifically our security notions and the complexity assumptions that will be used in the security proofs. In Section 3, we introduce our AMRIBE scheme. Section 4 provides security proofs for the confidentiality and anonymity of our proposed scheme. Next, we show the comparison between our scheme and the existing works in properties and performances in Section 5. Finally, Section 6 concludes our work and provides future research directions.


## 1.1. Contributions

For both practical and theoretical reasons mentioned above, in this paper, we propose the first AMRIBE scheme achieving full-ID security in confidentiality and anonymity with tight reduction. It is worth noting that the security of our scheme is proven in the standard model, i.e., without random oracles. The random oracle model [31] is a heuristic and idealized model used to help people to prove the security of cryptographic primitives. In the security proofs, one usually models a cryptographic hash function as a random oracle. However, there are schemes proven secure in the random oracle models while being insecure when implementing the random oracle with any hash function in the real world [32, 33]. To the best of our knowledge, our scheme is the first and only one to achieve IND-MID-CCA/ANON-MID-CCA security (the abbreviation of “Indistinguishability under full-multi-ID chosen-ciphertext attacks” and “Anonymity under full-multi-ID chosen-ciphertext attacks”) with tight reduction in the standard model. Besides, compared with other existing schemes, the encryption cost is low. Therefore, our scheme fits the scenario that a sender needs frequently to send messages for large amount of users, such as e-mail systems with receiver anonymity.


## 1.2. Organization

The remainder of this paper is organized as follows. Section2 presents some preliminaries, specifically our security notions and the complexity assumptions that will be used in the security proofs. In Section 3, we introduce our AMRIBE scheme. Section 4 provides security proofs for the confidentiality and anonymity of our proposed scheme. Next, we show the comparison between our scheme and the existing works in properties and performances in Section 5. Finally, Section 6 concludes our work and provides future research directions.


## 2. Preliminaries

### 2.1. Notations

In this paper, we use multiplicative group representation. Form,n where m<n, we mean the successive integer set from m to n, i.e., m,m+1,…,n. Furthermore, for an integer n, n denotes the integer set 1,2,…,n. For a set S, by “x⟵$S” we mean “choose x uniformly from S”. For an algorithm A, by “x⟵A,” we denote “x is the output of A”. For a bit-string s, we denote the i-th bit of s as si.


### 2.2. Bilinear Mapping

Definition 1.
LetG,G^, and GT be three multiplicative cyclic groups of prime order p. A bilinear map (pairing) e:G×G^⟶GT satisfies the following properties in which g,g^ is a generator of G,G^, respectively.(i)
Bilinearity:ega,g^b=eg,g^ab,∀a,b∈Zp.(ii)
Nondegeneracy: ifeg,g^=1GT, the identity element of GT, then either g is the identity of G or g^ is the identity of G^.(iii)
Computability: there exists an efficient algorithm to compute the functione.In this paper, we use type 3 pairings [34, 35], where G≠G^ and no efficient computable isomorphisms G^ between G are known.


### 2.3. Complexity Assumptions

The security of the proposed scheme is based on a variant of the decisional bilinear Diffie–Hellman (DBDH) problem, called DBDH-3 problem [36–39]. Let G,G^, and GT be three multiplicative cyclic groups of prime order p, where g,g^ is a generator of G,G^, respectively. Let e:G×G^⟶GT be a type 3 pairing.Definition 2.
(a variant of DBDH problem in type 3 pairing groups—DBDH-3). Giveng,g^,g^a,g^b,gb,gc,g^c,Z, where a,b,c⟵$Zp decide whether Z=eg,g^abc or a random element in GT.We say that an algorithmℬ that outputs a bit has the advantage ϵ in solving the DBDH-3 problem if(1)Prℬg,g^,g^a,g^b,gb,gc,g^c,eg,g^abc=1−Prℬg,g^,g^a,g^b,gb,gc,g^c,Z⟵GT=1≥ϵ.Definition 3.
(the DBDH-3 assumption). We say that theτ,ϵ-DBDH-3 assumption holds if no τ-time algorithm has advantage at least ϵ in solving the DBDH-3 problem. We occasionally drop τ,ϵ for simplicity.


### 2.4. Anonymous Multireceiver Identity-Based Encryption

An AMRIBE scheme consists of the following algorithms:(i)
Setup1λ: this algorithm takes as input a security parameter λ and outputs the master secret key msk and the system parameter param. Note that all algorithms except Setup will implicitly take param as one of the inputs, and thus, we will omit the term param for simplicity.(ii)
KeyExtractmsk,ID: this algorithm takes as inputs the master secret key msk and an identity ID and then outputs the private key dID for user ID.(iii)
EncryptS,M: this algorithm takes as inputs an identity set S=ID1,…,IDt for any positive t and a message M and then outputs a ciphertext C.(iv)
DecryptC,dID: this algorithm takes as inputs a ciphertext and a private key for ID and then outputs a message M or a dedicated error symbol ⊥.Correctness. For all C⟵EcryptS,M,dID⟵KeyExtractmsk,ID:(i)
IfID∈S, then M⟵DecryptC,dID(ii)
IfID∈S, then ⊥⟵DecryptC,dID


#### 2.4.1. Confidentiality

Next, we will give the security definition for confidentiality. Consider the following game played between a challengerC and an adversary A. The security game consists of four phases as follows:Setup:C generates the system parameter params and sends it to A.Phase 1:A is allowed to make queries from the following oracles:KeyExtract: A makes a KeyExtract query with an identity ID, and C returns the private key dID to ADecrypt: A makes a Decrypt query with a ciphertext C and an identity ID, and C returns the result of DecryptC,dIDChallenge: the adversary submits two messagesM0,M1 with the same length and a target identity set ID∗=ID1∗,…,IDt∗ for any positive integer t, with the restriction that all identities in ID∗ should not be submitted to KeyExtract oracle in Phase 1. C then randomly chooses β∈0,1 and generates C∗⟵EncryptID∗,Mβ. Finally, C∗ is returned to A.Phase 2:A is allowed to make queries as in Phase 1, except for KeyExtract queries with ID∈ID∗ and Decrypt queries with C∗,ID∈ID∗.Guess: finally,A outputs a bit β′ and wins the game if β′=β.One can observe that the above game is modelled for the security notion IND-MID-CCA. The security games for IND-sMID-CCA and IND-MID-CPA can be obtained by forcingA to commit ID∗ before Setup and disallowing A to query Decrypt oracle, respectively. The advantage of A winning the game is defined as(2)AdvIND−MID−CCAA=Prβ′=β−12.We say that an AMRIBE scheme isτ,ϵ-IND-MID-CCA secure if all τ-time adversaries have at most advantage ϵ in winning the above IND-MID-CCA game.


#### 2.4.2. Anonymity

Next, we define the anonymity for an AMRIBE. Consider the following game played between a challengerC and an adversary A. The security game consists of four phases as follows:Setup:C generates the system parameter params and sends it to A.Phase 1:A is allowed to make queries from the following oracles:KeyExtract: A makes a KeyExtract query with an identity ID, and C returns the private key dID to ADecrypt: A makes a Decrypt query with a ciphertext C and an identity ID, and C returns the result of DecryptC,dIDChallenge: the adversary submits a messageM, a target identity set ID∗=ID0∗,ID1∗, and an identity set ID2∗,…,IDt∗ for any positive integer t, with the restriction that all identities in ID∗ should not be submitted to KeyExtract oracle in Phase 1. C then randomly chooses β∈0,1, sets Sβ∗=IDβ∗,ID2∗,…,IDt∗, and generates C∗⟵EncryptSβ∗,M. Finally, C∗ is returned to A.Phase 2:A is allowed to make queries as in Phase 1, except for KeyExtract queries with ID∈ID∗ and Decrypt queries with C∗,ID∈ID∗.Guess: finally,A outputs a bit β′ and wins the game if β′=β.The above game is modelled for the security notion ANON-MID-CCA (the security games for ANON-sMID-CCA and ANON-MID-CPA can be obtained by forcingA to commit ID∗ before Setup and disallowing A to query Decrypt oracle, respectively). The advantage of A winning the game is defined as follows:(3)Adv−ANON−MID−CCAA=Prβ′=β−12.We say that an AMRIBE scheme isτ,ϵ-ANON-MID-CCA secure if all τ-time adversaries have at most advantage ϵ in winning the above ANON-MID-CCA game.Remark 1.
Note that this definition is actually modelled against insider adversaries, sinceA is allowed to query the private key for ID2∗,…,IDt∗, and the encrypted message M is chosen by A.Remark 2.
The ANON-MID-CCA game defined above is slightly different from some existing works, such as [19, 20, 22]. In their definition, A submits two different identity sets S0∗,S1∗, where S0∗=S1∗, with the restriction that all ID∈S0∗ΔS1∗=S0∗/S1∗∪S1∗/S0∗ have not been queried to KeyExtract oracle. In our model, one can image that S0∗=ID0∗,ID2∗,…,IDt∗ and S1∗=ID1∗,ID2∗,…,IDt∗, and thus, S0∗ΔS1∗=ID0∗,ID1∗, where S0∗ΔS1∗ is minimal. Actually, our model may be a stronger model since we allow an adversary to query as much private keys as possible, as long as the trivial way to win the game is prevented from the adversary.


### 2.5. Tight Security Reduction

In this section, we introduce the notion of tight security reduction. To prove the security of a cryptographic primitive, we usually construct a reduction between the security of the primitive and a well-studied hard assumption. That is, if there is an algorithmA breaks the security of the primitive, then there exists an algorithm C that makes black-box use of A to solve the hard problem. Assume that the algorithm A breaks the primitive with advantage ϵA in time τA, and the algorithm C breaks the assumption with advantage ϵC in time τC. In a conventional sense [40], a reduction is said to be tight if ϵC≈ϵA and τC≈τA. Another weaker notion of tight reduction is defined in [30, 41]. The quality of a reduction can also be measured by the ratio between τA/ϵA and τC/ϵC. Let(4)τCϵC=ℓ⋅τAϵA.In the above equation, “ℓ” is the “loss” for the reduction. A reduction is efficient if the loss ℓ is polynomially bounded. If ℓ is constant, then the reduction is said to be weakly tight. From this definition, we can see why an efficient (or ideally, tight) reduction is important. We briefly explain the reason. Assume that τC≈τA, then we have(5)ϵC=ϵAℓ.Ifℓ is exponentially large, then ϵC may be negligible; even if the adversary’s advantage ϵA is nonnegligible, we cannot base the security of our protocol on the underlying complexity assumptions.


## 2.1. Notations

In this paper, we use multiplicative group representation. Form,n where m<n, we mean the successive integer set from m to n, i.e., m,m+1,…,n. Furthermore, for an integer n, n denotes the integer set 1,2,…,n. For a set S, by “x⟵$S” we mean “choose x uniformly from S”. For an algorithm A, by “x⟵A,” we denote “x is the output of A”. For a bit-string s, we denote the i-th bit of s as si.


## 2.2. Bilinear Mapping

Definition 1.
LetG,G^, and GT be three multiplicative cyclic groups of prime order p. A bilinear map (pairing) e:G×G^⟶GT satisfies the following properties in which g,g^ is a generator of G,G^, respectively.(i)
Bilinearity:ega,g^b=eg,g^ab,∀a,b∈Zp.(ii)
Nondegeneracy: ifeg,g^=1GT, the identity element of GT, then either g is the identity of G or g^ is the identity of G^.(iii)
Computability: there exists an efficient algorithm to compute the functione.In this paper, we use type 3 pairings [34, 35], where G≠G^ and no efficient computable isomorphisms G^ between G are known.


## 2.3. Complexity Assumptions

The security of the proposed scheme is based on a variant of the decisional bilinear Diffie–Hellman (DBDH) problem, called DBDH-3 problem [36–39]. Let G,G^, and GT be three multiplicative cyclic groups of prime order p, where g,g^ is a generator of G,G^, respectively. Let e:G×G^⟶GT be a type 3 pairing.Definition 2.
(a variant of DBDH problem in type 3 pairing groups—DBDH-3). Giveng,g^,g^a,g^b,gb,gc,g^c,Z, where a,b,c⟵$Zp decide whether Z=eg,g^abc or a random element in GT.We say that an algorithmℬ that outputs a bit has the advantage ϵ in solving the DBDH-3 problem if(1)Prℬg,g^,g^a,g^b,gb,gc,g^c,eg,g^abc=1−Prℬg,g^,g^a,g^b,gb,gc,g^c,Z⟵GT=1≥ϵ.Definition 3.
(the DBDH-3 assumption). We say that theτ,ϵ-DBDH-3 assumption holds if no τ-time algorithm has advantage at least ϵ in solving the DBDH-3 problem. We occasionally drop τ,ϵ for simplicity.


## 2.4. Anonymous Multireceiver Identity-Based Encryption

An AMRIBE scheme consists of the following algorithms:(i)
Setup1λ: this algorithm takes as input a security parameter λ and outputs the master secret key msk and the system parameter param. Note that all algorithms except Setup will implicitly take param as one of the inputs, and thus, we will omit the term param for simplicity.(ii)
KeyExtractmsk,ID: this algorithm takes as inputs the master secret key msk and an identity ID and then outputs the private key dID for user ID.(iii)
EncryptS,M: this algorithm takes as inputs an identity set S=ID1,…,IDt for any positive t and a message M and then outputs a ciphertext C.(iv)
DecryptC,dID: this algorithm takes as inputs a ciphertext and a private key for ID and then outputs a message M or a dedicated error symbol ⊥.Correctness. For all C⟵EcryptS,M,dID⟵KeyExtractmsk,ID:(i)
IfID∈S, then M⟵DecryptC,dID(ii)
IfID∈S, then ⊥⟵DecryptC,dID


### 2.4.1. Confidentiality

Next, we will give the security definition for confidentiality. Consider the following game played between a challengerC and an adversary A. The security game consists of four phases as follows:Setup:C generates the system parameter params and sends it to A.Phase 1:A is allowed to make queries from the following oracles:KeyExtract: A makes a KeyExtract query with an identity ID, and C returns the private key dID to ADecrypt: A makes a Decrypt query with a ciphertext C and an identity ID, and C returns the result of DecryptC,dIDChallenge: the adversary submits two messagesM0,M1 with the same length and a target identity set ID∗=ID1∗,…,IDt∗ for any positive integer t, with the restriction that all identities in ID∗ should not be submitted to KeyExtract oracle in Phase 1. C then randomly chooses β∈0,1 and generates C∗⟵EncryptID∗,Mβ. Finally, C∗ is returned to A.Phase 2:A is allowed to make queries as in Phase 1, except for KeyExtract queries with ID∈ID∗ and Decrypt queries with C∗,ID∈ID∗.Guess: finally,A outputs a bit β′ and wins the game if β′=β.One can observe that the above game is modelled for the security notion IND-MID-CCA. The security games for IND-sMID-CCA and IND-MID-CPA can be obtained by forcingA to commit ID∗ before Setup and disallowing A to query Decrypt oracle, respectively. The advantage of A winning the game is defined as(2)AdvIND−MID−CCAA=Prβ′=β−12.We say that an AMRIBE scheme isτ,ϵ-IND-MID-CCA secure if all τ-time adversaries have at most advantage ϵ in winning the above IND-MID-CCA game.


### 2.4.2. Anonymity

Next, we define the anonymity for an AMRIBE. Consider the following game played between a challengerC and an adversary A. The security game consists of four phases as follows:Setup:C generates the system parameter params and sends it to A.Phase 1:A is allowed to make queries from the following oracles:KeyExtract: A makes a KeyExtract query with an identity ID, and C returns the private key dID to ADecrypt: A makes a Decrypt query with a ciphertext C and an identity ID, and C returns the result of DecryptC,dIDChallenge: the adversary submits a messageM, a target identity set ID∗=ID0∗,ID1∗, and an identity set ID2∗,…,IDt∗ for any positive integer t, with the restriction that all identities in ID∗ should not be submitted to KeyExtract oracle in Phase 1. C then randomly chooses β∈0,1, sets Sβ∗=IDβ∗,ID2∗,…,IDt∗, and generates C∗⟵EncryptSβ∗,M. Finally, C∗ is returned to A.Phase 2:A is allowed to make queries as in Phase 1, except for KeyExtract queries with ID∈ID∗ and Decrypt queries with C∗,ID∈ID∗.Guess: finally,A outputs a bit β′ and wins the game if β′=β.The above game is modelled for the security notion ANON-MID-CCA (the security games for ANON-sMID-CCA and ANON-MID-CPA can be obtained by forcingA to commit ID∗ before Setup and disallowing A to query Decrypt oracle, respectively). The advantage of A winning the game is defined as follows:(3)Adv−ANON−MID−CCAA=Prβ′=β−12.We say that an AMRIBE scheme isτ,ϵ-ANON-MID-CCA secure if all τ-time adversaries have at most advantage ϵ in winning the above ANON-MID-CCA game.Remark 1.
Note that this definition is actually modelled against insider adversaries, sinceA is allowed to query the private key for ID2∗,…,IDt∗, and the encrypted message M is chosen by A.Remark 2.
The ANON-MID-CCA game defined above is slightly different from some existing works, such as [19, 20, 22]. In their definition, A submits two different identity sets S0∗,S1∗, where S0∗=S1∗, with the restriction that all ID∈S0∗ΔS1∗=S0∗/S1∗∪S1∗/S0∗ have not been queried to KeyExtract oracle. In our model, one can image that S0∗=ID0∗,ID2∗,…,IDt∗ and S1∗=ID1∗,ID2∗,…,IDt∗, and thus, S0∗ΔS1∗=ID0∗,ID1∗, where S0∗ΔS1∗ is minimal. Actually, our model may be a stronger model since we allow an adversary to query as much private keys as possible, as long as the trivial way to win the game is prevented from the adversary.


## 2.4.1. Confidentiality

Next, we will give the security definition for confidentiality. Consider the following game played between a challengerC and an adversary A. The security game consists of four phases as follows:Setup:C generates the system parameter params and sends it to A.Phase 1:A is allowed to make queries from the following oracles:KeyExtract: A makes a KeyExtract query with an identity ID, and C returns the private key dID to ADecrypt: A makes a Decrypt query with a ciphertext C and an identity ID, and C returns the result of DecryptC,dIDChallenge: the adversary submits two messagesM0,M1 with the same length and a target identity set ID∗=ID1∗,…,IDt∗ for any positive integer t, with the restriction that all identities in ID∗ should not be submitted to KeyExtract oracle in Phase 1. C then randomly chooses β∈0,1 and generates C∗⟵EncryptID∗,Mβ. Finally, C∗ is returned to A.Phase 2:A is allowed to make queries as in Phase 1, except for KeyExtract queries with ID∈ID∗ and Decrypt queries with C∗,ID∈ID∗.Guess: finally,A outputs a bit β′ and wins the game if β′=β.One can observe that the above game is modelled for the security notion IND-MID-CCA. The security games for IND-sMID-CCA and IND-MID-CPA can be obtained by forcingA to commit ID∗ before Setup and disallowing A to query Decrypt oracle, respectively. The advantage of A winning the game is defined as(2)AdvIND−MID−CCAA=Prβ′=β−12.We say that an AMRIBE scheme isτ,ϵ-IND-MID-CCA secure if all τ-time adversaries have at most advantage ϵ in winning the above IND-MID-CCA game.


## 2.4.2. Anonymity

Next, we define the anonymity for an AMRIBE. Consider the following game played between a challengerC and an adversary A. The security game consists of four phases as follows:Setup:C generates the system parameter params and sends it to A.Phase 1:A is allowed to make queries from the following oracles:KeyExtract: A makes a KeyExtract query with an identity ID, and C returns the private key dID to ADecrypt: A makes a Decrypt query with a ciphertext C and an identity ID, and C returns the result of DecryptC,dIDChallenge: the adversary submits a messageM, a target identity set ID∗=ID0∗,ID1∗, and an identity set ID2∗,…,IDt∗ for any positive integer t, with the restriction that all identities in ID∗ should not be submitted to KeyExtract oracle in Phase 1. C then randomly chooses β∈0,1, sets Sβ∗=IDβ∗,ID2∗,…,IDt∗, and generates C∗⟵EncryptSβ∗,M. Finally, C∗ is returned to A.Phase 2:A is allowed to make queries as in Phase 1, except for KeyExtract queries with ID∈ID∗ and Decrypt queries with C∗,ID∈ID∗.Guess: finally,A outputs a bit β′ and wins the game if β′=β.The above game is modelled for the security notion ANON-MID-CCA (the security games for ANON-sMID-CCA and ANON-MID-CPA can be obtained by forcingA to commit ID∗ before Setup and disallowing A to query Decrypt oracle, respectively). The advantage of A winning the game is defined as follows:(3)Adv−ANON−MID−CCAA=Prβ′=β−12.We say that an AMRIBE scheme isτ,ϵ-ANON-MID-CCA secure if all τ-time adversaries have at most advantage ϵ in winning the above ANON-MID-CCA game.Remark 1.
Note that this definition is actually modelled against insider adversaries, sinceA is allowed to query the private key for ID2∗,…,IDt∗, and the encrypted message M is chosen by A.Remark 2.
The ANON-MID-CCA game defined above is slightly different from some existing works, such as [19, 20, 22]. In their definition, A submits two different identity sets S0∗,S1∗, where S0∗=S1∗, with the restriction that all ID∈S0∗ΔS1∗=S0∗/S1∗∪S1∗/S0∗ have not been queried to KeyExtract oracle. In our model, one can image that S0∗=ID0∗,ID2∗,…,IDt∗ and S1∗=ID1∗,ID2∗,…,IDt∗, and thus, S0∗ΔS1∗=ID0∗,ID1∗, where S0∗ΔS1∗ is minimal. Actually, our model may be a stronger model since we allow an adversary to query as much private keys as possible, as long as the trivial way to win the game is prevented from the adversary.


## 2.5. Tight Security Reduction

In this section, we introduce the notion of tight security reduction. To prove the security of a cryptographic primitive, we usually construct a reduction between the security of the primitive and a well-studied hard assumption. That is, if there is an algorithmA breaks the security of the primitive, then there exists an algorithm C that makes black-box use of A to solve the hard problem. Assume that the algorithm A breaks the primitive with advantage ϵA in time τA, and the algorithm C breaks the assumption with advantage ϵC in time τC. In a conventional sense [40], a reduction is said to be tight if ϵC≈ϵA and τC≈τA. Another weaker notion of tight reduction is defined in [30, 41]. The quality of a reduction can also be measured by the ratio between τA/ϵA and τC/ϵC. Let(4)τCϵC=ℓ⋅τAϵA.In the above equation, “ℓ” is the “loss” for the reduction. A reduction is efficient if the loss ℓ is polynomially bounded. If ℓ is constant, then the reduction is said to be weakly tight. From this definition, we can see why an efficient (or ideally, tight) reduction is important. We briefly explain the reason. Assume that τC≈τA, then we have(5)ϵC=ϵAℓ.Ifℓ is exponentially large, then ϵC may be negligible; even if the adversary’s advantage ϵA is nonnegligible, we cannot base the security of our protocol on the underlying complexity assumptions.


## 3. Anonymous Multireceiver Identity-Based Encryption with Tight Reduction

In this section, we demonstrate a novel AMRIBE scheme with tight reduction. The proposed AMRIBE scheme is, to the best of our knowledge, the first such scheme with full security under tight reduction in the standard model.


### 3.1. The Proposed AMRIBE with Tight Reduction

LetG,G^, and GT be three cyclic multiplicative groups with prime order p and g,g^ be the generators of G,G^, respectively. In this scheme, we adopt type 3 pairing, i.e., e:G×G^⟶GT. The proposed scheme consists of the following algorithms:Setup1λ: taking as input a security parameter 1λ, KGC performs as follows:(1)
Chooseα,β⟵$Zp.(2)
Choose two cryptographic hash functionsH:0,1∗⟶0,1n and H1:0,1∗⟶Zp, where n is a positive integer.(3)
ComputeΩ=eg,g^αβ,Λ=eg,g^αβ−1.(4)
Fori∈n, choose νi⟵$Zp and compute Ii=gνi,I^i=g^νi.(5)
Chooseϕ,ψ⟵$Zp, and compute Φ^=g^ϕ,Ψ^=g^ψ.(6)
Publish the system parameter(6)param=G,G^,GT,e,p,g,Ω,Λ,Iii∈n,Φ^,Ψ^,H,H1.and keep secret the master secret keymsk=g^,g^α,I^ii∈n.KeyExtractmsk,ID: taking as input the master secret key msk=g^,g^α,I^ii∈n and an identity ID, KGC computes the private key for ID as follows. For convenience, given an identity ID, where the corresponding hash value HID is hID, we define a function F^ID=∏i∈nI^ihIDi.(1)
Chooser⟵$Zp(2)
ComputeF^ID(3)
Set the private keydID=d^ID,0,d^ID,1=g^αF^IDr,g^rEncryptS,M: taking as input an identity set S=ID1,…,IDt for a positive integer t and a message M∈GT, the sender performs as follows. For convenience, given an identity ID, where the corresponding hash value HID is hID, we define a function FID=∏i∈nIihIDi.(1)
Chooses⟵$Zp.(2)
Fori∈t, compute FIDi.(3)
ComputeC0=M⋅Ωs,C1=Λs,C2=gs,C3,i=FIDis for i∈t, and K=Λs/Ωs.(4)
Computeh=H1C0,C1,C2,C3,1,…,C3,t,K,M, and Γ^=Φ^⋅Ψ^hs.(5)
The ciphertext isC=C0,C1,C2,C3,ii∈t,Γ^.DecryptC,dID: taking as input a ciphertext C=C0,C1,C2,C3,ii∈t,Γ^ and a private key dID, a user ID performs as follows. For i∈t, compute K′=eC3,i,d^ID,1/eC2,d^ID,0 and M′=C0/C1⋅K′. Then the user computes h=H1C0,C1,C2,C3,1,…,C3,t,K′,M′ and checks whether eC2,Φ^⋅Ψ^h′=eg,Γ^. If the equality holds, then output M′. If the equality does not hold for all i∈t, then output ⊥.Correctness. Assume that ID∈S (say ID=IDi) and hID=HID. Note that eFID,g^=eg,F^ID since the discrete logarithms of both sides are equal. We have(7)K′=eC3,i,d^ID,1eC2,d^ID,0=eFIDis,g^regs,g^αF^IDr=e∏j∈nIjhIDjs,g^regs,g^α∏j∈nI^jhIDjr=1eg,g^αs=ΛsΩs=K,and thus(8)M′=C0C1⋅K′=M⋅eg,g^αβseg,g^αβ−1seg,g^αs=M.Besides, the integrity of the ciphertext and the message can be verified by whethereC2,Φ^⋅Ψ^h′=eg,Γ^.Remark 3.
In the computations ofFID=∏i∈nIihi (F^ID=∏i∈nIihi), it seems that lots of scalar operations for G (G^) must be performed. However, we can construct an index set ℐID=i|hi=1, where h=HID before computing FID (F^ID). We then compute FID=∏i∈ℐIDIi (F^ID=∏i∈ℐIDI^i). Therefore, we can compute FID (F^ID) using only at most n cheap group operations.


## 3.1. The Proposed AMRIBE with Tight Reduction

LetG,G^, and GT be three cyclic multiplicative groups with prime order p and g,g^ be the generators of G,G^, respectively. In this scheme, we adopt type 3 pairing, i.e., e:G×G^⟶GT. The proposed scheme consists of the following algorithms:Setup1λ: taking as input a security parameter 1λ, KGC performs as follows:(1)
Chooseα,β⟵$Zp.(2)
Choose two cryptographic hash functionsH:0,1∗⟶0,1n and H1:0,1∗⟶Zp, where n is a positive integer.(3)
ComputeΩ=eg,g^αβ,Λ=eg,g^αβ−1.(4)
Fori∈n, choose νi⟵$Zp and compute Ii=gνi,I^i=g^νi.(5)
Chooseϕ,ψ⟵$Zp, and compute Φ^=g^ϕ,Ψ^=g^ψ.(6)
Publish the system parameter(6)param=G,G^,GT,e,p,g,Ω,Λ,Iii∈n,Φ^,Ψ^,H,H1.and keep secret the master secret keymsk=g^,g^α,I^ii∈n.KeyExtractmsk,ID: taking as input the master secret key msk=g^,g^α,I^ii∈n and an identity ID, KGC computes the private key for ID as follows. For convenience, given an identity ID, where the corresponding hash value HID is hID, we define a function F^ID=∏i∈nI^ihIDi.(1)
Chooser⟵$Zp(2)
ComputeF^ID(3)
Set the private keydID=d^ID,0,d^ID,1=g^αF^IDr,g^rEncryptS,M: taking as input an identity set S=ID1,…,IDt for a positive integer t and a message M∈GT, the sender performs as follows. For convenience, given an identity ID, where the corresponding hash value HID is hID, we define a function FID=∏i∈nIihIDi.(1)
Chooses⟵$Zp.(2)
Fori∈t, compute FIDi.(3)
ComputeC0=M⋅Ωs,C1=Λs,C2=gs,C3,i=FIDis for i∈t, and K=Λs/Ωs.(4)
Computeh=H1C0,C1,C2,C3,1,…,C3,t,K,M, and Γ^=Φ^⋅Ψ^hs.(5)
The ciphertext isC=C0,C1,C2,C3,ii∈t,Γ^.DecryptC,dID: taking as input a ciphertext C=C0,C1,C2,C3,ii∈t,Γ^ and a private key dID, a user ID performs as follows. For i∈t, compute K′=eC3,i,d^ID,1/eC2,d^ID,0 and M′=C0/C1⋅K′. Then the user computes h=H1C0,C1,C2,C3,1,…,C3,t,K′,M′ and checks whether eC2,Φ^⋅Ψ^h′=eg,Γ^. If the equality holds, then output M′. If the equality does not hold for all i∈t, then output ⊥.Correctness. Assume that ID∈S (say ID=IDi) and hID=HID. Note that eFID,g^=eg,F^ID since the discrete logarithms of both sides are equal. We have(7)K′=eC3,i,d^ID,1eC2,d^ID,0=eFIDis,g^regs,g^αF^IDr=e∏j∈nIjhIDjs,g^regs,g^α∏j∈nI^jhIDjr=1eg,g^αs=ΛsΩs=K,and thus(8)M′=C0C1⋅K′=M⋅eg,g^αβseg,g^αβ−1seg,g^αs=M.Besides, the integrity of the ciphertext and the message can be verified by whethereC2,Φ^⋅Ψ^h′=eg,Γ^.Remark 3.
In the computations ofFID=∏i∈nIihi (F^ID=∏i∈nIihi), it seems that lots of scalar operations for G (G^) must be performed. However, we can construct an index set ℐID=i|hi=1, where h=HID before computing FID (F^ID). We then compute FID=∏i∈ℐIDIi (F^ID=∏i∈ℐIDI^i). Therefore, we can compute FID (F^ID) using only at most n cheap group operations.


## 4. Security Proofs

Theorem 1.
The proposed AMRIBE scheme isτ,ϵ-IND-MID-CCA secure in the standard model if the τ′,ϵ′-DBDH-3 assumption holds, where ϵ=ϵ′ and τ=τ′−OqD⋅TP (qD is the maximum number of Decrypt queries and TP is the time required for a pairing).Proof.
Giveng,g^,g^a,g^b,gb,gc,g^c,Z, the challenger C simulates the following game for the adversary A:
Setup:C performs as follows:(1)
Choose two cryptographic hash functionsH:0,1∗⟶0,1n and H1:0,1∗⟶Zp, where n is the length of an identity.(2)
SetΩ=egb,g^a,Λ=egb/g,g^a=eg,g^ab−1.(3)
Fori∈n, choose νi⟵$Zp and compute Ii=gνi,I^i=g^νi.(4)
Chooseϕ,ψ⟵$Zp, and compute Φ^=g^ϕ,Ψ^=g^ψ.(5)
Set the master secret keymsk=g^,g^a,I^ii∈n.(6)
Send the system parameter(9)param=G,G^,GT,e,p,g,Ω,Λ,Iii∈n,Φ^,Ψ^,H,H1toA.
Phase 1: in this phase,A is allowed to make queries from KeyExtract and Decrypt oracles. Since C knows the master secret key msk, it can easily answer KeyExtract and Decrypt queries as the same way as the proposed scheme.
Challenge:A sends M0,M1 and a set of receivers ID∗=ID1∗,…,IDt∗ for a positive integer t to C, where M0,M1 are two distinct messages with the same length, and KeyExtractIDi∗ has not been queried in Phase 1 for i∈t. Then C performs as follows:(1)
Chooseβ⟵$0,1 compute C0=Mβ⋅Z(2)
ComputeC1=Z/egc,g^a,K=1/egc,g^a(3)
SetC2=gc(4)
Fori∈t, let hi∗=HIDi∗, compute C3,i=gc∑j∈nνjhi∗j(5)
Computeh=H1C0,C1,C2,C3,1,…,C3,t,K,Mβ, and Γ^=g^cϕ+ψh(6)
Output the challenge ciphertextC∗=C0,C1,C2,C3,ii∈t,Γ^
Phase 2:A makes the same queries as Phase 1. However, A is unable to query DecryptC∗,ID and KeyExtractID for ID∈ID∗.
Guess: finally,A outputs a bit β′ and wins the game if β′=β. Then, C outputs 1 if A wins the game; otherwise, outputs 0.
Perfect simulation: sinceC has full control on the master secret key msk, KeyExtract oracle and Decrypt oracle can be simulated perfectly. As for the challenge ciphertext C∗, we implicitly set s=c. If Z=eg,g^abc, then we have that(i)
C0=Mβ⋅Z=Mβ⋅egb,g^ac=Mβ⋅Ωc(ii)
C1=Z/egc,g^a=eg,g^abc/eg,g^ac=eg,g^ab−1c=Λc(iii)
C2=gc(iv)
Fori∈t,C3,i=gc∑j∈nνjhi∗j=∏j∈ngνihi∗jc=∏j∈nIjhi∗jc(v)
Γ^=g^cϕ+ψh=g^ϕ⋅g^ψhc=Φ^⋅Ψ^hc
Therefore, the challenge ciphertextC∗ is well formed. If Z is a random element in GT, then the distribution of β is independent from A’s view, and thus, the advantage will be 0.
Probability analysis: we then analyse the advantage thatC breaks the DBDH-3 assumption. If Z=eg,g^abc, we have AdvIND−MID−CCAA=Prβ′=β−1/2≥ϵ. If Z is a random element in GT, we have AdvIND−MID−CCAA=Prβ′=β−1/2=0. Therefore, we have(10)PrCg,g^,g^a,g^b,gb,gc,g^c,Z=eg,gabc=1−PrCg,g^,g^a,g^b,gb,gc,g^c,Z⟵GT=1=Prβ′=β|Z=eg,gabc−Prβ′=β|Z⟵GT≥12+ϵ−12≥ϵ.
Time complexity: letqD be the maximum numbers of the Decrypt queries. Since in each Decrypt query, C needs to perform at most 4u pairings, where u is the size of the receiver set, we have that τ′=τ+OqD⋅TP, where TP is the time required for a paring.
Tightness analysis: according to the definition given in Section2.5, a reduction is said to be tight if ϵ′≈ϵ and τ′≈τ. From the above analysis, we have that ϵ=ϵ′ and τ=τ′−OqD⋅TP. Since the DBDH-3 problem is an assume-to-be-hard problem, we have τ′=Oexpλ, where λ is the security parameter and expλ is an exponential function in λ. On the other hand, qD=Opolyλ and Tp=Opoly′λ, where polyλ and polyλ are polynomials of λ. Therefore, we know that τ≈τ′.One may wonder that, since the reduction algorithm is able to generate a private key for any ID and accept any IDs for the challenge ciphertext, whether it is possible that the reduction algorithm generates a private key forID∈ID∗ and decrypt C∗ to check if Z=g,g^abc. Note that our proof strategy is slightly similar to that of [28]. The challenge ciphertext is structured such that, if we decrypt C∗ with the private key for ID∈ID∗, the decryption procedure will succeed no matter the value of Z is. In the decryption algorithm, we recover the message M=C0/C1⋅K. In the reduction algorithm, we can see that both C2,C3,i are valid no matter the value of Z is. Thus, if we compute K=eC3,i,d^ID,1/eC2,d^ID,0, then we will have K=1/eg,g^ac. It leads that(11)C0C1⋅K=Mβ⋅ZZ/egc,g^a⋅1eg,g^ac=Mβ.Theorem 2.
The proposed AMRIBE scheme isτ,ϵ-ANON-MID-CCA secure in the standard model if the τ′,ϵ′-DBDH-3 assumption holds, where ϵ=ϵ′ and τ=τ′−OqD⋅TP (qD is the maximum number of Decrypt queries and TP is the time required for a pairing).Proof.
Giveng,g^,g^a,g^b,gb,gc,g^c,Z, the challenger C simulates the following game for the adversary A:
Setup:C performs as follows.(1)
Choose two cryptographic hash functionsH:0,1∗⟶0,1n and H1:0,1∗⟶Zp, where n is a positive integer.(2)
SetΩ=egb,g^a,Λ=egb/g,g^a=eg,g^ab−1.(3)
Fori∈n, choose νi⟵$Zp and compute Ii=gνi,I^i=g^νi.(4)
Chooseϕ,ψ⟵$Zp, and compute Φ^=g^ϕ,Ψ^=g^ψ.(5)
Set the master secret keymsk=g^,g^a,I^ii∈n.(6)
Send the system parameter(12)param=G,G^,GT,e,p,g,Ω,Λ,Iii∈n,Φ^,Ψ^,H,H1toA.
Phase 1: in this phase,A is allowed to make queries from KeyExtract and Decrypt oracles. Since C knows the master secret key msk, it can easily answer KeyExtract and Decrypt queries as the same way as the proposed scheme.
Challenge:A sends M, ID∗=ID0∗,ID1∗, and a set of identities ID2∗,…,IDt∗ for a positive integer t to C, where KeyExtractIDi∗ has not been queried in Phase 1 for IDi∗∈ID∗. Then C performs as follows:(1)
Chooseβ⟵$0,1 compute C0=M⋅Z(2)
ComputeC1=Z/egc,g^a,K=1/egc,g^a(3)
SetC2=gc(4)
Fori∈2,t∪β, let hi∗=HIDi∗, compute C3,i=gc∑j∈nνjhi∗j(5)
ComputeΓ^=g^cϕ+ψh, where h=H1C0,C1,C2,C3,β,C3,2,…,C3,t,K,M(6)
Output the challenge ciphertextC∗=C0,C1,C2,C3,ii∈2,t∪β,Γ^
Phase 2:A makes the same queries as Phase 1. However, A is unable to query DecryptC∗,ID and KeyExtractID for ID∈ID∗.
Guess: finallyA outputs a bit β′ and wins the game if β′=β. Then C outputs 1 if A wins the game; otherwise outputs 0.
Perfect simulation: sinceC has full control on the master secret key msk, KeyExtract oracle and Decrypt oracle can be simulated perfectly. As for the challenge ciphertext C∗, we implicitly set s=c. If Z=eg,g^abc, then we have that(i)
C0=M⋅Z=M⋅egb,g^ac=M⋅Ωc(ii)
C1=Z/egc,g^a=eg,g^abc/eg,g^ac=eg,g^ab−1c=Λc(iii)
C2=gc(iv)
Fori∈2,t∪β,C3,i=gc∑j∈nνjhi∗j=∏j∈ngνihi∗jc=∏j∈nIjhi∗jc(v)
Γ^=g^ϕ+ψh=g^ϕ⋅g^ψhc=Φ^⋅Ψ^hc
Therefore, the challenge ciphertextC∗ is well formed. If Z is a random element in GT, then the distribution of β is independent from A’s view, and thus, the advantage will be 0.
Probability analysis: we then analyse the advantage thatC breaks the DBDH-3 assumption. If Z=eg,g^abc, we have AdvANON−MID−CCAA=Prβ′=β−1/2≥ϵ. If Z is a random element in GT, we have AdvANON−MID−CCAA=Prβ′=β−1/2=0. Therefore, we have(13)PrCg,g^,g^a,g^b,gb,gc,g^c,Z=eg,gabc=1−PrCg,g^,g^a,g^b,gb,gc,g^c,Z⟵GT=1=Prβ′=β|Z=eg,gabc−Prβ′=β|Z⟵GT≥12+ϵ−12≥ϵ.
Time complexity: letqD be the maximum numbers of the Decrypt queries. Since in each Decrypt query, C needs to perform at most 4u pairings, where u is the size of the receiver set, we have that τ′=τ+OqD⋅TP, where TP is the time required for a paring.
Tightness analysis: according to the definition given in Section2.5, a reduction is said to be tight if ϵ′≈ϵ and τ′≈τ. From the above analysis, we have that ϵ=ϵ′ and τ=τ′−OqD⋅TP. Since the DBDH-3 problem is an assume-to-be-hard problem, we have τ′=Oexpλ, where λ is the security parameter and expλ is an exponential function in λ. On the other hand, qD=Opolyλ and Tp=Opoly′λ, where polyλ and poly′λ are polynomials of λ. Therefore, we know that τ≈τ′.


## 5. Comparisons

In this section, we give comparisons of our schemes with the existing schemes in both properties and efficiency. The notations used in this section are shown in Table1, and the comparisons for the properties and performances between our scheme and the existing works are shown in Tables 2 and 3, respectively. For convenience, we set the following scenario to quantize the efficiency. When a sender wants to share a file with t receivers, she/he first encrypts a symmetric key using the Encrypt algorithm of an AMRIBE scheme and then encrypts the file with this symmetric key. The “Encryption cost” means the computation cost to generate the ciphertext for the symmetric key, and the “Ciphertext Length” is the bit length of the ciphertext for the symmetric key. When a receiver wants to recover the shared file, she/he first recovers the symmetric key using the Decrypt algorithm of the AMRIBE scheme and then recovers the shared file. The “Decryption Cost” in the following tables means the computation cost to recover the symmetric key. In the comparison of computation cost, we mainly consider the costs of some heavy operations, such as scalar operation in G,G^,GT and pairing, and omit some lightweight operations, such as hash function and symmetric encryption. The reason is that the former is much more costly than the latter. To better evaluate the efficiency, we may assume that the number of receivers for a ciphertext to be t=100 and an identity is a string with n=80 bits. From [42], we have that Ts,TG,TP=0.55ms,5.16ms,5.05ms and G=G^=GT=256 bits in prime order groups of 128-bit security level. Besides, we consider the implementation of a Map-To-Point function given in [2] as the Map-To-Point function used in these papers, and we have TMTP≈6Ts≈3.3ms. Some of the existing schemes use a symmetric encryption function to encrypt the message. For convenience, we assume that the message length and the symmetric key length are 256 bits. Also we assume that the lengths of the outputs of hash functions and symmetric encryption function in these schemes are 256 bits.Table 1
The notations.
Ts=0.55msThe cost of a scalar operation inGG^TG=5.16msThe cost of a scalar operation inGTTP=5.05msThe cost of a pairing operationTMTP=3.3msThe cost of a Map-To-Point functionκ=256 bitsThe length of a symmetric key/symmetric ciphertextη=256 bitsThe length of the output of a hash functionG=256 bitsThe length of an element inGGT=256 bitsThe length of an element inGTG^p=128 bitsThe length of an element inZpID=80 bitsThe length of an identityROM/STDThe random oracle model/the standard modelFul/SelThe full-ID model/The selective-ID modelOursThe proposed AMRIBETable 2
Property comparison for AMRIBE.
ConfidentialityAnonymitySecurityTightnessFul/SelOutsiderInsiderModel[15]CCA⋄⋄ROMYesSel[18]CCACCA⋄ROMYesFul[43]⋄⋄⋄ROMNoSel[44]⋄⋄⋄ROMYesSel[45]⋄⋄⋄ROMYesSel[46]⋄⋄⋄ROMNoSel[47]CCACCA⋄ROMYesSel[48]⋄⋄⋄ROMYesSel[49]⋄⋄⋄ROMNoFul[50]CCACCA⋄ROMNoSel[17]CCACCACCAROMYesSelOursCCACCACCASTDYesFulTable 3
Efficiency comparison for AMRIBE.
Ciphertext lengthEncryption costDecryption cost[15]κ+η+t+2G≈26624 bitsTp+tTMTP+t2+3Ts≈5836.7 ms2TP+tTs≈65.1 ms[18]2G+3tη≈77312 bits2tTp+4Ts+tTMTP≈1342.2 ms2TP+2Ts≈11.2 ms[43]G+tℤp+κ+2η≈26624 bitstTp+2Ts+tTMTP≈836.1 msTp≈5.05 ms[44]G+tℤp+κ+η≈26368 bitstTp+2Ts+tTMTP≈836.1 msTp≈5.05 ms[45]G+κ2t+1η≈51968 bitstTp+2TstTMTP≈836.1 msTp≈5.05 ms[46]2G+κ+tη≈26368 bitstTp+3Ts+tTMTP≈836.65 msTp+Ts≈5.6 ms[47]2t+1G+κ+η≈51968 bitsTp+tTMTP+2t2+2Ts≈11336.15 ms2Tp2t−1Ts≈119.55 ms[48]3G+ID+tℤp≈13648 bitstTp+4Ts+t+1TMTP≈840.5 ms3Tp≈15.15 ms[49]t+2G+κ≈26368 bitstTp+tTMTP+t+4Ts≈892.2 ms2Tp+Ts≈10.65 ms[50]t+2G+κ≈26368 bitst+1Tp+tTMTP+t+2Ts≈896.15 ms2tTp+Ts≈10.65 ms[17]t+1ℤp+2G+GT+ID≈13776 bitstTp+t+2Ts+TG+t+1TMTP≈899.56 msTp+TG+Ts+Ts≈10.76 msOurs2GT+t+2G≈26624 bitst+3Ts+2TG≈66.97 mst+3TP+Ts≈520.7 msHere, we compare the proposed AMRIBE schemes with the existing AMRIBE schemes [15, 18, 43–50], whose CCA security has been claimed by their authors. The results are shown in Tables 2 and 3. The computation costs for decryption shown in Table 3 are evaluated in the worst case. That is, a receiver must try all t ciphertext components for successful decryption if necessary.From Table2, one can observe that our scheme is the first one achieving full security against chosen-ciphertext attacks with tight reduction in the standard model. As we mentioned in the Introduction, those properties are significant in both theoretic and practical points of view. Besides, from Table 3, we can see that, compared with other existing schemes, the encryption cost is low. Therefore, our scheme fits the scenario that a sender needs frequently to send messages for large amount of users, such as e-mail systems with receiver anonymity. However, the efficiency of the proposed scheme can be further improved in decryption cost, i.e., the decryption is almost the slowest among the existing schemes. Another disadvantage is that ours can only be implemented in groups supporting type 3 pairings, which is an additional requirement compared to other schemes.The symbol “⋄” in Table 2 means that the scheme is claimed to achieve CCA security, but some problem is found. All the cryptanalysis for these schemes can be found in [17, 49, 51, 52], except for [18, 19]. We will give the cryptanalysis for [18, 19] in Section 5.1.Although the authors of [53] have claimed that their scheme achieves IND-CCA security, they did not prove the anonymity. Therefore, their work is not included in Tables 2 and 3.Note that we do not list the schemes of [54, 55] in our comparison table because their schemes do not meet the basic requirement of identity-based encryption. In [54], Chen et al. proposed two schemes, and in both of their schemes, KeyGen algorithm needs a receiver set as one of the inputs. However, it is impossible for a user to know the receiver set which will be decided in the future. There are two possibilities: one is that the KGC must be online to generate private keys when a user needs to decrypt and the other is that all the ciphertext must be encrypted for a fixed group. Both assumptions are not practical and against the basic requirements of IBE. The problems of schemes in [55] are the same as that of [54].Some of the existing schemes [25, 56] are claimed to be CCA secure; however, they actually achieve only CPA security. The reason is that, in their proofs, the partitioning paradigm is used. That is, all the identities will be separated into two disjoint groups, say group A and group B. The challenger can only generate private keys for IDs of group A, while generate challenge ciphertexts for IDs of group B. When an adversary queries private keys with IDs of group B or challenge ciphertexts with IDs of group A, the challenger aborts the simulation. Therefore, if an adversary is only allowed to make decryption queries with IDs of group A, then that is actually equivalent to CPA security only.


### 5.1. Anonymity Analysis on He et al.’s AMRIBE Scheme

In 2016, He et al. proposed generic construction of AMRIBE [18], which is the preliminary version of [19]. The generic constructions given in the two papers are the same. Due to the page limitation, we give only a high-level overview on the cryptanalysis of He et al.’s AMRIBE scheme. We refer the readers to [18, 19] for more details. The idea of our cryptanalysis is similar to that in [49], where Zhang et al. presented an algorithm for an insider adversary to break the anonymity of the scheme of Zhang and Takagi [50].In He et al.’s scheme, the component associated with the encrypted message in a ciphertext is with the formC1=CID10,CID11…CIDt0,CIDt1. The message M is encrypted in CIDi1 with the encryption algorithm of an IND-CPA secure IBE scheme, i.e., CIDi1⟵IBE.EncParam⌢,ID,svkδM, and CIDi0=H2eg1,HIDir is used for a selected receiver to confirm whether herself is one of the receivers. However, in order to prove the IND-MID-CCA security, the scheme is designed such that r=H3δ,M, which means an insider adversary is able to recover r after successful decryption. Therefore, given an identity ID∗, an insider adversary can easily check whether ID∗ is also one of the receivers by checking if there exists j∈t, such that CIDj1=H2eg1,HID∗r.


## 5.1. Anonymity Analysis on He et al.’s AMRIBE Scheme

In 2016, He et al. proposed generic construction of AMRIBE [18], which is the preliminary version of [19]. The generic constructions given in the two papers are the same. Due to the page limitation, we give only a high-level overview on the cryptanalysis of He et al.’s AMRIBE scheme. We refer the readers to [18, 19] for more details. The idea of our cryptanalysis is similar to that in [49], where Zhang et al. presented an algorithm for an insider adversary to break the anonymity of the scheme of Zhang and Takagi [50].In He et al.’s scheme, the component associated with the encrypted message in a ciphertext is with the formC1=CID10,CID11…CIDt0,CIDt1. The message M is encrypted in CIDi1 with the encryption algorithm of an IND-CPA secure IBE scheme, i.e., CIDi1⟵IBE.EncParam⌢,ID,svkδM, and CIDi0=H2eg1,HIDir is used for a selected receiver to confirm whether herself is one of the receivers. However, in order to prove the IND-MID-CCA security, the scheme is designed such that r=H3δ,M, which means an insider adversary is able to recover r after successful decryption. Therefore, given an identity ID∗, an insider adversary can easily check whether ID∗ is also one of the receivers by checking if there exists j∈t, such that CIDj1=H2eg1,HID∗r.


## 6. Conclusion

Multireceiver identity-based encryption is a one-to-many encryption mechanism which encrypts a message to multiple receivers at the same time efficiently and securely. Such encryption is useful in many applications, e.g., pay-per-view TV, video conferencing, and distance education. Under certain circumstances, users may wish to protect their identities from revealing. To deal with this issue, Fan et al. first proposed the notion of anonymous multireceiver identity-based encryption and gave a concrete AMRIBE scheme. Since then, lots of research studies on these topics have been proposed.In this paper, we give a novel fully secure AMRIBE scheme. To the best of our knowledge, it is the first and only scheme that achieves the IND-MID-CCA and the ANON-MID-CCA security in the standard model with tight reduction. Moreover, compared with other existing schemes, the encryption cost is low. Therefore, our scheme fits the scenario that a sender needs frequently to send messages for large amount of users, such as e-mail systems with receiver anonymity. There are still some improvements that can be made to our schemes in the future. For instance, the efficiency of the proposed AMRIBE with tight reduction may be further improved, especially in the decryption cost. Besides, due to the thread of the supreme computing power of quantum computers, the researches of postquantum cryptographic primitives are becoming significant. Lots of postquantum ID-based schemes [57–59] are proposed in the literature as well. Hence, another direction for our future research could be figuring out an AMRIBE scheme achieving tight security and CCA security in postquantum setting.



---

*Source: 5519721-2021-06-15.xml*