© Wuhan University 2023

0 Introduction

In some special applications today, based on computational intelligence^[1,2], identity authentication requires anonymous authentication to protect user's privacy information^[3]. Anonymous authentication is divided into unconditional anonymous authentication and traceable anonymous authentication. Unconditional anonymous authentication can verify that the user belongs to an anonymous set, but the user's true identity cannot be obtained. At the same time, criminals often use unconditional anonymity to engage in criminal activities, since their true identity cannot be traced, they cannot be punished. In order to prevent illegal and criminal activities from being unable to trace their true identity, traceable anonymous authentication schemes have emerged.

Anonymous authentication is often accompanied by anonymous signature. Using ring signature^[4], with the help of an administrator and a verifier, Tian et al^[5] can trace the privacy identity of the authenticator. But the program only needs an administrator and a verifier to complete the tracing, which increases the risk of conspiracy attack. Using the democratic group signature^[6], Liu et al^[7] can trace the authenticator's privacy identity through cooperation with members whose number exceeds the threshold. However, the anonymous set size of the scheme is the total number of members n, and the authenticator cannot choose the anonymous set on its own. By using 1/n signature^[8], the authenticator can independently choose the anonymous set, so Yin et al^[9] can threshold trace the authenticator's privacy identity.

Anonymous authentication first needs to ensure the anonymity of users, and in some special applications, it is necessary to verify whether the identity authentication of the same person is the same in different occasions without disclosing the user's real identity. For example, anonymous electronic voting not only needs to ensure the anonymity of the voter's identity, but also needs to avoid repeated voting. But none of the above traceable anonymous authentication schemes have this linkable authentication. If the linkablity feature of ring signature is applied to anonymous authentication, linkable authentication can be achieved. Beullens et al^[10] constructed linkable ring signatures (LRS) from isogeny and lattice assumptions. However, either the speed of isogeny-based LRS is relatively slow,or the lattice based LRS has larger signatures. Liu et al^[11] proposed a linkable spontaneous anonymous group (LSAG) signature scheme, which enables two signatures of the same signer to be linked. In addition, they demonstrated the security of the signature using an improved bifurcation lemma. In this paper, based on the LSAG signature scheme, a selective linkable threshold tracing anonymous authentication scheme is proposed.

Based on the decisional Diffie-Hellman (DDH) assumption and discrete logarithm assumption, the proposed scheme can achieve linkable authentication without disclosing the user's real identity. The main contributions of this paper can be summarized as follows:

1) By embedding the linkable label to the authentication signature, the proposed scheme can achieve linkable authentication.

2) By using threshold joint tracing, the proposed scheme can realize anonymous tracing.

3) By the simulation experiment, the implementation time of the proposed scheme is slightly better than other similar schemes. Based on the DDH assumption and discrete logarithm assumption, the security of the scheme has been proven in the scheme analysis.

The rest of this paper is organized as follows. Some relevant basic theories are proposed in Section 1. A new anonymous authentication scheme is introduced in Section 2. Security analysis is provided in Section 3. Further analysis is performed in Section 4 and the conclusion is made in Section 5.

1 Preliminary

1.1 DDH Assumption

Let $G=<g>$ be a cyclic group of prime order q, which is determined by some security parameter n. For sufficient large q, define two 4-tuples $(g,g^a,g^b,g^{ab})$ and $(g,g^a,g^b,g^c)$, where $a,b,c{\in }_R{Z}_q$. The DDH problem is to distinguish the two tuples.

A probabilistic polynomial time (PPT) distinguisher D's advantage is defined as

$\mathrm{A}\mathrm{d}{\mathrm{v}}_{G,D}^{\mathrm{D}\mathrm{D}\mathrm{H}}(n)=|\mathrm{P}\mathrm{r}[D(g,g^a,g^b,g^{ab})=\mathrm{1}]$

$-\mathrm{P}\mathrm{r}[D(g,g^a,g^b,g^{ab})=\mathrm{1}]|$

If the advantage of any distinguisher $D$ is negligible in n, we say that the DDH assumption holds.

1.2 Linkable Ring Signature

