The design of IDbased cryptography has received much attention from researchers. However, how to revoke the misbehaviour/compromised user in IDbased public key cryptosystem becomes an important research issue. Recently, Tseng and Tsai proposed a novel public key cryptosystem called revocable IDbased public key cryptosystem (RIBE) to solve the revocation problem. Later on, numerous research papers based on the TsengTsai key RIBE were proposed. In this paper, we brief review Tseng and Tsais RIBE. We hope this review can help the readers to understand the Tseng and Tsais revocable IDbased public key cryptosystem.
Identitybased ; Revocable ; Encryption ; Bilinear pairings
In the traditional public key cryptosystems (Diffie and Hellman, 1976 , ElGamal, 1985 and Rivest et al., 1978 ), certificates play important roles to make publicly available the mapping between identities and public keys. Certificate is a signature generated by a trusted certificate authority (CA) which usually include the identity of a user, its associated public key, the issuing date and the expiration date. When users public key is used, the associated certificate must be checked to ensure its validity (revoked or nonrevoked). In general, Certificate Revocation List (CRL) (Housley et al., 2002 ) is used to revoke the users public key. Anyone can check these revoked users’ public keys by querying the CRL.
In order to solve the management of users’ certificates, Shamir (1984) first proposed the concept of IDbased public key cryptosystem (IDPKS). In his system, each users identity (e.g. email address or social security number) can be viewed as public key and the users private key is generated by a trusted private key generation center (PKG). However, Shamir’ IDPKS was not easy in practice because the underlying mathematical methods are not suitable. In 2001, Boneh and Franklin, (2001) followed Shamirs concept to propose a practical IDbased encryption scheme (IBE) from the Weil pairing. Later on, the design of IDbased cryptographic schemes and protocols using bilinear pairings has received much attention from researchers.
For the revocation problem in the IDPKS system, Boneh and Franklin, (2001) have suggested a solution in which the PKG can periodically renew the private keys for nonrevoked users. In other words, when the PKG wants to revoke a specific user, it only stops to issue the new private key. However, this solution has following drawbacks: (1) the workload of generating new private keys of nonrevoked users is too heavy for the PKG; (2) secure channels are needed between the PKG and the nonrevoked users to transmit the new private keys for each time period.
Boldyreva et al. (2008) proposed a revocable IDbased encryption scheme (RIBE) by using binary tree to reduce the PKGs workload in the Boneh–Franklin IBE. Unfortunately, their scheme is based on the relaxed selectiveID model (Canetti et al., 2003 ), a weak security model. In the next year, Libert and Vergnaud (2009) based on the Boldyreva et al.’s RIBE to propose a more secure RIBE scheme under an adaptiveID model, a strong security model. Seo and Emura (2013a) demonstrated Boldyreva et al.’s RIBE (Boldyreva et al., 2008 ) is vulnerable to the decryption key exposure. They also proposed a provably secure treebased revocable IDbased encryption scheme. Subsequently, Seo and Emura (2013b) presented a hierarchical revocable IDbased encryption scheme which solved the open problem mentioned in the Libert–Vergnaud RIBE.
Tseng and Tsai (2012) proposed a practical RIBE scheme over a public channel. The key construction their scheme is different from the previous schemes (Boldyreva et al., 2008 , Libert and Vergnaud, 2009 , Seo and Emura, 2013a and Seo and Emura, 2013b ). In the TsengTsai RIBE, each users private key consists of a fixed initial private key and an updating time key, where the updating time key is renewed along with the current period. For an honest (nonrevoked) user, the PKG periodically issues new time key and sends it to the user via a public channel. Upon receiving the new time key, the user can renew her/his private key by herself/himself. To revoke a malicious/misbehaviour user, the PKG only stops issuing the new time key in current period. In other words, the malicious/misbehaviour user cannot compute the newest private. She/he cannot execute any cryptographic behaviours in later periods. Later on, several revocable IDbased cryptographic schemes and protocols based on the key construction of the TsengTsai RIBE were proposed such as encryption (Tsai et al., 2012 and Tsai et al., 2014 ), signature (Hung et al., 2014 , Tsai et al., 2013 and Wu et al., 2012a ), signcryption (Wu et al., 2012b ), and authenticated group key exchange (Wu et al., 2012 and Wu et al., 2014 ).
In this paper, we brief review Tseng and Tsais RIBE scheme which contains the underlying mathematical problems and assumptions, the framework of RIBE, a concrete RIBE scheme, the security notion of RIBE, the security analysis of RIBE (sketched), and a full RIBE scheme. We hope this review can help the readers to understand the Tseng and Tsais revocable IDbased public key cryptosystem.
Bilinear pairings defined on elliptic curves over finite fields have been used to establish many IDbased cryptographic mechanisms. Let G_{1} be an additive cyclic group of large prime order q and G_{2} be a multiplicative cyclic group of the same order q . Specifically, particular, G_{1} is a subgroup of the group of points on an elliptic curve over a finite field and G_{2} is a subgroup of the multiplicative group over a finite field. A bilinear pairing is a map e : G_{1} × G_{1} → G_{2} and satisfies the following three properties:
A bilinear map that satisfies the above three properties is called an admissible bilinear map. Such nondegenerate admissible bilinear maps can be obtained from the Weil, Tate, or Ate pairings over supersingular elliptic curves or abelian varieties (Boneh and Franklin, 2003 and Chen et al., 2007 ). Some research results (Galbraith et al., 2008 and Wu and Tseng, 2010 ) for the relationship between security levels and speed of pairing computations on microprocessors were presented.
The BDH assumption is often used in the security proof of IDbased encryption scheme. The BDH problem is described as follows. Given P , aP , bP , cP ∈ G_{1} for some , this problem is to compute the value e (P , P )^{abc} ∈ G_{2} . The BDH assumption is stated as follows.
Given an additive cyclic group G_{1} and P , aP , bP , cP ∈ G_{1} for unknown , no probabilistic polynomial time (PPT) algorithm A with nonnegligible probability which can compute e (P , P )^{abc} ∈ G_{2} . The successful probability (advantage) of A is presented as

