Multiparty Key Agreement using Bilinear Map

Nam-Su Jho, Myung-Hwan Kim, Do Won Hong and Byung-Gil Lee

ABSTRACT ⎯ A key agreement protocol is a now.

cryptographical primitive which allows participants to share a The most important requirement for a key agreement protocol
common secret key via insecure channel. In particular, a is authentication of participants involved in the protocol.
multiparty key agreement protocol is a key agreement protocol
Although the Diffie–Hellman key agreement protocol is very
that can manage arbitrary number of participants at once. In
the security point of view, authentication and forward secrecy simple and efficient without requiring any preparation for the
are the most important requirements in such protocols. One protocol, it is seriously vulnerable to the well known man–in–
interesting problem in key agreement protocols is to construct a the–middle–attack and is not sufficient to accomplish the
multiparty key agreement protocol satisfying the above security purpose of key agreement protocols. The reason is that the
requirements with minimal number of communication rounds Diffie–Hellman key agreement allows no authentication of
(i.e. one-round). In literature, there has been no one-round participants. Formal definitions of various security requirements
multiparty key agreement protocol that satisfies both of
are given in the next section.
authentication and forward secrecy.
In this paper, we present a new multiparty key agreement
protocol using bilinear map and adopting the key generation In the early days, improving on Diffie-Hellman key agreement
center. The protocol demands only one–round for arbitrary protocol adopting authentication is mainly researched. MTI
number of participants to share a group key and satisfies both protocol [2] in 1986 and MQV protocol [3] in 1998 are
authentication and (partial) forward secrecy. representative results. However, only heuristic security analyses
are given. After formal security model is proposed by [4], [5] and
Keywords⎯Multiparty Key Agreement, Authentication,
Bilinear Map, Weil Pairing [6], attempts of constructing provably secure key agreement
protocol are made. Protocol proposed by Jeong, Kats and Lee [7]
in 2004 is an example of such a key agreement protocol.
I. Introduction Identity–Based key agreement protocol is another topic which
attracts one’s attention. Smart [8] and Smart [9] in 2002
A key agreement protocol is a cryptographical primitive which
proposed ID-based key agreement protocols modifying MTI key
allows participants to share a common secret key via insecure
agreement protocol using the idea of identity based encryption,
channel. The Diffie–Hellman key agreement protocol [1] in
independently. This works become the basis of other ID-based
1976 is the first practical solution to the key agreement problem.
key agreement protocols proposed later.
After Diffie and Hellman's work, many security requirements
On the other hand, multiparty key agreement protocols – key
and various solutions have been discussed and proposed up to
agreement protocols which can manage a group containing
. Nam-Su Jho (email: nsjho@etri.re.kr) – Electronics and Telecommunications Research Institute, arbitrary number of participants – attract attention and various
Daejeon, Korea. methods to generalize two–party key agreement protocols to
. Myung-Hwan Kim (email: mhkim@math.snu.ac.kr) – Department of Mathematical Sciences, multiparty protocols have been proposed.
Seoul National University, Seoul, Korea. Ingemarsson, Tang and Wong made a protocol which is
. Do Won Hong (email: dwhong@etri.re.kr) – Electronics and Telecommunications Research natural extension of the classical Diffie–Hellman key agreement
Institute, Daejeon, Korea. protocol, 1982 [10]. Similarly to the classical DH key agreement,
. Byung-Gil Lee (email: bglee@etri.re.kr) – Electronics and Telecommunications Research Institute, this protocol is secure against a passive adversary only. In 1995,
Daejeon, Korea. Burmester and Desmedt [11] proposed a group key agreement
protocol which reduces round complexity (roughly, the number map comes into the spotlight and a number of pairing-based
of communication exchanged) remarkably. The modified protocols were proposed
version and the security proof of this protocol is presented in
2005 by Burmester et al. [12] adopting the formal security model. The organization of this paper is as follows: In section 2, we
Bresson, Chevassut and Pointcheval [6], [13], [14] set up the summarize security requirements for key agreement protocols
formal security model about multiparty key agreement protocol and security model. In section 3, we will describe the
and provided protocols which are provably secure authenticated construction of our new key agreement protocol OAK. The
group key agreement protocols. Recently, Abdalla, Bresson, security proof is presented in section 4 and finally the section 5
Chevassut and Pointcheval [15] proposed password–based key concludes this paper.
agreement, i.e. pre–shared (or distributed) password is used to
authenticate each participant.
II. Security Definitions and Model.
In order to measure the efficiency of key agreement protocols, 1. Authentication
the computation complexity, the communication complexity and
the round complexity are often considered. The computation Roughly, authentication of key agreement protocol has two
complexity and the communication complexity denote the aspects, one is authentication of participants and the other is
amount of computations of each participant to obtain common authentication of the computed session key.
secret session key and the amount of broadcasted messages of
each participant to other ones, respectively. A round means one A. Implicit Key Authentication
broadcasting session in which every participant can cast The implicit key authentication is based on the authentication
messages to others but all at once. Therefore, in a one round key of participants for preventing impersonation (for example man-
agreement protocol for example, all the messages necessary in-the-middle) attack. The purpose of the attacker is sharing
should be cast by participants in parallel. The round complexity secret session key without detecting of legitimate participants
is simply the number of rounds needed to complete the protocol. by replacing legitimate participant. Thus, generally the attacker
Minimizing round complexity is very important in designing key is not considered to be a malicious participant. The implicit key
agreement protocols as well as reducing other complexities. authentication requires that each legitimate participant is
To now, there are few one round multiparty key agreement assured that no other one except for other legitimate
protocols proposed and the one proposed by Boyd, Manuel and participants learns the established group key.
Nieto [16] is the only one which is proved to be secure as an
implicitly authenticated protocol. The protocol of Boyd et al. is a B. Key Confirmation
simple combination of a public key encryption system and a
Key confirmation is the other aspect of the authentication. A
signature system. However, this protocol does not satisfy
key agreement protocol is said to provide key confirmation if
forward secrecy and explicit key authenticated. Since the
each participant is assured that the other legitimate participant
protocol by Boyd et al. does not satisfy some security
actually has possession of the same secret key to the key
requirements including forward secrecy, it is not regarded as a
computed by him/her. In key confirmation security, it must be
good enough solution. So it is still open to construct a one round
considered the case that the attacker is a malicious participant
multiparty key agreement protocol satisfying enough security
of the protocol. Because it is usually assumed that the attacker
requirements.
can control communication channel completely, the attacker
always can prevent participants from sharing the secret session
In this paper, we proposed new multiparty key agreement
key. So key confirmation considers the case of that key
protocol, OAK, which requires just one round without
agreement protocol is finished with no error detected.
dependency on the number of participants. The OAK satisfies
the (partial) forward secrecy and provides the key confirmation
C. Explicit Key Authentication
secrecy. However, the cost of minimizing the round complexity
is to bring in the trusted key generation center, which is used A key agreement protocol satisfying both implicit
often in ID-based key agreement protocols. A bilinear map authentication and key confirmation is called an explicit
defined on an elliptic curve [17], [18], [19] is a main building authenticated key agreement protocol.
block used to construct new protocol. Joux's key agreement [20]
was the first positive result which used a bilinear map to 2. Forward Secrecy
construct application in cryptography. After this work, a bilinear
 The basic idea of this security notion is to maintain security compromised. Note that since authentication of participants
