DABKE: Secure deniable attribute-based key exchange framework

Abstract

We introduce the first deniable attribute-based key exchange (DABKE) framework that is resilient to impersonation attacks. We define the formal security models for DABKE framework, and propose a generic compiler that converts any attribute-based key exchanges into deniable ones. We prove that it can achieve session key security and user privacy in the standard model, and strong deniability in the simulation-based paradigm. In particular, the proposed generic compiler ensures: 1) a dishonest user cannot impersonate other user’s session participation in conversations since implicit authentication is used among authorized users; 2) an authorized user can plausibly deny his/her participation after secure conversations with others; 3) the strongest form of deniability is achieved using one-round communication between two authorized users.

Keywords

Attribute-based key exchange impersonation attacks strong deniability generic compiler

1. Introduction

Authenticated key exchange (AKE) protocols are the core cryptographic primitives for many network security standards such as IPSec/IKE, TLS and SSH. AKE aims to share a secret key among multiple users over an insecure communication channel, where users authenticate each other using their identities or public keys. AKE can further be explored in the attribute-based context [15,33,42]: attribute-based AKE (AB-AKE), which enables fine-grained access control among authorized users. Specifically, AB-AKE provides authentication to authorized users based on whether their attributes satisfy a policy. The AB-AKE mechanism is significantly useful in many real-world applications, such as distributed collaborative systems [15,33]. In practice, it is desirable for users to communicate with each other based on their roles or responsibilities instead of identities or public keys.

AB-AKE has some inherent properties such as anonymity [20] and deniability [11], because different authorized users may satisfy the same policy. The anonymity means that authorized users are anonymous from the viewpoint of communication counterparts. Such property is implicitly held in AB-AKE due to the feature of fine-grained authentication. As for deniability, it allows authorized users to deny their participating in conversations if the security of communications is later compromised. In particular, deniability is the most important property in secure messaging protocols [35,36] such as Off-the-Record (OTR) Messaging protocol [6] and Signal [28]. Since personal or business communications may be revealed or leaked in practice, deniable secure messaging protocols are becoming more important to these private communications.

The inherent anonymity may bring a security risk to AB-AKE. For example, we consider an ad hoc group of users with their associated attributes are participating in a text messaging. The secure key establishment, as a central building block of most text messaging constructions, is vulnerable to impersonation attacks. Roughly speaking, a dishonest receiver can successfully impersonate another receiver to establish a shared secret key with a text sender for subsequent conversations, if receivers with different attributes satisfy the same policy. As a result, the text sender and the impersonator (dishonest receiver) perform the delivery of messages using the established shared secret key.

One may question the importance of preventing AB-AKE from impersonation attacks. To see why it is essential, consider AB-AKE in a multi-party setting where it is possible that a malicious authorized user can successfully impersonate other authorized users. For example, a malicious user Alice attempts to impersonate an honest user Bob to establish a conversion with another user Charlie, but the impersonated user Bob was not actually involved in the conversation with Charlie. Such an attack is possible in a multi-party setting due to the inherent anonymous property of attribute-based systems. Although there are some existing works on AB-AKE [15,42], they have not addressed the issue of impersonation attacks. We stress that in the “design” of AB-AKE, such impersonation attacks naturally exist because authorized users authenticate each other based on their access policies or attributes sets. On the other hand, the impersonation attacks are indeed not desirable when using AB-AKE protocols in real-world applications such as text messaging.

The impersonation attacks are easy to prevent if non-repudiable digital signature schemes are applied to protocol transcripts. However, this contradicts to inherent deniability of AB-AKE. The main goal of this work is to design deniable key exchanges in attribute-based setting while the impersonation-resistance is held. Furthermore, it is also desirable to establish a shared secret key using minimal communication rounds. In this work, we construct a deniable attribute-based key exchange (DABKE) framework with one-round communication in a two-party setting.

We stress that designing “impersonation resistant”, “strongly deniable” and “non interactive” DABKE framework is a non-trivial task. Recall that the naive way to prevent impersonation attacks is to use non-repudiable digital signature schemes on protocol transcripts. For example, the digital signature based SIGMA protocol [11] can achieve a weak form of deniability, but not the strong deniability we desired. Such weak form of deniability merely allows an accused sender to deny his/her communication with a specific receiver in conversations, but the accused sender cannot deny his/her signed protocol transcripts. While strong deniability allows the accused sender to later plausibly deny sending messages and participating in a conversation. Another possible way is to use non-malleable zero-knowledge (ZK) proof on protocol transcripts, such as deniable AKE protocol in [41]. Its strong deniability is achieved via a challenge-response mechanism for proving the knowledge (e.g., user’s secret key) to its peer in a ZK manner. However, its construction is not one-round.

To achieve our design goal, we rely on the implicit authentication (which is used in classic HMQV protocol [21]). It means that Alice knows that the only other party who could compute the shared secret key as her is Bob (and vice versa). More precisely, if Alice later receives a message together with a MAC tag that verifies with respect to the key generated from the session, then Alice is assured that the MAC tag must have been generated by Bob [14]. The implicit authentication is naturally suitable to achieve our design goal, in the sense that it enables the impersonation-resistance while the desired one-round communication is held in a two-party setting.

In summary, deniable attribute-based key exchange DABKE framework has the following unique features.

Generic Construction. We provide a generic framework that is built on top of any implicitly authenticated key exchanges and (ciphertext-policy based) attribute-based encryption schemes. In addition, the generic framework relies on standard model assumptions;

Impersonation Resistance. Authorized users can securely authenticate each other for private conversations, and prevent impersonation attacks by exploiting implicit authentication;

Strong Deniability. Authorized users can plausibly deny their participations after secure and private conversations, even if the security of conversations is completely compromised later;

Round Efficiency. We achieve the strongest form of deniability with one-round communication between two authorized users.

1.1. Related work

Attribute-based Encryption. Sahai and Waters [30] first proposed the fuzzy identity-based encryption, in which users must match at least a certain threshold of attributes. Later, Goyal et al. [16] proposed two types of attribute-based encryption (ABE): Key-policy ABE and Ciphertext-policy ABE. In particular, Bethencourt et al. [5] proposed the first CP-ABE scheme that allowing the ciphertext policies to be very expressive, but the scheme is secure in the generic group model. Large amount of works were followed this trend, some of them [16,39] are selectively secure under CPA (chosen plaintext attack), and some of them [24,27] are adaptively secure under CPA/CCA (chosen ciphertext attack) for general policies.

Key Exchange. Burmester and Desmedt [7] introduced several key exchange protocols in the multi-party setting, including star-based, tree-based, broadcast-based and cyclic-based protocols. Later, a few generic transformations [18,19] were proposed to convert passive-secure group key exchange protocols into active-secure ones. On the security models for key exchange protocols, Bellare and Rogaway [3] introduced the first complexity-theoretic security model for key exchange under the symmetric-key setting. The model was later extended and enhanced under different settings [1,2,4]. Canetti and Krawczyk [8] later refined the previous models and proposed a new model, known as the CK model, which is widely used in the analysis of many well-known key exchange protocols. Some variants [21,22] of CK model have also been proposed to allow the adversary to obtain either long-term secret key or ephemeral secret key of the challenge session. The models in [33,42] were naturally extended from extended CK (eCK) model [22] in the attribute-based setting, which allow adversary to access the master secret key.

