International Symposium on Information Theory and its Applications, ISITA2008
Auckland, New Zealand, 7-10, December, 2008

A Group-Key Agreement Protocol Secure against The Malleability Attacks
Seiko Arita† and Akihiko Sakuma‡
Institute of Information Security
2-14-1 Tsuruya-cho Kanagawa-ku Yokohama-shi Kanagawa, JAPAN†‡E-mail: arita@iisec.ac.jp
E-mail: dgs074106@iisec.ac.jp

Abstract. This paper treats group key agreement protocols (GKAP). In group key agreement, it is needed
and important to consider existence of malicious insiders. In this paper, we show a GKAP that is UC-secure
even if some of group members behave maliciously andattempt the malleability attacks that is the adversary
contorol the session-key as desired. So our group key
agreement protocol does not allow the adversary tocontrol the session-key, and maintain not only the key
freshness, but also the key authentication and the key
integrity. Our protocol is eﬃcient enough for practicaluses, being composed of 2 rounds and n messages forn-party groups.

1. Introduction
Background:A group key agreement protocol(GKAP, in short) is one of the most important andprimitive cryptographic protocols. Recently, more concerns have been emerging of GKAP [1]. Informally,
GKAP has three basic requirements: key freshness,
key integrity and key authentication. The key freshness requires a generated session-key by a session ofa protocol to be independent from other session-keys
generated by other sessions of the protocol. The key
integrity means all session-keys of honest parties resulting from a session of a protocol must be the same. And
the key authentication requires the secrecy of sessionkeys, i.e., the outsiders cannot only obtain the valueof the session-keys but also any information of sessionkeys by eavesdropping conversations of GKAP among
the parties.
Historically, a key agreement protocol (KAP) is ﬁrst
considered and made use of in a two-party case, suchas the famous Diﬃe-Hellman KAP. The formal securityof the two-party KAP is deﬁned and proved by Bellare
and Rogaway [2]. [2] deﬁnes a notion of Session-key
indistinguishability (SK-security) of two-party KAP.
Boyd and Nieto [3] showed a natural generalizationof the SK-security to the cases of GKAP and showed aSK-secure GKAP (we call the protocol BN), assuming
a broadcast channel. However, later it turned out that
the SK-security is not suﬃcient for security of GKAP.
We need to consider insider attacks more carefully in
the GKAP case. For example, it is possible that malicious insiders can make a selected honest party alone
in GKAP, resulting violation of the key integrity.
Katz and Shin [6] cast the security of GKAP into
the framework of Universal Composability (UC)[4]in order to consider the eﬀects of insider attacks
against GKAP. UC-framework deﬁnes security of cryptographic protocols by ensuring that the target protocol mimics the behavior of a corresponding ideal
trusted third party, called an ideal functionality, under
any adversarial environment. [6] deﬁnes an ideal functionality FKS05 of GKAP and gives a generic compiler
that takes a SK-secure GKAP and transforms it into a
UC-secure GKAP. However, If any party is corrupted,
the ideal functionality FKS05 allows the malicious insiders to choose a value of the session-key as they want,as long as it is the same for all parties in the group. So,
the key freshness is violated.
The Malleability Attacks: Desmedt et al.[5] shows
the malleability attack that aims to ‘cancel’ the contributions of the honest parties to and violate the key
freshness. and generate the session key as desired. The
attack proceeds as follows. In the protocol proceeding,the corrupted parties (i.e., malicious insiders) wait for
the honest parties to send messages containing theircontribution to the session-key. The corrupted parties use this information to compute their ‘bad’ protocol messages adaptively as some function of the honest
party’s messages, in order to ‘cancel’ the contributionsof the honest players and ﬁx the session-key as desired.
It means that the key freshness is violated.
Such an attack by the malicious insiders can allow
a collaborating outside eavesdropper to know some information on the session key even if the insiders areshielded. Now we describe one scenario of the collaborating Attacks[5]. The collaborating attacks proceed

