Keywords

1 Introduction

In recent decades, as electronic communications and information systems become more and more complicated, applications, such as video- or tele-conferencing involving multiple participants, are widespread throughout the Internet. In order to satisfy the requirement of secure communication channels within the insecure public network, it is necessary to design authenticated key exchange protocols for groups of principals.

To date, a collection of schemes has been designed elegantly. Bresson, et al. [10] is the first to usher in a formal model of security for group key exchange protocols, and the first to give a concrete scheme with a rigorous proof. However, in their protocol, the number of communication rounds depends upon the number of group members, so that this construction is impractical in the situation where the number of players is very large. Fewer rounds generally mean easier implementation and more effective reducing to synchronization problems. Subsequent to their work, several solutions [8, 24] to constant-round protocol for group key exchange are provided and proven secure in formal models. In addition, the desirable security goals of this kind of protocol not just focus on resistance against the outsider adversary who lies outside of the target group and seeks to get any information about the session key with observing and modifying protocol messages. Additionally, a certain degree of security properties against malicious insiders are expected in the designs of protocols. In Katz and Shin’s work [23], they define the insider security for group key exchange protocols: one prevents the adversary from determining the session key entirely, unless at least there exists one corrupted party in the group.

Many schemes, including ones mentioned above, relies on possession of shared keys with other peers or authentic public/private pairs. In some scenarios, passwords, the ubiquitous keys to on-line communications, are the proper alternative in the group key exchanges, which benefits from password’s convenience and low-cost. Namely, in the password-authenticated group key exchange (GPAKE), members only share a low-entropy password that can be reliably remembered by humans to bootstrap a high-entropy session key. Compared with other group key exchange protocols, GPAKEs, as password-based protocols, bear additional vulnerabilities to off-line dictionary attacks and the inevitable on-line dictionary attacks because of relatively small dictionary space. Thus, how to resist off-line attacks and restrict to adversaries eliminating at most one password per party instance, is also the basic security requirement in designing password-authenticated group key exchange protocols.

The first solution to the GPAKE is proposed by Bresson et al. [9]. Still, their protocol’s round complexity is related to the number of group users. Abdalla et al. [1, 4] demonstrate the first password-based group key exchange protocols in a constant number of rounds, in the random oracle /ideal cipher models [7, 25], and in the standard model, respectively. Later, they give provably secure schemes [2, 3] universal composability (UC) framework [15]. Recently, Xu et al. [27] present an one-round scheme in the standard model, using indistinguishability obfuscation as the main tool. Specifically, the works of [2, 3] achieve a strong notion of (t, n)-contributiveness which captures that no adversary can bias the key if no more t players in the group of n players have been corrupted.

These schemes have shown important outcomes in GPAKE, yet much work remains to be done to enhance the efficiency and practicality of existing schemes. We focus on how to realize as few rounds as possible for the design of GPAKE scheme, without the expense of desirable security involved in the preceding description.

1.1 Our Contributions

In this literature, we put forward a UC-secure solution for password-authenticated group key exchange protocol against the static adversary in the password-only model, where the players do not have public keys authenticated by a certificate authority, pre-shared symmetric keys or other auxiliary equipments.

In the aspect of security models, this scheme is provably secure in the UC framework by the help of random oracles under the one-more gap Diffie-Hellman assumption. Compared with the game-based security models, such as [6, 9], not only does the UC framework inherently provide the secure composition property, but it also has conspicuous advantages in distribution of passwords. Specifically, UC framework brings about strong composability properties: (1) UC-secure protocols remain secure even if many protocol instances (may be various kinds protocols) execute concurrently, and (2) The powerful universal composition theorem guarantees that they can be securely used as sub-routine protocols of other UC protocols. Besides, rather ideal assumptions on passwords independently chosen from pre-determined dictionary space in the game-based models, UC framework designates the environment (i.e. the distinguisher) to provide passwords to parties, which models arbitrary distributions and dependencies between passwords. Thereout, it captures the cases in real-life settings where the honest parties with incorrect but related passwords interacts with others—when a user obliviously makes typos.

