# Generic Construction of Forward-Secure Revocable Identity-Based Signature and Lattice-Based Instantiations

Authors: Yan He; Baodong Qin; Wen Gao; Dong Zheng; Qianqian Zhao
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Forward-secure revocation is a powerful cryptographic technique to alleviate key exposure attacks on identity-based cryptosystems. In recent years, quantum computers have made some breakthroughs, so in the foreseeable future, existing cryptographic systems will be subject to quantum attacks. However, known forward-secure revocable identity-based signature (FS-RIBS) schemes were designed over bilinear pairing groups and may suffer from quantum computing attacks. To address this issue, this paper proposes a generic method to construct FS-RIBS schemes, taking (hierarchical) IBS schemes as a basic component. By instantiating it with some post-quantum (hierarchical) IBS schemes, e.g., lattice-based (hierarchical) IBS, we immediately obtain six FS-RIBS schemes under the hardness of the small integer solution problem, which is secure against quantum computing attacks.


---

## Body

## 1. Introduction

In 1984, Adi [1] first introduced an identity-based mechanism. The core idea is to use the user’s identity as a public key for encryption or a public key for verifying signatures and give the first identity-based signature (IBS). Compared with PKI, it does not need to issue public key certificates and other related complex steps, which improves efficiency. However, it was not until 2001 that Boneh [2] proposed an identity-based encryption scheme for the first time. Boneh’s [2] revocable mechanism has huge computational overhead. To reduce the runtime of revocable user computations, Ge and Wei [3] proposed a binary tree method in 2008 with a logarithmic increase in computational cost. However, it cannot resist key exposure attacks.In 2013, Seo and Emura [4] proposed a stronger definition and security model of RIBE (revocable identity-based encryption), which can resist decryption key exposure attacks. In 2014, they [5] also gave a new security definition of RIBS (revocable identity-based signature) scheme that can resist signing key exposure attacks and introduced a scalable RIBS scheme. In 2013, Tsai et al. [6] proposed a bilinear pair-based RIBS scheme under the standard model. All RIBS schemes before Tsai were constructed by the random oracle model. All subsequent RIBS schemes [7, 8] refer to Tasi’s security model and definition, where scheme [8] achieves the SU-CMA security under the standard model. However, the previous RIBS schemes cannot guarantee both efficient revocation and strong unforgeability simultaneously. In 2016, Liu et al. [9] proposed a strong unforgeable RIBS scheme that solves the above problems in the standard model. However, these RIBS schemes [6–8] cannot resist signing key exposure attacks. In 2018, Yang et al. [10] performed some optimizations based on [8]. Zhao et al. [11] also proposed an efficient communication scheme based on multi-linear mapping in 2019. With the imminent advent of quantum computers, the need for cryptographic schemes to resist quantum attacks is increasingly urgent. In 2015, Xiang [12] introduced the first lattice-based RIBS scheme using a complete subtree structure, which can prevent signing key exposure but requires a secret channel. In 2020, Xie et al. [13] proposed the RIBS scheme under the standard model on the lattice. Later in the same year, Xie et al. [14] proposed a scheme that can resist the exposure of the signature key. As recently as 2022, Xie et al. [15] proposed a fully homomorphic RIBS (RIBFHS) scheme, which is homomorphic and is the first RIBFHS scheme that considers signature key exposure on lattices. However, its security only is sID-EU-CMA and forward security cannot be guaranteed.Furthermore, forward security has also become a hot research topic. Its original intention is to ensure that the adversary cannot decrypt the ciphertext of the user’s last period or forge the signature of the previous period after the private key of the current period is leaked. At present, few works research on the forward security of revocable signatures; only Wei et al. [16] studied forward security of revocable IBS. However, their construction security is based on traditional difficult problems and cannot resist quantum attacks. Qin et al. [17] proposed the general structure of revocable forward security encryption in 2021. Its main idea combines a node selection algorithm and identity-based hierarchical encryption. As far as we know, there is no revocable forward-secure identity-based signature scheme on the lattice. So, in this work, we propose a generic method to construct a forward-secure revocable identity-based signature (FS-RIBS) and introduce two methods to improve its verification efficiency.


### 1.1. Our Contributions

This article is mainly inspired by Qin et al.’s work [17]. In this work, we research on FS-RIBS and its instantiations on lattices. In a FS-RIBS system (see Figure 1), we split each user’s private key into two parts: the first part is the secret key held by the user for a long time, and the second part is the signing key that is only available to sign messages signed within t time period. Any user’s “long-term” (this long-term secret key is not immutable, and it evolves once in each time period) secret key is also closely related to the time period and will change with the time period, while the verification key does not change. At the start of all time periods, KGC publishes the update key on the public channel to ensure that users who have not been revoked can sign typically.(i)
Firstly, we introduce the formal definition and security model for the FS-RIBS system. The system captures signing key exposure resistance, forward security, and user revocation.(ii)
Secondly, we give a generic construction of the FS-RIBS scheme. A forward-secure RIBS scheme is built on a hierarchical IBS scheme and a standard IBS scheme. The HIBS scheme was used to obtain the signing key of the user’s initial time period, and this initial signature key can deduce the signature key of the following time period. Then, a time-based update key is generated through IBS and a complete binary tree.(iii)
Thirdly, we further make two improvements to our proposed generic construction; although it will increase some signature overhead, both improvements can greatly improve the efficiency of verifying signatures and have tight security.(iv)
Finally, an instance of our generic construction on the lattice is given, which is secure against signing key exposure (SKE) attacks and is forward secure, and has scalability, as in the generic construction. We also present a comparison of our example with other related RIBS schemes, including classical and recent schemes, both bilinear map-based and lattice-based.Figure 1
FS-RIBS system.


### 1.2. Related Work

#### 1.2.1. Revocable Identity-Based Signature Schemes

The user’s revocable mechanism is a basic requirement for identity-based signatures. Boneh [2] mentioned for the first time that KGC generates a private key for each user who has not been revoked by cascading the user’s identity and time. Because the identity of each user is unique, this scheme has met forward security. However, this scheme does not have good scalability because the complexity of updating the key is ON−R, and time complexity increases with N−R. N refers to the total number of users, and R is the number of revoked users. Subsequently, Ge and Wei [3] introduced a structure that can reduce the size of the update key and reduced the update key size to ORlogN/R. Subsequently, some works [6, 8] proposed new RIBS schemes. In 2014, Seo and Emura [5] proposed a new security model of RIBS, which can resist signing key exposure attacks and introduced a scalable RIBS scheme. All the following works [17, 18] are based on the improvement of the security model of the scheme [5], either increasing security or improving efficiency. In 2017, Wei et al. [16] proposed a scheme that can resist the exposure of signature keys and ensure forward security. However, all the above solutions are not resistant to quantum attacks. To resist quantum attacks, Xiang [12] proposed a lattice-based RIBS scheme in 2015, but its cancellation operation requires a secure channel. Subsequently, Wei et al. [16] introduced a RIBS scheme based on the NTRU lattice that the update key can be updated on the open channel. In the next few years, Xie et al. [13–15] proposed some RIBS schemes. These schemes all improve the security of the scheme in some cases. However, none of the above schemes can guarantee forward security. For now, there is no RIBS scheme on the lattice that can guarantee forward security and resist signature key exposure attacks.


#### 1.2.2. Forward-Secure Signature Scheme

For forward security (FS), Anderson [19] firstly proposed the idea of forward-secure signature in 1997. Later, Bellare and Miner proposed a more efficient scheme [20] based on [19] and gave the formal definition and security model of forward security signature. More forward-secure digital signature algorithms [21, 22] have been proposed. However, there is little research on identity-based forward-secure digital signature algorithm. In 2008, Liu et al. introduced the first FS-IBS scheme in [23]. Zhang et al. [18] gave the first FS-IBS scheme in 2014. In 2021, Wu and Huang [24] further proposed an efficient forward security algorithm on the lattice, which has stronger security. But there is no revocable mechanism, it and cannot resist key exposure attacks. To the best of our knowledge, Wei et al. [16] first studied FS-RIBS and gave a construction. But, it is not resistant to quantum attacks. Qin et al. [17] proposed the general structure of revocable forward security for encryption in 2021. Its main idea combines a node selection algorithm and identity-based hierarchical encryption.


## 1.1. Our Contributions

This article is mainly inspired by Qin et al.’s work [17]. In this work, we research on FS-RIBS and its instantiations on lattices. In a FS-RIBS system (see Figure 1), we split each user’s private key into two parts: the first part is the secret key held by the user for a long time, and the second part is the signing key that is only available to sign messages signed within t time period. Any user’s “long-term” (this long-term secret key is not immutable, and it evolves once in each time period) secret key is also closely related to the time period and will change with the time period, while the verification key does not change. At the start of all time periods, KGC publishes the update key on the public channel to ensure that users who have not been revoked can sign typically.(i)
Firstly, we introduce the formal definition and security model for the FS-RIBS system. The system captures signing key exposure resistance, forward security, and user revocation.(ii)
Secondly, we give a generic construction of the FS-RIBS scheme. A forward-secure RIBS scheme is built on a hierarchical IBS scheme and a standard IBS scheme. The HIBS scheme was used to obtain the signing key of the user’s initial time period, and this initial signature key can deduce the signature key of the following time period. Then, a time-based update key is generated through IBS and a complete binary tree.(iii)
Thirdly, we further make two improvements to our proposed generic construction; although it will increase some signature overhead, both improvements can greatly improve the efficiency of verifying signatures and have tight security.(iv)
Finally, an instance of our generic construction on the lattice is given, which is secure against signing key exposure (SKE) attacks and is forward secure, and has scalability, as in the generic construction. We also present a comparison of our example with other related RIBS schemes, including classical and recent schemes, both bilinear map-based and lattice-based.Figure 1
FS-RIBS system.


## 1.2. Related Work

### 1.2.1. Revocable Identity-Based Signature Schemes

The user’s revocable mechanism is a basic requirement for identity-based signatures. Boneh [2] mentioned for the first time that KGC generates a private key for each user who has not been revoked by cascading the user’s identity and time. Because the identity of each user is unique, this scheme has met forward security. However, this scheme does not have good scalability because the complexity of updating the key is ON−R, and time complexity increases with N−R. N refers to the total number of users, and R is the number of revoked users. Subsequently, Ge and Wei [3] introduced a structure that can reduce the size of the update key and reduced the update key size to ORlogN/R. Subsequently, some works [6, 8] proposed new RIBS schemes. In 2014, Seo and Emura [5] proposed a new security model of RIBS, which can resist signing key exposure attacks and introduced a scalable RIBS scheme. All the following works [17, 18] are based on the improvement of the security model of the scheme [5], either increasing security or improving efficiency. In 2017, Wei et al. [16] proposed a scheme that can resist the exposure of signature keys and ensure forward security. However, all the above solutions are not resistant to quantum attacks. To resist quantum attacks, Xiang [12] proposed a lattice-based RIBS scheme in 2015, but its cancellation operation requires a secure channel. Subsequently, Wei et al. [16] introduced a RIBS scheme based on the NTRU lattice that the update key can be updated on the open channel. In the next few years, Xie et al. [13–15] proposed some RIBS schemes. These schemes all improve the security of the scheme in some cases. However, none of the above schemes can guarantee forward security. For now, there is no RIBS scheme on the lattice that can guarantee forward security and resist signature key exposure attacks.


