# Cryptanalysis and Improvement of a Group Authentication Scheme with Multiple Trials and Multiple Authentications.

1. IntroductionAuthentication confirms whether some entity is who or what it claims to be. It is an important security service in cryptography and information security. Traditionally, the authentication process is carried out between two parties. The prover proves its identity to the verifier using a single or some combination of the following methods: something it has, something it knows, or something it is. The verifier will accept the proof if the prover, indeed, possesses the credential. However, this one-to-one authentication approach is inefficient in the group oriented environment, e.g., multicast/conference communications and broadroom elections [1,2]. If each user needs to authenticate every user's identity, a large number of authentication operations (quadratic to the number of users) need to be performed across the entire group. To address this problem, group authentication [3] has been proposed recently, so that instead of authenticating each user individually, all users in the group can be authenticated at once. If all users are legitimate group members, the group authentication is sufficient to prove that they all belong to the same group. Even if there exist some nonmembers, the group authentication still can be used as a preprocessing step before applying some traditional authentication techniques to identify those nonmembers.

In general, a group authentication scheme consists of two phases. In the initialization phase, the group manager (GM) generates a credential for each group member, and these credentials are sent through some secure networks. In the authentication phase, each player uses her credential to compute a token and broadcasts it. As follows, every user can use the revealed information to verify whether all these users are belonging to the same group. Two security requirements are fundamental for group authentication schemes. One is that if all users are legitimate group members, the authentication will always be successful. The other is that any nonmember with no valid credential cannot pretend to be a group member without being detected. Moreover, two other requirements are also highly desirable for group authentication schemes: (1) reuse of the credentials in multiple authentication sessions; (2) allowance of players to broadcast their tokens through asynchronous networks. Note that the first requirement helps to avoid the cumbersome processes of distributing credentials for every authentication session, and the asynchronous networks are easier to be established than the synchronous ones, especially in the distributed environment.

1.1. Our Contributions. In his work [4], Chien has proposed a group authentication scheme, claiming to satisfy the abovementioned requirements. In this paper, we first demonstrate that Chien's scheme fails to achieve its claimed security in the asynchronous networks. In particular, an adversary in the asynchronous communication model can always wait until the other legitimate users having revealed their tokens and then fabricate a valid token using the revealed ones. We then use a novel technique, called Anonymous Veto Networks (AV-net), to patch Chien's scheme. To avoid the "design-break-patch loop," our proposed scheme is rigorously analyzed in a well-defined security model [5].

1.2. Organization of the Paper. The rest of the paper is organized as follows. In Section 2, we briefly review some related works in the literature. Chien's scheme is described and analyzed in Section 3. In Section 4, we outline some preliminaries, including notations, building blocks, and security models. In Section 5, we introduce our improvement of Chien's scheme and analyze it with respect to security and efficiency. Finally, we conclude in Section 6.

2. Related Works

After the concept being initially introduced by Harn [3], group authentication has been widely accepted as a useful tool in cryptography to simultaneously prove that a group of users are all legitimate members [6]. Recently, a number of group authentication schemes have been proposed in the literature. For example, Chien [4] used a different mathematical structure to renovate Harn's scheme, with the purpose of allowing the credentials to be used in multiple trials in asynchronous networks. Liu et al. [7] considered the resource restrained environment and proposed a lightweight group authentication scheme in which the authentication is executed by checking whether the interpolation of the credentials returns a polynomial with the expected degree. Mahalle et al. [8] used the threshold Paillier cipher to design a group authentication scheme for the Internet of Things. Li et al. [9] extended the functionalities of group authentication so that not only the group members can be authenticated at once but also pairwise keys can be established among the group members. Guo et al. [10] and Elmouaatamid et al. [11] independently explored how to further trace the nonmembers if the group authentication fails.

However, a common drawback of these existing works is that their security is only justified using heuristic arguments rather than formal security proofs, and several of these schemes have already been found to contain security flaws. For example, Ahmadian and Jamshidpour [12] showed that Harn's scheme is insecure because an adversary in the asynchronous networks can impersonate a group member without being detected. In paper [3], Harn simply conjectured that the adversary needs to reconstruct all the polynomials to fabricate a valid token. But, this adversary may use a very novel method, called the linear subspace attack, to fabricate a valid token without recovering any of the polynomials. In their work [5], Xia et al. proposed a formal security model for group authentication that captures the main security requirements. This work has also improved Harn's scheme so that the modified scheme can be rigorously proved to achieve the desirable security properties.

In this paper, we first demonstrate that Chien's scheme is also insecure in the asynchronous networks. We then propose an improvement of Chien's scheme and prove its security using the security model in paper [5].

3. Analysis of Chien's Scheme

3.1. Description. Note that our description here is slightly different from Chien's original scheme [4]. We use a symmetric bilinear map in order to simplify the description, while Chien uses an asymmetric bilinear map. It is well known that compared with the symmetric bilinear map, the asymmetric one has advantages in security and bandwidth, but our attack against Chien's scheme also works when an asymmetric bilinear map is used instead.

