# Interdomain Identity-Based Key Agreement Schemes

Authors: Chun-I Fan; Yi-Hui Lin; Tuan-Hung Hsu; Ruei-Hau Hsu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

In order to simplify key management, two-party and three-party key agreement schemes based on user identities have been proposed recently. Multiparty (including more than three parties) key agreement protocols, which also are called conference key schemes, can be applied to distributed systems and wireless environments, such as ad hoc networks, for the purpose of multiparty secure communication. However, it is hard to extend two- or three-party schemes to multiparty ones with the guarantee of efficiency and security. In addition to the above two properties, interdomain environments should also be considered in key agreement systems due to diversified network domains. However, only few identity-based multiparty conference key agreement schemes for single domain environments and none for interdomain environments were proposed in the literature and they did not satisfy all of the security attributes such as forward secrecy and withstanding impersonation. In this paper, we will propose a novel efficient single domain identity-based multiparty conference key scheme and extend it to an interdomain one. Finally, we prove that the proposed schemes satisfy the required security attributes via
formal methods.


---

## Body

## 1. Introduction

The technique of key agreement allows two or more parties to exchange information and negotiate a common session key. The first key exchange scheme was proposed by Diffie and Hellman in 1976 [1] where two parties can exchange public information and then compute a common key by their private keys and received information. However, the basic Diffie-Hellman protocol lacks mutual authentication between two parties such that the man-in-the-middle attack is valid in this scheme. Many researchers modified Diffie-Hellman protocol to ensure mutual authentication between two parties, which are called authenticated key agreement (AKA) protocols. Lots of varieties of Diffie-Hellman protocol have been proposed and several different kinds of key agreement mechanisms have been shown in [2]. Up to now, Diffie-Hellman key exchange protocol is still an important basis for most key agreement protocols.In 1984, Shamir proposed an identity-based cryptosystem [3], where the public key of each user is her/his public identity information, and there exists a private key generator (PKG), a key generation center (KGC), or a Trusted Authority (TA) which is trusted by all users. PKG, KGC, or TA, which will be called TA below, can produce each user’s private key according to her/his public key. In almost all of the identity-based key agreement schemes, TA provides the private/public key generation services for users. When a user registers with TA, the user’s public information like ID or email address will be her/his public key and TA gives the user the private key corresponding to her/his public key.Pairing is a tool which is initially applied to cryptography to convert the Discrete Logarithm problem in elliptic curves to that in finite fields, and it can be derived from bilinear pairing, namely, Weil pairing [4] or Tate pairing [5]. First, Joux [6] used pairing to construct the first 3-party key agreement protocol based on a certificate system in 2000 and his scheme. Later, researchers found that pairing is suitable for the implementation of identity-based cryptosystems. Smart [7] proposed a two-party identity-based authenticated key agreement scheme in 2002. Boneh and Franklin [4] proposed an identity-based encryption scheme based on Weil pairing in 2003. Afterwards, pairing has become an important mathematic foundation of cryptography. There are many identity-based key agreement schemes, which have been proposed in the literature [7–11], based on pairings.A conference key agreement scheme is a variety of a multiparty key agreement or group key agreement scheme, but it is different from conference key distribution scheme. In a conference key distribution scheme, a session conference chair decides the conference key and then broadcasts it to every member in this session conference. In particular, in a conference key agreement scheme, we must guarantee that the protocol satisfies the following three properties.(1)
Each conference key is negotiated by all session members.
(2)
Every session member can compute the conference key via the same algorithm.
(3)
No session member can predict or preselect the conference key.The first formal security analysis in an identity-based two-party key agreement scheme was introduced by Chen and Kudla [9] and they improved the first identity-based key agreement scheme based on pairings [7]. Chen and Kudla proved that their protocol is secure on the security model of Bellare and Rogaway [12]. Later, Al-Riyami and Paterson also proposed four kinds of tripartite authenticated key agreement protocols by improving Joux’s scheme [13], and they showed that their scheme is secure. Unfortunately, Shim and Woo [14] pointed out that their scheme has some weaknesses. Furthermore, there are several conference key agreement schemes based on bilinear pairing which have been proposed in the literature [15–19], but they are all insecure, where their security weaknesses will be shown in Section 3 of the paper.Section4 will present two new hard problems, the n-Linear Diffie-Hellman (n-LDH) problem and the Decisional n-Linear Diffie-Hellman (n-DLDH) problem, on which our key agreement schemes are based.In Section5, we will propose a novel efficient identity-based conference key agreement scheme by combining the concepts of [16, 19]. In addition to a single TA, we also discuss how the users, who have registered with distinct TAs, negotiate a common conference key. Moreover, in order to formally demonstrate the security of our proposed schemes, we adopt the random oracle method, which was proposed by Bellare and Rogaway [12], to prove the security of our schemes under some well-known assumptions. We will define several security attributes in the third part of Section 2 and formally prove the security of our schemes in Section 6. Finally, we also provide performance comparison to demonstrate that our proposed schemes are more efficient than others.Our contributions are summarized as follows.(1)
We find some security flaws in the schemes of [15–19].
(2)
We introduce two new hard problems.
(3)
We propose interdomain identity-based conference key agreement schemes.
(4)
We formally prove that our schemes completely satisfy all of the security attributes.


## 2. Preliminaries

In this section, we review the concept of pairing which includes definitions, computationally hard problems, and security attributes of key agreement based on pairings.


### 2.1. Pairing

Pairing [20] in an elliptic curve cryptosystem is a function which maps a pair of elliptic curve points to an element of a multiplicative group in a finite field. It has been applied to key agreement, signatures, broadcast encryption, and identity-based encryption widely. In the following, we will review the definitions and properties of pairings.


#### 2.1.1. Bilinear Pairing

We briefly describe the concept of bilinear pairing [20]. Let (
G
1
,
+
) and (
G
2
,
+
) be abelian groups written in additive notation with prime order q and identity elements O
1 and O
2, respectively, such that q
P
=
O
1 and q
Q
=
O
2, where ∀
P
∈
G
1 and ∀
Q
∈
G
2. Suppose that (
G
T
,
*
) is a cyclic group of order q written in multiplicative notation with identity element 1
T. Now we have the groups (
G
1
,
+
), (
G
2
,
+
), and (
G
T
,
*
). The mapping function is
(1)
e
:
G
1
×
G
2
⟶
G
T
.Typically,G
1 and G
2 are subgroups of the points on an elliptic curve over a finite field and G
T is a subgroup of a multiplicative group over a finite field.In addition, the following additional properties must be satisfied:(i)
bilinearity
∀
P
,
P
′
∈
G
1
,
Q
,
Q
′
∈
G
2,
e
(
P
+
P
′
,
Q
)
=
e
(
P
,
Q
)
·
e
(
P
′
,
Q
) and e
(
P
,
Q
+
Q
′
)
=
e
(
P
,
Q
)
·
e
(
P
,
Q
′
),
e
(
a
P
,
Q
)
=
e
(
P
,
Q
)
a
=
e
(
P
,
a
Q
) for all a
∈
Z
q
*;
(ii)
nondegeneracy
∀
P
∈
G
1, with P
≠
O
1, ∃
Q
∈
G
2 such that e
(
P
,
Q
)
≠
1
T,
∀
Q
∈
G
2, with Q
≠
O
2, ∃
P
∈
G
1 such that e
(
P
,
Q
)
≠
1
T,
∀
P
∈
G
1 and ∀
Q
∈
G
2, e
(
P
,
O
2
)
=
e
(
O
1
,
Q
)
=
1
T;
(iii)
computability
ifP
∈
G
1 and Q
∈
G
2, there exists an efficient algorithm which can compute e
(
P
,
Q
) in polynomial time.The schemes in Section3 use symmetric bilinear pairing, so they set G
1
=
G
2. In order to make the following decisional problems remain hard, we set G
1
≠
G
2 and there is no polynomial-time computable isomorphism ϕ
:
G
1
→
G
2, such that ϕ
(
P
)
=
Q, where P is a generator of G
1 and Q is a generator of G
2.


### 2.2. Hard Problems

