Universal Designated Verifier Signature proof (or how to efficiently prove knowledge of a signature)

Proving knowledge of a signature has many interesting applications. As one of them, the Universal Designated Verifier Signature (UDVS), introduced by Steinfeld et al. in Asiacrypt 2003 aims to protect a signature holder’s privacy by allowing him to convince a verifier that he holds a valid signature from the signer without revealing the signature itself. The essence of the UDVS is a transformation from a publicly verifiable signature to a designated verifier signature, which is performed by the signature holder who does not have access to the signer’s secret key. However, one significant inconvenience of all the previous UDVS schemes considered in the literature is that they require the designated verifier to create a public key using the signer’s public key parameter and have it certified to ensure the resulting public key is compatible with the setting that the signer provided. This restriction is unrealistic in several situations where the verifier is not willing to go through such setup process. In this paper, we resolve this problem by introducing a new type of UDVS. Different from previous approach to UDVS, our new UDVS solution, which we call “Universal Designated Verifier Signature Proof (UDVSP)”, employs an interactive protocol between the signature holder and the verifier while maintaining high level of efficiency. We provide a formal model and security notions for UDVSP and give two constructions based on the bilinear pairings. We prove that the first construction is secure in the random oracle model and so is the second one in the standard model.