Degree Name

Doctor of Philosophy


School of Computer Science and Software Engineering


Third parties are very common in modern cryptography, both in symmetric cryptographic applications (e.g., a key distribution protocol and a non-repudiation protocol) and public key cryptographic systems (e.g., the certi cate authority and the private key generator in identity-based cryptography). A widely used approach is to assume that a third party has a certain level of trust, but is not fully trusted. In this thesis, we present several new results about cryptosystems, which do not require any fully trusted third party. We provide detailed schemes and security analysis on server-aided veri cation signatures, certi cate-based signatures and encryption, and optimistic fair exchange.

The computational cost required by cryptographic protocols is a signi cant burden to power-constrained devices such as smart cards and mobile terminals. Serveraided computation is a promising solution to mitigate this issue by employing a powerful server to carry out costly cryptographic computation. Such techniques require an additional care since servers cannot be fully trusted. In this thesis, we investigate the issues of server-aided veri cation signatures, i.e., using server(s) to assist signature veri cation. Several notions in digital signatures with server-aided veri cation are formally de ned, based on di erent trust levels of the server. As instances, we provide server-aided veri cation protocols for Boneh-Lynn-Shacham (BLS) signature (with the random oracle assumption) and Waters signature (without the random oracle assumption).

As cryptographic primitives, certi cate-based public key cryptography (CB-PKC) and certi cateless public key cryptography (CL-PKC) are used to ease certi cate management and solve key escrow problems due to the trust third party in identitybased public key cryptography. As one of features, the signature veri cation (resp. encryption) does not require public key authenticity check. In this thesis, we take a closer look at the relationship between certi cateless cryptosystem and certi catebased cryptosystem, present the security de nitions of certi cate-based signatures and certi cate-based encryption, and provide generic constructions of certi catebased signatures from certi cateless signatures and certi cate-based encryption from certi cateless encryption, respectively. The proposed generic constructions are proven to be secure in the random oracle model.

An off-line trusted third party (arbitrator) plays an important role in optimistic fair exchange (OFE), which allows two parties to exchange their digital items in a fair way. As one of the fundamental problems in secure electronic business and digital rights management, OFE has been studied intensively since its introduction. This thesis introduces and de nes a new property for OFE: Strong Resolution- Ambiguity. We show that many existing OFE protocols have the new property, but its formal investigation has been missing in those protocols. We prove that in the certi ed-key model, an OFE protocol is secure in the multi-user setting if it is secure in the single-user setting and has the property of strong resolutionambiguity. An OFE protocol has the property of strong resolution-ambiguity if one can transform a partial signature σʹ into a full signature σʹ using signer's private key or arbitrator's private key, and given such a pair (σʹσ), it is infeasible to tell which key is used in the conversion. Our result not only simpli es the security analysis of OFE protocols in the multi-user setting but also provides a new approach for the design of multi-user secure OFE protocols. In addition, a new OFE protocol with strong resolution-ambiguity is proposed. Our analysis shows that the protocol is setup-free, stand-alone and multi-user secure without the random oracle assumption.