of current communication sessions from the event which may depends on knowledge of long-term secret keys, the adversary
occur in the future. Note that compromised long-term keys who compromises a long–term secret key may impersonate the
make the attacker impersonate without detection in the future compromised participant. However, no key–compromise
protocol runs. impersonation security guarantees that the attacker cannot
impersonate other participants except compromised one.
A. (Partial) Forward Secrecy
C. No Key Control Secrecy
A key agreement protocol is forward secure if the long-term
secret keys of participants or more are compromised, the A key agreement protocol satisfying this security notion is
secrecy of previous session keys is not affected. The word sometimes called contributory group key agreement. No key
‘partial’ means that we assume that the attacker can control security means that shared secret session key must be
compromise some, but not all, participants. determined by all participants who involved in key agreement
protocol and no one can enforces some specific value on a
B. Perfect Forward Secrecy shared secret session key.
A key agreement protocol is perfect forward secure if the
long–term secret keys of all participants are compromised, the 4. Security Model
secrecy of previous session keys is not affected. In this section, we describe the formal security model for
security analysis. This model is following security models of
C. Weak Forward Secrecy Bresson et al. [6] and Dutta et al. [21], [22]. In these models,
A key agreement protocol is weak forward secure if the each user in the key agreement protocol is considered as an
protocol is forward secure against the attacker who can oracle and every interaction of the adversary with users is
compromise only long–term secret keys from participants. considered as an oracle query. We assume that the adversary
has the ability of controlling the network completely.
D. Strong Forward Secrecy Let S = {u1, u2, …, ut } be a set of all users. Without loss of
generality, we can give the unique number to each key
A key agreement protocol is strong forward secure if the
agreement instance although key agreement instances may
protocol is forward secure against the attacker who can
occur simultaneously. Let Πl be the l-th key agreement instance
compromise internal states of participants additionally to long–
and Sl be the subset of S which contains every user involved in
term secret keys. Note that this notion is meaningful where
the l-th key agreement instance with | Sl | = nl ≤ t.
participants has some reusable data, also called {\it ephemeral
More precisely, Πl is the set of instance of users who are in
keys}, in his/her internal memory. It is also assumed that each
Sl , let Πlu be the instance of user u in the l-th session. Mlu means
participant can erase ephemeral keys if it will be no longer used,
the message which is broadcasted by Πlu and Ml means the
so an attacker can compromise some, but not all, ephemeral
whole message which is broadcasted in the instance Πl. In
keys used in the past.
other words, Ml is the all messages in the l-th session.
And Kl is the shared secret session key in the l-th session. For
3. Other Security Requirements each user ui, ki means the user's long-term secret key and rl,i
Followings are often referred security requirements: means the users ephemeral key, i.e. random nonce used to
share the session key in the l-th session by the user ui.
A. Known Session Key Secrecy Followings are oracle queries which are executed by the
adversary:
A protocol is called satisfying known session key security, if
Eavesdrop(l) : This query models a passive attack, in which
the protocol is still secure against the adversary who knows
the adversary only eavesdrop messages among the users in Sl.
some other session keys. In other words, the knowledge about
The reply of this oracle is Ml.
some previous session keys gives no help to guess other
session keys.
Initiate(Sl) : This query models an active attack in which the
adversary initiates key agreement protocol among the users in
B. No Key-Compromise Impersonation Secrecy
Sl. Sl may be chosen by the adversary or randomly given. The
This means the compromise of a long-term secret key of a adversary obtains all messages among the users, i.e. the reply
participant doesn't imply that other participants' secret key is
of this oracle is Ml. FALSE otherwise.

