# A Provably Secure Revocable ID-Based Authenticated Group Key Exchange Protocol with Identifying Malicious Participants

Authors: Tsu-Yang Wu; Tung-Tso Tsai; Yuh-Min Tseng
Journal: The Scientific World Journal
 (2014)

---

## Abstract

The existence of malicious participants is a major threat for authenticated group key exchange (AGKE) protocols. Typically, there are two detecting ways (passive and active) to resist malicious participants in AGKE protocols. In 2012, the revocable identity- (ID-) based public key system (R-IDPKS) was proposed to solve the revocation problem in the ID-based public key system (IDPKS). Afterwards, based on the R-IDPKS, Wu et al. proposed a revocable ID-based AGKE (RID-AGKE) protocol, which adopted a passive detecting way to resist malicious participants. However, it needs three rounds and cannot identify malicious participants. In this paper, we fuse a noninteractive confirmed computation technique to propose the first two-round RID-AGKE protocol with identifying malicious participants, which is an active detecting way. We demonstrate that our protocol is a provably secure AGKE protocol with forward secrecy and can identify malicious participants. When compared with the recently proposed ID/RID-AGKE protocols, our protocol possesses better performance and more robust security properties.


---

## Body

## 1. Introduction

In the past, group-oriented applications, such as collaboration works and teleconference, were popularly and widely used in the Internet. Authenticated group key exchange (AGKE) protocol [1] is a cryptographic primitive which provides secure group communications for users in cooperative and distributed applications. During executing the protocol, group participants not only cooperatively generate a common key which is used to encrypt the transmitted messages but also authenticate the participants’ identities.The existence of malicious participants is a major threat for AGKE protocols. The goal of malicious participants is to disturb the establishing of common keys. Hence, how to resist malicious participants in AGKE protocols becomes a critical research. Typically, there are two detecting ways to resist malicious participants. (I) Passive detection [2–4]: it involves an explicit key confirmation approach in AGKE protocols. The resulted protocols only detect the existence of malicious participants and an additional round is required. (II) Active detection [5, 6]: it adopts a noninteractive confirmed computation technique into AGKE protocols. The resulted protocols can identify the identities of malicious participants without additional round. However, the computational cost of active detection is time-consuming than the one of passive detection.Quite recently, the revocable identity- (ID-) based public key system (R-IDPKS) was proposed to solve the revocation problem of users in the ID-based public key system (IDPKS). The concept of IDPKS was introduced by Shamir [7] in 1984 and was practiced by Bonch and Franklin [8] in 2001. Indeed, they [8] had suggested a solution that the private key generator (PKG) renews these nonrevoked users’ private keys periodically to answer the revocation problem in the IDPKS. The approach can be used to revoke the compromised or misbehaving users. Nevertheless, the heavy workload arose from the PKG for renewing users’ private keys periodically.In 2008, Boldyreva et al. [9] proposed a revocable ID-based encryption (RIBE) scheme by using binary tree. Their scheme can reduce the PKG’s workload mentioned in the Boneh-Franklin solution [8]. However, this scheme is based on a weak security model called the relaxed selective-ID model [10]. In 2009, Libert and Vergnaud [11] relied on Boldyreva et al.’s RIBE to present a secure RIBE scheme under an adaptive-ID model. Recently, Seo and Emura [12] demonstrated Boldyreva et al.’s scheme [9] is vulnerable to decryption key exposure and then proposed a provably secure tree based RIBE scheme. Subsequently, Seo and Emura [13] presented a hierarchical RIBE scheme to solve the open problem mentioned in [11].In 2011, Tseng and Tsai [14] proposed a practical RIBE scheme over a public channel. The key construction of the Tseng-Tsai scheme is different from the previous schemes [9, 11–13]. In [14], each user’s private key consists of a fixed initial private key and an update key, where the update key is renewed along with the current period. For an honest (nonrevoked) user, the PKG periodically issues new update key and sends it to the user via a public channel. Upon receiving the new updating key, the user can renew her/his private key by herself/himself. To revoke a malicious user, the PKG only stops issuing the new update key in current period. Thus, the user cannot compute the newest private key. In other words, she/he cannot execute any cryptographic behaviors in later periods. Later on, several revocable ID-based cryptographic schemes based on the Tseng-Tsai R-IDPKS [14] were presented such as encryption [15], signature [16, 17], authenticated group key exchange (AGKE) [4], and signcryption [18].In 2012, Wu et al. [4] proposed the first provably secure revocable ID-based AGKE (RID-AGKE) protocol. Their protocol adopted a passive detecting way to resist malicious participants. However, it requires three rounds and cannot identify the identities of malicious participants. In this paper, we fuse the key construction of Tseng-Tsai R-IDPKS [14] and a noninteractive confirmed computation technique [6] to present a two-round RID-AGKE protocol with identifying malicious participants. In our protocol, each group participant can confirm whether the broadcast values are correctly computed by other participants. Based on the detecting approach, our protocol can easily identify the participants who maliciously broadcast the incorrect values to disturb the common key establishing. The framework and security notions for RID-AGKE protocols are defined to formalize possible threats and attacks. We demonstrate the security of our protocol in the random oracle model [19] and under two mathematical assumptions (the computational Diffie-Hellman and the decisional bilinear Diffie-Hellman). Finally, we make the comparisons between our protocol and the recently proposed ID/RID-AGKE protocols to show the advantages of the proposed protocol.The rest of this paper is organized as follows. We briefly review the concepts of bilinear pairings and related mathematical problems in Section2. The security model and notions of RID-AGKE are presented in Section 3. We propose a concrete RID-AGKE protocol in Section 4. Security analysis of the proposed RID-AGKE protocol is demonstrated in Section 5. We make the performance analysis and comparisons in Section 6. Conclusions are drawn in Section 7.


## 2. Preliminaries

In this section, we briefly review the properties of bilinear pairings and related mathematical problems. For the details, a reader can refer to [8, 20, 21] for full descriptions.


### 2.1. Bilinear Pairings

LetG
1 and G
2 be two groups of a large prime order q, where G
1 is an additive cyclic group and G
2 is a multiplicative cyclic group. A bilinear pairing e is a map defined by e
:
G
1
×
G
1
→
G
2 and satisfies the following three conditions.(1)
Bilinearity: for all P
,
Q
∈
G
1 and a
,
b
∈
Z
q, e
(
a
P
,
b
Q
)
=
e
(
P
,
Q
)
a
b.
(2)
Nondegeneracy: there exist P
,
Q
∈
G
1 such that e
(
P
,
Q
)
≠
1.
(3)
Computability: for all P
,
Q
∈
G
1, there exists an algorithm to compute e
(
P
,
Q
).


### 2.2. Mathematical Hard Problems and Assumptions