as follows. The adversary A is a pair of the malicious
insider AI and the outside eavesdropper AO . Before
the GKAP execution, A = (AI , AO ) (the insider andthe outsider) chooses the session-key as desired. In the
protocol proceeding, the insider generates his ‘bad’ protocol messages in order to compute the session-key as
desired. After the GKAP ends, honest parties establish
the private channel using the session-key computed by
the GKAP. Since the outside eavesdropper AO knows
the session-key, he can open this private channel.
Here it is important that such attacks may be undetectable by the honest parties. The malleability attack
may apply to GKAPs that securely realize the Katz
and Shin’s functionality FKS05 , simply because FKS05
does not consider any malleability attacks at all, as
noted above.

where AI is the shielded-insider and AO is the outside eavesdropper, respectively. The attack model is
described by the game that has three stages and runs
as follow.

Our contribution: In this paper, we deﬁne an ideal
functionality of GKAP that takes the malleability attacks into consideration. Then, we show a GKAP thatrealizes that ideal functionality. Our GKAP is the ﬁrst
one that maintains UC-security in a meaningful way
even if malicious insiders attempt the malleability attacks. It is eﬃcient enough for practical uses, composedof 2 rounds and n messages for n-party groups.

3. Stage 3 (Adversary goal): We say that theadversary A(= AI , AO ) wins, if there exist somehonest party computes κ as the session-key. Otherwise (no party computes κ or all of the honest
party aborts) A lose.

Setup: We assume the following setup throughout
the paper. 1. The Broadcast Channel: Parties use
cryptographic broadcast channel to send and receive
messages. 2. The authenticated-link model (AM): An
adversary cannot inject or change messages without being detected. 3. The common reference strings (CRS).
4. A static adversary : The adversary may corrupt
some parties only at the beginning of protocols.

2. Adversary Model.
We use the shielded-insider model [5] to capture security against corrupted insiders collaborating with anoutside eavesdropper. The insiders can communicate
with the outsider only until the protocol begins, after
which the insiders are shielded, i.e. prevented from further communication with the outsider. Then insiders
can initiate several protocols to exchange session-keys
with honest parties. The insiders try to choose their
protocol messages in order to correlate the session-keys
computed by honest parties. To defeat the freshness,the insider’s goal is to cause some honest parties tocompute the session-keys as desired.
Attack Model: The attacker A is modelled by a pair
(AI , AO ) of the collaborating insiders and outsiders,

The Key-Control Game
1. Stage 1 (Initialization):
AO chooses thesession-key κ randomly from the key space (Atthis point, AO dose not know the CRS of the target session). AO sends κ to AI .
2. Stage 2 (Protocol Executions): (After thispoint, AO can not communicate with AI .) The
malicious insider AI generates and sends ‘bad’
protocol messages in order to make some honest
party computes κ as the session-key.

