Issue 
Wuhan Univ. J. Nat. Sci.
Volume 28, Number 4, August 2023



Page(s)  317  323  
DOI  https://doi.org/10.1051/wujns/2023284317  
Published online  06 September 2023 
Computer Science
CLC number: TP309.7
An Anonymous Authentication Scheme with Selective Linkability and Threshold Traceability
^{1}
Information Engineering Faculty, Anhui Finance and Trade Vocational College, Hefei 230601, Anhui, China
^{2}
School of Computing and Artificial Intelligence, Hefei Normal University, Hefei 230601, Anhui, China
Received:
27
December
2022
In order to protect the user's privacy identity, authentication requires anonymous authentication. 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. However, in some applications, it is necessary to trace the true identity of the user. Therefore, a traceable anonymous authentication scheme is proposed. In order to prevent random tracing, the proposed scheme uses threshold joint tracing. When the identity of the authenticator needs to be traced, the threshold number of members can jointly trace the identity of the authenticator. In some special network applications such as anonymous electronic voting, in order to prevent repeated authentications and repeated elections, it is necessary to verify whether the two authentication signatures are signed by the same user without revealing the true identity of the user. Therefore, the proposed anonymous authentication scheme should have selective linkability. In order to achieve linkable authentication, the linkable tag is embedded by linkable ring signature. Compared with similar schemes through the simulation experiments, the implementation time of the proposed scheme is slightly better than other schemes.
Key words: anonymous authentication / traceability / threshold / ring signature / linkability
Biography: PU Guangning, male, Professor, research direction: information security. Email: pgn_578@126.com
Fundation item: Supported by the Key Natural Science Foundation of Anhui Higher Education Institutions (2022AH052536)
© Wuhan University 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
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 isogenybased 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 DiffieHellman (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 4tuples $(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}]$
$\text{}\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})$
$\text{}{\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 $qp\mathrm{1}$, g is the qorder element on ${Z}_{q}$, t is the threshold value, H is oneway 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\text{}(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}:\text{}{\{\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 nonrelated. 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}})$.
$\text{}{\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}$,
$\text{}{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)$
︙
$\text{}{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)$
︙
$\text{}{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)$
$\text{}={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)$
$\text{}={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)\text{}={H}_{\mathrm{1}}(UAm\tilde{e}{g}^{{s}_{n}}{T}_{k}^{{c}_{n}}{y}_{n}^{{c}_{n}}\mathrm{m}\mathrm{o}\mathrm{d}p)={c}_{\mathrm{1}}\text{}$
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 noncounterfeiting 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}\text{}$$(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}}\text{}\mathrm{m}\mathrm{o}\mathrm{d}\text{}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
$\text{}\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 qth${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 qth 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}}$, authenticationrelated 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, nonring 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\text{}$
$={g}^{{a}_{\mathrm{0}}{t}_{k}}\mathrm{m}\mathrm{o}\mathrm{d}p\text{}$
$={v}_{\mathrm{0}}^{{t}_{k}}\mathrm{m}\mathrm{o}\mathrm{d}p\text{}$
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.
Property comparison
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.
Computational cost comparison
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:\text{}{y}^{\mathrm{2}}={x}^{\mathrm{3}}$$+x\text{}(\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 i38100T CPU, 8 GB RAM and the software is Windows 10 64 bits OS, codeblocks17.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
 Yang J Q, Chen C H, Li J Y, et al. Compressedencoding particle swarm optimization with fuzzy learning for largescale feature selection[J]. Symmetry, 2022, 14(6): 1142. [NASA ADS] [CrossRef] [Google Scholar]
 Tang Y M, Pan Z F, Pedrycz W, et al. Viewpointbased kernel fuzzy clustering with weight information granules[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2023, 7(2): 342356. [CrossRef] [Google Scholar]
 Ateniese G, Herzberg A, Krawczyk H, et al. Untraceable mobility or how to travel incognito[J]. Computer Networks, 1999, 31(8):871884. [CrossRef] [Google Scholar]
 Rivest R L, Shamir A, Tauman Y. How to leak a secret[C]// Proceedings of ASIACRYPT'01. Berlin: SpringerVerlag, 2001: 552565. [Google Scholar]
 Tian Z J, Wang J L, Wu Y X. A dynamic anonymous authentication scheme with identity escrow[J]. Journal of Electronics & Information Technology, 2005, 27(11):17371740. [Google Scholar]
 Manulis M.Democratic group signature: On an example of joint ventures[C]// Proceedings of ACM Symposium on Information, Computer and Communications Security. New York: ACM Press, 2006: 191196. [Google Scholar]
 Liu F B, Zhang K, Li H, et al. Threshold traceability anonymous authentication scheme without trusted center for adhoc network[J]. Journal of Communications, 2012, 33(8): 208213. [Google Scholar]
 Abe M, Ohkubo M, Suzuki K. 1outofn signatures from a variety of keys[C]// Proceedings of ASIACRYPT'02. Berlin:SpringerVerlag, 2002: 415423. [Google Scholar]
 Yin F M, Hou Z F, Pu G N. Selfselecting share threshold traceable anonymous authentication scheme[J]. Journal of Wuhan University (Natural Science Edition), 2015, 61(6): 549553. [MathSciNet] [Google Scholar]
 Beullens W, Katsumata S, Pintore F. Calamari and falafl: logarithmic (linkable) ring signatures from isogenies and lattices[C]// Advances in CryptologyASIACRYPT 2020. Cham:SpringerVerlag, 2020: 464492. [MathSciNet] [Google Scholar]
 Liu J K, Wei V K, Wong D S. Linkable spontaneous anonymous group signature for ad hoc groups[C]// Australasian Conference on Information Security and Privacy. Berlin: SpringerVerlag, 2004: 325335. [Google Scholar]
 Zhang W F, Xiong D,Wang X M, et al. Selectively linkable and convertible ring signature based on RSA public key cryptosystem[J]. Chinese Journal of Computers, 2017, 40(5): 11681180. [MathSciNet] [Google Scholar]
 Ming Y, Shen X Q. PCPA: A practical certificateless conditional privacy preserving authentication scheme for vehicular ad hoc networks[J]. Sensors, 2018, 18(5): 15731596. [CrossRef] [PubMed] [Google Scholar]
All Tables
All Figures
Fig. 1 Execution time for three schemes 

In the text 
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.