(1)
The Discrete Logarithm (DL) problem:
givenP
,
P
′
∈
G
1, find an integer x
∈
Z
q
* such that P
′
=
x
P.
(2)
The Computational Diffie-Hellman (CDH) problem: for x
,
y
∈
R
Z
q
*, given (
P
,
x
P
,
y
P
)
∈
G
1
3, compute x
y
P.
(3)
The Decisional Diffie-Hellman (DDH) problem:
forx
,
y
∈
R
Z
q
*, given (
P
,
x
P
,
y
P
,
z
P
)
∈
G
1
4 where z
=
x
y (mod q) or z
∈
R
Z
q
*  is decided by flipping a coin. Output “Yes” if z
=
x
y (mod q); otherwise output “No”.
(4)
The Divisible Computational Diffie-Hellman (DCDH) problem [21]: for x
,
y
∈
R
Z
q
*, given (
P
,
x
P
,
y
P
)
∈
G
1
3, compute x
y
-
1
P.
(5)
The Decisional Linear Diffie-Hellman (DLDH) problem in G
1 [22, 23]: for x
1
,
x
2
,
x
3
,
x
4
∈
R
Z
q
*, given (
P
,
x
1
P
,
x
2
P
,
x
1
x
3
P
,
x
2
x
4
P
,
Z
)
∈
G
1
6, where Z
=
(
x
3
+
x
4
)
P or Z
∈
R
G
1 is decided by flipping a coin. Output “Yes” if Z
=
(
x
3
+
x
4
)
P; otherwise output “No”.
This hard problem was first proposed by Boneh et al. [22] in 2004 and then Boyen and Waters [23] extended it to asymmetric bilinear groups in 2006.
(6)
The co-Bilinear Diffe-Hellman (co-BDH) problem [4]: given (
P
1
,
a
P
1
,
b
P
1
)
∈
G
1
3 and (
P
2
,
a
P
2
,
c
P
2
)
∈
G
2
3 in asymmetric bilinear map groups (
G
1
,
G
2
,
G
T
), compute e
(
P
1
,
P
2
)
a
b
c
∈
G
T.
We propose the variant-CDH problem and extend the DLDH problem to then-LDH and n-DLDH problems. We will prove that they are also hard in Section 4.
(7)
The Variant Computational Diffie-Hellman (variant-CDH) problem: given (
P
1
,
a
P
1
,
b
P
1
)
∈
G
1
3 and (
P
2
,
a
P
2
)
∈
G
2
2, compute a
b
P
1.
(8)
The n-Linear Diffie-Hellman (n-LDH) problem: given P, x
i
P’s, and x
i
x
n
+
j
P’s ∈
G
1 for all i, j with 1
≤
i, j
≤
n, i
≠
j, and n
≥
2, compute (
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P.
(9)
The Decisional n-Linear Diffie-Hellman (n-DLDH) problem: given Z, P, x
i
P’s, and x
i
x
n
+
j
P’s ∈
G
1 for all i, j with 1
≤
i, j
≤
n, i
≠
j, and n
≥
2, where Z
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P or Z
∈
R
G
1 is decided by flipping a coin. Output “Yes” if Z
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P; otherwise output “No”.


### 2.3. Security Attributes

There are some security definitions in the identity-based key agreement schemes based on pairing [13, 14]. We describe them as follows.Known Session Key Security. A key agreement protocol should produce a unique common secret key, which is called a session key, for every session. The protocol should still achieve this goal when an adversary has learned all of the other session keys.(Perfect) Forward Secrecy. Forward secrecy is that any adversary cannot derive previous session keys from compromised long-term private keys of one or more parties.Partial forward secrecy is that one or more (not all) parties’ long-term private keys are corrupted but any adversary cannot get any previous session keys which were established by these parties.Perfect forward secrecy means that any adversaries cannot derive previous session keys even though they have obtained the long-term private keys of all parties. In ID-based systems, perfect forward secrecy implies that TA’s and all users’ long-term private keys are corrupted but any previous session key established by the registered users cannot be derived by adversaries. We also call itTA forward secrecy.Key-Compromise Impersonation. A protocol can resist key-compromise impersonation if an adversary cannot impersonate some users even though the other users’ long-term private keys were disclosed.Man-in-the-middle attack is a special case of key-compromise impersonation in ID-based systems. If an adversary intercepts messages, retransmits them, and then communicates with users without being detected in the key agreement protocol, we say that he succeeds in impersonation.Withstanding key-compromise impersonation also covers unknown key-share resilience. It is the basic security attribute for key agreement scheme. Some users cannot have a key agreement with the other users without the knowledge of them. If some users cannot impersonate the others, they cannot run the key agreement scheme for them.Key Control. It should be impossible for any participant (or an adversary) to preselect a value as a session key or predict the value of the session key.


## 2.1. Pairing

Pairing [20] in an elliptic curve cryptosystem is a function which maps a pair of elliptic curve points to an element of a multiplicative group in a finite field. It has been applied to key agreement, signatures, broadcast encryption, and identity-based encryption widely. In the following, we will review the definitions and properties of pairings.


### 2.1.1. Bilinear Pairing

We briefly describe the concept of bilinear pairing [20]. Let (
G
1
,
+
) and (
G
2
,
+
) be abelian groups written in additive notation with prime order q and identity elements O
1 and O
2, respectively, such that q
P
=
O
1 and q
Q
=
O
2, where ∀
P
∈
G
1 and ∀
Q
∈
G
2. Suppose that (
G
T
,
*
) is a cyclic group of order q written in multiplicative notation with identity element 1
T. Now we have the groups (
G
1
,
+
), (
G
2
,
+
), and (
G
T
,
*
). The mapping function is
(1)
e
:
G
1
×
G
2
⟶
G
T
.Typically,G
1 and G
2 are subgroups of the points on an elliptic curve over a finite field and G
T is a subgroup of a multiplicative group over a finite field.In addition, the following additional properties must be satisfied:(i)
bilinearity
∀
P
,
P
′
∈
G
1
,
Q
,
Q
′
∈
G
2,
e
(
P
+
P
′
,
Q
)
=
e
(
P
,
Q
)
·
e
(
P
′
,
Q
) and e
(
P
,
Q
+
Q
′
)
=
e
(
P
,
Q
)
·
e
(
P
,
Q
′
),
e
(
a
P
,
Q
)
=
e
(
P
,
Q
)
a
=
e
(
P
,
a
Q
) for all a
∈
Z
q
*;
(ii)
nondegeneracy
∀
P
∈
G
1, with P
≠
O
1, ∃
Q
∈
G
2 such that e
(
P
,
Q
)
≠
1
T,
∀
Q
∈
G
2, with Q
≠
O
2, ∃
P
∈
G
1 such that e
(
P
,
Q
)
≠
1
T,
∀
P
∈
G
1 and ∀
Q
∈
G
2, e
(
P
,
O
2
)
=
e
(
O
1
,
Q
)
=
1
T;
(iii)
computability
ifP
∈
G
1 and Q
∈
G
2, there exists an efficient algorithm which can compute e
(
P
,
Q
) in polynomial time.The schemes in Section3 use symmetric bilinear pairing, so they set G
1
=
G
2. In order to make the following decisional problems remain hard, we set G
1
≠
G
2 and there is no polynomial-time computable isomorphism ϕ
:
G
1
→
G
2, such that ϕ
(
P
)
=
Q, where P is a generator of G
1 and Q is a generator of G
2.


## 2.1.1. Bilinear Pairing

We briefly describe the concept of bilinear pairing [20]. Let (
G
1
,
+
) and (
G
2
,
+
) be abelian groups written in additive notation with prime order q and identity elements O
1 and O
2, respectively, such that q
P
=
O
1 and q
Q
=
O
2, where ∀
P
∈
G
1 and ∀
Q
∈
G
2. Suppose that (
G
T
,
*
) is a cyclic group of order q written in multiplicative notation with identity element 1
T. Now we have the groups (
G
1
,
+
), (
G
2
,
+
), and (
G
T
,
*
). The mapping function is
(1)
e
:
G
1
×
G
2
⟶
G
T
.Typically,G
1 and G
2 are subgroups of the points on an elliptic curve over a finite field and G
T is a subgroup of a multiplicative group over a finite field.In addition, the following additional properties must be satisfied:(i)
bilinearity
∀
P
,
P
′
∈
G
1
,
Q
,
Q
′
∈
G
2,
e
(
P
+
P
′
,
Q
)
=
e
(
P
,
Q
)
·
e
(
P
′
,
Q
) and e
(
P
,
Q
+
Q
′
)
=
e
(
P
,
Q
)
·
e
(
P
,
Q
′
),
e
(
a
P
,
Q
)
=
e
(
P
,
Q
)
a
=
e
(
P
,
a
Q
) for all a
∈
Z
q
*;
(ii)
nondegeneracy
∀
P
∈
G
1, with P
≠
O
1, ∃
Q
∈
G
2 such that e
(
P
,
Q
)
≠
1
T,
∀
Q
∈
G
2, with Q
≠
O
2, ∃
P
∈
G
1 such that e
(
P
,
Q
)
≠
1
T,
∀
P
∈
G
1 and ∀
Q
∈
G
2, e
(
P
,
O
2
)
=
e
(
O
1
,
Q
)
=
1
T;
(iii)
computability
ifP
∈
G
1 and Q
∈
G
2, there exists an efficient algorithm which can compute e
(
P
,
Q
) in polynomial time.The schemes in Section3 use symmetric bilinear pairing, so they set G
1
=
G
2. In order to make the following decisional problems remain hard, we set G
1
≠
G
2 and there is no polynomial-time computable isomorphism ϕ
:
G
1
→
G
2, such that ϕ
(
P
)
=
Q, where P is a generator of G
1 and Q is a generator of G
2.


## 2.2. Hard Problems

(1)
The Discrete Logarithm (DL) problem:
givenP
,
P
′
∈
G
1, find an integer x
∈
Z
q
* such that P
′
=
x
P.
(2)
The Computational Diffie-Hellman (CDH) problem: for x
,
y
∈
R
Z
q
*, given (
P
,
x
P
,
y
P
)
∈
G
1
3, compute x
y
P.
(3)
The Decisional Diffie-Hellman (DDH) problem:
forx
,
y
∈
R
Z
q
*, given (
P
,
x
P
,
y
P
,
z
P
)
∈
G
1
4 where z
=
x
y (mod q) or z
∈
R
Z
q
*  is decided by flipping a coin. Output “Yes” if z
=
x
y (mod q); otherwise output “No”.
(4)
The Divisible Computational Diffie-Hellman (DCDH) problem [21]: for x
,
y
∈
R
Z
q
*, given (
P
,
x
P
,
y
P
)
∈
G
1
3, compute x
y
-
1
P.
(5)
The Decisional Linear Diffie-Hellman (DLDH) problem in G
1 [22, 23]: for x
1
,
x
2
,
x
3
,
x
4
∈
R
Z
q
*, given (
P
,
x
1
P
,
x
2
P
,
x
1
x
3
P
,
x
2
x
4
P
,
Z
)
∈
G
1
6, where Z
=
(
x
3
+
x
4
)
P or Z
∈
R
G
1 is decided by flipping a coin. Output “Yes” if Z
=
(
x
3
+
x
4
)
P; otherwise output “No”.
This hard problem was first proposed by Boneh et al. [22] in 2004 and then Boyen and Waters [23] extended it to asymmetric bilinear groups in 2006.
(6)
The co-Bilinear Diffe-Hellman (co-BDH) problem [4]: given (
P
1
,
a
P
1
,
b
P
1
)
∈
G
1
3 and (
P
2
,
a
P
2
,
c
P
2
)
∈
G
2
3 in asymmetric bilinear map groups (
G
1
,
G
2
,
G
T
), compute e
(
P
1
,
P
2
)
a
b
c
∈
G
T.
We propose the variant-CDH problem and extend the DLDH problem to then-LDH and n-DLDH problems. We will prove that they are also hard in Section 4.
(7)
The Variant Computational Diffie-Hellman (variant-CDH) problem: given (
P
1
,
a
P
1
,
b
P
1
)
∈
G
1
3 and (
P
2
,
a
P
2
)
∈
G
2
2, compute a
b
P
1.
(8)
The n-Linear Diffie-Hellman (n-LDH) problem: given P, x
i
P’s, and x
i
x
n
+
j
P’s ∈
G
1 for all i, j with 1
≤
i, j
≤
n, i
≠
j, and n
≥
2, compute (
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P.
(9)
The Decisional n-Linear Diffie-Hellman (n-DLDH) problem: given Z, P, x
i
P’s, and x
i
x
n
+
j
P’s ∈
G
1 for all i, j with 1
≤
i, j
≤
n, i
≠
j, and n
≥
2, where Z
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P or Z
∈
R
G
1 is decided by flipping a coin. Output “Yes” if Z
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P; otherwise output “No”.


## 2.3. Security Attributes

There are some security definitions in the identity-based key agreement schemes based on pairing [13, 14]. We describe them as follows.Known Session Key Security. A key agreement protocol should produce a unique common secret key, which is called a session key, for every session. The protocol should still achieve this goal when an adversary has learned all of the other session keys.(Perfect) Forward Secrecy. Forward secrecy is that any adversary cannot derive previous session keys from compromised long-term private keys of one or more parties.Partial forward secrecy is that one or more (not all) parties’ long-term private keys are corrupted but any adversary cannot get any previous session keys which were established by these parties.Perfect forward secrecy means that any adversaries cannot derive previous session keys even though they have obtained the long-term private keys of all parties. In ID-based systems, perfect forward secrecy implies that TA’s and all users’ long-term private keys are corrupted but any previous session key established by the registered users cannot be derived by adversaries. We also call itTA forward secrecy.Key-Compromise Impersonation. A protocol can resist key-compromise impersonation if an adversary cannot impersonate some users even though the other users’ long-term private keys were disclosed.Man-in-the-middle attack is a special case of key-compromise impersonation in ID-based systems. If an adversary intercepts messages, retransmits them, and then communicates with users without being detected in the key agreement protocol, we say that he succeeds in impersonation.Withstanding key-compromise impersonation also covers unknown key-share resilience. It is the basic security attribute for key agreement scheme. Some users cannot have a key agreement with the other users without the knowledge of them. If some users cannot impersonate the others, they cannot run the key agreement scheme for them.Key Control. It should be impossible for any participant (or an adversary) to preselect a value as a session key or predict the value of the session key.


## 3. Security Problems in the Previous Schemes

In the section, we briefly introduce security weaknesses on the schemes [15–19, 24–26]. The details of the security problems in these schemes are in the Appendices.Shi et al. [19] proposed an ID-based authenticated group key agreement protocol in 2005. The design of the protocol is efficient because it only takes one round to finish a group key agreement and it needs no exponentiation computation besides a pairing computation. We find that the protocol does not resist key-compromise impersonation since the users do not verify the messages with one another in the protocol. Moreover, it only achieves partial forward secrecy.Du et al. [15] proposed an ID-based authenticated group key agreement protocol in 2003 and improved it in the same year. Both of them does not achieve perfect forward secrecy. Although they embed a signature scheme to verify the messages, both of the protocols still suffer from key-compromise impersonation found by Zhang and Chen [29]. In the attack of [29], the adversaries collect the messages of the user in the previous session and replay them after modifying the messages. Zhang and Chen [30] also attacked Choi et al. [24] with the same method in 2004. The protocol of Zhang et al. [18] in 2005 has the same security problem as Du’s since they embed the same signature scheme in the protocol.Kim et al. [17] aims to design a one-round key agreement protocol. But we find that the protocol cannot even achieve known session key security. Anyone can compute the session key through collecting the broadcasting messages.Zhou et al. [26] proposed two schemes, one is one-round and the other is two-round. We find that both of them cannot withstand key-compromise impersonation. For the first scheme, the other users can collide to impersonate the user U
i. For the second one, the user U
1 can impersonate any other user he wants. We also find that the protocol of Yao et al. [25] is not immune to key-compromise impersonation, either. A user can impersonate another by rebroadcasting the messages. The work of [31] improved the flaw but did not provide any formal proofs. Yuan et al. [27] improved it with formal proofs.


## 4. Three New Hard Problems

We formally prove our proposed problems, the Variant Computational Diffie-Hellman problem, then-Linear Diffie-Hellman problem, and the Decisional n-Linear Diffie-Hellman problem, being hard by using problem reduction and generic model, respectively.


### 4.1.  The Variant Computational Diffie-Hellman (Variant-CDH) Problem

Theorem 1.
The variant-CDH problem is hard if the co-BDH problem is hard.Proof.
Suppose that there exists an oracle which can solve the variant-CDH problem with nonnegligible probability. We will prove that the oracle can help us to solve the co-BDH problem with nonnegligible probability. Given any parameters of the co-BDH problem,(
P
1
,
a
P
1
,
b
P
1
)
∈
G
1
3 and (
P
2
,
a
P
2
,
c
P
2
)
∈
G
2
3, we input (
P
1
,
a
P
1
,
b
P
1
) and (
P
2
,
a
P
2
) into the variant-CDH oracle. The oracle will output a
b
P
1. Then, we solve the co-BDH problem by computing e
(
a
b
P
1
,
c
P
2
)
=
e
(
P
1
,
P
2
)
a
b
c.


### 4.2.  Then-Linear Diffie-Hellman (n-LDH) Problem

Theorem 2.
Then-LDH problem is hard if and only if the DCDH problem is hard.Proof.
(1)n-LDH ⇒ DCDH. Suppose that there exists an oracle which can solve the n-LDH problem with nonnegligible probability. We will prove that the oracle can help us to solve the DCDH problem with nonnegligible probability.
For any DCDH triple(
P
,
x
P
,
y
P
), we convert them into the n-LDH oracle’s input parameters which are shown in (2):
(2)
x
1
P
x
2
P
…
x
n
-
1
P
x
n
P
⊥
x
2
x
n
+
1
P
…
x
n
-
1
x
n
+
1
P
x
n
x
n
+
1
P
x
1
x
n
+
2
P
⊥
…
x
n
-
1
x
n
+
2
P
x
n
x
n
+
2
P
⋮
⋮
⋮
⋮
x
1
x
2
n
-
1
P
x
2
x
2
n
-
1
P
…
⊥
x
n
x
2
n
-
1
P
x
1
x
2
n
P
x
2
x
2
n
P
…
x
n
-
1
x
2
n
P
⊥
.
We randomly pickt
2
,
t
3
,
…
,
t
n
∈
Z
q
* and Q
1
,
Q
2
,
…
,
Q
n
-
1
∈
G
1
*, compute Q
n
=
x
P
-
Q
1
-
Q
2
-
⋯
-
Q
n
-
1, and set other parameters in (3):
(3)
y
P
t
2
y
P
t
3
y
P
…
t
n
-
1
y
P
t
n
y
P
⊥
t
2
Q
1
t
3
Q
1
…
t
n
-
1
Q
1
t
n
Q
1
Q
2
⊥
t
3
Q
2
…
t
n
-
1
Q
2
t
n
Q
2
⋮
⋮
⋮
⋮
⋮
Q
n
-
1
t
2
Q
n
-
1
t
3
Q
n
-
1
…
⊥
t
n
Q
n
-
1
Q
n
t
2
Q
n
t
3
Q
n
…
t
n
-
1
Q
n
⊥
.
Equation (2) is equal to (3); that is, x
1
P
=
y
P, x
2
P
=
t
2
x
1
P
=
t
2
y
P, x
3
P
=
t
3
x
1
P
=
t
3
y
P
,
…
,
x
n
P
=
t
n
x
1
P
=
t
n
y
P in row 1, x
2
x
n
+
1
P
=
t
2
x
1
x
n
+
1
P
=
t
2
Q
1, x
3
x
n
+
1
P
=
t
3
x
1
x
n
+
1
P
=
t
3
Q
1
,
…
,
x
n
x
n
+
1
P
=
t
n
x
1
x
n
+
1
P
=
t
n
Q
1 in row 2 (suppose that x
1
x
n
+
1
P
=
Q
1), x
1
x
n
+
2
P
=
Q
2, x
3
x
n
+
2
P
=
t
3
x
1
x
n
+
2
P
=
t
3
Q
2
,
…
,
x
n
x
n
+
2
P
=
t
n
x
1
x
n
+
2
P
=
t
n
Q
2 in row 3
,
…, and x
1
x
2
n
P
=
Q
n, x
2
x
2
n
P
=
t
2
x
1
x
2
n
P
=
t
2
Q
n, x
3
x
2
n
P
=
t
3
x
1
x
2
n
P
=
t
3
Q
n
,
…
,
x
n
-
1
x
2
n
P
=
t
n
-
1
x
1
x
2
n
P
=
t
n
-
1
Q
n in row n
+
1. The oracle will output (
x
n
+
1
+
x
n
+
2
+
x
n
+
3
+
⋯
+
x
2
n
-
1
+
x
2
n
)
P. Thus, we have that
(4)
x
P
=
Q
1
+
Q
2
+
⋯
+
Q
n
-
1
+
Q
n
=
x
1
x
n
+
1
P
+
x
1
x
n
+
2
P
+
⋯
+
x
1
x
2
n
-
1
P
+
x
1
x
2
n
P
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
-
1
+
x
2
n
)
x
1
P
=
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
-
1
+
x
2
n
y
P
.
From (4), we can get x
y
-
1
P
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
-
1
+
x
2
n
)
P.
(2)n-LDH ⇐ DCDH. Suppose that there exists an oracle which can solve the the DCDH problem with nonnegligible probability. We will prove that the oracle can help us to solve the n-LDH problem with nonnegligible probability, too.
For anyn-LDH tuple in (2), we input (
x
1
x
n
+
2
P
,
x
1
P
)
,
(
x
1
x
n
+
3
P
,
x
1
P
)
,
…
,
(
x
1
x
2
n
P
,
x
1
P
), and (
x
2
x
n
+
1
P
,
x
2
P
) into the oracle. Then the oracle outputs x
n
+
2
P
,
x
n
+
3
P
,
…
,
x
2
n
P, and x
n
+
1
P, respectively.
Finally, we can computex
n
+
1
P
+
x
n
+
2
P
+
⋯
+
x
2
n
P
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P to solve the n-LDH problem.We use a way similar to [22] to prove the n-DLDH problem being hard. In the generic model, elements of G
1, G
2, and G
T are encoded as unique random strings, where G
1 and G
2 are additive groups and G
T is a multiplicative group. There is a bilinear pairing function e
:
G
1
×
G
2
→
G
T. Let S
1, S
2, and S
T be the sets of strings. The opaque encoding of the elements of G
1 is modeled as an injective function ζ
1
:
Z
q
→
S
1, where S
1
⊂
{
0,1
}
*, which maps all a
∈
Z
q to the string representation ζ
1
(
a
) of a
P
∈
G
1. Analogous mapping ζ
2
:
Z
q
→
S
2 and ζ
T
:
Z
q
→
S
T map all a
∈
Z
q to the string representation ζ
2
(
a
) of a
P
′
∈
G
2 and ζ
T
(
a
) of g
a
∈
G
T, where g
=
e
(
P
,
P
′
).


### 4.3.  The Decisionaln-Linear Diffie-Hellman (n-DLDH) Problem

Theorem 3.
LetA be an algorithm that solves the n-DLDH problem in the generic bilinear group model with at most q
k oracle queries. Let x
i’s, x
n
+
j’s, and z
∈
Z
q be chosen at random, where 1
≤
i, j
≤
n, and n
≥
2, ζ
1, ζ
2, and ζ
T are random encoding functions for G
1, G
2, and G
T, and b
∈
{
0,1
} is a random bit. Let w
b
=
z and w
1
-
b
=
∑
j
=
1
n
x
n
+
j
mod
q. The probability is
(5)
Pr
A
(
ζ
1
,
ζ
2
,
ζ
T
;
1
,
x
i
ʼ
s
,
x
i
x
n
+
j
ʼ
s
,
w
0
,
w
1
)
=
b
:
∀
i
,
j
,
x
i
,
x
n
+
j
∈
Z
q
*
,
1
≤
i
,
j
≤
n
,
i
≠
j
,
n
≥
2
,
b
∈
{
0,1
}
=
1
2
+
2
n
2
+
3
+
q
k
2
q
.Proof.
B plays the following game with A. B maintains the lists L
1
=
{
(
F
1
,
s
,
ζ
1
,
s
)
:
s
=
0,1
,
2
,
…
,
τ
1
-
1
}, L
2
=
{
(
F
2
,
t
,
ζ
2
,
t
)
:
t
=
0,1
,
2
,
…
,
τ
2
-
1
}, and L
T
=
{
(
F
T
,
u
,
ζ
T
,
u
)
:
t
=
0,1
,
2
,
…
,
τ
T
-
1
}. Let X
i’s, X
i
X
n
+
j’s, W
0, and W
1 (∀
i
,
j
,
1
≤
i, j
≤
n, i
≠
j) be indeterminate. All F
1
,
s’s, F
2
,
t’s, and F
T
,
u’s ∈
Z
q
[
X
i’s, X
i
X
n
+
j’s, W
0
,
W
1
] are polynomials and ζ
1
,
s’s, ζ
2
,
t’s, ζ
T
,
u’s ∈
{
0,1
}
* are distinct strings. At the beginning of the game, B sets F
1,0
=
1, F
1,1
=
X
1, F
1,2
=
X
2
,
…
,
F
1
,
n
=
X
n, F
1
,
n
2
+
1
=
W
0, F
1
,
n
2
+
2
=
W
1, F
2,0
=
1, F
T
,
0
=
1, and the following polynomials: [(
⊥
,
F
1
,
n
+
1
=
X
2
X
n
+
1
,
…
,
F
1,2
n
-
2
=
X
n
-
1
X
n
+
1
,
F
1,2
n
-
1
=
X
n
X
n
+
1
), (
F
1,2
n

=

X
1
X
n
+
2
,

⊥
,
…
,
F
1,3
n
-
3
=
X
n
-
1
X
n
+
2
,
F
1,3
n
-
2
=
X
n
X
n
+
2
),…
,
(
F
1
,
n
2
-
2
n
+
3
=
X
1
X
2
n
-
1
,
F
1
,
n
2
-
2
n
+
4
=
X
2
X
2
n
-
1
,
…
,
⊥
,
F
1
,
n
2
-
n
+
1
=
X
n
X
2
n
-
1
), (
F
1
,
n
2
-
n
+
2
=
X
1
X
2
n
,
F
1
,
n
2
-
n
+
3
=
X
2
X
2
n
,
…
,
F
1
,
n
2
=
X
n
-
1
X
2
n
,
,
⊥
)], where the symbol “⊥” means emptiness and B gives A the distinct strings ζ
1,0
,
ζ
1,1
,
…
,
ζ
1
,
n
2
+
2, ζ
2,0, and ζ
T
,
0. In the initial list index, the numbers of the records in L
1, L
2, and L
T are τ
1
=
n
2
+
3, τ
2
=
1, and τ
T
=
1, respectively, where τ
=
τ
1
+
τ
2
+
τ
T
=
n
2
+
5. At any step in the game, A can make the group and pairing queries. B performs and responds to A as follows.
Group Action.
A gives B two operands ζ
1
,
s, ζ
1
,
t and a sign bit, where 0
≤
s, t
<
τ
1. B sets F
1
,
τ
1
←
F
1
,
s
±
F
1
,
t. If F
1
,
τ
1
=
F
1
,
l for some l
<
τ
1, B sets ζ
1
,
τ
1
←
ζ
1
,
l. Otherwise, B sets ζ
1
,
τ
1 to be a string in {
0,1
}
* distinct from ζ
1,0
,
ζ
1,1
,
…
,
ζ
1
,
τ
1
-
1. Finally, B adds (
F
1
,
τ
1
,
ζ
1
,
τ
) to the list L
1, gives ζ
1
,
τ
1 to A, and sets τ
1
←
τ
1
+
1. The group action queries in G
2 and G
T are simulated similarly.
Pairing.
A gives B two operands ζ
1
,
s and ζ
1
,
t with 0
≤
s
<
τ
1 and 0
≤
t
<
τ
2. B sets the product F
T
,
τ
T
←
F
1
,
s
F
2
,
t. If F
T
,
τ
T
=
F
T
,
l for some l
<
τ
T, B sets ζ
T
,
τ
T
←
ζ
T
,
l. Otherwise, B sets ζ
T
,
τ
T to be a string in {
0,1
}
* distinct from ζ
T
,
0
,
ζ
T
,
1
,
…
,
ζ
T
,
τ
T
-
1. Finally, B adds (
F
T
,
τ
T
,
ζ
T
,
τ
T
) to the list L
T, gives ζ
T
,
τ
T to A, and sets τ
T
←
τ
T
+
1.Consider the operation thatB performs: (
1
)
B adds/subtracts all polynomials in the list L
1, L
2, and L
T by any A’s query. 2  B produces any of two polynomials in L
1 and L
2 to generate a new polynomial in L
T. For any variant X
n
+
j, it occurs within the monomials X
1
X
n
+
j
,
X
2
X
n
+
j
,
…
,
X
n
+
j
-
1
X
n
+
j
,
X
n
+
j
+
1
X
n
+
j
,
…
,
X
2
n
X
n
+
j in L
1 and L
T lists and it occurs no monomial in L
2 list. Therefore, B cannot produce any polynomial that contains the monomial c
X
n
+
j’s in G
1 or G
2 and the monomial F
2
,
t
X
n
+
j’s in G
T for any coefficient c
≠
0 and any nonzero monomial F
2
,
t in L
2 in the available operations.After at mostq queries, A terminates and returns a guess b
^
∈
{
0,1
}. The distinct values of operands provide no information to A because they are random bit strings. Therefore, the probability that A wins the game in the generic model is 1
/
2.However, whenB randomly chooses x
i’s, x
n
+
j’s, and z
∈
Z, sets w
b
=
∑
j
=
1
n
x
n
+
j and w
1
-
b
=
z, and assigns X
1
←
x
1
,
X
2
←
x
2
,
…
,
X
2
n
←
x
2
n
,
W
b
←
w
b, and W
1
-
b
←
w
1
-
b, a nontrivial equality relation may occur and give A some information that is not revealed in the generic model; that is, for some F
1
,
s
≠
F
1
,
t (and F
T
,
s
≠
F
T
,
t, resp.) and s
,
t
<
τ
1 (and s
,
t
<
τ
T, resp.), F
1
,
s
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1) = F
1
,
t
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1) (and F
T
,
s
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1) = F
T
,
t
(
x
i’s,
x
i
x
n
+
j’s,
w
0
,
w
1), resp.).The probability of the occurrence is computed according to the following lemma.Lemma 4 (see [32]).
Letq be prime and let t
≥
1. Let F
(
X
1
,
X
2
,
…
,
X
k
)
∈
Z
/
q
t
[
X
1
,
X
2
,
…
,
X
k
] be a nonzero polynomial of total degree d. Then for random x
1
,
x
2
,
…
,
x
k
∈
Z
/
q
t, the probability that F
(
x
1
,
x
2
,
…
,
x
k
)
=
0 is at most d
/
q.By Lemma4, all polynomials in the L
1 have degree at most 2, so that, for some s
,
t and F
1
,
s
≠
F
1
,
t, the probability of F
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1
) = F
1
,
s
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1
)
-
F
1
,
t
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1
)
=
0 is at most 2
/
q. The degree of polynomials in the L
2 is 0. All polynomials in the L
T have degree at most 2, so that, for some s
,
t and F
T
,
s
≠
F
T
,
t, the probability of F
′
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1
) = F
T
,
s
(
x
i’s,
x
i
x
n
+
j’s,
w
0
,
w
1
)
-
F
T
,
t
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1
)
=
0 is at most 2
/
q. Therefore, A wins the game with the probability ɛ
≤
1
/
2
+
τ
1
2
2
/
q
+
τ
T
2
2
/
q. Since τ
1
+
τ
T
≤
n
2
+
4
+
q
k, we have ɛ
≤
1
/
2
+
n
2
+
4
+
q
k
2
/
q, where the advantage is not greater than O
(
q
k
2
/
q
).


