# Concurrently Deniable Group Key Agreement and Its Application to Privacy-Preserving VANETs

Authors: Shengke Zeng; Yong Chen
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

VANETs need secure communication. Authentication in VANETs resists the attack on the receipt of false information. Authenticated group key agreement (GKA) is used to establish a confidential and authenticated communication channel for the multiple vehicles. However, authentication incurs privacy leakage, that is, by using digital signature. Therefore, the deniability is deserved for GKA (which is termed as DGKA) due to the privacy protection. In the DGKA protocol, each participant interacts with intended partners to establish a common group session key. After this agreement session, each participant can not only be regarded as the intended sender but also deny that it has ever participated in this session. Therefore, under this established key, vehicles send confidential messages with authentication property and the deniability protects the vehicles privacy. We present a novel transformation from an unauthenticated group key agreement to a deniable (authenticated) group key agreement without increasing communication round. Our full deniability is achieved even in the concurrent setting which suits the Internet environment. In addition, we design an authenticated and privacy-preserving communication protocol for VANETs by using the proposed deniable group key agreement.


---

## Body

## 1. Introduction

Vehicular ad hoc networks (VANETs) [1] refer to the peer-to-peer networks formed by roadside units and adjacent vehicles for sharing information, including traffic information (the speed and flow of vehicles, etc.) and warning information. VANETs provide a safe and comfortable driving environment for the drivers, which avoids the congestion and traffic accidents. VANETs should provide secure communication in case false information is inserted into the network. Besides that, VANETs should also have privacy issues as vehicles are reluctant to expose the sensitive information while sharing their own traffic information.The group key agreement (GKA) provides a secure channel for the vehicles communication. GKA protocol [2] allows a group of participants to establish a common session key for a secure communication channel over an insecure network by agreement. However, key agreement without authentication incurs man-in-middle attack. In order to handle this problem, the authentication is necessary. However, authentication binds the identity, which causes the privacy leakage. In many cases, the participants do not want the third party to know their involvements in some key agreements. In other words, they want to have the capacity to deny that they have ever participated in some sessions after the key agreement execution. Hence, the deniable GKA (DGKA) protocol was presented by introducing deniability into GKA protocol. Bohli and Steinwandt first formalized the DGKA protocol in [3]. In the DGKA protocol, it is not feasible to convince a third party that these participants in a group key agreement session have been involved in the conversation from the communication transcript. In other words, each participant can deny its involvement to the third party.


### 1.1. Related Work

The deniability is formalized by introducing a simulator that can simulate the conversation transcript without secrets. Therefore, the participants can deny this as someone else would produce this indistinguishable conversation transcript. If this simulator can be run by anyone, it is denoted by the full deniability. Deniable authentication was first introduced by Dolev et al. in [4] and formally studied by Dwork et al. in [5]. The general technique to realize the deniable authentication is that the sender uses its secret (i.e., the private key) to generate a value vs. If the receiver produces a value vr which equals vs by using a related witness, the receiver is convinced of the sender’s authentication. In order to simulate the transcript (for the deniability), this witness has to be revoked. Thus, the early works such as [5, 6] require more rounds to revoke the witness upon the receipt of the committed vs (i.e., COM(vs)). In this way, the simulator run by anyone can extract this witness to simulate the transcript by rewinding steps. However, the deniability does not hold in the concurrent scenario due to the rewinding. Therefore, the timing assumption is necessary to be considered to realize concurrent deniability, such as [5, 6].However, the timing assumption is farfetched for the Internet which is a fully concurrent environment. Some related works have to handle this problem by avoiding rewinding. Di Raimondo et al. [7] showed that the plaintext-awareness [8] of the underlying encryption can extract the witness for the simulation without rewinding steps. Jiang’s work [9] depends on the public random oracle to extract the witness and therefore the rewinding steps are not necessary. Yao and Zhao [10, 11] proposed the deniable Internet key exchange based on the knowledge of exponent assumption (KEA). By the KEA assumption, the witness can be extracted and the transcripts are perfectly simulated. Tian et al. [12] made use of the selectively unforgeable but existentially forgeable signature to simulate the transcript. Zeng et al. [13] presented a multireceiver encryption under KEA assumption and used it as a building block to propose a concurrently deniable ring authentication. Jiang [14] made use of a moderate encryption to avoid rewinding to construct the concurrently deniable key exchange. These approaches achieve the deniability without rewinding steps; thus the simulation even in the concurrent scenario is normal. However, as we see above, these works suffer the limitations such as the strong assumptions, inefficiency, or random oracles.Deniable authentication has been applied to many occasions nowadays [13, 15, 16] and was first introduced into the two-party key exchange protocol [17] in [18]. Mao and Paterson [18] informally defined the deniable key exchange (DKE) protocol and obtained its deniability by using identity-based techniques. Later, how to use the approach in [19] to design a DKE protocol was discussed and a concrete approach was proposed in [20], where the technique based on the public information was used to derive a symmetric key for authentication. Following this work, a series of DKE protocols were proposed in [10, 21, 22].When a two-party DKE protocol is extended to a group setting, there may be some troubles [23, 24]. If there exists malicious insiders, the use of a common symmetric key for deniable authentication is infeasible as the malicious participants may impersonate other participants [3]. A solution provided in [3] is to make use of Schnorr’s zero-knowledge identification scheme [25]. This approach needs 4 rounds to complete the establishment of session key and its efficiency was improved by Zhang et al. [26], which reduced the communication round to 3. Some approaches [27–29] transform the passively secure group key establishment to an actively secure one by adding one more round and the deniability was achieved as well.DGKA protocols can be applied to VANETs to provide the security and privacy protection for vehicles. In recent years, wireless networks (WN) have achieved rapid development [30], and their security issues have been extensively studied [31–33]. As a kind of WN, the security of VANETs should be taken seriously due to the high risk. Some related schemes for secure communication in VANETs have been presented [34–36]. Huang et al. [35] proposed a communication scheme based on GKA protocol that the roadside unit generated session key for adjacent vehicles in batches. This scheme could effectively reduce the cost of computation and communication. In [36], a representative selected from the adjacent vehicles was arranged to communicate with the roadside unit, thus making that the security of other vehicles guaranteed. Nevertheless, the public verification in these works leaks the privacy of vehicles. Hence, the deniable group key agreement is necessary to apply to privacy-preserving communication for VANETs.


### 1.2. Contribution

