In this master graduate thesis, we studied on Identity-Based Cryptosystem which is a popular research direction in recent years.

In the history of the cryptography, many attempts have been made to solve the problem of establishing secure communications, from symmetric and traditional public-key cryptography. In the 1970's, military networks, academic systems, interbank protocols and ATMs were the early adopters of modern cryptography, using system based on symmetric cryptography. These symmetric cryptosystems, the best known of which is the Data Encryption standard(DES) were widely used throughout the 1980's. However, it became clear that while symmetric cryptography was adequate for small contained networks with a limited number of users, it could not handle the volume of traffic brought on by the internet boom. This is due to the private key distribution problem. A new class of algorithms (called asymmetric or public key) were developed; the most well-know of these algorithms is RSA. Systems based on these algorithms, commonly called PKI, were introduced to the market in the late 1980's. In the PKI model, different keys: a public key and a private key are used to encrypt(sign) and decrypt(verify) messages. These public keys are often distributed using certificates, which are issued by a third party certificate server. While PKI has successed in certain server-side systems, it has proven to be cross-enterprise usage due to the administrative burden of certificates, revocation lists, etc.

In 1984, Shamir [1] first proposed the idea of ID-Based cryptosystem. It is a public key cryptosystem, but it is different from the original one. The most important concept in his paper is that the public key of the system is the identity of the users. The identity could be user's e-mail address or IP address. For example, when Alice sends mail to Bob at, she simply encrypts her message using the public key string There is no need for Alice to obtain Bob's public key certificate. When Bob receives the encrypted mail he contacts a third party which we call the Trust Authority(TA) center. Bob authenticates himself to the TA center and obtains the private key. Although Shamir proposed the ID-Based cryptosystem in 1984, on one can actually builds such system until 2001. Boneh and Franklin [2] and Cocks [3] independently built ID-based cryptosystem according to the Shamir's idea. In 2002, Craig Gentry and Alice Silverberg[20] proposed the idea of Hierarchical ID-based cryptosyetem. The motivation behind their scheme is the overload of the TA center in the original ID-based system. In order to release the burden of the TA center, they suggest that TA center authorizes the private key generation ability to the lower layer of the authority. Thus we have the hierarchical model of ID-Based system. Recent research on ID-Based cryptosystem is mainly carried on under this two models.

[20] discoverd that all Hierarchical ID-based encryption scheme could be transformed into Hierarchical ID-based signature scheme. We analysis several most recent famous ID-Based schemes. We found that after being transformed into Hierarcical ID-Based signature scheme, the signature size is not constant. Thus lots of bandwidth will be taken when communications take place. It is natural to consider if we can build a hierarchical ID-Based signature scheme which has constant signature size. This is also the intuition behind our scheme. Besides the constant signature size, our scheme can be proven secure under q-SDH problem without using random oracle model. A random oracle is a theoretical black box that responds to every query with a random response chosen uniformly from its output domain. Random oracles are a mathematical abstraction used in cryptography proofs. A system that is proven secure using such a proof is described as being secure in the random oracle model, as opposed to secure in the standard model. In practice, random oracle are typically used to model cryptographic hash functions in schemes. Since no real function can implement a true random oracle, the security of the schemes that proved under random oracle model may rely heavily on the security of the hash function. In order to avoid these, our scheme does not use random oracle model.
It is interesting that the verification of our HIBS scheme could be looked as a three combinations of the Dan Boneh's short signature verifications. Our security model requires that adversary has to submit all the first layer of the identities that he wants to query at the beginning. This is different from the selective ID model.

There are some problems exists in ID-based cryptosystem which we need to study in the future works. Generally speaking, key escrow problem and revocation problem are the most important ones. Key Escrow problem is a born weakness of the ID-based cryptosystem and the revocation problem is about when some user loses his/her private key, do we need to change his/her corresponding public key(ID)? Yet, we do not know any efficient solutions to the above problems. Thus it leaves us as a challenge in the future.