Now we deﬁne some security notion. First we deﬁne
the security against the malleability attacks.
Deﬁnition 1 : [The security against The Malleability Attacks.] A GKAP Π is secure against themalleability attacks, if any adversary A = (AI , AO ) can
not win the key-control game excepting with the negligible probability.
The Key Integrity Game: We also deﬁne about
The Key Integrity Game. Informally, the malicious insider AI generates and sends ‘bad’ protocol messages inorder to make some honest party computes the wrong
session-key. Adversary goal is to cause some honest
parties to compute the diﬀerent session-keys. We saythat the adversary A = AI wins the game, if there
exists some party who computes diﬀerent session-keysfrom another party. Otherwise (all of the honest party
computes the same session key or aborts) A lose.
Deﬁnition 2 : [The security in the sense of The
Key Integrity.] A GKAP Π is secure in the senseof the key integrity, if any adversary A = AI can not
win the key integrity game excepting with the negligible
probability.
The adversary capability: We assume the following adversary capability throughout the paper. AO
does not know the CRS (include the public keys) at
the Stage 1, because of the GKAP not yet start. Notethat since we assume the static adversary, when the
GKAP start, some party is already corrupted, but westress that AO does not know the secret key (AI knowsthis).
3. An Ideal Functionality FGKE
This section we deﬁnen an Ideal Functionality.
Assumptions on PRF: We use pseudorandom function families with additional properties of collisionresistance. The collision-resistance of f means that noeﬃcient adversary can ﬁnd two diﬀerent seeds s, s0 resulting in the same values fs (v0 ) = fs0 (v0 ) of f at asamplable element v0 .
Deﬁnition 3 : [A Collision-Resistant PRF [6]]Let f = {fs }s be a PRF. We say that f is if there isan eﬃcient procedure Sample such that the probability
Pr[v0 ← Sample(1k ); s, s0 ← A(1k , v0 ) : s, s0 ∈ {0, 1}k∧s 6= s0 ∧ fs (v0 ) = fs0 (v0 )]is negligible in k for all polynomial-time adversaries A.
[6] proves the existence of a collision-resistance PRF
assuming the existence of a one-way permutation.
We deﬁne an ideal functionality FGKE of GKAP
that takes the malleability attacks into consideration,
as Figure 1. In the functionality FGKE , if all parties
in a group gid are uncorrupted, FGKE proceeds justlike FKS05 . However, if any party is corrupted, FGKE
proceeds as follows. For uncorrupted parties Pi , FGKE
chooses a random nonce Ni for Pi , and sends Ni to
the ideal-process adversary S. For corrupted parties
Pj , FGKE waits for S to send a nonce Nj for the corrupted parties Pj . To generate session-keys κ, FGKE
computes κ = fN1 (V1 ) ⊕ fN2 (V2 ) ⊕ · · · ⊕ fNn (Vn ) with
Vi = (sid||ssid||Pi ) using a pseudorandom function f ,and delivers (sid, ssid, gid, κ).
Note that against that functionality FGKE , it is difﬁcult even for malicious insiders (who can select Nj ) tocontrol the session-key κ using the malleability attacks,
because they cannot cancel the eﬀect of nonces Ni ofhonest parties by the way in which the pseudorandomfunction f is used to generate κ.
Now we show the GKAP which securely realizes theideal functionality FGKE is secure against the malleability attacks (satisfy the deﬁnition 1).
Proposition 1 Let {fs }s be a pseudorandom function(PRF) family. A GKAP which securely realizes theideal functionality FGKE is secure against the malleability attacks
Proof: Assume the GKAP Π securely realizes theideal functionality FGKE , there exists a simulator S andno environment Z can distinguish between real andideal-process model with a non-negligible advantage.
First we construct an environment Z execution. Z
simulates AO and waits AO sends κ. Z executes a
GKAP Π with input (sid, ssid, gid) collaborating withan adversary A with input κ. The uncorrupted party
outputs the session-key κ0 , if κ0 = κ then Z output realmodel else ideal-process model.
Suppose there exists a simulator S described above,
we show a inconsistency to construct a seed inverter B
for PRF using such S. A seed inverter B function as
follows. B sends the value v to the challenger C. C
computes fN (v) and sends to B. B guess the seed N .
The seed inverter B proceeds as follows with input a security parameter k and w = (sid, ssid, gid). B
chooses a currupted party Pj∗ from gid randomly. B
sends the value v = (sid||ssid||Pj∗ ) to the challenger C.
C returns κ = fN (v) to B.
B choose random nonces for uncorrupted parties:RkNi ←− {0, 1} (i = 1, . . . , n(6= j)). Then B executes Z
with input w = (sid, ssid, gid) and κ⊕fNi (Vi ) together
with the simulator S with input κ ⊕ fNi (Vi ). B sends
nonces Ni (i = 1, . . . , n(6= j)) for uncorrupted parties.
If S outputs a nonce Nj , then B outputs Nj as the seedelse aborts.
Since S can output Nj s.t. κ = fNi (Vi ) ⊕fNj (Vj ) (i = 1, . . . , n(6= j)) with a non-negligible advantage, if B succeed to guess corrupted party, B canﬁnd the seed of PRF. It is a inconsistency. ¤Proposition 2 The GKAP which securely realizes theideal functionality FGKE is secure in the sense of the
key integrity.
Note that in the ideal functionality FGKE the key
integrity is always ensured even if some parities getcorrupted. We can prove this same case of FKS05 [6].
Here, we consider realizability of the functionality FGKE in short. It is impossible for 1 round, 1
broadcast-message protocol to securely realize FGKE .
(If the initiator is corrupted, there is no way to preventthe malleability attacks.) We can construct 1 round,n broadcast-messages protocol that securely realizes
FGKE by using some non-interactive zero-knowledge
proof, but it is not eﬃcient. In the below, we show
there exists an eﬃcient 2 round, n broadcast-messages
protocol that securely realizes the functionality FGKE .
4. A proposed GKAPThis section shows a 2 round, n broadcast-messages
GKAP that is secure against the malleability attacks.
Recall we assume: 1. The Broadcast Channel, 2. The