We denote [G.sub.1] and [G.sub.2] as two finite cyclic groups of order q for some large prime q. A bilinear map [??]: [G.sub.1] x [G.sub.1] [right arrow] [G.sub.2] is defined between these two groups, satisfying the following properties:

(i) Bilinear: the map [??]: [G.sub.1] x [G.sub.1] [right arrow] [G.sub.2] is said to be bilinear if [??](aP, bQ) = [??][(P, Q).sup.ab] for all P, Q [member of] [G.sub.1] and all a, b [member of] [Z.sub.q]

(ii) Nondegenerate: the map e does not send all pairs in [G.sub.1] x [G.sub.1] to the identity in [G.sub.2]

(iii) Computable: there exists an efficient algorithm to compute [??](P, Q) for any P, Q [member of] [G.sub.1]

Chien's multiple group authentication scheme works as follows:

(i) Init: GM first selects two finite cyclic groups [G.sub.1] and [G.sub.2] with prime order q and a bilinear map [??]: [G.sub.1] x [G.sub.1] [right arrow] [G.sub.2]. Denote P as a generator of [G.sub.1]. GM then selects a secret [mathematical expression not reproducible] and sets Q = sP. GM selects l values [mathematical expression not reproducible] for i [member of] [Z.sub.i]. GM associates the pairwise different integers {[w.sub.1], [w.sub.2], ..., [w.sub.n]} with the group members. Finally, GM outputs the system parameters [mathematical expression not reproducible].

(ii) Dist: GM selects a random polynomial f(x) = a0 + [a.sub.1]x + *** + [a.sub.t-1][x.sup.t-1] over [Z.sub.q] with degree t - 1, such that [a.sub.0] = s. GM, then computes the credentials [s.sub.i] = f([w.sub.i]), and sends them to the group members through the secure channel.

(iii) Comp: in the ff-th session ([sigma][member of]{1, 2, ..., 1}), every participating user in [OMEGA] ([absolute value of [OMEGA]] > t) computes her token [c.sub.i] = ([s.sub.i][L.sub.i])[R.sub.[sigma]] and broadcasts it, where [L.sub.i] = [mathematical expression not reproducible] is the Lagrange coefficient.

(iv) Auth: in the [sigma]-th session, every user can verify whether all the users are legitimate group members by checking:

[mathematical expression not reproducible]. (1)

Note that if all players are legitimate group members, we have [[SIGMA].sub.t[member of][OMEGA]][c.sub.i] = s[R.sub.[sigma]]. Also, thanks to the bilinear property, this further implies that the abovementioned equation holds. But, if there exist some nonmembers, the relation [[SIGMA].sub.t[member of][OMEGA]][c.sub.i] = s[R.sub.[sigma]] can only satisfy with negligible probability. Therefore, the abovementioned equation can be used to check whether a group authentication is successful.

3.2. Analysis. Now, we demonstrate that, in the asynchronous communication model, an adversary A who has no valid credential can pretend to be a legitimate group member without being detected. Without loss of generality, suppose that A attends the [sigma]-th group authentication session together with t legitimate group members {[U.sub.1], [U.sub.2], ..., [U.sub.t]} and A would like to impersonate the group member Ut+1. The attack works as follows:

(i) Each legitimate group member [U.sub.i] computes and broadcasts her token [c.sub.i] = ([s.sub.i][L.sub.i])[R.sub.[sigma]], where [L.sub.i] [[PI].sup.t+1.sub.j=1,j[not equal to]t+1] [w.sub.j]/([w.sub.j] - [w.sub.i]) is the Lagrange coefficient.

(ii) After receiving these tokens, A modifies them as [c'.sub.i] = [c.sub.i] * [([L.sub.i]).sup.-1] = [s.sub.i][R.sub.[sigma]] for i[epsilon]{1, 2, ..., t} and interpolates [s.sub.t+1][R.sub.[sigma]] = [[SIGMA].sup.t.sub.i=1][c'.sub.i]([w.sub.t+1]), where

[mathematical expression not reproducible]. (2)

(i) Finally, A computes the token [c.sub.t+1] = ([s.sub.t+1][L.sub.t+1])[R.sub.[sigma]], where [L.sub.t+1] = [[PI].sup.t+1.sub.j=1,j[not equal to]t+1] [w.sub.j]/([w.sub.j] - [w.sub.i]), and broadcasts [c.sub.t+1].

At this time, the group authentication will be successful because [[SIGMA].sup.t+1.sub.i=1][c.sub.i] = s[R.sub.[sigma]]. The consequence is that the adversary A has impersonated the group member Ut+1 without being detected. The main reason for this attack is that since the Lagrange coefficients can be publicly computed, A can remove them from the revealed tokens and then uses the modified tokens to interpolate a new valid token. To solve this problem, we need to disable A's ability of removing the Lagrange coefficients from the revealed tokens.

4. Preliminaries