Here, we present two mathematical hard problems and define the corresponding assumptions as follows.(1)
Computational Diffie-Hellman (CDH) problem: given P
,
a
P
,
b
P
∈
G
1 for some a
,
b
∈
Z
q
*, the CDH problem is to compute a
b
P
∈
G
1.
(2)
Decisional bilinear Diffie-Hellman (DBDH) problem: given P
,
a
P
,
b
P
,
c
P
,
d
P
∈
G
1 for some a
,
b
,
c
,
d
∈
Z
q
*, the DBDH problem is to distinguish (
P
,
a
P
,
b
P
,
c
P
,
d
P
,
e
(
P
,
P
)
a
b
c from (
P
,
a
P
,
b
P
,
c
P
,
d
P
,
e
(
P
,
P
)
d
).Definition 1 (CDH assumption).
GivenP
,
a
P
,
b
P
∈
G
1 for some a
,
b
∈
R
Z
q
*, there does not exist a probabilistic polynomial-time algorithm A with a nonnegligible probability to compute a
b
P
∈
G
1. The advantage of A within running time t is defined as A
d
v
C
D
H
(
t
)
=
Pr
[
A
(
P
,
a
P
,
b
P
)
=
a
b
P
∣
P
,
a
P
,
b
P
∈
G
1
].Definition 2 (DBDH assumption).
GivenP
,
a
P
,
b
P
,
c
P
,
d
P
∈
G
1 for some a
,
b
,
c
,
d
∈
R
Z
q
*, there does not exist a probabilistic polynomial-time algorithm A with nonnegligible probability to distinguish (
P
,
a
P
,
b
P
,
c
P
,
d
P
,
e
(
P
,
P
)
a
b
c
) from (
P
,
a
P
,
b
P
,
c
P
,
d
P
,
e
(
P
,
P
)
d
). The advantage of A within running time t is defined as A
d
v
D
B
D
H
(
t
)
=
Pr
[
A
(
e
(
P
,
P
)
a
b
c
,
e
(
P
,
P
)
d
)
=
1
∣
P
,
a
P
,
b
P
,
c
P
,
d
P
∈
G
1
].


## 2.1. Bilinear Pairings

LetG
1 and G
2 be two groups of a large prime order q, where G
1 is an additive cyclic group and G
2 is a multiplicative cyclic group. A bilinear pairing e is a map defined by e
:
G
1
×
G
1
→
G
2 and satisfies the following three conditions.(1)
Bilinearity: for all P
,
Q
∈
G
1 and a
,
b
∈
Z
q, e
(
a
P
,
b
Q
)
=
e
(
P
,
Q
)
a
b.
(2)
Nondegeneracy: there exist P
,
Q
∈
G
1 such that e
(
P
,
Q
)
≠
1.
(3)
Computability: for all P
,
Q
∈
G
1, there exists an algorithm to compute e
(
P
,
Q
).


## 2.2. Mathematical Hard Problems and Assumptions

Here, we present two mathematical hard problems and define the corresponding assumptions as follows.(1)
Computational Diffie-Hellman (CDH) problem: given P
,
a
P
,
b
P
∈
G
1 for some a
,
b
∈
Z
q
*, the CDH problem is to compute a
b
P
∈
G
1.
(2)
Decisional bilinear Diffie-Hellman (DBDH) problem: given P
,
a
P
,
b
P
,
c
P
,
d
P
∈
G
1 for some a
,
b
,
c
,
d
∈
Z
q
*, the DBDH problem is to distinguish (
P
,
a
P
,
b
P
,
c
P
,
d
P
,
e
(
P
,
P
)
a
b
c from (
P
,
a
P
,
b
P
,
c
P
,
d
P
,
e
(
P
,
P
)
d
).Definition 1 (CDH assumption).
GivenP
,
a
P
,
b
P
∈
G
1 for some a
,
b
∈
R
Z
q
*, there does not exist a probabilistic polynomial-time algorithm A with a nonnegligible probability to compute a
b
P
∈
G
1. The advantage of A within running time t is defined as A
d
v
C
D
H
(
t
)
=
Pr
[
A
(
P
,
a
P
,
b
P
)
=
a
b
P
∣
P
,
a
P
,
b
P
∈
G
1
].Definition 2 (DBDH assumption).
GivenP
,
a
P
,
b
P
,
c
P
,
d
P
∈
G
1 for some a
,
b
,
c
,
d
∈
R
Z
q
*, there does not exist a probabilistic polynomial-time algorithm A with nonnegligible probability to distinguish (
P
,
a
P
,
b
P
,
c
P
,
d
P
,
e
(
P
,
P
)
a
b
c
) from (
P
,
a
P
,
b
P
,
c
P
,
d
P
,
e
(
P
,
P
)
d
). The advantage of A within running time t is defined as A
d
v
D
B
D
H
(
t
)
=
Pr
[
A
(
e
(
P
,
P
)
a
b
c
,
e
(
P
,
P
)
d
)
=
1
∣
P
,
a
P
,
b
P
,
c
P
,
d
P
∈
G
1
].


## 3. Model and Notions

In this section, we define the model and notions for RID-AGKE protocol. Note that some of the following definitions and notations are referred to in [4, 6, 22–24].Initialization. The initialization of RID-AGKE protocol has three algorithms.(1)Setup Algorithm. This algorithm is a probabilistic algorithm which takes as input a security parameter k and a total number z of periods. It returns a system private key s and public parametersparam. Note that the whole life time of the system is divide into distinct periods 1
,
2
,
…
,
z. Here,param is made public.(2)Initial Key Extract Algorithm. This algorithm is a deterministic algorithm which takes as input the system private key s and a participant’s identity I
D. It returns the participant’s initial private key D
I
D.(3)Key Update Algorithm. This algorithm is a deterministic algorithm which takes as input the system private key s, a participant’s identity I
D, and a period index j, where 1
≤
j
≤
z. It returns the participant’s update key T
I
D
j.Here, note that the participant’s private key for periodj is defined by D
I
D
j
=
D
I
D
+
T
I
D
j.Related Notions. For simplicity, there is a fixed set G
=
{
U
1
,
U
2
,
…
,
U
n
} with polynomial size of potential participants. Assume that each participant U
i has a unique identity I
D
i
∈
{
0
,
1
}
*. Any subset of G may run a RID-AGKE protocol many times (possibly concurrently) in some period index j to establish a group session key, where 1
≤
j
≤
z and z is a total number of periods. Note that the set of participants’ identities, I
D
=
{
I
D
1
,
I
D
2
,
…
,
I
D
n
} is known by all participants (including adversary).An instancet of participant U in period j is denoted by Π
U
j
(
t
), where t is a positive integer. Each instance Π
U
j
(
t
) has associated with seven variables as follows.(i)
s
t
a
t
e
U
j
(
t
): it presents the current state of instance Π
U
j
(
t
).
(ii)
a
c
c
U
j
(
t
) and t
e
r
m
U
j
(
t
): they take Boolean values to demonstrate whether Π
U
j
(
t
)
has accepted or terminated. Informally, we say that an instancehas accepted meaning that it does not detect any incorrect behavior. An instance is called terminating if it has sent and received messages. Note that a terminated instance may also possibly accept.
(iii)
u
s
e
d
U
j
(
t
): it indicates whether Π
U
j
(
t
) is used in a RID-AGKE protocol.
(iv)
p
i
d
U
j
(
t
): the partner ID of instance Π
U
j
(
t
) is a set which contains the identities of participants in the group with whom Π
U
j
(
t
) wants to establish a group session key (including U itself).
(v)
s
i
d
U
j
(
t
): the session ID of instance Π
U
j
(
t
) is a concatenation of all messages sent and received by the instance in a given execution of RID-AGKE protocol.
(vi)
s
k
U
j
(
t
): a group session key which is accepted by instance Π
U
j
(
t
).In the following definitions, we will only focus on the three variablesp
i
d
U
j
(
t
), s
i
d
U
j
(
t
), and s
k
U
j
(
t
). The remaining variables will be left implicit. We say that two instances Π
U
j
(
t
) and Π
U
′
j
(
v
) arepartnered if (1) they have accepted the same group session key; (2) s
i
d
U
j
(
t
)
=
s
i
d
U
′
j
(
v
); and (3) p
i
d
U
j
(
t
)
=
p
i
d
U
′
j
(
v
).Adversarial Model. An adversary A can be viewed as a probabilistic polynomial-time algorithm. Here, we assume that A can potentially control all communications in a RID-AGKE protocol. The interaction between A and instances of participants in the protocol is modeled by the following oracles.(i)
Execute
(
V
,
j
): when A makesExecute query on (
V
,
j
), it executes the RID-AGKE protocol between the unused instances of participants in V for period index j and then returns a transcript of the execution, where V is a subset of G. Here,Execute query is used to model passive attacks.
(ii)
Inextract
(
I
D
U
): when A makesInitial key extract query on identity I
D
U, it generates an initial private key D
I
D
U corresponding to I
D
U and returns it to A, where I
D
U
∉
I
D.
(iii)
Kupdate
(
I
D
U
,
j
): when A makesKey update query on (
I
D
U
,
j
), it generates an update key T
I
D
U
,
j corresponding to (
I
D
U
,
j
) and returns it to A, where I
D
U
∉
I
D and j is a period index.
(iv)
Send
(
U
,
j
,
t
,
M
): when A makesSend query on (
U
,
j
,
t
,
M
), it sends message M to instance Π
U
j
(
t
) and then returns the reply generated by this instance according to procedures of RID-AGKE protocol.
(v)
Reveal
(
U
,
j
,
t
): when A makesReveal query on (
U
,
j
,
t
), it returns a group session key s
k
U
j
(
t
) for a terminated instance Π
U
j
(
t
). Here,Reveal query is used to model known session key attacks.
(vi)
Corrupt
(
I
D
U
,
j
): when A makesCorrupt query on (
I
D
U
,
j
), it returns a private key D
I
D
U
,
j of I
D
U in period j. Note thatCorrupt query models the corruption of this participant at a time in which it is not currently executing the protocol. We say that a participant U is honest if and only if noCorrupt query has been made by A.
(vii)
Test
(
U
,
j
,
t
,
): at any time, the adversary A makesTest query only once to this oracle during A’s execution. In this moment, a random coin b
∈
{
0,1
} is selected. If b
=
1, a group session key s
k
U
j
(
t
) is retuned. Otherwise, a random value is retuned. Here,Test query is used to model the semantic security of group session key.According to the above adversarial model, we define two types of adversaries. Apassive adversary is allowed to makeExecute,Reveal,Corrupt, andTest queries. Anactive adversary is allowed to make the above all queries. In order to get more precise analysis, we still useExecute query though it can be substituted by makingSend query repeatedly.Remark 3.
According to the adversarial model above, the adversaryA can compute the participant U’s private key D
I
D
U
,
j
=
D
I
D
U
+
T
I
D
U
,
j for period index j while A makes bothInitial key extract query on I
D
U andKey update query on (
I
D
U
,
j
) simultaneously. Hence, we disallow A to make both queries in the same time.Correctness.
A RID-AGKE protocol is calledcorrect if the following three conditions hold.(1)
All participants are honest and all messages are delivered honestly.
(2)
a
c
c
U
j
(
t
)
=
a
c
c
U
′
j
(
v
)
= “True” and s
k
U
j
(
t
)
=
s
k
U
′
j
(
v
).
(3)
s
i
d
U
j
(
t
)
=
s
i
d
U
′
j
(
v
)and p
i
d
U
j
(
t
)
=
p
i
d
U
′
j
(
v
) for all participants U
,
U
’
∈
V
⊆
G with instances Π
U
j
(
t
) and Π
U
′
j
(
v
).Freshness. We say that an instance Π
U
j
(
t
)is calledfresh (or called holding afresh group session key s
k
U
j
(
t
)) if the following three conditions hold.(1)
Π
U
j
(
t
) has accepted a group session key s
k
U
j
(
t
).
(2)
NeitherΠ
U
j
(
t
) nor its partners have been madeReveal query.
(3)
NoCorrupt query has been made on I
D
V
∈
p
i
d
U
j
(
t
) beforeSend query to Π
U
j
(
t
) orSend query to Π
U
’
j
(
v
), where I
D
U
’
∈
p
i
d
U
j
(
t
).Here, we assume all instances arefresh. Note that the notion offreshness is defined appropriately for the purpose of forward secrecy.Secure RID-AGKE. A secure RID-AGKE protocol contains the following four parts.(1)Freshness.(2)Security of RID-AGKE Protocol. The security of RID-AGKE protocol is defined in the following game played between an active adversary A and a set of instances:(a)
initialization: the system private key, public parameters, and participants’ private keys are generated in this phase;
(b)
query: A may make different types of queries to oracles and gets back the answers corresponding to the RID-AGKE protocol;
(c)
guess: finally, the adversary A outputs its guess for the coin b inTest query and terminates.In this game, the goal ofA is to distinguish a group session key from a random value. LetSucc be the event that A correctly guesses the coin b inTest query. The advantage of A in attacking a RID-AGKE protocol Ψ is defined by A
d
v
A
,
Ψ
(
k
)
=
|
2
·
Pr
[
S
u
c
c
]
-
1
|. We say that the protocol Ψ is secure, if the advantage A
d
v
A
,
Ψ
(
k
) is negligible.(3)Forward Secrecy. We say that a RID-AGKE protocol Ψ providesforward secrecy. It means that though an adversary A obtains participants’ private keys in Ψ, the previous establishing group session keys is preserved. The advantage of A in attacking the protocol Ψ within running time t is defined by A
d
v
Ψ
R
I
D
A
G
K
E
-
f
s(t
,
q
e
x
,
q
s), where q
e
x and q
s are the maximum numbers of makingExecute andSend queries, respectively.(4)Authentication. We say that a RID-AGKE protocol Ψ providesimplicit key authentication if all participants in Ψ are guaranteed that nobody other than their partners can learn the session key. In other words, any adversary should not learn the key. Note that this security property does not guarantee that the partners have computed the key.Malicious Participant. A participant U
m is calledmalicious in a RID-AGKE protocol Ψ if he is a legal participant but is fully controlled by adversary. The goal of malicious participant is to disturb the group key establishing in Ψ.


## 4. Concrete Protocol

In this section, we propose a concrete RID-AGKE protocol with identifying malicious participants. Our protocol fuses the Tseng-Tsai R-IDPKS [14] and a noninteractive confirmed computation technique [6]. In the initialization phase, given a security parameter k and a total number z of periods, a private key generator (PKG) executesSetup algorithm to generate the system private key s and the public parameters p
a
r
a
m
=
{
G
1
,
G
2
,
e
,
q
,
P
,
P
p
u
b
,
H
1
,
H
2
,
H
3
,
H
4
} defined in Notations section at the end of the paper.When a participantU with identity I
D
U
∈
{
0
,
1
}
* wants to obtain her/his initial private key D
I
D
U, the PKG runsInitial key extract algorithmto compute D
I
D
U
=
s
·
H
1
(
I
D
U
)
=
s
·
Q
I
D
U and returns it to U via a secure channel. For a nonrevoked participant U with identity I
D
U in time period j, the PKG runsKey update algorithm to compute her/his update key T
I
D
U
,
j
=
s
·
H
2
(
I
D
U
,
j
)
=
s
·
R
I
D
U
,
j and returns it to U via a public channel, where 1
≤
j
≤
z. Hence, any nonrevoked participant U can update her/his private key D
I
D
U
,
j
=
D
I
D
U
+
T
I
D
U
,
j by itself in period j.LetG
=
{
U
1
,
U
2
,
…
,
U
n
} be a set of participants who want to establish a group session key S
K
j in period j. We assume that each U
i has a unique identity I
D
i
∈
{
0
,
1
}
* as public key and U
i’s private key is D
I
D
i
,
j
=
D
I
D
i
+
T
I
D
i
,
j for period j. Note that the indices are subject to modulo n; that is, U
n
+
1 and U
0 denote U
1 and U
n, respectively. Finally, m
∈
{
0
,
1
}
* is a preknown common message by all participants. The details of proposed RID-AGKE protocol are described as follows.Round 1. Each participant U
i randomly selects a secret value a
i
∈
Z
q
* and computes P
i
=
a
i
·
P, h
i
=
H
3
(
I
D
i
,
P
I
D
j
,
j
,
m
,
P
i
), and V
i
=
D
I
D
i
,
j
+
a
i
·
h
i
·
P
p
u
b, where P
I
D
j denotes the concatenation of all participants’ identities in period j; that is, P
I
D
j
=
I
D
1
∥
I
D
2
∥
⋯
∥
I
D
n. Finally, each U
i broadcasts (
I
D
i
,
j
,
P
i
,
V
i
) to other participants.Round 2. Upon receiving (
I
D
i
-
1
,
j
,
P
i
-
1
,
V
i
-
1
) and (
I
D
i
+
1
,
j
,
P
i
+
1
,
V
i
+
1
), each U
i first verifies them by checking
(1)
e
(
P
,
∑
k
∈
{
-
1,1
}
V
i
+
k
)
=
?
e
(
P
p
u
b
,
∑
k
∈
{
-
1,1
}
H
1
(
I
D
i
+
k
)
+
H
2
(
I
D
i
+
k
,
j
)
V
V
V
V
k
V
V
V
I
+
h
i
+
k
·
P
i
+
k
∑
k
∈
{
-
1,1
}
H
1
(
I
D
i
+
k
)
+
H
2
(
I
D
i
+
k
,
j
)
)
,
where h
i
+
k
=
H
3
(
I
D
i
+
k
,
P
I
D
j
,
j
,
m
,
P
i
+
k
). If the verification is true, each U
i uses her/his secret value a
i to compute D
i
=
e
(
a
i
·
(
P
i
+
1
-
P
i
-
1
)
,
P
p
u
b
). Then, U
i randomly selects a value r
i
∈
Z
q
* and computes a tuple (
I
D
i
,
j
,
D
i
,
α
i
,
β
i
,
γ
i
), where α
i
=
r
i
·
P, β
i
=
r
i
·
(
P
i
+
1
-
P
i
-
1
), γ
i
=
r
i
·
P
i
+
w
i
·
a
i
·
P
p
u
b, w
i
=
H
4
(
I
D
i
∥
P
I
D
j
∥
j
∥
D
i
∥
S
j
,
P
i
+
1
-
P
i
-
1
,
α
i
,
β
i
), and S
j
=
P
1
∥
P
2
∥
⋯
∥
P
n. Finally, U
i sends this tuple to all other participants.Group Key Computation. Upon receiving all (
I
D
k
,
j
,
D
k
,
α
k
,
β
k
,
γ
k
) for k
=
1
,
2
,
…
,
n except i, each U
i verifies them by checking
(2)
e
(
P
,
∑
k
=
1
,
k
≠
i
n
γ
k
)
=
∏
k
=
1
,
k
≠
i
n
e
(
P
k
,
α
k
+
w
k
·
P
p
u
b
)
,
e
(
P
k
+
1
-
P
k
-
1
,
γ
k
)
=
?
e
(
β
k
,
P
k
)
·
D
k
w
k
.
If the two verifications hold, U
i can confirm that each D
k is computed by U
k using her/his secret a
k honestly for k
=
1
,
2
,
…
,
n except i. Finally, in period j, each participant U
i can compute the group session key S
K
j
=
e
(
a
i
·
P
i
-
1
,
P
p
u
b
)
n
·
D
i
n
-
1
·
D
i
+
1
n
-
2
⋯
D
i
-
2.Identifying Malicious Participant. When a malicious participant U
m tries to send a wrong tuple (
I
D
m
,
D
m
,
j
,
α
m
,
β
m
,
γ
m
) to disrupt the establishment of group session key, he will be identified as a malicious participant by using the following two verifying equations: e
(
P
,
γ
k
)
=
?
e
(
P
k
,
α
k
+
w
k
·
P
p
u
b
) and e
(
P
k
+
1
-
P
k
-
1
,
γ
k
)
=
?
e
(
β
k
,
P
k
)
·
D
k
w
k. Later on, U
m will be deleted from the participant set G and other honest participants may rerun the protocol.


## 5. Security Analysis

In this section, we prove the security of the proposed RID-AGKE protocol in the random oracle model [19] and under the CDH and DBDH assumptions.ID and Forgery AttacksTheorem 4.
The proposed RID-AGKE protocol is secure against ID and forgery attacks.Proof.
Note that we adopt a revocable ID-based signature (RIDS) scheme [16] in Round 1 and a pairing-based signature scheme [6] in Round 2, respectively. The two signature schemes had been proven secure against ID and forgery attacks for single signature and multiple signatures with batch verification. Therefore, the proposed RID-AGKE protocol Ψ is secure against ID and forgery attacks.
Secure RID-AGKE Providing Forward Secrecy. Now, we demonstrate that the proposed RID-AGKE protocol Ψ is a secure RID-AGKE providing forward secrecy. Note that we use a similar technique in [3, 4, 6] to prove Theorem 5.Theorem 5.
Assume that four hash functionsH
1, H
2, H
3, and H
4 are random oracles. Then, the proposed RID-AGKE protocol Ψ is a secure RID-AGKE providing forward secrecy under the decisional bilinear Diffie-Hellman (DBDH) and the computational Diffie-Hellman (CDH) assumptions. Concretely,
(3)
A
d
v
Ψ
R
I
D
A
G
K
E
-
f
s
(
t
,
q
e
x
,
q
s
)
≤
2
n
q
e
x
·
A
d
v
D
B
D
H
(
t
)
+
A
d
v
Ψ
f
o
r
g
e
(
t
)
,
where q
e
x and q
s are total numbers of making Execute and Send queries, respectively. Note that A
d
v
Ψ
f
o
r
g
e
(
t
) denotes the advantage of any forgers successfully attacking the protocol Ψ.Proof.
Assume thatA is an active adversary in attacking the proposed RID-AGKE protocol Ψ with a nonnegligible advantage. Now, we consider the two possible cases. The first case is that A with the advantage can impersonate a participant (i.e., forging authentication transcripts). Another case is that A with the advantage can break the protocol Ψ without modifying any transcripts.
Case  1. We assume that the adversary A with an adaptive impersonation ability can break the RID-AGKE protocol Ψ. Using A, we would like to construct a forger F which can return valid signature tuples (
I
D
,
j
,
a
P
,
V
) and (
I
D
,
j
,
D
,
α
,
β
,
γ
) with respect to the proposed protocol Ψ as follows. The forger F first generates all needed system parameters and keys. Then, F simulates the oracle queries made by A. This simulation is called perfect indistinguishable from A’s oracle queries except that A makesCorrupt query on (
I
D
,
j
), where j is a period index. If it occurs, F fails and stops. Otherwise, when A generates two signature tuples (
I
D
,
j
,
a
P
,
V
) and (
I
D
,
j
,
D
,
α
,
β
,
γ
), F returns the tuples (
I
D
,
j
,
a
P
,
V
) and (
I
D
,
j
,
D
,
α
,
β
,
γ
). LetForge be the event that the adversary A successfully generates two valid signature tuples. Then, the probability that F successfully returns two valid signature tuples is bounded by Pr
A
[
F
o
r
g
e
]
≤
A
d
v
F
,
Ψ
f
o
r
g
e
(
t
)
≤
A
d
v
Ψ
f
o
r
g
e
(
t
).
Case  2. We assume that the adversary A can break the proposed RID-AGKE protocol without modifying any transcripts. We first focus on the case that A makesExecute query once on (
I
D
1
,
I
D
2
,
…
,
I
D
n
,
j
) and then extends this to the case that A makes multipleExecute queries, where the number of participants n and period j are selected by A. The real execution of Ψ is given by(4)
p
a
r
a
m
=
{
(
G
1
,
G
2
,
e
)
⟵
PKG
;
P
⟵
G
1
;
s
⟵
Z
q
*
;
P
p
u
b
=
s
·
P
;
Q
I
D
1
,
…
,
Q
I
D
n
,
R
I
D
1
,
j
,
…
,
R
I
D
n
,
j
⟵
G
1
;
D
I
D
1
,
j
=
(
Q
I
D
1
+
R
I
D
1
,
j
)
·
s
,
…
,
D
I
D
n
,
j
=
(
Q
I
D
n
+
R
I
D
n
,
j
)
·
s
:
(
G
1
,
G
2
,
e
,
P
,
P
p
u
b
,
P
I
D
)
}
,
R
e
a
l
=
{
a
1
,
…
,
a
n
,
h
1
,
…
,
h
n
,
r
1
,
…
,
r
n
,
w
1
,
…
,
w
n
⟵
Z
q
*
;
P
1
=
a
1
P
,
…
,
P
n
=
a
n
P
;
V
1
=
D
I
D
1
,
j
+
a
1
h
1
P
p
u
b
,
…
,
V
n
=
D
I
D
n
,
j
+
a
n
h
n
P
p
u
b
;
D
1
=
e
(
P
2
-
P
n
,
P
p
u
b
)
a
1
,
…
,
D
n
=
e
(
P
1
-
P
n
-
1
,
P
p
u
b
)
a
n
;
α
1
=
r
1
P
,
…
,
α
n
=
r
n
P
;
β
1
=
r
1
(
P
2
-
P
n
)
,
…
,
β
n
=
r
n
(
P
1
-
P
n
-
1
)
;
γ
1
=
r
1
P
1
+
w
1
a
1
P
p
u
b
,
…
,
γ
n
=
r
n
P
n
+
w
n
a
n
P
p
u
b
;
T
=
(
P
1
,
…
,
P
n
,
V
1
,
…
,
V
n
,
D
1
,
…
,
D
n
,
α
1
,
…
,
α
n
,
β
1
,
…
,
β
n
,
γ
1
,
…
,
γ
n
)
;
S
K
j
=
e
(
a
1
P
n
,
P
p
u
b
)
n
·
D
1
n
-
1
·
D
2
n
-
2
⋯
D
n
-
1
:
(
j
,
T
,
S
K
j
)
}
,where T denotes the transcript and S
K
j is the group session key for period j.
InReal, each D
i
=
e
(
P
i
+
1
-
P
i
-
1
,
P
p
u
b
)
a
i
=
e
(
a
i
P
i
+
1
,
P
p
u
b
)
/
e
(
a
i
P
i
-
1
,
P
p
u
b
)
=
e
(
a
i
a
i
+
1
P
,
P
p
u
b
)
/
e
(
a
i
-
1
a
i
P
,
P
p
u
b
). by the bilinear pairing operations. We can use a random value d
1,2
∈
Z
q
* to substitute a
1
·
a
2. Thus, a new distribution F
a
k
e
1 is obtained as follows:(5)
F
a
k
e
1
=
{
d
1,2
,
a
1
,
…
,
a
n
,
h
1
,
…
,
h
n
,
r
1
,
…
,
r
n
,
w
1
,
…
,
w
n
⟵
Z
q
*
;
P
1
=
a
1
P
,
…
,
P
n
=
a
n
P
;
V
1
=
D
I
D
1
,
j
+
a
1
h
1
P
p
u
b
,
…
,
V
n
=
D
I
D
n
,
j
+
a
n
h
n
P
p
u
b
;
D
1
=
e
(
d
1,2
P
,
P
p
u
b
)
e
(
a
n
a
1
P
,
P
p
u
b
)
,
D
2
=
e
(
a
2
a
3
P
,
P
p
u
b
)
e
(
d
1,2
P
,
P
p
u
b
)
,
…
,
D
n
=
e
(
a
n
a
1
P
,
P
p
u
b
)
e
(
a
n
-
1
a
n
P
,
P
p
u
b
)
;
α
1
=
r
1
P
,
…
,
α
n
=
r
n
P
;
β
1
=
r
1
(
P
2
-
P
n
)
,
…
,
β
n
=
r
n
(
P
1
-
P
n
-
1
)
;
γ
1
=
r
1
P
1
+
w
1
a
1
P
p
u
b
,
…
,
γ
n
=
r
n
P
n
+
w
n
a
n
P
p
u
b
;
T
=
(
P
1
,
…
,
P
n
,
V
1
,
…
,
V
n
,
D
1
,
…
,
D
n
,
α
1
,
…
,
α
n
,
β
1
,
…
,
β
n
,
γ
1
,
…
,
γ
n
)
;
S
K
j
=
e
(
a
1
P
n
,
P
p
u
b
)
n
·
D
1
n
-
1
·
D
2
n
-
2
⋯
D
n
-
1
:
(
j
,
T
,
S
K
j
)
}
.
Note thatA can obtain all private keys D
I
D
i
,
j and hash values h
i by makingCorrupt andHash queries. It means that A can compute all a
i
·
P
p
u
b
=
h
i
-
1
·
(
V
i
-
D
I
D
i
,
j
) for i
=
1
,
2
,
…
,
n. Since the discrete logarithm assumption in G
1 is intractable, A cannot obtain some information about a
i from a
i
·
P
p
u
b for i
=
1
,
2
,
…
,
n.
In the following claim, we want to show that to distinguish two distributionsReal from F
a
k
e
1 can be reduced to solve the decisional bilinear Diffie-Hellman (DBDH) problem. Let ε
(
t
)
=
A
d
v
D
B
D
H
(
t
).
Claim. For any algorithm A with running time t, we have
(6)
|
Pr
[
(
j
,
T
,
S
K
j
)
⟵
R
e
a
l
|
A
(
j
,
T
,
S
K
j
)
=
1
]
-
Pr
[
(
j
,
T
,
S
K
j
)
⟵
F
a
k
e
1
|
A
(
j
,
T
,
S
K
j
)
=
1
]
|
≤
ε
(
t
)
.
Proof. As mentioned above, each D
i
=
e
(
a
i
a
i
+
1
P
,
P
p
u
b
)
/
e
(
a
i
-
1
a
i
P
,
P
p
u
b
)
=
e
(
P
,
P
p
u
b
)
a
i
a
i
+
1
e
(
P
,
P
p
u
b
)
a
i
-
1
a
i. Here, we use Γ
i
,
i
+
1 to substitute e
(
P
,
P
p
u
b
)
a
i
a
i
+
1 and then each D
i can be written into Γ
i
,
i
+
1
/
Γ
i
-
1
,
i for i
=
1
,
2
,
…
,
n. Hence, the group session key S
K
j also can be written into (
Γ
n
,
1
)
n
·
D
1
n
-
1
·
D
2
n
-
2
⋯
D
n
-
1, where (
Γ
n
,
1
)
n
=
e
(
P
,
P
p
u
b
)
n
a
n
a
1
=
e
(
a
1
P
n
,
P
p
u
b
)
n.
To solve the DBDH problem, we use a technique to dispose the related parameter. Considering the following algorithmD which inputs P
a
=
a
P,P
b
=
b
P, and P
c
=
c
P
∈
G
1 for some a
,
b
,
c
∈
R
Z
q
*. D first generates (
j
,
T
,
S
K
j
) according to the distribution D
i
s
t
1. Then, D runs A
(
j
,
T
,
S
K
j
) and outputs whatever A outputs. The distribution D
i
s
t
1 is defined as follows:(7)
D
i
s
t
1
=
{
a
1
,
…
,
a
n
,
h
1
,
…
,
h
n
,
u
1
,
…
,
u
n
-
2
,
r
1
,
…
,
r
n
,
w
1
,
…
,
w
n
⟵
Z
q
*
;
P
1
=
a
1
P
,
…
,
P
n
=
a
n
P
;
V
1
=
D
I
D
1
,
j
+
a
1
h
1
P
p
u
b
,
…
,
V
n
=
D
I
D
n
,
j
+
a
n
h
n
P
p
u
b
;
Γ
1,2
=
g
s
a
b
∈
G
2
,
Γ
2,3
=
e
(
P
b
,
P
p
u
b
)
u
1
,
Γ
i
,
i
+
1
=
e
(
P
,
P
p
u
b
)
u
i
-
2
u
i
-
1
for
i
=
3
to
n
-
1
Γ
n
,
1
=
e
(
P
a
,
P
p
u
b
)
u
n
-
2
;
D
1
=
Γ
1,2
Γ
n
,
1
,
…
,
D
n
=
Γ
n
,
1
Γ
n
-
1
,
n
;
α
1
=
r
1
P
,
…
,
α
n
=
r
n
P
;
β
1
=
r
1
(
P
2
-
P
n
)
,
…
,
β
n
=
r
n
(
P
1
-
P
n
-
1
)
;
γ
1
=
r
1
P
1
+
w
1
a
1
P
p
u
b
,
…
,
γ
n
=
r
n
P
n
+
w
n
a
n
P
p
u
b
;
T
=
(
P
1
,
…
,
P
n
,
V
1
,
…
,
V
n
,
D
1
,
…
,
D
n
,
α
1
,
…
,
α
n
,
β
1
,
…
,
β
n
,
γ
1
,
…
,
γ
n
)
;
S
K
j
=
(
Γ
n
,
1
)
n
·
D
1
n
-
1
·
D
2
n
-
2
⋯
D
n
-
1
:
(
j
,
T
,
S
K
j
)
}
.Note that this distribution depends on P
a, P
b, and P
c.
By the above distributionD
i
s
t
1, let Γ
1,2
=
e
(
P
,
P
p
u
b
)
a
b
=
e
(
P
,
P
)
s
a
b. Then, we can obtain another distribution called D
i
s
t
D
B
D
H
1. Obviously, D
i
s
t
D
B
D
H
1 is identical toReal because
(8)
S
K
j
=
(
Γ
n
,
1
)
(
Γ
1,2
)
(
Γ
2,3
)
⋯
(
Γ
n
-
2
,
n
-
1
)
(
Γ
n
-
1
,
n
)
=
e
(
P
a
,
P
p
u
b
)
u
n
-
2
·
e
(
P
,
P
)
s
a
b
·
e
(
P
b
,
P
p
u
b
)
u
1
⋯
e
(
P
,
P
p
u
b
)
u
n
-
4
u
n
-
3
·
e
(
P
,
P
p
u
b
)
u
n
-
3
u
n
-
2
=
e
(
P
,
P
)
s
u
n
-
2
a
+
s
a
b
+
s
b
u
1
+
⋯
+
s
u
n
-
4
u
n
-
3
+
s
u
n
-
3
u
n
-
2
.
Similarly, letΓ
1,2
=
e
(
P
c
,
P
p
u
b
)
=
e
(
P
,
P
)
s
c for some c
≠
a
b
∈
Z
q
*. Then, we can obtain another distribution called D
i
s
t
R
a
n
d
o
m
1. Obviously, D
i
s
t
R
a
n
d
o
m
1 is identical to F
a
k
e
1 because
(9)
S
K
j
=
(
Γ
n
,
1
)
(
Γ
1,2
)
(
Γ
2,3
)
⋯
(
Γ
n
-
2
,
n
-
1
)
(
Γ
n
-
1
,
n
)
=
e
(
P
a
,
P
p
u
b
)
u
n
-
2
·
e
(
P
,
P
)
s
c
·
e
(
P
b
,
P
p
u
b
)
u
1
⋯
e
(
P
,
P
p
u
b
)
u
n
-
4
u
n
-
3
·
e
(
P
,
P
p
u
b
)
u
n
-
3
u
n
-
2
=
e
(
P
,
P
)
s
u
n
-
2
a
+
s
c
+
s
b
u
1
+
⋯
+
s
u
n
-
4
u
n
-
3
+
s
u
n
-
3
u
n
-
2
.
Therefore, we have
(10)
|
Pr
[
(
j
,
T
,
S
K
j
)
⟵
R
e
a
l
|
A
(
j
,
T
,
S
K
j
)
=
1
]
-
Pr
[
(
j
,
T
,
S
K
j
)
⟵
F
a
k
e
1
|
A
(
j
,
T
,
S
K
j
)
=
1
]
|
≤
ε
(
t
)
.
This completes the proof of claim.
Using the same process inF
a
k
e
1, we can define other distributions F
a
k
e
i for i
=
2
,
3
,
…
,
n. By a similar approach in claim, we can obtain the following n-1 equations in (11) for any adversary A with running time t
(11)
|
Pr
[
(
j
,
T
,
S
K
j
)
⟵
F
a
k
e
1
|
A
(
j
,
T
,
S
K
j
)
=
1
]
-
Pr
[
(
j
,
T
,
S
K
j
)
⟵
F
a
k
e
2
|
A
(
j
,
T
,
S
K
j
)
=
1
]
|
≤
ε
(
t
)
,
⋮
|
Pr
[
(
j
,
T
,
S
K
j
)
⟵
F
a
k
e
n
-
1
|
A
(
j
,
T
,
S
K
j
)
=
1
]
-
Pr
[
(
j
,
T
,
S
K
j
)
⟵
F
a
k
e
n
|
A
(
j
,
T
,
S
K
j
)
=
1
]
|
≤
ε
(
t
)
.
This implies
(12)
|
Pr
[
(
j
,
T
,
S
K
j
)
⟵
R
e
a
l
|
A
(
j
,
T
,
S
K
j
)
=
1
]
-
Pr
[
(
j
,
T
,
S
K
j
)
⟵
F
a
k
e
n
|
A
(
j
,
T
,
S
K
j
)
=
1
]
|
≤
n
·
ε
(
t
)
.
InF
a
k
e
n, the values d
1,2
,
d
2,3
,
…
,
d
n
-
1
,
n
,
d
n
,
1 are constrained by T according to the following n equations:
(13)
log
⁡
g
⁡
D
1
=
s
·
(
d
1,2
-
d
n
,
1
)
,
log
⁡
g
⁡
D
2
=
s
·
(
d
2,3
-
d
1,2
)
,
…
,
log
⁡
g
⁡
D
n
=
s
·
(
d
n
,
1
-
d
n
-
1
,
n
)
,
where g
=
e
(
P
,
P
). Since S
K
j can be expressed as e
(
P
,
P
)
s
d
1,2
+
s
d
2,3
+
⋯
+
s
d
n
,
1, we can obtain log
⁡
g
S
K
j
=
s
d
1,2
+
s
d
2,3
+
⋯
+
s
d
n
,
1. Because s
d
1,2
+
s
d
2,3
+
⋯
+
s
d
n
,
1 is linear and independent from the set {
log
⁡
g
D
i
=
s
·
(
d
i
,
i
+
1
-
d
i
-
1
,
i
)
∣
i
=
1
,
2
,
…
,
n
}, it implies that S
K
j is independent for the transcript T. In other words, for any adversary A
(14)
Pr
[
(
j
,
T
,
S
K
j
,
0
)
⟵
F
a
k
e
n
,
S
K
j
,
1
⟵
G
2
∣
A
(
j
,
T
,
S
K
j
,
b
)
=
1
,
b
⟵
{
0
,
1
}
A
(
j
,
T
,
S
K
j
,
b
)
]
=
1
2
.
Therefore, the advantage of A on the event ¬
F
o
r
g
e is bounded by 2
n
·
A
d
v
D
B
D
H
(
t
). Combining the two cases, the advantage of A is bounded by
(15)
A
d
v
Ψ
R
I
D
A
G
K
E
-
f
s
(
t
,
1
,
q
s
)
≤
2
n
·
A
d
v
D
B
D
H
(
t
)
+
A
d
v
Ψ
f
o
r
g
e
(
t
)
.
Finally, a standard hybrid argument immediately demonstrates that
(16)
A
d
v
Ψ
R
I
D
A
G
K
E
-
f
s
(
t
,
q
e
x
,
q
s
)
≤
2
n
q
e
x
·
A
d
v
D
B
D
H
(
t
)
+
A
d
v
Ψ
f
o
r
g
e
(
t
)
for
q
e
x
>
1
.Under the decisional bilinear Diffie-Hellman (DBDH) assumption, the advantageA
d
v
D
B
D
H
(
t
) is negligible. By Theorem 4, the advantage A
d
v
Ψ
f
o
r
g
e
(
t
) is also negligible. Hence, we can obtain that the advantage A
d
v
Ψ
R
I
D
A
G
K
E
-
f
s
(
t
,
q
e
x
,
q
s
) is negligible according to the result in Theorem 5. It implies that the proposed RID-AGKE protocol Ψ is a secure RID-AGKE providing forward secrecy.Identifying Malicious ParticipantTheorem 6.
The proposed RID-AGKE protocol can identify malicious participants.Proof.
Note that in Round 2 a noninteractive confirmed computation technique is involved in adopted pairing-based signature scheme. The security of confirmed computation had been proven in [6]. Concretely, each participant U
i can confirm the broadcasted value D
k is computed by U
k using her/his secret a
k after passing two verifying equations for k
=
1
,
2
,
…
,
n except i. Hence, if there is a participant U
m who broadcasts a wrong D
m to disturb the group session key establishing, he will be identified as a malicious participant. In other words, the proposed RID-AGKE protocol can identify malicious participants by using the confirmed computation technique.


## 6. Performance Analysis and Comparisons

For convenience to evaluate the computational cost, we focus on the time-consuming pairing-based operations as follows:(i)
T
G
e: the time of executing a bilinear map operation e
:
G
1
×
G
1
→
G
2;
(ii)
T
G
m
u
l: the time of executing a point scalar multiplication operation in G
1;
(iii)
T
G
H: the time of executing a map-to-point hash function H
1
,
H
2
:
{
0
,
1
}
*
→
G
1;
(iv)
T
e
x
p: the time of executing a modular exponentiation operation over a finite field F
p, where p is a large prime number;
(v)
T
i
n
v: the time of executing a modular multiplicative inverse operation over a finite field F
p, where p is a large prime number.Here, we first analyze the computational cost of our protocol. In Round 1,2
T
G
m
u
l is required to compute (
P
i
,
V
i
). In Round 2, each participant requires 3
T
G
e
+
7
T
G
m
u
l
+
4
T
G
H to verify (
I
D
i
+
k
,
j
,
P
i
+
k
,
V
i
+
k
) for k
∈
{
-
1
,
1
} and to generate (
D
i
,
α
i
,
β
i
,
γ
i
). In the group key computation phase, (
3
n
-
1
)
T
G
e
+
n
T
G
m
u
l
+
(
n
-
1
)
T
e
x
p is required to verify all (
I
D
i
,
j
,
D
i
,
α
i
,
β
i
,
γ
i
) and to compute a group key S
K
j. Note that to evaluate S
K
j
=
e
(
a
i
·
P
i
-
1
,
P
p
u
b
)
n
·
D
i
n
-
1
·
D
i
+
1
n
-
2
·
·
·
D
i
-
2 is required T
G
e
+
T
G
m
u
l since S
K
j
=
A
i
-
1
·
A
i
·
A
i
+
1
⋯
A
i
-
2, where A
i
-
1
=
e
(
a
i
·
P
i
-
1
,
P
p
u
b
), A
i
=
A
i
-
1
·
D
i, A
i
+
1
=
A
i
·
D
i
+
1
,
…, and A
i
-
2
=
A
i
-
3
·
D
i
-
2. As a result, each participant requires (
3
n
+
2
)
T
G
e
+
(
n
+
9
)
T
G
m
u
l
+
4
T
G
H
+
(
n
-
1
)
T
e
x
p in our protocol.In Table1, we compare our RID-AGKE protocol with four previously proposed AGKE protocols which include Tseng’s AGKE protocol [25], Choi et al.’s ID-AGKE protocol [26], Wu et al.’s ID-AGKE protocol [6], and Wu et al.’s RID-AGKE protocol [4] in terms of the public key setting, number of rounds, computational cost, and security properties. One recent non-ID-based and non-RID-based AGKE protocol with identifying malicious participants was proposed by Tseng [25]. Since Tseng’s protocol is based on the ElGmal system [29], each participant must verify the other participants’ certificates for participant authentication. It will increase the required computational costs for verifying certificates, besides (
8
n
-
2
)
T
e
x
p
+
(
n
+
1
)
T
i
n
v. On the contrary, Choi et al.’s ID-AGKE [26], Wu et al.’s ID-AGKE [6], Wu et al.’s RID-AGKE [4], and our protocol rely on the IDPKS system [8] or the R-IDPKS system [14]. Thus, they need not manage and verify the participants’ certificates. However, Choi et al.’s ID-AGKE [26] suffered from an insider colluding attack demonstrated by Wu and Tseng [27].Table 1
Comparisons between our protocol and the previously proposed AGKE protocols.
Tseng’s AGKE [25]
Choi et al.’s ID-AGKE [26]
Wu et al.’s ID-AGKE [6]
Wu et al.’s RID-AGKE [4]
Our protocol
Public key setting
ElGmal
IDPKS
IDPKS
R-IDPKS
R-IDPKS
Certificate management
Required
Not required
Not required
Not required
Not required
Rounds
2
2
2
3
2
Computational cost for each participant
(
8
n
-
2
)
T
e
x
p
+
(
n
+
1
)
T
i
n
v
6
T
G
e
+
(
n
+
11
)
T
G
m
u
l
+
(
n
+
3
)
T
G
H
(
3
n
+
3
)
T
G
e
+
(
n
+
10
)
T
G
m
u
l
+
3
T
G
H
+
(
n
-
1
)
T
e
x
p
8
T
G
e
+
(
2
n
+
8
)
T
G
m
u
l
+
4
n
T
G
H
(
3
n
+
2
)
T
G
e
+
(
n
+
9
)
T
G
m
u
l
+
4
T
G
H
+
(
n
-
1
)
T
e
x
p
Security
Provably secure
Existing attack [27]
Provably secure
Provably secure
Provably secure
Revocation functionality
Using CRL [28]
No
No
Yes
Yes
Resistant to malicious participants
Yes (confirmed computation)
No
Yes (confirmed computation)
Yes (explicit key confirmation)
Yes (confirmed computation)
Identifying malicious participants
Yes
No
Yes
No
YesFor Wu et al.’s ID-AGKE [6], Wu et al.’s RID-AGKE [4], and our protocol, they are provably secure and are able to resist malicious participants. It is easy to see that our protocol is more efficient than Wu et al.’s ID-AGKE [6] even though both protocols can identify malicious participants via confirmed computation approach. More importantly, Wu et al.’s ID-AGKE protocol [6] does not provide a solution to revoke the compromised or misbehaving user in the group. It is very serious because these revoked participants should not be allowed to establish a common key with other legal (nonrevoked) participants. In another aspect, Wu et al.’s RID-AGKE [4] is a three-round protocol and adopts explicit key confirmation approach to resist malicious participants. Though their protocol can detect the existence of malicious participants, it cannot still identify malicious participant. Our proposed RID-AGKE is a two-round protocol and provides an active detection mechanism to identify malicious participants. According to Table 1, the advantage of our protocol is demonstrated.


## 7. Conclusions

In this paper, we have fused the Tseng-Tsai R-IDPKS system and a noninteractive confirmed computation technique to propose the first RID-AGKE protocol with identifying malicious participants. The framework and security notions for RID-AGKE protocols have been defined to formalize the possible threats and attacks. When compared with the recently proposed ID/RID-AGKE protocols resistant to malicious participants, our protocol has better performance and provides an active detection way to identify malicious participants. In the random oracle model and under two mathematical assumptions (CDH and DBDH), we have proven that the proposed protocol is a secure RID-AGKE protocol with forward secrecy and identifying malicious participants.



---

*Source: 367264-2014-06-01.xml*