## 5 Security Analysis  
In this section, we demonstrate that the SDVS-USU scheme holds strong unforgeability, non-transferability, PSI and undeniability. Theorem 5.1: _If the BDH assumption holds, then the SDVS-USU scheme is strongly unforgeable against adaptive chosen message attacks in the standard model._  
Proof of Theorem 5.1.: Suppose there exists a polynomial-time adversary \(\mathcal{F}\) who breaks the strong unforgeability of the SDVS-USU scheme with non-negligible probability, where \(\mathcal{F}\) can make at most \(q_{S}\) signing queries, \(q_{Sim}\) simulating queries and \(q_{V}\) verifying queries. Then, we construct another algorithm \(\mathcal{C}\) who can solve the BDH problem by using the \(\mathcal{F}\)'s forgery. Given a random BDH problem instance \((g,g^{a},g^{b},g^{c})\in G_{1}^{4}\), the goal of \(\mathcal{C}\) is to calculate \(e(g,g)^{abc}\). \(\mathcal{C}\) will act as \(\mathcal{F}\)'s challenger and respond to \(\mathcal{F}\)'s queries as follows. * _Setup_: \(\mathcal{C}\) simulates the algorithm **Setup** in the following way. 1. Select \(k(0\leq k\leq n)\) randomly, and set \(l=4(q_{S}+q_{Sim}+q_{V})\) to satisfy \(l(n+1)<p\). 2. Select two random values \(k_{1},k_{2}\in Z_{p}\), and set the signer's public key \(pk_{S}=(pk_{S,1},pk_{S,2})=(g^{a},g^{b})\), the designated verifier's public key \(pk_{V}=(pk_{V,1},pk_{V,2})=(g^{c},g^{k_{2}})\) and the arbiter's public key \(pk_{A}=g^{k_{1}}\). Note that \(a\), \(b\) and \(c\) are unknown to \(\mathcal{C}\). 3. Select \(x_{0},x_{1},...,x_{n}\in Z_{l}\) and \(y_{0},y_{1},...,y_{n}\in Z_{p}\) randomly. 4. Select a random integer \(z\in Z_{p}\), assign \(v=g^{z}\), \(u_{0}=(g^{b})^{p-kl+x_{0}}g^{y_{0}}\) and \(u_{j}=(g^{b})^{x_{i}}g^{y_{i}}\) for \(1\leq j\leq n\), and set a vector \(\vec{u}=(u_{1},...,u_{n})\). 5. Pick two collision-resistant hash functions \(H_{1}:\{0,1\}^{*}\times G_{1}\to Z_{p}\) and \(H_{2}:\{0,1\}^{*}\times G_{1}\times G_{1}\to Z_{p}\). 6. Send the public parameters \(params=(G_{1},G_{2},p,g,e,u_{0},v,\vec{u},H_{1},H_{2})\) and \((pk_{S},pk_{V},pk_{A})\) to \(\mathcal{F}\). For a \(n\)-bit message \(m=(m_{1},...,m_{n})\), we define two functions \[F(m)=(p-lk)+x_{0}+\sum\limits_{j=1}^{n}x_{j}m_{j},\] \[J(m)=y_{0}+\sum\limits_{j=1}^{n}y_{j}m_{j}.\] Hence, we obtain the following equation \[w=u_{0}\prod\limits_{j=1}^{n}u_{j}^{m_{j}}=(g^{b})^{F(m)}g^{I(m)}.\]
* _Signing queries_: When \(\mathcal{F}\) issues a signature query on a message \(m_{i}=(m_{i,1},...,m_{i,n})\in\{0,1\}^{n}\), \(\mathcal{C}\) computes the value of \(F(m_{i})\). Note that if \(F(m_{i})=0\bmod\ p\), there exists an unique value \(0\leq k\leq n\) such that \(F(m_{i})=0\bmod\ l\). On the other hand, \(F(m_{i})\
eq 0\bmod\ l\) implies \(F(m_{i})\
eq 0\bmod\ p\). If \(F(m_{i})=0\bmod\ l\), \(\mathcal{C}\) aborts. If \(F(m_{i})\
eq 0\bmod\ l\), \(\mathcal{C}\) first searches \(m_{i}\) in Table \(T_{r}\) which is initially empty. If there is a tuple \((m_{i},r_{i})\) in \(T_{r}\), \(\mathcal{C}\) extracts \(r_{i}\) from \(T_{r}\); otherwise, \(\mathcal{C}\) randomly selects \(r_{i}\in Z_{p}\) and adds \((m_{i},r_{i})\) in \(T_{r}\). Then, \(\mathcal{C}\) picks a random element \(T_{i}\in G_{1}\), and computes \(w_{i}=u_{0}\prod\limits_{j=1}^{n}u_{j}^{m_{i}}\), \(\sigma_{i,2}=(g^{a})^{\frac{-1}{F(m_{i})}}g^{r_{i}}\), \(h_{i}=H_{2}(m_{i},\sigma_{i,2},T_{i})\) and \[\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}).\] Finally, \(\mathcal{C}\) returns a signature \(\sigma_{i}=(\sigma_{i,1},\sigma_{i,2},T_{i})\) on \(m_{i}\) to \(\mathcal{F}\).