Flexible Group Non-interactive Key Exchange in the Standard Model

Abstract

In this paper, we constructed a non-interactive group key exchange protocol (GNIKE) with flexibility, i.e., the number of participants in the GNIKE is not predefined. Moreover, our GNIKE construction is only based on multilinear map and conventional cryptographic building blocks. The security proof of our GNIKE is in the standard model and relies on an n-exponent multilinear DDH assumption.

1 Introduction

1.1 Scalable and Flexible Key Exchange

To communicate with Bob in an untrusted environment, Alice has to agree with Bob on a common secret first. In such a situation, key exchange (KE) protocols can be applied to ensure a shared secret (key) protected against adversaries. Upon the establishment of the shared key, symmetric cryptography can be used to protect the real data (payload) flowing between them.

If we go beyond the 2-party case, one of the major challenges faced by group KE protocol design is to achieve scalability and flexibility simultaneously. Scalability means the shared key should be established within constant rounds of communication [18]. This property is critical for real-world KE protocol, especially in situations where expensive interactions have to be avoided as much as possible. Taking the Internet of Things (IoT) as an example, the energy consumption of the IoT end-devices rockets when sending and receiving messages, but the power supply is usually a battery with limited capacity. Thus communication round reduction can drastically reduce the manufacture and maintenance cost of such devices, generating greater margin for the IoT service provider.

On the other hand, flexibility means the protocol initiator Alice can choose how many partners she wants to share the key. This property becomes essential if the communication network is constructed in an ad-hoc way without predefined sizes. IoT and other mobile devices tend to form temporary communication groups frequently, so a flexible KE can also help support such applications.

Viewing from the pure theoretical aspect, non-interactive authenticated key exchange (NIKE) protocols can be applied to archive good scalability, as no communication round is needed between different participants for key establishment [9]. More specifically, by non-interactive it means that the initiator can first compute the shared group session key offline without contacting others. Once the key is ready to use, the initiator sends out the first message to all her peers, which carries the encrypted application data with associated information for sender identification and group member recognition. After the message arrived, the receiver can then use the associated information to compute the shared group (session) key, decrypt the application data and continue with more communication. However, it is not trivial to design flexible NIKE protocol for groups larger than three and it has become an attractive research topic since 2010.

1.2 Group Non-interactive Key Exchange With and Without $\textsf{ iO}$

Being proposed by Diffie and Hellman [8] in their celebrated work, the nature of NIKE was studied in depth by Freire et al. [9] in the 2 party case. Various security models were also formalized in [9]. Boneh et al. [5] constructed the first semi-static-secure GNIKE but with predefined number of users from indistinguishability obfuscator ($\textsf{ iO}$) [2]. Hofheinz et al. [15] constructed the first adaptively secure GNIKE with and without trusted setup from universal sampler, which is instantiated with $\textsf{ iO}$ and other components. The security proof of their trust-setup-free scheme is in the random oracle (RO) model. Rao [29] constructed adaptively secure NIKE among bounded number of parties based on the existence of $\textsf{ iO}$ and multilinear map for the cases with and without trusted setup. Khurana et al. [19] constructed a NIKE for unbounded parties from $\textsf{ iO}$ with trusted setup and non-adaptive security. An overview of the comparable GNIKE works can be found in Table 1. Unlike the existing and provably secure GNIKE protocols mentioned above, our solution and its security directly depends on multilinear map.

Indistinguishability Obfuscation and Multilinear Map. In STOC 2021, it has been shown that $\textsf{ iO}$ can be constructed through a long line of bootstrapping from well-founded assumptions (LWE, structured PRG in $\textbf{NC}^0$, LPN) [17] or from circular security assumptions [14], but most of the existing constructions of $\textsf{ iO}$ are in fact based on multilinear map [12, 23,24,25, 28].

Besides $\textsf{ iO}$, multilinear map is frequently used to construct other interesting primitives, such as attribute based encryption [13] and revocable identity based encryption [27]. Up to now, there exist a limited number of multi-linear map proposals, such as GGH [11], CLT [7] and their variants [21]. Each proposal depends only on the hardness of one problem. GGH needs learning-with-error problem (LWE) and CLT needs Graded Decisional Diffie-Hellman [7]. Analysis of these multilinear map proposals has also been made, which often exposes weakness in the candidate but also inspires remedies [4, 6, 16].

As multilinear map usually depends only on one assumption and as fundamental as $\textsf{ iO}$ [26], building a GNIKE protocol directly on multilinear map results in lightweight design and simplified security arguments.

1.3 Our Contribution and the Outline of the Paper

Provable security has become a fundamental requirement for all newly proposed schemes or protocols. To formally address the security issues of GNIKE protocols, we propose the definition and the generic security models.

Most importantly, we construct a provably secure and scalable GNIKE protocol with limited trusted setup. This means that only the system wide public parameters (including one public key) is required to be trusted, while the participants can generate their own key pairs conforming with the public parameters.

Moreover, our GNIKE construction is only based on the existence of multilinear maps, besides more conventional cryptographic building blocks such as the chameleon hash. In addition, our main security theorem is proved in standard model relying on an n-exponent multi-linear DDH ($\textsf{nEMDDH}$) assumption without the use of random oracles.

Outline. The notations and definitions of cryptographic primitives are presented in Sect. 2. The model and definition of GNIKE can be found in Sect. 3. The main construction, the security theorem proof and its proof are provided in Sect. 4. The conclusion, as well as the future works, is presented in Sect. 6. The intractability of our complexity assumption is analyzed in Appendix A.

1.4 Other Related Works

Scalable Interactive Group Key Exchange. In 2003, Katz et al. [18] proposed the first scalable interactive group authenticated key exchange protocol, as well as a scalable compiler that can transform other passively secure group KE protocol to a group AKE, adding only one round of communication. The authors also enclosed a survey about the then existing group AKE protocols, focusing on the provable security and efficiency of these protocols. Abdalla et al. [1] presented a flexible group AKE protocol, with which the members of the main group can establish session keys for sub-groups interactively.

Table 1. The comparison of GNIKE protocols involving n participants, w.r.t. computational complexity, where $\textsf{ iO}$ prog. gen. denotes to generate an obfuscated program with the $\textsf{ iO}$ and prog. op. denotes to call an obfuscated program.

2 Preliminaries

Notations. We let $\kappa \in \mathbb {N}$ denote the security parameter, and $1^\kappa$ the unary string of length $\kappa$. Let $[n] = \{1,\ldots ,n\} \subset \mathbb {N}$ be the set of integers between 1 and n. If S is a set, $a {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}S$ denotes the action of sampling a uniformly random element from S. The term X||Y denotes the operation of concatenating two binary strings X and Y. Let $F(x) {\mathop {\rightarrow }\limits ^{{\scriptscriptstyle \$}}}y$ denote that a probabilistic algorithm F() takes x as input and outputs y. Other notations will be introduced when they first appear.

2.1 Chameleon Hash Functions

Chameleon hashes [20] are a class of trapdoor cryptographic hash functions that, without knowledge of the associated trapdoor, are resistant to the inversion and of collision attacks. On the other hand, the collisions can be efficiently found with the trapdoor information.

Definition 1 (Chameleon Hash)

A chameleon hash function $\textsf{CH}$ is a tuple of three polynomial time algorithms $\textsf{CH}= (\mathsf {CH.GEN}, \textsf{H},\textsf{CF})$.

• $\mathsf {CH.GEN}(1^\kappa ) {\mathop {\rightarrow }\limits ^{{\scriptscriptstyle \$}}}(\textsf{p},\mathsf {\tau })$. The non-deterministic key generation algorithm $\mathsf {CH.GEN}(1^\kappa )$ on input of a security parameter $1^\kappa$, outputs a chameleon hash function key pair ($\textsf{p}$, $\mathsf {\tau }$), where $\textsf{p}$ is the public key of chameleon hash and $\mathsf {\tau }$ the trapdoor key.