We focus on the full deniability of the authenticated group key agreement. We provide a generic transformation from unauthenticated GKA to DGKA without increasing any additional communication rounds. Moreover, our deniability does not require rewinding steps; thus it holds even in the concurrent environment such as Internet. We also do not depend on any strong assumptions to reach the full deniability. The contribution of this work is as follows.(1)
We present a generic transformation from an unauthenticated GKA (named as DB protocol [37]) to a deniable (authenticated) GKA. The existing works achieve the full deniability by the rewinding steps, KEA assumption (which is strong), or the public random oracles. It results in inefficiency or insecurity (strong assumption). Our approach does not resort to these ways. We do not require that the underlying primitive is PA secure and the random oracles are not necessary.(2)
Our work achieves the concurrent deniability without timing constraint. In concurrent setting, the adversary can open and schedule sessions arbitrarily. Indeed, our simulation does not require extracting the witness by rewinding steps. Thus, the concurrent session attack (i.e., adversaries schedule the executions or delay messages in arbitrary ways) does not work in our scheme.(3)
We realize the optimal communication complexity. Our transformation does not increase the round of the unauthenticated one (original DB) although it realizes the property of privacy-preserving authentication in GKA, while the related works such as [3, 26] have to increase the additional rounds to obtain the deniability.(4)
We also design a privacy-preserving communication protocol for VANETs using the proposed DGKA protocol. In this communication protocol, the vehicles share their information without leaking any identity privacy and without leaving any evidence in the transcript of authentication.Organization. This paper is organized as follows. Section 2 introduces some preliminaries which are the building blocks in our protocol. Section 3 describes the adversarial model and related security definitions of the DGKA. We propose an efficient DGKA protocol with 2 rounds in Section 4. The security of DGKA protocol is proven and the performance is analyzed in Section 5. We design a privacy-preserving protocol for VANETs in Section 6. Section 7 concludes this work.


## 1.1. Related Work

The deniability is formalized by introducing a simulator that can simulate the conversation transcript without secrets. Therefore, the participants can deny this as someone else would produce this indistinguishable conversation transcript. If this simulator can be run by anyone, it is denoted by the full deniability. Deniable authentication was first introduced by Dolev et al. in [4] and formally studied by Dwork et al. in [5]. The general technique to realize the deniable authentication is that the sender uses its secret (i.e., the private key) to generate a value vs. If the receiver produces a value vr which equals vs by using a related witness, the receiver is convinced of the sender’s authentication. In order to simulate the transcript (for the deniability), this witness has to be revoked. Thus, the early works such as [5, 6] require more rounds to revoke the witness upon the receipt of the committed vs (i.e., COM(vs)). In this way, the simulator run by anyone can extract this witness to simulate the transcript by rewinding steps. However, the deniability does not hold in the concurrent scenario due to the rewinding. Therefore, the timing assumption is necessary to be considered to realize concurrent deniability, such as [5, 6].However, the timing assumption is farfetched for the Internet which is a fully concurrent environment. Some related works have to handle this problem by avoiding rewinding. Di Raimondo et al. [7] showed that the plaintext-awareness [8] of the underlying encryption can extract the witness for the simulation without rewinding steps. Jiang’s work [9] depends on the public random oracle to extract the witness and therefore the rewinding steps are not necessary. Yao and Zhao [10, 11] proposed the deniable Internet key exchange based on the knowledge of exponent assumption (KEA). By the KEA assumption, the witness can be extracted and the transcripts are perfectly simulated. Tian et al. [12] made use of the selectively unforgeable but existentially forgeable signature to simulate the transcript. Zeng et al. [13] presented a multireceiver encryption under KEA assumption and used it as a building block to propose a concurrently deniable ring authentication. Jiang [14] made use of a moderate encryption to avoid rewinding to construct the concurrently deniable key exchange. These approaches achieve the deniability without rewinding steps; thus the simulation even in the concurrent scenario is normal. However, as we see above, these works suffer the limitations such as the strong assumptions, inefficiency, or random oracles.Deniable authentication has been applied to many occasions nowadays [13, 15, 16] and was first introduced into the two-party key exchange protocol [17] in [18]. Mao and Paterson [18] informally defined the deniable key exchange (DKE) protocol and obtained its deniability by using identity-based techniques. Later, how to use the approach in [19] to design a DKE protocol was discussed and a concrete approach was proposed in [20], where the technique based on the public information was used to derive a symmetric key for authentication. Following this work, a series of DKE protocols were proposed in [10, 21, 22].When a two-party DKE protocol is extended to a group setting, there may be some troubles [23, 24]. If there exists malicious insiders, the use of a common symmetric key for deniable authentication is infeasible as the malicious participants may impersonate other participants [3]. A solution provided in [3] is to make use of Schnorr’s zero-knowledge identification scheme [25]. This approach needs 4 rounds to complete the establishment of session key and its efficiency was improved by Zhang et al. [26], which reduced the communication round to 3. Some approaches [27–29] transform the passively secure group key establishment to an actively secure one by adding one more round and the deniability was achieved as well.DGKA protocols can be applied to VANETs to provide the security and privacy protection for vehicles. In recent years, wireless networks (WN) have achieved rapid development [30], and their security issues have been extensively studied [31–33]. As a kind of WN, the security of VANETs should be taken seriously due to the high risk. Some related schemes for secure communication in VANETs have been presented [34–36]. Huang et al. [35] proposed a communication scheme based on GKA protocol that the roadside unit generated session key for adjacent vehicles in batches. This scheme could effectively reduce the cost of computation and communication. In [36], a representative selected from the adjacent vehicles was arranged to communicate with the roadside unit, thus making that the security of other vehicles guaranteed. Nevertheless, the public verification in these works leaks the privacy of vehicles. Hence, the deniable group key agreement is necessary to apply to privacy-preserving communication for VANETs.


## 1.2. Contribution

We focus on the full deniability of the authenticated group key agreement. We provide a generic transformation from unauthenticated GKA to DGKA without increasing any additional communication rounds. Moreover, our deniability does not require rewinding steps; thus it holds even in the concurrent environment such as Internet. We also do not depend on any strong assumptions to reach the full deniability. The contribution of this work is as follows.(1)
We present a generic transformation from an unauthenticated GKA (named as DB protocol [37]) to a deniable (authenticated) GKA. The existing works achieve the full deniability by the rewinding steps, KEA assumption (which is strong), or the public random oracles. It results in inefficiency or insecurity (strong assumption). Our approach does not resort to these ways. We do not require that the underlying primitive is PA secure and the random oracles are not necessary.(2)
Our work achieves the concurrent deniability without timing constraint. In concurrent setting, the adversary can open and schedule sessions arbitrarily. Indeed, our simulation does not require extracting the witness by rewinding steps. Thus, the concurrent session attack (i.e., adversaries schedule the executions or delay messages in arbitrary ways) does not work in our scheme.(3)
We realize the optimal communication complexity. Our transformation does not increase the round of the unauthenticated one (original DB) although it realizes the property of privacy-preserving authentication in GKA, while the related works such as [3, 26] have to increase the additional rounds to obtain the deniability.(4)
We also design a privacy-preserving communication protocol for VANETs using the proposed DGKA protocol. In this communication protocol, the vehicles share their information without leaking any identity privacy and without leaving any evidence in the transcript of authentication.Organization. This paper is organized as follows. Section 2 introduces some preliminaries which are the building blocks in our protocol. Section 3 describes the adversarial model and related security definitions of the DGKA. We propose an efficient DGKA protocol with 2 rounds in Section 4. The security of DGKA protocol is proven and the performance is analyzed in Section 5. We design a privacy-preserving protocol for VANETs in Section 6. Section 7 concludes this work.