Send(u, Sl, M’l) : This query models an active attack in The signature scheme Σ = (KG, SIGN, VER) is secure if it is
which the attacker send messages which can be originated or computationally impossible for any adversary to forge a
modified by the adversary to other user(s). Here, we simplify signature on any message (existential forgery) even under
this query as following: adaptive chosen–message attack. In other words, there is no
• Step1 : The adversary makes a message M’l. polynomial time algorithm with an input the public verification
• Step2 : Or the adversary intercepts the message Ml sent to key e outputs (m, σ) which satisfying VER(e, m, σ) = TRUE with
the user u ∈ Sl and modify to M’l . non–negligible probability, even it can query to signing oracle
• Step3 : The adversary sends M’l to the user u instead. at any time.
The reply of this oracle is Mlu.
2. Bilinear Map
KeyGen : This query models an active attack in which the
adversary contacts the KGC to obtain a long–term secret user Assume that G1 and G2 are two cyclic groups of prime order
key. The reply of this oracle is a long-term secret user key kj. p and P is a generator of G1, for convenience we’ll denote G1
Note that the KGC never issues same long–term key to two or as an additive group. A map e: G1 × G1 → G2 is a bilinear map
more users, i.e. the adversary can obtains kj for the index j if it satisfies:
which is never used. • Bilinear: for all P,Q ∈ G1 and a,b ∈ Z, we have
e(aP,bQ) = e(P,Q)ab.
Reveal(l) : This query models the event of leakage of a • Non-degenerate: e(P,P) ≠ 1.
particular session key to the adversary. The reply of this oracle By a bilinear group, we mean a group in which the group
is the session key Kl. operation can be computed efficiently and there exists an
efficiently computable bilinear map as above. Modified Weil
Corrupt(u) : This query models the corruption of the long– pairing [25] and Tate pairing [26] are the typical examples of
term secret key of the user u. The reply of this oracle is ku. Note bilinear maps which are defined on elliptic curves.
that in OAK the strong corruption is meaningless. So we make
only one corrupt model. 3. Construction
We now propose the new key agreement protocol which
Test(l) : The reply of this oracle is the real session key Kl if requires only one round to establish shared session key and
b=1 or a random key Rl if b=0, where b is randomly chosen bit satisfies explicit authentication. In literature there is no one-
by the Test oracle. This oracle is used to compute the round multiparty key agreement protocol which satisfies
adversary's ability to distinguish the real session key from a explicit authentication.
random key. The adversary can query this oracle at any time The One–round Authenticated Key agreement protocol
but only once. (OAK) consists of following three algorithms: Setup,
KeyGeneration and KeyAgreement.
III. New Protocol
A. Setup
1. Signature Scheme
Setup is executed by the key generation center KGC which is
Let k be the security parameter. A digital signature scheme assumed to be a trusted party.
Σ=(KG, SIGN, VER) consists of the following three algorithms: • With the security parameter λ, the KGC chooses a prime q
• The key generation algorithm KG is a probabilistic and generates two groups G1 and G2 of order q, where G1
algorithm with an input the security parameter λ and outputs is a bilinear group with a bilinear map e : G1 × G1 → G2.
(e, d) the secret key and public key pair. • The KGC randomly chooses P which is a generator of G1,
• The signing algorithm SIGN is a probabilistic algorithm with α and s from Zq* and an integer t.
an input the secret key and the message (d, m) outputs the • The KGC publishes G1, G2, e, t, P, αP, α2P, …, αtP as
signature of m, σm. public information of the protocol. Note that α and s is the
• The verification algorithm VER is a deterministic algorithm secret information that only the KGC knows.
with an input the triple verification key, message and
signature (e, m, σ), outputs TRUE if the signature is valid or B. Key Generation
 If a participant wants to join the protocol, he/she sends verifications of signatures and 1 bilinear map computation
his/her own information with which the KGC can identify are required.
him/her and his/her own verification key. After identifying
process, the KGC gives the secret key to him/her as followings: [Remark] Checking reliability of messages is required when
• Assume that each participant u runs KG to obtain a pair of participants want key confirmation property. Note that message
signing and verification key (du, eu) before the reliability can be checked with computing maximum 2(n-2)
KeyGeneration process. pairing computations and (n-3)n additions in G1.
• Each participant u is assigned unique identifier I(u) (an
integer between 1 and t) and KGC computes sαI(u)P. [Remark] In the viewpoint of computation, this protocol is
• The KGC gives the secret key sαI(u)P, to the participant u not efficient comparing to other group key agreement protocols.
and publishes the participant's identifier together with the The main contribution of this paper is the optimization of
verification key eu. round complexity satisfying security requirements.

