# On the Anonymity of Identity-Based Encryption

Authors: Song Luo; Ning Hu
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Anonymity of identity-based encryption (IBE) means that given a ciphertext, one cannot distinguish the target identity from a random identity. In this paper, we thoroughly discuss the anonymity of IBE systems. We found that the current definition of anonymity is obscure to describe some IBE systems, such as Gentry IBE system. Furthermore, current definition cannot express the degree of anonymity. So we divide the degree of anonymity into weak anonymity and strong anonymity based on indistinguishability between different games. For weakly anonymous IBE systems, the target identity in a ciphertext cannot be distinguished from a random identity. For strongly anonymous IBE systems, the whole ciphertext cannot be distinguished from a random tuple. We also discuss the type of anonymity and divide it into two types. Type 1 means that a random tuple can be seen as a valid ciphertext, while type 2 cannot. Based on our new definitions, we show that three famous IBE systems, Gentry IBE system, Boyen-Waters IBE system, and Lewko IBE system, have strong but different types of anonymity.


---

## Body

## 1. Introduction

Shamir [1] proposed the concept of identity-based encryption (IBE) in 1984 to simplify the public key infrastructure. In an IBE system, public keys for users can be formed from arbitrary strings such as e-mail addresses, IP addresses, or other meaningful strings. Anyone can encrypt messages using the identity, and only the owner of the corresponding secret key can decrypt the messages. But Shamir did not give a concrete construction of IBE until Boneh and Franklin [2] presented the first practical IBE system based on groups with efficiently computable bilinear maps. Another but less efficient IBE system using quadratic residues was proposed by Cocks [3]. After that, many new IBE systems are proposed [4–11].Anonymous IBE was first noticed by Boyen [12] and later formalized by Abdalla et al. [13, 14]. Roughly speaking, an IBE system is said to be recipient anonymous or simply anonymous if the ciphertext leaks no information about the recipient’s identity. In other words, an attack cannot distinguish the target identity from a random identity for a ciphertext. Recently, people found that the anonymity of IBE can help to construct public key encryption with keyword search (PEKS) systems [13, 15–17].The first anonymous IBE system is Boneh-Franklin IBE system [2]. In fact, this system has intrinsic anonymity; that is, its semantic security equals anonymity. But Boneh-Franklin IBE system is proposed in the random oracle model [18]. Boyen and Waters [8] gave the first construction of anonymous IBE in the standard model under the decisional bilinear Diffie-Hellman (BDH) and decisional linear assumptions. Another efficient construction of anonymous IBE in the standard model was proposed by Gentry [9], but it is proven secure under a dynamic and complicates assumption. After that, many new anonymous IBE systems in the standard model are proposed [19–21]. An extension of anonymous IBE, named committed blind anonymous IBE, was proposed by Camenisch et al. [22] in which a user can request the decryption key for a given identity without the key generation entity learning the identity.When studying how to construct anonymous IBE systems, researchers have found if asymmetric bilinear maps are used in previous IBE systems [4–7]; these systems seem anonymous. But how to prove anonymous security of these systems from simple assumptions was unknown until Ducas [23] gave a positive answer. He showed that an IBE system can be proven anonymous with some minor modification. Another anonymous IBE system using asymmetric bilinear map is proposed by Chen et al. [24]. Recently, Herranz et al. [25] discussed the relations between semantic security and anonymity for IBE systems.When an “anonymous” IBE system is constructed, we should prove its anonymity. It seems to prove anonymity for IBE systems, we only need to prove that we cannot distinguish the target identity from the challenge ciphertext in the security game for anonymity. However, current anonymous IBE systems, except Gentry IBE system [9], all use a stronger game called GameRandom than the standard game for anonymity where the challenge ciphertext is composed of independently random group elements to prove anonymity. Obviously, if a valid ciphertext is indistinguishable from a random tuple, it is definitely anonymous. However, the game GameRandom is overqualified for anonymity, because anonymity only requires that an attacker cannot distinguish the target identity for a ciphertext. Hence, current definition of anonymity is not complete enough to describe the anonymity of current IBE systems.Our Results. We make a concrete analysis of the anonymity of identity-based encryption systems. We found that current definition of anonymity is obscure to describe some IBE systems, such as Gentry IBE system [9]. Furthermore, current definition cannot express the degree of anonymity. By using the indistinguishability of some related security games, we divide anonymity into two degrees: weak anonymity and strong anonymity. Weak anonymity equals current definition of anonymity, in which the target identity for a ciphertext cannot be distinguished from a random identity. For strongly anonymous IBE systems, the whole ciphertext cannot be distinguished from a random tuple. We also discuss the type of anonymity and divide it into two types. Type 1 means that a random tuple can be seen as a valid ciphertext for some identity, while type 2 cannot. Based on our discussion, we analyse some IBE systems. We show that three famous IBE systems, Gentry IBE System [9], Boyen-Waters IBE system [8], and Lewko IBE System [26], have strong but different types of anonymity.Organization. The paper is organized as follows. We give necessary background information and definitions of security in Section 2. We then analyse the anonymity and define different degrees and types of anonymity in Section 3. In Section 4, we discuss the anonymity of some current IBE systems. At last we conclude the paper with Section 5.


## 2. Background

In this section, we briefly review the concepts of the bilinear maps, identity-based encryption, and its security models for semantic security and anonymity.


### 2.1. Bilinear Maps

Definition 1.
Let𝔾, 𝔾T be two cyclic multiplicative groups with prime order p. Let g be a generator of 𝔾 and e:𝔾×𝔾→𝔾T a bilinear map with the following properties:(1)
bilinearity: for allu,v∈𝔾 and for all a,b∈ℤ, one has e(ua,vb)=e(u,v)ab;(2)
nondegeneracy: the map does not send all pairs in𝔾×𝔾 to the identity in 𝔾T. Observe that since 𝔾,𝔾T are groups of prime order, this implies that if g is a generator of 𝔾 then e(g,g) is a generator of 𝔾T.
We say that𝔾 is a bilinear group if the group operation in 𝔾 and the bilinear map e:𝔾×𝔾→𝔾T are both efficiently computable.Bilinear maps are also called pairings. We assume that there is an efficient algorithm𝒢 for generating bilinear groups. The algorithm 𝒢, on input a security parameter λ, outputs a tuple G=[p,𝔾,𝔾1,g∈𝔾,e], where g is a generator and log(p)=Θ(λ).


### 2.2. Algorithms

An IBE system consists of the following four algorithms: Setup, KeyGen, Encrypt, and Decrypt.Setup(1
λ
). This algorithm takes as input the security parameter λ and outputs a public key PK and a master secret key MK. The public key implies also a key space 𝒦(PK) and an identity space ℐ𝒟(PK).KeyGen(MK,ℐ). This algorithm takes as input the master secret key MK and an identity ℐ∈ℐ𝒟(PK) and outputs a secret key SKℐ associated with ℐ.Encrypt(PK,ℐ, M). This algorithm takes as input the public key PK, an identity ℐ, and a message M and outputs a ciphertext CT.Decrypt(SK
ℐ
, CT). This algorithm takes as input a secret key SKℐ and the ciphertext CT. If the ciphertext is an encryption to ℐ, then the algorithm outputs the encrypted message M.


### 2.3. Security Models

