Degree Name

Doctor of Philosophy


School of Computer Science and Software Engineering - Faculty of Informatics


In an ordinary digital signature scheme, the verification of a signature requires the associated message, the signer’s public key and other public information (e.g. public parameter). Anyone in the system can verify the validity of the digital signature. This property is useful, as it has many applications. However, it is undesirable for some situations where signer’s privacy is a concern, especially in personally and commercially sensitive applications. In this thesis, we investigate several special signature schemes that accommodate the signer privacy.

In undeniable signatures, the most distinctive feature is that the signer is able to choose who can be convinced about his/her undeniable signature, as the validity of an undeniable signature can only be verified in collaboration with the signer. The property selective convertibility enables the signer to convert one or more undeniable signatures into ordinary digital signatures at some time later, while one can make all his/her undeniable signatures publicly verifiable in an undeniable signature scheme with universal convertibility. Undeniable signatures with selective and universal convertibility have found many applications in practice such as keeping digital records of confidential political decisions. However, the most known constructions bear a long signature length and some schemes can only be proven secure under strong complexity assumptions. In this thesis, we describe a new undeniable signature scheme with selective and universal convertibility, of which the signature length is the shortest among all comparable ones and the security can be reduced to weaker complexity assumptions. This scheme is considered in the traditional public key infrastructure, where the authenticity of a user’s public key is ensured by certificates. We also provide the first selectively and universally convertible undeniable signature scheme where a user’s public key is his/her identity.

Designated verifier signatures bridge the gap between ordinary digital signatures and undeniable signatures, in the sense that they will limit who can be convinced by the signer’s signature without any collaboration with the signer. The designated verifier can be chosen by the signer in the generation of designated verifier signatures. Although the verification of a designated verifier signature usually needs only public information, only the designated verifier can believe that the designated verifier signature has been generated by the signer. This is due to the fact that the designated verifier is able to generate designated verifier signatures which are indistinguishable from those produced by the signer. Strong designated verifier signatures provide a higher level of privacy, as anyone cannot even verify the validity of strong designated verifier signatures with public information. All known constructions of strong designated verifier signatures have a relatively long signature length and require costly operations, which affect the overall performance of the system. In this thesis, we present two new constructions of strong designated verifier signatures, in traditional public key infrastructure and in identity-based cryptography, respectively. Both schemes have high computational efficiency, short signature length and provable security in the random oracle model.

We finally consider universal designated verifier signatures, which can be viewed as an application of the general idea of designated verifier signatures. This notion was introduced to address the user privacy issue in certification systems, where a certificate holder (or more generally, a signature holder) wishes to generate a proof which can prove to a designated verifier his/her possession of the certificate, but does not want anyone else to be convinced. Universal designated verifier signatures achieve this by giving the designated verifier the full ability to generate that proof. The conviction thus is no longer transferable. In this thesis, we revise the notion of non-transferability in universal designated verifier signatures and give a new definition, which is meaningful both in theory and in practice. Our analysis, however, shows that not all existing schemes have that property. We describe a new universal designated verifier signature scheme, which can be proven secure without random oracles and has the property of non-transferability defined in this thesis. This thesis also investigates another property “delegatability”, which was previously believed as an inherent flaw in universal designated verifier signatures. We show that this problem can be overcome by proposing the first universal designated verifier signature scheme without delegatability.

02Whole.pdf (870 kB)