Degree Name

Doctor of Philosophy


School of Computer Science and Software Engineering


Digital signatures are one of important primitives of public-key cryptography. An ideal signature scheme should be provably secure in the standard model with weak assumption and tight reduction. It should also offer short parameters (e.g. public key, signing key and signature), signing efficiency, and verification efficiency. However, such an ideal signature scheme does not exist due to inherent tradeoffs in signature construction. Bilinear pairing is a popular mathematical tool towards constructing ideal signature schemes. In this thesis, we improve some well-known signature schemes constructed from bilinear pairings in terms of security and/or efficiency. The thesis is composed of the following nine chapters.

In Chapter 1, we introduce the evaluation of digital signatures in terms of security model, hard problem, reduction probability, parameter size, signing efficiency and verification efficiency. In Chapter 2, we introduce the background of digital signatures including the definition of digital signatures, the development of bilinear pairings and proposed signature schemes in the literature.

In Chapter 3, we improve short signatures with a tighter security reduction without random oracles. The Hofheinz-Kiltz signature scheme [HK08] is the first signature scheme whose signatures are less than 320 bits (80-bit security) in the standard model. However, their security reduction to the q-SDH assumption is loose. We utilize a new programmable hash function to construct short signature scheme such that the security proof has a tighter reduction. Taking security loss into account, for 80-bit security, our stateless signature scheme produces 286-bit signature only compared to 306 bits by [HK08]; our stateful signature scheme o ers 207-bit signature only compared to 266 bits by [HK08].

In Chapter 4, we improve Waters signature scheme [Wat05] with a tighter security reduction. The Waters signature scheme is the first provably secure scheme under the CDH assumption in the standard model. However, the security reduction is loose and dependent on the number of signature queries. We tighten the security proof by utilizing the technique of chameleon hash function. Our proposed signature scheme has a tighter reduction to the CDH assumption in the standard model, where the reduction probability is independent of the number of signature queries.

In Chapter 5, we improve q-SDH based signatures with a weaker assumption. Digital signature schemes based on the q-SDH assumption [BB04, Gen06] exhibit the nice features of short public key and strong unforgeability in the standard model. However, the q-SDH assumption is defined as a strong assumption, and one of the reasons is the exponential answers [HW09a]. We define a variant of the q-SDH assumption, where the answers to this modified assumption are no longer exponential but polynomial. We construct a digital signature scheme based on this modified assumption without losing the features of short public key, strong unforgeability and standard model.

In Chapter 6, we improve the security and efficiency of online/offline signatures. Online/offline signatures are desirable for quick signing in lightweight devices. We propose two online/offline signature schemes that are provably secure in the standard model and leakage-resilient in the online phase against unbounded computational leakage. Furthermore, our signature schemes are computationally efficient in the online phase (modular addition), and have a short signature (320 bits for 80-bit security).

In Chapter 7, we improve the efficiency of signature verification. With a precomputation, our proposed scheme does not need exponentiation computation or pairing computation to receive/verify signatures from a pre-defined signer. The remained verification cost for the signature receiver is the modular multiplication. We also show how to remove the modular multiplication when messages to be signed are partially known. Our signature scheme is suitable for those lightweight devices such as RFID tags where circuits are computationally weak.

In Chapter 8, we improve the server-aided verification protocols for pairing-based signatures [BB04, Gen06, BLS04]. With the help of server (or signer), our proposed schemes are not only computationally efficient for the verifier, but also require the fewest resources in hardware implementation. Precisely, in comparison with existing SAV protocols for signatures from pairings G1xG2 → GT, ours save the exponentiation circuit GT. Our SAV protocols are more suitable for those lightweight devices with limited hardware resource (circuit area) in algorithm implementation.

In Chapter 9, we summarize the contributions of this thesis and potential future work associated with secure and efficient digital signatures from bilinear pairings.