The chosen plaintext security (semantic security) and anonymity of an IBE system are defined according to the followingIND-ID-CPA (indistinguishability against full identity and chosen plaintext attacks) game and ANON-ID-CPA (anonymity against full identity and chosen plaintext attacks) game, respectively.IND-ID-CPA GameSetup. The challenger ℬ runs the Setup algorithm and gives PK to the adversary 𝒜.Phase 1. The adversary 𝒜 submits an identity ℐ. The challenger creates a secret key SKℐ for that identity and gives it to the adversary.Challenge.
𝒜 submits a challenge identity ℐ* and two equal length messages M0,M1 to ℬ with the restriction that each identity ℐ given out in the key phase must not be ℐ*. Then ℬ flips a random coin β∈{0,1} and passes the ciphertext CT*= Encrypt(PK,Mβ,ℐ*) to 𝒜.Phase 2. Phase 1 is repeated with the restriction that any queried identity ℐ is not ℐ*.Guess.
𝒜 outputs its guess β′ of β.The advantage of𝒜 in this game is defined as Adv𝒜=|Pr[β′=β]-(1/2)|.Definition 2.
One says that an IBE system isIND-ID-CPA secure, if no probabilistic polynomial time adversary 𝒜 has a nonnegligible advantage in winning the IND-ID-CPA game.ANON-ID-CPA  GameSetup. The challenger ℬ runs the Setup algorithm and gives PK to the adversary 𝒜.Phase 1. The adversary 𝒜 submits an identity ℐ. The challenger creates a secret key SKℐ for that identity and gives it to the adversary.Challenge.
𝒜 submits two challenge identities ℐ0*,ℐ1* and a message M to ℬ with the restriction that each identity ℐ given out in the key phase must not be ℐ0* or ℐ1*. Then ℬ flips a random coin μ∈{0,1} and passes the ciphertext CT*=Encrypt(PK,M,ℐμ*) to 𝒜.Phase 2. Phase 1 is repeated with the restriction that any queried identity ℐ is not ℐ0* or ℐ1*.Guess.
𝒜 outputs its guess μ′ of μ.The advantage of𝒜 in this game is defined as Adv𝒜=|Pr[μ′=μ]-(1/2)|.Definition 3.
One says that an IBE system isANON-ID-CPA secure, if no probabilistic polynomial time adversary 𝒜 has a nonnegligible advantage in winning the ANON-ID-CPA game.Some systems such as [8, 27] use weaker notions called IND-sID-CPA (indistinguishability against selective identity and chosen plaintext attacks) security and ANON-sID-CPA (anonymity against selective identity and chosen plaintext attacks) security, which are against selective identity. In the selective identity models, the adversary submits the target identity ℐ* (or ℐ1*, ℐ2*) before public parameters are generated.


## 2.1. Bilinear Maps

Definition 1.
Let𝔾, 𝔾T be two cyclic multiplicative groups with prime order p. Let g be a generator of 𝔾 and e:𝔾×𝔾→𝔾T a bilinear map with the following properties:(1)
bilinearity: for allu,v∈𝔾 and for all a,b∈ℤ, one has e(ua,vb)=e(u,v)ab;(2)
nondegeneracy: the map does not send all pairs in𝔾×𝔾 to the identity in 𝔾T. Observe that since 𝔾,𝔾T are groups of prime order, this implies that if g is a generator of 𝔾 then e(g,g) is a generator of 𝔾T.
We say that𝔾 is a bilinear group if the group operation in 𝔾 and the bilinear map e:𝔾×𝔾→𝔾T are both efficiently computable.Bilinear maps are also called pairings. We assume that there is an efficient algorithm𝒢 for generating bilinear groups. The algorithm 𝒢, on input a security parameter λ, outputs a tuple G=[p,𝔾,𝔾1,g∈𝔾,e], where g is a generator and log(p)=Θ(λ).


## 2.2. Algorithms

An IBE system consists of the following four algorithms: Setup, KeyGen, Encrypt, and Decrypt.Setup(1
λ
). This algorithm takes as input the security parameter λ and outputs a public key PK and a master secret key MK. The public key implies also a key space 𝒦(PK) and an identity space ℐ𝒟(PK).KeyGen(MK,ℐ). This algorithm takes as input the master secret key MK and an identity ℐ∈ℐ𝒟(PK) and outputs a secret key SKℐ associated with ℐ.Encrypt(PK,ℐ, M). This algorithm takes as input the public key PK, an identity ℐ, and a message M and outputs a ciphertext CT.Decrypt(SK
ℐ
, CT). This algorithm takes as input a secret key SKℐ and the ciphertext CT. If the ciphertext is an encryption to ℐ, then the algorithm outputs the encrypted message M.


## 2.3. Security Models

The chosen plaintext security (semantic security) and anonymity of an IBE system are defined according to the followingIND-ID-CPA (indistinguishability against full identity and chosen plaintext attacks) game and ANON-ID-CPA (anonymity against full identity and chosen plaintext attacks) game, respectively.IND-ID-CPA GameSetup. The challenger ℬ runs the Setup algorithm and gives PK to the adversary 𝒜.Phase 1. The adversary 𝒜 submits an identity ℐ. The challenger creates a secret key SKℐ for that identity and gives it to the adversary.Challenge.
𝒜 submits a challenge identity ℐ* and two equal length messages M0,M1 to ℬ with the restriction that each identity ℐ given out in the key phase must not be ℐ*. Then ℬ flips a random coin β∈{0,1} and passes the ciphertext CT*= Encrypt(PK,Mβ,ℐ*) to 𝒜.Phase 2. Phase 1 is repeated with the restriction that any queried identity ℐ is not ℐ*.Guess.
𝒜 outputs its guess β′ of β.The advantage of𝒜 in this game is defined as Adv𝒜=|Pr[β′=β]-(1/2)|.Definition 2.
One says that an IBE system isIND-ID-CPA secure, if no probabilistic polynomial time adversary 𝒜 has a nonnegligible advantage in winning the IND-ID-CPA game.ANON-ID-CPA  GameSetup. The challenger ℬ runs the Setup algorithm and gives PK to the adversary 𝒜.Phase 1. The adversary 𝒜 submits an identity ℐ. The challenger creates a secret key SKℐ for that identity and gives it to the adversary.Challenge.
𝒜 submits two challenge identities ℐ0*,ℐ1* and a message M to ℬ with the restriction that each identity ℐ given out in the key phase must not be ℐ0* or ℐ1*. Then ℬ flips a random coin μ∈{0,1} and passes the ciphertext CT*=Encrypt(PK,M,ℐμ*) to 𝒜.Phase 2. Phase 1 is repeated with the restriction that any queried identity ℐ is not ℐ0* or ℐ1*.Guess.
𝒜 outputs its guess μ′ of μ.The advantage of𝒜 in this game is defined as Adv𝒜=|Pr[μ′=μ]-(1/2)|.Definition 3.
One says that an IBE system isANON-ID-CPA secure, if no probabilistic polynomial time adversary 𝒜 has a nonnegligible advantage in winning the ANON-ID-CPA game.Some systems such as [8, 27] use weaker notions called IND-sID-CPA (indistinguishability against selective identity and chosen plaintext attacks) security and ANON-sID-CPA (anonymity against selective identity and chosen plaintext attacks) security, which are against selective identity. In the selective identity models, the adversary submits the target identity ℐ* (or ℐ1*, ℐ2*) before public parameters are generated.


