Anonymous and Unlinkable Membership Authentication with Illegal Privilege Transfer Detection

Show more

1. Introduction

The rapid development of the Internet has resulted in an increase in electronic transactions that allow users to buy goods or services from online platforms provided by Internet companies, including Google, Facebook, eBay, and Twitter. Service providers must confirm whether a user is permitted to access its resource. Access control [1] [2] provides a solution by verifying either a cryptographic certificate or a username and password. However, the information provided by the user during an interaction with the service provider may undermine the user privacy: the user must risk being traced or even impersonated by corrupt service providers.

Group signatures [3] [4] [5] [6] allow group members with privilege to sign a signature under the group secret key. On the basis of an auxiliary cryptographic technique called zero-knowledge proof [7] , the verifier can check the member’s access rights by using the group public key without knowing the member’s identity. The member obtains access to the service if their presented signature is verified to be valid. If necessary, the signature can be opened by a specific group manager to identify the signature’s originator in case of a dispute. Several provably secure authentication schemes [8] [9] [10] [11] have been proposed to create anonymous memberships in which any member of a group can prove to the service provider (i.e., the verifier) that they are qualified to access a service or file; however, these schemes are impractical because they do not provide exclusive verification of revoked memberships. As proven by the fact that some members have been revoked, in contrast to the use of fixed time periods [12] by employing a one-way chain, Ateniese et al. [13] require group members to prove that their membership does not appear on the current certificate revocation list (CRL). However, in their scheme, the verifier must check whether the member’s membership fits any of the revocation information on the CRL in turn by using their “REVOKE” algorithm every time a member requests membership authentication. The cost to the group manager is proportional to the number of revoked group members because issuing new memberships to non-revoked members is required every time a membership is revoked. Clearly, the scheme performs inefficiently and has not been improved to date.

Additionally, state-of-the-art authentication schemes provide few revocation methods without describing how to detect malicious members’ illegal behavior; in other words, such schemes are unaware of malicious members who have been involved in privilege transfer. This is known as impersonation or an illegal privilege transfer attack and is a priority for prevention because it regularly occurs in the aforementioned schemes and is difficult to trace. In addition, the modern authentication schemes are becoming more complicated to ensure security. However, this is not a favorable development because it will obstruct the development of membership authentication schemes, resulting in research becoming impractical and unattractive. In summary, a robust authentication scheme should contain two components: a membership authentication approach that can withstand members who engage in membership transfer and proof of membership that is exclusive to the current CRL.

In this paper, a novel membership authentication scheme is proposed that provides a simple solution for membership authentication and revocation. The proposed scheme may suffer from the disadvantage of illegal privilege transfer; however, this problem can easily be solved by employing the traitor tracing technique [14] [15] [16] [17] [18] . Traitor tracing was first suggested by [14] , which discusses how to identify a traitor in a public key cryptographic scheme and proposes some approaches for revoking access rights for at least one of the traitors involved in illegal privilege transfer. To evade accountability, a traitor may attempt to modify their secret key to avoid being traced. Traitor tracing schemes ensure that no such strategy can succeed, and the schemes guarantee that the traitor’s identity is revealed. Typical CRL approaches are not directly applicable to our proposed scheme because the memberships are anonymous and unlinkable. Instead of compiling a typical CRL, the dynamic accumulator technique [19] [20] [21] is employed in the proposed scheme to enable an eligible member to prove the exclusiveness of their membership on the CRL.

Organization of the Thesis

This paper is organized as follows. Section 2 describes the anonymous authentication scheme and its requirements as well as the dynamic accumulators. An anonymous and unlinkable membership authentication scheme with illegal privilege transfer detection is proposed in Section 3. Security and performance analysis of the proposed scheme is detailed in Section 4. Finally, Section 5 presents the conclusion.

2. Background

2.1. Anonymous Authentication Schemes

Group signatures [12] [13] with membership revocation are typically defined using the following algorithms:

Setup:

A probabilistic algorithm that outputs the group public key and group secret key for the group manager, given a security parameter as the input.

Join:

A protocol between the group manager and a user that results in the user becoming a group member and receiving a group signing key.

Sign:

A probabilistic algorithm that outputs an anonymous membership for a member, with some necessary parameters (including the member’s group signing key) as the input.

Verify:

An algorithm for examining the validity of an alleged membership with respect to a group public key.

Open:

An algorithm, which can only be implemented by the group manager, used to determine the originator’s identity.

Some authentication schemes [10] [11] have been proposed for creating anonymous memberships by extending the idea of group signatures. Three parties are involved in generic authentication schemes, namely the prover (i.e., the member), issuer (i.e., the key generation center [KGC]), and verifier (i.e., the application server [AS]). The issuer is assumed to be a trusted third party responsible for generating unique and anonymous memberships for eligible provers. A prover with membership can prove to the verifier that they have been given an appropriate membership. The verifier can verify the validity of memberships, but knows nothing about the prover’s real identity. The scheme must guarantee that different authentication messages submitted by the same prover cannot be linked.

Additionally, the following security requirements, which have been identified and discussed in the literature, should be inspected.

Unforgeability:

Only an eligible prover can obtain a unique valid membership. An adversary cannot feasibly forge a membership that can obtain verification.

Strong/weak unlinkability:

Strong unlinkability ensures that the pseudonym and real identity of a prover cannot be linked during multiple uses of the membership. Conversely, weak unlinkability allows only a pseudonym but not the prover’s real identity to be linked when the prover uses the membership more than once.

Nontransferability:

Even though the verifier knows nothing about the prover’s real identity during the interactions; however, a sound authentication scheme must guarantee that membership transfer behavior can be detected and abused memberships can be revoked.

Excludability:

Neither a group member nor the group manager can sign on behalf of other group members.

For efficient exclusive verification of the CRL and detection of illegal privilege transfer, the following attractive security properties are necessary:

Dynamic membership:

The membership can easily be updated by any eligible member of the group when inserting (deleting) a new (abusive) member rather than issuing a new membership or requiring the verifier to refer to the CRL.

Traitor detection:

The scheme must be able to determine the real identity of the malicious member.