## 4.1.  The Variant Computational Diffie-Hellman (Variant-CDH) Problem

Theorem 1.
The variant-CDH problem is hard if the co-BDH problem is hard.Proof.
Suppose that there exists an oracle which can solve the variant-CDH problem with nonnegligible probability. We will prove that the oracle can help us to solve the co-BDH problem with nonnegligible probability. Given any parameters of the co-BDH problem,(
P
1
,
a
P
1
,
b
P
1
)
∈
G
1
3 and (
P
2
,
a
P
2
,
c
P
2
)
∈
G
2
3, we input (
P
1
,
a
P
1
,
b
P
1
) and (
P
2
,
a
P
2
) into the variant-CDH oracle. The oracle will output a
b
P
1. Then, we solve the co-BDH problem by computing e
(
a
b
P
1
,
c
P
2
)
=
e
(
P
1
,
P
2
)
a
b
c.


## 4.2.  Then-Linear Diffie-Hellman (n-LDH) Problem

Theorem 2.
Then-LDH problem is hard if and only if the DCDH problem is hard.Proof.
(1)n-LDH ⇒ DCDH. Suppose that there exists an oracle which can solve the n-LDH problem with nonnegligible probability. We will prove that the oracle can help us to solve the DCDH problem with nonnegligible probability.
For any DCDH triple(
P
,
x
P
,
y
P
), we convert them into the n-LDH oracle’s input parameters which are shown in (2):
(2)
x
1
P
x
2
P
…
x
n
-
1
P
x
n
P
⊥
x
2
x
n
+
1
P
…
x
n
-
1
x
n
+
1
P
x
n
x
n
+
1
P
x
1
x
n
+
2
P
⊥
…
x
n
-
1
x
n
+
2
P
x
n
x
n
+
2
P
⋮
⋮
⋮
⋮
x
1
x
2
n
-
1
P
x
2
x
2
n
-
1
P
…
⊥
x
n
x
2
n
-
1
P
x
1
x
2
n
P
x
2
x
2
n
P
…
x
n
-
1
x
2
n
P
⊥
.
We randomly pickt
2
,
t
3
,
…
,
t
n
∈
Z
q
* and Q
1
,
Q
2
,
…
,
Q
n
-
1
∈
G
1
*, compute Q
n
=
x
P
-
Q
1
-
Q
2
-
⋯
-
Q
n
-
1, and set other parameters in (3):
(3)
y
P
t
2
y
P
t
3
y
P
…
t
n
-
1
y
P
t
n
y
P
⊥
t
2
Q
1
t
3
Q
1
…
t
n
-
1
Q
1
t
n
Q
1
Q
2
⊥
t
3
Q
2
…
t
n
-
1
Q
2
t
n
Q
2
⋮
⋮
⋮
⋮
⋮
Q
n
-
1
t
2
Q
n
-
1
t
3
Q
n
-
1
…
⊥
t
n
Q
n
-
1
Q
n
t
2
Q
n
t
3
Q
n
…
t
n
-
1
Q
n
⊥
.
Equation (2) is equal to (3); that is, x
1
P
=
y
P, x
2
P
=
t
2
x
1
P
=
t
2
y
P, x
3
P
=
t
3
x
1
P
=
t
3
y
P
,
…
,
x
n
P
=
t
n
x
1
P
=
t
n
y
P in row 1, x
2
x
n
+
1
P
=
t
2
x
1
x
n
+
1
P
=
t
2
Q
1, x
3
x
n
+
1
P
=
t
3
x
1
x
n
+
1
P
=
t
3
Q
1
,
…
,
x
n
x
n
+
1
P
=
t
n
x
1
x
n
+
1
P
=
t
n
Q
1 in row 2 (suppose that x
1
x
n
+
1
P
=
Q
1), x
1
x
n
+
2
P
=
Q
2, x
3
x
n
+
2
P
=
t
3
x
1
x
n
+
2
P
=
t
3
Q
2
,
…
,
x
n
x
n
+
2
P
=
t
n
x
1
x
n
+
2
P
=
t
n
Q
2 in row 3
,
…, and x
1
x
2
n
P
=
Q
n, x
2
x
2
n
P
=
t
2
x
1
x
2
n
P
=
t
2
Q
n, x
3
x
2
n
P
=
t
3
x
1
x
2
n
P
=
t
3
Q
n
,
…
,
x
n
-
1
x
2
n
P
=
t
n
-
1
x
1
x
2
n
P
=
t
n
-
1
Q
n in row n
+
1. The oracle will output (
x
n
+
1
+
x
n
+
2
+
x
n
+
3
+
⋯
+
x
2
n
-
1
+
x
2
n
)
P. Thus, we have that
(4)
x
P
=
Q
1
+
Q
2
+
⋯
+
Q
n
-
1
+
Q
n
=
x
1
x
n
+
1
P
+
x
1
x
n
+
2
P
+
⋯
+
x
1
x
2
n
-
1
P
+
x
1
x
2
n
P
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
-
1
+
x
2
n
)
x
1
P
=
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
-
1
+
x
2
n
y
P
.
From (4), we can get x
y
-
1
P
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
-
1
+
x
2
n
)
P.
(2)n-LDH ⇐ DCDH. Suppose that there exists an oracle which can solve the the DCDH problem with nonnegligible probability. We will prove that the oracle can help us to solve the n-LDH problem with nonnegligible probability, too.
For anyn-LDH tuple in (2), we input (
x
1
x
n
+
2
P
,
x
1
P
)
,
(
x
1
x
n
+
3
P
,
x
1
P
)
,
…
,
(
x
1
x
2
n
P
,
x
1
P
), and (
x
2
x
n
+
1
P
,
x
2
P
) into the oracle. Then the oracle outputs x
n
+
2
P
,
x
n
+
3
P
,
…
,
x
2
n
P, and x
n
+
1
P, respectively.
Finally, we can computex
n
+
1
P
+
x
n
+
2
P
+
⋯
+
x
2
n
P
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P to solve the n-LDH problem.We use a way similar to [22] to prove the n-DLDH problem being hard. In the generic model, elements of G
1, G
2, and G
T are encoded as unique random strings, where G
1 and G
2 are additive groups and G
T is a multiplicative group. There is a bilinear pairing function e
:
G
1
×
G
2
→
G
T. Let S
1, S
2, and S
T be the sets of strings. The opaque encoding of the elements of G
1 is modeled as an injective function ζ
1
:
Z
q
→
S
1, where S
1
⊂
{
0,1
}
*, which maps all a
∈
Z
q to the string representation ζ
1
(
a
) of a
P
∈
G
1. Analogous mapping ζ
2
:
Z
q
→
S
2 and ζ
T
:
Z
q
→
S
T map all a
∈
Z
q to the string representation ζ
2
(
a
) of a
P
′
∈
G
2 and ζ
T
(
a
) of g
a
∈
G
T, where g
=
e
(
P
,
P
′
).


## 4.3.  The Decisionaln-Linear Diffie-Hellman (n-DLDH) Problem

Theorem 3.
LetA be an algorithm that solves the n-DLDH problem in the generic bilinear group model with at most q
k oracle queries. Let x
i’s, x
n
+
j’s, and z
∈
Z
q be chosen at random, where 1
≤
i, j
≤
n, and n
≥
2, ζ
1, ζ
2, and ζ
T are random encoding functions for G
1, G
2, and G
T, and b
∈
{
0,1
} is a random bit. Let w
b
=
z and w
1
-
b
=
∑
j
=
1
n
x
n
+
j
mod
q. The probability is
(5)
Pr
A
(
ζ
1
,
ζ
2
,
ζ
T
;
1
,
x
i
ʼ
s
,
x
i
x
n
+
j
ʼ
s
,
w
0
,
w
1
)
=
b
:
∀
i
,
j
,
x
i
,
x
n
+
j
∈
Z
q
*
,
1
≤
i
,
j
≤
n
,
i
≠
j
,
n
≥
2
,
b
∈
{
0,1
}
=
1
2
+
2
n
2
+
3
+
q
k
2
q
.Proof.
B plays the following game with A. B maintains the lists L
1
=
{
(
F
1
,
s
,
ζ
1
,
s
)
:
s
=
0,1
,
2
,
…
,
τ
1
-
1
}, L
2
=
{
(
F
2
,
t
,
ζ
2
,
t
)
:
t
=
0,1
,
2
,
…
,
τ
2
-
1
}, and L
T
=
{
(
F
T
,
u
,
ζ
T
,
u
)
:
t
=
0,1
,
2
,
…
,
τ
T
-
1
}. Let X
i’s, X
i
X
n
+
j’s, W
0, and W
1 (∀
i
,
j
,
1
≤
i, j
≤
n, i
≠
j) be indeterminate. All F
1
,
s’s, F
2
,
t’s, and F
T
,
u’s ∈
Z
q
[
X
i’s, X
i
X
n
+
j’s, W
0
,
W
1
] are polynomials and ζ
1
,
s’s, ζ
2
,
t’s, ζ
T
,
u’s ∈
{
0,1
}
* are distinct strings. At the beginning of the game, B sets F
1,0
=
1, F
1,1
=
X
1, F
1,2
=
X
2
,
…
,
F
1
,
n
=
X
n, F
1
,
n
2
+
1
=
W
0, F
1
,
n
2
+
2
=
W
1, F
2,0
=
1, F
T
,
0
=
1, and the following polynomials: [(
⊥
,
F
1
,
n
+
1
=
X
2
X
n
+
1
,
…
,
F
1,2
n
-
2
=
X
n
-
1
X
n
+
1
,
F
1,2
n
-
1
=
X
n
X
n
+
1
), (
F
1,2
n

=

X
1
X
n
+
2
,

⊥
,
…
,
F
1,3
n
-
3
=
X
n
-
1
X
n
+
2
,
F
1,3
n
-
2
=
X
n
X
n
+
2
),…
,
(
F
1
,
n
2
-
2
n
+
3
=
X
1
X
2
n
-
1
,
F
1
,
n
2
-
2
n
+
4
=
X
2
X
2
n
-
1
,
…
,
⊥
,
F
1
,
n
2
-
n
+
1
=
X
n
X
2
n
-
1
), (
F
1
,
n
2
-
n
+
2
=
X
1
X
2
n
,
F
1
,
n
2
-
n
+
3
=
X
2
X
2
n
,
…
,
F
1
,
n
2
=
X
n
-
1
X
2
n
,
,
⊥
)], where the symbol “⊥” means emptiness and B gives A the distinct strings ζ
1,0
,
ζ
1,1
,
…
,
ζ
1
,
n
2
+
2, ζ
2,0, and ζ
T
,
0. In the initial list index, the numbers of the records in L
1, L
2, and L
T are τ
1
=
n
2
+
3, τ
2
=
1, and τ
T
=
1, respectively, where τ
=
τ
1
+
τ
2
+
τ
T
=
n
2
+
5. At any step in the game, A can make the group and pairing queries. B performs and responds to A as follows.
Group Action.
A gives B two operands ζ
1
,
s, ζ
1
,
t and a sign bit, where 0
≤
s, t
<
τ
1. B sets F
1
,
τ
1
←
F
1
,
s
±
F
1
,
t. If F
1
,
τ
1
=
F
1
,
l for some l
<
τ
1, B sets ζ
1
,
τ
1
←
ζ
1
,
l. Otherwise, B sets ζ
1
,
τ
1 to be a string in {
0,1
}
* distinct from ζ
1,0
,
ζ
1,1
,
…
,
ζ
1
,
τ
1
-
1. Finally, B adds (
F
1
,
τ
1
,
ζ
1
,
τ
) to the list L
1, gives ζ
1
,
τ
1 to A, and sets τ
1
←
τ
1
+
1. The group action queries in G
2 and G
T are simulated similarly.
Pairing.
A gives B two operands ζ
1
,
s and ζ
1
,
t with 0
≤
s
<
τ
1 and 0
≤
t
<
τ
2. B sets the product F
T
,
τ
T
←
F
1
,
s
F
2
,
t. If F
T
,
τ
T
=
F
T
,
l for some l
<
τ
T, B sets ζ
T
,
τ
T
←
ζ
T
,
l. Otherwise, B sets ζ
T
,
τ
T to be a string in {
0,1
}
* distinct from ζ
T
,
0
,
ζ
T
,
1
,
…
,
ζ
T
,
τ
T
-
1. Finally, B adds (
F
T
,
τ
T
,
ζ
T
,
τ
T
) to the list L
T, gives ζ
T
,
τ
T to A, and sets τ
T
←
τ
T
+
1.Consider the operation thatB performs: (
1
)
B adds/subtracts all polynomials in the list L
1, L
2, and L
T by any A’s query. 2  B produces any of two polynomials in L
1 and L
2 to generate a new polynomial in L
T. For any variant X
n
+
j, it occurs within the monomials X
1
X
n
+
j
,
X
2
X
n
+
j
,
…
,
X
n
+
j
-
1
X
n
+
j
,
X
n
+
j
+
1
X
n
+
j
,
…
,
X
2
n
X
n
+
j in L
1 and L
T lists and it occurs no monomial in L
2 list. Therefore, B cannot produce any polynomial that contains the monomial c
X
n
+
j’s in G
1 or G
2 and the monomial F
2
,
t
X
n
+
j’s in G
T for any coefficient c
≠
0 and any nonzero monomial F
2
,
t in L
2 in the available operations.After at mostq queries, A terminates and returns a guess b
^
∈
{
0,1
}. The distinct values of operands provide no information to A because they are random bit strings. Therefore, the probability that A wins the game in the generic model is 1
/
2.However, whenB randomly chooses x
i’s, x
n
+
j’s, and z
∈
Z, sets w
b
=
∑
j
=
1
n
x
n
+
j and w
1
-
b
=
z, and assigns X
1
←
x
1
,
X
2
←
x
2
,
…
,
X
2
n
←
x
2
n
,
W
b
←
w
b, and W
1
-
b
←
w
1
-
b, a nontrivial equality relation may occur and give A some information that is not revealed in the generic model; that is, for some F
1
,
s
≠
F
1
,
t (and F
T
,
s
≠
F
T
,
t, resp.) and s
,
t
<
τ
1 (and s
,
t
<
τ
T, resp.), F
1
,
s
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1) = F
1
,
t
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1) (and F
T
,
s
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1) = F
T
,
t
(
x
i’s,
x
i
x
n
+
j’s,
w
0
,
w
1), resp.).The probability of the occurrence is computed according to the following lemma.Lemma 4 (see [32]).
Letq be prime and let t
≥
1. Let F
(
X
1
,
X
2
,
…
,
X
k
)
∈
Z
/
q
t
[
X
1
,
X
2
,
…
,
X
k
] be a nonzero polynomial of total degree d. Then for random x
1
,
x
2
,
…
,
x
k
∈
Z
/
q
t, the probability that F
(
x
1
,
x
2
,
…
,
x
k
)
=
0 is at most d
/
q.By Lemma4, all polynomials in the L
1 have degree at most 2, so that, for some s
,
t and F
1
,
s
≠
F
1
,
t, the probability of F
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1
) = F
1
,
s
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1
)
-
F
1
,
t
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1
)
=
0 is at most 2
/
q. The degree of polynomials in the L
2 is 0. All polynomials in the L
T have degree at most 2, so that, for some s
,
t and F
T
,
s
≠
F
T
,
t, the probability of F
′
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1
) = F
T
,
s
(
x
i’s,
x
i
x
n
+
j’s,
w
0
,
w
1
)
-
F
T
,
t
(
x
i’s, x
i
x
n
+
j’s, w
0
,
w
1
)
=
0 is at most 2
/
q. Therefore, A wins the game with the probability ɛ
≤
1
/
2
+
τ
1
2
2
/
q
+
τ
T
2
2
/
q. Since τ
1
+
τ
T
≤
n
2
+
4
+
q
k, we have ɛ
≤
1
/
2
+
n
2
+
4
+
q
k
2
/
q, where the advantage is not greater than O
(
q
k
2
/
q
).


## 5. Our Key Agreement Schemes

In this section, we propose two conference key agreement schemes. The first scheme is designed for the situation where the users who register with a single TA (single domain) want to negotiate a session conference key. Furthermore, the second scheme makes it possible for the users in distinct groups who register with different TAs (interdomain) to negotiate a session conference key. In addition, we will prove the security of the two proposed schemes in Section6 and compare them with others in Section 7.


### 5.1. The Proposed Scheme in Single TA