## 3. Analysis of Anonymity

Most IBE systems are constructed on bilinear maps. However, it is hard to construct anonymous IBE systems due to the bilinearity of bilinear maps, that is, for allu,v∈𝔾 and for all a,b∈ℤp, we have e(ua,vb)=e(ub,va). For pairing-based IBE systems, it is easy for us to test the target identity if an IBE system is not anonymous. Roughly speaking, if an IBE system is not anonymous, supposing that C1,…,Ck∈𝔾 are components of a ciphertext of such a system, we can construct elements a1,…,ak∈𝔾^ from the public parameters and some identity ℐ to check whether e(C1,a1)⋯e(Ck,ak)=1, where e:𝔾×𝔾^→𝔾T denotes the bilinear map used in the system. If the equation is true, the target identity is ℐ. Using this method, we can easily see that some previous IBE systems are not anonymous, such as [4–7, 10, 11].Gentry proposed the concept ofANON-IND-ID-CPA (anonymity and indistinguishability against full identity and chosen plaintext attacks) security in [9] which is the conjunction of IND-ID-CPA security and ANON-ID-CPA security. It seems that Gentry’s definition is equivalent to IND-ID-CPA security and ANON-ID-CPA security, but there is a flaw which makes them not equivalent. To make up this flaw in Gentry’s definition, we first review Gentry’s definition and rewrite these definitions using the indistinguishability between some similar security games.ANON-IND-ID-CPA  GameSetup. The challenger ℬ runs the Setup algorithm and gives PK to the adversary 𝒜.Phase 1. The adversary 𝒜 submits an identity ℐ. The challenger creates a secret key SKℐ for that identity and gives it to the adversary.Challenge.
𝒜 submits two challenge identities ℐ0*,ℐ1* and two equal length message M0,M1 to ℬ with the restriction that each identity ℐ given out in the key phase must not be ℐ0* or ℐ1*. Then ℬ picks two random bits β,μ∈{0,1} and passes the ciphertext CT*=Encrypt(PK,Mβ,ℐμ*) to 𝒜.Phase 2. Phase 1 is repeated with the restriction that any queried identity ℐ is not ℐ0* or ℐ1*.Guess.
𝒜 outputs its guess β′ of β and μ′ of μ.The advantage of𝒜 in this game is defined as Adv𝒜=|Pr[β′=β∧μ′=μ]-(1/4)|.Definition 4.
One says that an IBE system isANON-IND-ID-CPA secure, if no probabilistic polynomial time adversary 𝒜 has a nonnegligible advantage in winning the ANON-IND-ID-CPA game.Though theANON-IND-ID-CPA game is the conjunction of the IND-ID-CPA game and the ANON-ID-CPA game, they are not always equivalent. If the assumption used in the IND-ID-CPA game is different from the assumption used in the ANON-ID-CPA game, these two games cannot be combined to be the ANON-IND-ID-CPA game. In Gentry’s definition, they are equivalent because only one assumption called the Decision q-ABDHE assumption is used in these games.To cover the difference caused by different assumptions and full or selective security, we focus on the core of these games. In theIND-ID-CPA game, the adversary needs to distinguish an encryption of the chosen message from an encryption of a random message both for the challenge identity, while in the ANON-ID-CPA game, the adversary needs to distinguish an encryption for the challenge identity from an encryption for a random identity both of the chosen message. And in the combined ANON-IND-ID-CPA game, the adversary needs to distinguish an encryption of the chosen message for the challenge identity from an encryption of a random message for a random identity. Hence, we can redefine these concepts using the indistinguishability between different challenge ciphertexts.LetM be a message and ℐ* a challenge identity both chosen by the adversary. Let MR be a random message and ℐR a random identity. We define the following games which differ on what challenge ciphertext is given by the simulator to the adversary.(i)
GameM,ℐ*: it is the basic game. The challenger runs the Setup algorithm and gives the public key to the adversary. The adversary can make a secret key query for ℐ, where ℐ is not equal to the target identity ℐ*. The challenge ciphertext is Encrypt(PK,M,ℐ*).(ii)
GameMR,ℐ*: this is like GameM,ℐ* except that the challenge ciphertext is Encrypt(PK,MR,ℐ*).(iii)
GameM,ℐR: this is like GameM,ℐ* except that the challenge ciphertext is Encrypt(PK,M,ℐR).(iv)
GameMR,ℐR: this is like GameM,ℐ* except that the challenge ciphertext is Encrypt(PK,MR,ℐR).Using the indistinguishability between these games, we rewrite the definitions ofANON-IND-ID-CPA, IND-ID-CPA, and ANON-ID-CPA securities as follows.Definition 5.
One says that an IBE system isANON-IND-ID-CPA secure, if no probabilistic polynomial time adversary 𝒜 has a nonnegligible advantage in distinguishing between GameM,ℐ* and GameMR,ℐR.Definition 6.
One says that an IBE system isIND-ID-CPA secure, if no probabilistic polynomial time adversary 𝒜 has a nonnegligible advantage in distinguishing between GameM,ℐ* and GameMR,ℐ*.Definition 7.
One says that an IBE system isANON-ID-CPA secure, if no probabilistic polynomial time adversary 𝒜 has a nonnegligible advantage in distinguishing between GameM,ℐ* and GameM,ℐR.Definitions for selective identity are similar except that in all the games the adversary should submit the target identityℐ* before public parameters are generated. Note that GameMR,ℐ*, GameM,ℐR, and GameMR,ℐR are three different games. We have the following result for the relation between ANON-IND-ID-CPA security, IND-ID-CPA security, and ANON-ID-CPA security.Lemma 8.
If an IBE systemℰ is IND-ID-CPA secure and ANON-ID-CPA secure, then ℰ is ANON-IND-ID-CPA secure.Proof.
We have(1)|GameM,ℐ*Adv𝒜-GameMR,ℐ*Adv𝒜|≤ϵ1,(2)|GameMR,ℐ*Adv𝒜-GameMR,ℐRAdv𝒜|≤ϵ2,
where ϵ1,ϵ2 are both negligible. Equation (1) holds because ℰ is IND-ID-CPA secure and (2) holds because ℰ is ANON-ID-CPA secure. So
(3)|GameM,ℐ*Adv𝒜-GameMR,ℐRAdv𝒜|≤ϵ1+ϵ2,
which means that ℰ is ANON-IND-ID-CPA secure.However, it is still unknown whether ANON-IND-ID-CPA security is equivalent toIND-ID-CPA security and ANON-ID-CPA security. The following lemma is an efficient method to prove the anonymity, which is used for some previous systems, such as Caro-Iovino-Persiano HIBE system [28], Seo-Cheon HIBE system [29].Lemma 9.
If an IBE systemℰ is IND-ID-CPA secure, and there is no polynomial time adversary who can distinguish between GameMR,ℐ* and GameMR,ℐR with nonnegligible advantage, then ℰ is ANON-ID-CPA secure.Proof.
We have(4)|GameM,ℐ*Adv𝒜-GameMR,ℐ*Adv𝒜|≤ϵ1,(5)|GameM,ℐRAdv𝒜-GameMR,ℐRAdv𝒜|≤ϵ2,(6)|GameMR,ℐ*Adv𝒜-GameMR,ℐRAdv𝒜|≤ϵ3,
where ϵ1,ϵ2,ϵ3 are all negligible. Equations (4) and (5) hold because ℰ is IND-ID-CPA secure and (6) holds according to the hypothesis. So
(7)|GameM,ℐ*Adv𝒜-GameM,ℐRAdv𝒜|≤ϵ1+ϵ2+ϵ3,
which means that ℰ is ANON-ID-CPA secure.In some anonymous IBE systems, such as Boyen-Waters anonymous IBE system, they use a new game calledGameRandom. We define it as follows.(i)
GameRandom: this is like GameM,ℐ* except that the challenge ciphertext consists of independent random group elements.Note thatGameRandom is different from GameMR,ℐR. Though they are similar concepts, they are not always equivalent. GameRandom is a special game in which the challenge ciphertext is composed of independent random group elements, while the challenge ciphertext of GameMR,ℐR is still a valid ciphertext. Since every element is random, the ciphertext leaks no information about the identity. So if the transition from GameM,ℐ* to GameRandom is computationally indistinguishable, the IBE system is no doubt anonymous. This proof method was used in Boyen-Waters anonymous IBE system and later anonymous IBE systems. Obviously, the transition from GameM,ℐ* to GameM,ℐR is different from the transition from GameM,ℐ* to GameRandom. The difference leads to the following classification of anonymous IBE systems.Definition 10 (weak anonymity).
One says that an IBE system has weak anonymity, if no probabilistic polynomial time adversary𝒜 has a nonnegligible advantage in distinguishing between GameM,ℐ* and GameM,ℐR or distinguishing between GameM,ℐ* and GameMR,ℐR.Definition 11 (strong anonymity).
One says that an IBE system has strong anonymity, if no probabilistic polynomial time adversary𝒜 has a nonnegligible advantage in distinguishing between GameM,ℐ* and GameRandom.Obviously, weak anonymity is the standard definition shown in previous articles where the target identity is indistinguishable from a random identity. It is easy to see that weak anonymity is required for all anonymous IBE systems and strong anonymity implies weak anonymity. So weak anonymity is also called standard anonymity, while strong anonymity is called superstandard anonymity. In the next section, we will analyse some IBE systems based on our definitions of anonymity. We will see that these IBE systems all have strong anonymity. To further clarify the anonymity of IBE systems, we use the difference betweenGameMR,ℐR and GameRandom to define two types of anonymity, named type 1 anonymity and type 2 anonymity. First we define the equivalence of two games. Let GameA, GameB be two games. If any ciphertext output by GameA can seem as a properly distributed ciphertext output by GameB and vice versa, we say that GameA equals GameB or GameA=GameB. Obviously, GameA=GameB means that GameA is indistinguishable from GameB. However, if two games are indistinguishable, they are not always equivalent. For example, for any IND-IND-CPA secure IBE system, GameM,ℐ*≠GameMR,ℐ*, but they are indistinguishable according to the definition of IND-ID-CPA security.Definition 12.
For an anonymous IBE systemℰ, if GameMR,ℐR=GameRandom, one says that ℰ has type 1 anonymity, or else ℰ has type 2 anonymity.If an IBE systemℰ has only weak anonymity, it is obvious that GameMR,ℐR≠GameRandom; that is, ℰ has type 2 anonymity. So there is no type 1 anonymous IBE system with only weak anonymity. For a strongly anonymous IBE system, type 1 anonymity always means that it only needs to prove ℰ’s anonymity in the ANON-IND-ID-CPA game or in the ANON-ID-CPA game, while type 2 anonymity always means that ℰ needs additional steps to prove strong anonymity, for example, proving the indistinguishability of transition from GameMR,ℐR to GameRandom.Note that there is some IBE system which has the propertyGameMR,ℐR=GameRandom, such as Boneh-Boyen IBE system. In Boneh-Boyen IBE system, a ciphertext is like Me(g,g)αs, (uℐh)s, gs. It is easy to see that a random tuple is still a valid ciphertext for some identity and message. But as we know, Boneh-Boyen IBE system is not anonymous because there is a gap between GameM,ℐ and GameM,ℐR.


