## 4 The SDVS-USU Scheme  
In this section, we design a strongly unforgeable SDVS scheme with undeniable property on the basis of a variant of [PERSON] scheme [28]. Although a few SDVS schemes [12; 13; 14] satisfy undeniability, their security depends on ideal random oracles, which might be insecure in reality. Most of the SDVS schemes [17; 18] without random oracles are malleable, so they cannot achieve strong unforgeability. To overcome these problems, the SDVS-USU scheme uses two collision-resistant hash functions to protect the integrity of the signature. This method can not only generate non-malleable signatures, but also achieve strong unforgeability and undeniability. Since we design the SDVS-USU scheme using a direct construction rather than a general conversion method, it basically maintains the performance of the [PERSON] scheme [28] in terms of signature size and computational overhead. Additionally, it should be emphasized that the employed collision-resistant hash functions are not considered as random oracles in our security proof. There are three participants in the SDVS-USU scheme: the signer \(S\), the designated verifier \(V\) and the arbiter \(A\). In the following, we assume that all signed messages are bit strings of length \(n\). To achieve this assumption, messages of arbitrary length can be converted into messages of fixed length \(n\) by using a secure hash function \(H:\{0,1\}^{*}\rightarrow\{0,1\}^{n}\). The SDVS-USU scheme is described as follows. * **Setup**: Let \(G_{1}\) and \(G_{2}\) be two multiplicative cyclic groups of prime order \(p\). \(g\) is any generator of \(G_{1}\), \(e:G_{1}\times G_{1}\to G_{2}\) is a bilinear pair, and \(\vec{u}=(u_{j})\) is a vector of length \(n\), where \(u_{j}\in G_{1}\). Let \(H_{1}:\{0,1\}^{*}\times G_{1}\to Z_{p}\) and \(H_{2}:\{0,1\}^{*}\times G_{1}\times G_{1}\to Z_{p}\) be two collision-resistant hash functions. The public parameters are \(params=(G_{1},G_{2},p,g,e,u_{0},\vec{u},H_{1},H_{2})\). * **KeyGen**: The signer \(S\) picks two random elements \(k_{S,1},k_{S,2}\in Z_{p}^{*}\) as the private key \(sk_{S}=(sk_{S,1},\)\(sk_{S,2})=(k_{S,1},k_{S,2})\), and computes the corresponding public key \(pk_{S}=(pk_{S,1},pk_{S,2})=(g^{k_{S,1}},g^{k_{S,2}})\). Similarly, \(sk_{V}=(sk_{V,1},sk_{V,2})=(k_{V,1},k_{V,2})\) and \(pk_{V}=(pk_{V,1},pk_{V,2})=(g^{k_{V,1}},g^{k_{V}2})\) are the designated verifier \(V\)'s private key and public key respectively. The arbiter \(A\)'s public/private key pair is \((pk_{A},sk_{A})=(g^{k_{A}},k_{A})\), where \(k_{A}\in Z_{p}^{*}\). * **Sign**: To generate the signature of a \(n\)-bit message \(m=(m_{1},...,m_{n})\in\{0,1\}^{n}\), the signer proceeds as follows. 1. Select \(r\in Z_{p}\) randomly and calculate \(\sigma_{2}=g^{r}\). 2. Compute \(w=u_{0}\prod\limits_{j=1}^{n}u_{j}^{m_{j}}\), \(T=(pk_{A})^{k_{S,1}k_{S,2}H_{1}(m,\sigma_{2})}\) and \(h=H_{2}(m,\sigma_{2},T)\). 3. Compute \(\sigma_{1}=e(g^{k_{S,1}k_{S,2}}(wv^{h})^{r},pk_{V,1})\). 4. Output a signature \(\sigma=(\sigma_{1},\sigma_{2},T)\) on \(m\). * **Verify**: After receiving a signature \(\sigma=(\sigma_{1},\sigma_{2},T)\) on a \(n\)-bit message \(m=(m_{1},...,m_{n})\in\{0,1\}^{n}\) from the signer, the designated verifier calculates \(h=H_{2}(m,\sigma_{2},T)\) and uses its private key \(sk_{V}=(sk_{V,1},sk_{V,2})=(k_{V,1},k_{V,2})\) to verify whether \[\sigma_{1}=e(pk_{S,1},pk_{S,2})^{k_{V,1}}e(wv^{h},\sigma_{2})^{k_{V,1}}.\] If it holds, the designated verifier believes that \(\sigma\) is legal and outputs 1; else, the designated verifier considers \(\sigma\) to be illegal and outputs 0. * **Sim**: To produce a simulated signature on a message \(m=(m_{1},...,m_{n})\in\{0,1\}^{n}\), the designated verifier performs the following: 1. Select \(s\in Z_{p}\) randomly and compute \(\sigma_{2}^{{}^{\prime}}=g^{s}\). 2. Compute \(w=u_{0}\prod\limits_{j=1}^{n}u_{j}^{m_{j}}\), \(T^{\prime}=(pk_{A})^{k_{V_{1}}k_{V_{2}}H_{1}(m,\sigma_{2}^{{}^{\prime}})}\) and \(h^{\prime}=H_{2}(m,\sigma_{2}^{{}^{\prime}},T^{\prime})\). 3.