## 2. Preliminaries

We show the notations and introduce the building blocks in this section.


### 2.1. Notations

The notations used in this paper are listed in Notations in DGKA Protocol.


### 2.2. DB-GKA Protocol

Our deniable group key agreement (DGKA) protocol is developed on the basis of Dutta-Barua (DB) GKA protocol [37], which is a 2-round unauthenticated GKA protocol. It is a variant of [38]. We now review the original DB-GKA protocol [37]. Each participant Ui chooses xi as its short-term private key, computes Xi=gxi, and broadcasts Xi in the first round. In Round 2, upon the receipt of messages (Xi-1,Xi+1), Ui computes Yi=f(Xi-1,Xi+1) and broadcasts it. Finally, each Ui generates the common session key sk with the received Yi and its secret xi. The concrete DB-GKA protocol is presented in Algorithm 1. The security of DB-GKA protocol has been proven in [37].Algorithm 1:DB-GKA protocol without authentication.
Round 1: Participant Ui performs the following steps: (1) Choose xi∈Zq∗ and compute Xi=gxi. (2) Broadcast message (Ui,Xi). Round 2: Upon receiving messages (Ui-1,Xi-1) and (Ui+1,Xi+1), each Ui does as following: (1) Compute YiL=Xi-1xi, YiR=Xi+1xi, Yi=YiR/YiL. (2) Broadcast message (Ui,Yi). Session Key Generation: Upon receiving all messages (Uj,Yj)j∈{1,…,n},j≠i, each Ui carries out the following steps: (1) Compute orderly Y^i+1R=Yi+1⋅YiR, Y^i+2R=Yi+2⋅Y^i+1R,…,Y^i+(n-1)R=Yi+(n-1)⋅Y^i+(n-2)R. (2) Check YiL=?Y^i+(n-1)R. If it is true, continue; Otherwise, abort. (3) Generate the session key sk=Y^1R⋅Y^2R⋅…⋅Y^nR=gx1x2+x2x3+⋯+xnx1.


### 2.3. Ring Signature with 2 Members

Our deniable group key agreement protocol provides the deniability based on the ring signature with 2 members. Now we introduce the syntax and the security properties of the ring signature with 2 members.The ring signature scheme was used to sign a message privately. Given a valid ring signatureσ with respect to a message M and a set of public keys PK={PK1,…,PKn}, any verifier cannot decide which member in set PK is the actual signer.We consider the ring signature withn members where n=2. The syntax of the ring signature is as follows.(1)
A probabilistic key generation algorithmKGen: given the security parameter κ, output the key pair (PKi,SKi) for Ui(i=1,2). That is, (PKi,SKi)←KGen(1κ).(2)
A probabilistic ring signing algorithmRSig: given a message M, two public keys (PK1,PK2), and a private (signing) key of Uk(k∈{1,2}), output the ring signature σ. That is, σ←RSig(M,(PK1,PK2);SKk).(3)
A deterministic verification algorithmRVer: given the ring signature σ, the message M, and the two public keys (PK1,PK2), determine whether σ is valid with respect to (M,PK1,PK2). That is, check 1=?RVer(σ,M,PK1,PK2).The properties of a secure ring signature with 2 members contain theunconditional anonymity andunforgeability as follows.(i)
Unconditional Anonymity. The distributions of the two ring signatures σ1←RSig (M,(PK1,PK2);SK1) and σ2←RSig(M(PK1,PK2);SK2) are statistic, identical. It implies that, given a ring signature σ with respect to (M,PK1,PK2), no one can decide the signer although the private keys (SK1,SK2) are revealed.(ii)
Unforgeability. A forger without the signing key SK1 or SK2 forges a ring signature σ^ with respect to (M,PK1,PK2). The probability that 1←RVer(σ^,M,PK1,PK2) is negligible.


## 2.1. Notations

The notations used in this paper are listed in Notations in DGKA Protocol.


## 2.2. DB-GKA Protocol

Our deniable group key agreement (DGKA) protocol is developed on the basis of Dutta-Barua (DB) GKA protocol [37], which is a 2-round unauthenticated GKA protocol. It is a variant of [38]. We now review the original DB-GKA protocol [37]. Each participant Ui chooses xi as its short-term private key, computes Xi=gxi, and broadcasts Xi in the first round. In Round 2, upon the receipt of messages (Xi-1,Xi+1), Ui computes Yi=f(Xi-1,Xi+1) and broadcasts it. Finally, each Ui generates the common session key sk with the received Yi and its secret xi. The concrete DB-GKA protocol is presented in Algorithm 1. The security of DB-GKA protocol has been proven in [37].Algorithm 1:DB-GKA protocol without authentication.
Round 1: Participant Ui performs the following steps: (1) Choose xi∈Zq∗ and compute Xi=gxi. (2) Broadcast message (Ui,Xi). Round 2: Upon receiving messages (Ui-1,Xi-1) and (Ui+1,Xi+1), each Ui does as following: (1) Compute YiL=Xi-1xi, YiR=Xi+1xi, Yi=YiR/YiL. (2) Broadcast message (Ui,Yi). Session Key Generation: Upon receiving all messages (Uj,Yj)j∈{1,…,n},j≠i, each Ui carries out the following steps: (1) Compute orderly Y^i+1R=Yi+1⋅YiR, Y^i+2R=Yi+2⋅Y^i+1R,…,Y^i+(n-1)R=Yi+(n-1)⋅Y^i+(n-2)R. (2) Check YiL=?Y^i+(n-1)R. If it is true, continue; Otherwise, abort. (3) Generate the session key sk=Y^1R⋅Y^2R⋅…⋅Y^nR=gx1x2+x2x3+⋯+xnx1.


## 2.3. Ring Signature with 2 Members

Our deniable group key agreement protocol provides the deniability based on the ring signature with 2 members. Now we introduce the syntax and the security properties of the ring signature with 2 members.The ring signature scheme was used to sign a message privately. Given a valid ring signatureσ with respect to a message M and a set of public keys PK={PK1,…,PKn}, any verifier cannot decide which member in set PK is the actual signer.We consider the ring signature withn members where n=2. The syntax of the ring signature is as follows.(1)
A probabilistic key generation algorithmKGen: given the security parameter κ, output the key pair (PKi,SKi) for Ui(i=1,2). That is, (PKi,SKi)←KGen(1κ).(2)
A probabilistic ring signing algorithmRSig: given a message M, two public keys (PK1,PK2), and a private (signing) key of Uk(k∈{1,2}), output the ring signature σ. That is, σ←RSig(M,(PK1,PK2);SKk).(3)
A deterministic verification algorithmRVer: given the ring signature σ, the message M, and the two public keys (PK1,PK2), determine whether σ is valid with respect to (M,PK1,PK2). That is, check 1=?RVer(σ,M,PK1,PK2).The properties of a secure ring signature with 2 members contain theunconditional anonymity andunforgeability as follows.(i)
Unconditional Anonymity. The distributions of the two ring signatures σ1←RSig (M,(PK1,PK2);SK1) and σ2←RSig(M(PK1,PK2);SK2) are statistic, identical. It implies that, given a ring signature σ with respect to (M,PK1,PK2), no one can decide the signer although the private keys (SK1,SK2) are revealed.(ii)
Unforgeability. A forger without the signing key SK1 or SK2 forges a ring signature σ^ with respect to (M,PK1,PK2). The probability that 1←RVer(σ^,M,PK1,PK2) is negligible.