## 4. Anonymity of Some IBE Systems

In this section, we analyse some IBE systems based on our definitions of anonymity. We discuss three famous anonymous IBE systems: Gentry IBE System [9], Boyen-Waters IBE system [8], and Lewko IBE System [26]. We show that these three IBE systems are all strongly anonymous but have different types.


### 4.1. Gentry IBE System [9]

We show that Gentry’s anonymous IBE system has type 1 strong anonymity. We first briefly describe Gentry IBE system as follows.Setup(1
λ
). Given the security parameter λ, the setup algorithm first gets (p,𝔾,𝔾T,g,e)←𝒢(λ). Next it chooses another random generator h∈𝔾 and random integer α∈ℤp. Then the setup algorithm sets g1=gα. The public key PK is published as
(8)PK=(g,g1,h),
and the master key MK is
(9)MK=(α).KeyGen(MK,ℐ). To generate the secret key SKℐ for an identity ℐ∈ℤp, the key extract algorithm chooses random rℐ∈ℤp and outputs SKℐ as
(10)SKℐ=(rℐ,(hg-rℐ)1/(α-ℐ)).The constraints are thatℐ≠α and the PKG always uses the same random value rℐ for ℐ.Encrypt(PK,ℐ, M). To encrypt a message M∈𝔾T for an identity ℐ, the algorithm chooses random integers s∈ℤp and outputs the ciphertext CT as
(11)CT=(M·e(g,h)-s,g1sg-s·ℐ,e(g,g)s).Decrypt(SK
ℐ
, CT). To decrypt a ciphertext CT=(C,C1,C2) for an identity ℐ, using the corresponding secret key SKℐ=(rℐ,hℐ) outputs
(12)M=C·e(hℐ,C1)·C2rℐ.Lemma 13 (see [9, Theorem 1]).
Gentry IBE system is ANON-IND-ID-CPA secure.Lemma 14.
For Gentry IBE system,GameMR,ℐR=GameRandom.Proof.
Let𝒞1 be the set of all the possible ciphertext output by GameMR,ℐR and 𝒞2 the set of all the possible ciphertext outputs by GameRandom. We will show that 𝒞1=𝒞2.
Obviously, we have𝒞1⊂𝒞2. Note that this claim is true for all IBE systems.
Next, for a random tuple(C,C1,C2), where C1∈𝔾 and C,C2∈𝔾T, we say that it is a valid ciphertext of Gentry-AIBE system. At first we can set C2=e(g,g)s for some s and then we can set C1=g1sg-s·ℐ for some identity ℐ and C=M·e(g,h)-s for some message M. So we have 𝒞2⊂𝒞1.
As a result,𝒞1=𝒞2. This means that the challenge ciphertext output by GameMR,IR can seem as a challenge ciphertext by GameRandom and vice versa. Then for Gentry-AIBE system, GameMR,IR=GameRandom.From Lemmas13 and 14, we get the following result.Theorem 15.
Gentry IBE system has type 1 strong anonymity.


### 4.2. Boyen-Waters IBE System [8]