C. Key Agreement
IV. Security
It is assumed that each session has a unique session identifier,
the session number l. Let Sl be a set of participants who want to 1. Assumptions
agree a secret session key in the l-th session.
• Each participant u in Sl randomly chooses ru∈Zp and A. Discrete Logarithm Assumption
broadcasts Mu = {mu,v = ruαt+1-I(v)P | v∈Sl , v≠u} together
with the signature σu = SIGN(du, l | Mu) to all other users. Let Gen(1λ) be an algorithm which generates a λ-bit prime q
• Each participant checks message integrity verifying the and a multiplicative group G = <g> of order q. Then the
signatures. If there is an unverifiable message then discrete logarithm assumption says that for all probabilistic
KeyAgreement outputs FAIL and terminates. polynomial time adversary A,
• Optionally, each participant may check message Pr[(q,g) ← Gen(1λ); A(q,g,y) = x : gx = y]
reliability of Mu = {mu,v | v∈Sl , v≠u} by verifying the
is negligible.
equations e(αt+1-I(v')P, mu,v) = e(αt+1-I(v)P, mu,v'). If
KeyAgreement finds some unreliable message, it outputs
B. Bilinear Diffie-Hellman Assumption
FAIL and terminates.
• Each participant u in Sl computes Σv∈Sl rvαt+1-I(u)P and the Let Gen(1λ) be an algorithm which generates a λ-bit prime q
secret session key, Kl = e(sαI(u),Σv∈Sl rvαt+1-I(u)P) = and two groups G1 = <P> and G2 of order q, where G1 is a
Exp[e(P,P), αt+1s(Σv∈Sl rv)], where Exp[a,b] means ab. bilinear group with a bilinear map e : G1 × G1 → G2.
• After computing the session key, each user ui erases Additionally, we assume that the discrete logarithm problems
his/her own random nonce ri. (DLP) in both G1 and G2 are hard. The bilinear Diffie-Hellman
Note that the protocol adopts the KGC for generating of assumption says for all probabilistic polynomial time adversary
public keys and each user's secret key similarly to ID-based A,
key agreement protocols. By necessity, we assume that the Pr[(q,P) ← Gen(1λ); A(P,aP,bP,cP) = x:x = e(P,P)abc]
KGC is trusted. Because the leakage of the secret key of the
is negligible.
KGC breaks forward secrecy and if the KGC itself is
compromised then the protocol cannot be guaranteed to be
C. Bilinear Diffie-Hellman Exponent Assumption
secure no longer. Even though the assumption is the cost for
reducing the round complexity to be optimized, it is somewhat In 2005, Boneh et al. [23] proposed bilinear Diffie–Hellman
expensive and removing this assumption is the next step of this Exponent (BDHE) assumption to generate an efficient HIBE.
work. Later BDHE assumption is used in construction a broadcast
encryption system [24] and considered as a general assumption
4. Efficiency in a bilinear group.
Let Gen(1λ) be an algorithm which generates a λ-bit prime q
• Rounds: One, regardless to the size of Sl . and two groups G1 = <P> and G2 of order q, where G1 is a
• Communication: Each user broadcasts n-1 elements of G1. bilinear group with a bilinear map e : G1 × G1 → G2.
• Computation: For each user, n scalar multiplications in G1, Additionally, we assume that the discrete logarithm problems
n-1 additions in G1, 1 computation of signature, n-1
(DLP) in both G1 and G2 are hard. The t-BDHE problem in G1
is stated as follows: given a vector of 2t + 1 elements
( Q, P, αP, α2P, …, αtP, αt+2P, …, α2tP) ∈ G12t+1 Let YP,Q,α,t,I = (αP, …, αtP, { αt+I | i which is not in I }, {α1-iQ
as input, output Exp[e(P,Q), αt+1] ∈ G2. Note that the input | i ∈ I }). The t-MBDHE assumption says that for all
probabilistic polynomial time algorithm A and all index set I,
vector is missing the term αt+1P so that the bilinear map seems
to be of little help in computing the required Exp[e(P,Q), αt+1]. following probability is negligible.
The t-BDHE assumption says that for all probabilistic Pr[(q,e,P)←Gen(1λ),Q←RG1,α←RZq*;
polynomial time algorithm A, the probability that A(P, YP,Q,α,t,I ) = x : x = e(P,Q)t+1]
Pr[(q,e,P)←Gen(1λ), Q ←R G1, α ←R Zq*; The definition of the decisional t-MBDHE assumption is
A (Q, P, αP, …, αtP, αt+2P, …, α2tP) = x : x = e(P,Q)t+1] similar to that of the decisional t-BDHE assumption. The
decisional t-BMDHE assumption holds in G1 if for all
is negligible.
probabilistic polynomial time algorithm B and all index set I,
The decisional version of the t-BDHE problem in G1 is
the advantage of B
defined analogously. Let YP,α,t = (αP, …, αtP, αt+2P, …, α2tP). A
probabilistic polynomial time algorithm B that outputs b ∈
{0,1} has advantage ε in solving decision t-BDHE in G1 if
| Pr[B(P, Y P,Q,α,t,I, e(αt+1P,Q)) = 0] - Pr[B(P, YP,Q,α,t,I, R) = 0] |
is negligible.
|Pr[B(Q,P,Y t+1
P,a,t, e(a |
P,Q))=0] - Pr[B(Q,P,YP,a,t, R)=0] ≥ε
2. Basic Theorems
where the probability is over the random choice of generators
P, Q in G1, the random choice of a in Zp*, the random choice To prove the security of proposed OAK protocol, we define
of R ∈ G2, and the random bits consumed by B. following adversaries:
The decisional t-BDHE assumption holds in G1 if no • Ai is a polynomial time algorithm for a fixed integer i (1 ≤
probabilistic polynomial time algorithm has non–negligible i ≤ t) with an input
advantage in solving the decisional t-BDHE problem in G1

D. Modified Bilinear Diffie–Hellman Exponent Assumption

outputs TRUE if R = Exp[e(P,Q), rαt+1] or FALSE
Generalizing BDHE assumption, we obtain Modified
otherwise. Adv(Ai) means the advantage of Ai i.e.
Bilinear Diffie–Hellman Exponent (MBDHE) assumption.
Adv(Ai) = | Pr[ the answer of Ai is correct ] – 1/2 |
Security of our system is mainly based on MBDHE
assumption. • AI is a polynomial time algorithm for a fixed set of index
Let Gen(1λ) be an algorithm which generates a λ-bit prime q I ⊆ {1, …, t} with an input
and two groups G1 = < P > and G2 of order q, where G1 is a
bilinear group with a bilinear map e : G1 × G1 → G2.
Additionally, we assume that the discrete logarithm problems
(DLP) in both G1 and G2 are hard.
Define the t-MBDHE problem in G1 as follows: given a outputs TRUE if R = Exp[e(P,Q), rαt+1] or FALSE
vector of 2t + 1 elements otherwise. Similarly, Adv(AI) means the advantage of AI.
• A’I is a polynomial time algorithm for a fixed set of index
I⊆ {1, …,t} with an input
as input, output Exp[e(P,Q), αt+1] ∈ G2, where I is an set of
integers such that {1}⊆ I ⊆ {1,2,…, t}. Note that for any 1 ≤
i ≤ t one of αt+iP or α1-iQ is missing in the input vector so that
the bilinear map seems to be of little help in computing the
required Exp[e(P,Q), αt+1] directly. outputs TRUE if R = Exp[e(P,Q),rαt+1] or FALSE
Note that for I = {1} we have the t-BDHE problem so we otherwise. Similarly, Adv(A’I) means the advantage of A’I.
can consider t-MBDHE problem as a generalization of t-
BDHE problem. Following is an example of an input for t- Theorem 1
MBDHE problem where t=5, I = {1,4}: Adv(Ai) is negligible under t-BDHE assumption.
 BDH assumption.
(Proof) Suppose there exists a Ai such that Adv(Ai) ≥
1/f(k) ,where f(·) is a polynomial. Then we can make a (Proof) To prove this theorem we need to define new
polynomial time algorithm which attacks t-BDHE problem adversary.
with the advantage greater than 1/f(k). • A0 is a polynomial time algorithm with an input (P, aP,
B is an adversary who wants to attack t-BDHE problem. So bP, cP, e(P, P)acs, R) which distinguish R from e(P, P)abs.
B is given a problem instance: Let Adv(A0) be the advantage of A0.
(Q, αP, α2P, …, αtP, αt+2P, …, α2tP),R
B chooses random r and computes Step 1: Under the BDH assumption, Adv(A0) is negligible.
rαt-iP, rαt-i+1P, …, rαtP, rαt+2P, …, rα2t+1-iP. Suppose that there exists a polynomial time algorithm A0
Note that i is an integer between 1 and t so all of above can be with Adv(A0) is non-negligible. We can make following
computed from the input for B and chosen r. Then B gives A polynomial time algorithm B which attacks BDH problem with
the following input: the non-negligible advantage.
From the input (P, aP, bP, cP, R), B choose random r and
computes rP and e(aP,cP)r = e(P, P)acr. B gives (P, aP, bP, rP,
e(P, P)arc, R) to A as an input. Then A distinguish R from e(P,
Finally, B outputs TRUE if A outputs TRUE or FALSE P)abc with non–negligible advantage. This is contradiction to
otherwise. the BDH assumption.
Now we compute the advantage of B with above attack.
With an input described above A can distinguish R from Step 2: With the assumption of Adv(AI) is negligible (let
Exp[e(P,Q), rαt-iαi] = Exp[e(P,Q), rαt+1] with the advantage Adv(AI) = εI), Adv(AI’) is also negligible.
greater than 1/f(k). Because in this attack the advantage of B is Suppose that there exists a polynomial time algorithm AI’
same to the advantage of A, Adv(B) is also greater than 1/f(k). with non-negligible advantage. Then we can construct A0 with
So, Adv(Ai) must be negligible under t-BDHE assumption. □ non-negligible advantage. With an input (P, aP, bP, cP, e(P,
P)acs, R), A0 chooses random x and computes followings:
Theorem 2
Adv(AI) is negligible under t-MBDHE assumption.

(Proof) With similar arguments, we can prove this theorem.

Suppose that there exists a polynomial time algorithm A with and gives it as input to A’I.
an index set I ⊆ {1, …, t}. Then we can construct a Note that e(P, P)acs is not a proper input. But, from the
polynomial time algorithm B which attacks t-MBDHE Theorem2, A’I cannot distinguish this input from a proper one.
problem with I' := {i-x+1| i ∈ I}, where x is the smallest Therefore, A’I works ordinarily and finally distinguishes R
element of I. from e(P, P)abs with non–negligible probability. This is
For a given input contradiction to the result of Step1 above. Therefore, Theorem3
is proved. □

3. Forward Secrecy
B randomly chooses r and computes following
Theorem 4
The proposed key agreement protocol, OAK, satisfies
(partial) forward secrecy against the strong corruption.
Note that rαt+1-x+iP is in fact r times αt+i'P and αx-iQ is exactly
same to α1-i'Q. B outputs TRUE if A outputs TRUE or FALSE In OAK, each user erases the random exponent after
otherwise. Since the advantage of B is same to the advantage of computing the session key. It is can be done because the
AI , Adv(AI) cannot be less than 1/f(k) for any polynomial f(·) random exponent is never reused in the future. And the
under t-MBDHE assumption. □ adversary cannot obtain any more information from the strong
corruption. So we can assume that the reply of Corrupt query
Theorem 3 is just the long-term key of participant.
If Adv(AI) is negligible, then Adv(A’I) is negligible under
 To prove the forward secrecy, we consider following attack [Remark] The OAK does not satisfy perfect forward
scenario: The adversary Af chooses a user u and do Corrupt(u) secrecy. Since the adversary can compute previous session
query. After that, Af chooses the session index l which satisfies keys with two long-term secret keys assigned to the
the condition that u is contained in Sl. Af do Test(l) query to participants who are involved to share the session key.
obtain the challenge. The challenge is Kl if the random bit b
chosen by Test oracle is 1 or Rl otherwise. In this attack, the 4. Authenticity
purpose of the adversary is to distinguish the shared session
key Kl from a randomly chosen Rl with the same length which The authenticity of OAK is guaranteed by following two
are the reply of the oracle Testl. The Af is allowed to query to theorems :
Eavesdrop, Initiate, KeyGen, Reveal and Send oracles freely at
any time. Note that Reveal(l) query is trivially forbidden. Theorem 6
In this attack model, we may ignore Initiate and Send The OAK is an implicit authenticated key agreement
queries. Since the reply of these oracles are information protocol under the t-MBDHE and BDH assumptions.
theoretically independent to Kl and gives no help to distinguish
the Kl. Except Eavesdrop(l), Eavesdrop queries are also helpless. Theorem 7
Here, to ignore Eavesdrop queries, we assume that the The OAK satisfies key confirmation security under the
adversary knows Ml already. Since the reply of the Reveal unforgeability of the signature scheme.
can be duplicated by the Af with randomly chosen exponent,
we include one reply of Reveal as an input of Af. To prove the Theorem6, we consider the adversary Aa who
wants to learn a session key Kl without participating in Sl.
Lemma 5 The Aa chooses the user set Sl and do Initiate(Sl) query to
Let ri be the random exponent of u = ui used in the session l obtain the reply Ml. After that Aa do Test(l) query, the purpose
to share the session key Kl. Then the probability of Af to of the Aa is to distinguish the session key Kl form the random
distinguish Kl from Rl is same to the probability of Af to challenge Rl which is the reply of Test(l). Aa can do any other
distinguish Exp[e(P, P), sαt+1ri] from R'l, where Rl and R'l are queries freely in any time except Corrupt and Reveal(l) queries.
randomly chosen elements from G2. Since we assumed that the signature scheme is unforgeable and
the Aa is not a member of Sl , the Aa cannot success Send
(Proof) It is trivial since that if Af knows sαiP then Af can queries with non-negligible probability. So we can ignore Send
compute Exp[e(P, P), sαt+1rj] for j ≠ i and j ∈ Sl from Ml and queries. Since the reply of the Reveal can be duplicated by the
sαiP. So distinguishing Kl is equivalent to distinguishing Aa with randomly chosen exponent, we include one reply of
Exp[e(P, P), sαt+1ri] = Kl / Πj≠I Exp[e(P, P), sαt+1rj] □ Reveal as an input of Aa.
We can summarize the Aa as a polynomial time algorithm
From this lemma, we can summarize Af as a polynomial with the inputs: the public information
time algorithm with the inputs: the public information αP, α2P, …, αtP,
αP, α2P, …, αtP, a reply of the query Initiate(l)
a reply of the Eavesdrop(l) query { riαjP | i,j ∈Sl , i ≠ j },
{ riαjP | j ∈ Sl, i ≠ j}, replies of KeyGen queries
a long-term key { sαjP | for j which is not in Sl },
sαiP replies from the Reveal queries and a challenge Rl from Test
from the Corrupt(i) query, replies of KeyGen queries oracle.
{ sαjP | for j which is not in Sl } Therefore, Aa is a polynomial time algorithm with input
a reply from the Reveal query
{ r'αjP | j ∈ Sl , i ≠ j }, Exp[e(P, P), r'sαt+1],
and a challenge Rl from the Test oracle. Therefore, Af is exactly
same to the A'I defined in the section IV–2.
Theorems in the section IV–2 say that Af cannot distinguish
Kl from Rl under t-MBDHE and BDH assumptions. Note that and replies of Reveal queries to distinguish Exp[e(P, P), sαt+1
if we restrict A not to query KeyGen query then OAK is (r1 + r2 +…+ rn)] from Rl. And let A1 be a polynomial time
forward secure under t-BDHE and BDE assumptions. algorithm with an input
 From the result of section IV-2 and above lemmas the
Theorem6 is proved under the t-MBDHE and BDH
and replies of Reveal queries to distinguish Exp[e(P, P), sαt+1r1] assumptions. Note that the A2 is exactly same to A'I in section
from R'l . IV-2.

Lemma 8 To prove the Theorem7, we define a proper form of the

There exists a polynomial adversary A1 with non-negligible message for the index set S as { rαiP | i∈S } first. It means that
advantage if there exists a polynomial time adversary Aa with the message vector is obtained by multiplying a random
non-negligible advantage. exponent to the vector consists public keys with the index i∈S,
i.e. {αiP | i∈S }. Note that if the message sent from each
(Proof) We suppose that there exits a polynomial time participant has proper form, each participant obtains same
algorithm Aa. Then for given input secret session key. And messages are forced to satisfy the
proper form, because that if one of messages has non-proper
form the key agreement protocol halts. Therefore, to disturb
participants from sharing the session key, although the
A1 chooses r2, r3, …, rn randomly and computes other vectors adversary is a malicious participant, is impossible.
{r2αt+1-j | j∈S, j ≠ i2}, …, {rnαt+1-j | j∈S, j ≠ in }. A1 can compute Trivially, if the adversary intercepts a message and discards it
Exp[e(P, P), sαt+1r2], …, Exp[e(P, P), sαt+1rn] trivially. then no key agreement protocol achieves key confirmation
Therefore A1 can set Rl = R'l ·Exp[e(P, P), sαt+1r2] ··· Exp[e(P, security. So we do not consider such an adversary here.
P), sαt+1rn]. And input
The Theorem6 and the Theorem7 imply that the OAK is a
explicit key agreement protocol.