Deniable Key Exchange. Deniable authentication was formally introduced by Dwork et al. [13] using the simulation-based paradigm. It requires that the transmitted messages are authenticated, and the simulator’s view can be simulated using adversary’s knowledge only. Later, Di Raimondo et al. [11] considered deniability of key exchange protocols, and formally presented two definitions: strong deniability and partial deniability. In particular, they used novel techniques to analyze strong deniability of SKEME and partial deniability of SIGMA respectively. More precisely, they prove strong deniability of SKEME based on the plaintext awareness of the underlying encryption scheme (in the standard model), and prove partial deniability of SIGMA based on a special “oracle” since non-repudiable digital signature schemes are used for authentication.

Jiang and Safavi-Naini [17] proposed an efficient key exchange protocol with full deniability, which allows anyone to prove to a distinguisher (i.e., judge) that the communication between two participants happened. Their deniable key exchange protocol is proven secure under the Bellare–Rogaway model [3] in the public random oracle (pRO) (pRO is introduced by Pass [29], which is a weaker assumption compared to random oracle model). A similar deniable work was proposed by Yao and Zhao [41]. They introduced the first provably secure internet key exchange protocol that provides strong deniability for protocol participants simultaneously. In particular, their strong deniability analysis relies on the restricted random oracle model (it is analogous to Pass’s non-programmable random oracle pRO [43]) and (concurrent) knowledge of exponent assumption (KEA). Note that these solutions [17,32,38,41] are interactive deniable key exchanges.

The implicitly AKE protocols [21,31,40] formed another important research line in the literature. They are not only enjoy high performance, but also ensure strong deniability. Based on the well-known HMQV protocol, Yao and Zhao [40] proposed a family of implicitly AKE protocols. In addition, they introduced a new notion: “honest player deniability” (HP-deniability). This assumption is the strongest form of deniability for implicitly AKE protocols. Because anyone (including judge) can produce transcripts and session keys that look valid to a judge. The relationship between HP-deniability and strong deniability [11] is analogues to that between honest-verifier zero-knowledge (HVZK) and standard ZK.

Recently, Schage [31] proposed a novel implicitly AKE protocol (TOPAS in short) with full perfect forward secrecy. Interestingly, TOPAS also enjoys strong deniability defined in [11], such that adversary is actually one of session participants. In addition, Unger and Goldberg [35] proposed a newly deniable authenticated key exchange for secure messaging applications. In particular, they introduced the first non-interactive Spawn^∗ that offers forward secrecy and strong deniability against both (partical) on-line and off-line distinguishers. The security of Spawn^∗ relies on the Generalized Universal Composability (GUC) framework [38] in the standard model. We compare our proposed framework with some typical works in Table 1 to highlight our distinction: it shows that our proposed generic framework has user privacy and strong deniability with one-round communication; the generic framework is proven secure in the standard model.

Table 1
A comparative summary for deniable AKE protocols

Function/Algorithm [11] a [17] [9] [40] [41] [31] [35] b Ours

User Privacy c ✓ × × × × × ✓ ✓

Standard Model ✓ × × × × × ✓ ✓

Non-interactive d × × ✓ ✓ × ✓ ✓ ✓

KEA-related e ✓ × × × ✓ × × ×

Implicit Auth N/A f N/A × ✓ × ✓ N/A ✓

†-Deniability g Strong Full Partial h Strong i Strong Strong Strong Strong

Function/Algorithm	[11] a	[17]	[9]	[40]	[41]	[31]	[35] b	Ours
User Privacy c	✓	×	×	×	×	×	✓	✓
Standard Model	✓	×	×	×	×	×	✓	✓
Non-interactive d	×	×	✓	✓	×	✓	✓	✓
KEA-related e	✓	×	×	×	✓	×	×	×
Implicit Auth	N/A f	N/A	×	✓	×	✓	N/A	✓
†-Deniability g	Strong	Full	Partial h	Strong i	Strong	Strong	Strong	Strong

The SKEME protocol in [11].

The Spawn^∗ protocol in [35].

We consider the user privacy with respect to non protocol participants in this work.

We denote one-round communication as non-interactive, and multi-round communications as interactive in this work.

KEA-related assumptions are used for the proof of strong deniability.

N/A denotes (e.g., plaintext awareness) public key cryptosystem is used to construct deniable AKE.

† denotes the level/range of deniability, and a detailed comparison between various deniability models (including full, strong and partial deniability) can be found in Section 2.5.

It denotes the peer-and-time deniability, which is a stronger assumption than the partial deniability offered by SIGMA [11].

ⁱ

It denotes the HP-deniability, which is a stronger assumption than the strong deniability offered by SKEME [11].

1.2. Paper organization

In the next section, we present the formal security models to capture the security requirements (namely, session key security, user privacy and strong deniability) of a secure attribute-based key exchange protocol. We present our generic attribute-based secure key exchange compiler and formally prove its security in Section 3. The paper is concluded in Section 4.

2. Security model

In this section, we present the security models for our proposed generic deniable attribute-based secure key exchanges. As mentioned in the introduction, a secure and deniable generic framework should achieve several security goals: session key security, user privacy and strong deniability. Note that we formalize user privacy and strong deniability separately because deniability and privacy are two different notions. Below we present corresponding security models to capture these requirements.

States. We define a system user set $U$ with n users, i.e. $| U | = n$ . We say an instance oracle $Π_{U}^{i}$ (e.g., session i of user U) may be used or unused, and a user U has unlimited number of instances called oracles. The oracle is considered as unused if it has never been initialized. Each unused oracle $Π_{U}^{i}$ can be initialized with a secret key $sk$ . The oracle is initialized as soon as it becomes part of a group. After the initialization the oracle is marked as used and turns into the stand-by state where it waits for an invocation to execute a protocol operation. Upon receiving such invocation the oracle $Π_{U}^{i}$ learns its partner id ${pid}_{U}^{i}$ and turns into a processing state where it sends, receives and processes messages according to the description of the protocol. During that stage, the internal state information $stat e_{U}^{i}$ is maintained by the oracle. The oracle $Π_{U}^{i}$ remains in the processing state until it collects enough information to compute the session key ${SK}_{U}^{i}$ . As soon as ${SK}_{U}^{i}$ is computed $Π_{U}^{i}$ accepts and terminates the protocol execution meaning that it would not send or receive further messages. If the protocol execution fails then $Π_{U}^{i}$ terminates without having accepted.

