## 3 Preliminaries
### Strong Designated Verifier Signature  
An SDVS scheme with undeniable property is defined as follows:  
* **Setup**: On the input of a security parameter \(\lambda\in Z\), this algorithm produces the public parameters _params_. * **KeyGen**: On the input of _params_, this algorithm produces a public/private key pair \((pk_{S},sk_{S})\) for a signer \(S\), \((pk_{V},sk_{V})\) for a designated verifier \(V\) and \((pk_{A},sk_{A})\) for an arbiter \(A\). * **Sign**: On the input of public keys of \(S\), \(V\) and \(A\), the signer \(S\)'s private key \(sk_{S}\) and a message \(m\), this algorithm produces a signature \(\sigma\) on \(m\). * **Verify**: Given public keys of \(S\), \(V\) and \(A\), this algorithm returns 1 if the designated verifier \(V\)'s private key \(sk_{V}\) can be used to verify that \(\sigma\) is a legal signature for a message \(m\); otherwise, it returns 0. * **Sim**: On the input of public keys of \(S\), \(V\) and \(A\), the designated verifier \(V\)'s private key \(sk_{V}\) and a message \(m\), this algorithm produces a simulated signature \(\sigma^{\prime}\) that is indistinguishable from \(\sigma\). The correctness of SDVS requires that both the original signature and the simulated signature are valid. That is, for any key pairs \((pk_{S},sk_{S})\), \((pk_{V},sk_{V})\) and \((pk_{A},sk_{A})\), any message \(m\), any signature \(\sigma\)=**Sign\((pk_{S},pk_{V},pk_{A},sk_{S},m)\)**, and any simulated signature \(\sigma^{\prime}\)=**Sim\((pk_{S},pk_{V},pk_{A},sk_{V},m)\)**, the following two equations must hold:  
\[ \begin{array}{l}\textbf{Verify}(pk_{S},pk_{V},pk_{A},sk_{V},m,\sigma)=1,\\ \textbf{Verify}(pk_{S},pk_{V},pk_{A},sk_{V},m,\sigma^{{}^{\prime}})=1.\end{array} \]  
A secure SDVS scheme with undeniable property should achieve the security requirements of strong unforgeability, non-transferability, privacy of the signer's identity (PSI) and undeniability. The unforgeability requires that only the signer and the designated verifier can produce a valid signature. Formally, the strong unforgeability of an SDVS scheme is defined by the following game between a challenger \(\mathcal{C}\) and an adversary \(\mathcal{F}\). * _Setup_: \(\mathcal{C}\) executes the **Setup** algorithm to output the public parameters _params_, and runs the **KeyGen** algorithm to generate the signer's key pair \((pk_{S},\ sk_{S})\), the designated verifier's key pair \((pk_{V},\ sk_{V})\) and the arbiter's key pair \((pk_{A},\ sk_{A})\). Then, \(\mathcal{C}\) sends \((params,pk_{S},pk_{V},pk_{A})\) to \(\mathcal{F}\). * _Signing queries_: When \(\mathcal{F}\) initiates a signature query for message \(m_{i}\), \(\mathcal{C}\) runs the \(\textbf{Sign}(pk_{S},pk_{V},pk_{A},\)\(sk_{S},m_{i})\) algorithm to obtain a signature \(\sigma_{i}\) on \(m_{i}\) and returns \(\sigma_{i}\) to \(\mathcal{F}\). * _Simulating queries_: When \(\mathcal{F}\) asks for a simulated signature on a message \(m_{i}\), \(\mathcal{C}\) runs the \(\textbf{Sim}(pk_{S},pk_{V},\ pk_{A},sk_{V},m_{i})\) algorithm to obtain a signature \(\sigma^{\prime}_{i}\) on \(m_{i}\) and returns \(\sigma^{\prime}_{i}\) to \(\mathcal{F}\). * _Verifying queries_: When \(\mathcal{F}\) submits a signature \(\sigma_{i}\) on a message \(m_{i}\), \(\mathcal{C}\) sends the signature verification result output by the algorithm **Verify\((pk_{S},pk_{V},pk_{A},sk_{V},m_{i},\sigma_{i})\)** to \(\mathcal{F}\). * _Output_: Finally, \(\mathcal{F}\) outputs a message/signature pair \((m^{*},\sigma^{*})\). \(\mathcal{F}\) wins the game if 1. **Verify\((pk_{S},pk_{V},pk_{A},sk_{V},m^{*},\sigma^{*})\)**=1. 2. \((m^{*},\sigma^{*})\) has not been produced by the _Simulating_ query. 3. \((m^{*},\sigma^{*})\) is not one of all tuples \((m_{i},\sigma_{i})\) during the _Signing_ queries. Definition 3: If the probability of any PPT attacker \(\mathcal{F}\) winning in the above game is negligible, then an SDVS scheme is said to be strongly unforgeable against adaptive chosen message attacks.