Figure 1: The ideal functionality FGKE of GKAP.
Let k be a security parameter, and {fs }s be a pseudorandom function (PRF) family. sid and ssid denote a session
id and sub-session id, respectively, and gid = {P1 , P2 , . . . , Pn } denotes a group of n parties. The ideal functionality
FGKE proceeds as follows with an ideal-process adversary S.
1. Initialization: Receiving (sid, ssid, gid, new-subsession) from Pi for the ﬁrst time on the subsession ssid, do:• FGKE records (sid, ssid, gid, Pi ) and sends this to S.
2. Key Generation: FGKE sends a message (sid, ssid, gid, ready) to S. Upon receiving a message (sid, ssid, gid, ok)from S , do:R• If all parties in gid are uncorrupted, FGKE chooses the session key: κ ←− {0, 1}k and stores (sid, ssid, gid, κ).
• If any party in gid is corrupted,– For uncorrupted parties Pi , FGKE chooses random nonces Ni for Pi and sends them to S.
– For corrupted parties Pj , FGKE waits for S to send nonces Nj for Pj and stores them.
FGKE computes κ = fN1 (V1 ) ⊕ fN2 (V2 ) ⊕ · · · fNn (Vn ) with Vi = (sid||ssid||Pi ) and stores (sid, ssid, gid, κ).
3. Key Delivery: If S sends a message (deliver, sid, ssid, gid, Pi ), then send (sid, ssid, gid, κ) to party Pi .

Figure 2: The proposed Group Key Agreement Protocol 1 in the AM.
Let k be a security parameter, π = {K, E, D} be a public-key encryption scheme, and {fs }s be a PRF familywith a public element v0 in the domain of f . sid and ssid denote a session id and sub-session id, respectively, andgid = {P1 , P2 , . . . , Pn } denotes a group of n parties. Each Pi generates its public and private key pair: (ei , di ) ← K(1k ).
The protocol with input sid, ssid, gid proceeds as follows.
1. The initiator P1 choose a k-bit random nonce N1 , and encrypt the nonce for each parties in gid, respectively:
cj ← Eej (sid||ssid||N1 ) (j = 2, . . . , n). Then, P1 sends (sid, ssid, gid, P1 , (c2 || · · · ||cn )) to parties in gid. P1computes σ1 = fN1 (v0 ) and stores this.
2. The responder Pj (j = 2, . . . , n) decrypts his parts of ciphertexts cj to get the nonce N1 : (sid||ssid||N1 ) ←Ddj (cj ). (Here, Pj veriﬁes sid and ssid.) Then, Pj chooses a random k-bit nonce Nj , and computes σj = fN1 (v0 ).
Pj sends (sid, ssid, gid, Pj , Nj , σj ) to parties in gid.
3. Each Pk (k = 1, . . . , n) checks the equality of all of the σ-values: σk = σl (∀l(∈ {2, . . . , n}) 6= k). If so, Pk
computes and outputs κ = fN1 (V1 ) ⊕ fN2 (V2 ) ⊕ · · · ⊕ fNn (Vn ) with Vi = (sid||ssid||Pi ).