2.2. Dynamic Reversed Accumulator

Accumulators were first proposed by Benaloh and de Mare [22] for combining a set of members’ specific values into one accumulator. Each corresponding member is assigned a unique witness, which is used to prove the validity of their membership. However, the computational complexity of the Benaloh-de Mare scheme increases linearly, either according to the number of group members or the number of revoked members. In 2002, Camenisch and Lysyanskaya [19] proposed an efficient dynamic accumulator scheme in which members can update their witness dynamically without the authority’s help. Additionally, the computational complexity of inserting and deleting a member as well as updating members’ witnesses is independent of the number of accumulated values. In 2009, Camenisch et al. proposed an additional accumulator scheme [20] that involves using a bilinear cryptography technique. However, the schemes in [19] [20] were later proved insecure by Kuo et al. [21] later. Although other accumulators [23] [24] [25] [26] utilize bilinear cryptography, these schemes are either vulnerable to collusion attacks or inefficient.

In this section, we review the dynamic reversed accumulator scheme of Kuo et al. [21] , which relies on the strong RSA assumption [7] [27] . To the best of our knowledge, their scheme is the most efficient and secure accumulator scheme for state-of-the-art dynamic accumulators and is highly applicable for the granting and revoking of privileges.

Initialization:

Let the modulus $n=p\times q$ , with p and q safe primes; U be a set of t eligible members, each with an identity ${x}_{u}$ ( $u=1,\cdots ,t$ ); and $\stackrel{\u02dc}{U}$ be a set of members being revoked. All identities are assumed to be pairwise relatively prime, and the authority maintains the sets U and $\stackrel{\u02dc}{U}$ , which are initially empty. The authority chooses an element $g\in Q{R}_{n}$ and a prime z (which can be 2); computes the accumulator as $ACC=f\left(g,z\right)={g}^{z}\mathrm{mod}n$ , where $g\ne 1$ ; and publishes $\left(ACC,g\right)$ . Here, $f(\cdot )$ is a public quasi-commutative function [21] . It holds that

・ $f\left(f\left(g,{x}_{1}\right),{x}_{2}\right)=f\left(f\left(g,{x}_{2}\right),{x}_{1}\right)={g}^{{\displaystyle {\prod}_{u=1}^{2}{x}_{u}}}\mathrm{mod}n$ ;

・ $f\left(g,U\right)=f\left(f\left(\cdots f\left(g,{x}_{1}\right)\cdots \right),{x}_{t}\right)={g}^{{\displaystyle {\prod}_{u=1}^{t}{x}_{u}}}\mathrm{mod}n\text{.}$

Member insertion:

To include a new member ${x}_{w}$ , the authority examines whether ${x}_{w}\notin U$ , and if so, adds ${x}_{w}$ to the set U (new set of eligible members as ${U}^{\prime}=U\cup \left\{{x}_{w}\right\}$ ) and updates the aforementioned archive. The new member is given a witness $wi{t}_{w}=f\left(ACC,{x}_{w}^{-1}\right)={g}^{z\times {x}_{w}^{-1}\mathrm{mod}\varphi \left(n\right)}\mathrm{mod}n$ and a value ${x}_{w}$ for $\mathrm{gcd}\left({x}_{w},\varphi \left(n\right)\right)=1$ . Here, the accumulator ACC is not changed; therefore, the group members do not need to update their witnesses.

Witness verification:

Only an eligible member ${x}_{u}\in U$ can prove the validity of their system access to a verifier, that their unique value ${x}_{u}$ is included in the public accumulator ACC, and that they know the corresponding witness $wi{t}_{u}$ on the basis of the zero-knowledge proof technique. The verifier can verify the correctness by using the online public information ACC maintained by the authority, and the group member ${x}_{u}$ is granted access rights if the following Equation (1) holds for their claim:

$wi{t}_{u}^{{x}_{u}}\equiv {g}^{\left(z\times {x}_{u}^{-1}\right)\times {x}_{u}}\equiv ACC\left(\mathrm{mod}n\right)$ . (1)

Member deletion:

When the membership of group member ${x}_{v}$ is revoked, the authority deletes ${x}_{v}$ from the set U and moves the value ${x}_{v}$ into the set $\stackrel{\u02dc}{U}$ . The authority computes the new accumulator $AC{C}^{\prime}=f\left(ACC,{x}_{v}^{-1}\right)=AC{C}^{{x}_{v}^{-1}}\mathrm{mod}n$ , updates the archive, and publishes the revocation information $\left(AC{C}^{\prime},{x}_{v}\right)$ . Knowledge of p, q is required for computing ${x}_{v}^{-1}$ . Kuo et al. called their scheme a dynamic reversed accumulator because the value ${x}_{v}\in \stackrel{\u02dc}{U}$ here is subtracted from the accumulator and the accumulator decreases gradually. Additionally, each member in U must update their witness to reflect the result of the updated accumulator. On the basis of the extended Euclidean algorithm, the eligible members ${x}_{u}\in U$ can compute the integers a and b satisfying $a\times {x}_{u}+b\times {x}_{v}=1$ and update their witnesses as $wi{{t}^{\prime}}_{u}=AC{{C}^{\prime}}^{a}\times wi{t}_{u}^{b}\mathrm{mod}n$ , such that ${\left(wi{{t}^{\prime}}_{u}\right)}^{{x}_{u}}=AC{C}^{\prime}$ . Computing the witness update does not require knowledge of (p, q) and can be performed only by the eligible members ${x}_{u}\in U$ . It is infeasible for the revoked member ${x}_{v}$ to update their witness because $\mathrm{gcd}\left({x}_{v},{x}_{v}\right)\ne 1$ . Crucially, the computational costs of both updating the group accumulator and each individual member’s witness are independent of the size of $\stackrel{\u02dc}{U}$ .

The scheme of Kuo et al. features a substantial computational cost reduction compared with the existing methods because renewing the accumulator and valid members’ witnesses is required only when revoking violating members (not including new members).

3. Proposed Anonymous Authentication Scheme