• $\textsf{H}_{\textsf{p}}( m, r) {\mathop {\rightarrow }\limits ^{{\scriptscriptstyle \$}}}h$. Let $\mathbb {D}_{\mathcal{C}\mathcal{H}}$ be the space of messages, $\mathbb {R}_{\mathcal{C}\mathcal{H}}$ the space of randomness and $\mathbb {Z}_{\mathcal{C}\mathcal{H}}$ the space of hash values, all of which are parametrized by $1^\kappa$ and associated with ($\textsf{p}$, $\mathsf {\tau }$). The polynomial algorithm $\textsf{H}_{\textsf{p}}( m, r)$, on input of the public key $\textsf{p}$, a message $m\in \mathbb {D}_{\mathcal{C}\mathcal{H}}$ and a randomness $r \in \mathbb {R}_{\mathcal{C}\mathcal{H}}$, computes a hash value $h\in \mathbb {Z}_{\mathcal{C}\mathcal{H}}$.

• $\textsf{CF}_{\mathsf {\tau }}(m,r) = (m^*,r^*)$. The collision finding algorithm $\textsf{CF}_{\mathsf {\tau }}(h,r)$ takes as input the trapdoor key $\mathsf {\tau }$, a message $m\in \mathbb {D}_{\mathcal{C}\mathcal{H}}$ and a randomness $r\in \mathbb {R}_{\mathcal{C}\mathcal{H}}$ and it outputs a message $m^* \in \mathbb {D}_{\mathcal{C}\mathcal{H}}$ and a randomness $r^*\in \mathbb {R}_{\mathcal{C}\mathcal{H}}$ with $\textsf{H}_{\textsf{p}}(m, r) = \textsf{H}_{\textsf{p}}( m^*, r^*)$, $m \ne m^*$ and $r \ne r^*$.

Definition 2 (Collision resistance)

$\textsf{CH}$ is called $(t_{\textsf{CH}},\epsilon _{\textsf{CH}})$-chameleon-hash if for all $t_{\textsf{CH}}$-time adversaries $\mathcal {A}$ it holds that