Furthermore, we incorporate the full-contributiveness property (or called as (n, n)-contributiveness) into our rewritten ideal functionality for GPAKE, which means that the adversary cannot bias the key if there exists at least one honest player in the group, while our scheme has proven to be capable of realizing it. In fact, the notion of contributiveness brings several advantages in group key exchange protocols. First, it pledges each party equally contributes to the session key, which makes one intuitively feel that key agreement is “fairer” than key distribution. Second, it still results in high quality random keys even though some malicious parties improperly choose their contributions. Third, it deters the case where the insider adversary determinates session keys to specific values known by an outsider adversary in advance, so that the latter can eavesdrop on the later communications without the former’s direct divulging to them. To a certain degree, the destructibility of the insider adversary is decreased.

Table 1. Comparison of GPAKE schemes
Full size table

An important measure of a protocol’s efficiency is the communication complexity (number of protocol rounds) of the given protocol. Our protocol achieves the properties above with only two rounds. It distinctly has better performance on round complexity than the other UC-secure ones [2, 3]. On the minus side, our scheme also has to perform \(O(\mathrm{n})\) exponent calculations per member. However, according to the Moore’s laws which declare the computing power grows faster than communication power, it is therefore an acceptable and reasonable compromise trade communication power for computing power in a group key exchange protocol. Comparison of some existing schemes for GPAKE is shown in Table 1.

2 Security Definitions

In this section, we will begin by reviewing the UC framework and the general split functionality. Then a detailed description of the ideal functionality for the password-authenticated group key exchange and related discussion are followed.

2.1 Universal Composability Framework

Universal composability [15] is the definition of secure computation that considers an execution of a protocol in the setting involving an environment \(\mathcal {Z}\), an adversary and parties. This framework involves two worlds—the real world and the ideal world. \(\mathcal Z\)’s aim is to distinguish two worlds. For it, the environment provides the inputs to the parties and observes their outputs. On one hand, as usual, the real world consists of participants of the protocol and an adversary \(\mathcal A\) that controls the communication channel and potentially attacks protocols. On the other hand, in the ideal world, there exists an entirely trusted entity \(\mathcal F\) called ideal functionality, and dummy participates of the target protocol simply hand their inputs to \(\mathcal F\). The ideal adversary \(\mathcal S\) directly interacts with \(\mathcal F\), and their communication essentially models the information it can obtain and its abilities to attack the protocols. Namely, the functionality describes the security goals we expect. Intuitively, the adversary, with a variety of means of attacks, should not learn more information than the functionality’s outputs to it. Thus, security requires that, for any adversary \(\mathcal {A}\) attacking a protocol \(\rho \), there exists an ideal adversary \(\mathcal {S}\) such that no environment \(\mathcal {Z}\) can distinguish the case that it is interacting with \(\mathcal {A}\) and parties in the real world, and the case which it is interacting with \(\mathcal {S}\) and a functionality \(\mathcal F\) in the ideal world. If so, we say that \(\rho \) UC-realizes \(\mathcal {F}\). From the point of view of the environment, the real-world protocol is at least as secure as the ideal-world one. In particular, the universal composability theorem guarantees that the protocol \(\rho \) continues to behave like the ideal functionality \(\mathcal {F}\) even if it is executed in an arbitrary network environment. The complete details refer to [15].

Fig. 1.
figure 1

The split version of ideal functionality \({\mathcal F}\)

Full size image

2.2 Split Functionalities

In a network, without any authentication mechanism, an adversary of the network can simply “disconnect” the parties completely, and engage in separate executions with the other parties on behalf of the honest ones. Such an attack is inevitable. Players cannot distinguish the case in which they interact with the expected ones from the case where they interact with the adversary. Hence, in the work of [5], Barak et al. propose a new model based on split functionalities which guarantees that this attack is the only one available to the adversary.

The split functionality is a generic construction based upon a normal ideal functionality \(\mathcal F\). Its formal description can be found on Fig. 1. It models security by allowing the adversary to carry out such an “attack” in the ideal world. In the initialization stage, the adversary adaptively chooses subsets of the honest parties’ \(\mathcal H\) under two constraints: (1) these subsets are disjoint; (2) the adversary must choose a unique session identifier \(sid_{\mathcal H}\) for each authentication set \(\mathcal H\). That is, the subsets create a partition of the players. During the computation stage of \(s\mathcal F\), each subset \(\mathcal H\) activates a different and independent instance of the ideal functionality \(\mathcal F\), denoted as \(\mathcal F^{\mathcal H}\). In each such execution, the parties \(P_i\in \mathcal H\) provide their own inputs, and the adversary \(\mathcal S\) provides the inputs for all \(P_i\notin \mathcal H\). Similarly, the parties \(P_i\in \mathcal H\) all receive their specified outputs as computed by their copy of \(\mathcal F\). However, the adversary receives all of its own outputs, as well as the outputs of the parties \(P_i\notin \mathcal H\) who are controlled by \(\mathcal S\). It’s important to note that there is no interaction between different instances of \(\mathcal F\) run by \(s\mathcal F\).

