An efficient certificateless anonymous signcryption communication scheme for vehicular adhoc network
Correctness analysis
Correctness of pseudonym verification
If registered member A generates their pseudonymous identity according to the agreed pseudonym generation algorithm, they can correctly pass the pseudonym verification of registered member B. The proof is as follows:
$$\beginaligned \beginaligned Y_A&=\phi _A r_A Pid_B_1 =\phi _A r_A \phi _B r_B P \\&=\phi _B r_B \phi _A r_A P = \phi _B r_B Pid_A_1 = Y_B \endaligned \endaligned$$
(1)
$$\beginaligned \beginaligned e(Pid_A_1,Pid_B_2)&=e(\phi _Ar_AP,\phi _BW_B) \\&=e(\phi _Aw_Ax_TP,\phi _Bw_BP) \\ &=e(x_TP,P)^\phi _Aw_A\phi _Bw_B \\&=e(\phi _Bw_Bx_TP,\phi _Aw_AP) \\ &=e(\phi _Br_BP,\phi _AW_A) \\ &=e(Pid_B_1,Pid_A_2) \endaligned \endaligned$$
(2)
Correctness of decryptionn
If registered member A uses the correct pseudonym identity and pseudonym public-private key for signcryption, then it can pass the decryption verification of registered member B correctly. The proof is as follows:
$$\beginaligned \beginaligned h_2&=H_2(\phi _Ar_APid_B_2)=H_2(\phi _Aw_Ax_T\phi _Bw_BP)\\&=H_2(\phi _Bw_Bx_T\phi _Aw_AP)=H_2(\phi _Br_BPid_A_2)=h’_2 \endaligned \endaligned$$
(3)
$$\beginaligned \beginaligned e(Sig_Pid_A,P)&=e(Q_P_A+h_1K_P_A,P) \\ &=e(\phi _As_AQ_A+h_1\phi _AK_A,P) \\&=e(\phi _As_Ax_AW_A+h_1\phi _AzW_A,P) \\ &=e(\phi _A(s_Ax_A+h_1z)W_A,P) \\&=e(\phi _AW_A,P)^ax_A+h_1z \\ &=e(\phi _AW_A,(s_Ax_A+h_1z)P) \\&=e(Pid_A_2,s_Ax_AP+h_1zP)\\ &=e(Pid_A_2,X_P_A+h_1P_hub) \endaligned \endaligned$$
(4)
Security analysis
Confidentiality
When member A communicates securely with member B, the encryption key is \(h_2=H_2(\phi _A r_A Pid_B_2)=H_2(\phi _B r_B Pid_A_2)\). If an attacker can obtain a parameter \(Q’\in G_1\) such that \(h_2=H_2(Q’)\), we consider the attacker to have compromised the encryption scheme described in this paper.
Theorem 1
Suppose there exists an adversary \(M_A\) that can, in polynomial time, break the encryption scheme described in this paper with a non-negligible advantage \(\mu (\lambda )\) through a bounded number of random oracle queries (assuming \(q_k\) queries for pseudonyms,parameters \(\phi _i\) , \(w_i\) and \(q_k(q_k-1)/2\) queries for ciphertexts), then there exists an algorithm \(M_B\) that can solve the Elliptic Curve Computational DiffieHellman (ECCDH) problem with advantage \(\frac2q_ke(q_k-1)^3\mu (\lambda )\), where e is a natural constant and \(\lambda\) is the system security parameter.
Proof
\(M_B\) first runs the Setup algorithm to establish the scheme described in this paper, publishing the public parameters \(params=<p,q,G_1,G_2,e,H_1,H_2,P_pub>\) and securely storing z and \(x_T\). \(M_A\) is the attacker of the encryption scheme described in this paper, while \(M_B\) is \(M_A\)’s challenger. \(M_A\)’s objective is to break the encryption scheme described in this paper through a bounded number of random oracle queries. \(M_B\) trains \(M_A\) to attack the encryption scheme by simulating the process, attempting to solve the ECCDH problem.
\(M_C\) is the challenger for \(M_B\) in solving the ECCDH problem. Before the simulation begins, \(M_B\) selects a message \(m\in \ 0,1 \^*_n\), computes \(P’=x_TP\), and sends \(<m,P’>\) to \(M_C\). \(M_C\) then selects \(a,b\in Z_q\), computes \(P’_1=aP’\), \(P’_2=bP’\), and \(E^*=H_2(abP’)\oplus m\), and sends \(<P’_1,P’_2,E^*>\) to \(M_B\). \(M_B\) then attempts to obtain \(abP’\) without knowing \(a,b\in Z_q\) in order to solve the ECCDH problem.
Additionally, \(M_B\) needs to maintain two initially empty lists, \(L_1=<PID_i,\phi _i,w_i>\) and \(L_2=<PID_i_1,PID_i_2,m^i_1_i_2,E^i_1_i_2>\), to track \(M_A\)’s pseudonym queries, parameters \(\phi _i\) , \(w_i\) queries, and ciphertext queries. \(M_B\) also selects \(j_1,j_2\in (1,2,…,q_K)\) a guess \(g\), where \(j_1,j_2\) represent an assumption about \(M_A\)‘s attack, the current query corresponds to the attack result (i.e., \(M_A\) will attack the encrypted communication between \(PID_j_1\) and \(PID_j_2\)). Without loss of generality, assume that \(M_A\) follows these basic principles:
-
i.
\(M_A\) does not initiate two parameters \(\phi _i\) and \(w_i\) queries for the same pseudonym.
-
ii.
If \(M_A\) attacks the encrypted communication between \(PID_j_1\) and \(PID_j_2\), it has previously submitted the corresponding ciphertext query.
\(\square\)
Phase 1: Query Phase
Pseudonym Queries. \(M_A\) queries \(M_B\) for several pseudonyms. For the i-th query, if \(i\notin \ j_1,j_2 \\), \(M_B\) randomly selects \(w_i\in G_1\), computes \(r_i=w_ix_T\) and \(W_i=w_iP\), runs the pseudonym generation algorithm Psm-gen(\(r_i,W_i\))\(\rightarrow PID_i\), and adds \(<PID_i,\phi _i,w_i>\) to \(L_1\); if \(i=j_1\), set \(Pid_i_1=P’_1\), compute \(Pid_i_1=x_T^-1P’_1\), and add \(<PID_i,null,null>\) to \(L_1\); if \(i=j_2\), set \(Pid_i_2=P’_2\), compute \(Pid_i_2=x_T^-1P’_2\), and add \(<PID_i,null,null>\) to \(L_1\). After completing these steps, \(M_B\) returns the result \(PID_i\) to \(M_A\).
Parameter \(\phi _i\) Query: \(M_A\) sends \(PID_i\) to \(M_B\), querying the corresponding \(\phi _i\). If \(i\notin \j_1,j_2\\), \(M_B\) retrieves \(\phi _i\) from \(L_1\) using \(PID_i\) and sends it to \(M_A\); otherwise, \(M_B\) randomly selects \(\phi _i \in G_1\), updates \(<PID_i,null,null>\) with \(<PID_i,\phi _i,null>\), and returns \(\phi _i\) to \(M_A\).
Parameter \(w_i\) Query: \(M_A\) sends \(PID_i\) to \(M_B\), querying the corresponding \(w_i\). If \(i\notin \j_1,j_2\\), \(M_B\) retrieves \(w_i\) from \(L_1\) using \(PID_i\) and sends it to \(M_A\); otherwise, the simulation is terminated.
Ciphertext Query: \(M_A\) sends \(PID_x\) and \(PID_y\) to \(M_B\), querying an encrypted message between them. If \(\ x,y \=\ j_1,j_2 \\), \(M_B\) adds \(<PID_x,PID_y,null,E^*>\) to \(L_2\) and returns \(E^*\) to \(M_A\). If \(\ x,y \\ne \ j_1,j_2 \\), let \(x\notin \ j_1,j_2 \\); \(M_B\) retrieves \(\phi _x,w_x\) and \(PID_y=<Pid_y_1,Pid_y_2>\) from \(L_1\), randomly selects a plaintext message \(m_y^x\in \ 0,1 \^*_n\), generates a ciphertext \(E_y^x=m_y^x\oplus H_2(\phi _xw_xPid_y_2)\), returns \(E_y^x\) to \(M_A\), and adds \(<PID_x,PID_y,m_y^x,E_y^x>\) to \(L_2\).
Phase 2: Challenge Phase
\(M_A\) outputs \(<PID_s,PID_t,E_t^s,Q’>\) as an attack attempt. If \(\ s,t \ \ne \ j_1,j_2 \\), \(M_B\) terminates the simulation; otherwise, \(M_B\) verifies whether \(m=E^*\oplus H_2(Q’)\) holds. If it does not hold, \(M_A\) fails and \(M_B\) terminates the simulation; if it holds, \(M_A\)’s attack is successful, then \(H_2(Q’)=H_2(abP’)\). \(M_B\) outputs \(Q’=abP’\), successfully solving the ECCDH problem.
In the above reduction process, \(M_B\) always responds to \(M_A\)’s queries with random values, ensuring that \(M_A\)’s simulated view is identically distributed to that of a real attack. Therefore, the simulation is complete. \(M_B\)’s ability to solve the ECCDH problem depends on the following three events:
-
1.
\(\epsilon _1\): The parameter \(w_i\)’s query does not terminate.
-
2.
\(\epsilon _2\): \(M_A\)’s challenge output satisfies \(\ s,t \=\ j_1,j_2 \\).
-
3.
\(\epsilon _3\): \(M_A\)’s attack is successful.
It is easy to see that \(Pr[\epsilon _1] = (1-\frac1q_K)^q_K-2=(1-\frac1q_K)^q_K\fracq_K^2(q_K-1)^2\), \(Pr[\epsilon _2] = \frac2q_K(q_k-1)\), and \(Pr[\epsilon _3]=\mu (\lambda )\). Hence, \(M_B\)’s advantage in solving the ECCDH problem is \((1-\frac1q_K)^q_K\fracq_K^2(q_K-1)^2\frac2q_K(q_k-1)\mu (\lambda )\approx \frac2q_ke(q_k-1)^3\mu (\lambda )\) . Proof complete.
In summary, breaking the encryption scheme described in this paper is difficult.
Authentication
Before decrypting the signcryption message from member A, member B first authenticates the validity of A’s pseudonym to determine whether A is registered. Considering that the pseudonyms of registered members are non-confidential, if a non-registered attacker selects a set of pseudonyms for A and is able to generate the parameter \(Y_B^A=Y_A=Y_B\) that passes B’s verification, we say the attacker has successfully compromised the authentication scheme described in this paper. Here, we assume \(Pid_A_1=\phi _A r_AP=a’P\), \(Pid_B_1=\phi _B r_BP=b’P\), and from equation (6), we know \(Y_B^A=a’b’P\).
Theorem 2
Suppose there exists an adversary \(M_A\) that can, in polynomial time, break the encryption scheme described in this paper with a non-negligible advantage \(\mu (\lambda )\) through a bounded number of random oracle queries (assuming \(q_k\) queries for pseudonyms,parameters \(\phi _i\), \(w_i\) and \(q_k(q_k-1)/2\) queries for parameter Y), then there exists an algorithm \(M_B\) that can solve the ECCDH problem with advantage \(\frac2q_ke(q_k-1)^3\mu (\lambda )\), where e is a natural constant and \(\lambda\) is the system security parameter.
Proof
\(M_B\) first runs the Setup algorithm to establish the scheme described in this paper, publishing the public parameters \(params=<p,q,G_1,G_2,e,H_1,H_2,P_pub>\) and securely storing z and \(x_T\). \(M_A\) is the attacker of the authentication scheme described in this paper, while \(M_B\) is \(M_A\)’s challenger. \(M_A\)’s objective is to break the authentication scheme described in this paper through a bounded number of random oracle queries. \(M_B\) trains \(M_A\) to attack the encryption scheme by simulating the process, attempting to solve the ECCDH problem.
\(M_C\) is the challenger for \(M_B\) in solving the ECCDH problem. Before the simulation begins, \(M_C\) selects \(a,b\in Z_q\), computes \(P_1=aP\) and \(P_2=bP\), and then sends \(<P_1,P_2>\) to \(M_B\). \(M_B\) then attempts to obtain abP without knowing \(a,b\in Z_q\), in order to solve the ECCDH problem.
Additionally, \(M_B\) needs to maintain two initially empty lists, \(L_1=<PID_i,\phi _i,w_i>\) and \(L_2=<PID_i_1,PID_i_2,Y_i_2^i_1>\), to track \(M_A\)’s pseudonym queries and parameters \(\phi _i,w_i\), Y queries. \(M_B\) also selects \(j_1,j_2\in (1,2,…,q_K)\), representing an assumption about \(M_A\)‘s attack. The current query corresponds to the attack result (i.e., \(M_A\) will use the pseudonym of \(PID_j_1\) or \(PID_j_2\) to generate a parameter \(Y_j_2^j^1\) and pass the authentication of \(PID_j_1\) or \(PID_j_2\)). Without loss of generality, assume that \(M_A\) does not initiate two parameters \(\phi _i\) and \(w_i\) queries for the same pseudonym.
Phase 1: Query Phase
Pseudonym Queries. \(M_A\) queries \(M_B\) for several pseudonyms. For the i-th query, if \(i\notin \ j_1,j_2 \\), \(M_B\) randomly selects \(w_i\in G_1\), computes \(r_i=w_ix_T\) and \(W_i=w_iP\), runs the pseudonym generation algorithm Psm-gen(\(r_i,W_i\))\(\rightarrow PID_i\), and adds \(<PID_i,\phi _i,w_i>\) to \(L_1\); if \(i=j_1\), set \(Pid_i_1=P_1\), compute \(Pid_i_1=x_T^-1P_1\), and add \(<PID_i,null,null>\) to \(L_1\); if \(i=j_2\), set \(Pid_i_2=P_2\), compute \(Pid_i_2=x_T^-1P_2\), and add \(<PID_i,null,null>\) to \(L_1\). After completing these steps, \(M_B\) returns the result \(PID_i\) to \(M_A\).
Parameter \(\phi _i\) Query: \(M_A\) sends \(PID_i\) to \(M_B\), querying the corresponding \(\phi _i\). If \(i\notin \j_1,j_2\\), \(M_B\) retrieves \(\phi _i\) from \(L_1\) using \(PID_i\) and sends it to \(M_A\); otherwise, \(M_B\) randomly selects \(\phi _i \in G_1\), updates \(<PID_i,null,null>\) with \(<PID_i,\phi _i,null>\), and returns \(\phi _i\) to \(M_A\).
Parameter \(w_i\) Query: \(M_A\) sends \(PID_i\) to \(M_B\), querying the corresponding \(w_i\). If \(i\notin \j_1,j_2\\), \(M_B\) retrieves \(w_i\) from \(L_1\) using \(PID_i\) and sends it to \(M_A\); otherwise, the simulation is terminated.
Parameter Y Query: \(M_A\) sends \(PID_x\) and \(PID_y\) to \(M_B\), querying an verification parameter \(Y_y^x\) between them. If \(\ x,y \=\ j_1,j_2 \\), \(M_B\) terminates the simulation; if \(\ x,y \\ne \ j_1,j_2 \\), let \(x\notin \ j_1,j_2 \\). \(M_B\) retrieves \(\phi _x,w_x\) and \(PID_y=<Pid_y_1,Pid_y_2>\) from \(L_1\), computes \(Y_y^x=\phi _xw_xPid_y_1\), returns \(Y_y^x\) to \(M_A\), and adds \(<PID_x,PID_y,Y_y^x>\) to \(L_2\).
Phase 2: Challnege Phase
\(M_A\) outputs \(<PID_s,PID_t,Y_t^s>\) as an attack attempt. If \(\ s,t \ \ne \ j_1,j_2 \\), \(M_B\) terminates the simulation; otherwise, \(M_B\) whether the condition \(e(Pid_s_1,Pid_t_1)=e(T_t^s,P)\) holds. If it holds, then it implies:
\(e(Pid_s_1,Pid_t_1)=e(aP,bP)=e(abP,P)=e(Y_t^s,P)\)
then \(Y_t^s=abP\), \(M_A\)‘s attack is successful. \(M_B\) outputs \(Y_t^s=abP\), successfully solving the ECCDH problem.
In the above reduction process, \(M_B\) always responds to \(M_A\)‘s queries with random values, ensuring that \(M_A\)‘s simulated view is identically distributed to that of a real attack. Therefore, the simulation is complete. \(M_B\)‘s ability to solve the ECCDH problem depends on the following three events:
-
1.
\(\epsilon _1\): The parameter \(w_i\)’s query does not terminate.
-
2.
\(\epsilon _2\): \(M_A\)’s challenge output satisfies \(\ s,t \=\ j_1,j_2 \\).
-
3.
\(\epsilon _3\): \(M_A\)’s attack is successful.
It is easy to see that \(Pr[\epsilon _1] = (1-\frac1q_K)^q_K-2=(1-\frac1q_K)^q_K\fracq_K^2(q_K-1)^2\), \(Pr[\epsilon _2] = \frac2q_K(q_k-1)\), and \(Pr[\epsilon _3]=\mu (\lambda )\). Hence, \(M_B\)’s advantage in solving the ECCDH problem is \((1-\frac1q_K)^q_K\fracq_K^2(q_K-1)^2\frac2q_K(q_k-1)\mu (\lambda )\approx \frac2q_ke(q_k-1)^3\mu (\lambda )\) . Proof complete.
In summary, breaking the authentication scheme described in this paper is difficult.
Unforgeability
In the analysis of authentication, it has been proven that non-registered members cannot forge valid pseudonyms, thus avoiding the possibility of external members forging signcryptions. For internal members, they can provide relevant parameters that pass pseudonym verification, thereby further enabling the possibility of forging others’ signatures.
Theorem 3
If there exists an adversary, denoted as MA, capable of providing an effective signature with non-negligible advantage \(\mu (\lambda )\) in polynomial time, by making a bounded number of random oracle queries (assuming \(q_H\) times \(H_1\) queries, \(q_K\) times pseudonym queries, public key queries, private key queries, and signature queries), then there exists an algorithm, denoted as \(M_B\), capable of solving the ECCDH problem with an advantage of \(\fracq_Ke^2(q_K-1)^2\mu (\lambda )\) , where e is the natural constant and \(\lambda\) is the system security parameter.
Proof
\(M_B\) aims to solve the ECCDH problem by randomly selecting \(P_1,P_2\in G_1\) , denoted \(<P,P_1,P_2>=<P,aP,bP>\) as input, with the objective of obtaining abP without knowing \(a,b\in Z_q\) . \(M_A\) acts as an internal attacker in this scenario, aiming to output a signature that can pass the verification process by making a bounded number of random oracle queries. As a challenger to \(M_A\), algorithm \(M_B\) trains the attacker by simulating the process and attempting to solve the ECCDH problem within the context of attacking the signature mechanism of this paper. \(\square\)
Before the simulation starts, \(M_B\) runs the Setup(*) algorithm and sends the public parameters to \(M_A\). It maintains initial empty lists \(L_PID\) , \(L_H_1\) , \(L_PK\) , and \(L_SK\) to track \(M_A\)’s queries for pseudonyms, \(H_1\) queries, public key extraction queries, and private key extraction queries, respectively. \(M_B\) randomly selects \(P_1\in G_1\) as one of the inputs to the ECCDH problem, \(P_2\) remains fixed throughout the simulation. Additionally, \(M_B\) selects \(j\in (1,2,…,q_K)\) as a guess for the attack against \(M_A\), representing the content of the current query and its corresponding attack result. Without loss of generality, assume that \(M_A\) adheres to the following basic principles:
-
i.
\(M_A\) does not make two \(H_1\) queries for the same message.
-
ii.
\(M_A\) does not make two public key queries for the same pseudonym.
-
iii.
If \(M_A\) asks for the signature of a message m or a guessed signature of an output message m , then it previously submitted an \(H_1\) query for that message.
-
iv.
If \(M_A\) challenges a signature for a particular pseudonym, then it previously queried that pseudonym and its public key.
Phase 1: Query Phase
Pseudonym Inquiry. \(M_A\) queries \(M_B\) for several pseudonyms. For the i query, \(M_B\) randomly selects \(Pid_i_2\in G_1\) , computes \(Pid_i_2=x_TPid_i_1\) , adds \(PID_i=(Pid_i_1,Pid_i_2)\) to \(L_PID\) , and returns \(PID_i\) .
\(H_1\) Inquiry. \(M_A\) sends \(m_i\in \ 0,1 \_n^*\) to \(M_B\), inquiring about the value of \(H_1(m_i)\) . If \((m_i,h_i)\) exists in \(L_H_1\) , then \(M_B\) returns \(h_i\) ; otherwise, \(M_B\) randomly selects \(h_i\in Z_q\) , adds \((m_i,h_i)\) to \(L_H_1\) , and returns \(h_i\) .
Public Key Extraction Inquiry. \(M_A\) sends \(PID_i\) to \(M_B\), inquiring about the corresponding complete public key of \(PID_i\) . If \(i\ne j\) , \(M_B\) randomly selects \(x_i\in Z_q\) , computes \(X_i=x_iP\) , adds \((X_i,Pid_i_2)\) to \(L_PK\) , and returns \((X_i,Pid_i_2)\) ; if \(i=j\) , then \(X_i=P_1\) , \(Pid_i_2\) is denoted as \(P_2\) , added \((x_i,X_i,Pid_i_2)\) to \(L_PK\) , and return \((X_i,Pid_i_2)\) .
Private Key Extraction Inquiry. \(M_A\) inquires about the private key corresponding to \((X_i,Pid_i_2)\) . If \((Pid_i_2,Q_P_i,K_P_i)\in L_SK\) , \(M_B\) returns \((Q_P_i,K_P_i)\) . Other-wise, if \(i\ne j\) , B retrieves \(L_PK\) through i , takes out \((x_i,X_i,Pid_i_2)\) , calculates \(Q_P_i=x_iPid_i_2\) , adds \(((Pid_i_2,Q_P_i,K_P_i))\) to \(L_SK\) , and returns \((Q_P_i,K_P_i)\) . If \(i=j\) , the simulation is interrupted and terminated.
Signature Inquiry. \(M_A\) inquires about the signature of \((m_k,X_i,Pid_i_2)\) . If \(i\ne j\), \(M_B\) utilizes \(m_k\) to extract the corresponding \(h_k\) from \(L_H_1\) , utilizes \(Pid_i_2\) to extract the corresponding \((Q_P_i,K_P_i)\) from \(L_SK\) , calculates, and returns \(Sig_i^m_k=Q_P_i+h_kK_P_i\) . If \(i=j\), the simulation is interrupted and terminated.
Phase 2: Challenge Phase
\(M_A\) outputs \((m^*,Sig^*,X_i,Pid_i_2)\). If \(i\ne j\), \(M_B\) interrupts the simulation. If \(i=j\), B verifies \(e(Sig^*,P)=e(X_i,h^*P_hub,Pid_i_2)\) by retrieving the corresponding \(h^*\) from \(L_H_1\) through \(m^*\) and checking. If the verification fails, \(M_A\) fails, and \(M_B\) interrupts the simulation; if it succeeds, \(M_A\)‘s attack is successful, thus:
$$\beginaligned \beginaligned e(Sig^*,P)&=e(X_i+h^*P_hub,Pid_i_2) \\&=e(P_1+h^*P_hub,P_2)\\&=e(abP+bh^*zP,P) \endaligned \endaligned$$
(5)
\(M_B\) outputs, solving the ECCDH problem.
In the above reduction process, \(M_B\) always responds to \(M_A\)’s queries with random values, meaning that the simulated view of \(M_A\) is identically distributed to the real attack, making the simulation process complete. The ability of \(M_B\) to solve the ECCDH problem depends on the following four events:
-
\(\epsilon _1\): Private key query was not interrupted.
-
\(\epsilon _2\) : Signature query was not interrupted.
-
\(\epsilon _3\) : \(M_A\) outputs the public key index corresponding to the signature.
-
\(\epsilon _4\) : \(M_A\) is able to produce a valid signature.
It is easy to see that \(Pr[\epsilon _1] = Pr[\epsilon _2] = (1-\frac1q_K)^q_K-1=(1-\frac1q_K)^q_K\fracq_K(q_K-1)\), \(Pr[\epsilon _3] = \frac1q_k\), and \(Pr[\epsilon _4]=\mu (\lambda )\). Hence, \(M_B\)’s advantage in solving the ECCDH problem is \([(1-\frac1q_K)^q_K]^2\fracq_K^2(q_K-1)^2\frac1q_K\mu (\lambda )\approx \fracq_ke^2(q_k-1)^2\mu (\lambda )\) . Proof complete.
In conclusion, it is difficult for internal members of the system to generate signatures for others. The signature messages in this paper’s scheme are therefore unforgeable.
Anonymity
During the signcryption process, both communicating parties use pseudonyms, and parameters \(r_i\) and \(W_i\) that could reveal member identities are concealed by random numbers \(\phi _i\) . The verifying party only checks if the pseudonym contains TMA registration factor \(x_T\) and if the signature includes KGC’s master key z to confirm if the other party is registered with TMA (i.e., traceable) and if they obtained partial private keys from KGC. Throughout the communication process, no real member identity information needs to be provided. Thus, this scheme provides identity anonymity.
System members can choose different pseudonyms and pseudonymous keys for different communication processes. Different pseudonyms are concealed by different random numbers \(\phi _i\) , making it impossible for the communicating parties to deter-mine if the pseudonyms come from the same member, i.e., if different signings come from the same entity. Therefore, this scheme has behavioral anonymity.
Traceability
This paper’s scheme includes a pseudonym tracking algorithm. If there are malicious members in encrypted communication, TMA can track them afterward using the pseudonyms they used and deter-mine their real identities.
Non-repudiation
This paper’s scheme incorporates pseudonymous component \(Pid_2\) as part of the public key, achieving automatic binding of identity and public key. Before signing, members need to submit their pseudonyms for verification by the other party. Once submitted, the pseudonym cannot be changed, and the pseudonymous component automatically be-comes part of the public key. As analyzed earlier, external members cannot forge pseudonyms, and internal members cannot forge others’ signatures. Therefore, system members can only generate signcryptions corresponding to their own pseudonyms, which can be tracked by TMA, thus preventing signers from denying the signcryptions.
Complexity analysis
Time complexity
The computational tasks involved in this scheme mainly include operations on elliptic curve point groups \(G_1\), such as addition (S) and multiplication (M), pairings (P), and hash mappings (h). Table 2 lists the number of times these operations are used in each algorithm of the scheme. From Table 2, it can be observed that, except for the Psm-trc algorithm, which involves pseudonym tracing, the frequencies of various types of operations used in other algorithms are constant and independent of the problem size n, resulting in a time complexity of O(1) . The Psm-trc algorithm includes a table lookup, resulting in a time complexity of O(logn) . However, since Psm-trc is executed by TMA and has low frequency of use, it runs only when arbitration is needed. Considering that TMA plays the role of a system manager with strong computational capabilities, undertaking the computational burden of an operation with low frequency and complexity O(logn) is not significant.
Space complexity
In this scheme, ordinary members need to store data including their complete keys, pseudonymous identities, pseudonymous keys, and system public constants. The total storage required for this data is a fixed constant, independent of the system scale n, thus the space complexity for ordinary members is O(1) . Clearly, the space complexity for KGC is also O(1) . Besides storing the mentioned data, TMA also needs to additionally save an entity list EIT, where the number of entries in EIT is equal to the number of registered members. Therefore, the space complexity for TMA is O(n) . Considering that TMA plays the role of system administrator and has strong storage capabilities, the storage pressure of O(n) complexity can be ignored.
link
