Chosen-Ciphertext Secure Hierarchical Identity-Based Key Encapsulation Mechanisms

In 1984, Shamir managed to build an Identity-Based Encryption (IBE) scheme in which an entity's public identification information, such as an email address or a telephone number, can be used as a valid public key. For instance, in an IBE email system, when Alice wishes to send an email to Bob at bob@company.com, she simply encrypts the email using the public key string "bob@company.com", without the need for Bob's public key certificate. Once Bob receives the encrypted email, he authenticates himself to a trusted third party, which we call the Private Key Generator (PKG), to request his private key corresponding to the public identity bob@company.com. After receiving the private key, Bob can read the email. It was not until 2001 that the first efficient and provably secure IBE scheme was presented by Boneh and Franklin. Since then, this breakthrough technology has pushed back the boundaries of exploring schemes based on the idea of identity-based cryptography, and various extensions were developed, such as Hierarchical Identity-Based Encryption (HIBE) schemes and Identity-Based Key Encapsulation Mechanisms (IB-KEMs). An IBE scheme employs only one PKG (i.e., root PKG) to generate private keys to its users, while an HIBE scheme as a generalisation of IBE contains a hierarchy of PKGs, which can greatly reduce the workload of the root PKG by delegating identity authentication and private key generation to its descendant PKGs. By comparison with (H)IBE schemes, in some scenarios, a hybrid encryption scheme may be more attractive since it has an unrestricted message space and is efficient to perform encryption for large amounts of data. Such a scheme is separated into two parts: one part, called Key Encapsulation Mechanism (KEM), focuses on encrypting a symmetric key by public key techniques; while the other part, called Data Encapsulation Mechanism (DEM), concentrates on using the symmetric key to encrypt an actual message. The encryption of the key together with the encryption of the message is then sent to the intended recipient. Bentahar et al. extended the concept of KEM to the identity-based setting and developed a generic IB-KEM which is based on one of Dent's generic KEM constructions. A specific instantiation of the generic IB-KEM was given in the same paper and when combining it with a suitable DEM, we can produce a hybrid IBE scheme (IB-KEM/DEM) that is secure in a strong sense in the random oracle model. In this work, we primarily study how to extend the concept of KEM to the hierarchical identity-based setting, thereby achieving Hierarchical Identity-Based Key Encapsulation Mechanisms (HIB-KEMs). As to DEM, the other component of a hybrid HIBE scheme (HIB-KEM/DEM), we shall not deal with too much as it is relatively easy to acquire an appropriate DEM which works together with our HIB-KEMs to provide secure hybrid HIBE schemes. We first construct an HIB-KEM, which is secure in a strong sense in the random oracle model, from Gentry and Silverberg's basic HIBE scheme, which is secure in a weak sense in the random oracle model. In addition, we discuss how to shorten the length of encapsulated keys as the depth of a recipient increases in the resulting HIB-KEM. Next, we shift our attention to the constructions of HIB-KEM that are secure without random oracle models and present a couple of HIB-KEMs of this type. Basically, both HIB-KEMs are built on the Boyen-Mei-Waters Hierarchical Identity-Based Key Encapsulation Mechanism (BMW-KEM), but from different angles. The first one is as secure as the BMW-KEM, but having an improved efficiency. The efficiency is achieved by incorporating into the BMW-KEM a tag technique proposed by Abe et al., accordingly, replacing almost all the quite expensive pairing-based verifications for the validity of an encapsulated key with only one Message Authentication Code (MAC)-based verification. MAC can be quickly produced with the help of fast hash functions, such as MD5 or SHA-1, and the resulting overhead is trivial. The second one makes use of threshold technology to resolve the key escrow problem that is inherent in the original BMW-KEM. In the threshold BMW-KEM, at least a certain amount (threshold) of PKGs are required to cooperate for the decapsulation of a given encapsulated key