2.3 The Ideal Functionality for GPAKE

The formalized description of GPAKE’s ideal functionality \(\mathcal F_{\textsf {GPAKE}}\) is presented in Fig. 2. In order to reduce repeated representations, assume that the ideal functionality only takes notice of the first query or input for each sid and party, and subsequent ones for the same sid and party are straightly ignored. What’s more, the session identifier sid are considered to be globally unique so that several sessions running in parallel can be distinguished. Note that we take into account the static corruption—the adversary could selectively designate and corrupt some participants, but only prior to the beginning of a protocol instance. From the corruption on, it not only obtains their inputs resulted from \(\mathcal Z\), and also fully controls their behaviors in the following executions.

In the ideal world, the functionality \(\mathcal F_{\textsf {GPAKE}}\) interacts with an adversary \(\mathcal S\) (i.e. the simulator), n parties \(P_1,\ldots ,P_n\) and the environment \(\mathcal Z\) (through the parties). Before beginning, \(\mathcal Z\) chooses the passwords \(pw_i\) (may be unequal) on its own for participants, which captures the arbitrary password distribution, including the case of making typos. As a bonus, this approach provides forward secrecy for free, which preserve the security of session keys even if the password is used for other purposes.

Fig. 2.
figure 2

The ideal functionality \(\mathcal F_{\textsf {GPAKE}}\)

Full size image

Though such a query \((\mathsf{NewSession},sid,P_i,pw_i)\), every party initiates a new session with the expected ones in the group \(\mathcal H\). Then \(\mathcal F_{\textsf {GPAKE}}\) is triggered to create the corresponding records, such as \((sid, P_i,pw_i)\), for them to store their inputs locally, and labeled it as \(\mathsf{fresh}\). Actually, among these group members, some may be impersonated or corrupted by the adversary S to take part in the protocol instance with \(\mathcal S\)’s own password attempt. In both cases, the records are marked as \(\mathsf{corrupted}\). Once all the parties in the group \(\mathcal H\) have sent \(\mathsf{NewSession}\) queries, the ideal functionality \(\mathcal F_{\textsf {GPAKE}}\) stores a record \((sid,\mathcal H,{\textsf {ready}})\), and informs the adversary \(\mathcal S\) with it as a notification. When the adversary \(\mathcal S\) commences with impersonating a party \(P_i\) with the \(\mathsf{NewSession}\) query, it is allowed temporarily to submit a character \(\bot \) instead of the password, and replenish it before sending the corresponding \(\mathsf{NewKey}\) query. This stipulation contributes to a more smooth simulation in the security proof. In principle, after this phase, the parties basically wait for receiving the session keys.

When receiving \(({\textsf {NewKey}},sid,P_i,\mathcal H^*,sk^*)\) query from the adversary \(\mathcal S\), the ideal functionality \(\mathcal F_{\textsf {GPAKE}}\) is instructed to release the session key to \(P_i\). Note that \(\mathcal H^*\) is the set of participants that is specified by the adversary and may not be equal to \(\mathcal H\) in the \(\mathsf{NewSession}\) queries. When \(\mathcal H=\mathcal H^*\), the computation happen within pre-assigned members, while \(\mathcal H\ne \mathcal H^*\) means that the adversary introduces outsiders (may be fictional entities) into the group to replace some honest ones. The latter case is forbidden in our definition. Besides, if there no exists a \(\mathsf{ready}\) record for \(\mathcal H^*\), i.e. members of \(\mathcal H^*\) do not entirely join this session, \(\mathcal F_{\textsf {GPAKE}}\) also abort this execution. Unlike previous key exchange functionalities [16, 23], in that if one of NewSession records is corrupted the adversary is given the ability to fully determine the resulting session key into \(sk^*\), ours deprives of this ability of \(\mathcal S\) unless all parties are corrupted simultaneously. By this definition, we integrate the full-contributiveness property in the functionality. Participants shall share the same, uniformly distributed session keys with whom have the matching password. Namely, \(\mathcal F_{\textsf {GPAKE}}\) has to traverse the records and the session keys sent to some parties, and return the corresponding ones. If no one is found out, \(\mathcal F_{\textsf {GPAKE}}\) chooses a random value from the range of session keys. In consideration of implicit authentication, the protocol will not end up with the case where no key is established for parties unless the inevitable abortions occur.