Assuming that n users make up the ring $U=\{U_{\mathrm{1}},U_{\mathrm{2}},\cdots ,U_n\}$ , the public/private key pair for each user $U_i$ in the ring is $(x_i,y_i)$, signer $U_k$ uses its own private key $x_k$ and the public key collection of all members $\mathrm{U}\mathrm{A}=\{y_{\mathrm{1}}||y_{\mathrm{2}}||\cdots ||y_n\}$ to generate a ring signature on message m.

1) Ring signature generation algorithm

Enter the message m, public key set UA, the private key $x_k$ of signer $U_k$, and add the linkable label $\tilde{e}$. Output linkable ring signature $\sigma \leftarrow (m,$$y_{\mathrm{1}},y_{\mathrm{2}},\cdots ,y_n,x_k,\tilde{e})$.

2) Ring signature verification algorithm

Enter $\sigma \leftarrow (m,y_{\mathrm{1}},y_{\mathrm{2}},\cdots ,y_n,$$x_k,\tilde{e})$ output 0 or 1. 0 indicates that the signature is invalid, and 1 indicates that the signature is valid. The linkable ring signature needs to meet the following properties.

• Correctness: Any member of the ring can execute the ring signature generation algorithm and pass the ring signature verification algorithm.

• Anonymity: The probability of identifying ring membership by ring signature is less than 1/n, that is, ring membership remains anonymous.

• Unforgeability: Illegal members falsify the signature $\sigma \leftarrow (m,y_{\mathrm{1}},y_{\mathrm{2}},\cdots ,y_n,x_k^{\text{'}},{\tilde{e}}^{\text{'}})$ of signer $U_k$, thus it is impossible to verify the algorithm by linkable ring signature.

• Linkability: If two signatures

$\sigma \leftarrow (m,y_{\mathrm{1}},y_{\mathrm{2}},\cdots ,y_n,x_k,\tilde{e})$