In this section, a basic scheme of anonymous membership authentication with anonymity, unlinkability, and efficiency is proposed. Furthermore, we discuss its security. Subsequently, an enhanced version of the scheme is accordingly proposed, and this scheme is analyzed in the next section. The member must additionally establish a secure channel with the verifier in contrast to the aforementioned authentication schemes; in other words, a lower layer node-to-node secure channel with randomized encryption is assumed.

3.1. Bilinear Groups and Security Assumptions

The following definition of a bilinear map comes from [28] and is a fundamental building block of our proposed scheme. Let $\left({\mathbb{G}}_{1},+\right)$ , $\left({\mathbb{G}}_{2},+\right)$ , and $\left({\mathbb{G}}_{T},\cdot \right)$ be three groups of the same prime order q, and let P, Q be two generators of ${\mathbb{G}}_{1}$ and ${\mathbb{G}}_{2}$ , respectively. We say that $\left({\mathbb{G}}_{1},{\mathbb{G}}_{2},{\mathbb{G}}_{T}\right)$ are asymmetric bilinear map groups if ${\mathbb{G}}_{1}\ne {\mathbb{G}}_{2}$ and the bilinear map $\stackrel{^}{e}:{\mathbb{G}}_{1}\times {\mathbb{G}}_{2}\to {\mathbb{G}}_{T}$ satisfies the following properties:

・ Bilinearity: $\forall \left(P,Q\right)\in {\mathbb{G}}_{1}\times {\mathbb{G}}_{2}$ and $\forall a,b\in {\mathbb{Z}}_{q}^{*}$ , $\stackrel{^}{e}\left(aP,bQ\right)=\stackrel{^}{e}{\left(P,Q\right)}^{ab}$ .

・ Nondegeneracy: $\stackrel{^}{e}\left(P,Q\right)\ne 1$ .

・ Computability: $\forall \left(P,Q\right)\in {\mathbb{G}}_{1}\times {\mathbb{G}}_{2}$ , $\stackrel{^}{e}\left(P,Q\right)$ is efficiently computable.

The proposed membership authentication scheme can be operated in both symmetric and asymmetric settings. For greater efficiency, the symmetric setting is more appropriate, whereas the asymmetric setting has greater security. Here, we directly use the asymmetric setting to enrich our cryptanalysis content in Section 4 and demonstrate the flexibility of our proposed scheme.

The security of our scheme relies on the hardness of the following problems, which were introduced in [29] .

Definition 1 (Fixed Argument Pairing Inversion Problems). Let $\stackrel{^}{e}$ be an asymmetric pairing. The fixed argument pairing inversion 1 (FAPI-1) problem is as follows: Given ${\mathcal{U}}_{1}{\in}_{R}{\mathbb{G}}_{1}$ and a value $z\in {\mathbb{G}}_{T}$ , compute ${\mathcal{U}}_{2}\in {\mathbb{G}}_{2}$ such that $\stackrel{^}{e}\left({\mathcal{U}}_{1},{\mathcal{U}}_{2}\right)=z$ . The fixed argument pairing inversion 2 (FAPI-2) problem is as follows: Given ${\mathcal{U}}_{2}{\in}_{R}{\mathbb{G}}_{2}$ and a value $z\in {\mathbb{G}}_{T}$ , compute ${\mathcal{U}}_{1}\in {\mathbb{G}}_{1}$ such that $\stackrel{^}{e}\left({\mathcal{U}}_{1},{\mathcal{U}}_{2}\right)=z$ .

Both problems FAPI-j (for j = 1 or 2) have a unique solution for each given pair $\left({\mathcal{U}}_{j},z\right)\in {\mathbb{G}}_{j}\times {\mathbb{G}}_{T}$ because the pairing is non-degenerate and the groups ${\mathbb{G}}_{1}$ , ${\mathbb{G}}_{2}$ , and ${\mathbb{G}}_{T}$ are cyclic of order q. Finally, a general case of the pairing inversion problem is presented in the following definition.

Definition 2 (Generalized Pairing Inversion (GPI) Problem). The problem is to find two values ${\mathcal{U}}_{1}\in {\mathbb{G}}_{1}$ and ${\mathcal{U}}_{2}\in {\mathbb{G}}_{2}$ such that $\stackrel{^}{e}\left({\mathcal{U}}_{1},{\mathcal{U}}_{2}\right)=z$ when a pairing $\stackrel{^}{e}$ as above and a value $z\in {\mathbb{G}}_{T}$ are given.

3.2. Basic Scheme

In this section, we first introduce a basic anonymous authentication scheme comprising three parties, namely the group member, KGC, and AS. A KGC is a trusted third party responsible for issuing private keys to all valid members, and an AS provides services to any eligible member with proof of valid membership. The basic scheme comprises the following algorithms:

Setup.

As mentioned in Section 3.1, ${\mathbb{G}}_{1}$ , ${\mathbb{G}}_{2}$ , and ${\mathbb{G}}_{T}$ are three bilinear cyclic groups of prime order q; $\stackrel{^}{e}:{\mathbb{G}}_{1}\times {\mathbb{G}}_{2}\to {\mathbb{G}}_{T}$ is a bilinear mapping with underlying groups of same order q; and $P\in {\mathbb{G}}_{1}$ and $Q\in {\mathbb{G}}_{2}$ are two generators. Let ${x}_{j}$ be N prime numbers chosen from the field ${\mathbb{Z}}_{q}^{*}$ , for $1\le j\le N$ . The KGC selects a large even integer k with $k<N$ and computes the group secret key as $X={\displaystyle {\prod}_{j=1}^{k}{x}_{j}}$ and the corresponding group public key as $Y=\stackrel{^}{e}{\left(P,Q\right)}^{X}$ . The KGC then publishes the system parameters as

$\mathcal{G}=\left({\mathbb{G}}_{1},{\mathbb{G}}_{2},{\mathbb{G}}_{T},q,\stackrel{^}{e},P,Q,Y\right).$

Join.