When \(\mathcal F_{\textsf {GPAKE}}\) outputs the session key to the specified party, the corresponding NewSession record is marked as completed to avoid undesired on-line guessing attacks from \(\mathcal S\) even after the authentication has ended.

2.4 Discussions

For the completeness of the ideal functionality, the adversary \(\mathcal S\) should be acquiescently allowed to abort the instance at any time to capture some trivial cases. For instance, in the real network, the attackers can always delay, hijack messages or revise them into irregular formats in the communication channel, resulting in a failed session among parties.

In our context of the ideal functionality \(\mathcal F_{\textsf {GPAKE}}\), the \(\mathsf{TestPwd}\) query is completely abandoned, since split functionality has modeled the adversary’s active attacks which enable it to take apart in the group. In the view of security analysis, the simulator does have to learn the results whether the passwords are matching, which is totally left to the functionality along with generation of session keys. Moreover, an outsider should not get the final results of protocol executions without the later communications in realistic scenarios.

In the UC framework, as per the formalism of [15], assume that multiple protocol instances are running concurrently. As the case in the real world, numerous execution instances often invoke the same common random strings or random oracles. Roughly, we have to consider the multi-session extension \({\widehat{\mathcal F}}\) through the JUC theorem [18]. We refer to [16, 18] for more discussions.

3 Our GPAKE Scheme

The basic idea of this protocol is inspired by Jarecki et al’s (verifiable) oblivious pseudorandom functions (V-OPRF) in [21, 22] and Camenisch et al’s constructions for distributed password verification protocol of [12], and then utilized to build our GPAKE scheme. Briefly, each participant \(P_i\in \{P_1,\ldots ,P_n\}\) has the shared password \(pw_i\), along with its own ephemeral secret key \(x_i\). The session key computed by parties for session and sub-session identifiers sid, ssid is \(H_2(sid,ssid,H_1(sid,pw_i)^X)\), where \(X=\sum ^n_{i=1}x_i~\mathrm{mod}~q\), and \(H_1,H_2\) are hash functions. In order to get this value, each party chooses \(r_i\leftarrow _\mathrm{R}\mathbb Z_q^*\) to blind the password hash \(a_i:=(H_1(sid,pw_i))^{r_i}\) and sends the result to the others. When \((b_{i,j}:=a_i^{x_j})_{j\in [n],\,j\ne i}\) are returned, it can compute \(v_i:=(a_i^{x_i}\cdot \begin{matrix} \prod _{j=1,\,j\ne i}^n b_{j,i} \end{matrix})^{1/r_i}=H_1(sid,pw_i)^X\). Simultaneously, \(P_i\) proceed to the similar power operation to \(\{a_j\}_{j\ne i}\) from the others with its own secret key \(x_i\). Nevertheless, such simple proposition of GPAKE cannot reach the UC-security in the unauthenticated channel. Hence, we provide other primitives, such as the zero-knowledge proof of knowledge and the extra hash function to ensure the simulator that the participants always use the coincident public/secret keys, and also to help it extract the secret key for simulation. More details are presented as follows.

Fig. 3.
figure 3

The description of our GPAKE protocol for each party \(P_i\)

Full size image

3.1 Concrete Construction

Let \(\mathbb G\) be a multiplicative group of prime order q with the generator g generated through an algorithm of parameters generation by the security parameter \(\kappa \). The hash functions \(H_1:\{0,1\}^*\times \{0,1\}^*\rightarrow \mathbb G\), \(H_2:\{0,1\}^*\times {\mathbb G}\times {\mathbb G}\rightarrow \{0,1\}^{2\kappa }\) and \(H_3:\{0,1\}^*\times \{0,1\}^*\times {\mathbb G}\rightarrow \{0,1\}^{\kappa }\) are modeled as random oracles. The public parameters also consist of the common random strings \(\mathsf{crs}\) for the zero-knowledge proofs of knowledge. \(\mathsf{PK}\) denotes the non-interactive proof of knowledge (which is formally defined by Camenisch et al. [11, 14]), showing \(y_i=g^{x_i}\wedge (b_{i,j}=a_j^{x_i})_{j\in [n],\,j\ne i}\).

