## 3 Preliminaries
### Strong Designated Verifier Signature
The non-transferability requires that no third party can tell the signature on a message was created by the signer or was simulated by the designated verifier. Definition 4: An SDVS scheme is said to be non-transferable if it is not feasible for any PPT algorithm \(\mathcal{A}_{1}\) to differentiate that a given signature is produced by the signer or the designated verifier without knowingthe signer's private key \(sk_{S}\), the designated verifier's private key \(sk_{V}\) or the arbiter's private key \(sk_{A}\). That is, the probability \(\varepsilon\) of \(\mathcal{A}_{1}\) distinguishing between simulated signatures and real signatures is negligible._  
\[\Pr\left[b=b^{{}^{\prime}}\left| \begin{array}{c}\sigma_{0}\gets Sign( pk_{S},pk_{V},pk_{A},sk_{S},m)\\ \sigma_{1}\gets Sim(pk_{S},pk_{V},pk_{A},sk_{V},m)\\ b\leftarrow\{0,1\}\\ b^{{}^{\prime}}\leftarrow\mathcal{A}_{1}(pk_{S},pk_{V},pk_{A},\sigma_{b}) \end{array} \right.\right]=\varepsilon.\]  
_In other words, the signature generated by the signer is computationally indistinguishable from the signature simulated by the designated verifier, i.e.,_  
\[\left\{Sign(pk_{S},pk_{V},pk_{A},sk_{S},m)\right\}\approx\left\{Sim(pk_{S},pk_ {V},pk_{A},sk_{V},m)\right\}.\]  
PSI requires that no one other than the designated verifier knows the identity of the signer, but any third party is unable to identify the designated verifier and the signer. That is, if there are two signers \(S_{0}\) and \(S_{1}\), it is infeasible for any PPT adversary to differentiate whether the signature of a message is signed by \(S_{0}\) or \(S_{1}\) without knowing the designated verifier's private key. PSI is formally defined by the following security game between a distinguisher \(\mathcal{D}\) and a challenger \(\mathcal{B}\). * _Setup_: \(\mathcal{B}\) runs the **Setup** algorithm to produce the public parameters _params_, and runs the **KeyGen** algorithm to generate the signer \(S_{0}\)'s key pair \((pk_{S_{0}}\), \(sk_{S_{0}})\), the signer \(S_{1}\)'s key pair \((pk_{S_{1}}\), \(sk_{S_{1}})\), the designated verifier \(V\)'s key pair \((pk_{V}\), \(sk_{V})\) and the arbiter \(A\)'s key pair \((pk_{A}\), \(sk_{A})\). Then, \(\mathcal{B}\) sends \((params,pk_{S_{0}},pk_{S_{1}},pk_{V},pk_{A})\) to \(\mathcal{D}\). * _Query phase_ 1: \(\mathcal{D}\) adaptively initiates a series of inquiries to \(\mathcal{B}\) as follows. * _Signing queries_: When \(\mathcal{D}\) issues a signature query on a message \(m_{i}\) and an index \(d_{i}\in\{0,1\}\), \(\mathcal{B}\) executes the \(\textbf{Sign}(pk_{S_{d_{i}}},pk_{V},pk_{A},sk_{S_{d_{i}}},m_{i})\) algorithm to obtain a signature \(\sigma_{i}\) on \(m_{i}\) and returns \(\sigma_{i}\) to \(\mathcal{D}\). * _Simulating queries_: When \(\mathcal{D}\) issues a simulated signature query on a message \(m_{i}\) and an index \(d_{i}\in\{0,1\}\), \(\mathcal{B}\) runs the \(\textbf{Sim}(pk_{S_{d_{i}}},pk_{V},pk_{A},sk_{V},m_{i})\) algorithm to obtain a signature \(\sigma_{i}^{{}^{\prime}}\) on \(m_{i}\) and returns \(\sigma_{i}^{{}^{\prime}}\) to \(\mathcal{D}\). * _Verifying queries_: After receiving a message \(m_{i}\), a signature \(\sigma_{i}\) and an index \(d_{i}\in\{0,1\}\), \(\mathcal{B}\) responds to \(\mathcal{D}\) with the output of the algorithm \(\textbf{Verify}(pk_{S_{d_{i}}},pk_{V},pk_{A},sk_{V},m_{i},\sigma_{i})\). * _Challenge_: After receiving the challenge message \(m^{*}\) submitted by \(\mathcal{D}\), \(\mathcal{B}\) obtains a random value \(d\in\{0,1\}\) by flipping a coin. Then, \(\mathcal{B}\) returns the signature \(\sigma^{*}\) generated by the algorithm \(\textbf{Sign}(pk_{S_{d}},pk_{V},pk_{A},sk_{S_{d}},m^{*})\) to \(\mathcal{D}\). * _Query phase_ 2: \(\mathcal{D}\) continues to make queries as in _Query phase_ 1 except that \(\mathcal{D}\) is unable to submit a signature verification query on \((m^{*},\sigma^{*},d^{*})\) for any \(d^{*}\in\{0,1\}\). * _Output_: \(\mathcal{D}\) returns a value \(d^{{}^{\prime}}\in\{0,1\}\). If \(d=d^{{}^{\prime}}\), \(\mathcal{D}\) wins the game.