## 3. Model of Deniable Group Key Agreement Protocol

### 3.1. Syntax

The syntax of the deniable group key agreement (DGKA) protocol is as follows. LetU={U1,…,Un} denote the set of n potential participants who would like to build a common session key to communicate securely. Each participant Ui∈U has a private/public key pair (SKi,PKi) and the public keys are authenticated and can be accessed by any member. The DGKA protocol may be executed among any subsets of U at any time. At the end of this execution, the common session key is built. Each participant is convinced of the identity of his partners. In addition, all of them can also deny the involvement in this conversation of this session.


### 3.2. Security Model

We formalize the underlying adversarial behaviors in this subsection.(i)
Execute(pidili): this query models the passive attacks in which the adversary can only eavesdrop the execution of protocol among the participants in pidili and outputs the transcript of the session sidili. The transcript consists of the messages that are exchanged during the honest execution of the protocol.(ii)
Send(d,i,li,M): this query models the active attacks which the adversary can arbitrarily eavesdrop, delay, modify, and insert on any message M. The output of this query is the reply generated by instance πili. When d=0, the query initializes the execution of the instance πili.(iii)
Reveal(i,li): if instance πili has successfully accepted the session key skili, then skili is returned. Otherwise, NULL is returned.(iv)
Corrupt(i): the long-term private key of participant Ui is returned, and the future action will be fully taken by adversary. This query implies that there exists the malicious insiders.(v)
Test(i,li): the query is allowed only once. The queried instance πili must be fresh and skili is not NULL. Furthermore, this session as well as its partnered session should not be issued when a Corrupt query or Reveal query occurs. When the Test query occurs, a bit b∈{0,1} is randomly chosen. The session key skili is returned if b=1; otherwise a random value of the same length is returned if b=0.(vi)
Response: the adversary outputs a guess bitb′. We say that the adversary wins the game if b′=b. Let SuccA denote the event that the adversary wins the game and AdvA denote the advantage of the adversary by AdvA=|Pr[SuccA]-1/2|.Freshness. An instance πili is fresh if none of the following happens: (1) A Reveal(i,li) query or a Reveal(j,lj) query happens, where πili is partnered with πjlj. (2) A Corrupt(j) query happens, where Uj∈pidili.Partnering. The instances πili and πjlj are said to be partnered if sidili=sidjlj and pidili=pidjlj.Communicational  Networks. We assume that our protocol is executed in the broadcasting channel; thus the adversaries can arbitrarily eavesdrop, delay, modify, and insert any message.A secure DGKA protocol should satisfy thecorrectness,deniability,authentication, andsecrecy.Correctness. This property states that the protocol will establish a session key without adversarial interference. The DGKA protocol is said to be correct if for any pair of instances πili and πjlj (i,j=1,…,n and i≠j), which have been accepted with sidili=sidjlj and pidili=pidjlj, the condition skili=skjlj≠NULL holds.Deniability. This deniability states that the adversary cannot convince anyone that the honest participants have indeed joined in some sessions. Let Ad be the adversary that violates the deniability. We use thesimulation paradigm to formally define the deniability. We construct a simulator S that is a probabilistic polynomial time (PPT) Turing machine. The simulator S can answer all queries from the adversary Ad, and its inputs only involve the public information and the long-term private keys of the corrupted participants. Let ViewS denote the outputs of the adversary Ad after interacting with the simulator S. Let ViewR denote the outputs of the adversary Ad in the real world. The protocol is said to be deniable if, for any PPT adversary Ad and the distinguisher D with unbounded computation, there exists a simulator S, such that PrDViewS=1-Pr⁡DViewR=1=negl(κ).Authentication. The authentication of the protocol guarantees that the received messages of the participants come from the intended participants. If an adversary Aa that may even be a malicious insider can impersonate an uncorrupted participant Ui and succeed to accomplish the protocol, then we say the adversary violates the authentication of DGKA protocol. We use Forge to denote the event that the adversary succeeds in cheating the honest participants. The protocol is said to be authenticated if Pr⁡[Forge]≈negl(κ) for any PPT adversary.Secrecy. The secrecy of the protocol states that the session key is known only to participants but is random to outsiders. Formally, let A be the adversary that violates the secrecy and SuccA denote the success of A in the Test query, who decides the session key from a random value successfully. We say the protocol meets the secrecy if Pr⁡[SuccA]≈1/2+negl(κ).


## 3.1. Syntax

The syntax of the deniable group key agreement (DGKA) protocol is as follows. LetU={U1,…,Un} denote the set of n potential participants who would like to build a common session key to communicate securely. Each participant Ui∈U has a private/public key pair (SKi,PKi) and the public keys are authenticated and can be accessed by any member. The DGKA protocol may be executed among any subsets of U at any time. At the end of this execution, the common session key is built. Each participant is convinced of the identity of his partners. In addition, all of them can also deny the involvement in this conversation of this session.


## 3.2. Security Model