For each legitimate member ${U}_{i}$ of a group, the KGC randomly selects $k/2$ elements of ${x}_{j}$ (the components of this subset are denoted as ${\stackrel{^}{x}}_{j}$ ) and computes ${a}_{i}={\displaystyle {\prod}_{j=1}^{k/2}{\stackrel{^}{x}}_{j}}$ and ${b}_{i}=X/{a}_{i}$ . Subsequently, ${U}_{i}$ is given their private key ( ${a}_{i}P$ , ${b}_{i}Q$ ). Clearly, we have $\stackrel{^}{e}\left({a}_{i}P,{b}_{i}Q\right)=\stackrel{^}{e}{\left(P,Q\right)}^{X}=Y$ , but ${a}_{i}P$ and ${b}_{i}Q$ cannot be used directly as proof of membership, otherwise any two application service requests are easily linked and the member’s privacy is threatened. Here, an archive is required for maintaining the tuple ( ${a}_{i}$ , ${b}_{i}$ , ${U}_{i}$ ) in which the KGC can reveal the real identity of a malicious member who has been recognized as a traitor.

Sign.

When the member ${U}_{i}$ requests service from an AS, ${U}_{i}$ selects two random numbers $\alpha ,\beta \in {\mathbb{Z}}_{q}^{*}$ and computes $\mathbb{P}={a}_{i}P+\alpha P$ and $\mathbb{Q}={b}_{i}Q+\beta Q$ . ${U}_{i}$ also computes $A=\stackrel{^}{e}{\left({a}_{i}P,Q\right)}^{\beta}$ , $B=\stackrel{^}{e}{\left(P,{b}_{i}Q\right)}^{\alpha}$ , and $C=\alpha \beta P$ . Here, the tuple $\left\{\mathbb{P},\mathbb{Q},A,B,C\right\}$ is the membership of ${U}_{i}$ for obtaining access to application services provided by a specific AS.

Verify.

1) ${U}_{i}\Rightarrow AS:\left\{\mathbb{P},\mathbb{Q},A,B,C\right\}$ over a secure channel.

2) AS verifies the membership proof by checking whether

$\stackrel{^}{e}\left(\mathbb{P},\mathbb{Q}\right)=Y\times A\times B\times \stackrel{^}{e}\left(C,Q\right).$ (2)

Because blinding factors $\alpha $ and $\beta $ are used, ${U}_{i}$ can prove their membership multiple times to the same or to a different AS; by contrast, all the authentication messages $\left\{\mathbb{P},\mathbb{Q},A,B,C\right\}$ cannot be linked to reveal that they are all generated by the same member ${U}_{i}$ .

Correctness of the scheme.

The correctness of the verification is shown as follows. Given the group public key $Y=\stackrel{^}{e}{\left(P,Q\right)}^{X}=\stackrel{^}{e}\left({a}_{i}P,{b}_{i}Q\right)$ and the membership proof $\left\{\mathbb{P},\mathbb{Q},A,B,C\right\}$ , ${U}_{i}$ gains access to AS’s services if the scheme works correctly and Equation (3) holds:

$\begin{array}{c}\stackrel{^}{e}\left(\mathbb{P},\mathbb{Q}\right)=\stackrel{^}{e}\left(\left({a}_{i}+\alpha \right)P,\left({b}_{i}+\beta \right)Q\right)\\ =\stackrel{^}{e}{\left(P,Q\right)}^{\left({a}_{i}+\alpha \right)\times \left({b}_{i}+\beta \right)}\\ =\stackrel{^}{e}{\left(P,Q\right)}^{{a}_{i}{b}_{i}}\times \stackrel{^}{e}{\left({a}_{i}P,Q\right)}^{\beta}\times \stackrel{^}{e}{\left(P,{b}_{i}Q\right)}^{\alpha}\times \stackrel{^}{e}{\left(P,Q\right)}^{\alpha \beta}\\ =Y\times A\times B\times \stackrel{^}{e}\left(C,Q\right).\end{array}$ (3)

${U}_{i}$ cannot compute and send $C=\stackrel{^}{e}{\left(P,Q\right)}^{\alpha \beta}$ directly to the AS. Otherwise, the scheme becomes insecure if it is designed in the aforementioned approach. Because the verification equation would become

$\stackrel{^}{e}\left(\mathbb{P},\mathbb{Q}\right)=Y\times A\times B\times C,$

and any attacker could select two random ${\mathbb{P}}^{\prime}$ and ${\mathbb{Q}}^{\prime}$ and then compute ${C}^{\prime}=\stackrel{^}{e}\left({\mathbb{P}}^{\prime},{\mathbb{Q}}^{\prime}\right)/\left(Y\times {A}^{\prime}\times {B}^{\prime}\right)$ , where ${A}^{\prime}$ and ${B}^{\prime}$ are also randomly selected. The attack can thusly pass the verification procedure with the forged membership proof $\left\{{\mathbb{P}}^{\prime},{\mathbb{Q}}^{\prime},{A}^{\prime},{B}^{\prime},{C}^{\prime}\right\}$ .

Selection of parameter k.

Let k = 100 and 200; it yields $C\left(100,50\right)={10}^{29}$ and $C\left(200,100\right)={10}^{59}$ combinations of the value ${a}_{i}$ , respectively, where $C(\cdot )$ is a combination function.

Remarks and Discussion

Impersonation or illegal privilege transfer attack.

A sound anonymous membership authentication scheme should consider how to counteract a forged membership duplication to others from a valid member. That is, a valid member ${U}_{i}$ may attempt to share their private key $\left\{{a}_{i}P,{b}_{i}Q\right\}$ with their untrusted friend ${U}_{x}$ . We assume that collusion among the AS, KGC, and ${U}_{x}$ is possible. With knowledge of both ${a}_{i}P$ and ${b}_{i}Q$ (and the related identity of its owner revealed by the ${U}_{x}$ ), the AS can obtain both $\alpha P=\mathbb{P}-{a}_{i}P$ and $\beta Q=\mathbb{Q}-{b}_{i}Q$ when the original member ${U}_{i}$ logs in to the AS. To check whether a service request is made by ${U}_{i}$ , the AS verifies whether

$\stackrel{^}{e}\left(C,Q\right)=\stackrel{^}{e}\left(\alpha P,\beta Q\right).$ (4)