Setup. TA inputs a security parameter κ into a setup algorithm which returns groups G
1, G
2, and G
T (G
1
≠
G
2) of prime order q with q
∈
{
0,1
}
κ, a suitable bilinear mapping e
:
G
1
×
G
2
→
G
T, generators P
∈
G
1, P
′
∈
G
2, and three hash functions H
:
{
0,1
}
*
→
G
1
,
H
1
:
G
1
→
{
0,1
}
l, H
2
:
G
1
×
{
0,1
}
*
→
{
0,1
}
l, and H
3
:
G
1
→
{
0,1
}
l where l is the output length of the hash functions. TA randomly generates a long-term private key s
∈
Z
q
* and the public key (
s
P
,
s
P
′
) and then publishes 〈
q
,
e
,
G
1
,
G
2
,
G
T
,
P
,
s
P
,
P
′
,
s
P
′
,
H
,
H
1
,
H
2
,
H
3
〉.Extract. When a user U
i registers a public identity (ID), such as an email address, with TA, TA will check whether the ID belongs to the user. If true, TA issues a long-term private key s
Q
i to U
i where Q
i
=
H(TA’s ID∥
U
i’s ID) is U
i’s public key.Conference Key Agreement. Suppose that there are n legal users U
1
,
U
2
,
…, and U
n who want to negotiate a conference key. Our conference key agreement scheme contains three rounds described as follows.Round 1: every userU
i
(
1
≤
i
≤
n
) randomly picks an integer r
i
∈
Z
q
* as a blinding factor, and then U
i computes b
i
=
r
i
-
1
P and broadcasts b
i to all users who join this session. The flow is shown in Algorithm 1.Algorithm 1:Round 1 of the first conference key protocol.
Round
1
U
i
_       U
1
,
U
2
,
…
,
U
i
-
1
,
U
i
+
1
,
…
,
U
n
_
Pick r
i
∈
R
Z
q
*
Compute b
i
=
r
i
-
1
P
Broadcast
b
i
→
b
1
,
b
2
,
…
,
b
i
-
1
,
b
i
+
1
,
…
,
b
n
←Round 2: afterU
i receives all b
j’s (
1
≤
j
≤
n, j
≠
i
), she/he randomly picks an integer k
i
∈
Z
q
* as an ephemeral key and computes B
i
=
(
k
i
b
1
,
k
i
b
2
,
…
,
k
i
b
i
-
1
,
⊥
,
k
i
b
i
+
1
,
…
,
k
i
b
n
), and then U
i broadcasts B
i. The flow is shown in Algorithm 2.Algorithm 2:Round 2 of the first conference key protocol.
Round
2
U
i
_       U
1
,
U
2
,
…
,
U
i
-
1
,
U
i
+
1
,
…
,
U
n
_
Pick k
i
∈
R
Z
q
*
Compute
k
i
b
j
=
k
i
r
j
-
1
P  (
1
≤
j
≤
n
,
j
≠
i
)
B
i
=
(
k
i
b
1
,
k
i
b
2
,
…
,
k
i
b
i
-
1
,
⊥
,
k
i
b
i
+
1
,
…
,
k
i
b
n
),
Broadcast
B
i
→
B
1
,
B
2
,
…
,
B
i
-
1
,
B
i
+
1
,
…
,
B
n
←Round 3: for allB
i’s in Round 2, we can rearrange them as shown in (7). When receiving B
j’s, U
i only stores k
j
b
i
(
1
≤
j
≤
n
,
j
≠
i
) and drops other useless information k
j
b
t’s (
1
≤
j
≤
n
,
1
≤
t
≤
n
,
t
≠
i
). For example, U
1 stores column 1 and U
2 stores column 2 in (7). Then U
i computes K as follows:
(6)
K
=
r
i
∑
j
=
1
n
‍
k
j
b
i
=
r
i
·
(
k
1
r
i
-
1
+
k
2
r
i
-
1
+
⋯
+
k
i
r
i
-
1
+
⋯
+
k
n
r
i
-
1
)
P
=
(
k
1
+
k
2
+
⋯
+
k
i
+
⋯
+
k
n
)
P
.AllB
i’s in Round 2
(7)
U
1
U
2
…
U
i
…
U
n
B
1
⊥
k
1
r
2
-
1
P
…
k
1
r
i
-
1
P
…
k
1
r
n
-
1
P
B
2
k
2
r
1
-
1
P
⊥
…
k
2
r
i
-
1
P
…
k
2
r
n
-
1
P
⋮
⋮
⋮
⋱
⋮
⋮
⋮
B
i
k
i
r
1
-
1
P
k
i
r
2
-
1
P
…
⊥
…
k
i
r
n
-
1
P
⋮
⋮
⋮
⋮
⋮
⋱
⋮
B
n
k
n
r
1
-
1
P
k
n
r
2
-
1
P
…
k
n
r
i
-
1
P
…
⊥
U
i computes α
=
H
1
(
K
), T
i
=
α
s
Q
i
+
r
i
-
1
s
P, and β
i
=
H
2
(
T
i
,
α
), and then she/he broadcasts (
T
i
,
β
i
). When U
i receives all (
T
j
,
β
j
)’s (
1
≤
j
≤
n
,
j
≠
i
), she/he first verifies all β
j’s by checking if H
2
(
T
j
,
α
)
=
β
j for each j. If they are true, U
i randomly chooses a
1
,
a
2
,
…
,
a
n
∈
Z
q
*, computes V
i
=
e
(
∑
i
=
1
n
‍
a
i
b
i
+
α
∑
i
=
1
n
‍
a
i
Q
i
,
s
P
′
), and verifies whether V
i
=
e
(
∑
i
=
1
n
‍
a
i
T
i
,
P
′
) or not. If true, U
i accepts K and computes the session conference key SCK
=
H
3
(
K
). Algorithm 3 illustrates the flow in Round 3.Algorithm 3:Round 3 of the first conference key protocol.
Round
3
U
i
_       U
1
,
U
2
,
…
,
U
i
-
1
,
U
i
+
1
,
…
,
U
n
_
Compute
K
=
r
i
∑
j
=
1
n
k
j
b
i
=
(
k
1
+
k
2
+
⋯
+
k
i
+
⋯
+
k
n
)
P
α
=
H
1
(
K
)
T
i
=
α
s
Q
i
+
r
i
-
1
s
P
β
i
=
H
2
(
T
i
,
α
)
Broadcast
(
T
i
,
β
i
)
→
(
T
1
,
β
1
)
,
(
T
2
,
β
2
)
,
…
,
(
T
i
-
1
,
β
i
-
1
)
,
(
T
i
+
1
,
β
i
+
1
)
,
…
,
(
T
n
,
β
n
)
←
Verify:
β
1
,
β
2
,
…
,
β
i
-
1
,
β
i
+
1
,
…
,
β
n
V
i
=
e
(
∑
i
=
1
n
a
j
b
i
+
α
∑
i
=
1
n
a
i
Q
i
,
s
P
′
)
?
=
e
(
∑
i
=
1
n
a
i
T
i
,
P
′
)
Compute session conference key SCK =H
3
(
K
)


### 5.2. The Proposed Scheme in Distinct TAs

Our single domain conference key agreement scheme can be extended to an interdomain conference key agreement scheme. Interdomain means that there are distinct domains with different TAs’, respectively. In this subsection, we present our interdomain conference key scheme. Assume that there arem Trusted Authorities T
A
1
,
T
A
2
,
…, and T
A
m and m user groups G
1
,
G
2
,
…, and G
m who register with the m distinct TAs, respectively. In the proposed scheme, the users in m different groups can negotiate a session conference key SCK via the following process.Setup.
TA
i, i
∈
{
1,2
,
…
,
m
}, inputs a security parameter κ into a setup algorithm which returns two groups G
1, G
2, and G
T (G
1
≠
G
2) of prime order q
∈
{
0,1
}
κ, a suitable bilinear mapping e
:
G
1
×
G
2
→
G
T, generators P
∈
G
1, P
′
∈
G
2, and three hash functions H
:
{
0,1
}
*
→
G
1, H
1
:
G
1
→
{
0,1
}
l, H
2
:
G
1
×
{
0,1
}
*
→
{
0,1
}
l, and H
3
:
G
1
→
{
0,1
}
l where l is the output length of the hash functions. TA
i randomly generates a long-term key s
i
∈
Z
q
* and public key (
s
i
P
,
s
i
P
′
) and then publishes 〈
q
,
e
,
G
1
,
G
2
,
G
T
,
P
,
s
i
P
,
P
′
,
s
i
P
′
,
H
,
H
1
,
H
2
,
H
3
〉.Extract. When a user U
j in group i registers a public ID with TA
i, TA
i will check whether the ID belongs to the user. If true, TA
i issues private key s
i
Q
i
,
j to the user, where Q
i
,
j
=
H(TA
i’s ID∥
U
i
,
j’s ID) is the public key and U
i
,
j denotes user U
j who has registered with TA
i.Interdomain Conference Key Agreement. Suppose that users in m distinct domains or groups want to negotiate a conference key. Let n
h
(
1
≤
h
≤
m
) be the number of users in the hth domain and N be the number of the total users (
N
=
n
1
+
n
2
+
⋯
+
n
m
). Our interdomain conference key agreement protocol contains three rounds where Round 1 and Round 2 are similar to those of the proposed single domain conference key protocol.Round 1: every userU
i
,
j randomly picks an integer r
i
,
j
∈
Z
q
* and then broadcasts b
i
,
j
=
(
r
i
,
j
)
-
1
P to the users who join this session.Round 2: after receivingb
h
,
l’s (
1
≤
h
≤
m
,
1
≤
l
≤
n
h
,
h
≠
i
,
l
≠
j
), U
i
,
j computes k
i
,
j
b
h
,
l, where k
i
,
j
∈
R
Z
q
* is U
i
,
j’s ephemeral key, and broadcasts B
i
,
j

=

(
k
i
,
j
b
1,1
,
k
i
,
j
b
1,2
,
,
…
,

k
i
,
j
b
1
,
n
1
,
…
,
k
i
,
j
b
i
,
1
,

…
,
k
i
,
j
b
i
,
j
-
1
,
⊥
,
k
i
,
j
b
i
,
j
+
1
,
…
,
k
i
,
j
b
i
,
n
i
,
…
,
k
i
,
j
b
m
,
1
,
…
,
k
i
,
j
b
m
,
n
m
).Round 3: when receivingB
h
,
l’s, U
i
,
j only stores k
h
,
l
b
i
,
j’s (
1
≤
h
≤
m
,
1
≤
l
≤
n
h
,
h
≠
i, and l
≠
j
) and drops other useless information k
h
,
l
b
u
,
v’s (
1
≤
h
≤
m
,
1
≤
l
≤
n
h
,
1
≤
u
≤
m
,
1
≤
v
≤
n
u
,
u
≠
i, and v
≠
j
). Then U
i
,
j computes every domain’s key K
h as follows:
(8)
K
h
=
r
i
,
j
∑
t
=
1
n
h
‍
k
h
,
t
b
i
,
j
=
r
i
,
j
(
k
h
,
1
r
i
,
j
-
1
+
k
h
,
2
r
i
,
j
-
1
+
⋯
+
k
h
,
n
h
r
i
,
j
-
1
)
P
=
(
k
h
,
1
+
k
h
,
2
+
⋯
+
k
h
,
n
h
)
P
.U
i
,
j computes K
=
∑
h
=
1
m
‍
K
h, α
=
H
1
(
K
), T
i
,
j
=
α
s
i
Q
i
,
j
+
r
i
,
j
-
1
s
i
P, and β
i
,
j
=
H
2
(
T
i
,
j
,
α
), and then she/he broadcasts (
T
i
,
j
,
β
i
,
j
). When U
i
,
j receives all messages, U
i
,
j first verifies all β
h
,
l’s by examining if H
2
(
T
h
,
l
,
α
)
=
β
h
,
l for each h and l
(
1
≤
h
≤
m
,
1
≤
l
≤
n
h
,
h
≠
i, and l
≠
j
). If all β
h
,
l’s are correct, U
i
,
j randomly chooses N integers a
h
,
l’s, where each a
h
,
l
∈
Z
q
*, computes V
h
,
l
=
∏
h
=
1
m
‍
e
(
∑
l
=
1
n
h
‍
a
h
,
l
b
h
,
l
+
α
∑
l
=
1
n
h
‍
a
h
,
l
Q
h
,
l
,
s
h
P
′
), and checks if V
h
,
l
=
e
(
∑
h
=
1
m
‍
∑
l
=
1
n
h
‍
a
h
,
l
T
h
,
l
,
P
′
). If it is true, U
i
,
j accepts K and computes the session conference key SCK
=
H
3
(
K
).


## 5.1. The Proposed Scheme in Single TA

Setup. TA inputs a security parameter κ into a setup algorithm which returns groups G
1, G
2, and G
T (G
1
≠
G
2) of prime order q with q
∈
{
0,1
}
κ, a suitable bilinear mapping e
:
G
1
×
G
2
→
G
T, generators P
∈
G
1, P
′
∈
G
2, and three hash functions H
:
{
0,1
}
*
→
G
1
,
H
1
:
G
1
→
{
0,1
}
l, H
2
:
G
1
×
{
0,1
}
*
→
{
0,1
}
l, and H
3
:
G
1
→
{
0,1
}
l where l is the output length of the hash functions. TA randomly generates a long-term private key s
∈
Z
q
* and the public key (
s
P
,
s
P
′
) and then publishes 〈
q
,
e
,
G
1
,
G
2
,
G
T
,
P
,
s
P
,
P
′
,
s
P
′
,
H
,
H
1
,
H
2
,
H
3
〉.Extract. When a user U
i registers a public identity (ID), such as an email address, with TA, TA will check whether the ID belongs to the user. If true, TA issues a long-term private key s
Q
i to U
i where Q
i
=
H(TA’s ID∥
U
i’s ID) is U
i’s public key.Conference Key Agreement. Suppose that there are n legal users U
1
,
U
2
,
…, and U
n who want to negotiate a conference key. Our conference key agreement scheme contains three rounds described as follows.Round 1: every userU
i
(
1
≤
i
≤
n
) randomly picks an integer r
i
∈
Z
q
* as a blinding factor, and then U
i computes b
i
=
r
i
-
1
P and broadcasts b
i to all users who join this session. The flow is shown in Algorithm 1.Algorithm 1:Round 1 of the first conference key protocol.
Round
1
U
i
_       U
1
,
U
2
,
…
,
U
i
-
1
,
U
i
+
1
,
…
,
U
n
_
Pick r
i
∈
R
Z
q
*
Compute b
i
=
r
i
-
1
P
Broadcast
b
i
→
b
1
,
b
2
,
…
,
b
i
-
1
,
b
i
+
1
,
…
,
b
n
←Round 2: afterU
i receives all b
j’s (
1
≤
j
≤
n, j
≠
i
), she/he randomly picks an integer k
i
∈
Z
q
* as an ephemeral key and computes B
i
=
(
k
i
b
1
,
k
i
b
2
,
…
,
k
i
b
i
-
1
,
⊥
,
k
i
b
i
+
1
,
…
,
k
i
b
n
), and then U
i broadcasts B
i. The flow is shown in Algorithm 2.Algorithm 2:Round 2 of the first conference key protocol.
Round
2
U
i
_       U
1
,
U
2
,
…
,
U
i
-
1
,
U
i
+
1
,
…
,
U
n
_
Pick k
i
∈
R
Z
q
*
Compute
k
i
b
j
=
k
i
r
j
-
1
P  (
1
≤
j
≤
n
,
j
≠
i
)
B
i
=
(
k
i
b
1
,
k
i
b
2
,
…
,
k
i
b
i
-
1
,
⊥
,
k
i
b
i
+
1
,
…
,
k
i
b
n
),
Broadcast
B
i
→
B
1
,
B
2
,
…
,
B
i
-
1
,
B
i
+
1
,
…
,
B
n
←Round 3: for allB
i’s in Round 2, we can rearrange them as shown in (7). When receiving B
j’s, U
i only stores k
j
b
i
(
1
≤
j
≤
n
,
j
≠
i
) and drops other useless information k
j
b
t’s (
1
≤
j
≤
n
,
1
≤
t
≤
n
,
t
≠
i
). For example, U
1 stores column 1 and U
2 stores column 2 in (7). Then U
i computes K as follows:
(6)
K
=
r
i
∑
j
=
1
n
‍
k
j
b
i
=
r
i
·
(
k
1
r
i
-
1
+
k
2
r
i
-
1
+
⋯
+
k
i
r
i
-
1
+
⋯
+
k
n
r
i
-
1
)
P
=
(
k
1
+
k
2
+
⋯
+
k
i
+
⋯
+
k
n
)
P
.AllB
i’s in Round 2
(7)
U
1
U
2
…
U
i
…
U
n
B
1
⊥
k
1
r
2
-
1
P
…
k
1
r
i
-
1
P
…
k
1
r
n
-
1
P
B
2
k
2
r
1
-
1
P
⊥
…
k
2
r
i
-
1
P
…
k
2
r
n
-
1
P
⋮
⋮
⋮
⋱
⋮
⋮
⋮
B
i
k
i
r
1
-
1
P
k
i
r
2
-
1
P
…
⊥
…
k
i
r
n
-
1
P
⋮
⋮
⋮
⋮
⋮
⋱
⋮
B
n
k
n
r
1
-
1
P
k
n
r
2
-
1
P
…
k
n
r
i
-
1
P
…
⊥
U
i computes α
=
H
1
(
K
), T
i
=
α
s
Q
i
+
r
i
-
1
s
P, and β
i
=
H
2
(
T
i
,
α
), and then she/he broadcasts (
T
i
,
β
i
). When U
i receives all (
T
j
,
β
j
)’s (
1
≤
j
≤
n
,
j
≠
i
), she/he first verifies all β
j’s by checking if H
2
(
T
j
,
α
)
=
β
j for each j. If they are true, U
i randomly chooses a
1
,
a
2
,
…
,
a
n
∈
Z
q
*, computes V
i
=
e
(
∑
i
=
1
n
‍
a
i
b
i
+
α
∑
i
=
1
n
‍
a
i
Q
i
,
s
P
′
), and verifies whether V
i
=
e
(
∑
i
=
1
n
‍
a
i
T
i
,
P
′
) or not. If true, U
i accepts K and computes the session conference key SCK
=
H
3
(
K
). Algorithm 3 illustrates the flow in Round 3.Algorithm 3:Round 3 of the first conference key protocol.
Round
3
U
i
_       U
1
,
U
2
,
…
,
U
i
-
1
,
U
i
+
1
,
…
,
U
n
_
Compute
K
=
r
i
∑
j
=
1
n
k
j
b
i
=
(
k
1
+
k
2
+
⋯
+
k
i
+
⋯
+
k
n
)
P
α
=
H
1
(
K
)
T
i
=
α
s
Q
i
+
r
i
-
1
s
P
β
i
=
H
2
(
T
i
,
α
)
Broadcast
(
T
i
,
β
i
)
→
(
T
1
,
β
1
)
,
(
T
2
,
β
2
)
,
…
,
(
T
i
-
1
,
β
i
-
1
)
,
(
T
i
+
1
,
β
i
+
1
)
,
…
,
(
T
n
,
β
n
)
←
Verify:
β
1
,
β
2
,
…
,
β
i
-
1
,
β
i
+
1
,
…
,
β
n
V
i
=
e
(
∑
i
=
1
n
a
j
b
i
+
α
∑
i
=
1
n
a
i
Q
i
,
s
P
′
)
?
=
e
(
∑
i
=
1
n
a
i
T
i
,
P
′
)
Compute session conference key SCK =H
3
(
K
)