We formalize the underlying adversarial behaviors in this subsection.(i)
Execute(pidili): this query models the passive attacks in which the adversary can only eavesdrop the execution of protocol among the participants in pidili and outputs the transcript of the session sidili. The transcript consists of the messages that are exchanged during the honest execution of the protocol.(ii)
Send(d,i,li,M): this query models the active attacks which the adversary can arbitrarily eavesdrop, delay, modify, and insert on any message M. The output of this query is the reply generated by instance πili. When d=0, the query initializes the execution of the instance πili.(iii)
Reveal(i,li): if instance πili has successfully accepted the session key skili, then skili is returned. Otherwise, NULL is returned.(iv)
Corrupt(i): the long-term private key of participant Ui is returned, and the future action will be fully taken by adversary. This query implies that there exists the malicious insiders.(v)
Test(i,li): the query is allowed only once. The queried instance πili must be fresh and skili is not NULL. Furthermore, this session as well as its partnered session should not be issued when a Corrupt query or Reveal query occurs. When the Test query occurs, a bit b∈{0,1} is randomly chosen. The session key skili is returned if b=1; otherwise a random value of the same length is returned if b=0.(vi)
Response: the adversary outputs a guess bitb′. We say that the adversary wins the game if b′=b. Let SuccA denote the event that the adversary wins the game and AdvA denote the advantage of the adversary by AdvA=|Pr[SuccA]-1/2|.Freshness. An instance πili is fresh if none of the following happens: (1) A Reveal(i,li) query or a Reveal(j,lj) query happens, where πili is partnered with πjlj. (2) A Corrupt(j) query happens, where Uj∈pidili.Partnering. The instances πili and πjlj are said to be partnered if sidili=sidjlj and pidili=pidjlj.Communicational  Networks. We assume that our protocol is executed in the broadcasting channel; thus the adversaries can arbitrarily eavesdrop, delay, modify, and insert any message.A secure DGKA protocol should satisfy thecorrectness,deniability,authentication, andsecrecy.Correctness. This property states that the protocol will establish a session key without adversarial interference. The DGKA protocol is said to be correct if for any pair of instances πili and πjlj (i,j=1,…,n and i≠j), which have been accepted with sidili=sidjlj and pidili=pidjlj, the condition skili=skjlj≠NULL holds.Deniability. This deniability states that the adversary cannot convince anyone that the honest participants have indeed joined in some sessions. Let Ad be the adversary that violates the deniability. We use thesimulation paradigm to formally define the deniability. We construct a simulator S that is a probabilistic polynomial time (PPT) Turing machine. The simulator S can answer all queries from the adversary Ad, and its inputs only involve the public information and the long-term private keys of the corrupted participants. Let ViewS denote the outputs of the adversary Ad after interacting with the simulator S. Let ViewR denote the outputs of the adversary Ad in the real world. The protocol is said to be deniable if, for any PPT adversary Ad and the distinguisher D with unbounded computation, there exists a simulator S, such that PrDViewS=1-Pr⁡DViewR=1=negl(κ).Authentication. The authentication of the protocol guarantees that the received messages of the participants come from the intended participants. If an adversary Aa that may even be a malicious insider can impersonate an uncorrupted participant Ui and succeed to accomplish the protocol, then we say the adversary violates the authentication of DGKA protocol. We use Forge to denote the event that the adversary succeeds in cheating the honest participants. The protocol is said to be authenticated if Pr⁡[Forge]≈negl(κ) for any PPT adversary.Secrecy. The secrecy of the protocol states that the session key is known only to participants but is random to outsiders. Formally, let A be the adversary that violates the secrecy and SuccA denote the success of A in the Test query, who decides the session key from a random value successfully. We say the protocol meets the secrecy if Pr⁡[SuccA]≈1/2+negl(κ).


## 4. Our Deniable Group Key Agreement Protocol

We construct the deniable GKA protocol based on Dutta-Barua (DB) GKA protocol [37], which is elaborated in Section 2. Our DGKA protocol achieves the deniable authentication by employing a ring signature with 2 members. We first give the high level description of our DGKA protocol.Considering a ring signature scheme with two members: a real participant and a logic entity. In the first round, each participant follows DB-GKA protocol to generateXi. Besides that, each one also produces another group element Ti. The product of each Ti is viewed as the public key of the logic entity. Therefore, in the second round, each participant gathers all Ti to result T. Then each one uses its own public key PKi and the logic public key T to form a ring to generate a ring signature on the message (X1,…,Xn,Yi) with its signing key SKi. The corresponding private key of the logic public key T is unknown to any participant and the third party. Thus, a valid ring signature implies that the authentication to (X1,…,Xn,Yi) can be completed only by the participant Ui. The authentication is achieved. On the other hand, the simulator can simulate the value T by its random choice of the exponent t to get T=gt. Then, the simulator produces a ring signature σ′=RSig(M,(PKi,T);t) with the “private key” of T. By the unconditional anonymity property of the ring signature, the two distributions of σ=RSig(M,(PKi,T);SKi) and σ′=RSig(M,(PKi,T);t) are statistic, identical, where the former one is the real transcription. Therefore, the simulation is perfect and the deniability is achieved. Since the rewinding steps are not necessary in the simulation, the deniability can also hold in the concurrent setting. We give a detailed description of our protocol in Algorithm 2.Algorithm 2:Our deniable group key agreement protocol.
Let(SKi,PKi) denote the private/public key pair for the participant Ui and n is the number of the participants of this session. Round 1: Participant Ui performs the following steps: (1) Choose xi,ti∈Zq∗ and compute Xi=gxi, Ti=gti. (2) Broadcast message Mi1=(Ui,Xi,Ti). Round 2: Upon the receipt of all messages {Mj1}j∈{1,…,n},j≠i, Ui parses Xi-1, Xi+1 and {Tj}j∈{1,…,n},j≠i. Next, Ui executes the following operations: (1) Compute YiL=Xi-1xi, YiR=Xi+1xi, Yi=YiR/YiL, T=∏j=1n‍Tj. (2) Generate a two-member ring signature on the message M=(X1,…,Xn,Yi): σi=RSig(M,(PKi,T);SKi). (3) Broadcast message Mi2=(Ui,Yi,σi). Session Key Generation: Upon the receipt of all messages {Mj2}j∈{1,…,n},j≠i, each Ui carries out the following steps: (1) Compute orderly Y^i+1R=Yi+1⋅YiR, Y^i+2R=Yi+2⋅Y^i+1R,…,Y^i+(n-1)R=Yi+(n-1)⋅Y^i+(n-2)R. Check YiL=?Y^i+(n-1)R. If it is true, continue; Otherwise, abort. (2) Check 1=RVer(σi,M,PKj,T) hold or not for j=1,…,n and j≠i. If it fails to any participant, abort; Otherwise, continue. (3) Generate the session key sk=Y^1R⋅Y^2R⋅…⋅Y^nR=gx1x2+x2x3+⋯+xnx1.Remark 1.
The ring signature is with 2 members. One is the participantUi, and the other one is a logic entity whose public key is T=∏j=1nTj. Obviously, the private key of T is t=∑j=1ntj and it is unknown to anybody. In the real conversation, Ui uses its private key SKi to generate the ring signature σ. Since σ is only bounded to 2 public keys and one of the public key is logic with unknown secret, the partner can be convinced of Ui’s signing. The authentication is completed. Meanwhile, in the simulation, the simulator simulates t (as no secret value is required) to produce the ring signature. Obviously, this simulation is perfect without any rewinding steps; concurrent deniability is realized.


## 5. Security and Performance

In this section, we analyze the security and performance of our protocol. Since the verification ofcorrectness of our protocol is straightforward, in what follows we will prove that our protocol meets the other three properties:deniability,authentication, andsecrecy, which have been presented in the security model. Then we give the performance comparisons of the related deniable key agreements regarding the communication round and the deniability.


### 5.1. Security

#### 5.1.1. Deniability