4.1. Notations. We assume that all players are probabilistic polynomial time (PPT) algorithms with respect to the security parameter A. Standard notations are used for probabilistic algorithms and experiments. For example, if A is a probabilistic algorithm, then A([x.sub.1], [x.sub.2], ...) denotes the result of running A on inputs [x.sub.1], [x.sub.2], and so on. We denote y [left arrow] A([x.sub.1], [x.sub.2], ...) as the experiment of assigning y as A([x.sub.1], [x.sub.2], ...). If S is a finite set, then we denote x [[left arrow].sub.R] S as the operation of picking an element uniformly from S. Moreover, Pr [x [left arrow] S; y [left arrow] T; ***: p(x, y, ...)] denotes the probability that the predicate p(x, y, ...) will be true after the ordered execution of the algorithms x [left arrow] S; y [left arrow] T, and so on. A function [epsilon](k): N [right arrow] [R.sup.+] is called negligible if for all c > 0, there exists a [k.sub.0] such that [epsilon](k) < (1/[k.sup.c]) for all k > [k.sub.0].

4.2. Building Blocks. Shamir secret sharing [13]: it shares the secret value s[epsilon][Z.sub.q] among n users, so that any t or more users can work together to recover the secret, but less than t users cannot get any information of the secret. In the sharing phase, the dealer first selects a random polynomial f(x) = [a.sub.0] + [a.sub.1]x + *** + [a.sub.t-1][x.sup.t-1] over [Z.sub.q] with degree t - 1, where [a.sub.0] = s. Then, the dealer computes the shares [s.sub.i] = f([w.sub.i]) and sends them to each user through the secure channel. Here, {[w.sub.1], [w.sub.2], ..., [w.sub.n]} are public parameters associated with the users that are pairwise different. In the reconstruction phase, any subset [OMEGA] (where [absolute value of ([OMEGA])] [greater than or equal to] t) of these users can reconstruct the secret s by Lagrange interpolation: s = [[SIGMA].sub.i[member of][OMEGA]][s.sub.i][L.sub.i], where [L.sub.i] = [[PI].sub.j[member of][OMEGA],j[not equal to]i][w.sub.j]([w.sub.j] - [w.sup.i]) is called the Lagrange coefficient.

Anonymous veto networks (AV-nets) [14]: they assume that there exist broadcast channels, and all the messages are exchanged through these channels. Suppose n users are involved, and then the protocol works as follows:

(i) Round 1: each user [U.sub.i] selects a value [x.sup.i] [[left arrow].sub.R][Z.sub.q] and broadcasts [mathematical expression not reproducible]. [U.sub.i] also proves that she has the knowledge of xi without revealing it, e.g., using the Schnorr identification technique [15]. When this round finishes, every user computes [mathematical expression not reproducible].

(ii) Round 2: every user broadcasts a value [mathematical expression not reproducible] and proves the knowledge of [x.sub.i] within [mathematical expression not reproducible] without revealing it. Now, we have

[mathematical expression not reproducible]. (3)

To see that the abovementioned property always holds, by definition, [y.sub.i] = [[SIGMA].sub.j<i][x.sub.j] - [[SIGMA].sub.j>i][x.sub.j]; hence, we have

[mathematical expression not reproducible]. (4)

4.3. Security model. We adapt the models and definitions in paper [5] and prove our proposed scheme using this security model.

The participants: there are four types of participants in group authentication schemes:

(i) Group manager (GM): the GM initializes the protocol and generates credentials for the users. In any authentication protocol, the user needs to possess some secret that is unknown to the others.

(ii) Users: each of the n users will receive a credential from the GM, and they will use their credentials to participate in the group authentication.

(iii) Inside adversary: the inside adversary [A.sub.I] controls at most t - 1 users, where t is the threshold such that t > n/2. [A.sub.I] can obtain these users' internal states. [A.sub.I]'s purpose is to learn some secret information or to pass the group authentication by herself.

(iv) Outside adversary: the outside adversary [A.sub.O] does not own any valid credential generated by the GM, but her purpose is to impersonate a group member in the group authentication without being detected.

Communication model: we assume that there exists a secure channel between the GM and every user, so that the credentials can be distributed securely. Moreover, we assume that every participant is connected to a broadcast channel, where any message sent through this channel can be heard by the other participants within some specified time bound. Note that the broadcast channel is only assumed to be asynchronous, such that messages sent from the uncorrupted users to the corrupted ones can be delivered relatively fast, the case in which the adversary can wait for the messages of the uncorrupted users to arrive, then decide on her computation and communication, and still get her messages delivered to the honest users on time. In comparison, all the users need to send their messages simultaneously in the synchronous networks. Therefore, adversaries in an asynchronous network are more powerful as they could obtain more information to assist their attacks.

System model: the group authentication scheme is specified by the following four randomized algorithms: Init, Dist, Comp, and Auth.

(i) The initialization algorithm Init is run by the GM. Init takes as inputs the security parameter [lambda]; it outputs the system parameters params.