## 5.2. The Proposed Scheme in Distinct TAs

Our single domain conference key agreement scheme can be extended to an interdomain conference key agreement scheme. Interdomain means that there are distinct domains with different TAs’, respectively. In this subsection, we present our interdomain conference key scheme. Assume that there arem Trusted Authorities T
A
1
,
T
A
2
,
…, and T
A
m and m user groups G
1
,
G
2
,
…, and G
m who register with the m distinct TAs, respectively. In the proposed scheme, the users in m different groups can negotiate a session conference key SCK via the following process.Setup.
TA
i, i
∈
{
1,2
,
…
,
m
}, inputs a security parameter κ into a setup algorithm which returns two groups G
1, G
2, and G
T (G
1
≠
G
2) of prime order q
∈
{
0,1
}
κ, a suitable bilinear mapping e
:
G
1
×
G
2
→
G
T, generators P
∈
G
1, P
′
∈
G
2, and three hash functions H
:
{
0,1
}
*
→
G
1, H
1
:
G
1
→
{
0,1
}
l, H
2
:
G
1
×
{
0,1
}
*
→
{
0,1
}
l, and H
3
:
G
1
→
{
0,1
}
l where l is the output length of the hash functions. TA
i randomly generates a long-term key s
i
∈
Z
q
* and public key (
s
i
P
,
s
i
P
′
) and then publishes 〈
q
,
e
,
G
1
,
G
2
,
G
T
,
P
,
s
i
P
,
P
′
,
s
i
P
′
,
H
,
H
1
,
H
2
,
H
3
〉.Extract. When a user U
j in group i registers a public ID with TA
i, TA
i will check whether the ID belongs to the user. If true, TA
i issues private key s
i
Q
i
,
j to the user, where Q
i
,
j
=
H(TA
i’s ID∥
U
i
,
j’s ID) is the public key and U
i
,
j denotes user U
j who has registered with TA
i.Interdomain Conference Key Agreement. Suppose that users in m distinct domains or groups want to negotiate a conference key. Let n
h
(
1
≤
h
≤
m
) be the number of users in the hth domain and N be the number of the total users (
N
=
n
1
+
n
2
+
⋯
+
n
m
). Our interdomain conference key agreement protocol contains three rounds where Round 1 and Round 2 are similar to those of the proposed single domain conference key protocol.Round 1: every userU
i
,
j randomly picks an integer r
i
,
j
∈
Z
q
* and then broadcasts b
i
,
j
=
(
r
i
,
j
)
-
1
P to the users who join this session.Round 2: after receivingb
h
,
l’s (
1
≤
h
≤
m
,
1
≤
l
≤
n
h
,
h
≠
i
,
l
≠
j
), U
i
,
j computes k
i
,
j
b
h
,
l, where k
i
,
j
∈
R
Z
q
* is U
i
,
j’s ephemeral key, and broadcasts B
i
,
j

=

(
k
i
,
j
b
1,1
,
k
i
,
j
b
1,2
,
,
…
,

k
i
,
j
b
1
,
n
1
,
…
,
k
i
,
j
b
i
,
1
,

…
,
k
i
,
j
b
i
,
j
-
1
,
⊥
,
k
i
,
j
b
i
,
j
+
1
,
…
,
k
i
,
j
b
i
,
n
i
,
…
,
k
i
,
j
b
m
,
1
,
…
,
k
i
,
j
b
m
,
n
m
).Round 3: when receivingB
h
,
l’s, U
i
,
j only stores k
h
,
l
b
i
,
j’s (
1
≤
h
≤
m
,
1
≤
l
≤
n
h
,
h
≠
i, and l
≠
j
) and drops other useless information k
h
,
l
b
u
,
v’s (
1
≤
h
≤
m
,
1
≤
l
≤
n
h
,
1
≤
u
≤
m
,
1
≤
v
≤
n
u
,
u
≠
i, and v
≠
j
). Then U
i
,
j computes every domain’s key K
h as follows:
(8)
K
h
=
r
i
,
j
∑
t
=
1
n
h
‍
k
h
,
t
b
i
,
j
=
r
i
,
j
(
k
h
,
1
r
i
,
j
-
1
+
k
h
,
2
r
i
,
j
-
1
+
⋯
+
k
h
,
n
h
r
i
,
j
-
1
)
P
=
(
k
h
,
1
+
k
h
,
2
+
⋯
+
k
h
,
n
h
)
P
.U
i
,
j computes K
=
∑
h
=
1
m
‍
K
h, α
=
H
1
(
K
), T
i
,
j
=
α
s
i
Q
i
,
j
+
r
i
,
j
-
1
s
i
P, and β
i
,
j
=
H
2
(
T
i
,
j
,
α
), and then she/he broadcasts (
T
i
,
j
,
β
i
,
j
). When U
i
,
j receives all messages, U
i
,
j first verifies all β
h
,
l’s by examining if H
2
(
T
h
,
l
,
α
)
=
β
h
,
l for each h and l
(
1
≤
h
≤
m
,
1
≤
l
≤
n
h
,
h
≠
i, and l
≠
j
). If all β
h
,
l’s are correct, U
i
,
j randomly chooses N integers a
h
,
l’s, where each a
h
,
l
∈
Z
q
*, computes V
h
,
l
=
∏
h
=
1
m
‍
e
(
∑
l
=
1
n
h
‍
a
h
,
l
b
h
,
l
+
α
∑
l
=
1
n
h
‍
a
h
,
l
Q
h
,
l
,
s
h
P
′
), and checks if V
h
,
l
=
e
(
∑
h
=
1
m
‍
∑
l
=
1
n
h
‍
a
h
,
l
T
h
,
l
,
P
′
). If it is true, U
i
,
j accepts K and computes the session conference key SCK
=
H
3
(
K
).


## 6. Security Proof

Bellare-Rogaway random oracle model [12, 33], which was extended by Blake-Wilson et al. [34], is suitably modified and adapted in analyzing the security of key agreement protocols like those in the literatures [9, 13]. In this section, we modify Bellare-Rogaway random oracle model and adopt the similar concepts and definitions in [8] to set our security game.Definition 5 (game environment).
Let adversaryA be a probabilistic polynomial time Turing machine and B a simulator to simulate this game for A. Let I
=
{
U
1
,
U
2
,
…
,
U
q
} be all users and U the group users who follow our first identity-based conference key (
I
D
C
K
) scheme, where q is the order of G
1 and U
⊆
{
U
1
,
U
2
,
…
,
U
q
}. In the game, we allow A to make the following types of queries. (1)
Execute
(
Π
U
s
): when A makes theExecute query, B simulates U to run the first I
D
C
K protocol Π (Section 5.1) and responds with all public messages (i.e., (
b
i
,
B
i
,
T
i
,
β
i
)’s for all U
i’s ∈
U
) in the sth session.
(2)
Send
(
Π
U
~
s
,
m
): when A makes theSend query with a set of users U
~
⊂
U and a message m which is the set of (
b
j
,
B
j
,
T
j
,
β
j
)’s broadcast by the users in U
~, B simulates all U
i’s ∈
U
-
U
~ to interact with A by broadcasting the messages (
b
i
,
B
i
,
T
i
,
β
i
)’s of U
i’s in the sth session.
(3)
Reveal
(
Π
U
s
): B reveals the session conference key SCK which was held by U in the sth session.
(4)
Corrupt
(
U
i
): B responds with the long-term private key of U
i.
(5)
Test
(
Π
U
s
): when A makes theTest query, B returns the broadcast messages of the sth session and gives the adversary either the session key of the sth session or a random string. A then outputs a bit to decide whether the string is the session key or not.
(6)
H
(
·
): when a participant inputs a string to H, it responds with the hashed value of the string and the hashed value will be recorded.
(7)
H
1
(
·
): when a participant inputs a message m
∈
G
1 to H
1, it responds with the hashed value of m and the hashed value will be recorded, too.
(8)
H
2
(
·
): when a participant inputs (
m
1
,
m
2
), where m
1
∈
G
1 and m
2
∈
{
0,1
}
*, to H
2, it responds with the hashed value of (
m
1
,
m
2
) and the hashed value will be recorded, too.


### 6.1. Correctness

Theorem 6 (correctness).
In the presence of a benign adversaryA, all the parties always accept holding the same session conference key, which is distributed randomly and uniformly in {
0,1
}
κ, where κ is the security parameter.Proof.
Every userU
i can generate a valid message (
b
i
,
B
i
,
T
i
,
β
i
) by following our proposed single domain scheme (Section 5.1), verify the correctness of the message V
i
=
e
(
∑
i
=
1
n
‍
a
i
b
i
+
α
∑
i
=
1
n
‍
a
i
Q
i
,
s
P
′
)
=
e
(
(
a
1
r
1
-
1
+
a
2
r
2
-
1
+
⋯
+
a
n
r
n
-
1
)
P
+
(
α
a
1
Q
1
+
α
a
2
Q
2
+
⋯
+
α
a
n
Q
n
)
,
s
P
′
) = e
(
a
1
(
α
s
Q
1
+
r
1
-
1
s
P
)
+
a
2
(
α
s
Q
2
+
r
2
-
1
s
P
)
+
⋯ + a
n
(
α
s
Q
n
+
r
n
-
1
s
P
)
,
P
′
)
=
e
(
∑
i
=
1
n
‍
a
i
(
α
s
Q
i
+
r
i
-
1
s
P
)
,
P
′
) = e
(
∑
i
=
1
n
‍
a
i
T
i
,
P
′
), and negotiate a common session conference key SCK
=
H
3
(
K
).
In our proposed interdomain scheme (Section5.2), U
i
j can generate a valid message (
b
i
j
,
B
i
j
,
T
i
j
,
β
i
j
) and verify the correctness of the message because
(9)
V
h
,
l
=
∏
h
=
1
m
‍
e
∑
l
=
1
n
h
‍
a
h
,
l
b
h
,
l
+
α
∑
l
=
1
n
h
‍
a
h
,
l
Q
h
,
l
,
s
h
P
′
=
e
(
a
1,1
r
1,1
-
1
+
a
1,2
r
1,2
-
1
+
⋯
+
a
1
,
n
1
r
1
,
n
1
-
1
)
P
+
α
a
1,1
Q
1,1
+
α
a
1,2
Q
1,2
+
⋯
+
α
a
1
,
n
1
Q
1
,
n
1
,
s
1
P
′
·
e
a
2,1
r
2,1
-
1
+
a
2,2
r
2,2
-
1
+
⋯
+
a
2
,
n
2
r
2
,
n
2
-
1
P
+
α
a
2,1
Q
2,1
+
α
a
2,2
Q
2,2
+
⋯
+
α
a
2
,
n
2
Q
2
,
n
2
,
a
2,1
r
2,1
-
1
+
a
2,2
r
2,2
-
1
+
⋯
+
a
2
,
n
2
r
2
,
n
2
-
1
s
2
P
′
·
e
a
m
,
1
r
m
,
1
-
1
+
a
m
,
2
r
m
,
2
-
1
+
⋯
+
a
m
,
n
m
r
m
,
n
m
-
1
P
+
α
a
m
,
1
Q
m
,
1
+
α
a
m
,
2
Q
m
,
2
+
⋯
+
α
a
m
,
n
m
Q
m
,
n
m
,
a
2,1
r
2,1
-
1
+
a
2,2
r
2,2
-
1
+
⋯
+
a
2
,
n
2
r
2
,
n
2
-
1
s
m
P
′
=
e
a
1,1
α
s
1
Q
1,1
+
r
1,1
-
1
s
1
P
+
a
1,2
α
s
1
Q
1,2
+
r
1,2
-
1
s
1
P
+
⋯
+
a
1
,
n
1
α
s
1
Q
1
,
n
1
+
r
1
,
n
1
-
1
s
1
P
,
P
′
·
e
a
2,1
α
s
2
Q
2,1
+
r
2,1
-
1
s
2
P
+
a
2,2
α
s
2
Q
2,2
+
r
2,2
-
1
s
2
P
+
a
2
,
n
2
α
s
2
Q
2
,
n
2
+
r
2
,
n
2
-
1
s
2
P
,
P
′
kkkkkkkkkkkkkkkkkkkkkkk
⋮
·
e
a
m
,
1
α
s
m
Q
m
,
1
+
r
m
,
1
-
1
s
m
P
+
a
m
,
2
α
s
m
Q
m
,
2
+
r
m
,
2
-
1
s
m
P
+
⋯
+
a
m
,
n
m
α
s
m
Q
m
,
n
m
+
r
m
,
n
m
-
1
s
m
P
,
P
′
=
e
∑
h
=
1
m
‍
∑
l
=
1
n
h
‍
a
h
,
l
α
s
h
Q
h
,
l
+
r
h
,
l
-
1
s
h
P
,
P
′
=
e
∑
h
=
1
m
‍
∑
l
=
1
n
h
‍
a
h
,
l
T
h
,
l
,
P
′
.


### 6.2. Known Session Key Security

After given broadcast messages and previous session keys according to theI
D
C
K scheme, an adversary makes a Test query and then receives a random string or a current session key. The adversary can continue asking for broadcast messages and other session keys. If no polynomial-time adversary can decide whether the received string is the current session key or not with nonnegligible advantage, we say that the I
D
C
K scheme satisfies known session key security.Definition 7 (known session key security).
AnI
D
C
K scheme is with known session key security if no polynomial-time adversary can decide if a challenge string is a current session key or a random string under the knowledge of previous session keys with the probability at least (
ɛ
+
1
/
2
) where ɛ, called the advantage, is nonnegligible.Theorem 8.
If an adversaryA can (
t
,
q
E
,
q
S
,
q
C
,
q
R
,
q
H
1
ɛ
)-decide whether the string received from a Test query is the session keySCK held by Π
U
l or not with advantage at least ɛ, where t is the running time and q
E
,
q
S
,
q
C
,
q
R, and q
H
1 are the numbers of makingExecute queries,Send queries,Corrupt queries,Reveal queries, and H
1 queries, respectively, there exists an algorithm which can solve the n-DLDH problem with advantage at least ɛ
′ in time t
′, where
(10)
ɛ
′
≥
ɛ
q
0
,
t
′
≈
t
+
q
E
O
(
t
E
)
+
+
q
S
O
(
t
S
)
+
q
C
O
(
t
C
)
+
q
R
O
(
t
R
)
+
q
H
1
O
(
t
H
1
)
+
O
(
n
2
)
,
q
0
=
q
E
+
q
S
+
q
C
+
q
R
+
q
H, t
E
,
t
S
,
t
C
,
t
R, and t
H
1 are the computing time of the Execute oracle, the Send oracle, the Corrupt oracle, the Reveal oracle, and H
1 oracle, respectively.Proof.
Initially, we construct a simulatorB which prepares the pairing parameters and simulates the system as follows. B randomly picks s
∈
Z
q
* as the system master private key and computes (
s
P
,
s
P
′
) as the system master public key. B computes each user’s long-term public/private key pair (
Q
i
,
s
Q
i
). B allows A to make the following queries (i)
Execute(Π
U
t): A can request U that is a set of users who are chosen by itself to run the key agreement protocol in session t. B follows the protocol (Section 5.1) to produce every (
r
i
,
b
i
,
B
i
,
T
i
,
β
i
,
k
i
), and K
=
∑
U
i
∈
U
k
i
P, and then records them. Finally, B responds every (
b
i
,
B
i
,
T
i
,
β
i
) to A, where U
i
∈
U.
(ii)
Send(Π
U
~
t
,
m): if A actively broadcasts the messages of users U
~
⊂
U to run the key agreement protocol in session t, B follows the protocol (Section 5.1) to produce every (
r
i
,
b
i
,
B
i
,
T
i
,
β
i
,
k
i
) and generate the session conference key in the end of the protocol and then records them. Finally, B responds (
b
i
,
B
i
,
T
i
,
β
i
) to A for each U
i
∈
U
-
U
~.
(iii)
Reveal(Π
U
t
): if Π
U
t does not exist, B creates Π
U
t. B returns the session conference key SCK
=
H
3
(
K
).
(iv)
Corrupt
(
U
i
): B returns (
Q
i
,
s
Q
i
) to A.
(v)
H
1
(
m
): after given m
∈
G
1, B randomly chooses α
∈
{
0,1
}
λ, returns H
1
(
m
)
=
α, and stores (
m
,
α
) in a list, called H
1-list.
(vi)
Test(Π
U
*
l): B guesses that A will send a Test query at the hth session in advance. If A makes aTest query at the lth session, where l
≠
h, B randomly answers “YES” or “NO” to the n-DLDH problem. When A makes aTest query at the lth session, where l
=
h, B checks whether there exists U
i which has been corrupted or not, where U
i
∈
U
* and |
U
*
|
=
n. If one of them has been corrupted, B returns ⊥ and aborts the game. Otherwise, B is given the parameters of an instance of the n-DLDH problem, Z
,
P, and (
x
i
P
,
x
i
x
n
+
j
P
)’s for all i
,
j with 1
≤
i, j
≤
n, and i
≠
j, and takes the advantage of A to decide whether Z
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P or not. B sets the public messages (
b
i
*
,
B
i
*
,
T
i
*
,
β
i
*
) of every user in U
* in the lth session as follows.
First,B forms b
1
*
=
x
1
P, b
2
*
=
x
2
P
,
…
,
b
n
*
=
x
n
P, K
*
=
Z, α
*

=

H
1
(
K
*
), and prepares B
i
*

=