This property states that all the participants can deny the fact that they have joined in the generation of the session key. We use thesimulation fashion to prove that our protocol satisfies the deniability. That is, if a simulator without any participant’s secret can simulate the transcript and the simulated transcript is indistinguishable from the real one, then we say the deniability is proven. Formal proof is presented as follows.Theorem 2.
The DGKA protocol is concurrently deniable if the underlying ring signature is secure.Proof.
In order to prove our protocol satisfying the deniability, we have to show the real view and the simulated view are indistinguishable. Formally, we construct a simulatorS, whose inputs involve the public information and the long-term private keys of the corrupted participants. Ad is an adversary that violates the deniability of the protocol. Use ViewR to denote the view of Ad in the real conversation and ViewS to denote the view of Ad in the simulated setting performed by S. We show that any distinguisher D with unbounded computation cannot distinguish ViewR and ViewS.
With the inputs of{PKi} and the long-term private keys of the corrupted participants, S simulates the Send, Corrupt, and Reveal queries for Ad as follows.(i)
Send(0,i,li,M): S normally performs protocol and answers the query as it does not require any secrets. S randomly chooses xi,ti∈Zi∗ to compute Xi, Ti, respectively. Then, S broadcasts message Mi1=(Ui,Xi,Ti) and records statili=(xi,Xi,ti,Ti).(ii)
Send(1,i,li,M): S checks if Ui has been corrupted.
(a)
IfUi has been corrupted, S with the known private key SKi simulates Mi2 normally.(b)
IfUi is uncorrupted, S retrieves xj,tj from statjlj to compute Yj (where j=1,…,n), t=∑j=1ntj, and T=gt. Then S produces a ring signature σi=RSig(M,(PKi,T);t). S updates statili=(xi,ti,Xi,Ti,Yi,σi).(iii)
Send(2,i,li,M): S normally answers the query no matter whether Ui has been corrupted or not as there is no secret required.(iv)
Reveal(i,li): S computes the session key skili according to the protocol and returns it to Ad.(v)
Corrupt(i): S returns the private key SKi of participant Ui and the fact that Ui is corrupted is marked.
Now, we argue thatViewR and ViewS are perfectly identical. It is obvious that S does not introduce any difference from the view of real one when Send(0,i,li,M), Send(2,i,li,M), Reveal(i,li), and Corrupt(i) are asked. Let us consider Send(1,i,li,M). In the real transcript, Send(1,i,li,M) is performed using Ui’s private key SKi. In the simulation, this oracle is answered using t, which is the private key of the logic party (whose public key is T=gt). This is a ring signing with Ui and the logic party. Since the underlying ring signature scheme with two members is secure, it implies that the unconditional anonymity property holds. If Send(1,i,li,M) introduces any difference, which means the ring signature under SKi and the ring signature under t can be distinguishable, obviously, it breaks the unconditional anonymity of this ring signature scheme. It is a contradiction.


#### 5.1.2. Authentication

Authentication states that eachUi can ensure that the message it received is authenticated by the intended partner. This property can prevent the man-in-middle attack which exists in the unauthenticated key agreement protocol. In our protocol, we apply the ring signature with two members to preserve the authentication. Indeed, the generated ring signature σi is bounded to two public keys PKi and T. Due to the unforgeability of the ring signature, anyone who knows SKi or t can generate a valid signature. Given a valid σi, the partner is convinced that M=(X1,…,Xn,Yi) which is used to generate the common session key is signed by Ui as t is unknown to anyone. Obviously, our protocol is authenticated due to the unforgeability of the underlying ring signature scheme.


#### 5.1.3. Secrecy

This property ensures the security of the session key. That is, any member without participating in the session cannot obtain the session key. Obviously, our DGKA protocol satisfies the secrecy if DB-GKA protocol produces the session key securely. It is easy to see that our DGKA protocol equals the original DB-GKA protocol only except that we provide a ring signing on(X1,…,Xn,Yi) in DGKA. We denote the game G0 as the environment of DB-GKA protocol and the game G1 as the environment of our DGKA. Let Forge be the event that A succeeds in forging a valid message after Round 2. The difference between the games G0 and G1 is that the challenger in G1 would stop the simulation when the event Forge occurs. However, Pr⁡[Forge] is negligible as the authentication property states. Therefore, the secrecy of our DGKA protocol can be reduced to the secrecy of DB-GKA, which is proven in [37].


### 5.2. Performance

The obvious advantage of our construction is the optimal communication round. We transfer the unauthenticated DB-GKA protocol to the deniable GKA without increasing round. While other related DGKA protocols are more than 2 rounds.One DGKA protocol [3] is based on Schnorr’s zero-knowledge identification scheme; the participants make the commitments in Round 1. Next, an unauthenticated GKA protocol is executed in Rounds 2 and 3. The deniable authentication is achieved in Round 4. It needs 4 rounds to complete the protocol. Similarly, in [26], the participants also make commitments in Round 1. At the same time, the participants begin to execute the unauthenticated GKA protocol in this round. Finally, the deniable authentication is executed in Round 3. It is easy to see that the deniable authentication depends on the generated session key in [3, 26]. This is the reason that these two protocols require more rounds than the unauthenticated GKA to realize the deniable authentication.Our protocol makes use of the unconditional anonymity of the ring signature to achieve the concurrent deniability. This ring signature is bounded to 2 members. The one is the actual participant and the other one is a logic party. This logic public key is accumulated by all participants with its own secret in Round 1. Then each participant uses the logic public key and its own public key to form a ring and signs the elements which are used to generate the common session key in Round 2. Obviously, the deniability is no longer dependent on the session key. Therefore, our work does not increase the communication round of the unauthenticated GKA.We also focus on the concurrent deniability. However, both [3, 26] depend on the rewinding steps to simulate the transcript. Therefore, the deniability cannot hold in the concurrent setting. Some other deniable authentication protocols or deniable key exchange protocols which realize the concurrent deniability depend on the strong assumptions/primitives, such as KEA assumption, public random oracle, or timed commitment/encryption to extract the witness for the simulations. Compared with them, our DGKA protocol is not restricted to these limitations.The comparisons of the related protocols with deniability are listed in the Table1.Table 1
Comparisons of deniable key agreement protocols.
Scheme Scale Round Concurrency RO Deniability realization [3] group 4 × ✓ Rewinding [26] group 3 × - Rewinding [10] 2-party 2 ✓ ✓ KEA assumption [22] 2-party 2 ✓ ✓ Public RO Proposed group 2 ✓ - Ring signature


## 5.1. Security

### 5.1.1. Deniability