(ii) The distribution algorithm Dist is run by the GM. Dist takes as inputs the system parameters params and the number of users n; it outputs a set of credentials {[s.sub.1], [s.sub.2], ..., [s.sub.n]}. These credentials are sent to U through the secure channel, where U denotes the set of all legitimate group members.

(iii) The computation algorithm Comp is run by every user. Comp takes as inputs the system parameters params, the session index [sigma], the set of participated users [OMEGA], and a credential [s.sub.i]; it outputs a token ci through the broadcast channel.

(iv) The group authentication algorithm Auth is run by the participated users. Auth takes as inputs the system parameters params, the session index [sigma] and a set of tokens [{[c.sub.i]}.sub.i[epsilon][OMEGA]]; it outputs 1 if [absolute value of ([OMEGA])] [greater than or equal to] t and [OMEGA] only contains legitimate group members, and it outputs 0 otherwise.

Security Model: the following security properties are considered in the security model.

Definition 1 (correctness). If a set [OMEGA] ([absolute value of ([OMEGA])] [greater than or equal to] t) of users are participating in the group authentication and they are all legitimate group members, then the group authentication will be successful. Formally, a group authentication scheme is said to have the correctness property if we have

[mathematical expression not reproducible]. (5)

In the abovementioned expression, [OMEGA] [??] U and [absolute value of ([OMEGA])] [greater than or equal to] t.

Definition 2 (secrecy). The inside adversary [A.sub.I] cannot learn any secret information in the group authentication process. Formally, a group authentication scheme is said to have the secrecy property if we have

[mathematical expression not reproducible]. (6)