(
x
1
x
n
+
i
P
,
x
2
x
n
+
i
P
,
…
,

x
i
-
1
x
n
+
i
P
,

⊥
,
x
i
+
1
x
n
+
i
P
,
…
,
x
n
x
n
+
i
P
), for each U
i
*
∈
U
*; that is,
(11)
U
1
*
U
2
*
…
U
i
*
…
U
n
*
B
1
*
⊥
x
2
x
n
+
1
P
…
x
i
x
n
+
1
P
…
x
n
x
n
+
1
P
B
2
*
x
1
x
n
+
2
P
⊥
…
x
i
x
n
+
2
P
…
x
n
x
n
+
2
P
⋮
⋮
⋮
⋱
⋮
⋮
⋮
B
i
*
x
1
x
n
+
i
P
x
2
x
n
+
i
P
…
⊥
…
x
n
x
n
+
i
P
⋮
⋮
⋮
⋮
⋮
⋱
⋮
B
n
*
x
1
x
2
n
P
x
2
x
2
n
P
…
x
i
x
2
n
P
…
⊥
B sets T
i
*
=
s
α
*
Q
i
+
s
x
i
P and computes β
i
*
=
H
2
(
T
i
*
,
α
*
) and SCK
*
=
H
3
(
K
*
), where 1
≤
i
≤
n. B responds every (
b
i
*
,
B
i
*
,
T
i
*
,
β
i
*
) and SCK
* to A.
A can continue making the queries ofExecute(Π
U
t),Send(Π
U
t),Reveal(Π
U
t
), andCorrupt
(
U
i
), where t
≠
l and U
i
∉
U
*, until A outputs a bit b. If SC
K
* is the key in session l from A’s point of view, A will output b
=
1; otherwise, b
=
0. If b
=
1, B outputs “YES”; that is, Z
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P; otherwise, B outputs “NO”.
If the adversary can compromise known session key security of the scheme with advantage at leastɛ, B can solve the n-DLDH problem with the advantage at least ɛ
′
≥
1
/
q
0
(
1
/
2
+
ɛ
)
+
1
/
2
q
0
-
1
/
q
0
-
1
/
2
=
ɛ
/
q
0.By Theorem8, we can solve the n-DLDH problem in polynomial time with nonnegligible advantage if there exists a polynomial-time adversary that can break the known session key security with nonnegligible advantage of the proposed single domain key agreement scheme.As for the proof of the interdomain case, we can letn be the number of the total users from all domains; that is, n
=
N. Then, by the proof of Theorem 8, the n-DLDH problem can be solved if the adversary can distinguish the session key from a random string in the proposed interdomain key agreement scheme.


### 6.3. Key-Compromise Impersonation

An adversary is given all users’ long-term keys by making Corrupt queries except the one that he claims to impersonate. If no adversary can output the correct messages of the user with nonnegligible probability, theI
D
C
K scheme can withstand key-compromise impersonation.Definition 9 (key-compromise impersonation).
AnI
D
C
K scheme can withstand key-compromise impersonation if no adversary can have nonnegligible probability to impersonate a user without the long-term private key of the user.Lemma 10 (the forking lemma [35]).
LetT
i
=
α
s
Q
i
+
r
i
-
1
s
P be a valid authentic parameter of user U
i, where s
Q
i is U
i’s private key, s
P is TA’s public key, r
i
-
1 is randomly chosen by U
i, and α is a hashed value of K shared by all users. Let A be a probabilistic polynomial time Turing machine. Given only the public data of the key agreement scheme as input, if A can find, with nonnegligible probability, a valid authentic parameter T
i with α, then, with nonnegligible probability, a replay of this machine, with the same random tape and a different value returned by the random oracle, can output two valid authentic parameters T
i with α and T
i
′ with α
′, such that α
≠
α
′.Lemma 11 (the splitting lemma [36]).
LetA
⊂
X
×
Y such that Pr
⁡
[
(
x
,
y
)
∈
A
]
=
|
A
|
/
(
|
X
|
×
|
Y
|
)
≥
δ. For any ρ
<
δ, define B
=
{
x
∈
X
∣
Pr
⁡
[
(
x
,
y
)
∈
A
]
≥
δ
-
ρ
} and B
¯
=
X
∖
B. Then the following statements hold: (1)
Pr
⁡
[
x
∈
B
]
=
|
B
|
/
|
X
|
≥
ρ,
(2)
∀
x
∈
B
,
Pr
⁡
[
(
x
,
y
)
∈
A
]
≥
δ
-
ρ,
(3)
Pr
⁡
[
x
∈
B
∣
(
x
,
y
)
∈
A
]
≥
ρ
/
δ.Lemma 12.
Assume thate
∑
i
=
1
n
‍
a
i
b
i
+
α
∑
i
=
1
n
‍
a
i
Q
i
,
s
P
′
=
e
∑
i
=
1
n
‍
a
i
T
i
,
P
′. Let E be an event that occurs if there is at least one T
i such that e
a
i
b
i
+
α
a
i
Q
i
,
s
P
′
≠
e
a
i
T
i
,
P
′. Then, the probability Pr
⁡
[
E
]
≤
1
/
2
q, where q is a security parameter.Proof.
The proof is using the technique of the small exponents test in [37]. If e
(
a
i
b
i
+
α
a
i
Q
i
,
s
P
′
)
≠
e
(
a
i
T
i
,
P
′
) for some i, then T
i
≠
s
b
i
+
s
α
Q
i. That is, there exists c
i
≠
0 (mod q) such that T
i
=
s
b
i
+
s
α
Q
i
+
c
i
P.
LetT
j
=
s
b
j
+
s
α
Q
j
+
c
j
P where ∀
j
∈
{
1
,
…
,
n
}
-
{
i
} and c
j
∈
{
0
,
…
,
q
-
1
}. As e
(
∑
i
=
1
n
‍
a
i
b
i
+
α
∑
i
=
1
n
‍
a
i
Q
i
,
s
P
′
)
=
e
(
∑
i
=
1
n
‍
a
i
T
i
,
P
′
), ∑
i
=
1
n
‍
c
i
a
i
≡
0 (mod q). Hence, a
i
≡
-
c
i
-
1
(
c
1
a
1
+
c
2
a
2
+
⋯
+
c
i
-
1
a
i
-
1
+
c
i
+
1
a
i
+
1
+
⋯
+
c
n
a
n
) (mod q). Since a
i is randomly chosen from Z
q
*, Pr
⁡
[
E
]
≤
1
/
2
q.Theorem 13.
If an adversaryA can (
t
,
q
S
,
q
C
,
q
R
,
q
H
,
q
H
1
,
ɛ
)-impersonate a user U
i
* without the long-term private key of U
i
* with probability at least ɛ, where t is the running time, q
S, q
C, q
R, q
H, and q
H
1 are the numbers of makingSend queries,Corrupt queries,Reveal queries, H queries, and H
1 queries, respectively, there exists an algorithm to solve the variant-CDH problem with probability at least ɛ
′ in time t
′, where
(12)
ɛ
′
≥
1
/
|
U
|
1
-
1
/
U
1
-
1
/
2
h
ɛ
-
1
/
2
q
2
2
,
t
′
≈
2
t
+
q
S
O
(
t
S
)
+
q
C
O
(
t
C
)
+
q
R
O
(
t
R
)
q
H
O
(
t
H
)
+
q
H
1
O
(
t
H
1
)
2
+
q
H
O
(
t
H
)
+
q
H
1
O
(
t
H
1
)
+
O
(
n
2
)
,
h is the length of H
1’s output, U is a set of users, and t
H is the computing time of H oracle.Proof.
At first,B inputs κ to generate pairing parameters and a variant-CDH tuple (
P
,
a
P
,
b
P
,
P
′
,
a
P
′
)
∈
G
1, where a
,
b
∈
R
Z
q
*. We will show that B can solve the variant-CDH problem with the assistance of an adversary A. B’s task is to compute and output the value c
P
=
a
b
P.
B simulates the system as follows. We define (
a
P
,
a
P
′
) as the system master public key and B does not know the master private key a. H and H
1 are two random oracles simulated by B to respond the queries to H and H
1, respectively. B randomly chooses one user U
i
* and let b
P be U
i
*’s long-term public key. Except U
i
*, B computes other users’ long-term public/private key pairs by H. B allows A to make the following queries. (i)
H
(
·
): after given m
∈
{
(TA’s ID∥
U
i’s ID)
∣
1
≤
i
≤
q
}, B responds the query, H
(
m
), and maintains the H-list as follows.
Ifm = (TA’s ID∥
U
i
*’s ID), B returns H
(
m
)
=
b
P and stores a record U
i
*
,
b
P
,
⊥
,
⊥ in the H-list. Otherwise, B randomly chooses u
i
∈
Z
q
*, returns H
(
m
)
=
u
i
P, and stores a record (
U
i
,
u
i
P
,
u
i
a
P
,
u
i
) in the H-list, where u
i
P and u
i
a
P are the long-term public and private keys, respectively, of U
i.
(ii)
H
1
(
·
): after given m
∈
G
1, B randomly chooses α
∈
{
0,1
}
l, returns H
1
(
m
)
=
α, and stores a record (
m
,
α
) in the H
1-list.
(iii)
Execute(Π
U
t): A can choose U and ask B to run the key agreement protocol. B returns the public messages (
b
i
,
B
i
,
T
i
,
β
i)’s of all U
i’s in U to A. B produces the messages as follows.
IfU
i
*
∈
U, B picks k
i
,
z
,
α
∈
R
Z
q
* and computes b
i
=
z
P
-
α
b
P
=
(
z
-
α
b
)
P, T
i
=
z
a
P, and β
i
=
H
2
(
T
i
,
α
). For each of the other U
j’s ∈
U, B randomly picks r
j
,
k
j
∈
Z
q
* and computes b
j
=
r
j
-
1
P, T
j
=
α
u
j
a
P
+
r
j
-
1
a
P, and β
j
=
H
2
(
T
j
,
α
). Thus, B can follow the protocol to compute B
i for each U
j
∈
U and sets α
=
H
1
(
K
) where K
=
∑
U
j
∈
U
k
j
P.
(iv)
Send(Π
U
~
t
,
m): if A actively broadcasts the message of users U
~
⊂
U to run the key agreement protocol in session t, B can produce each (
b
i
,
B
i
,
T
i
,
β
i
) of the other U
i
∈
U
-
U
~ as that in theExecute query. Once if U
-
U
~
=
{
U
i
*
}, B can obtain K from H
1-list while A is making the H
1 query for α.
(v)
Reveal(Π
U
t
): B looks up the H
1-list to obtain K by checking if H
2
(
T
i
,
α
)
=
β
i and returns the session conference key SCK
=
H
3
(
K
).
(vi)
Corrupt
(
U
i
): if U
i
=
U
i
*, B returns ⊥ and aborts the game. Otherwise, B searches U
i in the H-list. If U
i is not in the H-list, B calls H to produce and store (
U
i
,
u
i
P
,
u
i
a
P
,
u
i
) in the H-list. Then, B returns u
i
a
P.
IfA impersonates U
i
* at some point, according to Lemma 12, it must send out T
i
=
α
a
Q
i
*
+
r
i
-
1
a
P with the probability at least ɛ
-
1
/
2
q, where H
1
(
K
)
=
α. Once A produces a correct T
i, B replays A with the same random tape by forking lemma. At this time, A gets two different hashed values α and α
′ and generates two valid T
i
=
α
a
b
P
+
r
i
-
1
a
P and T
i
′
=
α
′
a
b
P
+
r
i
-
1
a
P. B can compute c
P
=
(
α
-
α
′
)
-
1
(
T
i
-
T
i
′
)
=
a
b
P. Finally, B outputs a
b
P.
LetX and Y be the set of any possible input messages of the random tape and H
1, respectively. A fails in makingCorrupt queries with probability 1
/
|
U
|. A guesses the value α
=
H
1
(
K
) without making H
1 queries with probability 2
-
h, where h is the length of H
1’s output. Therefore, the probability is δ
=
1
/
|
U
|
1
-
1
/
|
U
|
1
-
1
/
2
h
ɛ
-
1
/
2
q. By splitting lemma, we set ρ
=
δ
/
2 such that δ
-
ρ
=
δ
-
δ
/
2
=
δ
/
2. Overall, B performs two executions of A, so that we have
(13)
ɛ
′
≥
δ
2
2
=
1
/
|
U
|
1
-
1
/
|
U
|
1
-
1
/
2
h
ɛ
-
1
/
2
q
2
2
,
t
′
≈
2
t
+
q
S
O
(
t
S
)
+
q
C
O
(
t
C
)
+
q
R
O
(
t
R
)
q
H
O
(
t
H
)
+
q
H
1
O
(
t
H
1
)
≈
2
+
q
H
O
t
H
+
q
H
1
O
t
H
1
+
O
n
2
.As for the proof of the interdomain case,(
a
P
,
a
P
′
,
b
P
), the parameters of the variant-CDH problem are the public keys of some TA and some user who belongs to the CA, respectively. The private keys of the other TAs and users are randomly generated by B. Likewise, the proposed interdomain key agreement scheme can also withstand key-compromise impersonation.


### 6.4. Forward Secrecy

After given broadcast messages, session keys, and all users’ long-term keys according to anI
D
C
K scheme, an adversary makes a Test query and then receives a random string or a session key. The adversary can continue making queries. If no adversary can decide whether the received string is a session key or not with nonnegligible advantage, we say that the I
D
C
K scheme satisfies forward secrecy.Definition 14 (forward secrecy).
AnI
D
C
K scheme has forward secrecy if any adversary who obtains the other session keys and all users’ long term keys can distinguish a previous session key from a random string with the probability at least (
ɛ
+
1
/
2
) where ɛ, called the advantage, is negligible.
After running time at mostt, making at most q
H
1 queries to H
1, q
E
Execute queries, q
S
Send queries, q
C
Corrupt queries, and q
R
Reveal queries, an adversary A can obtain all users’ long-term private keys and receives a string through a Test query. A
(
t
,
q
E
,
q
S
,
q
C
,
q
R
,
q
H
1
,
ɛ
)-FS-breaks our I
D
C
K scheme if he can determine whether the received string is a previous session key negotiated by users with nonnegligible advantage at least ɛ.Theorem 15.
If an adversaryA can (
t
,
q
E
,
q
S
,
q
C
,
q
R
,
q
H
1
,
ɛ
)-FS-determine whetherSCK is a previous session key or not, where t is the running time, q
E, q
S, q
C, q
R, and q
H
1 are the numbers of makingSend queries,Corrupt queries,Reveal queries, and hash queries to H
1, respectively, there exists an algorithm to solve the n-DLDH problem with nonnegligible advantage at least ɛ
′ in time t
′, where
(14)
ɛ
′
≥
ɛ
q
0
,
t
′
≈
t
+
q
E
O
(
t
E
)
+
q
S
O
(
t
S
)
+
q
C
O
(
t
C
)
t
′
≈
+
q
R
O
(
t
R
)
+
q
H
1
O
(
t
H
1
)
+
O
(
n
2
)
,
and q
0
=
q
E
+
q
S
+
q
C
+
q
R
+
q
H
1.Proof.
The simulation and the queries answered byB are the same as those in the proof of Theorem 8 except that A is allowed to make C
o
r
r
u
p
t
(
U
i
) query, where U
i
∈
U
*, after makingTest(Π
U
*
l). That is, A has to activate the lth session first before any U
i
∈
U
* is corrupted. In the end, B can decide whether Z
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P or not according to the value of b output by A, where
(15)
ɛ
′
≥
ɛ
q
0
t
′
≈
t
+
q
E
O
(
t
E
)
+
q
S
O
(
t
S
)
+
q
C
O
(
t
C
)
+
q
R
O
(
t
R
)
+
q
H
1
O
(
t
H
1
)
+
O
(
n
2
)
.Similarly, the proposed interdomain key agreement scheme can also achieve forward secrecy.


### 6.5. Key Control

An adversary who is one of the users can obtain broadcast messages, session keys, and the other users’ long-term keys. Then, the adversary is given a preselected value. If the adversary cannot make the given preselected value become a new session key with nonnegligible probability, theI
D
C
K scheme can withstand key control attacks.Definition 16 (key control).
AnI
D
C
K scheme can withstand key control attacks if no adversary can predict a session key or preselect a session key with nonnegligible probability.Theorem 17.
If an adversaryA can (
t
,
q
E
,
q
S
,
q
C
,
q
R
,
q
H
,
ɛ
)-predict a session key or preselect a session key with probability at least ɛ, where t is the running time, q
E
,
q
S
,
q
C
,
q
R, and q
H are the numbers of makingSend queries,Corrupt queries,Reveal queries, and hash queries to H, respectively, there exists an algorithm to solve the CDH problem with nonnegligible probability at least ɛ
′ in time t
′, where
(16)
ɛ
′
≥
ɛ
q
0
,
t
′
≈
t
+
q
E
O
(
t
E
)
+
q
S
O
(
t
S
)
+
q
C
O
(
t
C
)
+
q
R
O
(
t
R
)
+
q
H
O
(
t
H
)
+
O
(
n
2
)
,
and q
0
=
q
E
+
q
S
+
q
C
+
q
R
+
q
H.Proof.
At first,B inputs κ to generate pairing parameters and a CDH triple (
P
,
a
P
,
b
P
)
∈
G
1, where a
,
b
∈
R
Z
q
*. We show that an algorithm B can solve the CDH problem with the help of an adversary A. B’s task is to compute and output the value c
P
=
a
b
P.
B simulates the system as follows. We define that (
s
P
,
s
P
′
) is the system master public key by randomly choosing the master private key s. B allows A to make the following queries. (i)
H
(
·
): after given m
∈
{
(TA’s ID∥
U
i’s ID)
∣
1
≤
i
≤
q
}, B responds the query H
(
m
) and maintains the H-list as follows: B randomly chooses u
i
∈
Z
q
*, returns H
(
m
)
=
u
i
P, and stores a record (
U
i
,
u
i
P
,
u
i
s
P
,
u
i
) in the H-list.
(ii)
Execute(Π
U
t): A can choose a set U of users to run the key agreement protocol in session t. B follows the protocol to produce every (
b
i
,
B
i
,
T
i
,
β
i
,
k
i
) and computes K
=
∑
U
i
∈
U
k
i
P. Finally, B responds every (
b
i
,
B
i
,
T
i
,
β
i
) to A.
(iii)
Send
(
Π
U
~
t
,
m
): if A can actively send the message of users U
~
⊂
U to run the key agreement protocol in session t, B can produce (
b
i
,
B
i
,
T
i
,
β
i
) of each U
i
∈
U
-
U
~ as that in theExecute query.
(iv)
Reveal
(
Π
U
t
): B returns the session conference key SCK
=
H
3
(
K
).
(v)
Corrupt
(
U
i
): B searches U
i in H-list and returns u
i
s
P. If U
i is not in H-list, B calls H oracle to produce (
U
i
,
u
i
P
,
u
i
s
P
,
u
i
) and returns u
i
s
P.
WhenA finishes making the above queries, B sets K
=
x
P
+
b
P, where x
∈
R
Z
q
*, and returns it to A. Suppose that A is user U
i and B simulates other users U
1
,
U
2
,
…
,
…
,
U
i
-
1
,
U
i
+
1
,
…
,
U
n to negotiate a session conference key with A. B returns {
(
b
1
,
B
1
,
T
1
,
β
1
)
,
…
,
(
b
i
-
1
,
B
i
-
1
,
T
i
-
1
,
β
i
-
1
), (
b
i
+
1
,
B
i
+
1
,
T
i
+
1
,
β
i
+
1
)
,
…
,
(
b
n
,
B
n
,
T
n
,
β
n
)
} to A, where x
=
k
1
+
⋯
+
k
i
-
1
+
k
i
+
1
+
⋯
+
k
n and b
1
=
a
P. A must broadcast B
i
=
(
k
i
b
1
,
…
,
k
i
b
i
-
1
,
k
i
b
i
+
1
,
…
,
k
i
b
n
) in round 2 such that (
k
1
+
k
2
+
⋯
+
k
n
)
P
=
(
x
+
b
)
P. Therefore, k
i
P
=
b
P and k
i
b
1
=
a
b
P.
Overall, we have that(17)
ɛ
′
≥
ɛ
q
0
,
t
′
≈
t
+
q
E
O
t
E
+
q
S
O
t
S
+
q
C
O
t
C
+
q
R
O
t
R
+
q
H
O
t
H
+
O
n
2
.Following a proof similar to that for the above theorem, we can show that the proposed interdomain key agreement scheme withstands key control attacks.


