Document Type  Conference Paper   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 thr