This property states that all the participants can deny the fact that they have joined in the generation of the session key. We use thesimulation fashion to prove that our protocol satisfies the deniability. That is, if a simulator without any participant’s secret can simulate the transcript and the simulated transcript is indistinguishable from the real one, then we say the deniability is proven. Formal proof is presented as follows.Theorem 2.
The DGKA protocol is concurrently deniable if the underlying ring signature is secure.Proof.
In order to prove our protocol satisfying the deniability, we have to show the real view and the simulated view are indistinguishable. Formally, we construct a simulatorS, whose inputs involve the public information and the long-term private keys of the corrupted participants. Ad is an adversary that violates the deniability of the protocol. Use ViewR to denote the view of Ad in the real conversation and ViewS to denote the view of Ad in the simulated setting performed by S. We show that any distinguisher D with unbounded computation cannot distinguish ViewR and ViewS.
With the inputs of{PKi} and the long-term private keys of the corrupted participants, S simulates the Send, Corrupt, and Reveal queries for Ad as follows.(i)
Send(0,i,li,M): S normally performs protocol and answers the query as it does not require any secrets. S randomly chooses xi,ti∈Zi∗ to compute Xi, Ti, respectively. Then, S broadcasts message Mi1=(Ui,Xi,Ti) and records statili=(xi,Xi,ti,Ti).(ii)
Send(1,i,li,M): S checks if Ui has been corrupted.
(a)
IfUi has been corrupted, S with the known private key SKi simulates Mi2 normally.(b)
IfUi is uncorrupted, S retrieves xj,tj from statjlj to compute Yj (where j=1,…,n), t=∑j=1ntj, and T=gt. Then S produces a ring signature σi=RSig(M,(PKi,T);t). S updates statili=(xi,ti,Xi,Ti,Yi,σi).(iii)
Send(2,i,li,M): S normally answers the query no matter whether Ui has been corrupted or not as there is no secret required.(iv)
Reveal(i,li): S computes the session key skili according to the protocol and returns it to Ad.(v)
Corrupt(i): S returns the private key SKi of participant Ui and the fact that Ui is corrupted is marked.
Now, we argue thatViewR and ViewS are perfectly identical. It is obvious that S does not introduce any difference from the view of real one when Send(0,i,li,M), Send(2,i,li,M), Reveal(i,li), and Corrupt(i) are asked. Let us consider Send(1,i,li,M). In the real transcript, Send(1,i,li,M) is performed using Ui’s private key SKi. In the simulation, this oracle is answered using t, which is the private key of the logic party (whose public key is T=gt). This is a ring signing with Ui and the logic party. Since the underlying ring signature scheme with two members is secure, it implies that the unconditional anonymity property holds. If Send(1,i,li,M) introduces any difference, which means the ring signature under SKi and the ring signature under t can be distinguishable, obviously, it breaks the unconditional anonymity of this ring signature scheme. It is a contradiction.


### 5.1.2. Authentication

Authentication states that eachUi can ensure that the message it received is authenticated by the intended partner. This property can prevent the man-in-middle attack which exists in the unauthenticated key agreement protocol. In our protocol, we apply the ring signature with two members to preserve the authentication. Indeed, the generated ring signature σi is bounded to two public keys PKi and T. Due to the unforgeability of the ring signature, anyone who knows SKi or t can generate a valid signature. Given a valid σi, the partner is convinced that M=(X1,…,Xn,Yi) which is used to generate the common session key is signed by Ui as t is unknown to anyone. Obviously, our protocol is authenticated due to the unforgeability of the underlying ring signature scheme.


### 5.1.3. Secrecy

This property ensures the security of the session key. That is, any member without participating in the session cannot obtain the session key. Obviously, our DGKA protocol satisfies the secrecy if DB-GKA protocol produces the session key securely. It is easy to see that our DGKA protocol equals the original DB-GKA protocol only except that we provide a ring signing on(X1,…,Xn,Yi) in DGKA. We denote the game G0 as the environment of DB-GKA protocol and the game G1 as the environment of our DGKA. Let Forge be the event that A succeeds in forging a valid message after Round 2. The difference between the games G0 and G1 is that the challenger in G1 would stop the simulation when the event Forge occurs. However, Pr⁡[Forge] is negligible as the authentication property states. Therefore, the secrecy of our DGKA protocol can be reduced to the secrecy of DB-GKA, which is proven in [37].


## 5.1.1. Deniability

This property states that all the participants can deny the fact that they have joined in the generation of the session key. We use thesimulation fashion to prove that our protocol satisfies the deniability. That is, if a simulator without any participant’s secret can simulate the transcript and the simulated transcript is indistinguishable from the real one, then we say the deniability is proven. Formal proof is presented as follows.Theorem 2.
The DGKA protocol is concurrently deniable if the underlying ring signature is secure.Proof.
In order to prove our protocol satisfying the deniability, we have to show the real view and the simulated view are indistinguishable. Formally, we construct a simulatorS, whose inputs involve the public information and the long-term private keys of the corrupted participants. Ad is an adversary that violates the deniability of the protocol. Use ViewR to denote the view of Ad in the real conversation and ViewS to denote the view of Ad in the simulated setting performed by S. We show that any distinguisher D with unbounded computation cannot distinguish ViewR and ViewS.
With the inputs of{PKi} and the long-term private keys of the corrupted participants, S simulates the Send, Corrupt, and Reveal queries for Ad as follows.(i)
Send(0,i,li,M): S normally performs protocol and answers the query as it does not require any secrets. S randomly chooses xi,ti∈Zi∗ to compute Xi, Ti, respectively. Then, S broadcasts message Mi1=(Ui,Xi,Ti) and records statili=(xi,Xi,ti,Ti).(ii)
Send(1,i,li,M): S checks if Ui has been corrupted.
(a)
IfUi has been corrupted, S with the known private key SKi simulates Mi2 normally.(b)
IfUi is uncorrupted, S retrieves xj,tj from statjlj to compute Yj (where j=1,…,n), t=∑j=1ntj, and T=gt. Then S produces a ring signature σi=RSig(M,(PKi,T);t). S updates statili=(xi,ti,Xi,Ti,Yi,σi).(iii)
Send(2,i,li,M): S normally answers the query no matter whether Ui has been corrupted or not as there is no secret required.(iv)
Reveal(i,li): S computes the session key skili according to the protocol and returns it to Ad.(v)
Corrupt(i): S returns the private key SKi of participant Ui and the fact that Ui is corrupted is marked.
Now, we argue thatViewR and ViewS are perfectly identical. It is obvious that S does not introduce any difference from the view of real one when Send(0,i,li,M), Send(2,i,li,M), Reveal(i,li), and Corrupt(i) are asked. Let us consider Send(1,i,li,M). In the real transcript, Send(1,i,li,M) is performed using Ui’s private key SKi. In the simulation, this oracle is answered using t, which is the private key of the logic party (whose public key is T=gt). This is a ring signing with Ui and the logic party. Since the underlying ring signature scheme with two members is secure, it implies that the unconditional anonymity property holds. If Send(1,i,li,M) introduces any difference, which means the ring signature under SKi and the ring signature under t can be distinguishable, obviously, it breaks the unconditional anonymity of this ring signature scheme. It is a contradiction.


## 5.1.2. Authentication

Authentication states that eachUi can ensure that the message it received is authenticated by the intended partner. This property can prevent the man-in-middle attack which exists in the unauthenticated key agreement protocol. In our protocol, we apply the ring signature with two members to preserve the authentication. Indeed, the generated ring signature σi is bounded to two public keys PKi and T. Due to the unforgeability of the ring signature, anyone who knows SKi or t can generate a valid signature. Given a valid σi, the partner is convinced that M=(X1,…,Xn,Yi) which is used to generate the common session key is signed by Ui as t is unknown to anyone. Obviously, our protocol is authenticated due to the unforgeability of the underlying ring signature scheme.