Assume that the actual members are known in advance, and we simply denote them as \(P_1,\ldots ,P_n\) according to a certain order. In a protocol instance, the parties communicate over an unauthenticated broadcast channel, where messages can be arbitrarily observed, modified, and delayed by the adversary \(\mathcal A\). Particularly, the adversary can corrupt or impersonate the valid ones to join the group as an insider with its own password attempt.

When a protocol execution begins, each party randomly chooses a blinding factor \(r_i\) and ephemeral secret key \(x_i\) from \(\mathbb Z^*_q\), and then generates the blinded password hash \(a_i:=(H_1(sid,pw_i))^{r_i}\) and the ephemeral public key \(y_i:=g^{x_i}\), respectively. By the end of this round, it computes a hash to the values \(a_i\) and \(y_i\), i.e. \(h_i:=H_2(sid,a_i,y_i)\). Then each party broadcasts \(\left\langle P_i,a_i,h_i\right\rangle \) to others. Note that the sub-session identifier is defined as messages received in this round \(ssid:=a_1,h_1||\ldots ||a_n,h_n\), which be included in the subsequent hash evaluations. Specifically, it means that parties are partitioned by the shared messages among them. The purpose of usage of \(H_2\) is, during the formal security proof, to embed the one-more gap Diffie-Hellman problem in the next round rather than this round when the group has not partitioned by the adversary yet (Fig. 3).

In the second round, each party computes blinded responses \(b_{i,j}:=a_j^{x_i}\) for the others in this group using its ephemeral secret key \(x_i\). Moreover, it is required to generate a non-interactive zero-knowledge proof of knowledge \(\mathsf{PK}\) that \(b_{i,j}\) is generated correctly using \(y_i\)’s discrete logarithm. That is,

$$\pi _i:=\mathsf{PK}\{x_i:y_i=g^{x_i}\wedge (b_{i,j}=a_j^{x_i})_{j\in [n],\,j\ne i}\}$$

Note that these zero-knowledge proofs should be on-line extractable, since the simulator \(\mathcal S\) needs to extract the adversary’s ephemeral secret keys to obtain the solutions to the one-more gap Diffie-Hellman problem in the simulation of random oracle \(H_3\). It ends this round communication with broadcasting the message \(\left\langle P_i,y_i,(b_{i,j})_{j\in [n],\,j\ne i},\pi _i\right\rangle \) to the other participants.

In the end, the parties check the hash values and the proofs of knowledge. As soon as a value received by \(P_i\) doesn’t be verified correctly, it aborts this instance and outputs nothing. Otherwise, it computes the key material \(v_i:=(a_i^{x_i}\cdot \begin{matrix} \prod _{j=1,\,j\ne i}^n b_{j,i} \end{matrix})^{1/r_i}\) and the session key \(sk_i:=H_3(sid,ssid,pw_i,v_i)\), outputs (sid, ssid, sk), and terminates this session.

Throughout this scheme, the hash values in the first round and the proofs of knowledge play important roles in ensuring the full-contributory property. For the existence of hash values and proofs of knowledge, it is impossible for a malicious party \(P_i\) adaptively to choose its ephemeral secret key \(x_i\) after it gets \(\begin{matrix} \prod _{j=1,\,j\ne i}^n H_1(sid,pw_i)^{x_j} \end{matrix}\). Namely, even if there is only one honest party, the remaining \(n-1\) ones still cannot have the sum of secret keys depend on its.

Remarkably, this scheme achieves the implicit authentication by only two rounds communications among the participants. Using general techniques, such as the hash values of session key materials along with new tags, it is easy to get explicit authentication at the cost of one more round messages.

In the scheme, \(\mathsf{PK}\) is a non-interactive transformation of a proof of knowledge with the Fiat-Shamir heuristic [19] in the random oracle model. It can be extended to be online-extractable, by verifiably encrypting the witness with a public key defined in the common reference string. The witness can be extracted from the CRS by the simulator without rewinding by decrypting the ciphertext. A practical instantiation is given by the CPA-secure version of Camenisch and Shoup’s encryption scheme [13], which is secure under the DCR assumption [26].

4 Security Analysis

In this section, we prove the security of our scheme utilizing the (N, Q) one-more gap Diffie-Hellman assumption, which states that for the group \(\mathbb G\) there no exists polynomial-time adversary \(\mathcal A\) so that the following probability is non-negligible:

$$\mathsf{Prob}[{\mathcal A}^{(\cdot )^k,\mathsf{DDH(\cdot )}}(g,g^k,g_1,\ldots ,g_N)=\{(g_{j_s},g^k_{j_s})|s=1,\ldots ,Q+1\}]$$

where \(k\in \mathbb Z_q^*\) and Q is the number of the queries \(\mathcal A\) makes to the \((\cdot )^k\) oracle. Moreover, \(\mathcal A\)’s other inputs \(g_1,\ldots ,g_N\) are assumed to be sampled from \(\mathbb G\).

We can draw a conclusion for the GPAKE scheme in this theorem below:

Theorem 1

Under the one-more gap Diffie-Hellman assumption in \(\mathbb G\), if the zero-knowledge proofs involved are online extractable, then the password-authenticated group key exchange presented in Sect. 3 securely realizes \(\widehat{s\mathcal F}_\mathsf{GPAKE}\) under static corruptions in the \(({\mathcal F}_\mathsf{CRS},{\mathcal F}_\mathsf{RO})\)-hybrid model.

In order to prove this theorem, it is an ideal-world adversary (i.e. simulator) \(\mathcal S\) that needs to be constructed such that an arbitrary environment \(\mathcal Z\) cannot distinguish between protocol executions in the ideal world and ones in the real world, which is described in Sect. 4.1. Then, in Sect. 4.2, we demonstrate the indistinguishability between two worlds through a sequence of games.

4.1 Description of Simulator

The simulator \(\mathcal S\) not only interacts with the functionality \(\mathcal F_\mathsf{GPAKE}\) in the ideal world, but also acts as honest parties and environment \(\mathcal Z\) against a copy of the real-world adversary \(\mathcal A\) invoked by \(\mathcal S\) internally, and provide it a simulated real world. Moreover, \(\mathcal S\) faithfully forwards all messages between \(\mathcal A\) and \(\mathcal Z\).

Simulating Random Oracles and Common Random Strings. When the simulator receives the queries to random oracles \(H_1\), \(H_2\) and \(H_3\), it chooses random values from appropriate ranges to provide answers, and then records inputs and outputs. Here, \(\mathcal S\) is allowed to maintain a list \(\Lambda \) to store them, which is also helpful to ensure the consistency of simulated random oracles. The simulator answers \(\mathcal A\)’s queries and updates the lists according to the rules which are analogous to the description in Fig. 4. Particularly, the random oracle \(H_3\) is answered by the help of \(\mathsf{NewKey}\) queries in some points.

Furthermore, the simulated common reference string is chosen by \(\mathcal S\) for the adversary \(\mathcal A\) as \(\mathcal F_\mathsf{CRS}\) presented in the Appendix A.2. \(\mathcal S\) runs the initial simulator for proofs of knowledge and gets \((\mathsf{crs},\tau )\). \(\mathcal S\) sets the common reference string to \(\mathsf{crs}\) and locally stores \(\tau \) as the trapdoor for generating simulated \(\mathsf{PK}\)s and extracting the adversary’s witnesses.

Simulating the Party \({{\varvec{P}}}_{{\varvec{i.}}}\) Once receiving \((\textsf {Init},sid,P_i)\) and \((\mathsf{NewSession}, sid, P_i)\) from the functionality, the simulator \(\mathcal S\) randomly samples an element \(g_i\) from the group \(\mathbb G\), and then sets \(a_i:=g_i\), due to the fact that it has no access to the correct password for the honest party \(P_i\). And it randomly chooses the value \(h_i\) from \(\{0,1\}^*_{H_2}\). Such messages from honest participants are delivered to the adversary \(\mathcal A\) in the simulated real world.

The adversary \(\mathcal A\) can make its decision about the subgroups participants belong to, on account of lack of strong authentication assumptions. It sends the first flow to target parties on behalf of ones it wants to impersonate (or they have been corrupted since the beginning of the session). These subgroups \(\mathcal H\)s are defined according to the messages \((a_i,h_i)_{i\in [n]}\) in the first round. \(\mathcal S\) forwards these \(\mathcal H\)s, which make a partition of all parties, to the split functionality. Namely, the players in the same session receive and share the same \((a_i,h_i)_{i\in [n]}\). The simulator \(\mathcal S\) also sends \(\mathsf{NewSession}\) queries for the corrupted parties or ones in disguise correspondingly. Note that the simulator might have no knowledge about the latter’s passwords in this moment, and thus it has to pass \((\mathsf{NewSession},sid,P_j,\bot )\) for the dishonest party \(P_j\) to the ideal functionality instead. Moreover, we assume that the simulator is permitted to fill in the blanks later.