## 6.1. Correctness

Theorem 6 (correctness).
In the presence of a benign adversaryA, all the parties always accept holding the same session conference key, which is distributed randomly and uniformly in {
0,1
}
κ, where κ is the security parameter.Proof.
Every userU
i can generate a valid message (
b
i
,
B
i
,
T
i
,
β
i
) by following our proposed single domain scheme (Section 5.1), verify the correctness of the message V
i
=
e
(
∑
i
=
1
n
‍
a
i
b
i
+
α
∑
i
=
1
n
‍
a
i
Q
i
,
s
P
′
)
=
e
(
(
a
1
r
1
-
1
+
a
2
r
2
-
1
+
⋯
+
a
n
r
n
-
1
)
P
+
(
α
a
1
Q
1
+
α
a
2
Q
2
+
⋯
+
α
a
n
Q
n
)
,
s
P
′
) = e
(
a
1
(
α
s
Q
1
+
r
1
-
1
s
P
)
+
a
2
(
α
s
Q
2
+
r
2
-
1
s
P
)
+
⋯ + a
n
(
α
s
Q
n
+
r
n
-
1
s
P
)
,
P
′
)
=
e
(
∑
i
=
1
n
‍
a
i
(
α
s
Q
i
+
r
i
-
1
s
P
)
,
P
′
) = e
(
∑
i
=
1
n
‍
a
i
T
i
,
P
′
), and negotiate a common session conference key SCK
=
H
3
(
K
).
In our proposed interdomain scheme (Section5.2), U
i
j can generate a valid message (
b
i
j
,
B
i
j
,
T
i
j
,
β
i
j
) and verify the correctness of the message because
(9)
V
h
,
l
=
∏
h
=
1
m
‍
e
∑
l
=
1
n
h
‍
a
h
,
l
b
h
,
l
+
α
∑
l
=
1
n
h
‍
a
h
,
l
Q
h
,
l
,
s
h
P
′
=
e
(
a
1,1
r
1,1
-
1
+
a
1,2
r
1,2
-
1
+
⋯
+
a
1
,
n
1
r
1
,
n
1
-
1
)
P
+
α
a
1,1
Q
1,1
+
α
a
1,2
Q
1,2
+
⋯
+
α
a
1
,
n
1
Q
1
,
n
1
,
s
1
P
′
·
e
a
2,1
r
2,1
-
1
+
a
2,2
r
2,2
-
1
+
⋯
+
a
2
,
n
2
r
2
,
n
2
-
1
P
+
α
a
2,1
Q
2,1
+
α
a
2,2
Q
2,2
+
⋯
+
α
a
2
,
n
2
Q
2
,
n
2
,
a
2,1
r
2,1
-
1
+
a
2,2
r
2,2
-
1
+
⋯
+
a
2
,
n
2
r
2
,
n
2
-
1
s
2
P
′
·
e
a
m
,
1
r
m
,
1
-
1
+
a
m
,
2
r
m
,
2
-
1
+
⋯
+
a
m
,
n
m
r
m
,
n
m
-
1
P
+
α
a
m
,
1
Q
m
,
1
+
α
a
m
,
2
Q
m
,
2
+
⋯
+
α
a
m
,
n
m
Q
m
,
n
m
,
a
2,1
r
2,1
-
1
+
a
2,2
r
2,2
-
1
+
⋯
+
a
2
,
n
2
r
2
,
n
2
-
1
s
m
P
′
=
e
a
1,1
α
s
1
Q
1,1
+
r
1,1
-
1
s
1
P
+
a
1,2
α
s
1
Q
1,2
+
r
1,2
-
1
s
1
P
+
⋯
+
a
1
,
n
1
α
s
1
Q
1
,
n
1
+
r
1
,
n
1
-
1
s
1
P
,
P
′
·
e
a
2,1
α
s
2
Q
2,1
+
r
2,1
-
1
s
2
P
+
a
2,2
α
s
2
Q
2,2
+
r
2,2
-
1
s
2
P
+
a
2
,
n
2
α
s
2
Q
2
,
n
2
+
r
2
,
n
2
-
1
s
2
P
,
P
′
kkkkkkkkkkkkkkkkkkkkkkk
⋮
·
e
a
m
,
1
α
s
m
Q
m
,
1
+
r
m
,
1
-
1
s
m
P
+
a
m
,
2
α
s
m
Q
m
,
2
+
r
m
,
2
-
1
s
m
P
+
⋯
+
a
m
,
n
m
α
s
m
Q
m
,
n
m
+
r
m
,
n
m
-
1
s
m
P
,
P
′
=
e
∑
h
=
1
m
‍
∑
l
=
1
n
h
‍
a
h
,
l
α
s
h
Q
h
,
l
+
r
h
,
l
-
1
s
h
P
,
P
′
=
e
∑
h
=
1
m
‍
∑
l
=
1
n
h
‍
a
h
,
l
T
h
,
l
,
P
′
.


## 6.2. Known Session Key Security

After given broadcast messages and previous session keys according to theI
D
C
K scheme, an adversary makes a Test query and then receives a random string or a current session key. The adversary can continue asking for broadcast messages and other session keys. If no polynomial-time adversary can decide whether the received string is the current session key or not with nonnegligible advantage, we say that the I
D
C
K scheme satisfies known session key security.Definition 7 (known session key security).
AnI
D
C
K scheme is with known session key security if no polynomial-time adversary can decide if a challenge string is a current session key or a random string under the knowledge of previous session keys with the probability at least (
ɛ
+
1
/
2
) where ɛ, called the advantage, is nonnegligible.Theorem 8.
If an adversaryA can (
t
,
q
E
,
q
S
,
q
C
,
q
R
,
q
H
1
ɛ
)-decide whether the string received from a Test query is the session keySCK held by Π
U
l or not with advantage at least ɛ, where t is the running time and q
E
,
q
S
,
q
C
,
q
R, and q
H
1 are the numbers of makingExecute queries,Send queries,Corrupt queries,Reveal queries, and H
1 queries, respectively, there exists an algorithm which can solve the n-DLDH problem with advantage at least ɛ
′ in time t
′, where
(10)
ɛ
′
≥
ɛ
q
0
,
t
′
≈
t
+
q
E
O
(
t
E
)
+
+
q
S
O
(
t
S
)
+
q
C
O
(
t
C
)
+
q
R
O
(
t
R
)
+
q
H
1
O
(
t
H
1
)
+
O
(
n
2
)
,
q
0
=
q
E
+
q
S
+
q
C
+
q
R
+
q
H, t
E
,
t
S
,
t
C
,
t
R, and t
H
1 are the computing time of the Execute oracle, the Send oracle, the Corrupt oracle, the Reveal oracle, and H
1 oracle, respectively.Proof.
Initially, we construct a simulatorB which prepares the pairing parameters and simulates the system as follows. B randomly picks s
∈
Z
q
* as the system master private key and computes (
s
P
,
s
P
′
) as the system master public key. B computes each user’s long-term public/private key pair (
Q
i
,
s
Q
i
). B allows A to make the following queries (i)
Execute(Π
U
t): A can request U that is a set of users who are chosen by itself to run the key agreement protocol in session t. B follows the protocol (Section 5.1) to produce every (
r
i
,
b
i
,
B
i
,
T
i
,
β
i
,
k
i
), and K
=
∑
U
i
∈
U
k
i
P, and then records them. Finally, B responds every (
b
i
,
B
i
,
T
i
,
β
i
) to A, where U
i
∈
U.
(ii)
Send(Π
U
~
t
,
m): if A actively broadcasts the messages of users U
~
⊂
U to run the key agreement protocol in session t, B follows the protocol (Section 5.1) to produce every (
r
i
,
b
i
,
B
i
,
T
i
,
β
i
,
k
i
) and generate the session conference key in the end of the protocol and then records them. Finally, B responds (
b
i
,
B
i
,
T
i
,
β
i
) to A for each U
i
∈
U
-
U
~.
(iii)
Reveal(Π
U
t
): if Π
U
t does not exist, B creates Π
U
t. B returns the session conference key SCK
=
H
3
(
K
).
(iv)
Corrupt
(
U
i
): B returns (
Q
i
,
s
Q
i
) to A.
(v)
H
1
(
m
): after given m
∈
G
1, B randomly chooses α
∈
{
0,1
}
λ, returns H
1
(
m
)
=
α, and stores (
m
,
α
) in a list, called H
1-list.
(vi)
Test(Π
U
*
l): B guesses that A will send a Test query at the hth session in advance. If A makes aTest query at the lth session, where l
≠
h, B randomly answers “YES” or “NO” to the n-DLDH problem. When A makes aTest query at the lth session, where l
=
h, B checks whether there exists U
i which has been corrupted or not, where U
i
∈
U
* and |
U
*
|
=
n. If one of them has been corrupted, B returns ⊥ and aborts the game. Otherwise, B is given the parameters of an instance of the n-DLDH problem, Z
,
P, and (
x
i
P
,
x
i
x
n
+
j
P
)’s for all i
,
j with 1
≤
i, j
≤
n, and i
≠
j, and takes the advantage of A to decide whether Z
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P or not. B sets the public messages (
b
i
*
,
B
i
*
,
T
i
*
,
β
i
*
) of every user in U
* in the lth session as follows.
First,B forms b
1
*
=
x
1
P, b
2
*
=
x
2
P
,
…
,
b
n
*
=
x
n
P, K
*
=
Z, α
*

=

H
1
(
K
*
), and prepares B
i
*

=

(
x
1
x
n
+
i
P
,
x
2
x
n
+
i
P
,
…
,

x
i
-
1
x
n
+
i
P
,

⊥
,
x
i
+
1
x
n
+
i
P
,
…
,
x
n
x
n
+
i
P
), for each U
i
*
∈
U
*; that is,
(11)
U
1
*
U
2
*
…
U
i
*
…
U
n
*
B
1
*
⊥
x
2
x
n
+
1
P
…
x
i
x
n
+
1
P
…
x
n
x
n
+
1
P
B
2
*
x
1
x
n
+
2
P
⊥
…
x
i
x
n
+
2
P
…
x
n
x
n
+
2
P
⋮
⋮
⋮
⋱
⋮
⋮
⋮
B
i
*
x
1
x
n
+
i
P
x
2
x
n
+
i
P
…
⊥
…
x
n
x
n
+
i
P
⋮
⋮
⋮
⋮
⋮
⋱
⋮
B
n
*
x
1
x
2
n
P
x
2
x
2
n
P
…
x
i
x
2
n
P
…
⊥
B sets T
i
*
=
s
α
*
Q
i
+
s
x
i
P and computes β
i
*
=
H
2
(
T
i
*
,
α
*
) and SCK
*
=
H
3
(
K
*
), where 1
≤
i
≤
n. B responds every (
b
i
*
,
B
i
*
,
T
i
*
,
β
i
*
) and SCK
* to A.
A can continue making the queries ofExecute(Π
U
t),Send(Π
U
t),Reveal(Π
U
t
), andCorrupt
(
U
i
), where t
≠
l and U
i
∉
U
*, until A outputs a bit b. If SC
K
* is the key in session l from A’s point of view, A will output b
=
1; otherwise, b
=
0. If b
=
1, B outputs “YES”; that is, Z
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P; otherwise, B outputs “NO”.
If the adversary can compromise known session key security of the scheme with advantage at leastɛ, B can solve the n-DLDH problem with the advantage at least ɛ
′
≥
1
/
q
0
(
1
/
2
+
ɛ
)
+
1
/
2
q
0
-
1
/
q
0
-
1
/
2
=
ɛ
/
q
0.By Theorem8, we can solve the n-DLDH problem in polynomial time with nonnegligible advantage if there exists a polynomial-time adversary that can break the known session key security with nonnegligible advantage of the proposed single domain key agreement scheme.As for the proof of the interdomain case, we can letn be the number of the total users from all domains; that is, n
=
N. Then, by the proof of Theorem 8, the n-DLDH problem can be solved if the adversary can distinguish the session key from a random string in the proposed interdomain key agreement scheme.


## 6.3. Key-Compromise Impersonation

An adversary is given all users’ long-term keys by making Corrupt queries except the one that he claims to impersonate. If no adversary can output the correct messages of the user with nonnegligible probability, theI
D
C
K scheme can withstand key-compromise impersonation.Definition 9 (key-compromise impersonation).
AnI
D
C
K scheme can withstand key-compromise impersonation if no adversary can have nonnegligible probability to impersonate a user without the long-term private key of the user.Lemma 10 (the forking lemma [35]).
LetT
i
=
α
s
Q
i
+
r
i
-
1
s
P be a valid authentic parameter of user U
i, where s
Q
i is U
i’s private key, s
P is TA’s public key, r
i
-
1 is randomly chosen by U
i, and α is a hashed value of K shared by all users. Let A be a probabilistic polynomial time Turing machine. Given only the public data of the key agreement scheme as input, if A can find, with nonnegligible probability, a valid authentic parameter T
i with α, then, with nonnegligible probability, a replay of this machine, with the same random tape and a different value returned by the random oracle, can output two valid authentic parameters T
i with α and T
i
′ with α
′, such that α
≠
α
′.Lemma 11 (the splitting lemma [36]).
LetA
⊂
X
×
Y such that Pr
⁡
[
(
x
,
y
)
∈
A
]
=
|
A
|
/
(
|
X
|
×
|
Y
|
)
≥
δ. For any ρ
<
δ, define B
=
{
x
∈
X
∣
Pr
⁡
[
(
x
,
y
)
∈
A
]
≥
δ
-
ρ
} and B
¯
=
X
∖
B. Then the following statements hold: (1)
Pr
⁡
[
x
∈
B
]
=
|
B
|
/
|
X
|
≥
ρ,
(2)
∀
x
∈
B
,
Pr
⁡
[
(
x
,
y
)
∈
A
]
≥
δ
-
ρ,
(3)
Pr
⁡
[
x
∈
B
∣
(
x
,
y
)
∈
A
]
≥
ρ
/
δ.Lemma 12.
Assume thate
∑
i
=
1
n
‍
a
i
b
i
+
α
∑
i
=
1
n
‍
a
i
Q
i
,
s
P
′
=
e
∑
i
=
1
n
‍
a
i
T
i
,
P
′. Let E be an event that occurs if there is at least one T
i such that e
a
i
b
i
+
α
a
i
Q
i
,
s
P
′
≠
e
a
i
T
i
,
P
′. Then, the probability Pr
⁡
[
E
]
≤
1
/
2
q, where q is a security parameter.Proof.
The proof is using the technique of the small exponents test in [37]. If e
(
a
i
b
i
+
α
a
i
Q
i
,
s
P
′
)
≠
e
(
a
i
T
i
,
P
′
) for some i, then T
i
≠
s
b
i
+
s
α
Q
i. That is, there exists c
i
≠
0 (mod q) such that T
i
=
s
b
i
+
s
α
Q
i
+
c
i
P.
LetT
j
=
s
b
j
+
s
α
Q
j
+
c
j
P where ∀
j
∈
{
1
,
…
,
n
}
-
{
i
} and c
j
∈
{
0
,
…
,
q
-
1
}. As e
(
∑
i
=
1
n
‍
a
i
b
i
+
α
∑
i
=
1
n
‍
a
i
Q
i
,
s
P
′
)
=
e
(
∑
i
=
1
n
‍
a
i
T
i
,
P
′
), ∑
i
=
1
n
‍
c
i
a
i
≡
0 (mod q). Hence, a
i
≡
-
c
i
-
1
(
c
1
a
1
+
c
2
a
2
+
⋯
+
c
i
-
1
a
i
-
1
+
c
i
+
1
a
i
+
1
+
⋯
+
c
n
a
n
) (mod q). Since a
i is randomly chosen from Z
q
*, Pr
⁡
[
E
]
≤
1
/
2
q.Theorem 13.
If an adversaryA can (
t
,
q
S
,
q
C
,
q
R
,
q
H
,
q
H
1
,
ɛ
)-impersonate a user U
i
* without the long-term private key of U
i
* with probability at least ɛ, where t is the running time, q
S, q
C, q
R, q
H, and q
H
1 are the numbers of makingSend queries,Corrupt queries,Reveal queries, H queries, and H
1 queries, respectively, there exists an algorithm to solve the variant-CDH problem with probability at least ɛ
′ in time t
′, where
(12)
ɛ
′
≥
1
/
|
U
|
1
-
1
/
U
1
-
1
/
2
h
ɛ
-
1
/
2
q
2
2
,
t
′
≈
2
t
+
q
S
O
(
t
S
)
+
q
C
O
(
t
C
)
+
q
R
O
(
t
R
)
q
H
O
(
t
H
)
+
q
H
1
O
(
t
H
1
)
2
+
q
H
O
(
t
H
)
+
q
H
1
O
(
t
H
1
)
+
O
(
n
2
)
,
h is the length of H
1’s output, U is a set of users, and t
H is the computing time of H oracle.Proof.
At first,B inputs κ to generate pairing parameters and a variant-CDH tuple (
P
,
a
P
,
b
P
,
P
′
,
a
P
′
)
∈
G
1, where a
,
b
∈
R
Z
q
*. We will show that B can solve the variant-CDH problem with the assistance of an adversary A. B’s task is to compute and output the value c
P
=
a
b
P.
B simulates the system as follows. We define (
a
P
,
a
P
′
) as the system master public key and B does not know the master private key a. H and H
1 are two random oracles simulated by B to respond the queries to H and H
1, respectively. B randomly chooses one user U
i
* and let b
P be U
i
*’s long-term public key. Except U
i
*, B computes other users’ long-term public/private key pairs by H. B allows A to make the following queries. (i)
H
(
·
): after given m
∈
{
(TA’s ID∥
U
i’s ID)
∣
1
≤
i
≤
q
}, B responds the query, H
(
m
), and maintains the H-list as follows.
Ifm = (TA’s ID∥
U
i
*’s ID), B returns H
(
m
)
=
b
P and stores a record U
i
*
,
b
P
,
⊥
,
⊥ in the H-list. Otherwise, B randomly chooses u
i
∈
Z
q
*, returns H
(
m
)
=
u
i
P, and stores a record (
U
i
,
u
i
P
,
u
i
a
P
,
u
i
) in the H-list, where u
i
P and u
i
a
P are the long-term public and private keys, respectively, of U
i.
(ii)
H
1
(
·
): after given m
∈
G
1, B randomly chooses α
∈
{
0,1
}
l, returns H
1
(
m
)
=
α, and stores a record (
m
,
α
) in the H
1-list.
(iii)
Execute(Π
U
t): A can choose U and ask B to run the key agreement protocol. B returns the public messages (
b
i
,
B
i
,
T
i
,
β
i)’s of all U
i’s in U to A. B produces the messages as follows.
IfU
i
*
∈
U, B picks k
i
,
z
,
α
∈
R
Z
q
* and computes b
i
=
z
P
-
α
b
P
=
(
z
-
α
b
)
P, T
i
=
z
a
P, and β
i
=
H
2
(
T
i
,
α
). For each of the other U
j’s ∈
U, B randomly picks r
j
,
k
j
∈
Z
q
* and computes b
j
=
r
j
-
1
P, T
j
=
α
u
j
a
P
+
r
j
-
1
a
P, and β
j
=
H
2
(
T
j
,
α
). Thus, B can follow the protocol to compute B
i for each U
j
∈
U and sets α
=
H
1
(
K
) where K
=
∑
U
j
∈
U
k
j
P.
(iv)
Send(Π
U
~
t
,
m): if A actively broadcasts the message of users U
~
⊂
U to run the key agreement protocol in session t, B can produce each (
b
i
,
B
i
,
T
i
,
β
i
) of the other U
i
∈
U
-
U
~ as that in theExecute query. Once if U
-
U
~
=
{
U
i
*
}, B can obtain K from H
1-list while A is making the H
1 query for α.
(v)
Reveal(Π
U
t
): B looks up the H
1-list to obtain K by checking if H
2
(
T
i
,
α
)
=
β
i and returns the session conference key SCK
=
H
3
(
K
).
(vi)
Corrupt
(
U
i
): if U
i
=
U
i
*, B returns ⊥ and aborts the game. Otherwise, B searches U
i in the H-list. If U
i is not in the H-list, B calls H to produce and store (
U
i
,
u
i
P
,
u
i
a
P
,
u
i
) in the H-list. Then, B returns u
i
a
P.
IfA impersonates U
i
* at some point, according to Lemma 12, it must send out T
i
=
α
a
Q
i
*
+
r
i
-
1
a
P with the probability at least ɛ
-
1
/
2
q, where H
1
(
K
)
=
α. Once A produces a correct T
i, B replays A with the same random tape by forking lemma. At this time, A gets two different hashed values α and α
′ and generates two valid T
i
=
α
a
b
P
+
r
i
-
1
a
P and T
i
′
=
α
′
a
b
P
+
r
i
-
1
a
P. B can compute c
P
=
(
α
-
α
′
)
-
1
(
T
i
-
T
i
′
)
=
a
b
P. Finally, B outputs a
b
P.
LetX and Y be the set of any possible input messages of the random tape and H
1, respectively. A fails in makingCorrupt queries with probability 1
/
|
U
|. A guesses the value α
=
H
1
(
K
) without making H
1 queries with probability 2
-
h, where h is the length of H
1’s output. Therefore, the probability is δ
=
1
/
|
U
|
1
-
1
/
|
U
|
1
-
1
/
2
h
ɛ
-
1
/
2
q. By splitting lemma, we set ρ
=
δ
/
2 such that δ
-
ρ
=
δ
-
δ
/
2
=
δ
/
2. Overall, B performs two executions of A, so that we have
(13)
ɛ
′
≥
δ
2
2
=
1
/
|
U
|
1
-
1
/
|
U
|
1
-
1
/
2
h
ɛ
-
1
/
2
q
2
2
,
t
′
≈
2
t
+
q
S
O
(
t
S
)
+
q
C
O
(
t
C
)
+
q
R
O
(
t
R
)
q
H
O
(
t
H
)
+
q
H
1
O
(
t
H
1
)
≈
2
+
q
H
O
t
H
+
q
H
1
O
t
H
1
+
O
n
2
.As for the proof of the interdomain case,(
a
P
,
a
P
′
,
b
P
), the parameters of the variant-CDH problem are the public keys of some TA and some user who belongs to the CA, respectively. The private keys of the other TAs and users are randomly generated by B. Likewise, the proposed interdomain key agreement scheme can also withstand key-compromise impersonation.