For an anonymous IBE system, equationGameMR,ℐR=GameRandom means that it is intrinsically strongly anonymous, just as we showed for Gentry IBE system in the previous section. The equation also holds for some previous systems, for example, Boneh-Franklin IBE system. But for some strongly anonymous IBE systems, it does not hold; that is, GameMR,IR≠GameRandom. In fact, these two games are computationally indistinguishable under some assumption, for example, the decisional linear assumption.As an example, we will show that Boyen-Waters anonymous IBE system is a type 2 anonymous IBE system; that is, it does not satisfy the equation. We first briefly describe Boyen-Waters IBE system as follows.Setup(1
λ
). Given the security parameter λ, the setup algorithm first gets (p,𝔾, 𝔾T,g,e)←𝒢(λ). Next it chooses another two random group elements g0,g1∈𝔾 and five random integers ω,t1,t2,t3,t4∈ℤp. Then the setup algorithm sets Ω=e(g,g)t1t2ω,v1=gt1,v2=gt2,v3=gt3,v4=gt4. The public key PK is published as
(13)PK=(Ω,g,g0,g1,v1,v2,v3,v4),
and the master key MK is
(14)MK=(ω,t1,t2,t3,t4).KeyGen(MK,ℐ). To generate the secret key SKℐ for an identity ℐ∈ℤp, the key extract algorithm chooses random r1,r2∈ℤp and outputs SKℐ as
(15)SKℐ=(gr1t1t2+r2t3t4,g-ωt2(g0g1ℐ)-r1t2,g-ωt1(g0g1ℐ)-r1t1,(g0g1ℐ)-r2t4,(g0g1ℐ)-r2t3).Encrypt(PK,ℐ, M). To encrypt a message M∈𝔾T for an identity ℐ, the algorithm chooses random integers s,s1,s2∈ℤp and outputs the ciphertext CT as
(16)CT=(MΩs,(g0g1ℐ)s,v1s-s1,v2s1,v3s-s2,v4s2).Decrypt(SK
ℐ
, CT). To decrypt a ciphertext CT=(C,C1,C2,C3,C4,C5) for an identity ℐ, using the corresponding secret key SKℐ=(d1,d2,d3,d4,d5) outputs
(17)M=C·e(d1,C1)·e(d2,C2)·e(d3,C3)·e(d4,C4)·e(d5,C5).Using the conjunction of Lemmas1,2, and 3 in [8], we have the following result for Boyen-Waters IBE system.Lemma 16.
For Boyen-Waters IBE system,GameM,ℐ* and GameRandom are computationally indistinguishable under the decisional BDH and decisional linear assumptions.Now we show that Boyen-Waters IBE system has type 2 anonymity.Lemma 17.
For Boyen-Waters IBE system,GameMR,ℐR≠GameRandom.Proof.
Given a random tuple(R,R1,R2,R3,R4,R5) where R∈𝔾T and R1,…,R5∈𝔾, we say that it has at most 1/p probability to be a valid ciphertext of BW-AIBE system. At first we set R3=v2s1 and R5=v4s2 for some s1 and s2, respectively, and then we can set R2=v1s-s1 for some s, but a valid ciphertext requires that R4=v3s-s2. Since R4 is a random element of 𝔾, so R4 has only 1/p probability to be v3s-s2. When R4≠v3s-s2, the random tuple cannot be a valid ciphertext which means that GameMR,IR≠GameRandom.From Lemmas16 and 17, we can easily get the following result.Theorem 18.
Boyen-Waters IBE system has type 2 strong anonymity.


### 4.3. Lewko IBE System [26]