During the second round, on the behalf of honest parties, \(\mathcal S\) just follows the protocol description to send \(\left\langle P_i,y_i,(b_{i,j})_{j\in [n],\,j\ne i},\pi _i\right\rangle \) back to \(\mathcal A\) in the broadcast channel, where \(\pi _i\) is a simulated one, and \(H_2\) is programmed as \(h_i:=H_2(sid,a_i,y_i)\). Finally, \(\mathcal S\) makes a call \(({\textsf {NewKey}},sid,P_i,\bot )\) to \(\widehat{\mathcal F}_\mathsf{GPAKE}\).

To make the session keys indistinguishable in the view of \(\mathcal Z\), the simulator deals with \(\mathcal A\)’s queries \(H_3(sid,ssid,pw_j,v_j)\) for some party \(P_j\) as follows. If \(v_j\ne H_1(sid,pw_j)^{{\varSigma x^*_l}+{\varSigma x_k}}\), where \(x_k\) results from an honest party \(P_k\), while \(x^*_l\) is extracted from the proofs of knowledge provided by the dishonest one \(P_l\), \(\mathcal S\) just return a random value. Otherwise, \(\mathcal S\) fills the blank \(\bot \) in \(P_j\)’s \(\mathsf{NewSession}\) record with \(pw_j\), and sends \(({\textsf {NewKey}},sid,P_j,\bot )\) to \(\widehat{\mathcal F}_\mathsf{GPAKE}\), and then obtain sk. Finally, it sets \(H_3(sid,ssid,pw_j,v_j):=sk\) and output it to \(\mathcal A\).

4.2 Sequence of Games

Here, via a sequence of games \(\mathbf{G}_\mathsf{i}\), we will prove that the real world with the arbitrary \(\mathcal A\) and the ideal world with \(\widehat{\mathcal F}_\mathsf{GPAKE}\) and \(\mathcal S\) as defined above are indistinguishable in the view of environment \(\mathcal {Z}\). This needs to be stressed that, the simulator \(\mathcal S\) “magically” obtains the inputs of honest parties provided by \(\mathcal Z\) in the intermediate games, but they are no longer needed at the end of simulation. Following is the sequence of concrete games:

Game \(\mathbf{G}_\mathsf{0}\): Let \(\mathbf{G}_\mathsf{0}\) be the real-world game. As we noted above, the simulator \(\mathcal S\) “magically” receives inputs from \(\mathcal Z\), and just simply runs the real-world protocol executions for all the honest parties.

Game \(\mathbf{G}_\mathsf{1}\): It is identical to \(\mathbf{G}_\mathsf{0}\), except that we change the generation of \(\mathsf{crs}\) and proofs of knowledge in the protocol. More specifically, on one hand, the common random strings are replaced with the simulated ones, and \(\mathcal S\) knows the secret keys. On the other hand, whenever the honest parties perform the proofs of knowledge, \(\mathcal S\) provides the simulated ones instead. The indistinguishability between them follows from the zero-knowledge properties of the proof system.

Game \(\mathbf{G}_\mathsf{2}\): Since \(\mathbf{G}_\mathsf{2}\), \(\mathcal S\) begins to simulate the hash functions \(H_1\), \(H_2\) and \(H_3\) instead of the real ones. It is distinguishable with the previous game in the view of the environment \(\mathcal Z\), if there happen collisions that multiple inputs of oracles correspond to an output. Obviously, this case occurs with negligible probability, due to the birthday paradox.

Game \(\mathbf{G}_\mathsf{3}\): Let \(\mathbf{G}_\mathsf{3}\) be the modification of \(\mathbf{G}_\mathsf{2}\), where the honest party \(P_i\) replaces a normal \(a_i:=H_1(sid,pw_i)^{r_i}\) with a random element \(g_i\) from \(\mathbb G\) in the first round. Actually, in the previous game, \(r_i\) is randomly chosen from \(\mathbb Z_q^*\) by \(P_i\) locally without leakage to the adversary \(\mathcal A\). Therefore, \(H_1(sid,pw_i)^{r_i}\) cannot be distinguished from the random \(g_i\), from \(\mathcal Z\)’s view.