## 6.4. Forward Secrecy

After given broadcast messages, session keys, and all users’ long-term keys according to anI
D
C
K scheme, an adversary makes a Test query and then receives a random string or a session key. The adversary can continue making queries. If no adversary can decide whether the received string is a session key or not with nonnegligible advantage, we say that the I
D
C
K scheme satisfies forward secrecy.Definition 14 (forward secrecy).
AnI
D
C
K scheme has forward secrecy if any adversary who obtains the other session keys and all users’ long term keys can distinguish a previous session key from a random string with the probability at least (
ɛ
+
1
/
2
) where ɛ, called the advantage, is negligible.
After running time at mostt, making at most q
H
1 queries to H
1, q
E
Execute queries, q
S
Send queries, q
C
Corrupt queries, and q
R
Reveal queries, an adversary A can obtain all users’ long-term private keys and receives a string through a Test query. A
(
t
,
q
E
,
q
S
,
q
C
,
q
R
,
q
H
1
,
ɛ
)-FS-breaks our I
D
C
K scheme if he can determine whether the received string is a previous session key negotiated by users with nonnegligible advantage at least ɛ.Theorem 15.
If an adversaryA can (
t
,
q
E
,
q
S
,
q
C
,
q
R
,
q
H
1
,
ɛ
)-FS-determine whetherSCK is a previous session key or not, where t is the running time, q
E, q
S, q
C, q
R, and q
H
1 are the numbers of makingSend queries,Corrupt queries,Reveal queries, and hash queries to H
1, respectively, there exists an algorithm to solve the n-DLDH problem with nonnegligible advantage at least ɛ
′ in time t
′, where
(14)
ɛ
′
≥
ɛ
q
0
,
t
′
≈
t
+
q
E
O
(
t
E
)
+
q
S
O
(
t
S
)
+
q
C
O
(
t
C
)
t
′
≈
+
q
R
O
(
t
R
)
+
q
H
1
O
(
t
H
1
)
+
O
(
n
2
)
,
and q
0
=
q
E
+
q
S
+
q
C
+
q
R
+
q
H
1.Proof.
The simulation and the queries answered byB are the same as those in the proof of Theorem 8 except that A is allowed to make C
o
r
r
u
p
t
(
U
i
) query, where U
i
∈
U
*, after makingTest(Π
U
*
l). That is, A has to activate the lth session first before any U
i
∈
U
* is corrupted. In the end, B can decide whether Z
=
(
x
n
+
1
+
x
n
+
2
+
⋯
+
x
2
n
)
P or not according to the value of b output by A, where
(15)
ɛ
′
≥
ɛ
q
0
t
′
≈
t
+
q
E
O
(
t
E
)
+
q
S
O
(
t
S
)
+
q
C
O
(
t
C
)
+
q
R
O
(
t
R
)
+
q
H
1
O
(
t
H
1
)
+
O
(
n
2
)
.Similarly, the proposed interdomain key agreement scheme can also achieve forward secrecy.


## 6.5. Key Control

An adversary who is one of the users can obtain broadcast messages, session keys, and the other users’ long-term keys. Then, the adversary is given a preselected value. If the adversary cannot make the given preselected value become a new session key with nonnegligible probability, theI
D
C
K scheme can withstand key control attacks.Definition 16 (key control).
AnI
D
C
K scheme can withstand key control attacks if no adversary can predict a session key or preselect a session key with nonnegligible probability.Theorem 17.
If an adversaryA can (
t
,
q
E
,
q
S
,
q
C
,
q
R
,
q
H
,
ɛ
)-predict a session key or preselect a session key with probability at least ɛ, where t is the running time, q
E
,
q
S
,
q
C
,
q
R, and q
H are the numbers of makingSend queries,Corrupt queries,Reveal queries, and hash queries to H, respectively, there exists an algorithm to solve the CDH problem with nonnegligible probability at least ɛ
′ in time t
′, where
(16)
ɛ
′
≥
ɛ
q
0
,
t
′
≈
t
+
q
E
O
(
t
E
)
+
q
S
O
(
t
S
)
+
q
C
O
(
t
C
)
+
q
R
O
(
t
R
)
+
q
H
O
(
t
H
)
+
O
(
n
2
)
,
and q
0
=
q
E
+
q
S
+
q
C
+
q
R
+
q
H.Proof.
At first,B inputs κ to generate pairing parameters and a CDH triple (
P
,
a
P
,
b
P
)
∈
G
1, where a
,
b
∈
R
Z
q
*. We show that an algorithm B can solve the CDH problem with the help of an adversary A. B’s task is to compute and output the value c
P
=
a
b
P.
B simulates the system as follows. We define that (
s
P
,
s
P
′
) is the system master public key by randomly choosing the master private key s. B allows A to make the following queries. (i)
H
(
·
): after given m
∈
{
(TA’s ID∥
U
i’s ID)
∣
1
≤
i
≤
q
}, B responds the query H
(
m
) and maintains the H-list as follows: B randomly chooses u
i
∈
Z
q
*, returns H
(
m
)
=
u
i
P, and stores a record (
U
i
,
u
i
P
,
u
i
s
P
,
u
i
) in the H-list.
(ii)
Execute(Π
U
t): A can choose a set U of users to run the key agreement protocol in session t. B follows the protocol to produce every (
b
i
,
B
i
,
T
i
,
β
i
,
k
i
) and computes K
=
∑
U
i
∈
U
k
i
P. Finally, B responds every (
b
i
,
B
i
,
T
i
,
β
i
) to A.
(iii)
Send
(
Π
U
~
t
,
m
): if A can actively send the message of users U
~
⊂
U to run the key agreement protocol in session t, B can produce (
b
i
,
B
i
,
T
i
,
β
i
) of each U
i
∈
U
-
U
~ as that in theExecute query.
(iv)
Reveal
(
Π
U
t
): B returns the session conference key SCK
=
H
3
(
K
).
(v)
Corrupt
(
U
i
): B searches U
i in H-list and returns u
i
s
P. If U
i is not in H-list, B calls H oracle to produce (
U
i
,
u
i
P
,
u
i
s
P
,
u
i
) and returns u
i
s
P.
WhenA finishes making the above queries, B sets K
=
x
P
+
b
P, where x
∈
R
Z
q
*, and returns it to A. Suppose that A is user U
i and B simulates other users U
1
,
U
2
,
…
,
…
,
U
i
-
1
,
U
i
+
1
,
…
,
U
n to negotiate a session conference key with A. B returns {
(
b
1
,
B
1
,
T
1
,
β
1
)
,
…
,
(
b
i
-
1
,
B
i
-
1
,
T
i
-
1
,
β
i
-
1
), (
b
i
+
1
,
B
i
+
1
,
T
i
+
1
,
β
i
+
1
)
,
…
,
(
b
n
,
B
n
,
T
n
,
β
n
)
} to A, where x
=
k
1
+
⋯
+
k
i
-
1
+
k
i
+
1
+
⋯
+
k
n and b
1
=
a
P. A must broadcast B
i
=
(
k
i
b
1
,
…
,
k
i
b
i
-
1
,
k
i
b
i
+
1
,
…
,
k
i
b
n
) in round 2 such that (
k
1
+
k
2
+
⋯
+
k
n
)
P
=
(
x
+
b
)
P. Therefore, k
i
P
=
b
P and k
i
b
1
=
a
b
P.
Overall, we have that(17)
ɛ
′
≥
ɛ
q
0
,
t
′
≈
t
+
q
E
O
t
E
+
q
S
O
t
S
+
q
C
O
t
C
+
q
R
O
t
R
+
q
H
O
t
H
+
O
n
2
.Following a proof similar to that for the above theorem, we can show that the proposed interdomain key agreement scheme withstands key control attacks.


## 7. Discussions

In this section, we compare our schemes with the schemes of [15–19, 24–27] according to the properties shown in Table 1 and performance factors in Table 2. We prove that our scheme in single domain satisfies all security attributes in Section 6 and it can be easily extended to an interdomain version. Besides, we do our best to extend each scheme in [15–19, 24–27] to an interdomain one, but only the schemes [17, 18, 24, 25] can achieve this goal with little modification. Therefore, we use the straightforward way [38] to extend the remaining schemes [15, 16, 19, 26, 27] to interdomain versions for performance comparisons. The result is shown in Table 3.Table 1
Properties.
[24]
[18]
[15, 16]
[17]
[19]
[25]
[27]
[26]
Ours
Know session key security
YES
YES
YES
NO
YES
YES
YES
YES
YES
(Perfect) forward secrecy
YES
YES
Δ
NO
Δ
YES
YES
Δ
YES
No key-compromise impersonation
NO
NO
NO
YES
NO
NO
YES
NO
YES
No key control
YES
YES
YES
YES
YES
YES
YES
YES
YES
Δ: partial forward secrecy.Table 2
Performance comparisons in single domain.
Communication cost
[24]
[18]
[15, 16]
[17]
[19]
[25]
[27]
[26] (1)
[26] (2)
Ours
Round
2
2
2
1
1
3
3
1
2
3
Bandwidth
3
3
3
3
(
n
-
1
)
4
(
n
-
1
)
(
n
+
1
)
3
(
n
+
1
)
Computation cost
[24]
[18]
[15, 16]
[17]
[19]
[25]
[27]
[26] (1)
[26] (2)
Ours
Point addition
9
6
3
n
-
3
2
n
-
3
n
-
1
2
n
+
3
n
+
1
—
n
-
2
4
n
-
2
Scalar multiplication (G
1
,
G
2)
8
4
n
+
5
n
+
3
n
2
n
+
6
3
n
-
1
—
2
4
n
+
3
Scalar multiplication (G
T)
2
n
—
n
-
1
2
n
-
2
—
—
—
2
n
-
2
2
—
Pairing
4
4
4
2
n
+
1
1
n
+
5
4
n
-
4
2
n
-
2
4
2
Exponentiation
—
—
n
-
2
—
—
—
—
—
—
—
Increment/decrement of computation time
n
=
100
↓22%
↓19%
↓78%
↓98%
↑48%
↓97%
↓196%
↓98%
↓19%
—
Bandwidth: the total number of messages (points) sent by a user.
n: the number of users.
From [28], 1 exponentiation ≈ 240 scalar multiplications, 1 point addition ≈ 0.12 scalar multiplication, 1 scalar multiplication in G
1
≈
29 scalar multiplications, 1 scalar multiplication in G
2
≈ 1 scalar multiplication, and 1 pairing ≈ 10 exponentiations.Table 3
Performance comparisons in interdomain.
Communication cost
[24]
[18]
[15, 16]
[17]
[19]
[25]
[27]
[26] (1)
[26] (2)
Ours
Round
2
2
≤2
+
⌈
log
⁡
3
(
m
)
⌉
1
≤1
+
⌈
log
⁡
3
(
m
)
⌉
3
≤3
+
⌈
log
⁡
3
(
m
)
⌉
≤1
+
⌈
log
⁡
3
(
m
)
⌉
≤2
+
⌈
log
⁡
3
(
m
)
⌉
3
Bandwidth
3
3
<
3
+
5
m
(
m
-
1
)
3
<
(
n
-
1
)
+
5
m
(
m
-
1
)
4
<
(
n
-
1
)
+
5
m
(
m
-
1
)
<
(
n
+
1
)
+
5
m
(
m
-
1
)
<
3
+
5
m
(
m
-
1
)
(
n
+
1
)
Computation cost
[24]
[18]
[15, 16]
[17]
[19]
[25]
[27]
[26] (1)
[26] (2)
Ours
Point addition
9
6
3
n
-
3
2
(
n
-
m
)
-
1
n
-
1
2
n
+
m
+
2
n
+
1
—
n
-
2
3
n
-
3
Scalar multiplication (G
1
,
G
2)
8
4
n
+
5
n
+
3
n
2
n
+
6
3
n
-
1
—
2
n
+
4
Scalar multiplication (G
T)
2
n
—
n
i
-
1
2
n
-
1
—
—
—
≤(
n
-
1
)
+
k
≤2
+
k
m
-
1
Pairing
4
4
≤4
+
k
2
(
n
+
m
)
-
1
≤1
+
k
n
+
5
≤
2
n
-
2
+
k
≤(
n
-
1
)
+
k
≤4
+
k
m
+
1
Exponentiation
—
—
n
i
-
2
—
—
—
—
—
—
—
Increment/decrement of computation time
n
=
100
,
m
=
10
,
n
i
=
10
↑191%
↑204%
↓89%
↓94%
↓88%
↓89%
↓158%
↓95%
↓92%
—
m: the number of TAs.
n: the number of users.
n
i: the number of users in the ith TA, where i
=
1,2
,
…
,
m.
k
=
5
m
⌈
log
⁡
3
(
m
)
⌉.In the design of a conference key agreement scheme, the other researchers always divide the protocol into two main parts: the authentication stage and the stage of the construction of a common secret value. These proposed schemes [15–19, 24–26] all perform the authentication stage first and then make a session conference key, so that they have some problems in security. We have showed that [15–19, 24–26] are insecure in Section 3 because an adversary A can get the valid parameters in the authentication stage and replay them in different sessions. In particular, we design our protocol in inverse order such that users share a common secret value first and then run the authentication stage. If we only consider a single TA, some schemes are more efficient than our proposed scheme. However, none of them are secure.


## 8. Conclusion

Many researchers proposed two- or three-party identity-based authenticated key agreement schemes, but general multiparty authenticated key agreement schemes are rare. When the number of the members is more than three, the multiparty scheme is difficult to achieve both security and efficiency at the same time. In this paper, we proposed a novel efficient identity-based conference key agreement scheme and proved its security via formal method. Furthermore, our scheme can be extended to an interdomain one.Consider the application of key agreement among the employees in a company. The focus of the past papers is that how users interact under a single TA. It means that the employees of a company can negotiate a common session key when they want to organize a private conference. But now, our schemes provide more flexibility for the users. Even if the users register with different TAs, they can also negotiate a common session key easily. In other words, when two or more companies want to hold a conference, the employees from different companies can still compute a common session key by our interdomain key agreement scheme.Our conference key agreement can be applied to the ad hoc networks, too. In the wireless environment, reliable communication and authentication is desired. By performing our method, it is unnecessary for ad hoc sensors to store a large amount of data in advance and they can still negotiate a session key under mutual authentication. We can ensure that the transmitted messages are reliable and also secure against malicious sensors in wireless networks.



---

*Source: 865367-2014-11-30.xml*