Public Key Cryptosystems (PKC) were first introduced by Diffie and Hellman [10]. The advantages of PKC have been proved through various applications. A traditional application of PKC is to issue a digital signature on a document. In PKC, a person has a key pair which contains a public key and the corresponding private key. Using the private key, a person can produce digital signatures on documents to prove that those documents are indeed generated by him. Anyone can easily verify the signatures on those documents using the public key of that person. Thus, the integrity of the documents is protected by the digital signatures on those documents.
A $\emph{threshold}$ digital signature scheme requires a certain number of people to produce digital signatures on documents. In other words, the secret key used to sign documents is distributed (in pieces) among some people. To sign a document a certain number of people (threshold value) have to cooperate in order to construct the digital signature on the document.
A $\emph{blind}$ digital signature scheme, first proposed by Chaum [8], is an important cryptographic component in many applications. Using a blind signature scheme, a user can get signature on a message from a signer without revealing the message content. Both types of signature are playing important roles in cryptography as well as practical applications such as e-cash and e-voting systems.
In this thesis, we construct a new threshold blind digital signature based on pairings without a trusted third party, which combines the notions of a threshold digital signature and a blind digital signature. A threshold blind digital signature allows possession of a private key to be distributed among a group of signers while a user can get a signature on a message without revealing the message content. Threshold blind digital signatures have various applications. For example, using such signatures we can design protocols for secure distributed electronic banking, or secure electronic voting with multiple administrators. Our scheme operates on Gap Diffie-Hellman ($\emph{GDH}$) group, where CDH problems are hard while DDH problems are easy. For instance, we use pairings that could be built from Weil pairing or Tate pairing. With this construction, the scheme is more efficient than previous ones with respect to signature size while keeping the same level of security. We prove that the proposed signature scheme is secure against the well known attacks if CDH problem is intractable in the random oracle model. We also compare this scheme with other threshold blind signature schemes. To the best of our knowledge, we claim that our scheme is the first threshold blind signature using pairings with provable security in the random oracle model.