$$\begin{aligned} \Pr \begin{bmatrix} \ (\textsf{p},\mathsf {\tau }) {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathsf {CH.GEN}(1^\kappa ); (m, m^*, r, r^*) {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathcal {A} (1^\kappa , \textsf{H}, \textsf{p}):\\ m \ne m^* \bigwedge r \ne r^* \bigwedge \textsf{H}_{\textsf{p}}(m, r)=\textsf{H}_{\textsf{p}}(m^*, r^*) \end{bmatrix} \le \epsilon _{\textsf{CH}}(\kappa )\text{, } \end{aligned}$$

where $\epsilon _{\textsf{CH}}(\kappa )$ is a negligible function in the security parameter $\kappa$, messages $m, m^* \in \mathbb {D}_{\mathcal{C}\mathcal{H}}$ and randomness $r, r^* \in \mathbb {R}_{\mathcal{C}\mathcal{H}}$.

2.2 Multilinear Maps

In the following, we briefly recall some of the basic properties of multilinear maps as in [3].

Definition 3 (n-Multilinear Maps)

We state that a map $\textsf{nMAP}$ : $\mathbb {G}_1 \times \ldots \times \mathbb {G}_n$ $\rightarrow$ $\mathbb {G}_T$ is an $\textsf{nMultilinear}$ map if it satisfies the following properties:

• 1. $\mathbb {G}_1 \ldots \mathbb {G}_n$ and $\mathbb {G}_T$ are groups of the same order.

• 2. if $x_i \in \mathbb {Z}_p$, $X_i \in \mathbb {G}_i$ and $i= 1, \ldots n$, then

  $\textsf{nMAP}(X_1^{x_1}, \ldots , X_n^{x_n})= \textsf{nMAP}(X_1, \ldots , X_n)^{\prod _{i=1}^{x} x_i}$,

• 3. if $g_i \in G_i$ is a generator of $\mathbb {G} _i$, then $g_T = \textsf{nMAP}(g_1, \ldots , g_n)$ is a generator of $\mathbb {G}_T$, where $i= 1, \ldots n$.

We assume the existence of a group description generation algorithm $\mathsf {nMGG.Gen}$, which takes as input a security parameter $\kappa$ and a positive integer $n \in \mathbb {N}$. The output of $\mathsf {nMGG.Gen}(1^\kappa , n)$ is $\textsf{MG}=(\mathbb {G}, \textsf{nMAP})$, which contains a sequence of groups $\mathbb {G}= (\mathbb {G}_1,\ldots ,\mathbb {G}_n, \mathbb {G}_T)$ each of a large prime order $p > 2^\kappa$ and a multilinear map $\textsf{nMAP}$ over $\mathbb {G}$. Note that a multilinear map is symmetric when $\mathbb {G}_1 = \ldots = \mathbb {G}_n$ and $g_1 = \ldots = g_n$, otherwise the asymmetric case when different $\mathbb {G}_i$ was considered.

2.3 The n-Exponent Multilinear Decision Diffie-Hellman Assumption

First, let $\textsf{GP}= (\mathbb {G}_1, g_1, \ldots , \mathbb {G}_n, g_n, \mathbb {G}_T, p, \textsf{nMAP})$ denote the description of asymmetric multilinear group. For simplicity, we state the complexity assumption needed for our proof of security using symmetric multilinear maps, i.e. $\mathbb {G}_1 = \ldots = \mathbb {G}_n$, and $g_1 = \ldots = g_n$. The n-Exponent multilinear decisional Diffie-Hellman ($\textsf{nEMDDH}$) problem that is stated as follows: given a tuple $(g, g^a, g^b, R) \in \mathbb {G}^3 \times \mathbb {G}_T$ as input, where $a, b \in \mathbb {Z}_p$ and output yes if $\textsf{nMAP}(g, \ldots , g )^{a^nb} = R$ and no otherwise.

Definition 4

We say that the $\textsf{nEMDDH}$ problem is $(t,\epsilon _{\textsf{nEMDDH}})$-hard in $\textsf{GP}$ if for all adversaries running in time t, it holds that

$$ \left| \Pr \left[ \mathcal {A} (g,g^a, g^b, \textsf{nMAP}(g, \ldots , g )^{a^nb}) = 1 \right] - \Pr \left[ \mathcal {A} (g,g^a, g^b, R) = 1\right] \right| \le \epsilon _{\textsf{nEMDDH}}, $$

where $(g, g^a, g^b, R) {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {G}^3 \times \mathbb {G}_T$.

3 Group Non-interactive Key Exchange and Security Models

3.1 Group Non-interactive Key Exchange

Following Freire, et al. [9], we first present a generic definition of group non-interactive key exchange ($\textsf{GNIKE}$) in the public key setting. For a $\textsf{GNIKE}$ protocol, each party of a group knows the others’ public keys, and without requiring any interaction they can agree on a common shared key. The shared key is generated to be known only by the members of a group.

Let $\mathcal {K}_\mathcal{G}\mathcal{K}$ be the space of shared keys, $\{\mathcal{P}\mathcal{K},\mathcal{S}\mathcal{K}\}$ be key spaces of long-term public keys and private keys respectively, $\mathcal {IDS}$ the identity space of the parties, $\mathcal {K}_\mathcal{G}\mathcal{K}$ the space of the shared group keys. Those spaces are associated with security parameter $\kappa$ of the considered protocol. Let $\textsf{GPK}= \{(ID_t, pk_{\textsf{ID}_t})\}_n$ be the set of tuples to store the public information of all parties for $\textsf{GNIKE}$, where n is the size of the group, $t \in [n]$ and $pk_{\textsf{ID}_t}$ the public key of the party with the identity $\textsf{ID}_t \in \mathcal {IDS}$, and $\textsf{GPK}_i=\textsf{GPK}\setminus \{ID_i, pk_{\textsf{ID}_i}\}$¹. Each party with $\textsf{ID}_t$ ($t \in [n]$) has a static key pair $(pk_{\textsf{ID}_t},sk_{\textsf{ID}_t}) \in (\mathcal{P}\mathcal{K},\mathcal{S}\mathcal{K})$. A general PKI-based $\textsf{GNIKE}$ protocol consists of three polynomial time algorithms $(\mathsf {GNIKE.Setup}, \mathsf {GNIKE.KGen},\mathsf {GNIKE.SKG})$ with following semantics:

• $\mathsf {GNIKE.Setup}(1^\kappa ) \rightarrow pms$: This algorithm takes as input a security parameter $\kappa$ and outputs a set of system parameters stored in a variable pms.

• $\mathsf {GNIKE.KGen}(pms,\textsf{ID}_i) \rightarrow (pk_{\textsf{ID}_i},sk_{\textsf{ID}_i})$: This algorithm takes as input system parameters pms and a party’s identity $\textsf{ID}_i$, and outputs a random key pair $(pk_{\textsf{ID}_i},sk_{\textsf{ID}_i}) \in \{\mathcal{P}\mathcal{K},\mathcal{S}\mathcal{K}\}$ for party $\textsf{ID}_i$.

• $\mathsf {GNIKE.SKG}(sk_{\textsf{ID}_i}, \textsf{ID}_i, \textsf{GPK}_i) \rightarrow K_{\textsf{GPK}}$: This algorithm take as input ($sk_{\textsf{ID}_i}$, $\textsf{ID}_i$) and the group public information $\textsf{GPK}_i=\{(\textsf{ID}_t, pk_{\textsf{ID}_t})\}$, then outputs a shared key $K_{\textsf{GPK}} \in \mathcal {K}_\mathcal{G}\mathcal{K}$. Notice that this algorithm $\mathsf {GNIKE.SKG}$ is allowed to output a shared key $K_{\textsf{GPK}}$, even though some participants $\textsf{ID}_i$ = $\textsf{ID}_{j}$, where $\textsf{ID}_i$, $\textsf{ID}_{j}$ $\in$ $\textsf{GPK}$. For correctness, on input the same group description the algorithm $\mathsf {GNIKE.SKG}$ must satisfy the constraint:

  • $\mathsf {GNIKE.SKG}(sk_{\textsf{ID}_i}, \textsf{ID}_i, \textsf{GPK}_i) = \mathsf {GNIKE.SKG}(sk_{\textsf{ID}_j}, \textsf{ID}_j, \textsf{GPK}_j)$, where $sk_{\textsf{ID}_i}$ and $sk_{\textsf{ID}_j}$ are secret keys of parties $\textsf{ID}_i, \textsf{ID}_j$.

3.2 Security Models for GNIKE

Freire, et al. [9] formalized a list of security models for $\textsf{NIKE}$ schemes in the 2-party setting, including the honest/dishonest key registration $\textsf{PKI}$ system, denoted here as $\textsf{FHKP}$ models. By generalizing these models into the n-party case ($n \ge 3$), various works have defined the static security [19, 31] and the adaptive security [15, 29]. It is the main difference between those two security definitions whether the adversary has to commit to a group $\mathcal {S}^*$ to be challenged on before issuing any other queries. Essentially, A protocol is said to be static secure if the adversary has to commit to $\mathcal {S}^*$ and adaptively secure otherwise. We follow the adaptive definition and in our models, the adversary can actively interact with $\textsf{RegisterHonestUID}$, $\textsf{RegisterCorruptUID}$, $\textsf{Corrupt}$, $\textsf{RevealHonestKey}$, $\textsf{RevealCorruptKey}$ and $\textsf{Test}$ oracles, which we will describe below.

Group Partner Identities. We say that a party $P_{\textsf{ID}_i}$ is a partner of another party $P_{\textsf{ID}_j}$, if they share the same shared key. Notice that $P_{\textsf{ID}_i}$ has multiple partners for $\textsf{GNIKE}$ protocol. Each party can sequentially and concurrently execute the protocol multiple times with its (different) partners. This is modeled by allowing each principal an unlimited number of instances with which to execute the protocol. We denote group partner identities of any instance s for $\textsf{GNIKE}$ using a variable $\textsf{Gpid}$. The group partner identities of instance s, denoted here as $\textsf{Gpid}^s$, stores a set containing the identities of the players that intend to establish a shared key for instance s, where the identities are ordered lexicographically. $n = |\textsf{Gpid}^s|$ is the number of the identities involved in this instance s. It means that n implies the group-size of key exchange. The $\textsf{Gpid}$ of instance s is set to $\{\textsf{ID}_1, \ldots , \textsf{ID}_n\}$.

Adversarial Model. The adversary $\mathcal {A}$ is assumed to have complete control over all communication in the public network. $\mathcal {A}$ in our models is a PPT Turing Machine taking as input the security parameter $\kappa$ and the public information (e.g. generic description of the environment mentioned above). $\mathcal {A}$’s interaction with the principals is modeled by the following oracles. In $\textsf{GNIKE}$ there is no interaction among the parties, so it means that for modelling a active adversaries against $\textsf{GNIKE}$ no $\textsf{Send}$ query can be considered in the models.

We assume for simplicity a polynomial-size set $\textsf{PP}$ = $\{\textsf{ID}_1, \ldots , \textsf{ID}_i, \ldots , \textsf{ID}_\ell \}$ of potential honest participants, where $\textsf{ID}_i$ represents the identity of a party, and $i \in [\ell ]$. In our models, $\mathcal {A}$ can control the number of the potential participants by the $\textsf{RegisterHonestUID}$ and $\textsf{RemoveUID}$ queries. Each identity $\textsf{ID}_i$ is associated with a static key pair $(pk_{\textsf{ID}_i},sk_{\textsf{ID}_i}) \in (\mathcal{P}\mathcal{K},\mathcal{S}\mathcal{K})$. The number of the honest parties ($[\ell ]$) is bounded by polynomials in the security parameter $\kappa$. Any subset of $\textsf{PP}$ may decide at any point to establish a shared key. Notice that we do not assume that these subsets are always the same size for the flexibility of $\textsf{GNIKE}$. $\textsf{ID}_i$ is chosen uniquely from the identity space $\mathcal {IDS}$ in the model.

• $\textsf{RegisterHonestUID}(\textsf{ID}_i)$: This query allows $\mathcal {A}$ to register with an identity. $\mathcal {A}$ supplies an identity $\textsf{ID}_i (i \in [\ell ]$) and a static public key $pk_{\textsf{ID}_i}$ is returned to $\mathcal {A}$.

• $\textsf{RegisterCorruptUID}(\textsf{ID}_i,pk_{\textsf{ID}_i})$: This query allows $\mathcal {A}$ to register a new identity $\textsf{ID}_i$ (i $\notin$ $[\ell ]$) and a static public key $pk_{\textsf{ID}_i}$ on behalf of a party $\textsf{ID}_i$. In response, if the same identity $\textsf{ID}_i$ (with a different public key) already exists for $\textsf{RegisterCorruptUID}$ query, a failure symbol $\bot$ is returned to $\mathcal {A}$. Otherwise, $\textsf{ID}_i$ with the static public key $pk_{\textsf{ID}_i}$ is added, successfully. The parties registered by this query are called corrupted or adversary controlled.

• $\textsf{Corrupt}(\textsf{ID}_i)$: This query allows $\mathcal {A}$ to obtain a secret key of a party with the identity $\textsf{ID}_i$ that was registered as an honest user. The corresponding long-term secret key $sk_{\textsf{ID}_i}$ is returned to $\mathcal {A}$.

• $\textsf{RevealHonestKey}(\textsf{Gpid}, s)$: $\mathcal {A}$ supplies the group partner identities $\textsf{Gpid}$ (in lexicographic order) for protocol instance s, and $\textsf{RevealHonestKey}$ Oracle returns a shared key $K_{\textsf{Gpid}}^s$ to $\mathcal {A}$. For the query the related identities in $\textsf{Gpid}$ must be registered as honest.

• $\textsf{RevealCorruptKey}(\textsf{Gpid}, s)$: This responds with the shared key $K_{\textsf{Gpid}}^s$. Notice that at least one of the involved identities in $\textsf{Gpid}$ was registered as honest.

• $\textsf{Test}(\textsf{Gpid}, s)$: $\mathcal {A}$ gives $\textsf{Gpid}$ and instance s as inputs to $\textsf{Test}$ Oracle. $\textsf{Test}$ Oracle handles this query as follows: if one of the identities supplied by $\mathcal {A}$ was registered as corrupt or $K_{\textsf{Gpid}}^s = \emptyset$, it then returns some failure symbol $\bot$. Otherwise it flips a fair coin b, samples a random element $K_0$ from key space $\mathcal {K}_\mathcal{G}\mathcal{K}$, sets $K_1 = K_{\textsf{Gpid}}^s$ to the real shared key, and returns $K_b$.

Secure GNIKE Protocols. Recall that actual security goals for $\textsf{GNIKE}$ protocols are always specified by individual security games. Here we describe how $\mathcal {A}$ interacts with the security game. We define when an adversary is said to break $\textsf{GNIKE}$ protocols. We firstly state the security game between a challenger $\mathcal {C}$ and an adversary $\mathcal {A}$.

Security Game. The security game is played between $\mathcal {C}$ and $\mathcal {A}$, where the following steps are performed:

• 1. At the beginning of the game, the challenger $\mathcal {C}$ runs algorithm $\mathsf {GNIKE.Setup}$ with the security parameter $\kappa$ as input. $\mathcal {C}$ gives the public parameters to $\mathcal {A}$.

• 2. Now the adversary $\mathcal {A}$ may start issuing $\textsf{RegisterHonestUID}$, $\textsf{RegisterCorruptUID}$, $\textsf{Corrupt}$, $\textsf{RevealHonestKey}$ and $\textsf{RevealCorruptKey}$ queries The numbers of queries made by $\mathcal {A}$ are bounded by polynomials in security parameter $\kappa$.

• 3. At some point, $\mathcal {A}$ may issue a $\textsf{Test}$-query during the experiment. Notice that $\mathcal {A}$ can issue an arbitrary number of $\textsf{Test}$-queries bounded by polynomials in $\kappa$ for a strong model ($\textsf{GNIKE}$ or $\mathsf {mGNIKE.Heavy}$). In this case, to keep random keys consistent, the $\mathcal {C}$ responds the same random key for the same identities every time $\mathcal {A}$ queries for their shared key, in either order.

• 4. At the end of the game, $\mathcal {A}$ terminates with outputting a bit $b'$ as its guess for b of $\textsf{Test}$ query.

Definition 5 (Correctness)

We require that for all participants $\textsf{ID}_i, \textsf{ID}_j \in \textsf{Gpid}$ for instance $s^*$ involved in the same $\textsf{GNIKE}$ and such that without a failure symbol $\bot$, the same valid shared key is established $K_{\textsf{Gpid}}^{s^*}$ = $K_{\textsf{ID}_i}^{s^*}$ = $K_{\textsf{ID}_j}^{s^*} \ne \textsf{null}$.

Definition 6 (Freshness)

For the security definition, we need the notion about the freshness of $\textsf{Test}$ oracle which formulates the restrictions on the adversary with respect to performing these above queries. Let $\textsf{Gpid}^{s^*}$ denote the group partner identities for instance $s^*$ (i.e. ($\textsf{Gpid}, s^*$)) queried to $\textsf{Test}$ oracle selected by $\mathcal {A}$. Then the $\textsf{Test}$ oracle is said to be fresh if none of the following conditions holds:

• 1. There is a party with identity $\textsf{ID}_i \in \textsf{Gpid}^{s^*}$ which is established by adversary $\mathcal {A}$ via $\textsf{RegisterCorruptUID}$ query, i.e. $\textsf{ID}_i$ was registered as dishonest.

• 2. $\mathcal {A}$ makes a corrupt query $\textsf{Corrupt}$ to any identity $\textsf{ID}_i$, where $\textsf{ID}_i \in \textsf{Gpid}^{s^*}$.

• 3. $\mathcal {A}$ either makes a query $\textsf{RevealHonestKey}(\textsf{Gpid}, s^*)$ for instance $s^*$, or a query $\textsf{RevealHonestKey}(\textsf{Gpid}, s)$ to any $\textsf{Gpid}$ of instance s, with $\textsf{Gpid}^s$ = $\textsf{Gpid}^{s^*}$.

Security of $\textsf{GNIKE}$ protocols is now defined by requiring that the protocol is a shared key secure non-interactive key-exchange protocol, thus an adversary cannot distinguish the shared key from a random key.

Definition 7 (Non-interactive Shared Key Security)

A group non-interactive key exchange protocol $\varSigma$ is called $(t,\epsilon )$-shared-key-secure if for all adversaries $\mathcal {A}$ running within probabilistic polynomial time t in the security game as above and for some negligible probability $\epsilon = \epsilon (\kappa )$ in the security parameter $\kappa$, it holds that:

• When $\mathcal {A}$ returns $b'$ and it holds that

  • $\mathcal {A}$ has issued a query on $\textsf{Test}$ oracle using ($\textsf{Gpid}, s^*$) without failure,

  • the $\textsf{Test}$ oracle for ($\textsf{Gpid}, s^*$) is fresh throughout the security experiment

  then the probability that $b'$ equals the bit b sampled by the $\textsf{Test}$-query is bounded by

  $$\begin{aligned} |\Pr [b = b'] - 1/2| \le \epsilon \end{aligned}$$

4 A Flexible GNIKE Protocol from Multilinear Maps

$\textsf{GNIKE}$ protocols are often carried out in dynamic sets of the participants. One critical feature of $\textsf{GNIKE}$ protocols is to ensure flexibility, i.e., one participant can choose the group members freely. In this section we present a flexible (and salable by definition) construction of group non-interactive key exchange $\textsf{GNIKE}$, which is provably secure in the standard model without assuming the existence of random oracles or $\textsf{ iO}$. The chameleon hash function is used to bind the user identity and the corresponding initial randomness when generating long-term user key pairs.

4.1 Protocol Description

We describe the protocol in terms of the following three parts: system setup $\mathsf {GNIKE.Setup}$, party-registration and long-term key generation $\mathsf {GNIKE.KGen}$, and group shared key computation $\mathsf {GNIKE.SKG}$.

• 1. $\mathsf {GNIKE.Setup}(1^\kappa , n)$: The proposed protocol is composed of the following building blocks which are instantiated and initialized respectively in accordance of the security parameter $1^\kappa$. Before the main protocol runs for the first time, an upper bound n on the size of the group is set in the initialization phase.

  • generate an $\textsf{nMultilinear}$ map $\textsf{MG}$ = $(\mathbb {G}, g, \mathbb {G}_{T}, p, \textsf{nMAP})$ ${\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}$ $\mathsf {GP.Gen}(1^{\kappa }, n)$, a random element $S {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {G}$, and a set of random values $\{u_{l}\}_{0 \le l \le n} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {G}$, where n is the upper bound on the size of the group.

  • fix an identity space $\mathcal{I}\mathcal{D}\subset \{0,1\}^*$.

  • parametrize a chameleon hash function

    $\textsf{CH}= (\mathsf {CH.GEN}, \textsf{H},\textsf{CF}):$ $(\mathbb {G}\times \mathcal{I}\mathcal{D}) \times \mathbb {R}_{\textsf{CH}} \rightarrow \mathbb {Z}^*_p$, i.e., $\mathbb {D}_{\mathcal{C}\mathcal{H}} = (\mathbb {Z}^*_p \times \mathcal{I}\mathcal{D})$ and $\mathbb {Z}_{\mathcal{C}\mathcal{H}} = \mathbb {Z}^*_p$. $\mathbb {R}_{\mathcal{C}\mathcal{H}} \subset \{0,1\}^*$ is a fixed the space of randomness. Let $\textsf{CHAMKey}=(\textsf{p}, \mathsf {\tau }) {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathsf {CH.GEN}(1^\kappa )$ be the pair of public key and trapdoor key.

  • select a random element $\varPhi {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {G}$, denoted here as padding for achieving flexibility.

  The system parameter variable pms is $(\textsf{MG},\{u_l\}_{0\le l \le n}, S, \varPhi , \textsf{CH}, \textsf{p})$.

• 2. $\mathsf {GNIKE.KGen}(pms, \textsf{ID}_{\hat{A_i}})$: On input the system parameter pms, the key generation algorithm $\mathsf {GNIKE.KGen}$ generates the long-term key pair for a party $\hat{A_i}$ as:

  • choose $a_{\hat{A}_i} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {Z}^*_p, r_{\hat{A}_i} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {R}_{\textsf{CH}}$,

  • compute $Z_{\hat{A}_i}$ := $g^{a_{\hat{A}_i}}$ and $t_{\hat{A}_i}$ = $\textsf{H}_{\textsf{p}}(Z_{\hat{A}_i} || \textsf{ID}_{\hat{A}_i}, r_{\hat{A}_i})$, and

  • compute $Y_{\hat{A}_i} := (u_{0} u_{1}^{(t_{\hat{A}_i})^1} u_{2}^{(t_{\hat{A}_i})^2} \ldots u_{n}^{(t_{\hat{A}_i})^n})$ and $X_{\hat{A}_i}$ := $Y_{\hat{A}_i}^{a_{\hat{A}_i}}$.

  The long-term key pair for $\hat{A}_i$: $PK_{\textsf{ID}_{\hat{A}_i}} = (Z_{\hat{A}_i}, r_{\hat{A}_i}, X_{\hat{A}_i})$ and $SK_{\textsf{ID}_{\hat{A}_i}} = a_{\hat{A}_i}$ .

• 3. $\mathsf {GNIKE.SKG}(sk_{\textsf{ID}_{\hat{A}_i}},ID_{\hat{A}_i}, \textsf{GPK}_{\hat{A}_i})$: On input a private key $sk_{\textsf{ID}_{\hat{A}_i}}$ and an identity $ID_{\hat{A}_i}$ of a party $\hat{A}_i$ along with a set of the public parameters $\textsf{GPK}_{\hat{A}_i}$², algorithm $\mathsf {GNIKE.SKG}$ is executed by each of the parties $\hat{A}_1$, $\ldots$, $\hat{A}_{n^*}$ as follows:

  • The party $\hat{A}_i$ first checks whether for all identities $\hat{A}_i$, $\hat{A}_j$ ($i, j \in [n^*], i\ne j$) it holds that $ID_{\hat{A_{i}}} \ne ID_{\hat{A_{j}}}$. The user identity must be unique within each group domain

  • $\hat{A}_i$ computes $t_{\hat{A}_j}$ = $\textsf{H}_{\textsf{p}}(Z_{\hat{A}_j} || \textsf{ID}_{\hat{A}_j}, r_{\hat{A}_j})$ and $Y_{\hat{A}_j} = u_{0} u_{1}^{(t_{\hat{A}_j})^1} \ldots u_{n}^{(t_{\hat{A}_j})^n}$ for all $j \in \{1, \ldots , i-1, i+1, \ldots , n^*\}$.

  • If $2\le n^* \le n$ and $\forall j\in \{1, \ldots , i-1, i+1, \ldots , n^*\}$, it holds that

    $$\begin{aligned} \textsf{nMAP}(Y_{\hat{A}_j}, Z_{\hat{A}_j}, \underbrace{g, \ldots , g}_\text {n-2}) = \textsf{nMAP}(X_{\hat{A}_j}, \underbrace{g, \ldots , g}_\text {n-1}) \end{aligned}$$

    (1)

    • If $n^* = n$, $\hat{A}_i$ computes the shared key as follows:

      $$\begin{aligned} K_{ID_{\hat{A}_{1, \ldots , n^*}}} = \textsf{nMAP}(Z_{\hat{A}_1}, \ldots , Z_{\hat{A_{i}-1}}, Z_{\hat{A}_{i+1}}, \ldots , Z_{\hat{A}_n^*}, S)^{sk_{\textsf{ID}_{\hat{A}_i}}}, \end{aligned}$$

    • Else, $\hat{A}_i$ adds ($n - n^*$) $\varPhi$ padding to the generation function of the shared key (i.e. $\textsf{nMAP}$)and computes the shared key as follows:

      $$\begin{aligned} K_{ID_{\hat{A}_{1, \ldots , n^*}}} = \textsf{nMAP}(Z_{\hat{A}_1}, \ldots , Z_{\hat{A}_{i-1}}, Z_{\hat{A}_{i+1}}, \ldots , Z_{\hat{A}_n^*}, \underbrace{\varPhi , \ldots , \varPhi }_{n - n^*}, S)^{sk_{\textsf{ID}_{\hat{A}_i}}} \end{aligned}$$

  • Else $\hat{A}_i$ terminates the protocol execution.

Correctness. In the case when $n^* = n$, for $\textsf{ID}_{\hat{A_i}}$ we have

$$\begin{aligned} K_{ID_{\hat{A}_{1, \ldots , n^*}}}&= \textsf{nMAP}(Z_{\hat{A}_1}, \ldots , Z_{\hat{A}_{i-1}}, Z_{\hat{A}_{i+1}}, \ldots , Z_{\hat{A}_n^*}, S)^{sk_{\textsf{ID}_{\hat{A}_i}}} \\&= \textsf{nMAP}(g,\ldots ,g, S)^{\prod _{i=1}^{n^*}{a_{\hat{A}_i}}} \end{aligned}$$

For $\textsf{ID}_{\hat{A_j}}$ we have

$$\begin{aligned} K'_{ID_{\hat{A}_{1, \ldots , n^*}}}&= \textsf{nMAP}(Z_{\hat{A}_1}, \ldots , Z_{\hat{A}_{j-1}}, Z_{\hat{A}_{j+1}}, \ldots , Z_{\hat{A}_n^*}, S)^{sk_{\textsf{ID}_{\hat{A}_j}}} \\&= \textsf{nMAP}(g,\ldots ,g, S)^{\prod _{j=1}^{n^*}{a_{\hat{A}_j}}} \end{aligned}$$

By changing the name of variable it can be easily seen that $K_{ID_{\hat{A}_{1, \ldots , n^*}}} = K'_{ID_{\hat{A}_{1, \ldots , n^*}}}$. The correctness argument for the case when $2 \le n^* < n$ is almost the same.

Rationale of the Construction. Given $(Z_{\hat{A}_i}, r_{\hat{A}_i}), \{u_{l}\}_{0 \le l \le n}$, it is straight forward to compute $Y_{\hat{A}_i}$ with the chameleon hash function $\textsf{CH}$ for the party $\textsf{ID}_{\hat{A}_i}$. If $X_{\hat{A}_i}$ is consistent with $\textsf{ID}_{\hat{A}_i}$ and $( Z_{\hat{A}_i}, r_{\hat{A}_i})$, i.e., $X_{\hat{A}_i} = Y_{\hat{A}_i}^{a_{\hat{A}_i}}$, then it should satisfy the $\textsf{nMAP}$-equation (1) in $\mathsf {GNIKE.SKG}$. The $\textsf{nMAP}$-equation (1) not only checks the internal consistency of a public key, but also the consistency of the given public key with public parameters and the party identity. The random padding $\varPhi$ and S provide extra flexibility and they also help eliminate the random oracle in the security analysis.

4.2 Security Analysis

For simplicity, we prove the security of the $\textsf{GNIKE}$ scheme mentioned above in our security $\mathsf {GNIKE.Light}$ model. In the $\mathsf {GNIKE.Light}$ model, $\mathcal {A}$ is allowed to make the following queries: $\textsf{RegisterHonestUID}$, $\textsf{RegisterCorruptUID}$, and $\textsf{RevealCorruptKey}$ to oracles, as well as a single $\textsf{Test}$ query, while $\textsf{Corrupt}$ and $\textsf{RevealHonestKey}$ queries are forbidden. To prove our protocol’s adaptive security as in $\mathsf {GNIKE.Heavy}$, we will lose a factor of $\left( {\begin{array}{c}n\\ n^*\end{array}}\right)$, where n is the group size bound and $n^*$ the actual group size. Here the loss factor is exponential in the group size $n^*$. Hence, in order to make the adversarial advantage negligible, one may need to use a larger security parameter or to limit $n^*$.

Theorem 1

Suppose that the $\textsf{nEMDDH}$ problem is $(t,\epsilon _{\textsf{nEMDDH}})$-hard in $\textsf{GP}$ in the sense of Definition 4, and the $\textsf{CH}$ is $(t,\epsilon _{\textsf{CH}})$-secure chameleon hash function family. Then the proposed $\textsf{GNIKE}$ protocol is $(t',\epsilon )$-shared-key-secure in the sense of Definition 7 with $t' \approx t$ and $\epsilon _{\mathcal {A},\textsf{GNIKE}}^{\mathsf {GNIKE.Light}} \le \epsilon _{\textsf{CH}} + \epsilon _{\textsf{nEMDDH}}.$

5 Proof of Theorem 1

Now, we prove Theorem 1 using the sequence-of-games approach, following [30]. The proof strategy to remove the random oracle is inspired by [10].

Let $\textsf{S}^{}_{\delta }$ be the event that the adversary wins in game $\mathsf {G^{}_{\delta }}$. Let $\textsf{Adv}_\delta := \Pr [\textsf{S}^{}_{\delta }] - 1/2$ denote the advantage of $\mathcal {A}$ in game $\mathsf {G^{}_{\delta }}$.

Game $\mathsf {G_{0}}$. This is the original game with adversary $\mathcal {A}$ as described in the $\mathsf {GNIKE.Light}$ model. Thus we have that

$$ \Pr [\textsf{S}^{}_0] = 1/2 + \epsilon _{\mathcal {A},\textsf{GNIKE}}^{\mathsf {GNIKE.Light}} = 1/2 +\textsf{Adv}_{0}. $$

Game $\mathsf {G_{1}}$. In this game we want to make sure that there exist no chameleon hash collisions. Technically, we add an abort rule. More precisely, let $\textsf{abort}_\mathsf {\textsf{CH}}$ be the event that the challenger aborts when there exist two distinct identifiers $\hat{\textsf{H}}$ (e.g. $\textsf{ID}_{\hat{\textsf{H}}}$ is registered as $\textsf{Honest}$) and $\hat{\mathcal {A}}$ (e.g. $\hat{\mathcal {A}}$ is registered as $\textsf{Corrupt}$), with corresponding public keys $(Z_{\hat{\textsf{H}}}, Y_{\hat{\textsf{H}}}, r_{\hat{\textsf{H}}})$ and $(Z_{\hat{\mathcal {A}}}, Y_{\hat{\mathcal {A}}}, r_{\hat{\mathcal {A}}})$ such that $\textsf{H}_{\textsf{p}}(Z_{\hat{\textsf{H}}} || \textsf{ID}_{\hat{\textsf{H}}}, r_{\hat{\textsf{H}}})$ = $\textsf{H}_{\textsf{p}}(Z_{\hat{\mathcal {A}}} || \textsf{ID}_{\hat{\mathcal {A}}}, r_{\hat{\mathcal {A}}})$. If $\textsf{abort}_\mathsf {\textsf{CH}}$ did not happen, the challenger continues as in $\mathsf {G^{}_{0}}$. Obviously the $\Pr [\textsf{abort}_\mathsf {\textsf{CH}} ] \le \epsilon _{\textsf{CH}}$, according to the security property of underlying chameleon hash function. Until the event $\textsf{abort}_\mathsf {\textsf{CH}}$ happens, $\mathsf {G^{}_{0}}$ = $\mathsf {G^{}_{1}}$. Thus we have

$$ |\textsf{Adv}_{0}-\textsf{Adv}_{1}| \le \epsilon _{\textsf{CH}}. $$

Game $\mathsf {G_{2}}$. This game proceeds as the previous one, but the challenger always replies to the $\textsf{Test}$ query with a uniformly random element in $\mathbb {G}_T$. Thus the advantage of the adversary in this game is

$$ \textsf{Adv}_{2} = 0. $$

Let $\epsilon = |\textsf{Adv}_{1} - \textsf{Adv}_{2}|$ and $\epsilon _{\textsf{nEMDDH}}$ be the advantage of any adversary against the $\textsf{nEMDDH}$ problem (Definition 4). We claim that $\epsilon \le \epsilon _{\textsf{nEMDDH}}$. Due to page limit, we leave the complete simulation in Appendix B.

As described in Appendix B, $\mathcal {B}$ sets up all system parameters with the correct distributions and can simulate all queries of $\mathcal {A}$. So if $\mathcal {A}$ can distinguish the real case $\mathsf {G^{}_{1}}$ from the random case $\mathsf {G^{}_{2}}$, $\mathcal {B}$ can solve the $\textsf{nEMDDH}$ problem. Therefore we have

$$\begin{aligned} \textsf{Adv}_{\mathcal {B}} = \epsilon = |\textsf{Adv}_{1}-\textsf{Adv}_{2}| \end{aligned}$$

Since $\textsf{nEMDDH}$ assumption holds, we also have $\epsilon = \textsf{Adv}_{\mathcal {B}} \le \epsilon _{\textsf{nEMDDH}}$ and thus

$$ |\textsf{Adv}_{1}-\textsf{Adv}_{2}| \le \epsilon _{\textsf{nEMDDH}}. $$

Collecting the probabilities from Game $\mathsf {G^{}_{0}}$ to $\mathsf {G^{}_{2}}$, we have that

$$ \epsilon _{\mathcal {A},\textsf{GNIKE}}^{\mathsf {GNIKE.Light}} \le \epsilon _{\textsf{CH}} + \epsilon _{\textsf{nEMDDH}}. $$

6 Conclusion and Future Works

We constructed a provably secure, flexible and scalable GNIKE protocol. The security is proved under the $\textsf{nEMDDH}$ assumption in standard model. We leave it for future research to design a secure GNIKE protocol with tight security in the standard model.

Appendices

A Intractability Analysis of n-Exponent Multilinear Diffie-Hellman Assumption

To analyze the intractability of the n-exponent multilinear Diffie-Hellman assumption, we relate it to another problem which is claimed to be hard [10, 22]. This $\textsf{nMDDH}$ problem is rephrased below in our notation.

Definition 8

The n-multilinear decisional Diffie-Hellman ($\textsf{nMDDH}$) problem is $(t,\epsilon _{\textsf{nMDDH}})$-hard in $\textsf{GP}= (\mathbb {G}, \mathbb {G}_T, p, \textsf{nMAP}, g)$ with multilinear map $\textsf{nMAP}$, if for all adversaries running in probabilistic polynomial time t, it holds that

$$ \left| \Pr \left[ \mathcal {A} (g,g^a, \textsf{nMAP}(g, \ldots , g )^{a^{n+1}}) = 1 \right] - \Pr \left[ \mathcal {A} (g, g^a, R) = 1\right] \right| \le \epsilon _{\textsf{nMDDH}}, $$

where $(g, a, R) {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {G}\times \mathbb {Z}_p \times \mathbb {G}_T$.

With the following lemma, the complexity of $\textsf{nEMDDH}$ can be demonstrated.

Lemma 1

If the $\textsf{nMDDH}$ problem is $(t,\epsilon _{\textsf{nMDDH}})$-hard in $\textsf{GP}$, then the n-Exponent multilinear decisional Diffie-Hellman ($\textsf{nEMDDH}$) problem is $(t_e,\epsilon _{\textsf{nEMDDH}})$-hard in $\textsf{GP}$, where $t_e \approx t$, $\epsilon _{\textsf{nMDDH}} = \epsilon _{\textsf{nEMDDH}}$.

Proof

Let $\mathcal {A}_{\textsf{nEMDDH}}$ be a ${\textsf{nEMDDH}}$ adversary. We show how to construct another adversary $\mathcal {B}$ against the $\textsf{nMDDH}$ problem instance $(\mathbb {G}, \mathbb {G}_T, p, \textsf{nMAP}, g, g^a, R)$, with $R = \textsf{nMAP}(g,g)^{a^{n+1}}$ or $R {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {G}_T$.

After receiving its own challenge $\mathcal {B}$ first chooses $c {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {Z}_p$ and sets implicitly $b = a\cdot c$ and then computes

$$R' = R^c,\ g^b = g^{ac} = (g^a)^c $$

$\mathcal {B}$ outputs whatever $\mathcal {A}_{\textsf{nEMDDH}}$ outputs on $(\mathbb {G}, \mathbb {G}_T, p, \textsf{nMAP}, g, g^a, g^b, R')$.

It is obvious that $\mathcal {B}$ runs in time $t_e \approx t$, if the exponentiation is efficient in $\textsf{GP}$.

Note that since c is uniformly random in $\mathbb {Z}_p$, so is $g^b = (g^a)^c$ in $\mathbb {G}$. Moreover, if $R = \textsf{nMAP}(g,g)^{a^{n+1}} = \textsf{nMAP}(g,g)^{a^{n}a}$, then $R' = R^c = (\textsf{nMAP}(g,g)^{a^{n}a})^c = \textsf{nMAP}(g,g)^{a^{n}\cdot ac} = \textsf{nMAP}(g,g)^{a^{n}\cdot b}$. Otherwise, $R'$ remains uniformly random in $\mathbb {G}_T$. Therefore, $\mathcal {B}$ has generated perfectly an ${\textsf{nEMDDH}}$ instance for $\mathcal {A}_{\textsf{nEMDDH}}$ and $\epsilon _{\textsf{nMDDH}} = \epsilon _{\textsf{nEMDDH}}$.

B Cases in Game 2 in the Proof of Theorem 1

In game 2, we prove the claim by constructing a $\textsf{nEMDDH}$ adversary $\mathcal {B}$ with advantage $\epsilon$ calling $\mathcal {A}$ as a sub-procedure. Let $(g, g^a, g^b, R) \in \mathbb {G}^3 \times \mathbb {G}_T$ be $\mathcal {B}$’s inputs, where $a, b \in \mathbb {Z}_p$. $\mathcal {B}$’s goal is to determine if $\textsf{nMAP}(g, \ldots , g )^{a^nb} = R$. To set up the $\textsf{GNIKE}$ instance, $\mathcal {B}$ as a challenger runs $\mathsf {GNIKE.Setup}(1^\kappa )$ to generate the system parameters, including a chameleon key pair $\textsf{CHAMKey}=(\textsf{p}, \mathsf {\tau })$ and the groups with $\textsf{nMultilinear}$ map $\textsf{MG}$. It then randomly selects $s_{\hat{A}_1}, \ldots , s_{\hat{A}_n} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\{0, 1\}^*$ and $r_{\hat{A}_i}, \ldots , r_{\hat{A}_i} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {R}_{\textsf{CH}}$.

Let p(t) = $\prod ^n_{i=0}(t-t_{\hat{A}_i})^i$ = $\varSigma ^{n}_{i=0} p_{i}t^i$ = $p_{0} + p_{1}{t} + \ldots + p_{n}{t^n}$ be a polynomial of degree n over $\mathbb {Z}_p$, where $t_{\hat{A}_i} :=$ $\textsf{H}_{\textsf{p}}(s_{\hat{A}_i}, r_{\hat{A}_i})$. Next, a polynomial of degree n, q(t) = $\varSigma ^{n}_{i=0} q_{i}t^i$ = $q_{0} + q_{1}{t} + \ldots + q_{n}{t^n}$ is randomly selected over $\mathbb {Z}_p$. Consequently, $\mathcal {B}$ selects random values $\gamma _1, \gamma _2$, uniformly in $\mathbb {Z}^*_p$, sets then $\varPhi = (g^a)^{\gamma _1}g^{\gamma _2}$, $u_{i}=(g^{a})^{p_i}g^{q_{i}}$ for $0 \le i \le n$ and $S = g^b$. Since $q_{i} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {Z}^*_p$, we have $u_{i} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {G}$. Observably, $u_{0}\ldots u_{n}^{t^n} = (g^{a})^{p(t)}g^{q(t)}$. $\mathcal {B}$ then returns the public parameters $(\textsf{MG},\{u_i\}_{0 \le i\le n}, \varPhi , S, \textsf{p})$ to $\mathcal {A}$ to finish the set up phase. Thereafter, $\mathcal {B}$ answers the queries from $\mathcal {A}$ in the following ways.

• $\textsf{RegisterHonestUID}(\textsf{ID}_{\hat{A}_i})$: $\mathcal {A}$ supplies an identity $\textsf{ID}_{\hat{A}_i}$ ($i \in [n]$) to be registered as honest. To answer this query, B selects $\alpha _i, \beta _i {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {Z}_p$, computes $Z_{\hat{A}_i} = (g^a)^{\alpha _i}g^{\beta _i}$. With the trapdoor key $\mathsf {\tau }$, $\mathcal {B}$ can extract $r_{\hat{A}_{i, ch}}$, such that

  $$\textsf{H}_{\textsf{p}}(Z_{\textsf{ID}_{\hat{A}_i}} || \textsf{ID}_{\hat{A}_i}, r_{\hat{A}_{i, ch}}) = \textsf{H}_{\textsf{p}} (s_{\hat{A}_i}, r_{\hat{A}_i}) = t_{\hat{A}_i}. $$

  $\mathcal {B}$ then computes $X_{\textsf{ID}_{\hat{A}_i}}$ = $[(g^{a})^{p(t_{\hat{A}_i})}g^{q(t_{\hat{A}_i})}]^{a\alpha _i+\beta _i}$ = $[(g^{a})^{0}g^{q(t_{\hat{A}_i})}]^{a\alpha _i+\beta _i}$ = $(g^{q(t_{\hat{A}_i})})^{a\alpha _i+\beta _i}$ = $(g^a)^{\alpha _iq(t_{\hat{A}_i})}g^{\beta _iq(t_{\hat{A}_i})}$. Finally, $\mathcal {B}$ returns the public key $pk_{\textsf{ID}_{\hat{A}_i}}$ = ($Z_{\hat{A}_i}$, $X_{\hat{A}_i}$, $r_{\hat{A}_{i, ch}}$) to $\mathcal {A}$.

• $\textsf{RegisterCorruptUID}(\textsf{ID}_{\mathcal {A} _i},pk_{\textsf{ID}_{\mathcal {A} _i}})$: Upon receiving a public key $pk_{\textsf{ID}_{\mathcal {A} _i}}$ and an identity $\textsf{ID}_{\mathcal {A} _i}$ from $\mathcal {A}$. The public key $pk_{\textsf{ID}_{\mathcal {A} _i}}$ is registered as corrupt if $\textsf{ID}_{\mathcal {A} _i}$ has not been registered before.

• $\textsf{RevealCorruptKey}$: $\mathcal {A}$ supplies two sets of identities $IDS_{\mathcal {A}}$ and $IDS_{H}$: $IDS_{\mathcal {A}}$ = $\{ \textsf{ID}_{\mathcal {A} _1}, \ldots , \textsf{ID}_{\mathcal {A} _{l_1}} \}$ denoted here as corrupt and $IDS_{H}$ = $\{$ $\textsf{ID}_{H_1}$, $\ldots$, $\textsf{ID}_{H_{l_2}}$ $\}$ as honest and $l_1 + l_2 = n^*$.

  • Case 1 ($n^* = n$), where n is the upper bound on the size of the group: For this query at least one of the identities supplied by $\mathcal {A}$ was registered as honest ($1 \le l_2 < n$), and all identities supplied by $\mathcal {A}$ must be unique. $\mathcal {B}$ then checks the public key of any corrupt identity in $IDS_{\mathcal {A}}$ using the multilinear equations to confirm that $pk_{\textsf{ID}_{\mathcal {A} _i}}$ is of the form ($Z_{\textsf{ID}_{\mathcal {A} _i}}$, $a_{\textsf{ID}_{\mathcal {A} _i}}$, $r_{\textsf{ID}_{\mathcal {A} _i}}$), where $Z_{\textsf{ID}_{\mathcal {A} _i}}$ = $g^{a_{\textsf{ID}_{\mathcal {A} _i}}}$ and $a_{\textsf{ID}_{\mathcal {A} _i}}$=$Y_{\textsf{ID}_{\mathcal {A} _i}}^{a_{\textsf{ID}_{\mathcal {A} _i}}}$ = $[(g^a)^{p(t_{\textsf{ID}_{\mathcal {A} _i}})}g^{q(t_{\textsf{ID}_{\mathcal {A} _i}})}]^{a_{\textsf{ID}_{\mathcal {A} _i}}}$. If the check fails, $\mathcal {B}$ rejects this query. $\mathcal {B}$ then computes the corresponding shared key $K_{IDS_{\mathcal {A}},IDS_{H}}$ as follows:

    $*$:

    $t_{\textsf{ID}_{\mathcal {A} _i}}$ = $\textsf{H}_{\textsf{p}}(Z_{\textsf{ID}_{\mathcal {A} _i}} || \textsf{ID}_{\textsf{ID}_{\mathcal {A} _i}}, r_{\textsf{ID}_{\mathcal {A} _i}})$, where $i \in [l_1]$,

    $*$:

    computes $p(t_{\textsf{ID}_{\mathcal {A} _i}})$ and $q(t_{\textsf{ID}_{\mathcal {A} _i}})$ using the polynomials p(t) and q(t)³,

    $*$:

    $\{[a_{\textsf{ID}_{\mathcal {A} _i}}]/ [Z_{\textsf{ID}_{\mathcal {A} _i}}^{q(t_{\textsf{ID}_{\mathcal {A} _i}})}]\}^{p(t_{\textsf{ID}_{\mathcal {A} _i}})^{-1}}$

    = $\{[(g^a)^{p(t_{\textsf{ID}_{\mathcal {A} _i}})}g^{q(t_{\textsf{ID}_{\mathcal {A} _i}})}]^{a_{\textsf{ID}_{\mathcal {A} _i}}}/ [(g^{a_{\textsf{ID}_{\mathcal {A} _i}}})^{q(t_{\textsf{ID}_{\mathcal {A} _i}})}]\}^{p(t_{\textsf{ID}_{\mathcal {A} _i}})^{-1}}$ = $(g^a)^{a_{\textsf{ID}_{\mathcal {A} _i}}}$,

    $*$:

    $Z_{\textsf{ID}_{\mathcal {A} _{i}}}^*$ = $[(g^a)^{a_{\textsf{ID}_{\mathcal {A} _i}}}]^{\alpha _i}$ $(Z_{\textsf{ID}_{\mathcal {A} _i}})^{\beta _i}$ = $(g^a)^{a_{\textsf{ID}_{\mathcal {A} _i}}{\alpha _i}}$ $(g^{a_{\textsf{ID}_{\mathcal {A} _i}}})^{\beta _i}$ = $(g^{a_{\textsf{ID}_{\mathcal {A} _i}}})^{({a \alpha _i} + {\beta _i})}$ = $Z_{\textsf{ID}_{\mathcal {A} _i}}^{({a \alpha _i} + {\beta _i})}$

    $*$:

    the shared key $K_{IDS_{\mathcal {A}},IDS_{H}}$⁴:

    $$\begin{aligned} \textsf{nMAP}(&Z_{\textsf{ID}_{\mathcal {A} _1}},\ldots ,Z_{\textsf{ID}_{\mathcal {A} _{i-1}}},Z_{\textsf{ID}_{\mathcal {A} _{i}}}^*,\\&Z_{\textsf{ID}_{\mathcal {A} _{i+1}}} \ldots ,Z_{\textsf{ID}_{\mathcal {A} _{l_1}}},Z_{\textsf{ID}_{H_{1}}},\ldots ,Z_{\textsf{ID}_{H_{i-1}}},Z_{\textsf{ID}_{H_{i+1}}},\ldots ,Z_{\textsf{ID}_{H_{l_2}}},S) \end{aligned}$$

  • Case 2 ($2 \le n^* < n$): $\mathcal {B}$ proceeds as the same as case 1 mentioned above. For this case $\mathcal {B}$ firstly adds $\varPhi$ as padding for ($n - n^*$) times in the following $\textsf{nMAP}$ equation, computes then the corresponding shared key $K_{IDS_{\mathcal {A}},IDS_{H}}$ as follows:

    $*$:

    the shared key $K_{IDS_{\mathcal {A}},IDS_{H}}$⁵ is computed as

    $$\begin{aligned} \textsf{nMAP}(&\ldots ,Z_{\textsf{ID}_{\mathcal {A} _{i-1}}},Z_{\textsf{ID}_{\mathcal {A} _{i}}}^*,Z_{\textsf{ID}_{\mathcal {A} _{i+1}}},\ldots ,Z_{\textsf{ID}_{\mathcal {A} _{l_1}}},Z_{\textsf{ID}_{H_{1}}},\ldots ,Z_{\textsf{ID}_{H_{i-1}}},\\&Z_{\textsf{ID}_{H_{i+1}}},\ldots ,Z_{\textsf{ID}_{H_{l_2}}},\underbrace{\varPhi ,\ldots ,\varPhi }_{{(n - n^*) }}, S) \end{aligned}$$

• $\textsf{Test}$: Assume $R =\textsf{nMAP}(g,\ldots ,g)^{a^n b}$. $\mathcal {A}$ supplies $n^*$ identities ($\textsf{ID}_i, i \in [n^*]$) that were registered as honest.

  • Caes 1 ($n^* = n$): $\mathcal {B}$ computes

    $$\begin{aligned} K_b&= \textsf{nMAP}(g, \ldots , g)^{(\varPi _{i=1}^{n^*}(a\alpha _i+\beta _i))b} \\&= \textsf{nMAP}(g, \ldots , g)^{(\sum _{k=0}^{n^*}\psi _k a^k)b} \\&= \textsf{nMAP}(g, \ldots , g)^{(a^nb\varPi \alpha _i)+(\sum _{k=0}^{(n^*-1)}\psi _k a^k)b} \\&= R^{\varPi \alpha _i} \textsf{nMAP}(g, \ldots , g)^{\sum _{k=0}^{(n^*-1)}(\psi _k a^k)b}, \end{aligned}$$

    and returns $K_b$ to $\mathcal {A}$.

  • Case 2 ($2 \le n^* < n$): $\mathcal {B}$ computes

    $$\begin{aligned} K_b&=\textsf{nMAP}(g, \ldots , g)^{(\varPi _{i=1}^{n^*}(a\alpha _i+\beta _i))\overbrace{(\varPi _{i=(n^*+1)}^{n}(a\gamma _1 + \gamma _2))}^{\varPhi \ padding} b} \\&=\textsf{nMAP}(g, \ldots , g)^{(\sum _{k=0}^{n}\psi _k a^k)b}\\&= \textsf{nMAP}(g, \ldots , g)^{(a^nb\psi _n)+(\sum _{k=0}^{(n-1)}\psi _k a^k)b}\\&= R^{\psi _n} \textsf{nMAP}(g, \ldots , g)^{\sum _{k=0}^{(n-1)}(\psi _k a^k)b}, \end{aligned}$$

    and returns $K_b$ to $\mathcal {A}$.

  • Finally, when $\mathcal {A}$ terminates by outputting a bit b, then $\mathcal {B}$ returns the same bit to $\textsf{nEMDDH}$ challenger.

In each case of the $\textsf{Test}$ query, the right side of the last equality is how $\mathcal {B}$ can compute $K_b$. According to other equalities, $\mathcal {B}$ can compute the real shared key if $R = \textsf{nMAP}(g,\ldots , g)^{a^n b}$ holds, with known values of R, $\alpha _i$, $\beta _i$, $\gamma _1$ and $\gamma _2$. This is exactly as in game $\mathsf {G^{}_{1}}$. On the other hand, if R is random, $\mathcal {B}$ will output an independent random value in $\mathbb {G}_T$. This is exactly as in game $\mathsf {G^{}_{2}}$.