authenticated-link model (AM), 3. The CRS model, 4.
An Static adversary.
The basic strategy of our protocol is as follows. 1.
We enhance the Boyd and Nieto protocol[3], that is themost eﬃcient SK-secure GKAP assuming a broadcast
channel. 2. We use some pseudorandom functions togenerate MACs of the initiator’s nonce to maintain the
key integrity even under malicious insiders. 3. We also
use some pseudorandom functions in a way to maintain the eﬀects of nonces of honest parties even undermalicious insiders that attempt the malleability attack.
Figure 2 shows the proposed GKAP in the AM.
The initiator P1 selects a k-bit random nonce N1and encrypts it for every responders, and sends(sid, ssid, gid, P1 , (c2 || · · · ||cn )) to all parties in gid. P1computes and stores σ1 = fN1 (v0 ).
Upon receiving the ciphertext from P1 , the responders Pj decrypt the corresponding parts to get N1 :(sid||ssid||gid||N1 ) ← Ddj (cj ). Then, Pj choose a random k-bit nonce Nj , computes σj = fN1 (v0 ) and sends(sid, ssid, gid, Pj , Nj , σj ) to parties in gid. Receiving
all the messages, each party Pk in gid veriﬁes the integrity of the nonce N1 using the σ-values as in Figure
2. Only if veriﬁed correctly, Pk computes and outputs
the session-key as κ = fN1 (V1 )⊕fN2 (V2 )⊕· · ·⊕fNn (Vn )with Vi = (sid||ssid||Pi ).
Here we analyze the security of the GKAP, intuitively. Since the initiator P1 is encrypting nonce
N1 , the generated session-key κ is expected to be
kept secret from an eavesdropper (key authentication).
Since the integrity of the received nonce N1 is veriﬁed
through the σ-values, all honest parties should output the same κ or abort (If fN1 (v0 ) = fM1 (v0 ) thenN1 = M1 by the collision-resistance of f ). So, the
GKAP would preserve the key integrity under malicious insiders. The session-key κ is generated using thenonces Ni of every parties Pi , and the way of combining
them as κ = fN1 (V1 ) ⊕ fN2 (V2 ) ⊕ · · · ⊕ fNn (Vn ) would
guarantee that even malicious insiders cannot remove
the eﬀect of the nonces of honest parties. Thus, the
GKAP would preserve security under malicious insiders who attempt the malleability attacks.
5. UC-security of The proposed GKAP1
In fact, we can prove the following theorem:
Theorem 1 Assume the broadcast channel. If encryption scheme π is indistinguishable under adaptively chosen-ciphertext attack and {fs }s is a collisionresistant PRF, then the group key agreement protocol (Figure 2) securely realizes the functionality
FGKE of GKAP against a static adversary under theauthenticated-link model (AM).
To prove Theorem 1, for an arbitrary static real-life
adversary A against the protocol, we have to show existence of an ideal-process adversary (the simulator) S
such that no environment Z can tell whether it interacts with A and parties running the GKAP in the realworld, or with S and (dummy) parties communicatingwith FGKE in the ideal process.
Due to lack of space, we can only sketch the workof the simulator S in this abstract. The full proof willappear in the full version.
The simulator S: The simulator S proceeds as follows. S internally invokes a copy of A. Messages fromZ to S are forwarded to A, and messages from A to its
environment are forwarded to Z. S generates public
and private key pairs for all parties and an element v0
in the domain of f . S gives the resulting (e1 , . . . , en )and v0 to A.
1. If A does not corrupt any party in gid, S choosesR
k-bit random nonces for all parties: N1 , · · · , Nn ←−k{0, 1} . Then, S simulates messages of initiator P1 as
cj ← Eej (sid||ssid||N1 ) for j = 2, . . . , n. S sends themessage (sid, ssid, gid, P1 , (c1 || · · · ||cn )) to A on thename of P1 and waits for A sending this message toall parties in gid. When A delivers the ciphertexts of
P1 to Pj , S computes σj = fN1 (v0 ), and sends the message (sid, ssid, gid, Pj , Nj , σj ) to A on the name of Pj
and waits for A sending the message to all parties.
2. In the case that some parties in gid get corrupted, S proceeds as follows. If the initiator P1
is uncorrupted, S waits an initiator’s nonce N1 from
FGKE . Upon receiving a nonce N1 from FGKE , S computes cj ← Eej (sid||ssid||N1 ) for j = 2, . . . , n. ThenS sends a message (sid, ssid, gid, P1 , (c1 ||c2 || · · · ||cn ))to A and waits for A sending this message to allparties in gid. If responders Pj are uncorrupted,
S waits a Pj ’s nonce Nj from FGKE . Upon receiving a message (sid, ssid, gid, Pj , Nj ) from FGKE ,S computes σj = fN1 (v0 ) and sends a message(sid, ssid, gid, Pj , Nj , σj ) to A and waits for A sending this message to all parties in gid.
In thecase that the initiator P1 gets corrupted and outputs a message (sid, ssid, gid, P1 , (c1 ||c2 || · · · ||cn )), S
decrypts the ciphertexts with the corresponding secret keys, then checks all of the decrypted messages are (sid||ssid||N1 ), and sends the nonce N1 to
FGKE . When corrupted responder Pj outputs a message (sid, ssid, gid, Pj , Nj , σj ), S sends the nonce Nj to
FGKE .
Upon receiving a message (sid, ssid, gid, ready)from FGKE , S sends a message (sid, ssid, gid, ok) to
FGKE . When A delivers all of the necessary messages
to Pj , S sends (deliver, sid, ssid, gid, Pj ) to FGKE todeliver a session-key to Pj .
Analysis of Simulation: We use some of hybrid
game to show the above simulator S works well.
First we construct the hybrid simulator 1 (Hyb1),
in which the simulator SHyb1 knows values of nonces
N1 , . . . , Nn where fN1 (V1 )⊕fN2 (V2 )⊕· · ·⊕fNn (Vn ) = κ
of session-keys of honest sub-sessions by some transcendental means. So, the simulation in honest sub-sessions
is trivially perfect: it merely mimics the behavior ofhonest parties using the knowledge of the session-key
κ. In corrupted sub-sessions, SHyb1 works in the same
way as S in the ideal-process model, checking the integrity of nonces under initiator’s ciphertexts directly
using the secret keys of simulated parties. (In the reallife, receivers check the integrity by using σi ’s.) We willshow Hyb1 is indistinguishable from the real-life modelby using collision-resistance of PRF f .
Second we construct a hybrid model 2 (Hyb2), in
which the simulator SHyb2 also knows values of nonces
N1 , . . . , Nn of honest sub-sessions. However, SHyb2 encrypts a new k-bit random string M1 instead of N1 toform a message of initiator in simulating honest subsessions. This M1 is completely independent of thesession key κ. We will show Hyb2 is indistinguishable
from Hyb1 by using indistinguishability of the encryption scheme {K, E, D}.
Finally we compare Hyb2 with the ideal-processmodel. SHyb2 computes σi using N1 as the seed of a
PRF, where N1 is ingredient of the session-key κ. On
the while, S in the ideal-process model computes σiusing M1 as the seeds, where M1 is independent from
κ. We will show the ideal-process model is indistinguishable from Hyb2 by using a assumption of a PRF
f.