Partnering. We denote the ith session of a user U by $Π_{U}^{i}$ , the set of attribute by $δ_{U}$ , and the access structure by $Λ_{U}$ . We provide the definition of access structure in Section 3.1. Let the partner identifier ${pid}_{U}^{i}$ include the identities of participating users (including U) in the ith session of user U with the condition that $\forall U_{j} \in {pid}_{U}^{i}, Λ_{U_{j}} (δ_{U}) = 1$ . Note that $Λ_{U_{j}}$ denotes the access structure specified by one of $n - 1$ users (e.g., $U_{j}$ ), and $Λ_{U_{j}} (δ_{U}) = 1$ means the attributes set $δ_{U}$ satisfies the access structure $Λ_{U_{j}}$ . In other words, ${pid}_{U}^{i}$ is a collection of recognized participants by the instance oracle $Π_{U}^{i}$ . Note that the recognized participants mean that authorized users are communicating with user U at some sessions. We also define ${sid}_{U}^{i}$ as the unique session identifier belonging to user U of session i. Specifically, ${sid}_{U}^{i} = {m_{j}}_{j = 1}^{n}$ , where $m_{j} \in {0, 1}^{*}$ is the message transcript (e.g., nonces) among users in ${pid}_{U}^{i}$ . We say two instance oracles $Π_{U}^{i}$ and $Π_{U^{'}}^{j}$ are partners if and only if ${pid}_{U}^{i} = {pid}_{U^{'}}^{j}$ and ${sid}_{U}^{i} = {sid}_{U^{'}}^{j}$ .

2.1. Definitions

A deniable attribute-based key exchange DABKE framework consists of the following algorithms:

Setup: This algorithm takes the security parameter λ as input, outputs master public/secret key pair $(mpk, msk)$ .

KeyGen: This is an interactive algorithm between a user and central authority (CA). User takes master public key $mpk$ as input, outputs a public/secret key pair ( $pk, sk$ ). While CA takes the master secret key $msk$ , an attributes set δ and public key $pk$ as input, outputs a decryption key $dk$ . Note that we focus on ciphertext-policy setting of attribute-based encryption in this work.

KeyExchange: This is an interactive algorithm among authorized users. Each authorized user takes his/her secret keys $(sk, dk)$ and his/her counterpart’s public keys $pk$ as input, outputs a shared secret key $SK$ .

2.2. Session key security

The security model for session key security is defined via a game between an adversary $A$ and a simulator (i.e., challenger) $S$ . $A$ is an active adversary with full control of communication channels among all authorized users.

Setup: $S$ first generates master public/secret key pair $(mpk, msk)$ for CA and public/secret key pair ${{pk}_{i}, {sk}_{i}}$ for n users by running the corresponding key generation algorithms, where ${sk}_{i}$ denote the secret key of user i. In addition, $S$ honestly generates user’s attributes set ${δ_{i}}$ and corresponding decryption keys ${{dk}_{i}}$ . $S$ also tosses a random coin b which will be used later in the game.

Training: $A$ can make the following queries in arbitrary sequence to $S$ .

send: If $A$ issues send query in the form of ( $U, i, m$ ) to simulate a network message for the ith session of user U, then $S$ would simulate the reaction of instance oracle $Π_{U}^{i}$ upon receiving message m, and returns to $A$ the response that $Π_{U}^{i}$ would generate; If $A$ issues send query in the form of ( $U^{'}$ , ‘ $start$ ’, $Λ_{U}$ ), then $S$ creates a new instance oracle $Π_{U^{'}}^{i}$ and returns $A$ with the first protocol message under the access structure $Λ_{U}$ .

long-term secret key reveal: If $A$ issues a long-term key reveal (or corrupt, for short) query to user i, then $S$ will return the long-term secret keys $({sk}_{i}, {dk}_{i})$ to $A$ .

ephemeral secret key reveal: If $A$ issues an ephemeral secret key reveal query to (possibly unaccepted) instance oracle $Π_{U}^{i}$ , then $S$ will return the ephemeral secret key contained in $Π_{U}^{i}$ at the moment when the query is asked.

master secret key reveal: If $A$ issues a master secret key reveal query to CA, then $S$ will return the master secret key $msk$ to $A$ .

session key reveal: $A$ can issue session key reveal query to an accepted instance oracle $Π_{U}^{i}$ . If the session is accepted (maybe terminated afterwards) successfully, then $S$ will return the session key to $A$ ; Otherwise, a special symbol $‘ ⊥$ ’ is returned to $A$ .

test: This query can only be made to an successfully accepted fresh (as defined below) session i of an user U. If the instance oracle $Π_{U}^{i}$ has generated a session key, then $S$ does the following:

If the coin $b = 1$ , $S$ returns the real session key to $A$ ;

Otherwise, a random session key is drawn from the session key space and returns to $A$ .

It is also worth noting that

A

can continue to issue other queries after the test query. However, the test session must maintain fresh throughout the entire game. Finally,

A

outputs

b^{'}

as its guess for b. If

b^{'} = b

, then

S

outputs 1; Otherwise,

S

outputs 0.

Freshness. We say an accepted instance oracle $Π_{U}^{i}$ with attributes set $δ_{U}$ and access structure $Λ_{U}$ is fresh if $A$ does not perform any of the following actions during the game:

$A$ issues session key reveal query to $Π_{U}^{i}$ or its accepted partnered instance oracles $Π_{U^{'}}^{j}$ (if the latter exists);

$A$ issues both long-term secret key reveal query to user $U^{'}$ s.t. $U^{'} \in {pid}_{U}^{i}$ and ephemeral secret key reveal query for some instances $Π_{U^{'}}^{j}$ partnered with $Π_{U}^{i}$ .

$A$ issues long-term secret key reveal query to user $U^{'}$ s.t. $U^{'} \in {pid}_{U}^{i}$ prior to the acceptance of instance $Π_{U}^{i}$ and there exist no instance oracles $Π_{U^{'}}^{j}$ partnered with $Π_{U}^{i}$ .

Note that master secret key reveal query to CA is equivalent to the long-term secret key reveal to all users.

We define the advantage of an adversary $A$ in the above game as $\begin{matrix} (1) & {Adv}_{A} (λ) = | Pr [S \to 1] - 1 / 2 | . \end{matrix}$

Definition 2.1.
We say a DABKE protocol has session key security if for any probabilistic polynomial-time (PPT) $A$ , ${Adv}_{A} (λ)$ is a negligible function of the security parameter λ.

2.3. User privacy

Informally, an adversary (not authorized users) attempts to identify the authorized users involved in a DABKE protocol. We then define the formal user privacy game between an adversary $A$ and a simulator $S$ as follows. Let $A$ chooses a challenge access structure $Λ^{*}$ before the game.

Setup: $S$ first generates master public/secret key pair $(mpk, msk)$ for the CA and public/secret key pair ${{pk}_{i}, {sk}_{i}}$ for n users by running the corresponding key generation algorithms, where ${sk}_{i}$ denote the long-term secret key of user i. In addition, $S$ honestly generates user’s attribute sets ${δ_{i}}$ and corresponding decryption keys ${{dk}_{i}}$ . $S$ also tosses a random coin b which will be used later in the game.

Training: $A$ is allowed to issue execute, ephemeral secret key reveal, long-term secret key reveal and session key reveal queries to $S$ . Let $U^{'}$ denote the users whose attributes set satisfies $Λ^{*} (δ) = 1$ , and $A$ is not allowed to issue long-term secret key reveal query to users in $U^{'}$ .

Note that the execute query [2] can be used by (passive) $A$ to invoke an honest execution of the protocol and obtain a transcript of exchanged messages.

Challenge: $A$ randomly selects $two$ users $U_{i}, U_{j} \in U^{'}$ as the challenge candidates. $A$ then sends the challenge candidates to $S$ . $S$ simulates $U_{b}^{*}$ by either $U_{b}^{*} = U_{i}$ if $b = 1$ or $U_{b}^{*} = U_{j}$ if $b = 0$ , and generates the protocol transcript using the access structure $Λ^{*}$ .

Let the rest users ${U_{r}}$ in $U^{'}$ interact with the challenge user $U_{b}^{*}$ , and $A$ can access all the communication transcripts among them. $\begin{matrix} {U_{r}}_{r \neq i, j} \leftrightarrow U_{b}^{*} = \{\begin{matrix} U_{i} & b = 1 \\ U_{j} & b = 0 \end{matrix} \end{matrix}$

Guess: $A$ outputs $b^{'}$ as its guess for b. If $b^{'} = b$ , then $S$ outputs 1; Otherwise, $S$ outputs 0.

We define the advantage of $A$ in the above game as $\begin{matrix} {Adv}_{A} (λ) = | Pr [S \to 1] - 1 / 2 | . \end{matrix}$

Definition 2.2.
We say a DABKE protocol has user privacy if for any PPT $A$ , ${Adv}_{A} (λ)$ is a negligible function of the security parameter λ.

2.4. Strong deniability

Informally, an adversary aims to present a “proof” to a third party (judge), claim that any authorized users were participated in some sessions. We formally define the strong deniability model for DABKE protocols as follows.

Definition 2.3.
Let Σ be an attribute-based key exchange protocol defined by a key generation algorithm KeyGen and interactive machines $Σ_{I}, Σ_{R}$ specifying the role of the initiator and responder respectively. We say that $(KeyGen, Σ_{I}, Σ_{R})$ is a concurrently deniable attribute-based key exchange protocol w.r.t the class Aux of auxiliary inputs, if for any PPT $A$ which runs on input decryption keys $dk = ({dk}_{1}, \dots, {dk}_{n})$ , public keys $pk = ({pk}_{1}, \dots, {pk}_{n})$ and any auxiliary input $aux \in Aux$ , there exists a simulator $S$ that, running on the same inputs (including random coins) as $A$ , produces a simulated view which is statistically indistinguishable from the real view of $A$ , where Aux models extra information that $A$ may have obtained in other form such as some legal transcripts eavesdropped by $A$ from the correctly executed protocols. That is, considering the following two probability distributions where $pk = ({pk}_{1}, \dots, {pk}_{n})$ is the set of public keys of honest users whose secrets keys are not compromised: $\begin{array}{l} Real (λ, aux) = [({dk}_{i}, {sk}_{i}, {pk}_{i}) \leftarrow KeyGen (λ); (aux, dk, pk, View (aux, dk, pk))] \\ Sim (λ, aux) = [({dk}_{i}, {sk}_{i}, {pk}_{i}) \leftarrow KeyGen (λ); (aux, dk, pk, S (aux, dk, pk))] \end{array}$ then for all PPT distinguishers Dist and all $aux \in Aux$ , we have $\begin{matrix} (2) & | {Pr}_{x \in Real (λ, aux)} [Dist (x)] = 1 - {Pr}_{x \in Sim (λ, aux)} [Dist (x)] = 1 | ⩽ ϵ (λ), \end{matrix}$ where ϵ is a negligible function of the security parameter λ. In particular, the actions of off-line distinguisher Dist are described as follows:
The Dist is given the full protocol transcripts and accepted session keys in which $A$ participated.

The Dist is allowed to obtain the secret keys of all participants.

Remark.
As for the strong sense of deniability, $A$ acts as one of protocol participants. The $View (aux, dk, pk)$ means that $A$ (maliciously) performs the Σ protocol runs with other honest users in a real view. While $S (aux, dk, pk)$ means that a simulator $S$ , who is running on the same inputs as $A$ (including $A$ ’s secret key and randomness), simulates an indistinguishable view from a real view to judge.

2.5. Relationship with various deniability models

We evaluate the relationship between the commonly used deniability models and our proposed strong deniability model, and we remove attribute-based context for fair comparison.

Relation to Partial Deniability. The digital signature based key exchange protocol (e.g., SIGMA in [11]) is partially deniable if the runs of the honest initiator with a responder are indistinguishable from runs with another responder. In other words, initiator’s transcripts are “peer-independent”. The formal partial deniability model is referred to [11], and we do not consider partial deniability and peer-and-time deniability [9] in this work.

Relation to “Full” Deniability. Some works [9,17,32] have used the term “full” deniability to describe strong deniability in [11]. The subtle difference between “full” and strong deniability is the actual role of simulator/adversary. More precisely, in the simulation view of a two-party key exchange setting, the simulator is outside the protocol participants for “full” deniability, while the simulator is one of protocol participants for strong deniability. We consider strong deniability [11] in this work.

Relation to On/Off-line Deniability. On-line deniability means that a protocol participant colludes with the judge during protocol execution. The on-line deniability is a stronger assumption than off-line deniability [12,35]. Specifically, the judge is allowed to interact with the adversary before or during the protocol execution. Since some impossibility results (e.g., in the symmetric-key setting) observed by Dodis et al. [12] for authentication or key exchange protocols, we consider off-line judge only in this work.

A Complete Comparison. We present a complete comparison between few well-known deniability models for authentication/key exchange protocols and our proposed deniability model (see Table 2), according to the role of adversary/simulator. We assume an initiator and a responder are running an AKE protocol, and the †-deniability is corresponding to the last function in Table 1.

Table 2
Simulated view with respect to †-deniability

Algorithm/Role Simulator Adversary

SIGMA [11]: Partial Initiator (resp., Responder) Responder (resp., Initiator)

TOPAS [31]: Strong Initiator (resp., Responder) Initiator (resp., Responder)

DIKE [41]: “Full” Neither of Them Neither of Them

Ours: Strong Initiator (resp., Responder) Initiator (resp., Responder)

Algorithm/Role	Simulator	Adversary
SIGMA [11]: Partial	Initiator (resp., Responder)	Responder (resp., Initiator)
TOPAS [31]: Strong	Initiator (resp., Responder)	Initiator (resp., Responder)
DIKE [41]: “Full”	Neither of Them	Neither of Them
Ours: Strong	Initiator (resp., Responder)	Initiator (resp., Responder)

In addition, we formalize an off-line judge [35] in our proposed deniability model, such that the judge is allowed to obtain the secret keys of protocol participants after the protocol execution. Note that our proposed deniability model has forward deniability as specified in [10].

3. Our construction

In this section, we firstly review the building blocks that will be used in the proposed generic attribute-based key exchange compiler, we then present our proposed generic compiler and its security analysis.

3.1. Building blocks

Access Structure. Let ${P_{1}, \dots, P_{n}}$ be a set of parties. A collection $Λ \subseteq 2^{{P_{1}, \dots, P_{n}}}$ is monotone if $\forall B, C$ : if $B \in Λ$ and $B \subseteq C$ then $C \in Λ$ . An access structure (i.e., monotone access structure) is a collection of non-empty subsets of ${P_{1}, \dots, P_{n}}$ (i.e., $Λ \subseteq 2^{{P_{1}, \dots, P_{n}}} ∖ {ϕ}$ ). The sets in Λ are called the authorized sets, and the sets not in Λ are called the unauthorized sets.

Access Tree Λ. Let Λ be a tree representing an access structure. Each non-leaf node of the tree represents a threshold gate, described by its children and a threshold value. If ${num}_{i}$ is the number of children of a node x and $k_{x}$ is its threshold value, then $1 ⩽ k_{x} ⩽ {num}_{x}$ . If $k_{x} = 1$ , it is an OR gate; If $k_{x} = {num}_{x}$ , it is an AND gate. Each leaf node x of the tree is described by an attribute and a threshold value $k_{x} = 1$ . We define the parent of the node x in the tree by $parent (x)$ , the attribute associate with the leaf node x in the tree by $att (x)$ , the ordering between the children of every node x in the tree by $index (x)$ (numbered from 1 to $num$ ).

Satisfying an Access Tree. Let Λ be an access tree with root R. The $Λ_{x}$ denote the subtree of Λ rooted at the node x (e.g., $Λ = Λ_{R}$ ). If a set of attributes δ satisfies the access tree $Λ_{x}$ , we denote it as $Λ_{x} (δ) = 1$ . We compute $Λ_{x} (δ)$ as follows: If x is a leaf node, then $Λ_{x} (δ)$ returns 1 iff $att (x) \in δ$ ; If x is a non-leaf node, evaluate $Λ_{x^{'}} (δ)$ for all children $x^{'}$ of node x. $Λ_{x} (δ)$ returns 1 iff at least $k_{x}$ children return 1.

Ciphertext-Policy Attribute-Based Encryption Scheme: It consists of four algorithms [39]: CP-ABE = (Setup, KeyGen, Enc, Dec).

Setup: The algorithm takes the security parameter λ as input, outputs master public parameters $mpk$ and master secret key $msk$ .

KeyGen: The algorithm takes the master secret key $msk$ and an attributes set δ as input, outputs a decryption key $dk$ .

Enc: The probablistic algorithm takes the master public parameters $mpk$ , a message m and an access structure Λ as input, outputs a ciphertext $CT$ . The $CT$ implicitly contains Λ.

Dec: The deterministic algorithm takes the master public parameters $mpk$ , a ciphertext $CT$ and the decryption key $dk$ as input, outputs the message m if and only if the attributes set δ satisfies the access structure Λ.

Two-Pass Authenticated Key Exchange (TP-AKE) Protocol: It consists of two algorithms: TP-AKE = (KeyGen, KeyExchange).

KeyGen: Each user i outputs a long-term secret/public key pair $({sk}_{i}, {pk}_{i})$ .

KeyExchange (KE): This is an interactive algorithm among willing users. It actually consists of the following sub-algorithms.

KE.Ephemeral: User i outputs an ephemeral secret/public key pair $({ek}_{i}, {epk}_{i})$ ; Note that ephemeral secret/public key pair may have NAXOS technique for achieving eCK security, and the detailed technical explanations are referred to [22].

KE.EX: Users exchange their ephemeral public keys, i.e., ${epk}_{i}, {epk}_{j}$ ; Note that users also exchange their long-term public keys at post-specified peer setting.

KE.KDF: User i executes a key derivation function and obtains $K = KDF : ({sk}_{i}, {ek}_{i}, {pk}_{j}, {epk}_{j})$ ( $j \neq i$ ). Note that we consider TP-AKE protocol in a two-party setting for simplicity. More generally, we can define $K = KDF : ({sk}_{i}, {ek}_{i}, {{pk}_{j}, {epk}_{j}})$ ( $j \neq i$ ) in a multi-party setting.

Implicit Authentication. Implicit authentication is mainly used to prevent man-in-the-middle attacks for TP-AKE protocols. Specifically, we analyze the common features of TP-AKE protocols as follows: 1) The participants exchange ephemeral public keys only; 2) The key derivation function is composed of his/her own ephemeral/secret keys $(ek, sk)$ , and the peer’s ephemeral/long-term public keys $(epk, pk)$ ; 3) The exchanged ephemeral public keys are uniformly distributed in the key space.

Relation to Strong Deniability. Two-pass authenticated key exchange protocols with implicit authentication ensure strong deniability [11], such that one of protocol participants is able to deny his/her session participations. Specifically, one of session participants can randomly chooses the session transcripts (i.e., the uniformly distributed ephemeral public keys), and honestly generate the shared key K under the symmetric-key setting. Furthermore, we discover that many existing TP-AKE protocols (e.g., [21–23,25,26,31,34,37,40] and enormous HMQV variants) can achieve strong deniability (Definition 2 in [11]), we then have the following Lemma.

Lemma 3.1.
TP-AKE protocols with implicit authentication have the strong deniability defined in [ 11 ].
Proof.
We assume a two-pass key exchange protocol is executed between Alice and Bob where Alice sends ephemeral public key ${epk}_{A}$ to Bob, and vice versa for Bob. We assume that both Alice and Bob aim to establish a shared key K in a real view. Note that two simulated values will be presented to judge: the exchanged ephemeral public keys and the resulting shared key. Also note that adversary is one of protocol participants.

The exchanged ephemeral public key pair $({epk}_{A}, {epk}_{B})$ derives from either the secret key pair $({ek}_{A}, {ek}_{B})$ or the function $f ({ek}_{A}, {sk}_{A}), f ({ek}_{B}, {sk}_{B})$ (f denotes a randomized algorithm, such as hash function or pseudorandom function). Simulator $S$ (i.e., adversary Bob) is simply choosing a random value ${epk}_{A}$ from ephemeral public space to simulate transmitted ephemeral public key on behalf of Alice, while the judge cannot statistically distinguish it since the real/simulated value is uniformly distributed in either the ephemeral public key space or the output of function f (except collisions with a negligible probability). Note that the judge is not allowed to obtain either ephemeral or long-term secret keys of protocol participants (refer to Definition 2 in [11]).

The resulting shared key K can be easily simulated by $S$ . Specifically, $S$ (i.e., adversary Bob) randomly chooses ephemeral public key ${epk}_{B}$ and computes $K = TP - AKE . KE . KDF : ({pk}_{A}, {epk}_{A}, {sk}_{B}, {ek}_{B})$ , where secret keys $({sk}_{B}, {ek}_{B})$ are known to $S$ . □

Pseudo-Random Function (PRF). A function family $\tilde{F}$ is associated with ${{Seed}_{λ}}_{λ \in N}$ , ${{Dom}_{λ}}_{λ \in N}$ , ${{Rng}_{λ}}_{λ \in N}$ , where $N$ is the set of natural numbers. Formally, for any randomly chosen $K \overset{R}{\leftarrow} {Seed}_{λ}$ , $σ \overset{U}{\leftarrow} K$ , $D \overset{R}{\leftarrow} {Dom}_{λ}$ , $R \overset{R}{\leftarrow} {Rng}_{λ}$ , $F_{σ}^{λ, K, D, R}$ define a function which map an element of $D$ to an element of $R$ . That is, $F_{σ}^{λ, K, D, R} (ρ) \in R$ for any $ρ \in D$ . Definition 3.1 (PRF [26]).

We say that $\tilde{F}$ is a pseudo-random function (PRF) family if $\begin{matrix} (3) & {{\tilde{F}}_{σ}^{λ, K, D, R} (ρ_{i})} \approx {RF (ρ_{i})} \end{matrix}$ for any $ρ_{i} \in D$ adaptively chosen by any polynomial time distinguisher, where RF is a truly random function. That is, for any $ρ \in D$ , $RF (ρ) \overset{U}{\leftarrow} R$ .

3.2. Generic compiler

High-level Description. Two authorized users aim to establish a secure session key using their attributes and public keys, meanwhile a subsequent deniable communication is provided among authorized users. A generic compiler (GC) is used for adding strong deniability and impersonation-resistance to attribute-based key exchanges, and the proposed generic compiler consists of the following building blocks.

An eCK secure TP-AKE protocol $TP - AKE = (KeyGen, KeyExchange)$ .

An ABE scheme $ABE = (Setup, KeyGen, Enc, Dec)$ .

A PRF $\tilde{F}$ .

For simplicity, we use initiator $U_{i}$ and responder $U_{j}$ to illustrate our generic compiler (see Figure 1).

Fig. 1.

Generic compiler. $sid = ({epk}_{i} | | {epk}_{j})$ .

Setup: CA takes the security parameter λ as input, outputs master public/secret key pair $(mpk, msk)$ . Let $\tilde{F} : K \times D \to {0, 1}^{l (λ)}$ (l is polynomial in the security parameter λ, and $l (λ) \in R$ ) be a PRF.

KeyGen: CA runs the ABE.KeyGen algorithm to obtain decryption key ${dk}_{i}$ of user i. In addition, user i runs the TP-AKE.KeyGen algorithm to obtain his own long-term secret/public key pair $({sk}_{i}, {pk}_{i})$ .

KeyExchange: User i (i.e., initiator) performs the following steps.

Run the TP-AKE.KE.Ephemeral algorithm to obtain ephemeral secret/public key pair $({ek}_{i}, {epk}_{i})$ ;

Generate a ciphertext ${CT}_{i} = ABE . Enc ({pk}_{i} | | {epk}_{i})$ and send it to user j. Note that at CP-ABE case, ABE.Enc takes master public key $mpk$ , a message $m_{i} = ({pk}_{i} | | {epk}_{i})$ (where ${epk}_{i}$ is also used for key exchange $KE$ of TP-AKE) and an access structure $Λ_{i}$ as input, outputs a ciphertext ${CT}_{i}$ which implicitly contains $Λ_{i}$ .

Then user j (i.e., responder) performs the following steps.

Obtain $({pk}_{i} | | {epk}_{i})$ after running $ABE . Dec$ algorithm on ${CT}_{i}$ ; Note that (CP-) ABE.Dec takes master public key $mpk$ , a ciphertext ${CT}_{i}$ and the decryption key ${dk}_{j}$ as input, outputs the message $m_{i}$ iff the attributes set $δ_{j}$ satisfies the access structure $Λ_{i}$ .

Run the TP-AKE.KE.Ephemeral algorithm to obtain ephemeral secret/public key pair $({ek}_{j}, {epk}_{j})$ ;

Generate a ciphertext ${CT}_{j} = ABE . Enc ({pk}_{j} | | {epk}_{j})$ and send ${CT}_{j}$ to user i;

Compute the final session key ${SK}_{j} = {\tilde{F}}_{T_{j}} (sid)$ , where $T_{j} = TP - AKE . KE . KDF ({ek}_{j}, {sk}_{j}, {epk}_{i}, {pk}_{i}), sid = ({epk}_{i} | | {epk}_{j})$ .

User i performs the following steps.

Obtain $({pk}_{j} | | {epk}_{j})$ after running $ABE . Dec$ algorithm on ${CT}_{j}$ ;

Compute the final session key ${SK}_{i} = {\tilde{F}}_{T_{i}} (sid)$ , where $T_{i} = TP - AKE . KE . KDF ({ek}_{i}, {sk}_{i}, {epk}_{j}, {pk}_{j}), sid = ({epk}_{i} | | {epk}_{j})$ . Note that the equation $T_{i} = T_{j}$ holds due to the correctness of TP-AKE protocol.

Remark.

One may argue that the proposed GC is transforming from a TP-AKE protocol to an attribute-based one. Essentially, we aim to prevent impersonation attacks and provide strong deniability for AB-AKE protocols. To achieve these goals, the proposed GC can be construted from either AB-AKE protocol with implicit authentication or TP-AKE protocol with ABE scheme, which in turn provides more flexibility in the sense of generic construction.

3.3. Security analysis

Theorem 3.2.
The proposed GC achieves session key security (Definition 2.2 ) if the TP-AKE is session key secure and $\tilde{F}$ is a pseudo-random family.
Proof.
We define a sequence of games $G_{i}$ , $i = 0, \dots, 4$ and let ${Adv}_{i}^{GC}$ denote the advantage of the adversary in game $G_{i}$ . Assume that $A$ activates at most m sessions in each game.
$G_{0}$ This is original game for session key security.

$G_{1}$ This game is identical to game $G_{0}$ except that $S$ will output a random bit if user i (initiator) and user j (responder) accept, but ${pid}_{i} \neq {pid}_{j}, {sid}_{i} \neq {sid}_{j}$ . Since n users involved in this game, we have: $\begin{matrix} (4) & | {Adv}_{0}^{GC} - {Adv}_{1}^{GC} | ⩽ n \cdot m^{2} / 2^{λ} \end{matrix}$

$G_{2}$ : This game is identical to game $G_{1}$ except the following difference: $S$ randomly chooses g $\in [1, m]$ as a guess for the index of the test session. $S$ will output a random bit if $A$ ’s test query does not occur in the gth session. Therefore we have $\begin{matrix} (5) & {Adv}_{1}^{GC} = m \cdot {Adv}_{2}^{GC} \end{matrix}$

$G_{3}$ This game is identical to game $G_{2}$ except that in the gth session, $S$ replaces the real TP-AKE session key by a random value $R \in K$ . Below we show the difference between $G_{2}$ and $G_{3}$ is negligible under the assumption that TP-AKE is eCK secure. Note that we choose eCK security of TP-AKE in this game, which is used to match our proposed session key security defined in Section 2.2.

Let $S$ denotes an attacker against the TP-AKE protocol, who is given corresponding oracles in the sense of eCK security model, and aims to distinguish a real session key from a random value. $S$ simulates the game for $A$ as follows.

Setup: $S$ sets up the game for $A$ by creating n users with the corresponding attributes/identity set ${δ_{i}, I D_{i}}$ . $S$ honestly generates master public/secret key pair $(mpk, msk)$ for CA. In addition, $S$ generates user’s decryption keys ${{dk}_{i}}$ by running $ABE . KeyGen$ algorithm and public/secret key pairs ${({pk}_{i}, {sk}_{i})}$ from his oracle queries (i.e., long-term secret key query). Eventually, $S$ sends all attribute sets, identities and public keys to $A$ .

$S$ answers $A$ ’s queries as follows.
If $A$ issues send query in the form of ${CT}_{j} = Enc ({pk}_{j} | | {epk}_{j})$ to user i, then $S$ will perform the simulation as follows.
Obtain messages ${pk}_{j}, {epk}_{j}$ using decryption key of user i;

Forward ${epk}_{j}$ to his challenger and obtain ${epk}_{i}$ from his send oracle;

Return ${CT}_{i} = Enc ({pk}_{i} | | {epk}_{i})$ as the response to $A$ ;

Compute the final session key ${SK}_{i} = {\tilde{F}}_{T_{i}} (sid)$ , where $T_{i}$ is obtained from either session key reveal oracle or test oracle w.r.t. gth session, and $sid = ({pk}_{i} | | {pk}_{j} | | {epk}_{i} | | {epk}_{j})$ .
Note that if $A$ issues send query in the form of ( $U^{'},^{'} {start}^{'}, Λ_{U^{'}}$ ), then $S$ returns ${CT}^{'} = Enc ({pk}_{U^{'}} | | {epk}^{'})$ ( ${epk}^{'}$ is randomly chosen by $S$ ) to $A$ .

If $A$ issues an ephemeral key reveal query to $S$ , then $S$ makes an ephemeral key reveal query to its own oracle to get ${ek}_{i}$ and returns it to $A$ .

If $A$ issues a long-term key reveal query to user i, then $S$ returns $({dk}_{i}, {sk}_{i})$ to $A$ .

If $A$ issues a master secret key reveal query to $S$ , then $S$ returns $msk$ to $A$ .

$S$ answers the session key reveal query and test query by using the session key ${SK}_{i}$ it has derived during the protocol simulation described above.
Note that in the test session $S$ will get either a real session key or a random key from his own test oracle. If it is the real session key, then the simulation is consistent with $G_{2}$ ; Otherwise, the simulation is consistent with $G_{3}$ . Therefore, if the advantage of $A$ is significantly different in $G_{2}$ and $G_{3}$ , $S$ can break the TP-AKE protocol. Hence, we have $\begin{matrix} (6) & | {Adv}_{2}^{GC} - {Adv}_{3}^{GC} | ⩽ {Adv}_{S}^{TP - AKE} (λ) \end{matrix}$

$G_{4}$ : This game is identical to game $G_{3}$ except that in the test session, we replace the PRF function ${\tilde{F}}_{T_{i}} (sid)$ by a random function. We next to showing the difference between $G_{3}$ and $G_{4}$ is negligible if $\tilde{F}$ is PRF family.

Let $S$ denotes an attacker against the PRF, who is given an oracle either ${\tilde{F}}_{σ}$ ( $σ \overset{U}{\leftarrow} K$ ) or a random function RF, aims to distinguish them. $S$ simulates the game for $A$ as the exact same way as $G_{3}$ except the computation of final session key ${SK}_{i} = {\tilde{F}}_{T_{i}^{}} ({sid}^{})$ . Specifically, $S$ forwards ${sid}^{}$ to his challenger and sets the value returned from the oracle as ${SK}_{i}$ . Finally, $S$ outputs whatever $A$ outputs.

Note that in the test session, if the oracle is ${\tilde{F}}_{σ}$ (note that the returned value ${\tilde{F}}_{σ} ({sid}^{})$ from the oracle is indistinguishable from ${\tilde{F}}_{T_{i}^{}} ({sid}^{})$ because the value $T_{i}^{} \overset{U}{\leftarrow} K$ in $G_{3}$ is uniform and independent), then the simulation is consistent with $G_{3}$ ; Otherwise, the simulation is consistent with $G_{4}$ . Therefore, if the advantage of $A$ is significantly different in $G_{3}$ and $G_{4}$ , $S$ can break the PRF family. Hence, we have $\begin{matrix} (7) & | {Adv}_{3}^{GC} - {Adv}_{4}^{GC} | ⩽ {Adv}_{S}^{PRF} (λ) \end{matrix}$

It is easy to see that in game $G_{4}$ , $A$ has no advantage, i.e., $\begin{matrix} (8) & {Adv}_{4}^{GC} = 0 \end{matrix}$

Combining the above results together, we have $\begin{array}{l} {Adv}_{A}^{GC} (λ) = n \cdot m^{2} / 2^{λ} + m \cdot ({Adv}_{S}^{TP - AKE} (λ) + {Adv}_{S}^{PRF} (λ)) . \end{array}$ □
Remark.
The impersonation attacks can be prevented in an implicit manner. If adversary can perform the impersonation attacks with a non-negligible probability, then we can use it to built an efficient attacker to break the session key security of TP-AKE protocol.
Theorem 3.3.
The proposed GC achieves user privacy (Definition* 2.3 ) if the ABE scheme is selective IND-CPA secure.
Proof.
Let $S$ denote an attacker who is given the $KeyGen$ oracle and challenge access structure $Λ^{}$ (CP-ABE case), aims to break the selective IND-CPA (sIND-CPA) security of ABE scheme. $S$ simulates the game for $A$ as follows.
Setup: $S$ sets up the game for $A$ by creating n users with the corresponding attributes/identity set ${δ_{i}, I D_{i}}$ . Then $S$ honestly generates user’s public/secret key pairs ${({pk}_{i}, {sk}_{i})}$ . Eventually, $S$ sends all attribute sets, identities and public keys to $A$ .

Training: $S$ answers $A$ ’s queries as follows.

If $A$ issues an execute query between user i and user j ( $Λ^{} (δ_{i}) = 1$ and $Λ^{} (δ_{j}) = 1$ ), then $S$ randomly chooses ephemeral secret keys $({ek}_{i}, {ek}_{j})$ , and performs the session execution and session key derivation honestly according to the protocol specification.

$S$ answers ephemeral secret key reveal and session key reveal queries using the secret values it has derived during the protocol simulation described above. In addition, $S$ can honestly answer long-term secret key reveal queries to users $Λ^{} (δ_{w}) \neq 1$ ( $w \neq i, j$ ) using his $KeyGen$ oracle.

Challenge: After receiving user i and user j ( $Λ^{} (δ_{i}) = 1$ and $Λ^{} (δ_{j}) = 1$ ) from $A$ , $S$ firstly follows the user privacy game to select $U_{b}^{}$ and construct message $m_{0} = ({pk}_{b} | | {epk}_{b})$ . Secondly, $S$ randomly chooses another user l ( $Λ^{} (δ_{l}) = 1$ ), and generates another message $m_{1} = ({pk}_{l} | | {epk}_{l})$ . Thirdly, $S$ sends challenge messages $(m_{0}, m_{1})$ to his challenger oracle, and obtains challenge ciphertext $C^{}$ as the transcript of $U_{b}^{}$ . Note that ${epk}_{b}, {epk}_{l}$ are randomly chosen by $S$ , and a randomly chosen value R acts as the transcript of user l.

Finally, $S$ outputs whatever $A$ outputs. If $A$ guesses the random bit correctly, then $S$ can break the selective IND-CPA security of ABE. Hence, we have $\begin{array}{l} {Adv}_{A}^{GC} (λ) ⩽ {Adv}_{S}^{sIND - CPA} (λ) . \end{array}$ □
Theorem 3.4.
The proposed GC achieves strong deniability defined in Definition 2.4 .
Proof.
We assume the GC is executed between Alice and Bob where Alice sends ${CT}_{A}$ to Bob, and vice versa for Bob. We assume that both Alice and Bob aim to establish a shared session key $SK$ in a real view. Note that two simulated values will be presented to a judge: the exchanged ciphertexts and the resulting session key. Also note that adversary is one of protocol participants who can decrypt the ciphertext from its counterpart.

Simulator $S$ (i.e., adversary Bob) simulates Alice’s transcript as follows: $S$ randomly chooses ephemeral public key ${epk}_{A}$ as described in Lemma 3.1, and generates ciphertext as ${CT}_{A} \leftarrow ABE . Enc ({pk}_{A} | | {epk}_{A})$ . As for Bob’s transcript and resulting session key, $S$ can generate ciphertext ${CT}_{B}$ and session key ${SK}_{B}$ by following the GC execution honestly. Specifically, the ciphertext is ${CT}_{B} \leftarrow Enc ({pk}_{B} | | {epk}_{B})$ and the resulting session key is ${SK}_{B} = {\tilde{F}}_{T_{B}} (sid)$ , where $T_{B} = TP - AKE . KE . KDF ({ek}_{B}, {sk}_{B}, {epk}_{A}, {pk}_{A}), sid = ({pk}_{A} | | {pk}_{B} | | {epk}_{A} | | {epk}_{B})$ , and $({ek}_{B}, {epk}_{B}) \leftarrow TP - AKE . KE . Ephemeral$ . Note that the secret keys $({sk}_{B}, {ek}_{B})$ are known to $S$ .

We stress that an off-line judge is allowed to obtain long-term secret keys $({sk}_{A}, {sk}_{B})$ rather than ephemeral secret keys, the transcripts simulated by $S$ are statistically indistinguishable from a real view because the randomly chosen value (e.g., ${epk}_{A}$ ) in simulated transcript is uniformly distributed as in a real view. Since $S$ can simulate the transcripts and resulting session key in the exact same way as a real protocol execution between Alice and Bob, the simulation by $S$ is perfect to a judge. □
4. Conclusion

In this paper, we proposed a deniable attribute-based secure key exchange framework based on the attribute-based encryption schemes and implicitly authenticated key exchange protocols. We defined the formal security models to capture the security requirements, including session key security, user privacy and strong deniability. We leave the construction of attribute-based secure key exchange with on-line deniability in the standard model as our future work.

Footnotes

Acknowledgments

The work is supported by the Singapore National Research Foundation under NCR Award Number NRF2014NCR-NCR001-012.

References

Bellare,

Canetti and

Krawczyk, A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract), in: STOC, 1998, pp. 419–428.

Bellare,

Pointcheval and

Rogaway, Authenticated key exchange secure against dictionary attacks, in: EUROCRYPT, 2000, pp. 139–155.

Bellare and

Rogaway, Entity authentication and key distribution, in: CRYPTO, 1993, pp. 232–249.

Bellare and

Rogaway, Provably secure session key distribution: The three party case, in: STOC, 1995, pp. 57–66.

Bethencourt,

Sahai and

Waters, Ciphertext-policy attribute-based encryption, in: 2007 IEEE Symposium on Security and Privacy (S&P), 2007, pp. 321–334. doi:10.1109/SP.2007.11.

Borisov,

Goldberg and

Brewer, Off-the-record communication, or, why not to use PGP, in: Proceedings of the 2004 ACM Workshop on Privacy in the Electronic Society, 2004, pp. 77–84.

Burmester and

Desmedt, Efficient and secure conference-key distribution, in: Security Protocols, International Workshop, Proceedings, Cambridge, United Kingdom, April 10–12, 1996, 1996, pp. 119–129.

Canetti and

Krawczyk, Analysis of key-exchange protocols and their use for building secure channels, in: EUROCRYPT, 2001, pp. 453–474.

C.J.F.

Cremers and

Feltz, One-round strongly secure key exchange with perfect forward secrecy and deniability, IACR Cryptology ePrint Archive 2011 (2011), 300.

10.

Di Raimondo and

Gennaro, New approaches for deniable authentication, in: ACM, CCS, 2005, pp. 112–121.

11.

Di Raimondo,

Gennaro and

Krawczyk, Deniable authentication and key exchange, in: ACM, CCS, 2006, pp. 400–409.

12.

Dodis,

Katz,

A.D.

Smith and

Walfish, Composability and on-line deniability of authentication, in: TCC, 2009, pp. 146–162.

13.

Dwork,

Naor and

Sahai, Concurrent zero-knowledge, Journal of the ACM (JACM) 51(6) (2004), 851–898. doi:10.1145/1039488.1039489.

14.

S.D.

Galbraith, Authenticated key exchange for SIDH, 2018.

15.

M.C.

Gorantla,

Boyd and

J.M.G.

Nieto, Attribute-based authenticated key exchange, in: ACISP, 2010, pp. 300–317.

16.

Goyal,

Pandey,

Sahai and

Waters, Attribute-based encryption for fine-grained access control of encrypted data, in: ACM, CCS, 2006, pp. 89–98.

17.

Jiang and

Safavi-Naini, An efficient deniable key exchange protocol, Financial Cryptography and Data Security (2008), 47–52. doi:10.1007/978-3-540-85230-8_4.

18.

Katz and

J.S.

Shin, Modeling insider attacks on group key-exchange protocols, in: ACM, CCS, 2005, pp. 180–189.

19.

Katz and

Yung, Scalable protocols for authenticated group key exchange, in: CRYPTO, 2003, pp. 110–125.

20.

Kolesnikov,

Krawczyk,

Lindell,

Malozemoff and

Rabin, Attribute-based key exchange with general policies, in: ACM, CCS, 2016, pp. 1451–1463.

21.

Krawczyk, HMQV: A high-performance secure Diffie-Hellman protocol, in: CRYPTO, 2005, pp. 546–566.

22.

B.A.

LaMacchia,

K.E.

Lauter and

Mityagin, Stronger security of authenticated key exchange, in: Provable Security, 2007, pp. 1–16.

23.

Law,

Menezes,

Qu,

Solinas and

Vanstone, An efficient protocol for authenticated key agreement, Designs, Codes and Cryptography 28(2) (2003), 119–134. doi:10.1023/A:1022595222606.

24.

A.B.

Lewko,

Okamoto,

Sahai,

Takashima and

Waters, Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption, in: EUROCRYPT, 2010, pp. 62–91.

25.

Menezes, Another look at HMQV, Mathematical Cryptology JMC 1(1) (2007), 47–64.

26.

Okamoto, Authenticated key exchange and key encapsulation in the standard model, ASIACRYPT (2007), 474–484.

27.

Okamoto and

Takashima, Fully secure functional encryption with general relations from the decisional linear assumption, in: CRYPTO, 2010, pp. 191–208.

28.

Open Whisper Systems.

29.

Pass, On deniability in the common reference string and random oracle model, in: Crypto, Vol. 3, 2003, pp. 316–337.

30.

Sahai and

Waters, Fuzzy identity-based encryption, in: Advances in Cryptology – EUROCRYPT, 2005, pp. 457–473.

31.

Schäge, TOPAS: 2-pass key exchange with full perfect forward secrecy and optimal communication complexity, in: ACM, CCS, 2015, pp. 1224–1235.

32.

Tian,

Li,

Zhang,

Li,

Yang and

Yu, DSH: Deniable secret handshake framework, in: ISPEC, 2018, pp. 341–353.

33.

Tian,

Yang,

Mu,

Liang and

Yu, One-round attribute-based key exchange in the multi-party setting, in: Provable Security, 2016, pp. 227–243.

34.

Tian,

Zhang,

Yang,

Mu and

Yu, Privacy-preserving k-time authenticated secret handshakes, in: ACISP, 2017, pp. 281–300.

35.

Unger and

Goldberg, Deniable key exchanges for secure messaging, in: ACM, CCS, 2015, pp. 1211–1223.

36.

Unger and

Goldberg, Improved strongly deniable authenticated key exchanges for secure messaging, Proceedings on Privacy Enhancing Technologies 2018(1) (2018), 21–66. doi:10.1515/popets-2018-0003.

37.

Ustaoglu, Obtaining a secure and efficient key agreement protocol from (H) MQV and NAXOS, Designs, Codes and Cryptography 46(3) (2008), 329–342. doi:10.1007/s10623-007-9159-1.

38.

Walfish, Enhanced security models for network protocols, PhD thesis, New York University, 2008.

39.

Waters, Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization, in: PKC, 2011, pp. 53–70.

40.

A.C.-C.

Yao and

Zhao, OAKE: a new family of implicitly authenticated Diffie–Hellman protocols, in: ACM, CCS, 2013, pp. 1113–1128.

41.

A.C.-C.

Yao and

Zhao, Privacy-preserving authenticated key-exchange over Internet, IEEE Transactions on Information Forensics and Security 9(1) (2014), 125–140. doi:10.1109/TIFS.2013.2293457.

42.

Yoneyama, Strongly secure two-pass attribute-based authenticated key exchange, in: Pairing-Based Cryptography, 2010, pp. 147–166.

43.

Yung and

Zhao, Interactive zero-knowledge with restricted random oracles, in: TCC, 2006, pp. 21–40.

DABKE: Secure deniable attribute-based key exchange framework

Abstract

Keywords

1. Introduction

1.1. Related work

2. Security model

2.1. Definitions

2.2. Session key security

Definition 2.1. We say a DABKE protocol has session key security if for any probabilistic polynomial-time (PPT) A , Adv A ( λ ) is a negligible function of the security parameter λ. 2.3. User privacy

Definition 2.2. We say a DABKE protocol has user privacy if for any PPT A , Adv A ( λ ) is a negligible function of the security parameter λ. 2.4. Strong deniability

3.1. Building blocks

3.2. Generic compiler

Footnotes

Acknowledgments

References

Definition 2.1.
We say a DABKE protocol has session key security if for any probabilistic polynomial-time (PPT) $A$ , ${Adv}_{A} (λ)$ is a negligible function of the security parameter λ.

2.3. User privacy

Definition 2.2.
We say a DABKE protocol has user privacy if for any PPT $A$ , ${Adv}_{A} (λ)$ is a negligible function of the security parameter λ.

2.4. Strong deniability