${\sigma }^{\text{'}}\leftarrow (m^{\text{'}},y_{\mathrm{1}}^{\text{'}},y_{\mathrm{2}}^{\text{'}},\cdots ,y_n^{\text{'}},x_k,\tilde{e})$

have the same linkable label $\tilde{e}$, it can be judged that the two signatures were signed by the same signer.

2 Proposed Anonymous Authentication Scheme

2.1 System Initialization

n members make up a collection of $U=\{U_{\mathrm{1}},U_{\mathrm{2}},\cdots ,U_n\}$, exposing {p,q,g,t,H,$\mathrm{I}{\mathrm{D}}_i$}. Among them, p and q are large prime numbers, and $q|p-\mathrm{1}$, g is the q-order element on $Z_q$, t is the threshold value, H is one-way hash function, $\mathrm{I}{\mathrm{D}}_i$ is the identity of the member $U_i$.

Step 1   Each $U_i$ randomly selects the $t-\mathrm{1}$ secondary polynomial $f_i(x)$, exposes the polynomial coefficient commitment $v_{ik}$, calculates $f_i(\mathrm{I}{\mathrm{D}}_j)$, and sends it to $U_j$ via a secure channel, retaining the $f_i(\mathrm{I}{\mathrm{D}}_i)$.

$f_i(x)={\displaystyle \sum _{k=\mathrm{0}}^{t-\mathrm{1}}}{a}_{ik}{x}^k\mathrm{m}\mathrm{o}\mathrm{d}q$(1)

$v_{ik}=g^{a_{ik}}\mathrm{m}\mathrm{o}\mathrm{d}p(k=\mathrm{0,1},\cdots ,t-\mathrm{1})$(2)

$v_{\mathrm{0}}={\displaystyle \sum _{i=\mathrm{1}}^n}{v}_{i\mathrm{0}}\mathrm{m}\mathrm{o}\mathrm{d}q=g^{a_{\mathrm{0}}}\mathrm{m}\mathrm{o}\mathrm{d}p$(3)

Step 2   $U_j$ checks the correctness of $f_i(\mathrm{I}{\mathrm{D}}_j)$ through formula (4) , calculates the private key $x_j$ according to formula (5) and keeps secret, $y_j$ will be disclosed as the public key. Other members can verify the correctness of $y_j$ through the formula (7).

$g^{f_i(\mathrm{I}{\mathrm{D}}_j)}={\displaystyle \prod _{k=\mathrm{0}}^{t-\mathrm{1}}}{v_{ik}}^{\mathrm{I}{{\mathrm{D}}_j}^k}\mathrm{m}\mathrm{o}\mathrm{d}p$(4)

$x_j={\displaystyle \sum _{i=\mathrm{1}}^n}{f}_i(I{D}_j)\mathrm{m}\mathrm{o}\mathrm{d}q$(5)

$y_j={\mathrm{g}}^{x_j}\mathrm{m}\mathrm{o}\mathrm{d}p$(6)

$y_j={\displaystyle \prod _{i=\mathrm{1}}^n}{\displaystyle \prod _{k=\mathrm{0}}^{t-\mathrm{1}}}{v_{ik}}^{\mathrm{I}{{\mathrm{D}}_j}^k}\mathrm{m}\mathrm{o}\mathrm{d}p$(7)

2.2 Anonymous Authentication

Suppose the message that needs to be signed is $m\in {\{\mathrm{0,1}\}}^{*}$, and the public key set is $\mathrm{U}\mathrm{A}=\{y_{\mathrm{1}}||y_{\mathrm{2}}||\cdots$$||y_n\}$. The authenticator $U_k$ uses the private key $x_k$ and the public key set UA to generate the signature σ using the linkable ring signature^[11], and sends σ to the verifier $U_v$. If the result outputs 1, $U_k$ belongs to the collection U, otherwise it does not belong to the collection U. The authentication process consists of two algorithms: signature generation and signature authentication.

1) Signature generation

The authenticator $U_k$ follows the steps below.

Step 1   Select random number $t_k,r\in Z_q$, calculate and expose $T_k$, $W_k$ and linkable label $\tilde{e}$.

$T_k=g^{t_{\mathrm{k}}}\mathrm{m}\mathrm{o}\mathrm{d}p$(8)

$W_k=v_{\mathrm{0}}^{t_k}{y}_k\mathrm{m}\mathrm{o}\mathrm{d}p$(9)

$\tilde{e}=t_k^{-\mathrm{1}}r\mathrm{m}\mathrm{o}\mathrm{d}p$(10)

Step 2   For $i=k$, select random number $u\in Z_q$ and secure Hash function $H_i:{\{\mathrm{0,1}\}}^{\mathrm{*}}\to Z_q$, calculate $c_{k+\mathrm{1}}$.

$c_{k+\mathrm{1}}=H_{k+\mathrm{1}}(\mathrm{U}\mathrm{A}||m||\tilde{e}||g^u\mathrm{m}\mathrm{o}\mathrm{d}p)$(11)

For $i=k+\mathrm{1},\cdots ,n,\mathrm{1},\cdots ,k-\mathrm{1}$, select random number $s_i\in Z_q$, calculate $c_{i+\mathrm{1}}$, make $H_{n+\mathrm{1}}=H_{\mathrm{1}}$.

$c_{i+\mathrm{1}}=H_{i+\mathrm{1}}(\mathrm{U}\mathrm{A}||m||\tilde{e}||g^{s_i}{T}_k^{c_i}{y}_i^{c_i}\mathrm{m}\mathrm{o}\mathrm{d}p)$(12)

Step 3   Calculate $s_k$.

$s_k=u-(t_k+x_k)c_k\mathrm{m}\mathrm{o}\mathrm{d}q$(13)

Step 4   Generate the signature ${\sigma }_L(m)$ and send it to the verifier $U_v$.

${\sigma }_L(m)=(c_{\mathrm{1}},H_{\mathrm{1}},\cdots ,H_n,s_{\mathrm{1}}\cdots ,s_n,\tilde{e},r)$(14)

2) Signature authentication

The verifier $U_v$ receives the signature ${\sigma }_L(m)$, and verifies the correctness of the ring signature.

For $i=\mathrm{1,2},\cdots ,n$,$z_i$ is calculated in (15) and $c_{i+\mathrm{1}}$$(i\ne n)$ is calculated in accordance with the formula (16). If the formula (17) is established and the signature is correct, $U_k$ belongs to set U, output 1. Otherwise, $U_k$ does not belong to set U, output 0.