5. Other Security Requirements

Security analyses about Known Session Key Secrecy, No
to Aa. Because Aa can distinguish Exp[e(P, P), sαt+1(r1 + r2 + … Key-Compromise Impersonation Secrecy and No Key Control
+ rn)] from Rl with non-negligible advantage A1 also can Secrecy are omitted here. Those are presented in the appendix.
distinguish Exp[e(P, P), sαt+1r1] from R'l with same advantage.
It is the end of proof of the above lemma. □ V. Conclusion

Now, consider the adversary A2 which is a polynomial time A key agreement protocol is a cryptographical primitive
which allows participants to share a common secret key via
algorithm with input
insecure channel. One interesting problem which is still
unsolved in key agreement is to construct an one-round
multiparty key agreement protocol satisfying various security
requirements. In this paper, we present a new multiparty key
to distinguish Exp[e(P, P), sαt+1r] from Rl. Note that for A2 the agreement protocol using bilinear map and adopting the key
Reveal queries are not allowed. generation center. The protocol demands only one–round for
arbitrary number of participants to share a group key and
satisfies both authentication and (partial) forward secrecy.
Lemma 9
There exists a polynomial adversary A2 with non-negligible
advantage if there exists a polynomial time adversary A1 with References
non-negligible advantage.
[1] W. Diffie and M. Hellman, “New Directions in
(Proof) To prove this lemma, it is sufficient to show the A2 Cryptography”, IEEE Transaction on Information Theory, IT-
can simulate Reveal queries from A1. Note that the reply of 22(6), 1976, pp. 644-654.
Reveal query can be constructed using public keys, a secret key [2] T. Matsumoto, Y. Takashima and H. Imai, “On Seeking
which can be obtained from KeyGen query and randomly Smart Public-key Distribution Systems”, Transactions of the
chosen exponent. □ IECE of Japan, E69, 1986, pp. 99-106
[3] L. Law, A. Menezes, M. Qu, J. Solinas and S. Vanstone,
An Efficient Protocol for Authenticated Key Agreement, [18] S. Lang, Elliptic Functions, Addison-Wesley, Reading,
Technical Report CORR 98-05, Department of C & O, 1973..
University of Waterloo, 1998. [19] J. Silverman, The arithmetic of elliptic curve, Springer-
[4] M. Bellare and P. Rogaway, “Entity Authentication and Verlag, 1986.
Key Distribution}, LNCS 773, Proc. CRYPTO '93, 1993, pp. [20] A. Joux, “One Round Protocol for Tripartite Diffie-
232-249. Hellman”, LNCS 1838, Proc. ANTS 4, 2000, pp. 385-394.
[5] M. Bellare and P. Rogaway, “Random Oracles are [21] R. Dutta and R. Barua, “Constant Round Dynamic
Practical : A Paradigm for Designing Efficient Protocols”, Proc. Group Key Agreement”, LNCS 3650, Proc. ISC '05, 2005, pp.
ACM CCS '93, 1993, pp. 62-73. 74-88.
[6] E. Bresson, O. Chevassut and D. Pointcheval, “Dynamic [22] R. Dutta and R. Barua. “Overview of Key Agreement
Group Diffie-Hellman Key Exchange under Standard Protocols”, Cryptology ePrint Archive, http://eprint.iacr.org/2005
Assumptions”, LNCS 2332, Proc. Eurocrypt '02, 2002, pp. /289, 2005.
321-336. [23] D. Boneh, X. Boyen and E. Goh, “ Hierarchical Identity
[7] I. R. Jeong, J. Kats and D. H. Lee, “One-round protocols Based Encryption with Constant Size Ciphertext”, LNCS 3494,
for Two-Party Authenticated Key Exchange”, LNCS 3089, Proc. Eurocrypt '05, 2005, pp. 440-456.
Proc. ACNS '04, 2004, pp. 220-232. [24] D. Boneh, C. Gentry and B. Waters, “Collusion
[8] N. P. Smart, “An Identity-based Authenticated Key Resistant Broadcast Encryption with Short Ciphertexts and
Agreement Protocol Based on the Weil Pairing”, Electronic Private Keys, LNCS 3621, Proc. CRYPTO '05, 2005, pp. 258-
Letters, 38, 2002, pp. 630-632. 275.
[9] M.. Scott, “Authenticated ID-based Key Exchange and [25] D. Boneh and M. Franklin, “Identity-Based Encryption
Remote Log-in with Insecure Token and PIN Number”, from the Weil Pairing”, LNCS 2139, Proc. CRYPTO '01, 2001,
Cryptology ePrint Archive, http://eprint.iacr.org/2002/164, pp. 213-229.
2002. [26] P. S. L. M. Barreto, H. Y. Kim and M. Scott, “Efficient
[10] I. Ingemarsson, D. T. Tang and C. K. Wong, “A Algorithms for Pairing-Based Cryptosystems”, LNCS 2442,
Conference Key Distribution System”, IEEE Transaction on Proc. CRYPTO '02, 2002, pp. 354-368.
Information Theory 28(5), 1982, pp. 714-720.
[11] M. Burmester and Y. Desmedt, “A Secure and Efficient
Conference Key Distribution System”, LNCS 950, Proc.
Eurocrypt '94, 1995, pp.275-286.
[12] M. Burmester and Y. Desmedt, “ A Secure and Scalable
Group Key Exchange System”, In Information Processing
Letters, 94(3), 2005, pp. 137-143.
[13] E. Bresson, O. Chevassut and D. Pointcheval,
“Provably Authenticated Group Diffie-Hellman Key Exchange
– The Dynamic Case”, LNCS 2248, Proc. Asiacrypt '01, 2001,
pp. 290-309.
[14] E. Bresson and D. Catalano, “Constant Round
Authenticated Group Key Agreement via Distributed
Computing”, LNCS 2947, Proc. PKC '04, 2004, pp. 115-129.
[15] M. Abdalla, E. Bresson, O. Chevassut and D.
Pointcheval, “Password-based Group Key Exchange in a
Constant Number of Rounds”, LNCS 3958, Proc. PKC '06,
2006, pp. 427-442
[16] C. Boyd, J. Manuel and G. Nieto, “Round-optimal
Contributory Conference Key Agreement”, LNCS 2567, Proc.
PKC '03, 2003, pp.161-174.
[17] G. Frey, M. Müller and H. Rück, “ The Tate Pairing and
the Discrete Logarithm Applied to Elliptic Curve
Cryptosystems”, IEEE Transaction on Information Theory Vol.
45, 1999, pp. 1717-1718.
 From the security of signature scheme, if the adversary is not