### 1.2.2. Forward-Secure Signature Scheme

For forward security (FS), Anderson [19] firstly proposed the idea of forward-secure signature in 1997. Later, Bellare and Miner proposed a more efficient scheme [20] based on [19] and gave the formal definition and security model of forward security signature. More forward-secure digital signature algorithms [21, 22] have been proposed. However, there is little research on identity-based forward-secure digital signature algorithm. In 2008, Liu et al. introduced the first FS-IBS scheme in [23]. Zhang et al. [18] gave the first FS-IBS scheme in 2014. In 2021, Wu and Huang [24] further proposed an efficient forward security algorithm on the lattice, which has stronger security. But there is no revocable mechanism, it and cannot resist key exposure attacks. To the best of our knowledge, Wei et al. [16] first studied FS-RIBS and gave a construction. But, it is not resistant to quantum attacks. Qin et al. [17] proposed the general structure of revocable forward security for encryption in 2021. Its main idea combines a node selection algorithm and identity-based hierarchical encryption.


## 1.2.1. Revocable Identity-Based Signature Schemes

The user’s revocable mechanism is a basic requirement for identity-based signatures. Boneh [2] mentioned for the first time that KGC generates a private key for each user who has not been revoked by cascading the user’s identity and time. Because the identity of each user is unique, this scheme has met forward security. However, this scheme does not have good scalability because the complexity of updating the key is ON−R, and time complexity increases with N−R. N refers to the total number of users, and R is the number of revoked users. Subsequently, Ge and Wei [3] introduced a structure that can reduce the size of the update key and reduced the update key size to ORlogN/R. Subsequently, some works [6, 8] proposed new RIBS schemes. In 2014, Seo and Emura [5] proposed a new security model of RIBS, which can resist signing key exposure attacks and introduced a scalable RIBS scheme. All the following works [17, 18] are based on the improvement of the security model of the scheme [5], either increasing security or improving efficiency. In 2017, Wei et al. [16] proposed a scheme that can resist the exposure of signature keys and ensure forward security. However, all the above solutions are not resistant to quantum attacks. To resist quantum attacks, Xiang [12] proposed a lattice-based RIBS scheme in 2015, but its cancellation operation requires a secure channel. Subsequently, Wei et al. [16] introduced a RIBS scheme based on the NTRU lattice that the update key can be updated on the open channel. In the next few years, Xie et al. [13–15] proposed some RIBS schemes. These schemes all improve the security of the scheme in some cases. However, none of the above schemes can guarantee forward security. For now, there is no RIBS scheme on the lattice that can guarantee forward security and resist signature key exposure attacks.


## 1.2.2. Forward-Secure Signature Scheme

For forward security (FS), Anderson [19] firstly proposed the idea of forward-secure signature in 1997. Later, Bellare and Miner proposed a more efficient scheme [20] based on [19] and gave the formal definition and security model of forward security signature. More forward-secure digital signature algorithms [21, 22] have been proposed. However, there is little research on identity-based forward-secure digital signature algorithm. In 2008, Liu et al. introduced the first FS-IBS scheme in [23]. Zhang et al. [18] gave the first FS-IBS scheme in 2014. In 2021, Wu and Huang [24] further proposed an efficient forward security algorithm on the lattice, which has stronger security. But there is no revocable mechanism, it and cannot resist key exposure attacks. To the best of our knowledge, Wei et al. [16] first studied FS-RIBS and gave a construction. But, it is not resistant to quantum attacks. Qin et al. [17] proposed the general structure of revocable forward security for encryption in 2021. Its main idea combines a node selection algorithm and identity-based hierarchical encryption.


## 2. Preliminary

Notations. We use “U|V” to represent a concatenation of two elements U and V, which can be binary strings, matrices, etc. We use “t” to represent a time period in binary form. We denote sets with capital italic, e.g., U and V. Security parameter is λ. mpk means master public key, and msk means master secret key. The revocation list is represented by RL. A complete binary tree is represented by BT.


### 2.1. The Algorithm of Node Selection

In order to prevent the time complexity of revoking users from increasing linearly, our revocation scheme adopts a node selection algorithm. The core idea of the algorithm is to use a complete binary tree to find the fewest nodes required to cover all non-revoked users. In this tree, each leaf node has a one-to-one correspondence with an identity. The set of all nodes on the path from the root node of the userID to the leaf node is represented by Path (ID). xl and xr are used to represent the left and right child nodes of node x. This algorithm KUNBT,RL,t will input RL, a binary tree BT, and t time period. The algorithm has the following four steps:(1)
Let setsU and V be empty sets.(2)
∀IDi,ti∈RL, if ti≤t, add IDi to U.(3)
∀x∈U, if xl∉U, then addend xl to V; if xr∉U, then addend xr to V.(4)
IfRL∉∅, return V; else return the root node.Figures2 and 3 give a simple example of this algorithm, in which Figure 2 shows that no user has been revoked, and Figure 3 shows that the user with ID=3 has been revoked.Figure 2
No user is revoked:U=∅ and V=root.Figure 3
ID = 3 is revoked: U=root,x1,x4,x10 and =  V=x2,x3,x9.


### 2.2. Definition of (H)IBS