$z_i=g^{s_i}{T}_k^{c_i}{y}_i^{c_i}\mathrm{m}\mathrm{o}\mathrm{d}p$(15)

$c_{i+\mathrm{1}}=H_{i+\mathrm{1}}(\mathrm{U}\mathrm{A}||m||\tilde{e}||z_i\mathrm{m}\mathrm{o}\mathrm{d}p)$(16)

$c_{\mathrm{1}}=H_{n+\mathrm{1}}(\mathrm{U}\mathrm{A}||m||\tilde{e}||z_n\mathrm{m}\mathrm{o}\mathrm{d}p)$(17)

2.3 Linkable Authentication

In different situations, the authenticator may produce a different signature. To prevent consistency attacks, two different signatures need to be non-related. However, on special occasions, such as anonymous electronic voting systems, anonymous authentication requires linkable authentication in order to prevent duplicate voting.

Two different authentication signatures are ${\sigma }_{L\mathrm{1}}(m_{\mathrm{1}})$ and ${\sigma }_{L\mathrm{2}}(m_{\mathrm{2}})$.

${\sigma }_{L\mathrm{1}}(m_{\mathrm{1}})=(c_{\mathrm{1}}^{\text{'}},H_{\mathrm{1}}^{\text{'}},\cdots ,H_n^{\text{'}},s_{\mathrm{1}}^{\text{'}}\cdots ,s_n^{\text{'}},\tilde{e},r)$(18)

${\sigma }_{L\mathrm{2}}(m_{\mathrm{2}})=(c_{\mathrm{1}},H_{\mathrm{1}},\cdots ,H_n,s_{\mathrm{1}}\cdots ,s_n,\tilde{e},r)$(19)

If the authenticator uses the same $(\tilde{e},r)$, anonymous authentication is relevant. Otherwise, it is not. The authenticator determines whether the anonymous identity is relevant by verifying that two different anonymous authentications have the same $(\tilde{e},r)$.

2.4 Anonymous Tracing

Linkable authentication can only prove whether two authentication are relevant and does not obtain the true identity of the authenticator. In some cases, the anonymous identity of the authenticator also needs to be traced. For example, in the anonymous electronic voting system, some users use anonymous identities to repeatedly vote. At this time, it is necessary to trace the anonymous identities of such users. In order to prevent random tracing, this scheme uses threshold joint tracing.

Assume that the t members $u_i(\mathrm{1}\le i\le t)$ consist of an anonymous trace set $\mathrm{U}\mathrm{T}=\{U_{\mathrm{1}},U_{\mathrm{2}},\cdots ,U_t\}$, and follow the steps below.

Step 1   Use private key $x_i(\mathrm{1}\le i\le t)$ and $T_k$ to jointly calculate $E_k$.

$E_k={\displaystyle \prod _{i=\mathrm{1}}^t}{T_k}^{x_i{h}_i}\mathrm{m}\mathrm{o}\mathrm{d}p$(20)

In the formula,

$h_i={\displaystyle \prod _{\begin{array}{l}j=\mathrm{1}\\ j\ne i\end{array}}^t}\frac{-\mathrm{I}\mathrm{D}{}_j{}^{}}{\mathrm{I}{\mathrm{D}}_i-\mathrm{I}{\mathrm{D}}_j}\mathrm{m}\mathrm{o}\mathrm{d}q$(21)

Step 2   Query the public $W_k$, calculate the identity information of the authenticator $y_k$ according to formula (22).

$\frac{W_k}{E_k}\mathrm{m}\mathrm{o}\mathrm{d}p=y_k$(22)

3 Characteristics Analysis

Theorem 1   (Anonymous authentication) Under DDH assumption, the authenticator's anonymous identity can pass authentication.

Proof   It is available by formula (12), when $i=k+\mathrm{1},\cdots ,$$n,\mathrm{1},\cdots ,k-\mathrm{1}$,

$c_{k+\mathrm{2}}=H_{k+\mathrm{2}}(\mathrm{U}\mathrm{A}||m||\tilde{e}||g^{s_{k+\mathrm{1}}}{T}_k^{c_{k+\mathrm{1}}}{y}_{k+\mathrm{1}}^{c_{k+\mathrm{1}}}\mathrm{m}\mathrm{o}\mathrm{d}p)$

︙

$c_{n+\mathrm{1}}=H_{n+\mathrm{1}}(\mathrm{U}\mathrm{A}||m||\tilde{e}||g^{s_n}{T}_k^{c_n}{y}_n^{c_n}\mathrm{m}\mathrm{o}\mathrm{d}p)$

︙

$c_k=H_k(\mathrm{U}\mathrm{A}||m||\tilde{e}||g^{s_{k-\mathrm{1}}}{T}_k^{c_{k-\mathrm{1}}}{y}_{k-\mathrm{1}}^{c_{k-\mathrm{1}}}\mathrm{m}\mathrm{o}\mathrm{d}p)$

When $i=k$, it is available by formula (11) and (13),

$c_{k+\mathrm{1}}=H_{k+\mathrm{1}}(\mathrm{U}\mathrm{A}||m||\tilde{e}||g^u\mathrm{m}\mathrm{o}\mathrm{d}p)$

$=H_{k+\mathrm{1}}(\mathrm{U}\mathrm{A}||m||\tilde{e}||g^{s_k+(t_k+x_k)c_k}\mathrm{m}\mathrm{o}\mathrm{d}p)$

$=H_{k+\mathrm{1}}(\mathrm{U}\mathrm{A}||m||\tilde{e}||g^{s_k}{T}_k^{c_k}{y}_k^{c_k}\mathrm{m}\mathrm{o}\mathrm{d}p)$

It can be seen that $c_{k+\mathrm{1}}(i=k)$ is consistent with $\left\{c_i\right\}$$(i=k+\mathrm{1},\cdots ,n,\mathrm{1},\cdots ,k-\mathrm{1})$, that is, the sequence $\left\{c_i\right\}(i=\mathrm{1},$$\mathrm{2},\cdots ,n)$ is consistent during the generation and authentication of ring signatures, so there is

$c_{n+\mathrm{1}}=H_{n+\mathrm{1}}(\mathrm{U}\mathrm{A}||m||\tilde{e}||g^{s_n}{T}_k^{c_n}{y}_n^{c_n}\mathrm{m}\mathrm{o}\mathrm{d}p)=H_{\mathrm{1}}(UA||m||\tilde{e}||g^{s_n}{T}_k^{c_n}{y}_n^{c_n}\mathrm{m}\mathrm{o}\mathrm{d}p)=c_{\mathrm{1}}$

formula (17) is valid, $U_k$ can pass authentication.

During the signature generation process, the $s_i\in Z_q$$(i=\mathrm{1,2},\cdots ,k,k-\mathrm{1},\cdots ,n)$ contained in the signature sent by the authenticator is randomly selected and evenly distributed on $Z_q$. Therefore, the probability that the verifier calculates the true identity of the authenticator from the authentication signature ${\sigma }_L(m)$ is $\mathrm{1}/q^n$ which is negligible. That is, the authenticator's identity can pass anonymous authentication.

Theorem 2   (Signature unforgeability) Under adaptive chosen message and selective public key attack, signature generation satisfies unforgeability.

Proof   Referring to the non-counterfeiting proof method^[12], it is assumed that there is a probabilistic polynomial algorithm PPT, a stochastic predictor $H_i(i=\mathrm{1,2},$$\cdots ,n)$, and a signature prophecy machine $\mathrm{S}\mathrm{O}(m,\mathrm{U}\mathrm{A})$. Counterfeiter A can simulate signature prophecy machine $\mathrm{S}\mathrm{O}$ through PPT simulator sim, get each $H_i$, and in line with the signature prophecy machine $\mathrm{S}\mathrm{O}$ prophecy. Because the private key $x_i$ cannot be obtained, A only uses $H_i$ and $\mathrm{S}\mathrm{O}$ to simulate the signature generation process, and generate a signature $\sigma$. A follows the steps below.

Step 1   Randomly select $c_i\in Z_q$$(i=\mathrm{1,2},\cdots ,n),t_k,r\in$$Z_q$, and compute $\tilde{e}=t_k^{-\mathrm{1}}r\mathrm{m}\mathrm{o}\mathrm{d}p$ and $T_k=g^{t_k}\mathrm{m}\mathrm{o}\mathrm{d}p$.

Step 2   For $i=k,\cdots ,n,\mathrm{1},\cdots ,k-\mathrm{2}$, randomly select $s_i\in Z_q$, calculate $z_i=g^{S_i}{T}_k^{c_i}{y}_i^{c_i}\mathrm{m}\mathrm{o}\mathrm{d}p$, $c_{i+\mathrm{1}}=H_{i+\mathrm{1}}(\mathrm{U}\mathrm{A}||m||\tilde{e}||$$z_i)$. Among them, let $H_{n+\mathrm{1}}=H_{\mathrm{1}}$.

Step 3   Let $H_k(\mathrm{U}\mathrm{A}||m||\tilde{e}||z_{k-\mathrm{1}})=c_k$, find $z_{k-\mathrm{1}}$, and then find $s_{k-\mathrm{1}}$.

Step 4   Output signature

$\sigma =(c_{\mathrm{1}},H_{\mathrm{1}},\cdots ,H_n,s_{\mathrm{1}},\cdots ,s_n,\tilde{e},r)$

When A forges signature $\sigma$, it is necessary to inquire $H_i$n times $Q_{i_{\mathrm{1}}},Q_{i_{\mathrm{2}}},\cdots ,Q_{i_n}$, $\mathrm{1}\le i_{\mathrm{1}}<i_{\mathrm{2}}<\cdots <i_n$. A's inquiry about $\mathrm{S}\mathrm{O}$ is negligible. Assuming that q-th$Q_{q_{\mathrm{1}}},Q_{q_{\mathrm{2}}},\cdots ,Q_{q_n}$ are the n inquiries that satisfy the consistency with the validation equation, where $Q_{q_k}$ is an inquiry into the stochastic predictor $H_k$ satisfying $Q_{q_k}\to H_k(\mathrm{U}\mathrm{A}||m||\tilde{e}||g^{s_{k-\mathrm{1}}}{T}_k^{c_{k-\mathrm{1}}}{y}_{k-\mathrm{1}}^{c_{k-\mathrm{1}}}\mathrm{m}\mathrm{o}\mathrm{d}p)$, k is a gap in the ring signature $\sigma$. So, A forges signature $\sigma$ for (q,k)-forged signature.

At the beginning of the simulation, A selects a pair(q,k) through sim, and can query the stochastic predictor $H_i(i=\mathrm{1,2},\cdots ,n)$ up to $q_h$ times, and the signature prophecy machine $\mathrm{S}\mathrm{O}(m,\mathrm{U}\mathrm{A})$ can be asked for up to $q_s$ times. Within the time $\epsilon$, A takes the probability $\delta$ to ensure that the q-th query is in accordance with the authentication process, and receives

$Q_{q_k}\to H_k(\mathrm{U}\mathrm{A}||m||\tilde{e}||z_{k-\mathrm{1}}\mathrm{m}\mathrm{o}\mathrm{d}p)$

$Q_{q_{k+\mathrm{1}}}\to H_{k+\mathrm{1}}(\mathrm{U}\mathrm{A}||m||\tilde{e}||z_k\mathrm{m}\mathrm{o}\mathrm{d}p)$

where $\delta \ge \frac{\mathrm{1}}{n(q_h+n{q}_s)Q(k)}$, $Q(k)$ is a polynomial function, $q_h$ and $q_s$ can only carry on polynomial secondary growth under the security parameter k.

When asked about $Q_{q_k}$, authentication-related queries have occurred and the sim returns the value of $c_k$. Let $H_k(\mathrm{U}\mathrm{A}||m||\tilde{e}||z_{k-\mathrm{1}})=c_k$, A finds $z_{k-\mathrm{1}}$, then A finds $s_{k-\mathrm{1}}$ from $z_{k-\mathrm{1}}=g^{s_{k-\mathrm{1}}}{T}_k^{c_{k-\mathrm{1}}}{y}_{k-\mathrm{1}}^{c_{k-\mathrm{1}}}\mathrm{m}\mathrm{o}\mathrm{d}p$, and finally creates ring signature

$\sigma =(c_{\mathrm{1}},H_{\mathrm{1}},\cdots ,H_n,s_{\mathrm{1}},\cdots ,s_n,\tilde{e},r).$

However, we found that the signature forgery process is in contradiction with the difficulty in solving discrete logarithm. Therefore, the signature generation satisfies unforgeability.

Theorem 3   (Linkable authentication) For a signature ${\sigma }_L(m)=(c_{\mathrm{1}},H_{\mathrm{1}},\cdots ,H_n,s_{\mathrm{1}},\cdots ,s_n,\tilde{e},r)$, forger A is unlikely to falsify another signature associated with the same linkable label of the authenticator ${\sigma }_{L^{\text{'}}}(m^{\text{'}})=(c_{\mathrm{1}}^{\text{'}},$$H_{\mathrm{1}}^{\text{'}},\cdots ,H_n^{\text{'}},s_{\mathrm{1}}^{\text{'}},\cdots ,s_n^{\text{'}},\tilde{e},r)$.

Proof   Based on the understanding of linkability in Section 2.3, if the $(\tilde{e},r)$ of two signatures are the same, the two signatures are relevant. Under normal circumstances, when anonymous authentication occurs, if the two generated signatures need to be linkable, the authenticator will choose the same $(\tilde{e},r)$ by himself. Therefore, the main task of the proof is that the forger A cannot falsify another signature with the same $(\tilde{e},r)$ associated with the identity of the authenticator.

As can be seen from Theorem 2, non-ring members can not falsify the legal signature, so the following is mainly to prove that other members outside the ring can not falsify the legal signature associated with the authenticator.

Known the authenticator $U_k$ has produced a legitimate signature ${\sigma }_L(m)=(c_{\mathrm{1}},H_{\mathrm{1}},\cdots ,H_n,s_{\mathrm{1}},\cdots ,s_n,\tilde{e},r)$, forger A forged the signature ${\sigma }_L(m^{\text{'}})=(c_{\mathrm{1}}^{\text{'}},H_{\mathrm{1}}^{\text{'}},\cdots ,H_n^{\text{'}},s_{\mathrm{1}}^{\text{'}}$ ,$\cdots ,s_n^{\text{'}},\tilde{e},r)$ associated with ${\sigma }_L(m)$. From the proof of Theorem 2, A needs to find $s_{k-\mathrm{1}}^{\text{'}}$ from $z_{k-\mathrm{1}}^{\text{'}}=g^{s_{k-\mathrm{1}}^{\text{'}}}{T}_k^{c_{k-\mathrm{1}}^{\text{'}}}{y}_{k-\mathrm{1}}^{c_{k-\mathrm{1}}^{\text{'}}}$$\mathrm{m}\mathrm{o}\mathrm{d}p$, which is in contradiction with the difficulty in solving discrete logarithm at the present stage. Therefore, the anonymous authentication of this scheme has linkable authentication.

Theorem 4   (Threshold traceability) The threshold number of members can jointly trace the identity of the authenticator.

When the identity of the authenticator needs to be traced, each member of t tracing members use the private key $x_i$ and the identification $\mathrm{I}{\mathrm{D}}_i$ to jointly calculate E_k, the identity of $y_k$ is obtained by the formula (22). According to (20), (8), (21), (3), we have

$E_k={\displaystyle \prod _{i=\mathrm{1}}^t}{T_k}^{x_i{h}_i}\mathrm{m}\mathrm{o}\mathrm{d}p$

$=g^{t_k{\displaystyle \sum _{i=\mathrm{1}}^t}{x}_i{h}_i}\mathrm{m}\mathrm{o}\mathrm{d}p$

$=g^{t_k{a}_{\mathrm{0}}}\mathrm{m}\mathrm{o}\mathrm{d}p$

$=g^{a_{\mathrm{0}}{t}_k}\mathrm{m}\mathrm{o}\mathrm{d}p$

$=v_{\mathrm{0}}^{t_k}\mathrm{m}\mathrm{o}\mathrm{d}p$

By (22) and (9), we get

$\frac{W_k}{E_k}\mathrm{m}\mathrm{o}\mathrm{d}p=y_k$

4 Further Analysis

4.1 Property Comparison

Compared with the threshold traceable anonymous authentication scheme mentioned in the preface, the proposed scheme has the properties of anonymous authentication, signature unforgeability, threshold traceability, linkable authentication, as shown in Table 1.

4.2 Computational Cost Comparison

The following mainly compares this scheme with Liu et al's scheme^[7] and Yin et al's scheme^[9] at the computational cost. Assuming that T_exp represents the calculation cost of the modulus index, T_mul represents the cost of the modulus multiplication calculation, and the time complexity of the modulus plus, XOR, or other operations is quite small and negligible. n is the number of members, t is the threshold value, and d is the size of the anonymous collection. In the initialization stage, both the proposed scheme and Liu et al's schemeadopt the secret sharing method without trusted center to compute member's private and public keys at the cost of $n(t-\mathrm{1})T_{\mathrm{m}\mathrm{u}\mathrm{l}}+n(t-\mathrm{2})T_{\mathrm{e}\mathrm{x}\mathrm{p}}$, while Yin et al's scheme allows members to choose their own keys and then collaborate to generate the system's key at the cost of $(t-\mathrm{1})T_{\mathrm{m}\mathrm{u}\mathrm{l}}+(\mathrm{2}n+\mathrm{3}t)T_{\mathrm{e}\mathrm{x}\mathrm{p}}$. In the anonymous authentication stage, the proposed scheme uses the linkable ring signature, and the calculation cost is $(\mathrm{2}n+\mathrm{1})T_{\mathrm{m}\mathrm{u}\mathrm{l}}+(\mathrm{6}n+\mathrm{2})T_{\mathrm{e}\mathrm{x}\mathrm{p}}$. In the anonymous tracing stage, the proposed scheme uses threshold tracing, and the calculation cost is $T_{\mathrm{m}\mathrm{u}\mathrm{l}}+t{T}_{\mathrm{e}\mathrm{x}\mathrm{p}}$. See Table 2 for details.

The data in Table 2 shows that the calculation cost of this scheme is similar to that of Liu et al's scheme at various stages, and the anonymous authentication stage is even smaller. On the premise of similar calculation cost, this scheme also has linkable authentication, which is more suitable for special applications such as anonymous electronic voting.

4.3 Simulation Experiment

By the simulation experiment, the proposed scheme is compared with Liu et al's scheme^[7] and Yin et al's scheme^[9] for execution time. The elliptic curve $E:y^{\mathrm{2}}=x^{\mathrm{3}}$$+x(\mathrm{m}\mathrm{o}\mathrm{d}p)$^[13] with the finite field $F{}_p{}^{}$ is chosen, where p is a large prime number of 512 bits. The hardware of the simulation is i3-8100T CPU, 8 GB RAM and the software is Windows 10 64 bits OS, codeblocks-17.12 software. The execution time of the three schemes is shown in Fig.1. Figure 1(a) shows the execution time required for anonymous authentication, and Fig.1(b) shows the execution time required for anonymous tracing.

Fig. 1 Execution time for three schemes

From Fig.1(a), we can see that in the anonymous authentication process, the execution time of the proposed scheme is slightly longer than that of Yin et al's scheme, but much shorter than that of Liu et al's. Figure 1(b) shows that the execution time of anonymous tracing in the proposed scheme is shorter than that of the other two schemes. Therefore, the implementation time of the proposed scheme is slightly better than that of the other two schemes.

5 Conclusion

The selectively linkable threshold tracing anonymous authentication scheme proposed in this paper, with the help of the linkable ring signature, adds the linkable tag to the authentication signature, which can not only can realize the threshold tracing, but also realize linkable authentication. In the special application of anonymous authentication and linkable authentication, such as anonymous electronic voting, this scheme has a good application prospect.

References

All Tables

All Figures

	Fig. 1 Execution time for three schemes
In the text