Boyen-Waters IBE system only has selective security. We now show that a fully secure IBE system, Lewko IBE system, has type 2 full anonymity. Lewko IBE system is constructed from dual orthonormal bases and can seem as a translation of Lewko-Waters IBE system [11] in prime order groups. In Lewko’s original description, she only gave a proof for chosen plaintext security.Lewko IBE system is constructed on dual orthonormal bases of dual pairing vector spaces. We first review vectors of group elements. Given a group elementg∈𝔾 and a vector v=(v1,…,vn)∈ℤpn, we write gv to denote a n-tuple of elements of 𝔾:gv∶=(gv1,…,gvn). For any a∈ℤp and v,w∈ℤpn, we have (gv)a=gav=(gav1,…,gavn) and gv+w=(gv1+w1,…,gvn+wn). We also use en to denote the pairing of vectors:
(18)en(gv,gw)∶=∏i=1n‍e(gvi,gwi)=e(g,g)v·w.For a fixed (constant) dimensionn, we choose two random bases 𝔹∶=(b1,…,bn) and 𝔹*∶=(b1,…,bn) of ℤpn×n, subject to the constraint that
(19)bi·bj*={0,i≠jψ,i=j(modp).(
𝔹
,
𝔹
*
) are called dual orthonormal bases and Dual(ℤpn) denotes the set of dual orthonormal bases. We then describe Lewko IBE system as follows.Setup(1
λ
). Given the security parameter λ, the setup algorithm first gets (p,𝔾, 𝔾T,g,e)←𝒢(λ). Next it chooses random dual orthonormal bases (𝔻,𝔻*) from Dual(ℤp6). Let 𝔻=(d1,…,d6) and 𝔻=(d1*,…,d6*). It also chooses random values α,θ,σ∈ℤp. The public key is published as
(20)PK=(p,𝔾,Ω=e(g,g)αθd1·d1*,gd1,…,gd4),and the master key is(21)MK=(gθd1*,gαθd1*,gθd2*,gσd3*,gσd4*).KeyGen(MK,ℐ). The key generation algorithm chooses random r1,r2∈ℤp and outputs the secret key as
(22)SKℐ∶=g(α+r1ℐ)θd1*-r1θd2*+r2ℐσd3*-r2σd4*.Encrypt(PK,ℐ, M). To encrypt a message M∈𝔾T for an identity ℐ, the algorithm chooses random integers s1,s2∈ℤp and outputs the ciphertext as
(23)CT=(C1∶=MΩs1,C2∶=gs1d1+s1ℐd2+s2d3+s2ℐd4).Decrypt(SK
ℐ
, CT). The decryption algorithm computes the message as
(24)M=C1en(SKℐ,C2).Security proof of Lewko IBE system used the dual system encryption technique [10]. Its semifunctional keys are like g(α+r1ℐ)θd1*-r1θd2*+r2ℐσd3*-r2σd4*+t5d5*+t6d6* and its semifunctional ciphertext is (MΩs1,gs1d1+wd2+s2d3+s2ℐd4+s5d5+s6d6) where t5,t6,s5,s6←Rℤp. Let GameFinal be the game, where all returned keys are semifunctional and the challenge ciphertext is (R,gs1d1+wd2+s2d3+s2ℐd4+s5d5+s6d6), where R←R𝔾T and w,s5,s6←Rℤp. In [26], Lewko showed that GameM,ℐ is indistinguishable from GameFinal′ under the subspace assumption. We continue her work and show that her IBE system has type 2 strong anonymity.We first review the subspace assumption introduced by Lewko in [26].Definition 19.
Given a group generation𝒢, one defines the following distribution:
(25)G∶=(p,𝔾,𝔾T,g,e)⟵R𝒢,(𝔹,𝔹*)⟵RDual(ℤpn),η,β,τ1,τ2,τ3,μ1,μ2,μ3⟵Rℤp,U1∶=gμ1b1+μ2bk+1+μ3b2k+1,U2∶=gμ1b2+μ2bk+2+μ3b2k+2,…,Uk∶=gμ1bk+μ2b2k+μ3b3k,V1∶=gτ1ηb1*+τ2βbk+1*,V2∶=gτ1ηb2*+τ2βbk+2*,…,Vk∶=gτ1ηbk*+τ2βb2k*,W1∶=gτ1ηb1*+τ2βbk+1*+τ3b2k+1*,W2∶=gτ1ηb2*+τ2βbk+2*+τ3b2k+2*,…,Wk∶=gτ1ηbk*+τ2βb2k*+τ3b3k*,D→∶=(gb1,gb2,…,gb2k,gb3k+1,…,gbn,gηb1*,…,gηbk*,gβbk+1*,…,gβb2k*,gb2k+1*,…,gbn*,U1,U2,…,Uk,μ3).
We define the advantage of an algorithm 𝒜 in breaking the subspace assumption to be
(26)|Pr[𝒜(D→,V1,…,Vk)=1]-Pr[𝒜(D→,W1,…,Wk)=1]|.
We say that the subspace assumption holds if no probabilistic polynomial time algorithm has a nonnegligible advantage in breaking the subspace assumption.Lemma 20.
LetGameFinal′ be the game, where all returned keys are semifunctional and the challenge ciphertext is (R,gs1d1+w2d2+s2d3+w4d4+s5d5+s6d6), where R←R𝔾T and w2,w4,s5,s6←Rℤp. If there exists a polynomial time algorithm 𝒜, where GameFinalAdv𝒜-GameFinal′Adv𝒜=ϵ, then we can construct a polynomial time algorithm ℬ with advantage ϵ to break the subspace assumption with n=6 and k=1.Proof.
ℬ is given D∶=(gb1,gb2,gb4,gb5,gb6,gηb1*,gβb2*,gb3*,gb4*,gβb5*,gβb6*,U1,μ3) along with T1. ℬ should decide whether T1 is distributed as gτ1ηb1*+τ2βb2* or as gτ1ηb1*+τ2βb2*+τ3b3*.
At firstℬ implicitly sets d1=b6*,d2=b5*,d3=b4*,d4=b3*,d5=b2*,d6=b1*. Then ℬ can produce gd1,…,gd4 for the public parameters. Next ℬ sets d1*=b6,d2*=b5,d3*=b4,d4*=b3,d5*=b2,d6*=b1. Note that ℬ only does not know gd4*.
ℬ chooses random values θ,σ,α∈ℤp for itself. It can compute e(g,g)αθd1·d1* as (en(gb6*,gb6))αθ. It gives 𝒜 the public key
(27)PK∶=𝔾,p,e(g,g)αθd1·d1*,gd1,…,gd4.
To respond a key query forℐ, ℬ chooses random values r1,r2′,t5′,t6′∈ℤp. It will set r2=μ3r2′. It forms the secret key as
(28)SKℐ∶=(U1)σr2′g(α+r1ℐ)θd1*-r1θd2*+μ3r2′ℐσd3*+t5′d5*+t6′d6*.
At the challenge phase,ℬ receives two messages M0,M1 and a challenge identity ℐ*. ℬ chooses a random bit b∈{0,1}, a random element R∈𝔾T, and random values w2,s1,s2∈ℤp and sets
(29)C1∶=R,C2∶=gs1d1+w2d2+s2d3+s2ℐ*d4T1.
IfT1=gτ1ηb1*+τ2βb2*, then the exponent vector of T1 is a random linear combination of d5 and d6, so it is in GameFinal. If the exponent of T1 additionally has τ3b3*=τ3d4, it is in GameFinal′. Therefore, ℬ can use the output of 𝒜 to break the subspace assumption.Theorem 21.
Lewko IBE system has type 2 strong anonymity.Proof.
From Lemma20 we know that the ciphertext of Lewko IBE system leaks no information about target identity, so it is anonymous.
Furthermore, note thatd1,…,d6 is a base of ℤp6×6, so gs1d1+w2d2+s2d3+w4d4+s5d5+s6d6 can seem a random element in ℤp6×6. In other words, GameFinal′=GameRandom. So Lewko IBE system has strong anonymity.
Obviously, the set of all possibleC2 is contained in span(gd1,gd2,gd3,gd4). Note that any nonzero vectors in span(gd5,gd6) are not included in span(gd1,gd2,gd3,gd4), so GameMR,ℐR≠GameRandom for Lewko IBE system which means that Lewko IBE system has type 2 anonymity.


### 4.4. Comparison

Like previous analysis for Gentry IBE system, Boyen-Waters IBE system, and Lewko IBE system, we can analyse other anonymous IBE systems. A brief comparison for some anonymous IBE systems is given in Table1. We would find that all listed IBE systems have strong anonymity, that is, superstandard anonymity. Though weak anonymity, that is, standard anonymity, is the current definition of anonymity, to the best of our knowledge, there is no IBE system having only weak anonymity. Hence we leave an open problem to construct an IBE system with only weak anonymity.Table 1
Comparison.
System
Security
Anonymity degree
Anonymity type
Security model
Boneh and Franklin [2]
IND-ID-CPAANON-ID-CPA
Strong
1
Random oracle
Boyen and Waters [8]
IND-sID-CPAANON-sID-CPA
Strong
2
Standard
Gentry [9]
ANON-IND-ID-CPA
Strong
1
Standard
Ducas [23]
IND-sID-CPAANON-sID-CPA
Strong
2
Standard
Lewko [26]
IND-ID-CPAANON-ID-CPA
Strong
2
Standard
Chen et al. [24]
ANON-IND-ID-CPA
Strong
2
Standard


## 4.1. Gentry IBE System [9]

We show that Gentry’s anonymous IBE system has type 1 strong anonymity. We first briefly describe Gentry IBE system as follows.Setup(1
λ
). Given the security parameter λ, the setup algorithm first gets (p,𝔾,𝔾T,g,e)←𝒢(λ). Next it chooses another random generator h∈𝔾 and random integer α∈ℤp. Then the setup algorithm sets g1=gα. The public key PK is published as
(8)PK=(g,g1,h),
and the master key MK is
(9)MK=(α).KeyGen(MK,ℐ). To generate the secret key SKℐ for an identity ℐ∈ℤp, the key extract algorithm chooses random rℐ∈ℤp and outputs SKℐ as
(10)SKℐ=(rℐ,(hg-rℐ)1/(α-ℐ)).The constraints are thatℐ≠α and the PKG always uses the same random value rℐ for ℐ.Encrypt(PK,ℐ, M). To encrypt a message M∈𝔾T for an identity ℐ, the algorithm chooses random integers s∈ℤp and outputs the ciphertext CT as
(11)CT=(M·e(g,h)-s,g1sg-s·ℐ,e(g,g)s).Decrypt(SK
ℐ
, CT). To decrypt a ciphertext CT=(C,C1,C2) for an identity ℐ, using the corresponding secret key SKℐ=(rℐ,hℐ) outputs
(12)M=C·e(hℐ,C1)·C2rℐ.Lemma 13 (see [9, Theorem 1]).
Gentry IBE system is ANON-IND-ID-CPA secure.Lemma 14.
For Gentry IBE system,GameMR,ℐR=GameRandom.Proof.
Let𝒞1 be the set of all the possible ciphertext output by GameMR,ℐR and 𝒞2 the set of all the possible ciphertext outputs by GameRandom. We will show that 𝒞1=𝒞2.
Obviously, we have𝒞1⊂𝒞2. Note that this claim is true for all IBE systems.
Next, for a random tuple(C,C1,C2), where C1∈𝔾 and C,C2∈𝔾T, we say that it is a valid ciphertext of Gentry-AIBE system. At first we can set C2=e(g,g)s for some s and then we can set C1=g1sg-s·ℐ for some identity ℐ and C=M·e(g,h)-s for some message M. So we have 𝒞2⊂𝒞1.
As a result,𝒞1=𝒞2. This means that the challenge ciphertext output by GameMR,IR can seem as a challenge ciphertext by GameRandom and vice versa. Then for Gentry-AIBE system, GameMR,IR=GameRandom.From Lemmas13 and 14, we get the following result.Theorem 15.
Gentry IBE system has type 1 strong anonymity.


## 4.2. Boyen-Waters IBE System [8]

For an anonymous IBE system, equationGameMR,ℐR=GameRandom means that it is intrinsically strongly anonymous, just as we showed for Gentry IBE system in the previous section. The equation also holds for some previous systems, for example, Boneh-Franklin IBE system. But for some strongly anonymous IBE systems, it does not hold; that is, GameMR,IR≠GameRandom. In fact, these two games are computationally indistinguishable under some assumption, for example, the decisional linear assumption.As an example, we will show that Boyen-Waters anonymous IBE system is a type 2 anonymous IBE system; that is, it does not satisfy the equation. We first briefly describe Boyen-Waters IBE system as follows.Setup(1
λ
). Given the security parameter λ, the setup algorithm first gets (p,𝔾, 𝔾T,g,e)←𝒢(λ). Next it chooses another two random group elements g0,g1∈𝔾 and five random integers ω,t1,t2,t3,t4∈ℤp. Then the setup algorithm sets Ω=e(g,g)t1t2ω,v1=gt1,v2=gt2,v3=gt3,v4=gt4. The public key PK is published as
(13)PK=(Ω,g,g0,g1,v1,v2,v3,v4),
and the master key MK is
(14)MK=(ω,t1,t2,t3,t4).KeyGen(MK,ℐ). To generate the secret key SKℐ for an identity ℐ∈ℤp, the key extract algorithm chooses random r1,r2∈ℤp and outputs SKℐ as
(15)SKℐ=(gr1t1t2+r2t3t4,g-ωt2(g0g1ℐ)-r1t2,g-ωt1(g0g1ℐ)-r1t1,(g0g1ℐ)-r2t4,(g0g1ℐ)-r2t3).Encrypt(PK,ℐ, M). To encrypt a message M∈𝔾T for an identity ℐ, the algorithm chooses random integers s,s1,s2∈ℤp and outputs the ciphertext CT as
(16)CT=(MΩs,(g0g1ℐ)s,v1s-s1,v2s1,v3s-s2,v4s2).Decrypt(SK
ℐ
, CT). To decrypt a ciphertext CT=(C,C1,C2,C3,C4,C5) for an identity ℐ, using the corresponding secret key SKℐ=(d1,d2,d3,d4,d5) outputs
(17)M=C·e(d1,C1)·e(d2,C2)·e(d3,C3)·e(d4,C4)·e(d5,C5).Using the conjunction of Lemmas1,2, and 3 in [8], we have the following result for Boyen-Waters IBE system.Lemma 16.
For Boyen-Waters IBE system,GameM,ℐ* and GameRandom are computationally indistinguishable under the decisional BDH and decisional linear assumptions.Now we show that Boyen-Waters IBE system has type 2 anonymity.Lemma 17.
For Boyen-Waters IBE system,GameMR,ℐR≠GameRandom.Proof.
Given a random tuple(R,R1,R2,R3,R4,R5) where R∈𝔾T and R1,…,R5∈𝔾, we say that it has at most 1/p probability to be a valid ciphertext of BW-AIBE system. At first we set R3=v2s1 and R5=v4s2 for some s1 and s2, respectively, and then we can set R2=v1s-s1 for some s, but a valid ciphertext requires that R4=v3s-s2. Since R4 is a random element of 𝔾, so R4 has only 1/p probability to be v3s-s2. When R4≠v3s-s2, the random tuple cannot be a valid ciphertext which means that GameMR,IR≠GameRandom.From Lemmas16 and 17, we can easily get the following result.Theorem 18.
Boyen-Waters IBE system has type 2 strong anonymity.


## 4.3. Lewko IBE System [26]

Boyen-Waters IBE system only has selective security. We now show that a fully secure IBE system, Lewko IBE system, has type 2 full anonymity. Lewko IBE system is constructed from dual orthonormal bases and can seem as a translation of Lewko-Waters IBE system [11] in prime order groups. In Lewko’s original description, she only gave a proof for chosen plaintext security.Lewko IBE system is constructed on dual orthonormal bases of dual pairing vector spaces. We first review vectors of group elements. Given a group elementg∈𝔾 and a vector v=(v1,…,vn)∈ℤpn, we write gv to denote a n-tuple of elements of 𝔾:gv∶=(gv1,…,gvn). For any a∈ℤp and v,w∈ℤpn, we have (gv)a=gav=(gav1,…,gavn) and gv+w=(gv1+w1,…,gvn+wn). We also use en to denote the pairing of vectors:
(18)en(gv,gw)∶=∏i=1n‍e(gvi,gwi)=e(g,g)v·w.For a fixed (constant) dimensionn, we choose two random bases 𝔹∶=(b1,…,bn) and 𝔹*∶=(b1,…,bn) of ℤpn×n, subject to the constraint that
(19)bi·bj*={0,i≠jψ,i=j(modp).(
𝔹
,
𝔹
*
) are called dual orthonormal bases and Dual(ℤpn) denotes the set of dual orthonormal bases. We then describe Lewko IBE system as follows.Setup(1
λ
). Given the security parameter λ, the setup algorithm first gets (p,𝔾, 𝔾T,g,e)←𝒢(λ). Next it chooses random dual orthonormal bases (𝔻,𝔻*) from Dual(ℤp6). Let 𝔻=(d1,…,d6) and 𝔻=(d1*,…,d6*). It also chooses random values α,θ,σ∈ℤp. The public key is published as
(20)PK=(p,𝔾,Ω=e(g,g)αθd1·d1*,gd1,…,gd4),and the master key is(21)MK=(gθd1*,gαθd1*,gθd2*,gσd3*,gσd4*).KeyGen(MK,ℐ). The key generation algorithm chooses random r1,r2∈ℤp and outputs the secret key as
(22)SKℐ∶=g(α+r1ℐ)θd1*-r1θd2*+r2ℐσd3*-r2σd4*.Encrypt(PK,ℐ, M). To encrypt a message M∈𝔾T for an identity ℐ, the algorithm chooses random integers s1,s2∈ℤp and outputs the ciphertext as
(23)CT=(C1∶=MΩs1,C2∶=gs1d1+s1ℐd2+s2d3+s2ℐd4).Decrypt(SK
ℐ
, CT). The decryption algorithm computes the message as
(24)M=C1en(SKℐ,C2).Security proof of Lewko IBE system used the dual system encryption technique [10]. Its semifunctional keys are like g(α+r1ℐ)θd1*-r1θd2*+r2ℐσd3*-r2σd4*+t5d5*+t6d6* and its semifunctional ciphertext is (MΩs1,gs1d1+wd2+s2d3+s2ℐd4+s5d5+s6d6) where t5,t6,s5,s6←Rℤp. Let GameFinal be the game, where all returned keys are semifunctional and the challenge ciphertext is (R,gs1d1+wd2+s2d3+s2ℐd4+s5d5+s6d6), where R←R𝔾T and w,s5,s6←Rℤp. In [26], Lewko showed that GameM,ℐ is indistinguishable from GameFinal′ under the subspace assumption. We continue her work and show that her IBE system has type 2 strong anonymity.We first review the subspace assumption introduced by Lewko in [26].Definition 19.
Given a group generation𝒢, one defines the following distribution:
(25)G∶=(p,𝔾,𝔾T,g,e)⟵R𝒢,(𝔹,𝔹*)⟵RDual(ℤpn),η,β,τ1,τ2,τ3,μ1,μ2,μ3⟵Rℤp,U1∶=gμ1b1+μ2bk+1+μ3b2k+1,U2∶=gμ1b2+μ2bk+2+μ3b2k+2,…,Uk∶=gμ1bk+μ2b2k+μ3b3k,V1∶=gτ1ηb1*+τ2βbk+1*,V2∶=gτ1ηb2*+τ2βbk+2*,…,Vk∶=gτ1ηbk*+τ2βb2k*,W1∶=gτ1ηb1*+τ2βbk+1*+τ3b2k+1*,W2∶=gτ1ηb2*+τ2βbk+2*+τ3b2k+2*,…,Wk∶=gτ1ηbk*+τ2βb2k*+τ3b3k*,D→∶=(gb1,gb2,…,gb2k,gb3k+1,…,gbn,gηb1*,…,gηbk*,gβbk+1*,…,gβb2k*,gb2k+1*,…,gbn*,U1,U2,…,Uk,μ3).
We define the advantage of an algorithm 𝒜 in breaking the subspace assumption to be
(26)|Pr[𝒜(D→,V1,…,Vk)=1]-Pr[𝒜(D→,W1,…,Wk)=1]|.
We say that the subspace assumption holds if no probabilistic polynomial time algorithm has a nonnegligible advantage in breaking the subspace assumption.Lemma 20.
LetGameFinal′ be the game, where all returned keys are semifunctional and the challenge ciphertext is (R,gs1d1+w2d2+s2d3+w4d4+s5d5+s6d6), where R←R𝔾T and w2,w4,s5,s6←Rℤp. If there exists a polynomial time algorithm 𝒜, where GameFinalAdv𝒜-GameFinal′Adv𝒜=ϵ, then we can construct a polynomial time algorithm ℬ with advantage ϵ to break the subspace assumption with n=6 and k=1.Proof.
ℬ is given D∶=(gb1,gb2,gb4,gb5,gb6,gηb1*,gβb2*,gb3*,gb4*,gβb5*,gβb6*,U1,μ3) along with T1. ℬ should decide whether T1 is distributed as gτ1ηb1*+τ2βb2* or as gτ1ηb1*+τ2βb2*+τ3b3*.
At firstℬ implicitly sets d1=b6*,d2=b5*,d3=b4*,d4=b3*,d5=b2*,d6=b1*. Then ℬ can produce gd1,…,gd4 for the public parameters. Next ℬ sets d1*=b6,d2*=b5,d3*=b4,d4*=b3,d5*=b2,d6*=b1. Note that ℬ only does not know gd4*.
ℬ chooses random values θ,σ,α∈ℤp for itself. It can compute e(g,g)αθd1·d1* as (en(gb6*,gb6))αθ. It gives 𝒜 the public key
(27)PK∶=𝔾,p,e(g,g)αθd1·d1*,gd1,…,gd4.
To respond a key query forℐ, ℬ chooses random values r1,r2′,t5′,t6′∈ℤp. It will set r2=μ3r2′. It forms the secret key as
(28)SKℐ∶=(U1)σr2′g(α+r1ℐ)θd1*-r1θd2*+μ3r2′ℐσd3*+t5′d5*+t6′d6*.
At the challenge phase,ℬ receives two messages M0,M1 and a challenge identity ℐ*. ℬ chooses a random bit b∈{0,1}, a random element R∈𝔾T, and random values w2,s1,s2∈ℤp and sets
(29)C1∶=R,C2∶=gs1d1+w2d2+s2d3+s2ℐ*d4T1.
IfT1=gτ1ηb1*+τ2βb2*, then the exponent vector of T1 is a random linear combination of d5 and d6, so it is in GameFinal. If the exponent of T1 additionally has τ3b3*=τ3d4, it is in GameFinal′. Therefore, ℬ can use the output of 𝒜 to break the subspace assumption.Theorem 21.
Lewko IBE system has type 2 strong anonymity.Proof.
From Lemma20 we know that the ciphertext of Lewko IBE system leaks no information about target identity, so it is anonymous.
Furthermore, note thatd1,…,d6 is a base of ℤp6×6, so gs1d1+w2d2+s2d3+w4d4+s5d5+s6d6 can seem a random element in ℤp6×6. In other words, GameFinal′=GameRandom. So Lewko IBE system has strong anonymity.
Obviously, the set of all possibleC2 is contained in span(gd1,gd2,gd3,gd4). Note that any nonzero vectors in span(gd5,gd6) are not included in span(gd1,gd2,gd3,gd4), so GameMR,ℐR≠GameRandom for Lewko IBE system which means that Lewko IBE system has type 2 anonymity.


## 4.4. Comparison

Like previous analysis for Gentry IBE system, Boyen-Waters IBE system, and Lewko IBE system, we can analyse other anonymous IBE systems. A brief comparison for some anonymous IBE systems is given in Table1. We would find that all listed IBE systems have strong anonymity, that is, superstandard anonymity. Though weak anonymity, that is, standard anonymity, is the current definition of anonymity, to the best of our knowledge, there is no IBE system having only weak anonymity. Hence we leave an open problem to construct an IBE system with only weak anonymity.Table 1
Comparison.
System
Security
Anonymity degree
Anonymity type
Security model
Boneh and Franklin [2]
IND-ID-CPAANON-ID-CPA
Strong
1
Random oracle
Boyen and Waters [8]
IND-sID-CPAANON-sID-CPA
Strong
2
Standard
Gentry [9]
ANON-IND-ID-CPA
Strong
1
Standard
Ducas [23]
IND-sID-CPAANON-sID-CPA
Strong
2
Standard
Lewko [26]
IND-ID-CPAANON-ID-CPA
Strong
2
Standard
Chen et al. [24]
ANON-IND-ID-CPA
Strong
2
Standard


## 5. Conclusion

In this paper, we discuss the anonymity of identity-based encryption systems. Anonymity can be divided into two degrees: weak anonymity and strong anonymity. If an IBE system has weak anonymity, the target identity of its ciphertext cannot be distinguished from a random identity. For strongly anonymous IBE systems, the whole ciphertext cannot be distinguished from a random tuple. We also discuss the type of anonymity and divide it into two types: type 1 means that a random tuple can be seen as a valid ciphertext for some identity, while type 2 cannot. We show that some current anonymous IBE systems, such as Gentry IBE system, Boyen-Waters IBE system, and Lewko IBE system, have strong but different type of anonymity. We hope that our analysis of anonymity would help to construct more anonymous IBE and related systems.



---

*Source: 217480-2013-12-31.xml*