Year

2011

Degree Name

Master of Computer Science

Department

School of Computer Science and Software Engineering

Abstract

Digital signatures are used for proving the authorship of a given message. It is an important primitive of modern cryptography. To verify a signature, a user has to be equipped with a valid public key of the signer. A public key certificate issued by a trusted third party is required for public key authentication. It is necessary to verify the validity of a public key prior to verifying a signature, through a Public Key Infrastructure (PKI). However, the complexity of certificate management [ARP03] is a problem. Although the notion of identity-based signatures [Sha85] is introduced as a solution, key escrow is still an inherent problem.

The efficiency of a signature scheme and the size of a signature are two important aspects in evaluating a signature scheme. Taking PKI-based ring signature schemes as an example, they are inefficient in a large scale of applications [ALSY07]. This is due to the transport and verification costs of public key certificates. Low computational cost for signature signing and verification processes is required in practice. This thesis provides an efficient scheme to solve public key certificate management and key escrow problems, and reduce the communication cost of ring signature schemes.

To eliminate the need of public key certificates from traditional PKI and the problem of key escrow in identity-based cryptography, the concept of self-certified public keys was put forth by Girault [Gir91]. In this thesis, we propose an efficient and novel self-certified signature scheme, which requires only one modular multiplication in signing with pre-computation. One of the features of our scheme lies in its batch verification in both single-signer and multi-signer settings. Pairing computations in the batch verification are independent from the number of signatures. Our scheme is proved to be secure in the random oracle model.

Two similar solutions of the certificate management problem and the key escrow problem were proposed in 2003, namely certificateless public key cryptography andcertificate-based cryptography. In the signing process, both of them require two pieces of information where one is from a trusted third party and the other is chosen by a user itself. The validity of a user's public key is implicitly verified during the signature verification. However, it is different in self-certified signature schemes. The user's public key can not only be implicitly verified in the verification algorithm, but can also be computed explicitly. The computational cost of signature verification is reduced since there is no need to verify the user's public key after a valid key has been recovered. However, in the either certificateless signature schemes or certificatebased signature schemes, public key verifications are indispensable.

We also present a new notion called self-certified ring signatures (SCRS), to provide an alternative solution to the certificate management problem in ring signatures and eliminate the key escrow problem in identity-based ring signatures. A precise definition and elaborated security model of SCRS are provided, along with a concrete construction. We prove that our proposed scheme is secure in the random oracle model. This scheme captures all features of ring signatures, and exhibits the advantages of low storage, communication and computation cost.

Download

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.