Clearly, this “private key revelation” forces ${U}_{i}$ not to share their private key and privilege with others; otherwise, any two of ${U}_{i}$ ’s service requests can be linked and their anonymity will be ruined. In this attack, the original member ${U}_{i}$ also risks privilege revocation by the KGC (here, a typical blacklist is required) after an unauthorized privilege transfer is confirmed. The privilege is thus nontransferable.

In the following, we show another privilege transfer approach launched by the member ${U}_{i}$ , but this approach does not undermine ${U}_{i}$ ’s anonymity. Let $\alpha $ and $\beta $ be two blinding factors as before; ${U}_{i}$ uses a third blinding factor $\gamma $ and sends the “transformed” private key $\left\{\gamma {a}_{i}P,{\gamma}^{-1}{b}_{i}Q\right\}$ to their friend ${U}_{x}$ , who can be either trusted or untrusted. On the basis of this transformed private key, the unprivileged ${U}_{x}$ can prove their membership to the AS through the same anonymous authentication scheme by computing $\mathbb{P}=\gamma {a}_{i}P+\alpha P$ , $\mathbb{Q}={\gamma}^{-1}{b}_{i}Q+\beta Q$ , $A=\stackrel{^}{e}{\left({a}_{i}\gamma P,Q\right)}^{\beta}$ , $B=\stackrel{^}{e}{\left(P,{b}_{i}{\gamma}^{-1}Q\right)}^{\alpha}$ , and $C=\alpha \beta P$ . The AS also verifies the membership proof by checking whether Equation (2) holds. In this attack, collusion between the AS and ${U}_{x}$ to threaten the original member ${U}_{i}$ ’s privacy is impossible. Nevertheless, the untrusted friend ${U}_{x}$ can disclose the fact of illegal privilege transfer to the KGC by providing $\left\{\gamma {a}_{i}P,{\gamma}^{-1}{b}_{i}Q\right\}$ . Recall that the KGC keeps the ${a}_{i}$ and ${b}_{i}$ selected for each member ${U}_{i}$ and can therefore check whether a member ${U}_{i}$ is involved in an unauthorized privilege transfer as follows:

$\stackrel{^}{e}{\left(\gamma {a}_{i}P,{\gamma}^{-1}{b}_{i}Q\right)}^{{a}_{i}^{-1}{b}_{i}^{-1}}=\stackrel{^}{e}\left(P,Q\right).$ (5)

If Equation (5) holds, the original member ${U}_{i}$ is revoked, and this forces ${U}_{i}$ to not share their transformed private key and privilege with others.

In addition, if ${U}_{x}$ would never betray ${U}_{i}$ , the trusted KGC can be consulted online to recognize this privilege transfer as follows. Assume that the KGC can compute $\stackrel{^}{e}{\left(P,Q\right)}^{{a}_{i}+{b}_{i}}$ in advance for all registered members. If the AS provides a suspicious $\left\{\mathbb{P},\mathbb{Q},A,B\right\}$ to the KGC for investigating potential privilege transfers, the KGC attempts to use all registered members’ information $\left({a}_{i},{b}_{i}\right)$ , for $1\le i\le N$ , and computes both

${\pi}_{i}={A}^{{a}_{i}^{-1}}{B}^{{b}_{i}^{-1}}=\stackrel{^}{e}{\left(P,Q\right)}^{\gamma \beta +{\gamma}^{-1}\alpha}$ (6)

and

$\begin{array}{c}{\lambda}_{i}=\stackrel{^}{e}\left(\mathbb{P},Q\right)\times \stackrel{^}{e}\left(P,\mathbb{Q}\right)\\ =\stackrel{^}{e}{\left(P,Q\right)}^{\gamma {a}_{i}+\alpha}\stackrel{^}{e}{\left(P,Q\right)}^{{\gamma}^{-1}{b}_{i}+\beta}\\ =\stackrel{^}{e}{\left(P,Q\right)}^{\gamma {a}_{i}+{\gamma}^{-1}{b}_{i}+\alpha +\beta}.\end{array}$ (7)

The KGC then tests whether any $\stackrel{^}{e}{\left(P,Q\right)}^{{a}_{i}+{b}_{i}}\times {\pi}_{i}$ equals ${\lambda}_{i}$ to verify whether the received authentication message was generated by privileged member ${U}_{i}$ . Clearly, the authentication message generated from a transformed private key with $\gamma \ne 1$ will fail to pass the verification, and we can conclude that someone has transferred their membership to someone else. The KGC knows nothing regarding the malicious member’s real identity, which is known as “weak unlinkability.” In a medium-sized setting with a moderately large number of members, the described online investigation might be possible if not performed frequently. However, this method cannot completely prevent illegal privilege transfer attack.

Replay attack.

This basic scheme cannot withstand the replay attack.

3.3. Enhanced Version of the Proposed Scheme

Consider the potential illegal privilege transfer attack and unpreventable replay attack mentioned in Section 3.2.1. An enhanced scheme is proposed in this section. The scheme features anonymity and unlinkabilty and guarantees security against the aforementioned attacks. Because some algorithms are identical to those defined in Section 3.2, including Setup and Join, this section describes only the differences. The algorithms of the enhanced scheme are detailed as follows:

Sign.

Let ${T}_{i}$ be a timestamp and $h(\cdot ):{\left\{0,1\right\}}^{*}\to {\mathbb{G}}_{1}$ be a collision-free one-way hash function. When the member ${U}_{i}$ requests service from an AS, ${U}_{i}$ selects two random numbers $\alpha ,\beta \in {\mathbb{Z}}_{q}^{*}$ and computes $A=\alpha \beta P$ , $B=\alpha P$ , $\mathbb{P}={\beta}^{-1}{a}_{i}P+t\alpha P$ , and $\mathbb{Q}=\beta {b}_{i}Q$ , where $t=h\left({T}_{i}\right)$ . Here, the tuple $\left\{\mathbb{P},\mathbb{Q},A,B,{T}_{i}\right\}$ is the membership of ${U}_{i}$ for obtaining access to the application services provided by a specific AS.

Verify.