Figure 3: The proposed Group Key Agreement Protocol 2 in the UM.
Let k be a security parameter, π = {K, E, D} be a public-key encryption scheme, Σ = {Gen, Sgn, V rf y} be asignature scheme, and {fs }s be a PRF family with a public element v0 in the domain of f . sid and ssid denote a
session id and sub-session id, respectively, and gid = {P1 , P2 , . . . , Pn } denotes a group of n parties. Each Pi generates
its public/private key pair and signature/verify key pair: (ei , di ) ← K(1k ), (SKi , P Ki ) ← Gen(1k ). The protocol
with input sid, ssid, gid proceeds as follows.
1. The initiator P1 choose a k-bit random nonce N1 , and encrypt the nonce for each parties in gid, respectively:
cj ← Eej (sid||ssid||N1 ) (j = 2, . . . , n). P1 computes his signature τ1 : τ1 ← SgnSK1 (sid||ssid||P1 ||c2 || · · · ||cn ).
Then, P1 sends (sid, ssid, gid, P1 , (c2 || · · · ||cn ), τ1 ) to parties in gid. P1 computes σ1 = fN1 (v0 ) and stores this.
2. The responder Pj (j = 2, . . . , n) veriﬁe the signature τ1 and decrypt his parts of ciphertexts cj to get thenonce N1 : V rf yP K1 ((sid||ssid||P1 ||c2 || · · · ||cn ), τ1 ) = 1, (sid||ssid||N1 ) ← Ddj (cj ). (Here, Pj veriﬁes sid andssid.) Pj chooses a random k-bit nonce Nj , and computes σj = fN1 (v0 ). Pj computes his signature τj :
τj ← SgnSKj (sid||ssid||Pj ||Nj ||σj ). Then Pj sends (sid, ssid, gid, Pj , Nj , σj , τj ) to parties in gid.
3. Each Pk (k = 1, . . . , n) veriﬁes signatures τk (k = 2, . . . , n): V rf yP Kk ((sid||ssid||Pk ||Nk ||σk ), τk ) = 1, andchecks the equality of all of the σ-values: σk = σl (∀l(∈ {2, . . . , n}) 6= k). If so, Pk computes and outputs
κ = fN1 (V1 ) ⊕ fN2 (V2 ) ⊕ · · · ⊕ fNn (Vn ) with Vi = (sid||ssid||Pi ).

