# An XTR-Based Constant Round Key Agreement Scheme

Authors: Silan Zhang; Jianhua Chen; Jingbo Xia; Xiaochuan Ai
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

A new XTR-based key agreement scheme with constant rounds is presented. Three theorems are formulated to reveal the logarithmic computational complexity of this scheme. Furthermore, the computation framework of XTR-based key agreement scheme is introduced, and security of the scheme is proven under the formal model.


---

## Body

## 1. Introduction

Key agreement is to construct secure infrastructures for networks by computing a common session key among a pool of group members. It is a central issue in various multicast applications such as pay preview broadcast of TV program, teleconferencing, military communication, and distributed interactive games.The pioneer work can be traced to Steiner et al. [1] in 1996, who proposed the first key agreement scheme, GDH. As an extension of Diffie-Hellman key exchange based on the discrete logarithm problem in 〈g〉, GDH achieves group key exchange, and it is known as the first key agreement scheme. After that, various improved schemes of GDH are presented such as CLIQUES [2] and TGDH [3]. Unfortunately, the improved schemes are still flawed in excessive computation or unreasonable communication.Nowadays, it has been widely accepted that a reliable key agreement scheme should meet three utmost crucial demands: fast computation, less communication, and provable security. Here the first demand, that is, fast computation, relies heavily on the algorithm one designed. With the outcome of the new ideas in cryptosystems, including elliptic curve cryptography (ECC) and Hash, computation efficiency in key agreement scheme was increased gradually. At first, the computations were based on the discrete logarithm problem, like Steiner’s classic work [1, 2], Kim’s TGDH [3], and a lot of forthcoming schemes [4–6]. Afterwards, Hash function was incorporated into some schemes to increase the computation efficiency, referring to Tso et al.’s work [7], Fu et al.’s work [8], and so forth. With the development of elliptic curves cryptography, faster computing module like Weil paring was regarded as a good replacement for common exponentiations or multiplications computations in traditional scheme. By using Weil paring on elliptic curve, the pairwise key agreement protocol [9], the tripartite key agreement protocol [10], and the ID-based authenticated group key agreement scheme [11] were given. A newer tendency was to constructing key agreement without using pairing computation; see He et al.’s work [12].The second demand is less communicate, which refers to less information exchange between group members. In 2004, the bottleneck of key agreement scheme was illustrated as communication rounds, instead of computation rounds, which reveals the emphasis of design for an efficient key agreement scheme. In the beginning, GDH.3, proposed by Steiner et al. [1], need n+1 rounds of communications. Kim et al. [3] and Dutta and Barua [4] reduced the rounds of communications to log2n and log3n, respectively. Afterwards, key agreement with four rounds of communications are proposed by Tso et al. [7], Fu et al. [8], Zheng et al. [13], and so forth, and computation complexity of these schemes is slight. From Tso et al. [7], Fu et al. [8] to Zheng et al. [13], the number of exponentiations is decreased from 2n2+5n, 7n to 5n, and the numbers of hash are n2+n+1, 2n, and 3n, respectively. In the meantime, the reduction of communication rounds has been regarded as a central issue. Three rounds scheme is obtained by Nam et al. [5], Augot et al. [6] Yao et al. [14], and so forth. Recently, the rounds of communications have been reduced to two rounds, where Lv and Li [11], He et al. [12], and Feng et al. [15] contribute a lot. In short, key agreement with less communications has drawn many attentions nowadays, and for recent researches and reviews, refer to [16, 23, 24].Besides the computation cost and communication, another focus on research of the key agreement scheme is the security analysis. The reason lies in two aspects. Firstly, it was widely accepted that a secure key agreement should meet several demands, including key completeness, forward secrecy, and backward secrecy. Secondly, the claim of a secure new scheme should be on the basis of a strict and formal proof, instead of colloquial illustration or informal proof. The strict proof of scheme was commenced by Bresson et al. [17], who modeled the execution of an authenticated group Diffie-Hellman scheme and proved its security by defining a formal model. Raymond Choo et al. [18] gave formal proof of certain known protocol to reveal their weakness in the security and henceforth encourage the future designer to provide proofs of security for new protocols. Actually, the importance of provable security has been widely accepted nowadays, and it has been an indispensable part of almost all key agreement schemes appeared in the newly published literatures.Unfortunately, few schemes can achieve all the three goals because of the unbalance between security and efficiency. However, a suitable balance between computation, communication, and security is utmost importance in current key agreement research. In terms of this, this study is to propose a reliable scheme which meets the above three demands by taking the advantages of Lenstra’s XTR cryptosystem [19, 20]. Here, XTR stands for ECSTR, which is an abbreviation for Efficient and Compact Subgroup Trace Representation. Actually, XTR is an efficient cryptosystem and the mathematics underlying XTR is straightforward while compared to ECC [19]. Moreover, the corresponding XTR public keys are only about twice as large as ECC keys, assuming global system parameters. Unlike RSA and ECC, parameter initiation from scratch for XTR takes a negligible amount of computing time [21]. Furthermore, Verheul [22] showed that XTR is at least as secure as supersingular elliptic curve system. This conclusion relied on a deduction that the elapse of XTR might lead to the elapse of ECC. Henceforth, the security of XTR was ensured.In this paper, three algorithms with computation complexity in XTR theory are given. Based on these algorithms, an XTR-based key agreement scheme with constant rounds (XTR-CR) is proposed. The scheme achieves high efficiency and is scalable in computation and security as well. Moreover, the efficiency in computation and communication between XTR-CR and XTR-GDH, which is the natural analogue of GDH in XTR, is compared and the better efficiency of the XTR-CR is shown. Finally, under a decisional Diffie-Hellman (DDH) assumption, the XTR-CR is proved to be secure against active adversary in the formal model. The paper is organized as follows. In Section2, introductions of XTR cryptosystem with three computation theorems are given. Section 3 introduces our new scheme. The security proof of the new scheme is presented in Section 4. Conclusions are given in the last section.


## 2. XTR Cryptosystem

As a reliable key agreement scheme which is aiming to achieve good balance in efficiency and security, this scheme is designed on the basis of XTR. Since the XTR cryptosystem has not ever been incorporated into key agreement scheme, preliminaries of XTR cryptosystem are introduced in Section2.1. By giving and proving three related computation theorems in Section 2.2, computation complexity of our XTR-based scheme is clarified.


### 2.1. Preliminaries