Game \(\mathbf{G}_\mathsf{4}\): Compared with \(\mathbf{G}_\mathsf{3}\), the simulator \(\mathcal S\) makes the party \(P_i\) output sk which \(\widehat{\mathcal F}_\mathsf{GPAKE}\) forwards to it after the \(\mathsf{NewKey}\) query, rather than the normal value \(H_3(sid,ssid,pw_i,v_i)\). Only by querying the \(H_3(\cdot )\) oracle can the environment distinguish between these two outputs. Concretely, When the adversary \(\mathcal A\) makes a query \((sid,ssid,pw_j,H_1(sid,pw_j)^{{\varSigma x^*_l}+{\varSigma x_k}})\), \(\mathcal S\) interacts with the functionality \(\widehat{\mathcal F}_\mathsf{GPAKE}\), and obtains the proper output value sk as the response. Besides, We define an event \(\varGamma \) that the adversary \(\mathcal A\) queries the oracle \(H_3(\cdot )\) on the input \((sid,ssid,pw_j,H_1(sid,pw_j)^{{\varSigma x^*_l}+{\varSigma x_k}})\) without communicating with some honest parties of \(\mathcal H\), which gives rise to an abort in \(\mathbf{G}_\mathsf{4}\), since \(\mathcal S\) has to send \(({\textsf {NewKey}},sid,P_j,\mathcal H^*,\bot )\) to the functionality, where \(\mathcal H^*\ne \mathcal H\). It is observed that, provided that the event \(\varGamma \) does not occur, the environment is not able to distinguish between two cases.

Here, by the help of reduction from the one-more gap Diffie-Hellman problem, we conclude that the event \(\varGamma \) just happens with a negligible probability. Given an instance of the one-more gap Diffie-Hellman problem \((Q,g,y=g^k,g_1,\ldots ,g_N)\), we revise the simulator’s behaviors as follows. Before the beginning, the simulator initializes a counter \(c(k):=0\) modeling the number of times that the \((\cdot )^k\) oracle is invoked and a set of pairs of the form \((z,z^k)\), where z is in \(\{g_1,\ldots ,g_N\}\), denoted as \({\mathcal T}(k):=\varnothing \). It uses the challenges \(g_1,\ldots ,g_N\) as the responses to \(H_1(\cdot )\) queries instead of random values from \(\mathbb G\), and as the value \(a_j\) for the honest party \(P_j\) to the other members in the first round.

In the second round, without loss of generality, assume that there exists s (\(s\ge 1\)) honest parities in the target group \(\mathcal H\), the simulator randomly samples \(s-1\) values from \(\mathbb Z_q^*\) and implicitly sets \(k_t=k-\sum ^{s}_{i=1,i\ne t}k_i\) for a honest party \(P_t\). Note that \(\mathcal S\) has no access to \(k_t\), but it still can provide the \(P_t\)’s ephemeral public key \(y_t:=y/(\prod ^{s}_{i=1,i\ne t}g^{k_i})\). If \(a_j\) is the first round message sent to \(P_t\), the simulator calls the \((\cdot )^k\) oracle to compute \(b_{t,j}:=a_j^k/(\prod ^{s}_{i=1,i\ne t}a_j^{k_i})\) and simulates the proof of knowledge \(\pi _t\) using the trapdoor \(\tau \) corresponding to the specified CRS. Moreover, once the oracle \((\cdot )^k\) is invoked, it increases the counter c(k). For the other honest ones, the simulations proceeds as before. When \(\mathcal A\) later queries \(H_2(sid,ssid,pw_i,v_i)\), the simulator invokes the DDH oracle to check whether it satisfies \(v_i=H_1(sid,pw_i)^{k+{\varSigma x^*_l}}\). If so, it adds \((H_1(sid,pw_i),v_i/H_1(sid,pw_i)^{\varSigma x^*_l})\) to the set \(\mathcal T(k)\). Once the event \(c(k)<|{\mathcal T(k)}|\), which the adversary never communicates with \(P_t\) since the end of the first round but submits an appropriate \(H_3\) query corresponding the solution, occurs, the simulator \(\mathcal S\) addresses the one-more gap DH problem by returning the set \(\mathcal T(k)\).

Now, the ideal-world is identical to \(\mathbf{G}_\mathsf{4}\), except that \(\mathcal S\) no longer owns the specified inputs from \(\mathcal Z\). Thus, the proof of theorem is completed.