in the Sl, he cannot make a change of the session key. So we
Appendix assume that the adversary is a malicious user in the set Sl who
1. Known Session Key Secrecy want to make the session key a certain value R.
Because the adversary Ac cannot change the random
This security requirement is guaranteed by proof of the exponent which is chosen by other users, only possible
Theorem6. Note that in proving the Theorem6, we assume that scenario is following: Ac initiates key agreement protocol
the adversary Aa can query Reveal freely. This means that there among the set Sl which is selected by Ac, using Initiate(Sl)$
is no adversary who can distinguish the given session key from query. After receiving all messages from other users, let u2, …,
a random key although the adversary knows many other un, Ac chooses random r satisfying
session keys. Exp[e(P, P), rsαt+1] = R / Πj = 2, …, n Exp[e(P, P), rjsαt+1].
So, we can summarize this as a problem that for given R, R'
2. No Key-Compromise Impersonation Secrecy whether the Ac can choose r satisfying Rr = R' or not. As you
know this is an instance of the DLP problem. So it is not
Remind that no key-compromise impersonation security
possible that Ac can control the session key for a certain fixed
means the adversary who knows a long-term private key of a
value R with non-negligible advantage.
participant u cannot impersonate u', for u ≠ u'. Basically, the
security against impersonation attack is based on the security of
the signature scheme used. Here we claim that even in the case
of the adversary can forge the signature of other users, the
adversary cannot success the impersonation attack.
Because that if an adversary cannot success impersonation
attack to one user then trivially the adversary cannot success
impersonation attack to a set of users, we will consider an
impersonation attack to one user. Consider the adversary who
acts as followings: Aim chooses a target user u and executes
Initiate(Sl) query on the index set Sl which contains u. The
purpose of Aim is sharing the same key with u by sending
modified messages to u.
Let u = u1 and Sl = { u1, u2, …, un }. And suppose that the
message to u from Aim is

Assume that Aim successfully forges all signatures of these

messages. After u receives these messages u chooses r and
sends { r·Exp[α,t+1-i2]·P, …, r·Exp[α,t+1-in]·P } to Aim. And u
computes the session key Exp[e(P, P), rsαt+1] · Πj=2, …, n
Exp[e(P,mj,1), sαi] Because mj,1 are all chosen by Aim, we can
assume that Aim can compute Exp[e(P,mj,1), sαi] easily. At last
the problem is reduced to whether Aim can distinguish Exp[e(P,
P), rsαt+1] from a random with the inputs { r·Exp[α,t+1-i2]·P,
…, r·Exp[α,t+1-in]·P } and the replies of some oracle queries.
Note that Aim is same to A2 in the section IV-4. From the
result of the section \ref{groundwork} we can deduce the Aim
cannot distinguish this with non-negligible advantage.

3. No Key Control Secrecy