Paper 2009/518

Efficient Strong Designated Verifier Signature Schemes without Random Oracles or Delegatability

Qiong Huang, Guomin Yang, Duncan S. Wong, and Willy Susilo

Abstract

Designated verifier signature (DVS) is a cryptographic primitive that allows a signer to convince a verifier the validity of a statement in a way that the verifier is unable to transfer the conviction to a third party. In DVS, signatures are publicly verifiable. The validity of a signature ensures that it is from either the signer or the verifier. Strong DVS (SDVS) enhances the privacy of the signer so that anyone except the designated verifier cannot verify the signer's signatures. In this paper we propose a highly efficient SDVS scheme based on pseudorandom functions, which is proved to be secure in the standard model. Compared with the most efficient SDVS scheme secure in the random oracle model, our scheme has almost the same complexity in terms of both the computational cost of generating a signature and signature size. A signature of our scheme is simply the output of a pseudorandom function. The security of the scheme is tightly reduced to the hardness of DDH problem and the security of the pseudorandom function. Since our scheme is vulnerable to delegatability attacks, the study of which was initiated by Lipmaa, Wang and Bao in ICALP 2005, we then propose another construction of SDVS, which is the \emph{first} one immune to delegatability attacks. The scheme is also very efficient, and has the same signature size with that of Lipmaa-Wang-Bao non-delegatable DVS scheme. We show that it is secure based on discrete logarithm assumption and gap Diffie-Hellman assumption in the random oracle model.