where the probability is over the random choice consumed by A .
The TsengTsai RIBE consists of two roles: a trusted PKG and users. Without loss of generality, the whole lifetime of the system is divided into distinct time periods 1, 2, …, z . For simplicity, these time periods may be viewed as 1 day, 1 week, or 1 month. The PKG selects a master secret key and generates public parameters. For a given users identity ID, the PKG computes his/her associated initial private key and sends it to the user via a secure channel. At the beginning of each time period, the PKG uses the master secret key to generate a time updating key for each nonrevoked users identity ID and then sends them to users via a public channel. For a revoked user, it is unable to receive the associated time updating key in the current time period.
For a RIBE, the point is that any sender can encrypt a message to some identity ID without concerning with the key updating process. In a RIBE, encrypting a message m to a receiver with identity ID during time period i that results in a ciphertext tuple (ID, i , C ). Upon receiving (ID, i , C ), a nonrevoked user with the valid private key can recover the message m .
A RIBE with a public channel is a 5tuple of polynomialtime algorithms (G , IKE , TKU , E , D ):
The users entire private key DID_{i} for the time period i is not explicitly provided for the user. Each legitimate (nonrevoked) user may obtain the corresponding entire decryption key DID_{i} by DID_{i} = DID + TID_{i} , where the users initial private key DID is generated by the initial key extract algorithm and the users time updating key TID_{i} is periodically generated by the PKG along with time.
Basic RIBE scheme consists of five algorithms: the system setup, the initial key extract, the time key updating, the encryption, and the decryption algorithms.
Here, we present the correctness of the decryption equation as follows:

Tseng and Tsai followed the security requirement of IBE (Boneh and Franklin, 2001 ) to propose the requirements of RIBE. A RIBE is semantically secure against an adaptive CPA (INDRIDCPA) if no PPT adversary A has a nonnegligible advantage against the challenger B in the following INDRIDCPA game:
The restriction here is that either ID* or (ID*, i *) is disallowed to be queried in the initial key extract query or the time key update query, respectively.
We refer to such an adversary A as an INDRIDCPA adversary. We define the adversary A s advantage in attacking the RIBE as the following function of the security parameter k: Adv_{A} (k ) = Pr[β ′ = β ] − 1/2.
We say that a RIBE is semantically secure against an adaptive CPA if, for any polynomial time INDRIDCPA adversary A , the function Adv_{A} (k ) is negligible.
Then, a more secure security model than CPA model is introduced called CCA model. We say that a RIBE is semantically secure against an adaptive CCA (INDRIDCCA) if no PPT adversary A has a nonnegligible advantage against the challenger B in the following INDRIDCCA game:
The restriction here is that either ID* or (ID*, i *) is disallowed to be queried in the initial key extract query or the time key update query, respectively.
We refer to such an adversary A as an INDRIDCCA adversary. We define the adversary A s advantage in attacking the RIBE as the following function of the security parameter k: Adv_{A} (k ) = Pr[β ′ = β ] − 1/2.
We say that a RIBE is semantically secure against an adaptive CPA if, for any polynomial time INDRIDCCA adversary A , the function Adv_{A} (k ) is negligible.
In the INDRIDCPA and INDRIDCCA games, an adversary A is disallowed to issue both an initial key extract query on ID* and a time key update query on (ID*, i *) because it is obvious that the users entire decryption key will be revealed. Hence, it is only allowed that the adversary A may issue either the initial key extract query on ID* or the time key updating query on (ID*, i *). If the initial key extract query on ID* is allowed, it simulates the ability of a revoked user (an inside adversary) without the corresponding time key update key for time period i *. On the other hand, an outside adversary is only allowed to obtain the time key update key for time period i *. Certainly, the adversary A is allowed to obtain the initial key and the time key for any other ID and any time period.
Tseng and Tsai applied the work of Boneh and Franklin, (2001) to provide a tight security proof in the random model (Bellare and Rogaway, 1993 and Canetti et al., 2004 ). The following two theorems are given to show that the Basic RIBE scheme is semantically secure against adaptive CPA (INDRIDCPA) for the outside adversary and the revoked user (or an inside adversary).
Suppose that the hash functions H_{0}, H_{1}, and H_{2}are random oracles. Then the basic RIBE is a semantically outsidersecure IBE scheme (INDORIDCPA) assuming that the BDH problem is hard in groups generated by G. Concretely, assume that there is an outside adversary A that has advantage ɛ(k) against the Basic RIBE scheme. Suppose that A makes at most q_{E} > 0 initial key extraction queries, q_{U} > 0 time key updating queries, and q_{Hi} > 0 queries to hash functions H_{i}(i = 0, 1, 2). Then there is an algorithm B that solves the BDH problem in groups generated by G with advantage at least Adv_{G,B}(k) = 2ɛ(k)/[e(1 + q_{E})·q_{H2}], where e is the base of the natural logarithm .
Suppose that the hash functions H_{0}, H_{1}, and H_{2}are random oracles. Then the basic RIBE is a semantically insidersecure IBE scheme (INDIRIDCPA) assuming that the BDH problem is hard in groups generated by G. Concretely, assume that there is an outside adversary A that has advantage ɛ(k) against the basic RIBE scheme. Suppose that A makes at most q_{E} > 0 initial key extraction queries, q_{U} > 0 time key updating queries, and q_{Hi} > 0 queries to hash functions H_{i}(i = 0, 1, 2). Then there is an algorithm B that solves the BDH problem in groups generated by G with advantage at least Adv_{G,B}(k) = 2ɛ(k)/[e(1 + q_{U}) ·q_{H2}], where e is the base of the natural logarithm .
Fujisaki and Okamoto (1999) presented a simple conversion from a weak publickey encryption scheme (INDCPA) to a strong publickey encryption scheme (INDCCA) in the random oracle model. Kitagawa et al. (2006) proposed an improvement on Fujisaki and Okamotos (1999) conversion to IBE. They can transform a weak IBE scheme (INDIDCPA) to a strong IBE scheme (INDIDCCA). In Kitagawa et al.’s conversion, a weak IBE scheme (INDIDCPA) must be γ uniformity, where γ uniformity means that the used hash functions are random oracles. Meanwhile, the weak IBE scheme must be proved to be semantically secure against an adaptive CPA (INDRIDCPA). Meanwhile, an extra hash function (also random oracle) must be added to the system to achieve strong IBE scheme.
Based on the basic RIBE scheme (INDRIDCPA), Tseng and Tsai applied the transformation technique (Kitagawa et al., 2006 ) to construct the full RIBE scheme (INDRIDCCA). The full RIBE scheme consists of five algorithms that include the system setup , the initial key extract , the time key updating , the encryption , and the decryption algorithms.
For the general transformation from a basic IBE scheme with γ uniformity to a full IBE scheme, Kitagawa et al. have already given a theorem to prove the security of the full IBE scheme (INDIDCCA) using the basic IBE scheme (INDIDCPA). Here, we introduce their theorem. Without loss of generality, let Π_{1} and Π_{2} be the basic IBE scheme and the full IBE scheme, respectively. An extra hash function is .
Suppose that the hash function H is a random oracle and Π_{1}is a γuniform basic IBE scheme. Let A be an INDIDCCA adversary that has an advantage ɛ(k) against the full IBE scheme Π_{2}. Suppose the challenger B makes at most q_{H} > 0 queries to hash function H, q_{E} > 0 initial key extraction queries, and q_{D} > 0 decryption queries. Then, there is an INDIDCPA adversary that has advantage at least (ɛ(k) + 1/2 − q_{H}/2^{n−l})·(1 − γq_{D}) − 1/2 against the basic IBE scheme Π_{1} .
Since the hash functions used in the basic RIBE scheme are random oracles, it is γ uniformity ( Fujisaki and Okamoto, 1999 and Kitagawa et al., 2006 ). The full RIBE scheme is constructed from basic RIBE scheme by applying the general transformation technique proposed by Kitagawa et al. (2006) . Thus, we can enjoy Theorem 3 to obtain two theorems, directly. The following two theorems state that the full RIBE is semantically outsidersecure (INDORIDCCA) and insidersecure (INDIRIDCCA) based on the basic RIBE scheme.
Suppose that the hash function H_{3}is a random oracle. Let A be an outsider adversary (INDORIDCCA) which has advantage ɛ(k) against the full RIBE scheme. Suppose the challenger B makes at most q_{Hi} > 0 queries to hash functions H_{i}(i = 0, 1, 2, 3), q_{E} > 0 initial key extraction queries, q_{U} > 0 time key updating queries, and q_{D} > 0 decryption queries. Then there is an outsider adversary (INDORIDCPA) that has advantage at least (ɛ(k) + 1/2 − q_{H3}/2^{n−l})·(1 − γq_{D}) − 1/2 against the basic RIBE scheme .
Suppose that the hash function H_{3}is a random oracle. Let A be an insider adversary (INDIRIDCCA) which has advantage ɛ(k) against the full RIBE scheme. Suppose the challenger B makes at most q_{Hi} > 0 queries to hash functions H_{i}(i = 0, 1, 2, 3), q_{E} > 0 initial key extraction queries, q_{U} > 0 time key updating queries, and q_{D} > 0 decryption queries. Then there is an outsider adversary (INDIRIDCPA) that has advantage at least (ɛ(k) + 1/2 − q_{H3}/2^{n−l})·(1 − γq_{D}) − 1/2 against the basic RIBE scheme .
In this paper, we have given a brief review of Tseng and Tsais RIBE. We have introduced the underlying mathematical problems and assumptions, framework of RIBE, two concrete RIBE schemes (basic RIBE and full RIBE), sketched security analysis of two RIBE schemes. For the details of security analysis, readers can refer to the full paper.
The authors declare that there is no conflict of interest.
This publication has been created within the project Support of VŠBTUO activities with China with financial support from the MoravianSilesian Region and partially was supported by the grant SGS reg. no. SP2015/82 conducted at VSBTechnical University of Ostrava, Czech Republic, and was partially supported by the Natural Scientific Research Innovation Foundation in Harbin Institute of Technology under grant no. HIT.NSRIF.2015089, by the National Natural Science Foundation of China under grant no. 61402135, by the Shenzhen Strategic Emerging Industries Program of China under grant no. ZDSY20120613125016389.
Published on 05/10/16
Licence: Other
Are you one of the authors of this document?