In this section, we introduce the formal definition of (H)IBS constructions. First, we give the definition of IBS, which can easily be extended to HIBS. There are 4 PPT algorithms in an IBS system:(i)
Setupλ,lid: on input λ and identity length lid, output mpk and msk.(ii)
Extract (mpk, msk, ID): on input (mpk, msk) and an arbitrary identity ID, it outputs the user’s secret key uskID, associated with ID.(iii)
SignM,ID,uskID: on input a message M∈ℳ, ID and uskID. A signature σ is returned.(iv)
Verifympk,M,ID,σ: on input mpk, M, ID, and σ, it returns 0 if σ is invalid and 1 otherwise.Essentially, the HIBS scheme only has one more feature than the IBS scheme, which is the feature of hierarchy, that is, the user of the parent node can deduce the key of the user of its child node, but the user of the leaf node cannot deduce the key of the parent node. However, there is no connection between the users of the IBS scheme. So, we just need to add aDerive algorithm to the IBS scheme. Let the maximum depth of our HIBS system be d; set a user ID=ID1,…,IDk, and the signature private key is uskID, where k≤d. The Derive algorithm inputs ID and uskID and obtains the key uskID|r of the following hierarchy where r is 0 or 1. Through iteration, the user ID can get keys of all users whose depth is up to d and prefixed with ID. When d=1, it is the IBS scheme.Next, we give the security model of the (H)IBS scheme. Strong unforgeability under adaptive chosen message attack (SU-CMA) is the required security for our HIBS and IBS schemes. We set the maximum hierarchy depth of our HIBS scheme to bed (IBS is the case of d=1). It formally defines the game between adversary A and challenger C.(1)
Setup:C gets (mpk, msk) by running Setupλ,lid,d and sends mpk to adversary A.(2)
Phase 1:A adaptively makes a polynomial number of the following queries:(i)
Create key: for any identity ID|1=ID1 at depth 1, the challenge runs uskID|1←Extract (mpk, msk, ID1). It adds ID|1,1,uskID|1 to a key list KL.(ii)
Secret key: A can query a secret key for an identity ID|k=ID1,…,IDk where k≤d. C first checks whether the key list has a secret key uskID|i for identity ID|i which is a prefix of identity ID|k. If so, C runs uskID|k←DeriveuskID|i,ID|k and returns to A the secret key uskID|k. If no such tuple, C returns ⊥. If i=k, C sends uskID|i to A.(iii)
Signature query:A can adaptively query C for polynomial signatures. The identity and message of these signatures are arbitrary. Here, suppose A queries q times, the message set is M1,…,Mq, and the identity set is ID1,…,IDq. Note that IDi where i=1,2,…,q refers to the i-th identity. C calculates the signature of these messages by Sign(Mi,IDi,uskIDi where i=1,2,…,q to form a set M1,σID1M1,…,Mq,σIDqMq and returns the set to A.(4)
Forgery: the adversary A forges a signature σID∗M∗ of M∗. A will succeed if the following three conditions hold:(1)
Verifympk,ID∗,M∗,σID∗M∗=1.(2)
ID∗ or its any prefix cannot be queried during the secret key query phase.(3)
M∗,σID∗M∗ cannot be queried during the signature query phase.The advantage ofA in the above game is defined as AdvHIBS,ASU−CMAλ=PrAsucceeds.Definition 1.
For any PPT adversaryA, if the above advantage of A is negligible in λ, then the (H)IBS is SU-CMA secure.
Multi-Identity Security. In the forgery stage, multiple identities can be submitted, and as long as one is successfully verified, the adversary is won. We assume there are n identities. By a hybrid argument, we can prove that the advantage of A to forge a signature successfully is no more than n⋅AdvHIBS,ASU−CMAλ.


## 2.1. The Algorithm of Node Selection

In order to prevent the time complexity of revoking users from increasing linearly, our revocation scheme adopts a node selection algorithm. The core idea of the algorithm is to use a complete binary tree to find the fewest nodes required to cover all non-revoked users. In this tree, each leaf node has a one-to-one correspondence with an identity. The set of all nodes on the path from the root node of the userID to the leaf node is represented by Path (ID). xl and xr are used to represent the left and right child nodes of node x. This algorithm KUNBT,RL,t will input RL, a binary tree BT, and t time period. The algorithm has the following four steps:(1)
Let setsU and V be empty sets.(2)
∀IDi,ti∈RL, if ti≤t, add IDi to U.(3)
∀x∈U, if xl∉U, then addend xl to V; if xr∉U, then addend xr to V.(4)
IfRL∉∅, return V; else return the root node.Figures2 and 3 give a simple example of this algorithm, in which Figure 2 shows that no user has been revoked, and Figure 3 shows that the user with ID=3 has been revoked.Figure 2
No user is revoked:U=∅ and V=root.Figure 3
ID = 3 is revoked: U=root,x1,x4,x10 and =  V=x2,x3,x9.


## 2.2. Definition of (H)IBS

In this section, we introduce the formal definition of (H)IBS constructions. First, we give the definition of IBS, which can easily be extended to HIBS. There are 4 PPT algorithms in an IBS system:(i)
Setupλ,lid: on input λ and identity length lid, output mpk and msk.(ii)
Extract (mpk, msk, ID): on input (mpk, msk) and an arbitrary identity ID, it outputs the user’s secret key uskID, associated with ID.(iii)
SignM,ID,uskID: on input a message M∈ℳ, ID and uskID. A signature σ is returned.(iv)
Verifympk,M,ID,σ: on input mpk, M, ID, and σ, it returns 0 if σ is invalid and 1 otherwise.Essentially, the HIBS scheme only has one more feature than the IBS scheme, which is the feature of hierarchy, that is, the user of the parent node can deduce the key of the user of its child node, but the user of the leaf node cannot deduce the key of the parent node. However, there is no connection between the users of the IBS scheme. So, we just need to add aDerive algorithm to the IBS scheme. Let the maximum depth of our HIBS system be d; set a user ID=ID1,…,IDk, and the signature private key is uskID, where k≤d. The Derive algorithm inputs ID and uskID and obtains the key uskID|r of the following hierarchy where r is 0 or 1. Through iteration, the user ID can get keys of all users whose depth is up to d and prefixed with ID. When d=1, it is the IBS scheme.Next, we give the security model of the (H)IBS scheme. Strong unforgeability under adaptive chosen message attack (SU-CMA) is the required security for our HIBS and IBS schemes. We set the maximum hierarchy depth of our HIBS scheme to bed (IBS is the case of d=1). It formally defines the game between adversary A and challenger C.(1)
Setup:C gets (mpk, msk) by running Setupλ,lid,d and sends mpk to adversary A.(2)
Phase 1:A adaptively makes a polynomial number of the following queries:(i)
Create key: for any identity ID|1=ID1 at depth 1, the challenge runs uskID|1←Extract (mpk, msk, ID1). It adds ID|1,1,uskID|1 to a key list KL.(ii)
Secret key: A can query a secret key for an identity ID|k=ID1,…,IDk where k≤d. C first checks whether the key list has a secret key uskID|i for identity ID|i which is a prefix of identity ID|k. If so, C runs uskID|k←DeriveuskID|i,ID|k and returns to A the secret key uskID|k. If no such tuple, C returns ⊥. If i=k, C sends uskID|i to A.(iii)
Signature query:A can adaptively query C for polynomial signatures. The identity and message of these signatures are arbitrary. Here, suppose A queries q times, the message set is M1,…,Mq, and the identity set is ID1,…,IDq. Note that IDi where i=1,2,…,q refers to the i-th identity. C calculates the signature of these messages by Sign(Mi,IDi,uskIDi where i=1,2,…,q to form a set M1,σID1M1,…,Mq,σIDqMq and returns the set to A.(4)
Forgery: the adversary A forges a signature σID∗M∗ of M∗. A will succeed if the following three conditions hold:(1)
Verifympk,ID∗,M∗,σID∗M∗=1.(2)
ID∗ or its any prefix cannot be queried during the secret key query phase.(3)
M∗,σID∗M∗ cannot be queried during the signature query phase.The advantage ofA in the above game is defined as AdvHIBS,ASU−CMAλ=PrAsucceeds.Definition 1.
For any PPT adversaryA, if the above advantage of A is negligible in λ, then the (H)IBS is SU-CMA secure.
Multi-Identity Security. In the forgery stage, multiple identities can be submitted, and as long as one is successfully verified, the adversary is won. We assume there are n identities. By a hybrid argument, we can prove that the advantage of A to forge a signature successfully is no more than n⋅AdvHIBS,ASU−CMAλ.


## 3. Definition of FS-RIBS Scheme

### 3.1. Syntax of FS-RIBS Scheme

A forward-secure revocable identity-based signature (FS-RIBS) is made up of the following 8 algorithms:(i)
(mpk, msk, ST, RL) ←Setup(λ,lid,ltime: λ is the security parameter of the algorithm, 0,1lid represents the user’s identity space, and the algorithm has 2ltime time periods. This algorithm inputs λ, lid, and ltime and outputs (mpk, msk) and two empty sets ST and RL.(ii)
skIDt1←KeyGen (mpk, msk, ID, ST): the algorithm generates a secret key for the newly added user ID∈0,1lid and then outputs a secret key skIDt1 that can be evolved in initial time period t1≐ 0 ltime 1.(iii)
skIDt←SKEvalmpk,skIDt−1,t: this algorithm outputs the secret key skIDt of the current time period t from the secret key skIDt−1 of the previous time period t-1 through evolution.(iv)
ukt←SKUpdate (mpk, msk, RL, ST, t): the algorithm outputs the update key ukt within time period t∈0,1ltime.(v)
SignkID,t←SKGenskIDt,ukt: in time period t, this algorithm inputs update key ukt and user ID secret key skIDt and returns a signing key SignkID,t within time period t.(vi)
σID,t←SignSignkID,t,t,ID,M: on input a message M∈ℳ, the algorithm signs it within the time period t, identity ID, and signing key SignkID,t and outputs a signature σID,t.(vii)
1/0←Verify (mpk, M, t, ID, σID,t): this algorithm verifies the signature σID,t and outputs 0 if σID,t is an invalid signature, and 1 otherwise.(viii)
RL←Revoke (RL, ID, t): suppose that the input identity ID is not a non-revoked user at time period t; then, (ID, t) is added to RL by key authority, and it outputs new RL.Correctness. An FS-RIBS needs to meet correctness as follows. For any message M and identity ID, if the user is not revoked at time period t, then for (mpk, msk, ST, RL)←Setupλ,lid,ltime, skIDt1←KeyGen (mpk, msk, ID, ST), skIDt←SKEvalmpk,skIDt−1,t, ukt←SKUpdate (mpk, msk, ST, RL,t), SignkID,t←SKGenskIDt,ukt, and σID,t←Sign(SignkID,t, ID, t, M), Verifympk,M,t,ID,σID,t=1 holds with overwhelming probability.


### 3.2. Attacker Model

We refer to [25–27] and give what capabilities the attacker is allowed to have in our scheme combined with the actual situation. Attackers are divided into two different types:(1)
T1 adversary is able to query skID∗t of ID∗ within time period t≤t∗. Thus, the user ID∗ must have been revoked before t∗ time period.(2)
T2 adversary does not do the above query. However, it is allowed to query a signing key within any t≠t∗ and can query the secret key of ID∗ after time period t∗.Both adversaries are allowed to obtain all public parameters of the system.


### 3.3. Security Definition of FS-RIBS Scheme

Next, we give a security definition of FS-RIBS, which is resistant to signing key exposure and can guarantee forward security. The FS-RIBS scheme is SU-CMA secure.Definition 2.
(SU-CMA). The SU-CMA security of FS-RIBS is defined by the following experiment played between a challengerC and a PPT adversary A.(1)
Setup:C gets mpk, msk, RL, and a state ST by running Setupλ,lid,ltime. mpk is sent by C to A. Then, AsendsCthat he wants to challengeID∗and challenge time periodt∗.(2)
Query phase:A is allowed to make adaptive polynomial queries to C as follows:(i)
Create key query: if A queries the identity ID∈0,1lid and creates key in time period t∈0,1ltime, firstly, C judges whether t is the initial time period of the ID. If C finds this to be the case, then it gets an initial secret key skIDt by running KeyGen (mpk, msk, ID, ST). Next, it adds triple (ID, t, skIDt) to the secret key list SKL. Otherwise, C queries in SKL whether there exists a triple (ID, skIDt′, t′) satisfying t′<t. If this is the case, it iteratively runs SKEval (mpk, skIDt′ , t′+1) until SKEval (mpk, skIDt−1, t), gets secret key skIDt in time period t, and updates the triple (ID, skIDt′, t′) with (ID, skIDt, t). If this is not the case, C returns ⊥ to A.(ii)
Secret key query: if A wants to query the secret key with ID∈0,1lid in t∈0,1ltime, C searches the SKL for triple (ID, t, skIDt). If it searched such triple, C sends skIDt to A; otherwise, it sends ⊥ to A.(iii)
Update key query: if A sends C a query for the update key at t time period, C gets ukt and sends it to A by running SKUpdate (mpk, msk, ST, RL,t).(iv)
Signing key query: if A does a signing key query for ID within the time period t, firstly, C searches the SKL for the triple (ID, t′, skIDt′) satisfying t≥t′. If it does not search such triple, Cresponds ⊥. On the contrary, C evolves skIDt′ from time period t′ to t by iterative running SKEval (mpk, skIDt′ , t′+1) until SKEval (mpk, skIDt−1 , t) and gets the signing key skIDt by running algorithm SKGen (skIDt, ukt). C returns skIDt to A.(v)
Revocation query:C returns RL to A if it receives A’s request to query the revocation list for time period t.(vi)
Signature query: A can adaptively query C for polynomial signatures. The identity, time period, and the message of these signatures are arbitrary. Here, suppose A queries q times; the message set is M1,…,Mq, the time period set is t1,…,tq, and the identity set is ID1,…,IDq. C calculates the signature of these messages by Sign (SignkIDi,ti,IDi,ti,Mi where i=1,2,…,q to form a set M1,σID1,t1M1,…,Mq,σID1,tqMq and returns the set to A.The above query has the following restrictions:(i)
A cannot query the signing key whose ID∗ is within time period t∗.(ii)
A can query the secret key of ID∗ in time period t<t∗, provided that ID∗ must be revoked before time period t∗.(iii)
If the identityIDi is not a non-revoked user within time period ti, return σIDi,tiM1  =  ⊥ to A.(3)
Forgery: the adversary A forged a signature σID∗,t∗M∗ of M∗. The adversary can win the game unless M∗,σID∗,t∗M∗∉M1,σID1,t1M1,…,Mq,σID1,tqMq and Verify(mpk, mpk,M∗,t∗,ID∗,σID∗,t∗M∗=1, ID∗,σID∗,t∗M∗) = 1.
In the above experiment, the probability ofA successfully forging a verified signature is defined as(1)AdvFS−RIBS,ASU−CMAλ.
For any PPT adversaryA, if AdvFS−RIBS,ASU−CMAλ is negligible in λ, then the FS-RIBS scheme is SU-CMA secure.


## 3.1. Syntax of FS-RIBS Scheme

A forward-secure revocable identity-based signature (FS-RIBS) is made up of the following 8 algorithms:(i)
(mpk, msk, ST, RL) ←Setup(λ,lid,ltime: λ is the security parameter of the algorithm, 0,1lid represents the user’s identity space, and the algorithm has 2ltime time periods. This algorithm inputs λ, lid, and ltime and outputs (mpk, msk) and two empty sets ST and RL.(ii)
skIDt1←KeyGen (mpk, msk, ID, ST): the algorithm generates a secret key for the newly added user ID∈0,1lid and then outputs a secret key skIDt1 that can be evolved in initial time period t1≐ 0 ltime 1.(iii)
skIDt←SKEvalmpk,skIDt−1,t: this algorithm outputs the secret key skIDt of the current time period t from the secret key skIDt−1 of the previous time period t-1 through evolution.(iv)
ukt←SKUpdate (mpk, msk, RL, ST, t): the algorithm outputs the update key ukt within time period t∈0,1ltime.(v)
SignkID,t←SKGenskIDt,ukt: in time period t, this algorithm inputs update key ukt and user ID secret key skIDt and returns a signing key SignkID,t within time period t.(vi)
σID,t←SignSignkID,t,t,ID,M: on input a message M∈ℳ, the algorithm signs it within the time period t, identity ID, and signing key SignkID,t and outputs a signature σID,t.(vii)
1/0←Verify (mpk, M, t, ID, σID,t): this algorithm verifies the signature σID,t and outputs 0 if σID,t is an invalid signature, and 1 otherwise.(viii)
RL←Revoke (RL, ID, t): suppose that the input identity ID is not a non-revoked user at time period t; then, (ID, t) is added to RL by key authority, and it outputs new RL.Correctness. An FS-RIBS needs to meet correctness as follows. For any message M and identity ID, if the user is not revoked at time period t, then for (mpk, msk, ST, RL)←Setupλ,lid,ltime, skIDt1←KeyGen (mpk, msk, ID, ST), skIDt←SKEvalmpk,skIDt−1,t, ukt←SKUpdate (mpk, msk, ST, RL,t), SignkID,t←SKGenskIDt,ukt, and σID,t←Sign(SignkID,t, ID, t, M), Verifympk,M,t,ID,σID,t=1 holds with overwhelming probability.


## 3.2. Attacker Model

We refer to [25–27] and give what capabilities the attacker is allowed to have in our scheme combined with the actual situation. Attackers are divided into two different types:(1)
T1 adversary is able to query skID∗t of ID∗ within time period t≤t∗. Thus, the user ID∗ must have been revoked before t∗ time period.(2)
T2 adversary does not do the above query. However, it is allowed to query a signing key within any t≠t∗ and can query the secret key of ID∗ after time period t∗.Both adversaries are allowed to obtain all public parameters of the system.


## 3.3. Security Definition of FS-RIBS Scheme

Next, we give a security definition of FS-RIBS, which is resistant to signing key exposure and can guarantee forward security. The FS-RIBS scheme is SU-CMA secure.Definition 2.
(SU-CMA). The SU-CMA security of FS-RIBS is defined by the following experiment played between a challengerC and a PPT adversary A.(1)
Setup:C gets mpk, msk, RL, and a state ST by running Setupλ,lid,ltime. mpk is sent by C to A. Then, AsendsCthat he wants to challengeID∗and challenge time periodt∗.(2)
Query phase:A is allowed to make adaptive polynomial queries to C as follows:(i)
Create key query: if A queries the identity ID∈0,1lid and creates key in time period t∈0,1ltime, firstly, C judges whether t is the initial time period of the ID. If C finds this to be the case, then it gets an initial secret key skIDt by running KeyGen (mpk, msk, ID, ST). Next, it adds triple (ID, t, skIDt) to the secret key list SKL. Otherwise, C queries in SKL whether there exists a triple (ID, skIDt′, t′) satisfying t′<t. If this is the case, it iteratively runs SKEval (mpk, skIDt′ , t′+1) until SKEval (mpk, skIDt−1, t), gets secret key skIDt in time period t, and updates the triple (ID, skIDt′, t′) with (ID, skIDt, t). If this is not the case, C returns ⊥ to A.(ii)
Secret key query: if A wants to query the secret key with ID∈0,1lid in t∈0,1ltime, C searches the SKL for triple (ID, t, skIDt). If it searched such triple, C sends skIDt to A; otherwise, it sends ⊥ to A.(iii)
Update key query: if A sends C a query for the update key at t time period, C gets ukt and sends it to A by running SKUpdate (mpk, msk, ST, RL,t).(iv)
Signing key query: if A does a signing key query for ID within the time period t, firstly, C searches the SKL for the triple (ID, t′, skIDt′) satisfying t≥t′. If it does not search such triple, Cresponds ⊥. On the contrary, C evolves skIDt′ from time period t′ to t by iterative running SKEval (mpk, skIDt′ , t′+1) until SKEval (mpk, skIDt−1 , t) and gets the signing key skIDt by running algorithm SKGen (skIDt, ukt). C returns skIDt to A.(v)
Revocation query:C returns RL to A if it receives A’s request to query the revocation list for time period t.(vi)
Signature query: A can adaptively query C for polynomial signatures. The identity, time period, and the message of these signatures are arbitrary. Here, suppose A queries q times; the message set is M1,…,Mq, the time period set is t1,…,tq, and the identity set is ID1,…,IDq. C calculates the signature of these messages by Sign (SignkIDi,ti,IDi,ti,Mi where i=1,2,…,q to form a set M1,σID1,t1M1,…,Mq,σID1,tqMq and returns the set to A.The above query has the following restrictions:(i)
A cannot query the signing key whose ID∗ is within time period t∗.(ii)
A can query the secret key of ID∗ in time period t<t∗, provided that ID∗ must be revoked before time period t∗.(iii)
If the identityIDi is not a non-revoked user within time period ti, return σIDi,tiM1  =  ⊥ to A.(3)
Forgery: the adversary A forged a signature σID∗,t∗M∗ of M∗. The adversary can win the game unless M∗,σID∗,t∗M∗∉M1,σID1,t1M1,…,Mq,σID1,tqMq and Verify(mpk, mpk,M∗,t∗,ID∗,σID∗,t∗M∗=1, ID∗,σID∗,t∗M∗) = 1.
In the above experiment, the probability ofA successfully forging a verified signature is defined as(1)AdvFS−RIBS,ASU−CMAλ.
For any PPT adversaryA, if AdvFS−RIBS,ASU−CMAλ is negligible in λ, then the FS-RIBS scheme is SU-CMA secure.


## 4. Our Generic Construction

The two fundamental schemes in our generic construction are HIBS and IBS. HIBS consists of five algorithms,HIBS.Setup, HIBS.Extract, HIBS.Derive, HIBS.Sign, and HIBS.Verify and its maximum depth is ltime+1. The IBS is composed of 4 algorithms: IBS.Setup, IBS.Extract, IBS.Sign, and IBS.Verify. We let the message spaces of our HIBS and IBS schemes be ℳ for both. As described in Construction 1, we construct a FS-RIBS scheme consisting of eight algorithms: RIBS.Setup, RIBS.KeyGen, RIBS.SKEval, RIBS.SKUpdate, RIBS.SKGen, RIBS.Sign, RIBS.Verify, and RIBS.Revoke. Obviously, the message space of this scheme is ℳ, 0,1lid is the identity space of this scheme, and 0,1ltime is the time period space of this scheme.In the construction, the signature key of each user is related to a discrete time period. Specifically, it is necessary to cascade a certain time periodT after each user ID, where t∈T=0,1,…,2ltime−1 is binary. In other words, when generating the signature key, the ID is concatenated with a certain time period T as the input identity, which will lead to each user ID having different signature keys in different time periods, which ensures its forward security. More specifically, a time period can be represented by the integer t=E1E2…Eltime∈0,1ltime of ltime-bit, arranged from the top of the tree to the bottom. For t∈T, a set of ltime+1 identities is represented by Jt=Jt,1,Jt,2,…,Jt,ltime+1 and Jt,c is treated as an identity vector. For, c=1⋯ltime+1:(2)Jt,c=E1,E2,…,Ec−1,1,ifEc=0and1≤c≤ltime,⊥,ifEc=1and1≤c≤ltime,E1,E2,…,Eltime,ifc=ltime+1.We give an example as shown in Figure4. In the figure, time t=0010 and T=24 time periods, and the set J2=1,01,⊥,0011,0010.Figure 4
t = 0010.


### 4.1. Basic Construction

Construction 1 (Forward-Secure RIBS Scheme). Our generic construction of FS-RIBS scheme is detailed as follows(i)
mpk,msk,ST,RL←RIBS.Setupλ,lid,ltime: it runs HIBS.Setupλ,ltime+1 and IBS.Setupλ,ltime+lid to obtain mpk1,msk1 and mpk2,msk2, respectively. It initializes BT, whose depth is lid. All leaf nodes are closely related to an identity. Ultimately, it outputs mpk=mpk1,mpk2, msk=msk1,msk2, an empty revocation list RL, and ST = BT.(ii)
skIDt1← textbfRIBS.KeyGen (mpk, msk, ID, ST): generate a secret key set for any user ID∈0,1lid, and the algorithm first calculates the set Jt=Jt1,1,Jt1,2,…,Jt1,ltime+1 for initial time period 0ltime 1. For c = 1, c=1,…,ltime, +1, if Jt1,c≠⊥, it runs HIBS.Extractmpk1,msk1,ID,|Jt1,c to get a secret key Kt1,c. If Jt1,c=⊥, it sets Kt1,c=⊥. Ultimately, this algorithm outputs the secret key skIDt1=1,Kt,1,…,Kt,ltime+1.(iii)
skIDt←SKEvalmpk,skIDt−1,t: for t∈0,1ltime, firstly, the algorithm calculates the two sets Jt−1 and Jt. For c2=1,…,ltime +1, if Jt,c2≠⊥, there must be an element c1 in the set 1,…,ltime+1 such that a prefix of (ID, Jt,c2) is (ID, Jt−1,c1). It then runs HIBS.Derivempk1,Kt−1,c1,ID,|Jt,c2 to gain the corresponding key Kt,c2. If Jt,c2=⊥, it sets Kt,c2=⊥. Ultimately, it returns skIDt=t,Kt,1,…,Kt,ltime+1.(iv)
ukt←SKUpdatempk,msk,ST,RL,t: for t∈0,1ltime, firstly, this algorithm runs node selection algorithm to get cover set KUN (BT,RL,t). Then, for ∀x∈KUNBT,RL,t, it runs IBS.Extractmpk2,msk2,t|vx to get the key Lx corresponding to identity t|vx. Ultimately, it outputs the update key set ukt=t,Lxx∈KUNBT,RL,t.(v)
SignkID,t←SKGenskIDt,ukt: suppose that a user’s ukt=t,Lxx∈KUNBT,RL,t and skIDt=t,Kt,1,…,Kt,ltime+1. Suppose that ID is a non-revoked user within time period t; there must exist a x∗∈KUNBT,RL,t∩PathID. It outputs ID’s signature key SignkIDt=Kt,ltime+1,Lx∗.(vi)
σID,t←SignSignkID,t,ID,t,M: for a message M∈ℳ, suppose that ID is a non-revoked user within t time period; the signer has a valid signing key skIDt=Kt,ltime+1,Lx∗. Then, it computes σ1←HIBS.SignKt,ltime+1,ID|Jt,ltime+1,M, and σ2←IBS.SignLx∗,t|vx∗,M. Finally, the algorithm returns a signature σID,t=σ1,σ2.(vii)
1/0←Verifympk,M,t,ID,σID,t: for a signature σID,t=σ1,σ2, the algorithm computes V1←HIBS.Verifympk1,M,ID|Jt,ltime+1,σ1 and V2,x←IBS.Verifympk2,M,t|vx,σ2 for each node x∈PathID. Note that V2,xx∈PathID is a set. If there is a V2∈V2,x such that V1×V2=1, the algorithm outputs 1, and 0 otherwise.(viii)
RL←Revoke (RL, ID, t): suppose that the input identity ID is not a non-revoked user at time period t; then (ID, t) is added to RL by key authority and outputs new RL.Correctness. The correctness of Con.1 (Construction 1) is determined by the correctness of the fundamental HIBS and IBS schemes. Suppose that identity ID is a non-revoked user within time period t; in the IBS scheme, the signing key corresponding to t|vx∗ is Lx∗, and Kt,ltime+1 is the signing key corresponding to ID|Jt,ltime+1 in the HIBS scheme. The two signature algorithms IBS.Sign and HIBS.Sign can correctly sign the message M. We can correctly get σID,t by HIBS.SignKt,ltime+1,M and IBS.SignL_x∗,t|vx∗,M. Then, compute V1←HIBS.Verifympk1,M,t,ID|Jt,ltime+1,σ1 and V2,x←IBS.Verifympk2,M,t|vx,σ2 for each node x∈PathID. There always exists a V2∈V2,x such that V1×V2 = 1 holds.Security. The SU-CMA security of Con.1 is determined by the SU-CMA security of the fundamental HIBS scheme and IBS scheme. Especially, it is ensured by Theorem 1.Theorem 1.
If the fundamental HIBS and IBS schemes are SU-CMA secure, the FS-RIBS scheme in Con.1 is SU-CMA secure.Outline of Proof. Firstly, we emphasize the core idea of security proof and then introduce a strict proof of security reduction. For this proof, adversaries are classified into two types as described in Section 3.2. T2 adversary is designed to break Con.1’s forward security. For T1 adversary, we need to build an emulator to store the master secret key of the fundamental HIBS and reduce the SU-CMA security of the FS-RIBS scheme to the SU-CMA security of the fundamental IBS scheme. For T2 adversary, the emulator holds the master secret key of the fundamental IBS scheme and reduces the SU-CMA security of the FS-RIBS scheme to the SU-CMA security of fundamental HIBS scheme.Proof.
Let adversaryA break the SU-CMA security of the FS-RIBS scheme; then, we build a PPT emulator E to break the SU-CMA security of the fundamental IBS scheme or HIBS scheme. The emulator works in two steps: firstly, it randomly gets a bit b. Secondly, if b=0, A is regarded as E a T1 adversary, else a T2 adversary. So, the probability of E correctly or incorrectly guessing the adversary’s type is 1/2.(i)
ForT1 adversary, E is given mpk2 of the fundamental IBS scheme. It emulates the process as follows:(1)
Setup: it produces the master key pair mpk1,msk1 of the fundamental HIBS scheme. E initializes RL and BT. It sends mpk1 and mpk2 to A. Then, A sends a challenge identity ID∗ and a challenge time period t∗ to E.(2)
Phase 1: since E gets the msk1 of HIBS scheme, it can respond to A’s secret key query and create key query for any time period t and any ID. If A needs an update key query within time period t, E first calculates the set KUN (BT,ST, t). Then, it sends the set of identities t|vxx∈KUNBT,ST,t to the challenger of the fundamental IBS scheme to get the corresponding update keys Lxx∈KUNBT,ST,t. Ultimately, E sends Lxx∈KUNBT,ST,t to A. E can get corresponding update keys from its challenger, so E can respond to A’s signing queries.(3)
Signature query phase:A can adaptively query E for polynomial signatures. The identity, time period, and message of these signatures are arbitrary. Here, suppose A queries q times, the message set is M1,…,Mq, and the time period set is t1,…,tq. For i=1,2,…,q, it calculates σIDi,ti1,Mi←HIBS.SignKti,ltime+1,Mi and σIDi,ti2,Mi←IBS.SignLx∗,Mi if IDi is a non-revoked user within time period ti, respectively. Finally, it returns σIDi,tiMi=σIDi,ti1,Mi,σIDi,ti2,Mi to A.(4)
Forgery: let us assume that A successfully constructs a signature σID∗,t∗M∗=σID∗,t∗1,M∗,σID∗,t∗2,M∗, and this signature M∗,σID∗,t∗M∗∉M1,σID1,t1M1,…,Mq,σIDq,tqMq. Now, we calculate the probability of success of A. First, we calculate V1∗←HIBS.Verifympk1,M∗,t∗,ID∗|Jt∗,ltime+1,σID∗,t∗1,M∗ and V2,x∗←IBS.Verifympk2,M∗,t∗|vx,σID∗,t∗2,M∗ for ∀x∈PathID∗. Then, in the above emulated experiment, since ID∗ has been revoked before the challenge t∗ time period, for any (even the challenge) time period t, the sets of identities t∗|vxx∈PathID∗∩t|vxx∈KUNBT,ST,t=∅. Therefore, the challenge identities that E transmits to its own challenger are indeed valid. Naturally, if M∗,σID∗,t∗M∗ is a valid FS-RIBS signature, there must exist one x∗∈PathID∗, so that 1←IBS.Verifympk2,M∗,t∗|vx∗,σID∗,t∗2,M∗. That is, M∗,σID∗,t∗2,M∗ is a valid IBS signature under identity t∗|vx∗. Thus, E has the same success probability of breaking the SU-CMA security of the fundamental IBS scheme. Therefore, we have(3)AdvFS−RIBS,ASU−CMAλ≤AdvIBS,A1SU−CMAλ,whereA1 is any PPT adversary who can break the SU-CMA security of the fundamental IBS scheme.(ii)
Next, forT2 adversary, we introduce a PPT algorithm E to emulate the experiment and reduce the SU-CMA security of our FS-RIBS scheme to the SU-CMA security of the fundamental HIBS scheme. E is the master public key of the HIBS scheme and gets the master key pair mpk2,msk2 of IBS by itself.
E can respond to A’s queries about creating keys and secret keys. Obviously, A may query the secret key within t∗. E can answer the update key queries using msk2 of the fundamental IBS scheme. The signature query is the same as the signature query of T-1. Let us assume that A successfully constructs a signature σID∗,t∗M∗=σID∗,t∗1,M∗,σID∗,t∗2,M∗. Because the ID∗ is a non-revoked user in the time period t∗, its σID∗,t∗2,M∗ is necessary to pass the verification. Then, because A can only query for the signing key Kt,ltime+1t≠t∗, A successfully forges σID∗,t∗1,M∗ which is equivalent to breaking the SU-CMA security of the fundamental HIBS scheme. Thus, for Type-2 adversary, we will have(4)AdvFS−RIBS,ASU−CMAλ≤AdvHIBS,A2SU−CMAλ,where A2 is any PPT adversary who can attack the SU-CMA security of the fundamental IBS scheme.
Considering the above two cases comprehensively, we can get the following inequality:(5)AdvFS−RIBS,ASU−CMAλ≤12AdvIBS,A1SU−CMAλ+12AdvHIBS,A2SU−CMAλ.


### 4.2. Improvement

In Con.1, to determine the validity of the second part signatureσ2, Con.1 requires computing IBS verification algorithm lid times for each identity t|vx, where x∈PathID. Next, we introduce two simple methods to solve this problem.


#### 4.2.1. The First Method

The difference from Con.1 is that the second component of IBS scheme is replaced with a HIBS scheme. That is, the HIBS scheme will be used to get the update keys of the FS-RIBS scheme. Additionally, the value of each selected node in the node section algorithm is regarded as the identity vector of the fundamental HIBS scheme. For example, suppose thatvx12 = 101 as in Figures 2 and 3. Therefore, for t∈0,1ltime, the identity vector t,1,0,1 is used to represent t|vx12. The details of this improved FS-RIBS scheme are given in Construction 2.Construction 2 (Forward-Secure RIBS Scheme). The construction is described as follows.(i)
(mpk, msk, ST, RL) ←RIBS.Setupλ,lid,ltime: it getsmpk1,msk1by runningHIBS.Setupλ,ltime+1andmpk2,msk2 by running HIBS.Setupλ,lid+1. A complete binary tree of depthlidis initialized by the algorithm. Each leaf node corresponds to an identity. Ultimately, it returnsmpk=mpk1,mpk2, msk=msk1,msk2, ST = BT, andRL.(ii)
skIDt1←RIBS.KeyGen(mpk, msk, ID, ST): this algorithm is the same as in Construction 1.(iii)
skIDt←SKEvalmpk,skIDt−1,t: this algorithm is the same as in Construction 1.(iv)
ukt←SKUpdatempk,msk,ST,RL,t: for t∈0,1ltime, firstly, it calculates the cover setKUN(BT, RL, t). Then,∀x∈KUNBT,RL,t, it runsHIBS.Extractmpk2,msk2,t|vxto get the keyLxcorresponding to the hierarchical identityt|vx. Ultimately, it returns the update keyukt=t,Lxx∈KUNBT,RL,t.(v)
SignkID,t←SKGenskIDt,ukt: suppose that a user’s current secret key isskIDt=t,Kt,1,…,Kt,ltime+1and current update key isukt=t,Lxx∈KUNBT,RL,t. Suppose thatIDis a non-revoked user at time periodt; there must be a node such thatx∗∈KUNBT,RL,t∩PathID. Therefore, a prefix oft|vIDmust bet|vx∗. Firstly, The algorithm runsHIBS.Extractmpk2,Lx∗,t|vIDto get the corresponding keyLID. It returns the corresponding signing keySignkIDt=Kt,ltime+1,LID.(vi)
σID,t←SignSignkID,t,ID,t,M: if the identityIDis a non-revoked user withinttime period,SignkIDt=Kt,ltime+1,LID. Then, it computesσ1←HIBS.SignKt,ltime+1,ID|Jt,ltime+1,M, andσ2←IBS.SignLID,t|vID,M. Finally, the algorithm returns a signatureσID,t=σ1,σ2.(vii)
1/0←Verifympk,M,t,ID,σID,t: for a signatureσID,t=σ1,σ2, the algorithm computesV1←HIBS.Verifympk1,M,ID|Jt,ltime+1,σ1andV2,x←HIBS.Verifympk2,M,t|vID,σ2. IfV1×V2=1, the algorithm outputs 1, and 0 otherwise.(viii)
RL←RevokeRL,ID,t: suppose that the input identityIDis not a non-revoked user at time periodt; then, (ID, t) is added toRLby key authority and outputs newRL.Correctness. Similar to the first generic construction, the correctness of Construction 2 (Con.2) is based on the correctness of two basic HIBS schemes. The difference from Con.1 is that Lx∗ is the signing key corresponding to identity vector t|vx∗ in the second HIBS scheme, and the actual signature key LID is extracted from Lx∗ as t|vx is a prefix identity vector of t|vID. Therefore, the two verify algorithms of HIBS schemes can verify σ1 and σ2, respectively.Security. The SU-CMA security of Con.2 is determined by the SU-CMA security of the fundamental HIBS schemes. Then, we have Theorem 2.Theorem 2.
If the fundamental HIBS schemes are SU-CMA secure, then the FS-RIBS scheme in Con.2 is SU-CMA secure.The proof of Theorem2 is basically the same as Theorem 1. The only difference is that ukt is obtained by a HIBS scheme. We omit its proof.


#### 4.2.2. The Second Method

Observe that, in Con.1, as the verifier does not know the target nodex∗ used by the signer to generate the second part signature σ2, he must run the IBS verification algorithm lid times for each node x∈PathID. So, to solve this issue, the signer can indicate the target node x∗ in the signature. The second improved FS-RIBS scheme (referred to as Construction 3) is identical to that of Con.1, except for the following differences in algorithms Sign and Verify.(i)
The modified signing algorithmSignSignkID,t,ID,t,M: for a message M∈ℳ, if ID is a non-revoked user within time period t, the signer should have a valid signing key skIDt=Kt,ltime+1,Lx∗. Then, it sets M′=M|vx∗ and computes σ1←HIBS.SignKt,ltime+1,ID|Jt,ltime+1,M′, and σ2←IBS.SignLx∗,t|vx∗,M′. Finally, the algorithm returns a signature σID,t=σ1,σ2,x∗.(ii)
The modified verification algorithmVerifympk,M,t,ID,σID,t: for a signature σID,t=σ1,σ2,x∗, firstly, the algorithm judges whether x∗∈PathID. If this is not the case, it outputs ⊥; otherwise, it sets M′=M|vx∗ and computes V1←HIBS.Verifympk1,M′,ID|Jt,ltime+1,σ1 and V2←IBS.Verifympk2,M′,t|vx∗,σ2. If V1×V2=1, the algorithm outputs 1, and 0 otherwise.In Con.1, if we change the messageM to M′=M|vx∗, where x∗ is the corresponding node x∗ in the signing key Lx∗, this is just the above improved Construction 3 (Con.3). So, the correctness and security of Con.3 can be proved similarly as in Con.1. We omit the details.


## 4.1. Basic Construction

Construction 1 (Forward-Secure RIBS Scheme). Our generic construction of FS-RIBS scheme is detailed as follows(i)
mpk,msk,ST,RL←RIBS.Setupλ,lid,ltime: it runs HIBS.Setupλ,ltime+1 and IBS.Setupλ,ltime+lid to obtain mpk1,msk1 and mpk2,msk2, respectively. It initializes BT, whose depth is lid. All leaf nodes are closely related to an identity. Ultimately, it outputs mpk=mpk1,mpk2, msk=msk1,msk2, an empty revocation list RL, and ST = BT.(ii)
skIDt1← textbfRIBS.KeyGen (mpk, msk, ID, ST): generate a secret key set for any user ID∈0,1lid, and the algorithm first calculates the set Jt=Jt1,1,Jt1,2,…,Jt1,ltime+1 for initial time period 0ltime 1. For c = 1, c=1,…,ltime, +1, if Jt1,c≠⊥, it runs HIBS.Extractmpk1,msk1,ID,|Jt1,c to get a secret key Kt1,c. If Jt1,c=⊥, it sets Kt1,c=⊥. Ultimately, this algorithm outputs the secret key skIDt1=1,Kt,1,…,Kt,ltime+1.(iii)
skIDt←SKEvalmpk,skIDt−1,t: for t∈0,1ltime, firstly, the algorithm calculates the two sets Jt−1 and Jt. For c2=1,…,ltime +1, if Jt,c2≠⊥, there must be an element c1 in the set 1,…,ltime+1 such that a prefix of (ID, Jt,c2) is (ID, Jt−1,c1). It then runs HIBS.Derivempk1,Kt−1,c1,ID,|Jt,c2 to gain the corresponding key Kt,c2. If Jt,c2=⊥, it sets Kt,c2=⊥. Ultimately, it returns skIDt=t,Kt,1,…,Kt,ltime+1.(iv)
ukt←SKUpdatempk,msk,ST,RL,t: for t∈0,1ltime, firstly, this algorithm runs node selection algorithm to get cover set KUN (BT,RL,t). Then, for ∀x∈KUNBT,RL,t, it runs IBS.Extractmpk2,msk2,t|vx to get the key Lx corresponding to identity t|vx. Ultimately, it outputs the update key set ukt=t,Lxx∈KUNBT,RL,t.(v)
SignkID,t←SKGenskIDt,ukt: suppose that a user’s ukt=t,Lxx∈KUNBT,RL,t and skIDt=t,Kt,1,…,Kt,ltime+1. Suppose that ID is a non-revoked user within time period t; there must exist a x∗∈KUNBT,RL,t∩PathID. It outputs ID’s signature key SignkIDt=Kt,ltime+1,Lx∗.(vi)
σID,t←SignSignkID,t,ID,t,M: for a message M∈ℳ, suppose that ID is a non-revoked user within t time period; the signer has a valid signing key skIDt=Kt,ltime+1,Lx∗. Then, it computes σ1←HIBS.SignKt,ltime+1,ID|Jt,ltime+1,M, and σ2←IBS.SignLx∗,t|vx∗,M. Finally, the algorithm returns a signature σID,t=σ1,σ2.(vii)
1/0←Verifympk,M,t,ID,σID,t: for a signature σID,t=σ1,σ2, the algorithm computes V1←HIBS.Verifympk1,M,ID|Jt,ltime+1,σ1 and V2,x←IBS.Verifympk2,M,t|vx,σ2 for each node x∈PathID. Note that V2,xx∈PathID is a set. If there is a V2∈V2,x such that V1×V2=1, the algorithm outputs 1, and 0 otherwise.(viii)
RL←Revoke (RL, ID, t): suppose that the input identity ID is not a non-revoked user at time period t; then (ID, t) is added to RL by key authority and outputs new RL.Correctness. The correctness of Con.1 (Construction 1) is determined by the correctness of the fundamental HIBS and IBS schemes. Suppose that identity ID is a non-revoked user within time period t; in the IBS scheme, the signing key corresponding to t|vx∗ is Lx∗, and Kt,ltime+1 is the signing key corresponding to ID|Jt,ltime+1 in the HIBS scheme. The two signature algorithms IBS.Sign and HIBS.Sign can correctly sign the message M. We can correctly get σID,t by HIBS.SignKt,ltime+1,M and IBS.SignL_x∗,t|vx∗,M. Then, compute V1←HIBS.Verifympk1,M,t,ID|Jt,ltime+1,σ1 and V2,x←IBS.Verifympk2,M,t|vx,σ2 for each node x∈PathID. There always exists a V2∈V2,x such that V1×V2 = 1 holds.Security. The SU-CMA security of Con.1 is determined by the SU-CMA security of the fundamental HIBS scheme and IBS scheme. Especially, it is ensured by Theorem 1.Theorem 1.
If the fundamental HIBS and IBS schemes are SU-CMA secure, the FS-RIBS scheme in Con.1 is SU-CMA secure.Outline of Proof. Firstly, we emphasize the core idea of security proof and then introduce a strict proof of security reduction. For this proof, adversaries are classified into two types as described in Section 3.2. T2 adversary is designed to break Con.1’s forward security. For T1 adversary, we need to build an emulator to store the master secret key of the fundamental HIBS and reduce the SU-CMA security of the FS-RIBS scheme to the SU-CMA security of the fundamental IBS scheme. For T2 adversary, the emulator holds the master secret key of the fundamental IBS scheme and reduces the SU-CMA security of the FS-RIBS scheme to the SU-CMA security of fundamental HIBS scheme.Proof.
Let adversaryA break the SU-CMA security of the FS-RIBS scheme; then, we build a PPT emulator E to break the SU-CMA security of the fundamental IBS scheme or HIBS scheme. The emulator works in two steps: firstly, it randomly gets a bit b. Secondly, if b=0, A is regarded as E a T1 adversary, else a T2 adversary. So, the probability of E correctly or incorrectly guessing the adversary’s type is 1/2.(i)
ForT1 adversary, E is given mpk2 of the fundamental IBS scheme. It emulates the process as follows:(1)
Setup: it produces the master key pair mpk1,msk1 of the fundamental HIBS scheme. E initializes RL and BT. It sends mpk1 and mpk2 to A. Then, A sends a challenge identity ID∗ and a challenge time period t∗ to E.(2)
Phase 1: since E gets the msk1 of HIBS scheme, it can respond to A’s secret key query and create key query for any time period t and any ID. If A needs an update key query within time period t, E first calculates the set KUN (BT,ST, t). Then, it sends the set of identities t|vxx∈KUNBT,ST,t to the challenger of the fundamental IBS scheme to get the corresponding update keys Lxx∈KUNBT,ST,t. Ultimately, E sends Lxx∈KUNBT,ST,t to A. E can get corresponding update keys from its challenger, so E can respond to A’s signing queries.(3)
Signature query phase:A can adaptively query E for polynomial signatures. The identity, time period, and message of these signatures are arbitrary. Here, suppose A queries q times, the message set is M1,…,Mq, and the time period set is t1,…,tq. For i=1,2,…,q, it calculates σIDi,ti1,Mi←HIBS.SignKti,ltime+1,Mi and σIDi,ti2,Mi←IBS.SignLx∗,Mi if IDi is a non-revoked user within time period ti, respectively. Finally, it returns σIDi,tiMi=σIDi,ti1,Mi,σIDi,ti2,Mi to A.(4)
Forgery: let us assume that A successfully constructs a signature σID∗,t∗M∗=σID∗,t∗1,M∗,σID∗,t∗2,M∗, and this signature M∗,σID∗,t∗M∗∉M1,σID1,t1M1,…,Mq,σIDq,tqMq. Now, we calculate the probability of success of A. First, we calculate V1∗←HIBS.Verifympk1,M∗,t∗,ID∗|Jt∗,ltime+1,σID∗,t∗1,M∗ and V2,x∗←IBS.Verifympk2,M∗,t∗|vx,σID∗,t∗2,M∗ for ∀x∈PathID∗. Then, in the above emulated experiment, since ID∗ has been revoked before the challenge t∗ time period, for any (even the challenge) time period t, the sets of identities t∗|vxx∈PathID∗∩t|vxx∈KUNBT,ST,t=∅. Therefore, the challenge identities that E transmits to its own challenger are indeed valid. Naturally, if M∗,σID∗,t∗M∗ is a valid FS-RIBS signature, there must exist one x∗∈PathID∗, so that 1←IBS.Verifympk2,M∗,t∗|vx∗,σID∗,t∗2,M∗. That is, M∗,σID∗,t∗2,M∗ is a valid IBS signature under identity t∗|vx∗. Thus, E has the same success probability of breaking the SU-CMA security of the fundamental IBS scheme. Therefore, we have(3)AdvFS−RIBS,ASU−CMAλ≤AdvIBS,A1SU−CMAλ,whereA1 is any PPT adversary who can break the SU-CMA security of the fundamental IBS scheme.(ii)
Next, forT2 adversary, we introduce a PPT algorithm E to emulate the experiment and reduce the SU-CMA security of our FS-RIBS scheme to the SU-CMA security of the fundamental HIBS scheme. E is the master public key of the HIBS scheme and gets the master key pair mpk2,msk2 of IBS by itself.
E can respond to A’s queries about creating keys and secret keys. Obviously, A may query the secret key within t∗. E can answer the update key queries using msk2 of the fundamental IBS scheme. The signature query is the same as the signature query of T-1. Let us assume that A successfully constructs a signature σID∗,t∗M∗=σID∗,t∗1,M∗,σID∗,t∗2,M∗. Because the ID∗ is a non-revoked user in the time period t∗, its σID∗,t∗2,M∗ is necessary to pass the verification. Then, because A can only query for the signing key Kt,ltime+1t≠t∗, A successfully forges σID∗,t∗1,M∗ which is equivalent to breaking the SU-CMA security of the fundamental HIBS scheme. Thus, for Type-2 adversary, we will have(4)AdvFS−RIBS,ASU−CMAλ≤AdvHIBS,A2SU−CMAλ,where A2 is any PPT adversary who can attack the SU-CMA security of the fundamental IBS scheme.
Considering the above two cases comprehensively, we can get the following inequality:(5)AdvFS−RIBS,ASU−CMAλ≤12AdvIBS,A1SU−CMAλ+12AdvHIBS,A2SU−CMAλ.


## 4.2. Improvement

In Con.1, to determine the validity of the second part signatureσ2, Con.1 requires computing IBS verification algorithm lid times for each identity t|vx, where x∈PathID. Next, we introduce two simple methods to solve this problem.


### 4.2.1. The First Method

The difference from Con.1 is that the second component of IBS scheme is replaced with a HIBS scheme. That is, the HIBS scheme will be used to get the update keys of the FS-RIBS scheme. Additionally, the value of each selected node in the node section algorithm is regarded as the identity vector of the fundamental HIBS scheme. For example, suppose thatvx12 = 101 as in Figures 2 and 3. Therefore, for t∈0,1ltime, the identity vector t,1,0,1 is used to represent t|vx12. The details of this improved FS-RIBS scheme are given in Construction 2.Construction 2 (Forward-Secure RIBS Scheme). The construction is described as follows.(i)
(mpk, msk, ST, RL) ←RIBS.Setupλ,lid,ltime: it getsmpk1,msk1by runningHIBS.Setupλ,ltime+1andmpk2,msk2 by running HIBS.Setupλ,lid+1. A complete binary tree of depthlidis initialized by the algorithm. Each leaf node corresponds to an identity. Ultimately, it returnsmpk=mpk1,mpk2, msk=msk1,msk2, ST = BT, andRL.(ii)
skIDt1←RIBS.KeyGen(mpk, msk, ID, ST): this algorithm is the same as in Construction 1.(iii)
skIDt←SKEvalmpk,skIDt−1,t: this algorithm is the same as in Construction 1.(iv)
ukt←SKUpdatempk,msk,ST,RL,t: for t∈0,1ltime, firstly, it calculates the cover setKUN(BT, RL, t). Then,∀x∈KUNBT,RL,t, it runsHIBS.Extractmpk2,msk2,t|vxto get the keyLxcorresponding to the hierarchical identityt|vx. Ultimately, it returns the update keyukt=t,Lxx∈KUNBT,RL,t.(v)
SignkID,t←SKGenskIDt,ukt: suppose that a user’s current secret key isskIDt=t,Kt,1,…,Kt,ltime+1and current update key isukt=t,Lxx∈KUNBT,RL,t. Suppose thatIDis a non-revoked user at time periodt; there must be a node such thatx∗∈KUNBT,RL,t∩PathID. Therefore, a prefix oft|vIDmust bet|vx∗. Firstly, The algorithm runsHIBS.Extractmpk2,Lx∗,t|vIDto get the corresponding keyLID. It returns the corresponding signing keySignkIDt=Kt,ltime+1,LID.(vi)
σID,t←SignSignkID,t,ID,t,M: if the identityIDis a non-revoked user withinttime period,SignkIDt=Kt,ltime+1,LID. Then, it computesσ1←HIBS.SignKt,ltime+1,ID|Jt,ltime+1,M, andσ2←IBS.SignLID,t|vID,M. Finally, the algorithm returns a signatureσID,t=σ1,σ2.(vii)
1/0←Verifympk,M,t,ID,σID,t: for a signatureσID,t=σ1,σ2, the algorithm computesV1←HIBS.Verifympk1,M,ID|Jt,ltime+1,σ1andV2,x←HIBS.Verifympk2,M,t|vID,σ2. IfV1×V2=1, the algorithm outputs 1, and 0 otherwise.(viii)
RL←RevokeRL,ID,t: suppose that the input identityIDis not a non-revoked user at time periodt; then, (ID, t) is added toRLby key authority and outputs newRL.Correctness. Similar to the first generic construction, the correctness of Construction 2 (Con.2) is based on the correctness of two basic HIBS schemes. The difference from Con.1 is that Lx∗ is the signing key corresponding to identity vector t|vx∗ in the second HIBS scheme, and the actual signature key LID is extracted from Lx∗ as t|vx is a prefix identity vector of t|vID. Therefore, the two verify algorithms of HIBS schemes can verify σ1 and σ2, respectively.Security. The SU-CMA security of Con.2 is determined by the SU-CMA security of the fundamental HIBS schemes. Then, we have Theorem 2.Theorem 2.
If the fundamental HIBS schemes are SU-CMA secure, then the FS-RIBS scheme in Con.2 is SU-CMA secure.The proof of Theorem2 is basically the same as Theorem 1. The only difference is that ukt is obtained by a HIBS scheme. We omit its proof.


### 4.2.2. The Second Method

Observe that, in Con.1, as the verifier does not know the target nodex∗ used by the signer to generate the second part signature σ2, he must run the IBS verification algorithm lid times for each node x∈PathID. So, to solve this issue, the signer can indicate the target node x∗ in the signature. The second improved FS-RIBS scheme (referred to as Construction 3) is identical to that of Con.1, except for the following differences in algorithms Sign and Verify.(i)
The modified signing algorithmSignSignkID,t,ID,t,M: for a message M∈ℳ, if ID is a non-revoked user within time period t, the signer should have a valid signing key skIDt=Kt,ltime+1,Lx∗. Then, it sets M′=M|vx∗ and computes σ1←HIBS.SignKt,ltime+1,ID|Jt,ltime+1,M′, and σ2←IBS.SignLx∗,t|vx∗,M′. Finally, the algorithm returns a signature σID,t=σ1,σ2,x∗.(ii)
The modified verification algorithmVerifympk,M,t,ID,σID,t: for a signature σID,t=σ1,σ2,x∗, firstly, the algorithm judges whether x∗∈PathID. If this is not the case, it outputs ⊥; otherwise, it sets M′=M|vx∗ and computes V1←HIBS.Verifympk1,M′,ID|Jt,ltime+1,σ1 and V2←IBS.Verifympk2,M′,t|vx∗,σ2. If V1×V2=1, the algorithm outputs 1, and 0 otherwise.In Con.1, if we change the messageM to M′=M|vx∗, where x∗ is the corresponding node x∗ in the signing key Lx∗, this is just the above improved Construction 3 (Con.3). So, the correctness and security of Con.3 can be proved similarly as in Con.1. We omit the details.


## 4.2.1. The First Method

The difference from Con.1 is that the second component of IBS scheme is replaced with a HIBS scheme. That is, the HIBS scheme will be used to get the update keys of the FS-RIBS scheme. Additionally, the value of each selected node in the node section algorithm is regarded as the identity vector of the fundamental HIBS scheme. For example, suppose thatvx12 = 101 as in Figures 2 and 3. Therefore, for t∈0,1ltime, the identity vector t,1,0,1 is used to represent t|vx12. The details of this improved FS-RIBS scheme are given in Construction 2.Construction 2 (Forward-Secure RIBS Scheme). The construction is described as follows.(i)
(mpk, msk, ST, RL) ←RIBS.Setupλ,lid,ltime: it getsmpk1,msk1by runningHIBS.Setupλ,ltime+1andmpk2,msk2 by running HIBS.Setupλ,lid+1. A complete binary tree of depthlidis initialized by the algorithm. Each leaf node corresponds to an identity. Ultimately, it returnsmpk=mpk1,mpk2, msk=msk1,msk2, ST = BT, andRL.(ii)
skIDt1←RIBS.KeyGen(mpk, msk, ID, ST): this algorithm is the same as in Construction 1.(iii)
skIDt←SKEvalmpk,skIDt−1,t: this algorithm is the same as in Construction 1.(iv)
ukt←SKUpdatempk,msk,ST,RL,t: for t∈0,1ltime, firstly, it calculates the cover setKUN(BT, RL, t). Then,∀x∈KUNBT,RL,t, it runsHIBS.Extractmpk2,msk2,t|vxto get the keyLxcorresponding to the hierarchical identityt|vx. Ultimately, it returns the update keyukt=t,Lxx∈KUNBT,RL,t.(v)
SignkID,t←SKGenskIDt,ukt: suppose that a user’s current secret key isskIDt=t,Kt,1,…,Kt,ltime+1and current update key isukt=t,Lxx∈KUNBT,RL,t. Suppose thatIDis a non-revoked user at time periodt; there must be a node such thatx∗∈KUNBT,RL,t∩PathID. Therefore, a prefix oft|vIDmust bet|vx∗. Firstly, The algorithm runsHIBS.Extractmpk2,Lx∗,t|vIDto get the corresponding keyLID. It returns the corresponding signing keySignkIDt=Kt,ltime+1,LID.(vi)
σID,t←SignSignkID,t,ID,t,M: if the identityIDis a non-revoked user withinttime period,SignkIDt=Kt,ltime+1,LID. Then, it computesσ1←HIBS.SignKt,ltime+1,ID|Jt,ltime+1,M, andσ2←IBS.SignLID,t|vID,M. Finally, the algorithm returns a signatureσID,t=σ1,σ2.(vii)
1/0←Verifympk,M,t,ID,σID,t: for a signatureσID,t=σ1,σ2, the algorithm computesV1←HIBS.Verifympk1,M,ID|Jt,ltime+1,σ1andV2,x←HIBS.Verifympk2,M,t|vID,σ2. IfV1×V2=1, the algorithm outputs 1, and 0 otherwise.(viii)
RL←RevokeRL,ID,t: suppose that the input identityIDis not a non-revoked user at time periodt; then, (ID, t) is added toRLby key authority and outputs newRL.Correctness. Similar to the first generic construction, the correctness of Construction 2 (Con.2) is based on the correctness of two basic HIBS schemes. The difference from Con.1 is that Lx∗ is the signing key corresponding to identity vector t|vx∗ in the second HIBS scheme, and the actual signature key LID is extracted from Lx∗ as t|vx is a prefix identity vector of t|vID. Therefore, the two verify algorithms of HIBS schemes can verify σ1 and σ2, respectively.Security. The SU-CMA security of Con.2 is determined by the SU-CMA security of the fundamental HIBS schemes. Then, we have Theorem 2.Theorem 2.
If the fundamental HIBS schemes are SU-CMA secure, then the FS-RIBS scheme in Con.2 is SU-CMA secure.The proof of Theorem2 is basically the same as Theorem 1. The only difference is that ukt is obtained by a HIBS scheme. We omit its proof.


## 4.2.2. The Second Method

Observe that, in Con.1, as the verifier does not know the target nodex∗ used by the signer to generate the second part signature σ2, he must run the IBS verification algorithm lid times for each node x∈PathID. So, to solve this issue, the signer can indicate the target node x∗ in the signature. The second improved FS-RIBS scheme (referred to as Construction 3) is identical to that of Con.1, except for the following differences in algorithms Sign and Verify.(i)
The modified signing algorithmSignSignkID,t,ID,t,M: for a message M∈ℳ, if ID is a non-revoked user within time period t, the signer should have a valid signing key skIDt=Kt,ltime+1,Lx∗. Then, it sets M′=M|vx∗ and computes σ1←HIBS.SignKt,ltime+1,ID|Jt,ltime+1,M′, and σ2←IBS.SignLx∗,t|vx∗,M′. Finally, the algorithm returns a signature σID,t=σ1,σ2,x∗.(ii)
The modified verification algorithmVerifympk,M,t,ID,σID,t: for a signature σID,t=σ1,σ2,x∗, firstly, the algorithm judges whether x∗∈PathID. If this is not the case, it outputs ⊥; otherwise, it sets M′=M|vx∗ and computes V1←HIBS.Verifympk1,M′,ID|Jt,ltime+1,σ1 and V2←IBS.Verifympk2,M′,t|vx∗,σ2. If V1×V2=1, the algorithm outputs 1, and 0 otherwise.In Con.1, if we change the messageM to M′=M|vx∗, where x∗ is the corresponding node x∗ in the signing key Lx∗, this is just the above improved Construction 3 (Con.3). So, the correctness and security of Con.3 can be proved similarly as in Con.1. We omit the details.


## 5. Lattice-Based Instantiation and Comparison

In this section, we instantiate our generic construction to several lattice-based (H)IBS schemes and compare them with other lattice-based RIBS games. These schemes have or do not have forward security.


### 5.1. Instantiations

The instantiation of the fundamental HIBS scheme uses the scheme of Rückert [28], and the instantiation of the fundamental IBS scheme uses the scheme of Liu et al. [29]. It produces an adaptively secure FS-RIBS scheme (represented by “Con.1+ [28, 29]”). In addition, the instantiations of Construction 2 and Construciton 3 are represented by “Con.2+ [28]” and “Con.3+ [28, 29],” respectively). To reduce the storage overhead of instantiation, we further replace the above HIBS scheme with the HIBS scheme of Tian et al. [30] and the above IBS scheme with the IBS scheme of Chen et al. [31] (represented by “Con.1+ [30, 31],” “Con.2+ [30],” and “Con.3+ [30, 31],” respectively). Next, we take Con.1+ [28, 29] as an example to introduce the detailed requirement and parameter settings:(1)
The schemes in [28, 29] are strongly unforgeable under choice message attack. Their security is based on SIS over lattices.(2)
mpk1=A∗,A,B,y, where A∗∈Zqn×m1+m2,S∗ is a trapdoor ∧q⊥A∗,A:=Ai0,Ai11lk+2ltime, B:=Bi0,Bi11l,y←Zqn. msk1=S∗. The sizes of q,m1,m2,n are defined in Proposition 1 of Rückert [28].(3)
The definitions ofmpk2 and msk2 are not different from those in Section 3 of Liu et al. [29].(4)
The key extraction algorithm is the same as that defined in [28, 29]. The difference is that only input in [28, 29] is the identity, while our HIBS part (user’s long-term private key) input is ID|Jt1,c, and the IBS part (user’s temporary private key) input is t|vx.(5)
HIBS.SignKt,ltime+1,ID|Jt,ltime+1,M is constructed as in Section 4.2 [28] and IBS.SignLx∗,t|vx∗ is constructed in Section 3 [29]. The bottom layer of the signature algorithms in both parts is based on the SIS problem, in which the HIBS.Sign () algorithm is based on the SamplePre algorithm proposed by Craig et al. [32]. IBS.Sign () algorithm is based on SampleLeft algorithm proposed by Agrawal et al. [33].The instantiation details of other schemes (“Con.2+ [28]” and “Con.3+ [28, 29]”) are similar to the above schemes and will not be repeated.


### 5.2. Comparison

We mainly compare security and storage overhead through two tables. We compare the security of our six schemes (“Con.1+ [28, 29],” “Con.2+ [28],” “Con.3+ [28, 29],” “Con.1+ [30, 31],” “Con.2+ [30],” and “Con.3+ [30, 31]”) with other RIBS schemes in Table 1, in terms of whether it has forward security (FS), whether it is signing key exposure resistance (SKER), whether it is under the standard model or the random oracle model (SD/RO), whether it is existential unforgeability or strong unforgeability (SU/EU), whether it is resistant to quantum attacks (RQA), whether it is adaptive or not adaptive, and what difficult problems (DPs) are these schemes based on. We list in Table 2 space cost of our six schemes and other RIBS schemes in terms of mpkmpkskIDskID, uktukt, and signature S. In Table 2, the binary string length of the message is l, T is the maximum time period, and L=RlogN/R. ° means that the complexity of the subsequent scheme must be multiplied by the vector or matrix after °.Table 1
Security comparison of RIBS schemes.
SchemesFSSKERSD/ROSU/EURQAAdaptiveDPSE13 [4]NoYesSDEUNoNoCDHWLH17 [16]YesYesSDEUNoYesq-DHEHTH17 [34]NoNoROEUYesYesSIS/NTRUXWW20 [13]NoYesROEUYesNoSISXWW20 [14]NoNoSDEUYesNoSISXWZ22 [15]NoYesROEUYesNoSISCon.1+ [28, 29]YesYesSDSUYesNoSISCon.1+ [30, 31]YesYesROSUYesYesSISCon.2+ [28]YesYesSDSUYesNoSISCon.2+ [30]YesYesROSUYesYesSISCon.3+ [28, 29]YesYesSDSUYesNoSISCon.3+ [30, 31]YesYesROSUYesYesSISTable 2
Comparison of space cost.
Traditional schemesmpkskIDuktSSE13 [4]OλO1OLO1WLH17 [16]OλO1OLO1Post-quantum schemesmpkskIDuktSHTH17 [34]OλOλlogλOλlogλOλ+logλmpk°ℤqn×mskID°ℤm×mukt°ℤm×mS°ℤqmXWW20 [13]OlO1OLO1XWW20 [14]OlO1OLO1XWZ22 [15]OlO1OLO1Con.1+ [28, 29]Ol+logTOlogTOLOlCon.1+ [30, 31]O1OlogTOLO1Con.2+ [28]Ol+logTOlogTOLOl+logTCon.2+ [30]O1OlogTOLO1Con.3+ [28, 29]Ol+logTOlogTOLOlCon.3+ [30, 31]O1OlogTOLO1It can be seen from Table1 that our schemes can resist most attacks, including quantum computing attacks, forward security, revocation (backward security), standard model, signing key exposure attacks, and strong unforgeability. From Table 2, we can see that the master key and signature size of our “Con.1+ [28, 29],” “Con.2+ [28,]” and “Con.3+ [28, 29]” are large. This is because the underlying HIBS scheme [28] does not apply lattice basis delegation [35]. As shown in “Con.1+ [30, 31],” “Con.1+ [30]” and “Con.3+ [30, 31],” we then used the technique of [30] and the lattice basis delegation [31] to reduce the size of the signature as well as the system master key to a constant size.


## 5.1. Instantiations

The instantiation of the fundamental HIBS scheme uses the scheme of Rückert [28], and the instantiation of the fundamental IBS scheme uses the scheme of Liu et al. [29]. It produces an adaptively secure FS-RIBS scheme (represented by “Con.1+ [28, 29]”). In addition, the instantiations of Construction 2 and Construciton 3 are represented by “Con.2+ [28]” and “Con.3+ [28, 29],” respectively). To reduce the storage overhead of instantiation, we further replace the above HIBS scheme with the HIBS scheme of Tian et al. [30] and the above IBS scheme with the IBS scheme of Chen et al. [31] (represented by “Con.1+ [30, 31],” “Con.2+ [30],” and “Con.3+ [30, 31],” respectively). Next, we take Con.1+ [28, 29] as an example to introduce the detailed requirement and parameter settings:(1)
The schemes in [28, 29] are strongly unforgeable under choice message attack. Their security is based on SIS over lattices.(2)
mpk1=A∗,A,B,y, where A∗∈Zqn×m1+m2,S∗ is a trapdoor ∧q⊥A∗,A:=Ai0,Ai11lk+2ltime, B:=Bi0,Bi11l,y←Zqn. msk1=S∗. The sizes of q,m1,m2,n are defined in Proposition 1 of Rückert [28].(3)
The definitions ofmpk2 and msk2 are not different from those in Section 3 of Liu et al. [29].(4)
The key extraction algorithm is the same as that defined in [28, 29]. The difference is that only input in [28, 29] is the identity, while our HIBS part (user’s long-term private key) input is ID|Jt1,c, and the IBS part (user’s temporary private key) input is t|vx.(5)
HIBS.SignKt,ltime+1,ID|Jt,ltime+1,M is constructed as in Section 4.2 [28] and IBS.SignLx∗,t|vx∗ is constructed in Section 3 [29]. The bottom layer of the signature algorithms in both parts is based on the SIS problem, in which the HIBS.Sign () algorithm is based on the SamplePre algorithm proposed by Craig et al. [32]. IBS.Sign () algorithm is based on SampleLeft algorithm proposed by Agrawal et al. [33].The instantiation details of other schemes (“Con.2+ [28]” and “Con.3+ [28, 29]”) are similar to the above schemes and will not be repeated.


## 5.2. Comparison

We mainly compare security and storage overhead through two tables. We compare the security of our six schemes (“Con.1+ [28, 29],” “Con.2+ [28],” “Con.3+ [28, 29],” “Con.1+ [30, 31],” “Con.2+ [30],” and “Con.3+ [30, 31]”) with other RIBS schemes in Table 1, in terms of whether it has forward security (FS), whether it is signing key exposure resistance (SKER), whether it is under the standard model or the random oracle model (SD/RO), whether it is existential unforgeability or strong unforgeability (SU/EU), whether it is resistant to quantum attacks (RQA), whether it is adaptive or not adaptive, and what difficult problems (DPs) are these schemes based on. We list in Table 2 space cost of our six schemes and other RIBS schemes in terms of mpkmpkskIDskID, uktukt, and signature S. In Table 2, the binary string length of the message is l, T is the maximum time period, and L=RlogN/R. ° means that the complexity of the subsequent scheme must be multiplied by the vector or matrix after °.Table 1
Security comparison of RIBS schemes.
SchemesFSSKERSD/ROSU/EURQAAdaptiveDPSE13 [4]NoYesSDEUNoNoCDHWLH17 [16]YesYesSDEUNoYesq-DHEHTH17 [34]NoNoROEUYesYesSIS/NTRUXWW20 [13]NoYesROEUYesNoSISXWW20 [14]NoNoSDEUYesNoSISXWZ22 [15]NoYesROEUYesNoSISCon.1+ [28, 29]YesYesSDSUYesNoSISCon.1+ [30, 31]YesYesROSUYesYesSISCon.2+ [28]YesYesSDSUYesNoSISCon.2+ [30]YesYesROSUYesYesSISCon.3+ [28, 29]YesYesSDSUYesNoSISCon.3+ [30, 31]YesYesROSUYesYesSISTable 2
Comparison of space cost.
Traditional schemesmpkskIDuktSSE13 [4]OλO1OLO1WLH17 [16]OλO1OLO1Post-quantum schemesmpkskIDuktSHTH17 [34]OλOλlogλOλlogλOλ+logλmpk°ℤqn×mskID°ℤm×mukt°ℤm×mS°ℤqmXWW20 [13]OlO1OLO1XWW20 [14]OlO1OLO1XWZ22 [15]OlO1OLO1Con.1+ [28, 29]Ol+logTOlogTOLOlCon.1+ [30, 31]O1OlogTOLO1Con.2+ [28]Ol+logTOlogTOLOl+logTCon.2+ [30]O1OlogTOLO1Con.3+ [28, 29]Ol+logTOlogTOLOlCon.3+ [30, 31]O1OlogTOLO1It can be seen from Table1 that our schemes can resist most attacks, including quantum computing attacks, forward security, revocation (backward security), standard model, signing key exposure attacks, and strong unforgeability. From Table 2, we can see that the master key and signature size of our “Con.1+ [28, 29],” “Con.2+ [28,]” and “Con.3+ [28, 29]” are large. This is because the underlying HIBS scheme [28] does not apply lattice basis delegation [35]. As shown in “Con.1+ [30, 31],” “Con.1+ [30]” and “Con.3+ [30, 31],” we then used the technique of [30] and the lattice basis delegation [31] to reduce the size of the signature as well as the system master key to a constant size.


## 6. Conclusion and Future Work

This paper introduced a generic method to construct forward-secure revocable identity-based signature and introduced two methods to improve its verification efficiency. In addition, the paper instantiated the generic construction from various lattice-based (H)IBS schemes and obtained the first lattice-based FS-RIBS schemes. In the future, we will try to optimize the fundamental HIBS or IBS scheme to improve its practicality.



---

*Source: 7494452-2022-11-16.xml*