Short Strong Designated Verifier Signature

The concept of Designated Verifier Signature(DVS for short) was first presented by Jakobsson, Sako and Impagliazzo at Europcrypt'96 and independently by Chaum in his patent, under the name private signatures. Designated Verifier Signature is intended to a specific and unique designated verifier, who is the only one that is able to believe the signature's validity. This designated verifier cannot convince any third party that the signature is actually valid, especially because the designated verifier can also generate a signature which is indistinguishable from the original one. This kind of signature has wide applications in many areas, such as call for tenders, electronic voting and electronic auction.This master thesis considers a stronger notion of the designated verifier signature: Strong Designated Verifier Signature(SDVS for short). This kind of signature has the property that given two potential signing public keys with a strong designated verifier signature, it is computationally infeasible for an eavesdropper to determine under which of the two secret keys the signature was performed. There are several strong designated verifier signature schemes in the literature. However they all suffer from high computational cost and long signature length. After introducing the basics of the cryptology and (strong) designated verifier signature, two short strong designated verifier signature schemes are proposed: one in traditional public key system and the other in identity-based public key system.One of the advantages of the proposed schemes is the short length of the signature. The signature length is only |Z_q~*|, which is the shortest com-pared with all the existing SDVS schemes. Therefore the proposed schemes have low communication cost and more applicable in the networks with low bandwidth. Another advantage is that the proposed schemes have the least computational cost among all known SDVS schemes. Concretely, generating and verifying a signature only needs two exponentiations in traditional public key system and requires only two pairings in identity-based public key system. The computational cost is reduced dramatically and the new schemes are more applicable in the systems with limited computational resource.Both the two schemes satisfy all the properties of strong designated verifier signature and are provably secure under the Diffle-Hellman assumptions. What's more, the formal proofs of their security are presented.