1) ${U}_{i}\Rightarrow AS:\left\{\mathbb{P},\mathbb{Q},A,B,{T}_{i}\right\}$ over a secure channel.

2) Let ${T}_{V}$ be the current timestamp of the AS and ${T}_{td}$ be an appropriate tolerance in the time delay. Given the group public key Y, the AS can verify the membership proof presented by a member ${U}_{i}$ , and ${U}_{i}$ is granted access rights if the following Equations ((8) and (9)) hold; otherwise, the AS rejects the request of ${U}_{i}$ :

${T}_{V}-{T}_{i}\le {T}_{td}$ (8)

$\stackrel{^}{e}\left(\mathbb{P},\mathbb{Q}\right)\equiv Y\times \stackrel{^}{e}\left(tB,\mathbb{Q}\right)$ (9)

The scheme enables the AS to validate ${U}_{i}$ ’s claim while learning nothing about their real identity, even if it colludes with the KGC. For the purpose of anonymous authentication and strong unlinkability, two blinding factors and a timestamp are employed so that a member can prove their membership multiple times to the same or to a different AS. All the authentication messages $\left\{\mathbb{P},\mathbb{Q},A,B,{T}_{i}\right\}$ cannot be linked to reveal that they are all generated by the same member. Cryptanalysis of this enhanced scheme is presented in Section 4.

3.3.1. Detection of Illegal Privilege Transfer

The member ${U}_{i}$ is assumed to be able to send the transformed private key $\left\{\gamma {a}_{i}P,{\gamma}^{-1}{b}_{i}Q\right\}$ to their friend ${U}_{x}$ , who can be either a trusted or an untrusted individual, where $\gamma $ is a random number and $\gamma \ne 1$ . After obtaining the transformed private key, ${U}_{x}$ computes $A=\alpha \beta P$ , $B=\alpha P$ , $\mathbb{P}={\beta}^{-1}\gamma {a}_{i}P+$ $t\alpha P$ , and $\mathbb{Q}=\beta {\gamma}^{-1}{b}_{i}Q$ , where $t=h\left({T}_{x}\right)$ . The unprivileged party ${U}_{x}$ can prove their membership to the AS through the aforementioned improved anonymous authentication scheme and obtain access to the resource on the AS if Equations ((8) and (9)) hold. Here, collusion between the AS and ${U}_{x}$ that threatens the original member ${U}_{i}$ ’s privacy is impossible. As mentioned in Section 3.2.1, two approaches exist for detecting whether a member ${U}_{i}$ is involved in an unauthorized privilege transfer. The first is to let ${U}_{x}$ disclose ${U}_{i}$ ’s illegal privilege transfer by providing $\left\{\gamma {a}_{i}P,{\gamma}^{-1}{b}_{i}Q\right\}$ to the KGC; however, this approach is passive and impractical for preventing private keys from being transformed. The second is that the trusted KGC can be consulted online to recognize the privilege transfer as follows. Recall that the KGC retains ${a}_{i}$ and ${b}_{i}$ when generating private keys for each member ${U}_{i}$ . If the AS provides a suspicious $\left\{\mathbb{P},\mathbb{Q},A,B,{T}_{i}\right\}$ to the KGC for investigating potential privilege transfer, the KGC attempts to use all values of ${b}_{i}$ , for $1\le i\le N$ , of registered members and computes both

${\pi}_{i}=\stackrel{^}{e}\left(B,{\mathbb{Q}}^{{b}_{i}{}^{-1}}\right)=\stackrel{^}{e}{\left(P,Q\right)}^{\alpha \beta {\gamma}^{-1}}$ (10)

and

${\lambda}_{i}=\stackrel{^}{e}\left(A,Q\right)=\stackrel{^}{e}{\left(P,Q\right)}^{\alpha \beta}\text{.}$ (11)

The KGC checks whether any ${\pi}_{i}$ equals to determine whether the received authentication message was generated by privileged member. Clearly, the aforementioned authentication message generated from a transformed private key with fails to pass the verification. We can conclude that the received authentication message is an impersonated membership and that someone has shared their private key and privilege with another, but the KGC does not know who is the traitor at this stage because the proposed authentication scheme provides “anonymity”. Consequently, the KGC uses the information (,) to compute, for, as follows:

(12)

The KGC subsequently examines all values of, for, to determine whether any equals and thus discover the real identity and revoke the membership of the traitor who is involved in an unauthorized privilege transfer. This online detection approach can be performed regularly in case the AS has noticed that an unauthorized privilege transfer has occurred in the system.

3.3.2. Exclusiveness of the Membership

By employing the dynamic reversed accumulator of Kuo et al., which is described in Section 2.2, a member Alice who has been included in the set U receives a membership (,) and can therefore prove to the AS that her identity is not on the CRL; this is called “exclusiveness of the membership”. Of course, a dynamic public archive is required for storing information regarding joined and revoked members as well as the current accumulator ACC. Each member is assumed to read the archive regularly and update their witness when ACC has been changed. This accumulator performs more efficiently than existing methods because renewing the accumulator and valid members’ witnesses is required only when revoking violating members but not when adding new members. The AS thus does not have to verify whether a member is on the CRL in contrast to those presented in [6] [13] . Additionally, forging of the witness by an adversary is infeasible according to the strong RSA assumption [7] [27] .

In addition, the accumulator of Kuo et al. provides efficient multiwitness verification in which a group member may access multiple services or files simultaneously and the AS can verify the member’s qualifications simultaneously. This property is outstanding and has not been demonstrated in previous studies. Suppose that m services exist, namely, provided by various AS. The KGC must generate m accumulators in advance as for service, where. If Alice is permitted to access the services and both provided by the same AS, she may be assigned the witnesses (). Thus, Alice can convince the AS of the validity of her membership and gains access to services and by providing the corresponding witnesses and on the basis of the zero- knowledge proof technique. The AS must obtain the current accumulators and of services and and verify whether Alice is qualified to access these services through Equation (13):

(13)

4. Performance and Security Analysis

This section verifies our claim of an efficient, anonymous, and unlinkable membership authentication scheme. We first detail the security properties provided by our scheme. Note that some properties have been detailed in the aforementioned sections.