6. A proposed GKAP2 in the UM
This section shows our GKAP in the authenticatedlink model (AM). The protocol can be enhanced to be
secure also in the unauthenticated-link model (UM) byusing digital signature schemes.
Figure 3 shows the proposed GKAP in the
UM. The initiator P1 selects a k-bit random
nonce N1 and encrypts it for every responders,and computes his signature τ1 then P1 sends(sid, ssid, gid, P1 , (c2 || · · · ||cn ), τ1 ) to all parties in gid.
P1 computes and stores σ1 = fN1 (v0 ).
Upon receiving the message from P1 , the responders
Pj veriﬁe the signature τ1 and decrypt the corresponding parts to get N1 : (sid||ssid||gid||N1 ) ← Ddj (cj ).
Then, Pj choose a random k-bit nonce Nj , computes
σj = fN1 (v0 ) and his signature τj . Then Pj sends(sid, ssid, gid, Pj , Nj , σj , τj ) to parties in gid. Receiving all the messages, each party Pk in gid veriﬁes all
responder’s signatures and the integrity of the nonce
N1 using the σ-values as in Figure 3. Only if veriﬁed correctly, Pk computes and outputs the sessionkey as κ = fN1 (V1 ) ⊕ fN2 (V2 ) ⊕ · · · ⊕ fNn (Vn ) with
Vi = (sid||ssid||Pi ).
Theorem 2 Assume the broadcast channel. If encryption scheme π is indistinguishable under adaptively
chosen-ciphertext attack, signature scheme Σ is unforgeable under adaptively chosen-message attack and{fs }s is a collision-resistant PRF, then the group key
agreement protocol (Figure 3) securely realizes the functionality FGKE of GKAP against a static adversary under the unauthenticated-link model (UM).
Proof Due to lack of space, we can only sketch theproof. The full proof will appear in the full version.

Suppose there exist a UM-Adversary U against
GKAP2. We show that we can construct a AMAdversary A using U. For any AM-adversary A
against GKAP2 in the UM, there exists AM-adversary
U and no environment Z can distinguish between
real and ideal-process model with a non-negligible advantage. An adverasary A proceed as follow. A
computes (SKi , P Ki ) ← Gen(1k ). The initiator P1
sends his ﬁrst message (sid, ssid, gid, P1 , (c2 || · · · ||cn )),then A computes his signature τ1 and sends(sid, ssid, gid, P1 , (c2 || · · · ||cn ), τ1 ) to the adversary U.
AU M outputs (sid, ssid, gid, P1 , (c02 || · · · ||c0n ), τ10 ) thenA veriﬁes τ10 . If veriﬁed correctly, then A outputs(sid, ssid, gid, P1 , (c02 || · · · ||c0n )) else aborts. ¤7. Conclusion
We have shown a group key agreement protocolthat is secure under malicious insiders. Especially, ourgroup key agreement protocol is the ﬁrst one that maintains UC-security in a meaningful way even if malicious
insiders attempt the malleability attacks. So our group
key agreement protocol does not allow the adversary tocontrol the session-key as desired. The protocol is eﬃcient enough for practical uses, composed of 2 rounds
and n messages for n-party groups.
References[1] M. Abdalla E. Bresson O. Chevassut and D.
Pointcheval, Password-Based Group Key Exchange ina Constant Number of Rounds, PKC 2006, LNCS
3958, pp. 427–442, 2006.
[2] M. Bellare and P. Rogaway, Entity Authentication andKey Distribution, CRYPTO ’93, LNCS 773, pp. 232–
249, 1993.
[3] C. Boyd and J. M. G. Nieto, Round-Optimal Contributory Conference Key Agreement, PKC 2003, LNCS
2567, pp. 161–174, 2003.
[4] R. Canetti, Universally Composable Security, A New
Paradigm for Cryptographic Protocols, FOCS 2001,
pp. 136–145, 2001.
[5] Y. Desmedt J. Pieprzyk R. Steinfeld and H. Wang, A
Non-malleable Group Key Exchange Protocol Robust
Against Active Insiders, ISC 2006, LNCS 4176, pp.
459–475, 2006.
[6] J. Katz and J. Shin, Modeling Insider Attacks onGroup Key-Exchange Protocols, ACM CCCS 2005,
pp. 180–189, 2005.