## 5.1.3. Secrecy

This property ensures the security of the session key. That is, any member without participating in the session cannot obtain the session key. Obviously, our DGKA protocol satisfies the secrecy if DB-GKA protocol produces the session key securely. It is easy to see that our DGKA protocol equals the original DB-GKA protocol only except that we provide a ring signing on(X1,…,Xn,Yi) in DGKA. We denote the game G0 as the environment of DB-GKA protocol and the game G1 as the environment of our DGKA. Let Forge be the event that A succeeds in forging a valid message after Round 2. The difference between the games G0 and G1 is that the challenger in G1 would stop the simulation when the event Forge occurs. However, Pr⁡[Forge] is negligible as the authentication property states. Therefore, the secrecy of our DGKA protocol can be reduced to the secrecy of DB-GKA, which is proven in [37].


## 5.2. Performance

The obvious advantage of our construction is the optimal communication round. We transfer the unauthenticated DB-GKA protocol to the deniable GKA without increasing round. While other related DGKA protocols are more than 2 rounds.One DGKA protocol [3] is based on Schnorr’s zero-knowledge identification scheme; the participants make the commitments in Round 1. Next, an unauthenticated GKA protocol is executed in Rounds 2 and 3. The deniable authentication is achieved in Round 4. It needs 4 rounds to complete the protocol. Similarly, in [26], the participants also make commitments in Round 1. At the same time, the participants begin to execute the unauthenticated GKA protocol in this round. Finally, the deniable authentication is executed in Round 3. It is easy to see that the deniable authentication depends on the generated session key in [3, 26]. This is the reason that these two protocols require more rounds than the unauthenticated GKA to realize the deniable authentication.Our protocol makes use of the unconditional anonymity of the ring signature to achieve the concurrent deniability. This ring signature is bounded to 2 members. The one is the actual participant and the other one is a logic party. This logic public key is accumulated by all participants with its own secret in Round 1. Then each participant uses the logic public key and its own public key to form a ring and signs the elements which are used to generate the common session key in Round 2. Obviously, the deniability is no longer dependent on the session key. Therefore, our work does not increase the communication round of the unauthenticated GKA.We also focus on the concurrent deniability. However, both [3, 26] depend on the rewinding steps to simulate the transcript. Therefore, the deniability cannot hold in the concurrent setting. Some other deniable authentication protocols or deniable key exchange protocols which realize the concurrent deniability depend on the strong assumptions/primitives, such as KEA assumption, public random oracle, or timed commitment/encryption to extract the witness for the simulations. Compared with them, our DGKA protocol is not restricted to these limitations.The comparisons of the related protocols with deniability are listed in the Table1.Table 1
Comparisons of deniable key agreement protocols.
Scheme Scale Round Concurrency RO Deniability realization [3] group 4 × ✓ Rewinding [26] group 3 × - Rewinding [10] 2-party 2 ✓ ✓ KEA assumption [22] 2-party 2 ✓ ✓ Public RO Proposed group 2 ✓ - Ring signature


## 6. A Privacy-Preserving Communication Protocol for VANETs

In this section, we design a privacy-preserving communication protocol for VANETs by using the proposed deniable group key agreement protocol. Our protocol guarantees the secure communication between vehicles and vehicles and vehicles and roadside unit. VANETs are composed of Trusted Authority (TA), roadside unit (RSU, which is the infrastructure), and On-board Units (OBUs, with which vehicles are equipped). Our security model for privacy-preserving VANETs is as follows.(i)
Authentication: in the VANETs environment, RSU and OBUs should ensure that only legitimate (certificated by TA) vehicles can join this networks. Similarly, RSU should be also authenticated by vehicles in order to prevent pseudo base stations.(ii)
Anonymity: OBUs receive the information without knowing the sender identity, but only to confirm that this message is from an authenticated group.(iii)
Privacy: the conversations among the OBUs do not leave any paper trail. This “off-the-record” property prevents the shared information from being maliciously used.(iv)
Secrecy: during the process of communication, the sent messages are only known to receivers but are random to any third parties.Our privacy-preserving communication protocol for VANETs is mainly divided into three steps. The first step is to initialize a group of VANETs. Then, OBUs and RSU in this group authenticate mutually to generate a session key. Finally, they communicate with each other with this session key under an authenticated and privacy-preserving environment.LetUi be one of vehicles and UR be RSU. (SKi,PKi)=(si,gsi) denote the private/public key pair for vehicle Ui; (SK0,PK0)=(s0,gs0) denote the private/public key pair for UR. H:{0,1}∗→{0,1}l, where l is the length of a message. A detailed protocol is given as follows.Initialization Step. The members of a group of VANETs are decided.(i)
UR randomly chooses id as the session ID and forms a group R by using its public key PK0 and the public keys of adjacent vehicles {PKi}. Finally, broadcast message Vinit=id∥R.Authentication Step. The identities of members are authenticated.(i)
Round 1 (OBUs and RSU). Choose xi, ti, and compute Xi=gxi, Ti=gti. Broadcast message Vauth1=id∥PKi∥Xi∥Ti.(ii)
Round 2 (OBUs and RSU). Compute Yi and σi as the proposed DGKA protocol (described in Algorithm 2). Broadcast message Vauth2=id∥Yi∥σi.(iii)
Key Generation (OBUs and RSU). Authenticate the identities of other members and get the session key sk as in Algorithm 2.Communication Step. With this session key sk, all the members in this group R can communicate securely. There are two cases in this step, including broadcast from UR or Ui to all members and communication from UR to Ui, Ui to UR, or Ui to Uj.(i)
Broadcast (one-to-many):
(a)
RSU or OBUs send messagemb: compute ν=H(id,sk) and e=mb⊕ν. Broadcast message Vbro=id∥e.(b)
RSU and OBUs recovermb: compute ν=H(id,sk) and mb=e⊕ν.(ii)
Communication (one-to-one):
(a)
RSU or OBUs sendmc to Ui: choose r←Zq∗ and compute R=gr, ν=H(id,R,PKir,sk), and e=mc⊕ν. Broadcast message Vcom=id∥e∥PKi∥R.(b)
Ui recovers mc: compute ν=H(id,R,Rsi,sk) and mc=e⊕ν.By employing the proposed DGKA protocol, each receiver can identify the source of the received information without knowing the actual sender by using the session keysk. Moreover, this session key sk can be simulated by anyone; the vehicles involved in the above communication can deny this. There is no paper trail; thus the vehicle privacy is protected.


## 7. Conclusions

This paper presents a 2-round fully deniable group key agreement protocol. We provide a novel approach to transfer an unauthenticated GKA to a deniable GKA without increasing round. The transcript simulation does not require the rewinding steps; thus our deniability also holds even in the concurrent setting. We also design a privacy-preserving communication protocol for VANETs using the proposed DGKA protocol.



---

*Source: 6870742-2018-04-15.xml*