## 5 Security Analysis
**Correctness:** We show that the above signature \(\sigma_{i}=(\sigma_{i,1},\sigma_{i,2},T_{i})\) produced by the _Signing_ query is correct since \[w=u_{0}\prod\limits_{j=1}^{n}u_{j}^{m_{j}}=(g^{b})^{F(m)}g^{I(m)}.\]9 \[\sigma_{i,1}=e((g^{a})^{\frac{-J(m_{i})-2h_{i}}{F(m_{i})}}(w_{i}v^{h_{i}})^{r_ {i}},pk_{V,1}).\]0 \[\sigma_{i,1}=e((g^{a})^{\frac{-J(m_{i})-2h_{i}}{F(m_{i})}}(w_{i}v^{h_{i}})^{r_ {i}},pk_{V,1}).\]1 \[\sigma_{i,1}=e((g^{a})^{\frac{-J(m_{i})-2h_{i}}{F(m_{i})}}(w_{i}v^{h_{i}})^{r_ {i}},pk_{V,1}).\]2
7. _Challenge_: When \(\mathcal{D}\) submits a challenge message \(m^{*}=(m_{1}^{*},...,m_{n}^{*})\), \(\mathcal{B}\) proceeds as follows: 1. Pick \(r^{*}\in Z_{p}^{*}\) randomly, and compute \(\sigma_{2}^{*}=g^{r^{*}}\). 2. Pick a random element \(T^{*}\in G_{1}\), and compute \(w^{*}=u_{0}\prod\limits_{j=1}^{n}u_{j}^{m_{j}^{*}}\) and \(h^{*}=H_{2}(m^{*},\sigma_{2}^{*},T^{*})\). 3. Flip a fair coin to obtain a random bit \(d\in\{0,1\}\). 4. Compute \(\sigma_{1}^{*}=sk_{S_{d}\leftrightarrow V}\cdot e(w^{*}v^{h^{*}},g^{c})^{r^{*}}\). 5. Return a signature \(\sigma^{*}=(\sigma_{1}^{*},\sigma_{2}^{*},T^{*})\) on \(m^{*}\) to \(\mathcal{D}\). * _Query phase_ 2: \(\mathcal{D}\) continues to issue various queries as in _Query phase_ 1 except that \(\mathcal{D}\) cannot make a signature verification query on \((m^{*},\sigma^{*},d^{*})\) for any \(d^{*}\in\{0,1\}\). * _Output_: \(\mathcal{D}\) outputs a value \(d^{{}^{\prime}}\in\{0,1\}\). If \(d=d^{{}^{\prime}}\), indicating \(Z=e(g,g)^{abc}\), \(\mathcal{B}\) outputs 1; else, indicating \(Z\) is a random element in \(G_{2}\), \(\mathcal{B}\) outputs 0. From the above simulation, we can see that \(\mathcal{B}\) does not exit in the whole simulation. Therefore, if \(\mathcal{D}\) breaks the PSI property of the SDVS-USU scheme with probability \(\varepsilon\), then \(\mathcal{B}\) can solve the DBDH problem instance with probability of \(\frac{1}{2}+\varepsilon\). The SDVS-USU scheme is undeniable. Proof of Theorem 4.: On receiving a disputed signature \(\tilde{\sigma}=(\tilde{\sigma}_{1},\tilde{\sigma}_{2},\tilde{T})\) on a message \(\tilde{m}\), the arbiter performs the following:  
1. Obtain the signer's public key \(pk_{S}=(pk_{S,1},pk_{S,2})=(g^{k_{S,1}},g^{k_{S,2}})\) and the designated verifier's public key \(pk_{V}=(pk_{V,1},pk_{V,2})=(g^{k_{V,1}},g^{k_{V,2}})\). 2. Compute \(T_{S}=e(pk_{S,1},pk_{S,2})^{k_{A}H_{1}(m,\rho_{2})}\) and \(T_{V}=e(pk_{V,1},pk_{V,2})^{k_{A}H_{1}(m,\rho_{2})}\), where \(k_{A}\) is the arbiter's private key. 3. Check \(e(\tilde{T},g)=T_{S}\) or \(e(\tilde{T},g)=T_{V}\). If \(e(\tilde{T},g)=T_{S}\), the arbiter confirms \(\tilde{\sigma}\) is created by the signer. If \(e(\tilde{T},g)=T_{V}\), the arbiter confirms \(\tilde{\sigma}\) is produced by the designated verifier. In the proposed scheme, a signature from the signer has the form \(T=(pk_{A})^{k_{S,1}k_{S,2}H_{1}(m,\rho_{2})}\), while a signature from the designated verifier has the form \(T^{{}^{\prime}}=(pk_{A})^{k_{V,1}k_{V,2}H_{1}(m,\sigma_{2}^{\prime})}\). The arbiter can independently prove the real signer of any valid signature by verifying \(e(\tilde{T},g)=T_{S}\) or \(e(\tilde{T},g)=T_{V}\) with probability 1. Therefore, the SDVS-USU scheme holds the undeniability property.