For a givenc∈GF(p2), let F(c,x) be the polynomial X3-cX2+cpX-1∈GF(p2)[X] with roots h0,h1,h2 in GF(p6), and denote cn=h0n+h1n+h2n for all n∈Z. The trace Tr(h) over GF(p2) of h∈GF(p6) is the sum of conjugates over GF(p2), that is, Tr(h)=h+hp2+hp4. Security analysis of the XTR system is based on the difficulties of the following three computational problems:(i)
XTR-DL problem: discrete logarithm problem in XTR system. Givena∈Tr(〈g〉), one computes x(0≤x<q) such that a=Tr(gx),(ii)
XTR-DH problem: Diffie-Hellman problem in XTR system. This problem is the computation ofTr(gxy) with given Tr(gx) and Tr(gy). The XTR-Diffie-Hellman value Tr(gxy) is denoted by XDH(Tr(gx), Tr(gy),(iii)
XTR-DDH problem: decisional Diffie-Hellman problem of determining whetherXDH(a,b)=c with given a,b,c∈Tr(〈g〉).Unlike RSA and Elgamal, the computation in XTR is involved in a subgroup of multiplicative groupGF(p6)* with order p2-p+1. The computation owns polynomial complexity, and as a result, it ensures the high efficiency of the implementation. Furthermore, in order to evaluate the security level of XTR, the following equivalence was proven [19].(i)
The XTR-DL problem is(1,1) equivalent to the DL problem in 〈g〉.(ii)
The XTR-DH problem is(1,2) equivalent to the DH problem in〈g〉.(iii)
The XTR-DL problem is(3,2) equivalent to the DDH problem in〈g〉.where the problem A is(a,b) equivalent to problem B, if any instance of problem A (or B) can be solved by at most a (or b) calls to an algorithm solving problem B (or A).


### 2.2. Computation Theorem of XTR

For simplicity, denotec=Tr(g), cn=Tr(gn)∈GF(p2), and Sn(c)=(cn-1,cn,cn+1)∈GF(p2)3, and denote H as the hash function from GF(p2) toGF(p).Let(1)A(c)=(00110-cp01c),Mn(c)=(cn-2cn-1cncn-1cncn+1cncn+1cn+2)
be 3×3 matrix over GF(p2) with c and cn defined above, and let C(V) be the center column of a 3×3 matrix V.Following six lemmas are necessary for the proof of Theorems7, 8, and 9.Lemma 1 (Theorem2.3.8 in [19]).
Givenc, computation of Sn(c) takes 8log2(n) multiplications in GF(p).Lemma 2 (Lemma2.3.4 in [19]).
c
u
+
v
=
c
u
c
v
-
c
v
p
c
u
-
v
+
c
u
-
2
v, for u,v∈Z.Lemma 3 (Corollary2.4.3 in [19]).
c
n
=
S
m
(
c
)
C
(
A
(
c
)
n
-
m
), where C(V) is defined before.Lemma 4 (Lemma2.4.4 in [19]).
The determinant ofM0(c) equals D=c2p+2+18cp+1-4(c3p+c3)-27∈GF(p). IfD≠0, then(2)M0(c)-1=1D(2c2-6cp2c2p+3c-cp+2cp+1-92c2p+3c-cp+2(c2-2cp)p+1-9(2c2p+3c-cp+2)pcp+1-9(2c2p+3c-cp+2)p(2c2-6cp)p).Lemma 5 (Corollary2.4.7 in [19]).
C
(
A
(
Tr
(
g
)
)
n
)
=
M
0
(
Tr
(
g
)
)
-
1
(
S
n
(
Tr
(
g
)
)
)
T.Lemma 6 (Theorem2.4.9 in [19]).
GivenM0(Tr(g))-1,Tr(g) and Sk(Tr(g)), the trace Tr(gagbk) of gagbk is computed at a cost of 8log2(a/bmodp+8log2b+34) multiplications in GF(p), for a,b∈Zq and unknown k.Based on the above lemmas, three theorems crucial to the implementation of XTR-CR scheme can be obtained.Theorem 7.
It takes 12 multiplications inGF(p) to compute Tr(ga+b) with Sa(Tr(g)) and Sb(Tr(g)).Proof.
From Lemmas3, 4, and 5, it is straight that
(3)Tr(ga+b)=Sa(Tr(g))M0(Tr(g))-1Sb(Tr(g))T.
Note that the matrix M0(Tr(g))-1 is computed in advance, by analyzing the computation cost of Sa(Tr(g)), Sb(Tr(g))T; the conclusion is direct.Theorem 8.
For unknowna,b∈Zq, givenSa(c)andSb(c), the multiplicationSa+b(c)is computed at a cost of 40 multiplications inGF(p).Proof.
Firstca-2 and ca+2 can be computed from Lemma 2, that is,
(4)ca-2=ca-1+(-1)=ca-1c-1-c-1pca+ca+1,ca+2=c(a+1)+1=ca+1c1-c1pca+ca-1.
As a result, Sa-1(c),Sa(c) and Sa+1(c) can be obtained from the computed vector (ca-2(c),ca-1(c),ca(c),ca+1(c),ca+2(c)). From Theorem 7, we have
(5)ca+b-1=Tr(ga+b-1)=Sa-1(c)M0(c)-1Sb(c)T,ca+b=Tr(ga+b)=Sa(c)M0(c)-1Sb(c)T,ca+b+1=Tr(ga+b+1)=Sa+1(c)M0(c)-1Sb(c)T.
Thus Sa+b(c) is computed.
Note thatc-1p and c1p are computed in advance, so it takes 4 multiplications to compute ca-2 and ca+2. From Theorem 7, it costs 12 rounds multiplications in each turn to compute ca+b-1,ca+b and ca+b+1, summing up to 36. Thus the total demanded multiplication is 40, and the proof of Theorem 8 is now complete.Theorem 9.
For givenb, Sa(c), and unknown a, the computation of Sab(c) takes 24log2b+8log2(-1/bmodp)+8log2(1/bmodp)+24 multiplications in GF(p).Proof.
From givenb, Sa(c), and unknown a, one can compute cab+(-1) via Lemma 6 by 8log2(b)+8log2(-1/bmodp)+34 multiplications. Since the matrix M0(Tr(g))-1 is precomputed, 22 multiplications can be reduced. Similarly, the computation of cab+1 takes 8log2b+8log2(-1/bmodp)+12 multiplications. Thus Sab(c)=(cab-1,cab,cab+1) is computed. In conjunction with Lemma 1, the claim is direct.


## 2.1. Preliminaries

For a givenc∈GF(p2), let F(c,x) be the polynomial X3-cX2+cpX-1∈GF(p2)[X] with roots h0,h1,h2 in GF(p6), and denote cn=h0n+h1n+h2n for all n∈Z. The trace Tr(h) over GF(p2) of h∈GF(p6) is the sum of conjugates over GF(p2), that is, Tr(h)=h+hp2+hp4. Security analysis of the XTR system is based on the difficulties of the following three computational problems:(i)
XTR-DL problem: discrete logarithm problem in XTR system. Givena∈Tr(〈g〉), one computes x(0≤x<q) such that a=Tr(gx),(ii)
XTR-DH problem: Diffie-Hellman problem in XTR system. This problem is the computation ofTr(gxy) with given Tr(gx) and Tr(gy). The XTR-Diffie-Hellman value Tr(gxy) is denoted by XDH(Tr(gx), Tr(gy),(iii)
XTR-DDH problem: decisional Diffie-Hellman problem of determining whetherXDH(a,b)=c with given a,b,c∈Tr(〈g〉).Unlike RSA and Elgamal, the computation in XTR is involved in a subgroup of multiplicative groupGF(p6)* with order p2-p+1. The computation owns polynomial complexity, and as a result, it ensures the high efficiency of the implementation. Furthermore, in order to evaluate the security level of XTR, the following equivalence was proven [19].(i)
The XTR-DL problem is(1,1) equivalent to the DL problem in 〈g〉.(ii)
The XTR-DH problem is(1,2) equivalent to the DH problem in〈g〉.(iii)
The XTR-DL problem is(3,2) equivalent to the DDH problem in〈g〉.where the problem A is(a,b) equivalent to problem B, if any instance of problem A (or B) can be solved by at most a (or b) calls to an algorithm solving problem B (or A).


## 2.2. Computation Theorem of XTR

For simplicity, denotec=Tr(g), cn=Tr(gn)∈GF(p2), and Sn(c)=(cn-1,cn,cn+1)∈GF(p2)3, and denote H as the hash function from GF(p2) toGF(p).Let(1)A(c)=(00110-cp01c),Mn(c)=(cn-2cn-1cncn-1cncn+1cncn+1cn+2)
be 3×3 matrix over GF(p2) with c and cn defined above, and let C(V) be the center column of a 3×3 matrix V.Following six lemmas are necessary for the proof of Theorems7, 8, and 9.Lemma 1 (Theorem2.3.8 in [19]).
Givenc, computation of Sn(c) takes 8log2(n) multiplications in GF(p).Lemma 2 (Lemma2.3.4 in [19]).
c
u
+
v
=
c
u
c
v
-
c
v
p
c
u
-
v
+
c
u
-
2
v, for u,v∈Z.Lemma 3 (Corollary2.4.3 in [19]).
c
n
=
S
m
(
c
)
C
(
A
(
c
)
n
-
m
), where C(V) is defined before.Lemma 4 (Lemma2.4.4 in [19]).
The determinant ofM0(c) equals D=c2p+2+18cp+1-4(c3p+c3)-27∈GF(p). IfD≠0, then(2)M0(c)-1=1D(2c2-6cp2c2p+3c-cp+2cp+1-92c2p+3c-cp+2(c2-2cp)p+1-9(2c2p+3c-cp+2)pcp+1-9(2c2p+3c-cp+2)p(2c2-6cp)p).Lemma 5 (Corollary2.4.7 in [19]).
C
(
A
(
Tr
(
g
)
)
n
)
=
M
0
(
Tr
(
g
)
)
-
1
(
S
n
(
Tr
(
g
)
)
)
T.Lemma 6 (Theorem2.4.9 in [19]).
GivenM0(Tr(g))-1,Tr(g) and Sk(Tr(g)), the trace Tr(gagbk) of gagbk is computed at a cost of 8log2(a/bmodp+8log2b+34) multiplications in GF(p), for a,b∈Zq and unknown k.Based on the above lemmas, three theorems crucial to the implementation of XTR-CR scheme can be obtained.Theorem 7.
It takes 12 multiplications inGF(p) to compute Tr(ga+b) with Sa(Tr(g)) and Sb(Tr(g)).Proof.
From Lemmas3, 4, and 5, it is straight that
(3)Tr(ga+b)=Sa(Tr(g))M0(Tr(g))-1Sb(Tr(g))T.
Note that the matrix M0(Tr(g))-1 is computed in advance, by analyzing the computation cost of Sa(Tr(g)), Sb(Tr(g))T; the conclusion is direct.Theorem 8.
For unknowna,b∈Zq, givenSa(c)andSb(c), the multiplicationSa+b(c)is computed at a cost of 40 multiplications inGF(p).Proof.
Firstca-2 and ca+2 can be computed from Lemma 2, that is,
(4)ca-2=ca-1+(-1)=ca-1c-1-c-1pca+ca+1,ca+2=c(a+1)+1=ca+1c1-c1pca+ca-1.
As a result, Sa-1(c),Sa(c) and Sa+1(c) can be obtained from the computed vector (ca-2(c),ca-1(c),ca(c),ca+1(c),ca+2(c)). From Theorem 7, we have
(5)ca+b-1=Tr(ga+b-1)=Sa-1(c)M0(c)-1Sb(c)T,ca+b=Tr(ga+b)=Sa(c)M0(c)-1Sb(c)T,ca+b+1=Tr(ga+b+1)=Sa+1(c)M0(c)-1Sb(c)T.
Thus Sa+b(c) is computed.
Note thatc-1p and c1p are computed in advance, so it takes 4 multiplications to compute ca-2 and ca+2. From Theorem 7, it costs 12 rounds multiplications in each turn to compute ca+b-1,ca+b and ca+b+1, summing up to 36. Thus the total demanded multiplication is 40, and the proof of Theorem 8 is now complete.Theorem 9.
For givenb, Sa(c), and unknown a, the computation of Sab(c) takes 24log2b+8log2(-1/bmodp)+8log2(1/bmodp)+24 multiplications in GF(p).Proof.
From givenb, Sa(c), and unknown a, one can compute cab+(-1) via Lemma 6 by 8log2(b)+8log2(-1/bmodp)+34 multiplications. Since the matrix M0(Tr(g))-1 is precomputed, 22 multiplications can be reduced. Similarly, the computation of cab+1 takes 8log2b+8log2(-1/bmodp)+12 multiplications. Thus Sab(c)=(cab-1,cab,cab+1) is computed. In conjunction with Lemma 1, the claim is direct.


## 3. The XTR-Based Key Agreement Scheme

In this section, the new scheme XTR-CR is presented. For this, the fundamental application of Lenstra and Verheul’s work [19] is mentioned first in Section 3.1. After that, two group extension protocols, XTR-GDH and XTR-CR, are listed in Section 3.2. Among them, XTR-GDH is the natural extension of GDH by combining XTR, while XTR-CR is our proposed new scheme with low computation complexity and two rounds of communications. Finally, explicit comparisons of XTR-CR, XTR-GDH, and other competitive schemes are performed in Section 3.3, so as to reveal the advantage of XTR-based schemes, especially XTR-CR.


### 3.1. Key Exchange between Alice and Bob

XTR-Diffie-Hellman key exchange protocol between two members is a routine idea in  Lenstra and Verheul’s work [20], and it is remarkable enough to illustrate here in detail.Suppose that Alice and Bob, who both have access to the XTR public key datap, q, Tr(g), want to agree on a shared secret key K. This is done by using the following XTR version of Diffie-Hellman protocol.Step 1.
Alice selects a randoma∈Fp, uses Algorithm 2.37 in [19], computes Sa(Tr(g))=(Tr(ga-1),Tr(ga),Tr(ga+1))∈GF(p2)3, and sends Tr(ga) to Bob.Step 2.
Bob receivesTr(ga) from Alice, selects b∈Fp randomly, similarly computes Sb(Tr(g))=(Tr(gb-1),Tr(gb),Tr(gb+1))∈GF(p2)3, and sends Tr(gb) to Alice.Step 3.
Alice receivesTr(gb), computes Sa(Tr(gb))=(Tr(g(a-1)b),Tr(gab),Tr(g(a+1)b)), and determines K based on Tr(gab).Step 4.
Bob receivesTr(ga), computes Sb(Tr(ga))=(Tr(g(b-1)a),Tr(gba),Tr(g(b+1)a)), and also determines K based on Tr(gab).


### 3.2. Key Agreement of Group

Here, we present two constant-round communication protocols for the group key agreement. One is an analogue of GDH in XTR, denoted as XTR-GDH, another is the proposed scheme, XTR-CR.Assume that there aren members in group, that is, M1,M2,…,Mn, and an identity code IDi has been assigned to each member Mi(i=1,2,…,n) in advance.


#### 3.2.1. Analogue of GDH in XTR: XTR-GDH

The first protocol XTR-GDH is a natural extension ofR. Steiner’s Group Diffie-Hellman protocol [19].Algorithm XTR-GDHStep 1.
M
1 selects r,r1∈[1,p2-p] randomly, computes Sr1(Tr(g))=(Tr(gr1-1),Tr(gr1),Tr(gr1+1)), and broadcast message m1=(ID1,Tr(gr1)) to Mi(i=2,3,…,n).Step 2.
M
i
(
i
=
2,3
,
…
,
n
) selects a random ri∈[1,p2-p], computes Sri(Tr(g))=(Tr(gri-1),Tr(gri),Tr(gri+1)), and sends message mi=(IDi,Tr(gri)) back to M1.Step 3.
M
1 computes Tr(gr1ri) via XTR-DH method, hashes it to bi(i=2,3,…,n). Let ci=∏1≤j≤n-1,j≠i‍bj, and M1 broadcasts messages mn-1+i=(ID1,IDi,Tr(grci)) to Mi(i=2,3,…,n).Step 4.
The session key isK=Tr(gb1b2⋯bn-1r).


#### 3.2.2. Proposed Scheme: XTR-CR

Below is the scheme we proposed, Algorithm XTR-CR.Step 1.
M
i
(
i
=
1,2
,
…
,
n
-
1
) selects a random ri∈[1,p2-p], computes Sri(Tr(g))=(Tr(gri-1),Tr(gri),Tr(gri+1)), and broadcasts message mi=(IDi,Tr(gri)) to Mn.Step 2.
M
n selects r,rn∈[1,p2-p] at random. With Sri(Tr(g)) and r, Mn computes Srri(Tr(g))=(Tr(grri-1),Tr(grri),Tr(grri+1)) by the algorithm in Theorem 9 of last section, where i=1,2,…,n-1.
Letbi=∑1≤j≤n,j≠i‍rj, Mn computes Sbir(Tr(g)) by Theorem 8, i=1,2,…,n-1.
Then,Mn broadcasts message mn=(IDn,Sr(Tr(g)),Sb1r(Tr(g)),Sb2r(Tr(g)),…,Sbn-1r(Tr(g))) to Mi(i=1,2,…,n-1).Step 3.
EachMi(i=1,2,…,n-1) computes Srri(Tr(g))=(Tr(grri-1),Tr(grri),Tr(grri+1)) by Theorem 9. By doing this, Mi reveal the session key K by computing Srri+rbi(Tr(g))=Sr(r1+r2+⋯+rn)(Tr(g)). Thus K=Tr(gr(r1+r2+⋯+rn)) is the session key. The key agreement procedure is finished.The flow charts of two schemes are depicted in Figure1.Flow charts of XTR-GDH and XTR-CR.
(a)
(b)During the whole process, the latter memberMn acts as a sponsor which carries heavier computation burden than other members. The obligation of sponsor is reasonable and necessary, because the presence of sponsor not only provides high efficiency for the scheme but also keeps the member equality in the group. This property is similar to that in the scheme of GDH [1] and TGDH [3].


### 3.3. Comparison of XTR-GDH, XTR-CR, and Other Competitive Key Agreement Schemes in Communication and Computation

The performances of XTR-based scheme are compared with several competitive key agreement schemes by considering the computations, message amount, and communications. Twelve typical key agreement schemes are listed in Table1 for comparison with XTR-based schemes in terms of efficiency. All of the chosen schemes are listed with the descending order according to the number of communication rounds. Among them, GDH.3 [1] and TGDH [3] are classic and traditional protocols, while Dutta95 [4] show better performance in the rounds of communication. Other schemes are typical and competitive key agreement schemes in the literature, as introduced in the first section, and the number of communication rounds is sorted from four, three to two. As a typical one round protocol, Shim’s work [23] is designed for three-party key agreement instead of arbitrarynentities, and signature is demanded; therefore, it is not equal to give a computation comparison. The explicit information of these schemes could be found in Table 1.Table 1
Comparison between XTR-GDH, XTR-CR, and other competitive key agreements schemes.
Protocol
Number of exponentiations
Number of pairings
Number of scalar multiplications
Number of hash
Message amount
Round of communications
GDH.3 [1]
2
n
-
3
—
—
—
2
n
-
1
n
+
1
TGDH [3]
n
(
log
2
n
+
1
)
—
—
—
n
log
2
n
Dutta05 [4]
n
log
3
n
—
—
—
n
log
3
n
TYO07 [7]
2
n
2
+
5
n
—
—
n
2
+
n
+
1
5
n
2
+
6
n
+
1
4
FXW09 [8]
7
n
—
2
n
2
n
2
+
6
n
4
ZZLC09 [13]
5
n
—
—
3
n
4
n
2
4
YWJ08 [14]
—
2
n
2
+
4
n
n
2
+
5
n
—
5
n
2
3
NPKW07 [5]
5.5
n
+
5
n
log
2
n
-
1
—
—
—
7
n
+
10
n
log
2
n
-
4
3
Daniel07 [6]
n
-
2
—
—
—
3
n
3
XTR-GDH
—
—
16
n
log
2
p
1
2
n
-
1
3
FWM08 [15]
—
—
2
n
3
-
2
n
2
+
n
2
n
2
n
3
-
n
2
2
LL10 [11]
—
5
n
10
n
—
3
n
2
2
Xiong13 [24]
n
n
5
n
—
<2n
2
XTR-CR
—
—
(n − 1)(88log2p+128)
—
n
2As shown in Table1, both XTR-GDH and XTR-CR perform good in the rounds of communications. In the following, performances in XTR-based schemes will be compared with other two or three round communication schemes.Among these schemes with three rounds communications, XTR-GDH only demands16nlog2p scalar multiplications, which seems better than YWJ08 [9] and slightly weaker than NPKW07 [5], and the latter need 5.5n+5nlog2n-1 exponentiations. Though Daniel07 [6] need much less computations than XTR-GDH, it could be easily found that XTR-GDH owns the least message amount. These results show that XTR-GDH is also a competitive scheme.While observing the performance of XTR-CR among two rounds communication schemes,(n-1)(88log2p+128) scalar multiplications are counted for XTR-CR. The computation load in XTR-CR is less than that in FWM08 [15] but a little heavier than that in LL10 [11] and Xiong13 [24]. Taking into account that5nornpairing computation is time-consuming for LL10 [11] and Xiong13 [24], XTR-CR needs comparatively less computations than the above schemes. Besides, message amount of XTR-CR is the least among all of the schemes.If compared XTR-GDH with XTR-CR, the latter performs better in communication and message amount. Meanwhile, XTR-CR shows slight weakness in computation complexity. For the sake of rapid development of XTR cryptosystem, the weakness in XTR-CR is subtle. Moreover, as mentioned in Section1, key agreement with less communication is critical in the implementation. Since XTR-GDH needs one more communication than XTR-CR, the proposed scheme is a better and more efficient scheme than XTR-GDH.In short, result from full comparisons of fourteen competitive key agreement schemes shows that XTR-GDH and XTR-CR achieve good balance in the performance of computation and communication. Moreover, XTR-CR performs the best both in computation and communication.


## 3.1. Key Exchange between Alice and Bob

XTR-Diffie-Hellman key exchange protocol between two members is a routine idea in  Lenstra and Verheul’s work [20], and it is remarkable enough to illustrate here in detail.Suppose that Alice and Bob, who both have access to the XTR public key datap, q, Tr(g), want to agree on a shared secret key K. This is done by using the following XTR version of Diffie-Hellman protocol.Step 1.
Alice selects a randoma∈Fp, uses Algorithm 2.37 in [19], computes Sa(Tr(g))=(Tr(ga-1),Tr(ga),Tr(ga+1))∈GF(p2)3, and sends Tr(ga) to Bob.Step 2.
Bob receivesTr(ga) from Alice, selects b∈Fp randomly, similarly computes Sb(Tr(g))=(Tr(gb-1),Tr(gb),Tr(gb+1))∈GF(p2)3, and sends Tr(gb) to Alice.Step 3.
Alice receivesTr(gb), computes Sa(Tr(gb))=(Tr(g(a-1)b),Tr(gab),Tr(g(a+1)b)), and determines K based on Tr(gab).Step 4.
Bob receivesTr(ga), computes Sb(Tr(ga))=(Tr(g(b-1)a),Tr(gba),Tr(g(b+1)a)), and also determines K based on Tr(gab).


## 3.2. Key Agreement of Group

Here, we present two constant-round communication protocols for the group key agreement. One is an analogue of GDH in XTR, denoted as XTR-GDH, another is the proposed scheme, XTR-CR.Assume that there aren members in group, that is, M1,M2,…,Mn, and an identity code IDi has been assigned to each member Mi(i=1,2,…,n) in advance.


### 3.2.1. Analogue of GDH in XTR: XTR-GDH

The first protocol XTR-GDH is a natural extension ofR. Steiner’s Group Diffie-Hellman protocol [19].Algorithm XTR-GDHStep 1.
M
1 selects r,r1∈[1,p2-p] randomly, computes Sr1(Tr(g))=(Tr(gr1-1),Tr(gr1),Tr(gr1+1)), and broadcast message m1=(ID1,Tr(gr1)) to Mi(i=2,3,…,n).Step 2.
M
i
(
i
=
2,3
,
…
,
n
) selects a random ri∈[1,p2-p], computes Sri(Tr(g))=(Tr(gri-1),Tr(gri),Tr(gri+1)), and sends message mi=(IDi,Tr(gri)) back to M1.Step 3.
M
1 computes Tr(gr1ri) via XTR-DH method, hashes it to bi(i=2,3,…,n). Let ci=∏1≤j≤n-1,j≠i‍bj, and M1 broadcasts messages mn-1+i=(ID1,IDi,Tr(grci)) to Mi(i=2,3,…,n).Step 4.
The session key isK=Tr(gb1b2⋯bn-1r).


### 3.2.2. Proposed Scheme: XTR-CR

Below is the scheme we proposed, Algorithm XTR-CR.Step 1.
M
i
(
i
=
1,2
,
…
,
n
-
1
) selects a random ri∈[1,p2-p], computes Sri(Tr(g))=(Tr(gri-1),Tr(gri),Tr(gri+1)), and broadcasts message mi=(IDi,Tr(gri)) to Mn.Step 2.
M
n selects r,rn∈[1,p2-p] at random. With Sri(Tr(g)) and r, Mn computes Srri(Tr(g))=(Tr(grri-1),Tr(grri),Tr(grri+1)) by the algorithm in Theorem 9 of last section, where i=1,2,…,n-1.
Letbi=∑1≤j≤n,j≠i‍rj, Mn computes Sbir(Tr(g)) by Theorem 8, i=1,2,…,n-1.
Then,Mn broadcasts message mn=(IDn,Sr(Tr(g)),Sb1r(Tr(g)),Sb2r(Tr(g)),…,Sbn-1r(Tr(g))) to Mi(i=1,2,…,n-1).Step 3.
EachMi(i=1,2,…,n-1) computes Srri(Tr(g))=(Tr(grri-1),Tr(grri),Tr(grri+1)) by Theorem 9. By doing this, Mi reveal the session key K by computing Srri+rbi(Tr(g))=Sr(r1+r2+⋯+rn)(Tr(g)). Thus K=Tr(gr(r1+r2+⋯+rn)) is the session key. The key agreement procedure is finished.The flow charts of two schemes are depicted in Figure1.Flow charts of XTR-GDH and XTR-CR.
(a)
(b)During the whole process, the latter memberMn acts as a sponsor which carries heavier computation burden than other members. The obligation of sponsor is reasonable and necessary, because the presence of sponsor not only provides high efficiency for the scheme but also keeps the member equality in the group. This property is similar to that in the scheme of GDH [1] and TGDH [3].


## 3.2.1. Analogue of GDH in XTR: XTR-GDH

The first protocol XTR-GDH is a natural extension ofR. Steiner’s Group Diffie-Hellman protocol [19].Algorithm XTR-GDHStep 1.
M
1 selects r,r1∈[1,p2-p] randomly, computes Sr1(Tr(g))=(Tr(gr1-1),Tr(gr1),Tr(gr1+1)), and broadcast message m1=(ID1,Tr(gr1)) to Mi(i=2,3,…,n).Step 2.
M
i
(
i
=
2,3
,
…
,
n
) selects a random ri∈[1,p2-p], computes Sri(Tr(g))=(Tr(gri-1),Tr(gri),Tr(gri+1)), and sends message mi=(IDi,Tr(gri)) back to M1.Step 3.
M
1 computes Tr(gr1ri) via XTR-DH method, hashes it to bi(i=2,3,…,n). Let ci=∏1≤j≤n-1,j≠i‍bj, and M1 broadcasts messages mn-1+i=(ID1,IDi,Tr(grci)) to Mi(i=2,3,…,n).Step 4.
The session key isK=Tr(gb1b2⋯bn-1r).


## 3.2.2. Proposed Scheme: XTR-CR

Below is the scheme we proposed, Algorithm XTR-CR.Step 1.
M
i
(
i
=
1,2
,
…
,
n
-
1
) selects a random ri∈[1,p2-p], computes Sri(Tr(g))=(Tr(gri-1),Tr(gri),Tr(gri+1)), and broadcasts message mi=(IDi,Tr(gri)) to Mn.Step 2.
M
n selects r,rn∈[1,p2-p] at random. With Sri(Tr(g)) and r, Mn computes Srri(Tr(g))=(Tr(grri-1),Tr(grri),Tr(grri+1)) by the algorithm in Theorem 9 of last section, where i=1,2,…,n-1.
Letbi=∑1≤j≤n,j≠i‍rj, Mn computes Sbir(Tr(g)) by Theorem 8, i=1,2,…,n-1.
Then,Mn broadcasts message mn=(IDn,Sr(Tr(g)),Sb1r(Tr(g)),Sb2r(Tr(g)),…,Sbn-1r(Tr(g))) to Mi(i=1,2,…,n-1).Step 3.
EachMi(i=1,2,…,n-1) computes Srri(Tr(g))=(Tr(grri-1),Tr(grri),Tr(grri+1)) by Theorem 9. By doing this, Mi reveal the session key K by computing Srri+rbi(Tr(g))=Sr(r1+r2+⋯+rn)(Tr(g)). Thus K=Tr(gr(r1+r2+⋯+rn)) is the session key. The key agreement procedure is finished.The flow charts of two schemes are depicted in Figure1.Flow charts of XTR-GDH and XTR-CR.
(a)
(b)During the whole process, the latter memberMn acts as a sponsor which carries heavier computation burden than other members. The obligation of sponsor is reasonable and necessary, because the presence of sponsor not only provides high efficiency for the scheme but also keeps the member equality in the group. This property is similar to that in the scheme of GDH [1] and TGDH [3].


## 3.3. Comparison of XTR-GDH, XTR-CR, and Other Competitive Key Agreement Schemes in Communication and Computation

The performances of XTR-based scheme are compared with several competitive key agreement schemes by considering the computations, message amount, and communications. Twelve typical key agreement schemes are listed in Table1 for comparison with XTR-based schemes in terms of efficiency. All of the chosen schemes are listed with the descending order according to the number of communication rounds. Among them, GDH.3 [1] and TGDH [3] are classic and traditional protocols, while Dutta95 [4] show better performance in the rounds of communication. Other schemes are typical and competitive key agreement schemes in the literature, as introduced in the first section, and the number of communication rounds is sorted from four, three to two. As a typical one round protocol, Shim’s work [23] is designed for three-party key agreement instead of arbitrarynentities, and signature is demanded; therefore, it is not equal to give a computation comparison. The explicit information of these schemes could be found in Table 1.Table 1
Comparison between XTR-GDH, XTR-CR, and other competitive key agreements schemes.
Protocol
Number of exponentiations
Number of pairings
Number of scalar multiplications
Number of hash
Message amount
Round of communications
GDH.3 [1]
2
n
-
3
—
—
—
2
n
-
1
n
+
1
TGDH [3]
n
(
log
2
n
+
1
)
—
—
—
n
log
2
n
Dutta05 [4]
n
log
3
n
—
—
—
n
log
3
n
TYO07 [7]
2
n
2
+
5
n
—
—
n
2
+
n
+
1
5
n
2
+
6
n
+
1
4
FXW09 [8]
7
n
—
2
n
2
n
2
+
6
n
4
ZZLC09 [13]
5
n
—
—
3
n
4
n
2
4
YWJ08 [14]
—
2
n
2
+
4
n
n
2
+
5
n
—
5
n
2
3
NPKW07 [5]
5.5
n
+
5
n
log
2
n
-
1
—
—
—
7
n
+
10
n
log
2
n
-
4
3
Daniel07 [6]
n
-
2
—
—
—
3
n
3
XTR-GDH
—
—
16
n
log
2
p
1
2
n
-
1
3
FWM08 [15]
—
—
2
n
3
-
2
n
2
+
n
2
n
2
n
3
-
n
2
2
LL10 [11]
—
5
n
10
n
—
3
n
2
2
Xiong13 [24]
n
n
5
n
—
<2n
2
XTR-CR
—
—
(n − 1)(88log2p+128)
—
n
2As shown in Table1, both XTR-GDH and XTR-CR perform good in the rounds of communications. In the following, performances in XTR-based schemes will be compared with other two or three round communication schemes.Among these schemes with three rounds communications, XTR-GDH only demands16nlog2p scalar multiplications, which seems better than YWJ08 [9] and slightly weaker than NPKW07 [5], and the latter need 5.5n+5nlog2n-1 exponentiations. Though Daniel07 [6] need much less computations than XTR-GDH, it could be easily found that XTR-GDH owns the least message amount. These results show that XTR-GDH is also a competitive scheme.While observing the performance of XTR-CR among two rounds communication schemes,(n-1)(88log2p+128) scalar multiplications are counted for XTR-CR. The computation load in XTR-CR is less than that in FWM08 [15] but a little heavier than that in LL10 [11] and Xiong13 [24]. Taking into account that5nornpairing computation is time-consuming for LL10 [11] and Xiong13 [24], XTR-CR needs comparatively less computations than the above schemes. Besides, message amount of XTR-CR is the least among all of the schemes.If compared XTR-GDH with XTR-CR, the latter performs better in communication and message amount. Meanwhile, XTR-CR shows slight weakness in computation complexity. For the sake of rapid development of XTR cryptosystem, the weakness in XTR-CR is subtle. Moreover, as mentioned in Section1, key agreement with less communication is critical in the implementation. Since XTR-GDH needs one more communication than XTR-CR, the proposed scheme is a better and more efficient scheme than XTR-GDH.In short, result from full comparisons of fourteen competitive key agreement schemes shows that XTR-GDH and XTR-CR achieve good balance in the performance of computation and communication. Moreover, XTR-CR performs the best both in computation and communication.


## 4. Security Analysis of XTR-CR

In this section, a formal model is utilized to prove that XTR-CR scheme is secure against adversary under XTR-DDH assumption. The explicit security proof of the proposed scheme is given in Section4.2.


### 4.1. Security Basis of Formal Model

LetS={M1,M2,…,Mn} be a set of n users who wish to participate in a group key agreement. One assumes that n is polynomially bounded in the security parameter k. A player Mi has many instances called oracles, involved in distinct concurrent executions of protocols. The instances s of player Mi are denoted as ∏is‍.The adversaryA has an endless supply of oracles ∏is‍ and makes various queries to them. Each query models a capability of adversary.(i)
Execute (S). This query returns a transcript of an honest protocol execution among instances of users in S.(ii)
Send (∏is‍,m). This query sends message m to oracle ∏is‍. When oracle ∏is‍ receives the message m, it proceeds as specified in the protocol; the oracle updates its state and then generates and sends out a response message as needed. The response message is returned to the adversary A. A query of form Send (prodis′,Start′) allows adversary A to initiate an execution of the protocol.(iii)
Reveal (∏is‍). This query returns the session key K if oracle ∏is‍ has computed a session key. This query models the capability of adversary to obtain some session keys.(iv)
Corrupt (Mi). The long-term private key of user Mi is returned in response to the query which is considered to deal with forward secrecy.(v)
Dump (∏is‍). This query returns all short-term secret values used by oracle ∏is‍, modeling the adversary’s capability to embed a Trojan horse or other forms of malicious code into a system and then log all the session-specific information of victim. But neither the session key K computed by ∏is‍ nor the long-term private key SKi is returned.(vi)
Test (∏is‍). This query is asked only once when the adversary A wants to attempt to distinguish the real session key K from a random fake key, modeling the semantic security of session key K. To answer the query, one flips a secret coin b and returns the real session key K if b=1, or else a random string chosen from {0,1}l, if b=0, where l is the length of session key to be distributed in the protocol. This query is made only if oracle ∏is‍ is fresh, and the definition of which will be given below.To quantify the ability of an adversaryA, one consider the query action of A here. During the execution of protocol, the adversary A, at any time, asks a Test query to a fresh oracle, then gets back an l-bit string as the response to this query, and at some later point, outputs a bit b′ as a guess for the hidden bit b. Let Correct Guess (CG) be the event that b′=b. Then we define the advantage of A in attacking protocol P to be
(6)AdvA,P(k)=2Pr[CG]-1.
We define protocol P as secure against an adversary A if AdvA,P(k) is negligible.According to the illustration of XTR-DDH problem in Section2, a formal description of XTR-DDH assumption is displayed below.LetG=Tr(〈g〉) be XTR group, and let x,y,z be randomly chosen elements in Zp. Informally, the XTR-DDH assumption is that it is difficult to distinguish between the distributions of (Tr(gx),Tr(gy),Tr(gxy)) and (Tr(gx),Tr(gy),Tr(gz)).More formally, if we defineAdvGXTR-DDH(A) as
(7)AdvGXTR-DDH(A)=|Pr[A(Tr(g),Tr(gx),Tr(gy),Tr(gxy))=1]-Pr[A(Tr(g),Tr(gx),Tr(gy),Tr(gz))=1]|,
the XTR-DDH assumption holds in G=Tr(〈g〉) if AdvGXTR-DDH(A) is negligible for any probabilistic polynomial time adversary A. We denote by AdvGXTR-DDH(t) the maximum value of AdvGXTR-DDH(A) over all adversaries A running in time at most t.


### 4.2. Security Proof of the Key Agreement Protocol

Theorem 10.
LetA be a passive adversary attacking protocol XTR-CR, running in time t and making qex Execute queries. Then one has
(8)AdvA,P(k)≤2qexAdvGXTR-DDH(t′),
where t′=t+O(nqextexp), with texp being the time required to compute an exponentiation in G=Tr(〈g〉).Proof.
Assume thatA can guess the hidden bit b correctly with probability 1/2+ε. Then we construct from a distinguisher D that solves the XTR-DDH problem in G with probability ε/qex.
Before describing the construction ofD, we define the following two distributions.
Consider the following(9)Real={(T,K)|r1,r2,…,rn,r∈RZp,z1=Tr(gr1),…,zn=Tr(grn),z=Tr(gr),x1=Tr(grr1),…,xn=Tr(grrn),y1=x2x3⋯xn=Sb1r(Tr(g)),…,yn-1=x1x2⋯xn-2xn=Sbn-1r(Tr(g)).}Rand={(T,K)|r1,r2,…,rn,r,s1,s2,…,sn∈RZp,z1=Tr(gr1),…,zn=Tr(grn),z=Tr(gr),x1=Tr(gs1),…,xn=Tr(gsn),y1=x2x3⋯xn=Ss2+s3+⋯+sn(Tr(g)),…,yn-1=x1x2⋯xn-2xn=Ss1+⋯+sn-2+sn(Tr(g)).},where bi=∑1≤j≤n,j≠i‍rj as in protocol XTR-CR, T=(z,z1,…,zn-1,y1,…,yn-1) is the transcript of message and K=H(y1,…,yn-1,X) is the hash value. We now construct a distribution Dist by the triple (Tr(gr),Tr(gr2),Tr(gr′r2)), as below:(10)Dist={(T,K)|r1,r2,α3,β3,…,αn,βn∈RZp,z1=Tr(gr1),z2=Tr(gr2),z3=Tr(gr1α3+r2β3),…,zn=Tr(gr1αn+r2βn),z=Tr(gr),x1=Tr(grr1),x2=Tr(grr2),x3=Tr(grr1α3+r′r2β3),…,xn=Tr(grr1αn+r′r2βn),y1=x2x3⋯xn=Sc2+c3+⋯+cn(Tr(g)),…,yn-1=x1x2⋯xn-2xn=Sc1+⋯+cn-2+cn(Tr(g)).},where T, K are defined above and c1=rr1, c2=rr2, c3=rr1α3+r′r2β3,…,cn=rr1αn+r′r2βn.
If(Tr(gr),Tr(gr2),Tr(gr′r2)) is a XTR-DH triple (i.e., r=r′), then Dist=Real, since triple (Tr(g),zi,xi)=(Tr(g),Tr(ga),Tr(gar)) for all i∈[1,n]. If not, (Tr(gr),Tr(gr2),Tr(gr′r2)) is a random triple, so Dist=Rand. Thus a distribution is constructed to display the advantage of XTR-DDH.
Hence, letA′ be an algorithm that, given (T,K) computing from Real and Rand distributions, runs in time t and outputs 0 or 1. Then, we have
(11)|Pr[A′(T,K)=1∣(T,K)⟵Real]-Pr[A′(T,K)=1∣(T,K)⟵Rand]|≤AdvGXTR-DDH(t+O(n·texp)).
On the other hand, it is clear to find that the transcriptT in experiment Rand is independent of si, which implies that for any computationally unbounded adversary A, we have (12)Pr[A(T,Kb)∣(T,K1)⟵Rand;k0⟵{0,1}l;b⟵{0,1}]=12.The detail of construction of distinguisher D is given now. Assume without loss of generality that A makes its Test query to an oracle activated by the δth Execute query. The distinguisher D begins by choosing a random bit as a guess for the value of δ. Then D invokes A and simulates the queries of A. D answers all the queries from A in a specified way, following the protocol, except in the dth query. In this latter case, D embed the DDH problem instance into the transcript as follows.
Given a triple(Tr(gr),Tr(gr2),Tr(gr′r2))∈GF(p2)3, D generates (T,K) according to the distribution Dist and answers the dth Execute query of A with T. The distinguisher D aborts and outputs a random bit of d≠δ. Otherwise, D answers the Test query of A with K.
WhenA terminates and outputs its guess b′, D outputs 1 if b=b′, and 0 otherwise. If (Tr(gr),Tr(gr2),Tr(gr′r2)) is a XTR-DDH triple, from the deduction mentioned before, it is deduced that Dist=Real, and thus Pr[b=b′]=1/2+ε. If not, (Tr(gr),Tr(gr2),Tr(gr′r2) is a random triple, and then Dist=Rand and Pr[b=b′]=1/2. Finally, since Pr[d=δ]=1/qex, we obtain
(13)AdvgXTR-DDH(D)=εqex.
From AdvA,P(k)=2Pr[CG]-1, we have that
(14)12+ε=Pr[CG]=Pr[b=b′]=(AdvA,P(k)+1)2.
Therefore,
(15)AdvA,P(k)=2ε=2qexAdvGXTR-DDH(D)≤AdvGXTR-DDH(t+O(n·texp)).
Thus the theorem follows.The result of the above theorem shows that the security of proposed key agreement scheme is based on the computational difficulty of XTR-DDH problem. Also, it is shown that the proposed scheme is secure against adversary’s attacking under XTR-DDH assumption.Moreover, the result of this security proof also supports the idea of Steiner et al. [1], who proved that DDH assumption implied the G-DDH assumption. Here, G-DDH is short for group decisional Diffie-Hellman assumption, which refers to the difficulty of distinguishing g∏‍xi from a random value by knowing elements g∏‍xi for some subsets of indices i. Actually, Theorem 10 could be regarded as an evidence for this result.


## 4.1. Security Basis of Formal Model

LetS={M1,M2,…,Mn} be a set of n users who wish to participate in a group key agreement. One assumes that n is polynomially bounded in the security parameter k. A player Mi has many instances called oracles, involved in distinct concurrent executions of protocols. The instances s of player Mi are denoted as ∏is‍.The adversaryA has an endless supply of oracles ∏is‍ and makes various queries to them. Each query models a capability of adversary.(i)
Execute (S). This query returns a transcript of an honest protocol execution among instances of users in S.(ii)
Send (∏is‍,m). This query sends message m to oracle ∏is‍. When oracle ∏is‍ receives the message m, it proceeds as specified in the protocol; the oracle updates its state and then generates and sends out a response message as needed. The response message is returned to the adversary A. A query of form Send (prodis′,Start′) allows adversary A to initiate an execution of the protocol.(iii)
Reveal (∏is‍). This query returns the session key K if oracle ∏is‍ has computed a session key. This query models the capability of adversary to obtain some session keys.(iv)
Corrupt (Mi). The long-term private key of user Mi is returned in response to the query which is considered to deal with forward secrecy.(v)
Dump (∏is‍). This query returns all short-term secret values used by oracle ∏is‍, modeling the adversary’s capability to embed a Trojan horse or other forms of malicious code into a system and then log all the session-specific information of victim. But neither the session key K computed by ∏is‍ nor the long-term private key SKi is returned.(vi)
Test (∏is‍). This query is asked only once when the adversary A wants to attempt to distinguish the real session key K from a random fake key, modeling the semantic security of session key K. To answer the query, one flips a secret coin b and returns the real session key K if b=1, or else a random string chosen from {0,1}l, if b=0, where l is the length of session key to be distributed in the protocol. This query is made only if oracle ∏is‍ is fresh, and the definition of which will be given below.To quantify the ability of an adversaryA, one consider the query action of A here. During the execution of protocol, the adversary A, at any time, asks a Test query to a fresh oracle, then gets back an l-bit string as the response to this query, and at some later point, outputs a bit b′ as a guess for the hidden bit b. Let Correct Guess (CG) be the event that b′=b. Then we define the advantage of A in attacking protocol P to be
(6)AdvA,P(k)=2Pr[CG]-1.
We define protocol P as secure against an adversary A if AdvA,P(k) is negligible.According to the illustration of XTR-DDH problem in Section2, a formal description of XTR-DDH assumption is displayed below.LetG=Tr(〈g〉) be XTR group, and let x,y,z be randomly chosen elements in Zp. Informally, the XTR-DDH assumption is that it is difficult to distinguish between the distributions of (Tr(gx),Tr(gy),Tr(gxy)) and (Tr(gx),Tr(gy),Tr(gz)).More formally, if we defineAdvGXTR-DDH(A) as
(7)AdvGXTR-DDH(A)=|Pr[A(Tr(g),Tr(gx),Tr(gy),Tr(gxy))=1]-Pr[A(Tr(g),Tr(gx),Tr(gy),Tr(gz))=1]|,
the XTR-DDH assumption holds in G=Tr(〈g〉) if AdvGXTR-DDH(A) is negligible for any probabilistic polynomial time adversary A. We denote by AdvGXTR-DDH(t) the maximum value of AdvGXTR-DDH(A) over all adversaries A running in time at most t.


## 4.2. Security Proof of the Key Agreement Protocol

Theorem 10.
LetA be a passive adversary attacking protocol XTR-CR, running in time t and making qex Execute queries. Then one has
(8)AdvA,P(k)≤2qexAdvGXTR-DDH(t′),
where t′=t+O(nqextexp), with texp being the time required to compute an exponentiation in G=Tr(〈g〉).Proof.
Assume thatA can guess the hidden bit b correctly with probability 1/2+ε. Then we construct from a distinguisher D that solves the XTR-DDH problem in G with probability ε/qex.
Before describing the construction ofD, we define the following two distributions.
Consider the following(9)Real={(T,K)|r1,r2,…,rn,r∈RZp,z1=Tr(gr1),…,zn=Tr(grn),z=Tr(gr),x1=Tr(grr1),…,xn=Tr(grrn),y1=x2x3⋯xn=Sb1r(Tr(g)),…,yn-1=x1x2⋯xn-2xn=Sbn-1r(Tr(g)).}Rand={(T,K)|r1,r2,…,rn,r,s1,s2,…,sn∈RZp,z1=Tr(gr1),…,zn=Tr(grn),z=Tr(gr),x1=Tr(gs1),…,xn=Tr(gsn),y1=x2x3⋯xn=Ss2+s3+⋯+sn(Tr(g)),…,yn-1=x1x2⋯xn-2xn=Ss1+⋯+sn-2+sn(Tr(g)).},where bi=∑1≤j≤n,j≠i‍rj as in protocol XTR-CR, T=(z,z1,…,zn-1,y1,…,yn-1) is the transcript of message and K=H(y1,…,yn-1,X) is the hash value. We now construct a distribution Dist by the triple (Tr(gr),Tr(gr2),Tr(gr′r2)), as below:(10)Dist={(T,K)|r1,r2,α3,β3,…,αn,βn∈RZp,z1=Tr(gr1),z2=Tr(gr2),z3=Tr(gr1α3+r2β3),…,zn=Tr(gr1αn+r2βn),z=Tr(gr),x1=Tr(grr1),x2=Tr(grr2),x3=Tr(grr1α3+r′r2β3),…,xn=Tr(grr1αn+r′r2βn),y1=x2x3⋯xn=Sc2+c3+⋯+cn(Tr(g)),…,yn-1=x1x2⋯xn-2xn=Sc1+⋯+cn-2+cn(Tr(g)).},where T, K are defined above and c1=rr1, c2=rr2, c3=rr1α3+r′r2β3,…,cn=rr1αn+r′r2βn.
If(Tr(gr),Tr(gr2),Tr(gr′r2)) is a XTR-DH triple (i.e., r=r′), then Dist=Real, since triple (Tr(g),zi,xi)=(Tr(g),Tr(ga),Tr(gar)) for all i∈[1,n]. If not, (Tr(gr),Tr(gr2),Tr(gr′r2)) is a random triple, so Dist=Rand. Thus a distribution is constructed to display the advantage of XTR-DDH.
Hence, letA′ be an algorithm that, given (T,K) computing from Real and Rand distributions, runs in time t and outputs 0 or 1. Then, we have
(11)|Pr[A′(T,K)=1∣(T,K)⟵Real]-Pr[A′(T,K)=1∣(T,K)⟵Rand]|≤AdvGXTR-DDH(t+O(n·texp)).
On the other hand, it is clear to find that the transcriptT in experiment Rand is independent of si, which implies that for any computationally unbounded adversary A, we have (12)Pr[A(T,Kb)∣(T,K1)⟵Rand;k0⟵{0,1}l;b⟵{0,1}]=12.The detail of construction of distinguisher D is given now. Assume without loss of generality that A makes its Test query to an oracle activated by the δth Execute query. The distinguisher D begins by choosing a random bit as a guess for the value of δ. Then D invokes A and simulates the queries of A. D answers all the queries from A in a specified way, following the protocol, except in the dth query. In this latter case, D embed the DDH problem instance into the transcript as follows.
Given a triple(Tr(gr),Tr(gr2),Tr(gr′r2))∈GF(p2)3, D generates (T,K) according to the distribution Dist and answers the dth Execute query of A with T. The distinguisher D aborts and outputs a random bit of d≠δ. Otherwise, D answers the Test query of A with K.
WhenA terminates and outputs its guess b′, D outputs 1 if b=b′, and 0 otherwise. If (Tr(gr),Tr(gr2),Tr(gr′r2)) is a XTR-DDH triple, from the deduction mentioned before, it is deduced that Dist=Real, and thus Pr[b=b′]=1/2+ε. If not, (Tr(gr),Tr(gr2),Tr(gr′r2) is a random triple, and then Dist=Rand and Pr[b=b′]=1/2. Finally, since Pr[d=δ]=1/qex, we obtain
(13)AdvgXTR-DDH(D)=εqex.
From AdvA,P(k)=2Pr[CG]-1, we have that
(14)12+ε=Pr[CG]=Pr[b=b′]=(AdvA,P(k)+1)2.
Therefore,
(15)AdvA,P(k)=2ε=2qexAdvGXTR-DDH(D)≤AdvGXTR-DDH(t+O(n·texp)).
Thus the theorem follows.The result of the above theorem shows that the security of proposed key agreement scheme is based on the computational difficulty of XTR-DDH problem. Also, it is shown that the proposed scheme is secure against adversary’s attacking under XTR-DDH assumption.Moreover, the result of this security proof also supports the idea of Steiner et al. [1], who proved that DDH assumption implied the G-DDH assumption. Here, G-DDH is short for group decisional Diffie-Hellman assumption, which refers to the difficulty of distinguishing g∏‍xi from a random value by knowing elements g∏‍xi for some subsets of indices i. Actually, Theorem 10 could be regarded as an evidence for this result.


## 5. Conclusions

In this paper, a constant round key agreement scheme XTR-CR is proposed on the basis of XTR cryptosystem. Three theorems are given to make a theoretical guarantee of the quick implementation of system. Moreover, under XTR-DHH assumption, the security of scheme is proved in the formal model. It is believed that this scheme is efficient both in communication and computation. Hence, this proposed scheme is reliable in the sense of achieving three efficient and secure demands: less communication, fast computation, and provable security.



---

*Source: 596868-2013-08-29.xml*