In the abovementioned expression, [mathematical expression not reproducible] is denoted as A/s view in the real run of the protocol [PI], [[congruent to].sub.c] means computationally indistinguishable, and [mathematical expression not reproducible] is denoted as [[A.sub.I].sub.'s] view of the transcripts simulated by a PPT simulator S with only public information as inputs.

Definition 3 (no forgery). The inside adversary [A.sub.I] cannot pass the group authentication by herself. Formally, a group authentication scheme is said to have the no forgery property if we have

[mathematical expression not reproducible]. (7)

In the abovementioned expression, [U.sub.A] denotes the users that are controlled by [A.sub.I], such that [U.sub.A] [??] U and [absolute value of ([U.sub.A])] [less than or equal to] t - 1. [OMEGA] denotes an oracle that is used to query the group authentication service, and [SIGMA] records all the session indexes which have been queried.

Definition 4 (no impersonation). The outside adversary [A.sub.O] cannot impersonate a group member without being detected. Formally, a group authentication scheme is said to have the no impersonation property if we have

[mathematical expression not reproducible]. (8)

In the abovementioned expression, [A.sub.O] is assumed to impersonate the user [U.sub.[mu]], where [mu] [??] [OMEGA].

Computational assumptions: we assume that the following assumptions hold against any PPT algorithm.

Definition 5 (discrete logarithm (DL) assumption). The description of the finite cyclic group G is given, where [absolute value of (G)] [greater than or equal to] q and g is a generator of G. The discrete logarithm assumption implies that there exists a negligible function [epsilon](*) such that for all PPT adversaries [A.sub.DL], we have

Pr[x [[left arrow].sub.R][Z.sub.q]; [x.sup.*] [left arrow][A.sub.DL](G, q, g, [g.sup.x]): [x.sup.*] = x] < [epsilon]([lambda]). (9)

Definition 6 (computational Diffie-Hellman (CDH) assumption). The description of the finite cyclic group G given, where [absolute value of (G)] [greater than or equal to] q and g is a generator of G. The computational Diffie-Hellman assumption implies that there exists a negligible function [epsilon](*) such that for all PPT adversaries ACDH we have Pr[x [[left arrow].sub.R] [Z.sub.q]; y [[left arrow].sub.R] [Z.sub.q]; R [left arrow] [A.sub.CDH] (G, q, g, [g.sup.x], [g.sup.y]): R = [g.sup.xy]] < [epsilon]([lambda])

5. An Improvement of Chien's Scheme

5.1. The Proposed Scheme. The improved multiple group authentication scheme in the asynchronous communication model works as follows:

(i) Init: GM first selects two finite cyclic groups [G.sub.1] and [G.sub.2] with prime order q, and a bilinear map [??]: [G.sub.1] * [G.sub.1] [right arrow] [G.sub.2]. P is denoted as a generator of [G.sub.1]. GM then selects a secret s [[left arrow].sub.R] [Z.sub.q] and sets Q = sP. GM selects l values [R.sub.i] [[left arrow].sub.R] [G.sub.1] for i [member of] [Z.sub.l];. GM associates the pairwise different integers {[w.sub.1], [w.sub.2], ..., [w.sub.n]} with the group members. Finally, GM outputs the system parameters params [mathematical expression not reproducible].

(ii) Dist.: GM selects a random polynomial f(x) = [a.sub.0] + [a.sub.1]x +***+ [a.sub.t-1] [x.sup.t-1] over [Z.sub.q] with degree t - 1, such that [a.sub.0] = s. GM, then computes the credentials [s.sub.i] = f ([w.sub.i]), and sends them to the group members through the secure channel.

(iii) Comp: in the [sigma]-th session, every participating user in Q first selects [u.sub.i] [[left arrow].sub.R][Z.sub.q] and broadcasts [u.sub.i][R.sub.[sigma]]. Then, each user computes [v.sub.i][R.sub.[sigma]] = [[SIGMA].sub.j[member of][OMEGA],j<i][u.sub.j][R.sub.[sigma]] - [[SIGMA].sub.j[member of][OMEGA],j>i][u.sub.j][R.sub.[sigma]]. As follows, every user computes and broadcasts her token as

[c.sub.i] = ([s.sub.i][L.sub.i])[R.sub.[sigma]] + [u.sub.i][v.sub.i][R.sub.[sigma]], (10)

where [L.sub.i] = [[PI].sub.j[member of][OMEGA],j[not equal to]i][w.sub.j]/([w.sub.j] - [w.sub.i]) is the Lagrange coefficient.

(iv) Auth: In the [sigma]-th session, every user can verify whether all the users are legitimate group members by checking:

[mathematical expression not reproducible]. (11)

5.2. Security Analysis

Theorem 1. Our modified group authentication scheme satisfies the correctness property.

Proof. If [OMEGA] [??] U and [absolute value of ([OMEGA])] [greater than or equal to] t, the Lagrange interpolation implies that s = [[SIGMA].sub.i[member of][OMEGA]][s.sub.i][L.sub.i], where [L.sub.i] = [[PI].sub.i[member of][OMEGA]] [w.sub.j]/([w.sub.j] - [w.sub.i]) is the Lagrange coefficient. Moreover, because the AV-nets have the property that [[SIGMA].sub.i[member of][OMEGA]][u.sub.i][v.sub.i][R.sub.[sigma]] = 0, we have

[mathematical expression not reproducible], (12)

Therefore, the equation [mathematical expression not reproducible] will hold, and the authentication will be successful.

Theorem 2. Our modified group authentication scheme satisfies the secrecy property, assuming that the DL problem holds in [G.sub.1].

Proof. We denote [Real.sub.[PI]] ([lambda], params) as the real run of the protocol [PI] and [SIM.sub.S] ([lambda], params) as the protocol simulated by a PPT simulator S with only public information as inputs. [Real.sub.[PI]] ([lambda], params):

(i) Init: GM generates and outputs the system parameters params = [mathematical expression not reproducible].

(ii) Dist: GM computes the credentials [s.sub.i] = f([w.sub.i]) and sends them to the group members through the secret channel. Without loss of generality, we assume that the credentials {[s.sub.1], [s.sub.2], ..., [s.sub.t-1]} are learnt by the inside adversary [A.sub.I].

(iii) Comp: in the [omega]-th session, every participating user in [OMEGA] selects [u.sub.i] [[left arrow].sub.R] [Z.sub.q] and broadcasts [u.sub.i][R.sub.[omega]]. Then, each user computes [v.sub.i][R.sub.[sigma]] = [[SIGMA].sub.j[member of][OMEGA]j<i][u.sub.j][R.sub.[sigma]] - [[SIGMA].sub.j[member of][OMEGA]j<i][u.sub.j][R.sub.[sigma]] and broadcasts her token as [c.sub.i] = ([s.sub.i][L.sub.i])[R.sub.[sigma]] + [u.sub.i][v.sub.i][R.sub.[sigma]]. In this step, [A.sub.I] learns {[u.sub.1], [u.sub.2], ..., [u.sub.t-1]} which are possessed by the corrupted users and all the broadcast values.

(iv) Auth: in the [sigma]-th session, everyone verifies whether [mathematical expression not reproducible].

[SIM.sub.S] ([lambda], params):

(i) Init: the simulator S outputs the system parameters params = [mathematical expression not reproducible].

(ii) Dist: S sends the credentials {[s.sub.1], [s.sub.2], ..., [s.sub.t-1]} to the inside adversary [A.sub.I].

(iii) Comp: We denote k = [absolute value of ([OMEGA])]. In the [omega]-th session, S randomly selects k values {[u'.sub.1], [u'.sub.2], ..., [u'.sub.k]} from [Z.sub.q] and broadcasts [u'.sub.i][R.sub.[omega]] for i [member of] {1, 2, ..., k}. S sends {[u'.sub.1], [u'.sub.2], ..., [u'.sub.t-1]} to [A.sub.I]. S, then, randomly selects k 1 values {[c'.sub.1], [c'.sub.2], ..., [c'.sub.k-1]} from [G.sub.1] and computes [c'.sub.k] = [[SIGMA].sub.i[member of][OMEGA]][c.sub.i] - [[SIGMA].sup.k-1.sub.i=1][c'.sub.i] Then, S broadcasts the tokens {[c'.sub.1], [c'.sub.2], ..., [c'.sub.k]}.

(iv) Auth: in the [omega]-th session, everyone verifies whether [mathematical expression not reproducible].

We now prove that it is infeasible for the inside adversary [A.sub.I] to distinguish these two protocols. In the Init algorithm, the same public parameters params are published in both protocols. In the Dist algorithm, the same credentials {[s.sub.1], [s.sub.2], ..., [s.sub.t-1]} are learnt by [A.sub.I] in both protocols. In the Comp algorithm, both sets {[u.sub.1], [u.sub.2], ..., [u.sub.t-1]} and {[u'.sub.1], [u'.sub.2], ..., [u'.sub.t-1]} are randomly distributed in [Z.sub.q], and all the broadcast values are randomly distributed in [G.sub.1]. In Auth, the algorithm will be successful in both protocols. Therefore, [A.sub.I] cannot distinguish between [Real.sub.[PI]] ([lambda], params) and SIMS(A, params) because all these algorithms in [A.sub.I]'s view are indistinguishable. In other words, we have

[mathematical expression not reproducible]. (13)

Moreover, based on the DL assumption, [A.sub.I] cannot learn any secret information of s from the public information Q = sP or [[SIGMA].sub.i[member of][OMEGA]][c.sub.[sigma]] = s[R.sup.[sigma]]. Hence, our modified scheme satisfies the secrecy property.

Theorem 3. Our modified group authentication scheme satisfies the no forgery property, assuming that the CDH problem holds in [G.sub.1].

Proof. We denote X as the event that [A.sub.I] can predict the value s[R.sub.[sigma]] from the public parameters params and Y as the event that [A.sub.I] has learnt some secret information through querying the oracle [OMEGA]. We denote F as the event that [A.sub.I] outputs a successful forgery. Then, we have

[mathematical expression not reproducible]. (14)

In the abovementioned expression, [bar.X] and [bar.Y] denote the complements of X and Y, respectively.

Firstly, we prove that Pr [X] is negligible. Assume that the inside adversary [A.sub.O] can predict the value s[R.sub.[sigma]] from the public parameters params with nonnegligible probability, e.g., [A.sub.I] derives s[R.sub.[sigma]] from the equation [mathematical expression not reproducible]. Then, we show that there exists another adversary B who can use [A.sub.I] as a subroutine to break the CDH problem in [G.sub.1] with nonnegligible probability. The reduction works as follows: suppose B is given the description of [G.sub.1] with prime order q and P is a generator of [G.sub.1]. Moreover, B is given two random values Q = sP and [R.sub.[sigma]] = xP in [G.sub.1], and B's task is to compute s[R.sub.[sigma]] = sxP. In the Init algorithm, B simulates the public parameters params by selecting another cyclic group [G.sub.2] with order q, a bilinear map [??]: [G.sub.1] * [G.sub.1] [right arrow] [G.sub.2], as well as l - 1 random values [{[R.sub.i]}.sub.i[member of]{1,2...,l}]\{g} in [G.sub.1]. B, then, sends params to [A.sub.I]. In the Dist algorithm, B selects t - 1 random values {[s.sub.1], [s.sub.2], ..., [s.sub.t-1]} in [Z.sub.q] and sends them to [A.sub.I]. In the Comp algorithm, B selects t - 1 random values {[u.sub.1], [u.sub.2], ..., [u.sub.t-1]} in [Z.sub.q] and sends them to [A.sub.I]. B also broadcasts the required number of random values in [G.sub.1]. Note that the abovementioned steps generate a simulated environment for [A.sub.I] that is indistinguishable from a real run of our modified scheme [PI]. If [A.sub.I] outputs her predict of s[R.sub.[sigma]], B uses it to solve the CDH problem. Because it is assumed that the CDH assumption holds in [G.sub.1], our hypothesis that [A.sub.I] can predicate the value s[R.sub.[sigma]] from params with nonnegligible probability must be false. Hence, we have Pr [X] < [[epsilon].sub.1] (A) for some negligible function [[epsilon].sub.1] (*).

Secondly, Theorem 2 implies that the real run of our modified scheme n does not leak any secret information to [A.sub.I], based on the DL assumption in [G.sub.1]. Also, the hybrid argument [16] further implies that [A.sub.I] does not learn any secret information even if she has queried the oracle O polynomial number of times. Hence, we have Pr [Y] < [[epsilon].sub.2] (A) for some negligible function [[epsilon].sub.2] (*).

Finally, we analyze the probability Pr [F|[bar.X] [and] [bar.Y]]. In this case, [A.sub.I] needs to guess the value s[R.sub.[sigma]]. Because s is randomly distributed in [Z.sub.q] and [A.sub.I] only controls at most t - 1 group members, the probability of guessing s[R.sub.[sigma]] correct in each trial is exactly 1/q. Recall that [A.sub.I] can try polynomial number of times, and we have Pr [F|[bar.X] [and] [bar.Y]] = Q/q, where Q denotes the number of trials [A.sub.I] has made.

Putting the abovementioned analyses together, assuming that the CDH assumption holds in [G.sub.1], we have

[mathematical expression not reproducible], (15)

for some negligible function [epsilon](*). Therefore, our modified scheme satisfies the no forgery property.

Theorem 4. Our modified group authentication scheme satisfies the no impersonation property, assuming that the CDH problem holds in [G.sub.1].

Proof. Denote X as the event that [A.sub.O] can predict the value s[R.sub.[sigma]] from the public parameters params and F as the event that [A.sub.O] can impersonate a group member without being detected. Then, we have

[mathematical expression not reproducible]. (16)

Firstly, we prove that Pr[X] is negligible. Assume that the outside adversary [A.sub.O] can predict the value s[R.sub.[sigma]] from params with nonnegligible probability. Then, one can prove that there exists another adversary B who can use [A.sub.O] as a subroutine to break the CDH problem in [G.sub.1] with nonnegligible probability. The reduction is very similar as in Theorem 3. The main difference is that B does not need to send any user's internal states to [A.sub.O]. Hence, we have Pr[X] < [epsilon]([lambda]) for some negligible function [epsilon](*).

Next, we analyze the probability Pr [F|[bar.X]]. In this case, [A.sub.O] needs to output a token ct+1, such that the equation [[SIGMA].sup.t+1.sub.i=1] = s[R.sub.[sigma]] holds, where the set {[c.sub.1], [c.sub.2], ..., [c.sub.t]} denotes the other users' tokens that [A.sub.O] has already learnt. Because s is randomly selected in [Z.sub.q], the value s[R.sub.[sigma]] is randomly distributed in [G.sub.1]. Moreover, because the value s[R.sub.[sigma]] is unpredictable, the probability that [A.sub.O] outputs a valid token is exactly 1/q. Recall that [A.sub.O] can try polynomial number of times, and we have Pr[F|[bar.X]] = Q/q, where Q denotes the number of trials [A.sub.O] has made.

Putting the abovementioned analysis together, we conclude that Pr[F] < [epsilon]([lambda]) + Q/q, which is negligible. Therefore, our modified scheme satisfies the no impersonation property assuming that the CDH assumption holds in [G.sub.1].

5.3. Efficiency Analysis. We now give a brief efficiency analysis of our modified scheme. In the Init algorithm, GM selects the system parameters, including two finite cyclic group [G.sub.1] and [G.sub.2], a bilinear map [??] between these two groups, and some random values in [G.sub.1]. The computation of Q = sP takes 1 multiplication in [G.sub.1]. In the Dist algorithm, GM selects a random polynomial f(x) over [Z.sub.q] with degree t - 1 and evaluates this polynomial at n different points. When using Horner's rule, each evaluation of f (x) takes t - 1 multiplications and t additions in [Z.sub.q], and each credential is a value in [Z.sub.q]. In the Comp algorithm, each user broadcasts 2 values in [G.sub.1] in two individual rounds. The total computations for each user require at most n + 2 multiplications and n additions in [G.sub.1]. Note that, in this step, the Lagrange coefficients can be precomputed beforehand. In the Auth algorithm, each user performs at most n additions in [G.sub.1] and 2 bilinear maps.

An efficiency comparison between our proposed scheme and Chien's scheme [4] is given in Table 1. Denote the symbols + [G.sub.1], x [G.sub.1], + [Z.sub.q], * [Z.sub.q] and [right arrow] as the computations of addition in [G.sub.1], multiplication in [G.sub.1], addition in [Z.sub.q], multiplication in [Z.sub.q], and bilinear pairing [G.sub.1] * [G.sub.1] [right arrow] [G.sub.2], respectively. Also, we ignore the other calculations, i.e., select a random element from a group, since their costs are negligible compared with the abovementioned computations.

6. Conclusions

In this paper, we have pointed out a security flaw in an existing group authentication scheme by Chien [4]. If this scheme was used in the asynchronous communication model, the adversary can pretend to be a legitimate group member without being detected. The major reason for this attack is that the adversary is able to remove the Lagrange coefficients from the revealed tokens. We have employed the AV-net to solve this problem, and we have rigorously proved that our improvement satisfies the desirable security properties in a well-defined security model. Therefore, our proposed protocol can be safely used as a drop-in replacement for Chien's scheme in asynchronous networks.

https://doi.org/10.1155/2020/6183861

Data Availability

The authors confirm that no data were used to support this study.

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant nos. 61662016 and 61772224), Key Projects of Guangxi Natural Science Foundation (Grant no. 2018JJD170004), and Guangxi Key Laboratory of Trusted Software (Grant no. KX201908).

References

[1] Y. Liu and Q. Zhao, "E-voting scheme using secret sharing and k-anonymity," World Wide Web, vol. 22, no. 4, pp. 1-11,2019.

[2] Y. Zhou, Y. Liu, C. Jiang, and S. Wang, "An improved FOO voting scheme using blockchain," International Journal of Information Security, vol. 19, no. 3, pp. 303-310, 2019.

[3] L. Harn, "Group authentication," IEEE Transactions on Computers, vol. 62, no. 9, pp. 1893-1898, 2013.

[4] H.-Y. Chien, "Group authentication with multipletrials and multiple authentications," Security and Communication Networks, vol. 2017, Article ID 3109624, 7 pages, 2017.

[5] Z. Xia, L. Harn, B. Yang et al., "Provably secure group authentication in the asynchronous communication model," in Proceedings of the 21st International Conference on Information and Communications Security (ICICS), Springer, Beijing, China, pp. 1-16, 2019.

[6] W.-T. Su, W.-M. Wong, and W.-C. Chen, "A survey of performance improvement by group-based authentication in IoT," in Proceedings of the 2016 International Conference on Applied System Innovation (ICASI), IEEE, Okinawa, Japan, pp. 1-4, 2016.

[7] Y. Liu, Q. Sun, Y. Wang, L. Zhu, and W. Ji, "Efficient group authentication in rfid using secret sharing scheme," Cluster Computing, vol. 22, no. S4, pp. 8605-8611, 2018.

[8] P. N. Mahalle, N. R. Prasad, and R. Prasad, "Threshold cryptography-based group authentication (TCGA) scheme for the internet of things (IoT)," in Proceedings of the 2014 4th International Conference on Wireless Communications, Vehicular Technology, Information Theory and Aerospace & Electronic Systems (VITAE), Aalborg, Denmark, 2014.

[9] J. Li, M. Wen, and T. Zhang, "Group-based authentication and key agreement with dynamic policy updating for mtc in lte-a networks," IEEE Internet of Things Journal, vol. 3, no. 3, pp. 408-417, 2016.

[10] C. Guo, R. Zhuang, L. Yuan, and B. Feng, "A group authentication scheme supporting cheating detection and identification," in Proceedings of the 2015 Ninth International Conference on Frontier of Computer Science and Technology

(FCST), IEEE, Dalian, China, pp. 110-114, 2015.

[11] O. Elmouaatamid, M. Lahmer, and M. Belkasmi, "Group authentication with fault tolerance for internet of things," in Ubiquitous Networking, pp. 299-307, Springer, Berlin, Germany, 2017.

[12] Z. Ahmadian and S. Jamshidpour, "Linear subspace cryptanalysis of Harn's secret sharing-based group Authentication scheme," IEEE Transactions on Information Forensics and Security, vol. 13, no. 2, pp. 502-510, 2018.

[13] A. Shamir, "How to share a secret," Communications of the ACM, vol. 22, no. 11, pp. 612-613, 1979.

[14] H. Feng and P. Zielinski, "A 2-round anonymous veto protocol," in International Workshop on Security Protocols, pp. 202-211, Springer, Berlin, Germany, 2006.

[15] C.-P. Schnorr, "Efficient signature generation by smart cards," Journal of Cryptology, vol. 4, no. 3, pp. 161-174, 1991.

[16] S. Goldwasser and S. Micali, "Probabilistic encryption," Journal of Computer and System Sciences, vol. 28, no. 2, pp. 270-299, 1984.

Zhe Xia [ID], (1,2) Yining Liu, (3) Ching-Fang Hsu, (4) and Chin-Chen Chang (5,6)

(1) School of Computer Science, Wuhan University of Technology, Wuhan 430071, China

(2) Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China

(3) School of Computer and Information Security, Guilin University of Electronic Technology, Guilin 541004, China

(4) Computer School, Central China Normal University, Wuhan 430079, China

(5) Department of Information Engineering and Computer Science, Feng Chia University, Taichung, Taiwan

(6) School of Computer Science and Technology, Hangzhou Dianzi University, Hangzhou 310018, China

Correspondence should be addressed to Zhe Xia; xiazhe@whut.edu.cn

Received 27 November 2019; Revised 1 April 2020; Accepted 11 June 2020; Published 13 July 2020

Academic Editor: Leandros Maglaras

TABLE 1: Comparison between our scheme and Chien's scheme. Init Dist Chien's scheme 1 * [G.sub.1] (t-1) * [Z.sub.q], t + [Z.sub.q] Our scheme 1 * [G.sub.1] (t-1) * [Z.sub.q], t + [Z.sub.q] Comp Chien's scheme 1 * [G.sub.1] Our scheme (n + 2) * [G.sub.1], n + [G.sub.1] Auth Chien's scheme n + [G.sub.1], 1 [right arrow] Our scheme n + [G.sub.1], 1 [right arrow]

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Xia, Zhe; Liu, Yining; Hsu, Ching-Fang; Chang, Chin-Chen |

Publication: | Security and Communication Networks |

Geographic Code: | 9CHIN |

Date: | Jul 31, 2020 |

Words: | 6726 |

Previous Article: | Unordered Multisecret Sharing Based on Generalized Chinese Remainder Theorem. |

Next Article: | Research on SKINNY Optimal Differential Trail Search. |

Topics: |