Resistance of replay attack

An adversary may attempt to resend a stolen membership tuple to pass verification. Recall that AS accepts a membership proof if Equation (8) holds (one of the necessary conditions); thus, resending a stolen membership tuple would increase the time of () and therefore the adversary cannot pass the verification.

Membership nontransferability

Recall that a valid member can send the transformed private key to their friend by adding a random number as. The unprivileged party can prove their validity to the AS by computing with the transformed private key. Through detection of illegal privilege transfer, as described in Section 3.3.1, the membership of any traitor who is involved in unauthorized privilege transfer will be revoked by the KGC. This can force the member not to share their private key and privilege with others; otherwise, any two of’s service requests can be linked and their anonymity will be ruined.

The following two lemmas from [29] [30] must be given before demonstrating theorems related to our scheme.

Lemma 1. The GPI is not harder than either FAPI-1 or FAPI-2.

Proof.

(FAPI-1 ⟹ GPI:)

Given a GPI instance Y and an element as input, call the FAPI-1 oracle and output; the FAPI-1 solver can solve the GPI problem.

(GPI ⇏ FAPI-1:)

By contrast, given an FAPI-1 instance as input, the GPI solver cannot solve the FAPI-1 problem.

We can similarly prove that GPI ≤ FAPI-2.

Lemma 2. If FAPI-j is solvable, then the computational Diffie-Hellman (CDH) problem in, , and is solvable.

Proof.

Let be the oracle to solve FAPI-j, for j = 1 or 2. Recall that returns and returns such that. Suppose that (, ,) is a CDH input in. Choose a and compute. Call FAPI-1 solver to obtain. Finally, compute and call FAPI-2 solver to obtain.

The other two cases (solving CDH in and) are similar.

Theorem 3 (Private key forgery freeness). Let be a polynomial-time adversary who is not in the group and who is assigned a parameter . The proposed scheme can withstand from private key forgery through the following manners of attack:

1) computing and with

2) choosing an element and finding with

3) choosing an element and finding with

4) extracting the group secret key X from the group public key Y.

Proof.

We discuss these cases of possible forgery in the following.

Case 1:

An adversary may attempt to find two elements and such that, for an unknown X. For to forge an eligible private key pair with a nonnegligible probability as follows is computationally infeasible:

(14)

The success of can be used to solve the GPI problem defined in Section 3.1.

Cases 2 & 3:

From Lemmas 1 and 2, we know that 1) the GPI problem is not harder than either FAPI-1 or FAPI-2 and 2) if FAPI-j (where j = 1 or 2) is solvable, then the CDH problem is solvable. That is, an who can succeed in cases 2 and 3 can be used to solve the problems of GPI and CDH.

Case 4:

Similarly, if can succeed in extracting the group secret key X from the group public key without knowledge of k prime numbers, then it can be used directly to solve the discrete logarithm (DL) problem in. Moreover, such an adversary can create any private key pair by computing and. That is, pairing inversion can be computed efficiently by in known pairing groups. This case has been discussed in [31] [32] and is known as the MOV reduction in that the DL in and can be solved in polynomial time if a DL oracle exists for. Breaking the DL in, , or is clearly harder than FAPI-j because intuitively breaking FAPI-j (where j = 1 or 2) involves only computing a group element in or and does not directly provide a method for recovering an exponent in, , or. □

From this reasoning, we know GPI ≤ FAPI-j

Theorem 4 (Resistance against membership impersonation). Let be a polynomial-time adversary with a valid private key. Given the system parameter, the proposed scheme can withstand an adversary engaging in a private key impersonation aimed at the other eligible members or the new member.

Proof.

If the adversary has ever joined the group, they may attempt to add a random number to the private key they received previously to find the private key of an eligible member such that and. Clearly, this attack cannot be recognized by the proposed illegal privilege transfer detection mechanism. This problem can be reduced to the selection of parameter k described in Section 3.2. We assume that k = 200, which yields combinations of the value. The probability that two assignments of the value for different members are identical is approximately 1/10^{59}, which is also the probability that the adversary can succeed in computing the valid private keys of eligible members and is negligible.

Finally, Table 1 illustrates the substantial improvement of our proposed scheme compared with other schemes for the security concerns that we mentioned and defined in Section 2.1. Our proposed scheme features strong unlinkability, nontransferability, dynamic membership, and traitor detection. Table 2 shows the main enhancement in efficiency achieved by our scheme. The computational cost of our scheme comprises that of the presented anonymous authentication scheme and the dynamic reversed accumulator of Kuo et al. [21] .

5. Conclusion

We propose a novel membership authentication scheme through which anonymity, strong unlinkability, and illegal privilege transfer detection are

Table 1. Comparison of security requirements.

Table 2. Comparison of computational costs.

*: number of eligible/revoked members,: time period, H: hash operation,: exponentiation in,: inverse modulo,: multiplication modulo,: multiplication in,: addition/subtraction over exponent, P: pairing operation,: squaring operation modulo n, Eu: extended Euclidean, and PK: proof of knowledge.

provided. As aforementioned discussion, our proposed scheme can perform more efficiently if the symmetric setting of bilinear map groups is applied. By employing an efficient dynamic reversed accumulator, system members can prove their membership exclusiveness of the CRL to the verifier. Additionally, the practicality and attractiveness of our proposed scheme is supported.

References

[1] Malik, Federal Financial Institutions Examination Council (2001) Authentication of Internet Banking Environment.

http://www.ffiec.gov

[2] Hu, V.C., Ferraiolom, D., Schnitzer, A., Sandlin, K., Miller, R. and Scarfone, K. (2013) Guide to Attribute Based Access Control (ABAC) Definition and Considerations. NIST Special Publication.

[3] Chaum, D. and van Heyst, E. (1991) Group Signatures. Advances in Cryptology— EUROCRYPT ’91, 547, 257-265.

[4] Camenisch, J. (1997) Efficient and Generalized Group Signatures. Advances in Cryptology—EUROCRYPT ’97, 1233, 465-479.

[5] Camenisch, J. (1998) Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem. Ph.D. Dissertation, Swiss Federal Institute of Technology, Zürich.

[6] Boneh, D., Boyen, X. and Shacham, H. (2004) Short Group Signatures. Advances in Cryptology—CRYPTO ’04, 3152, 41-55.

[7] Fujisaki, E. and Okamoto, T. (1997) Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations. Advances in Cryptology—CRYPTO’97, 1294, 16-30.

[8] Lee, Y.K., Lee, S., Lee, S.J., Hwang, J.Y., Chung, B.H. and Lee, D.G. (2010) Anonymous Access Control Framework Based on Group Signature. Proceedings of the 2nd International Conference on Information Technology Convergence and Services, Cebu, 11-13 August 2010, 1-5.

[9] Zheng, H., Zhao, Z. and Zhang, X. (2012) Access Control Based on Group Signatures in Cloud Service. IEEE International Conference on Computer Science and Automation Engineering, 2, 316-320.

[10] Hu, X. (2014) Cost-Effective Scalable and Anonymous Certificateless Remote Authentication Protocol. IEEE Transactions on Information Forensics and Security, 9, 2327-2339.

[11] He, D., Zeadally, S., Kumar, N. and Lee, J.H. (2016) Anonymous Authentication for Wireless Body Area Networks with Provable Security. IEEE Systems Journal, 11, 2590-2601.

[12] Song, D. (2001) Practical Forward-Secure Group Signature Schemes. Proceedings of ACM Symposium on Computer and Communication Security, Philadelphia, 5-8 November 2001, 225-234.

https://doi.org/10.1145/501983.502015

[13] Ateniese, G., Song, D. and Tsudik, G. (2002) Quasi-Efficient Revocation of Group Signatures. Proceedings of the 6th International Conference on Financial Cryptography, Southampton, 11-14 March 2002, 183-197.

https://doi.org/10.1007/3-540-36504-4_14

[14] Chor, B., Fiat, A. and Naor, M. (1994) Tracing Traitors. Advances in Cryptology, Wollongong, 28 November-1 December 1994, 257-270.

[15] Mitsunari, S., Sakai, R. and Kasahara, M. (2002) A New Traitor Tracing. IEICE Transactions on Fundamentals, E85-A, 481-484.

[16] Tô, V.D., Safavi-Naini, R. and Zhang, F. (2003) New Traitor Tracing Schemes using Bilinear Map. Proceedings of ACM Workshop on Digital Rights Management, Washington DC, 27 October 2003, 67-76.

[17] Boneh, D., Sahai, A. and Waters, B. (2006) Fully Collusion Resistant Traitor Tracing with Short Ciphertexts and Private Keys. Advances in Cryptology, Santa Barbara, 20-24 August 2006, 573-592.

[18] Boneh, D. and Naor, M. (2008) Traitor Tracing with Constant Size Ciphertext. Proceedings of 15th ACM Conference on Computer and Communications Security, Alexandria, 27-31 October 2008, 501-510.

https://doi.org/10.1145/1455770.1455834

[19] Camenisch, J. and Lysyanskaya, A. (2002) Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. Advances in Cryptology, Santa Barbara, 18-22 August 2002, 61-76.

[20] Camenisch, J., Kohlweiss, M. and Soriente, C. (2009) An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials. Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, 18-20 March 2009, 481-500.

https://doi.org/10.1007/978-3-642-00468-1_27

[21] Kuo, T.M., Yen, S.M. and Han, M.C. (2017) Dynamic Reversed Accumulator. International Journal of Information Security, 1-9.

https://doi.org/10.1007/s10207-017-0360-6

[22] Benaloh, J. and de Mare, M. (1993) One-Way Accumulators: A Decentralized Alternative to Digital Signatures. Advances in Cryptology, Santa Barbara, 22-26 August 1993, 274-285.

[23] Nguyen, L. (2005) Accumulators from Bilinear Pairings and Applications. Proceedings of the Cryptographers’ Track at the RSA Conference 2009 on Topics in Cryptology, San Francisco, 20-24 April 2009, 275-292.

https://doi.org/10.1007/978-3-540-30574-3_19

[24] Li, J., Li, N. and Xue, R. (2007) Universal Accumulators with Efficient Non-Membership Proofs. Proceedings of the 5th International Conference on Applied Cryptography and Network Security, Zhuhai, 5-8 June 2007, 253-269.

https://doi.org/10.1007/978-3-540-72738-5_17

[25] Au, M.H., Tsang, P.P., Susilo, W. and Mu, Y. (2009) Dynamic Universal Accumulators for DDH Groups and Their Application to Attribute-Based Anonymous Credential Systems. Proceedings of the Cryptographers’ Track at the RSA Conference 2009 on Topics in Cryptology, San Francisco, 20-24 April 2009, 295-308.

https://doi.org/10.1007/978-3-642-00862-7_20

[26] Mashatan, A. and Vaudenay, S. (2013) A Fully Dynamic Universal Accumulator. Proceedings of the Romanian Academy, 14, 269-285.

[27] Baric, N. and Pfitzmann, B. (1997) Collision-Free Accumulators and Fail-Stop Signature Schemes without Trees. Advances in Cryptology, Santa Barbara, 17-21 August 1997, 480-494.

[28] Miller, V. (2004) The Weil Pairing, and Its Efficient Calculation. Journal of Cryptology, 17, 235-261.

[29] Galbraith, S., Hess, F. and Vercauteren, F. (2008) Aspects of Pairing Inversion. IEEE Transactions on Information Theory, 54, 5719-5728.

[30] Kiraz, M.S. and Uzunkol, O. (2016) Still Wrong Use of Pairings in Cryptography. Cryptology ePrint Archive, Report 2016/223.

https://eprint.iacr.org/2016/223

[31] Frey, G. and Ruck, H.G. (1994) A Remark Concerning m-divisibility and the Discrete Logarithm in the Divisor Class Group of Curves. Mathematics of Computation, 62, 865-874.

[32] Menezes, A., Okamoto, T. and Vanstone, S. (1993) Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. IEEE Transactions on Information Theory, 39, 1639-1646.