# Fully Secure ID-Based Signature Scheme with Continuous Leakage Resilience

Authors: Qihong Yu; Jiguo Li; Sai Ji
Journal: Security and Communication Networks
 (2022)

---

## Abstract

The side channel attacks will lead to the destruction of the security of the traditional cryptographic scheme. Leakage-resilient identity-based signature has attracted great attention. Based on the dual system encryption technology, we construct an identity-based signature scheme that can resist continuous private key leakage. In the standard model, the security of the scheme is proved. The key points of our leakage-resilient signature scheme are as follows: (1) The private key can be extended according to the security requirements. In other words, when the leakage is serious, we can select a bigger value n, where n is a parameter related to the leakage rate. (2) An elaborate key update algorithm makes the scheme resist continuous leakage attacks. Furthermore, the updated private key has the same distribution as the previous private key. (3) The proposed scheme is fully secure in the standard model rather than in the random oracle model or in the general group model. In order to achieve this goal, we use dual system encryption technology. Thus, the security of the constructed scheme does not depend on the number of queries of the attacker.


---

## Body

## 1. Introduction

In recent years, cryptography researchers have found that some side-channel attacks [1–7] can leak the secret information of the cryptosystem to attackers. In side-channel attacks, the attacker can obtain secret information by observing the energy consumption and timing of the cryptosystem.The traditional provably secure cryptographic system is based on the black-box model, which does not consider secret information leakage. In the case of side-channel attacks, the security of traditional cryptographic schemes is destroyed. Therefore, it is an urgent problem to design leakage-resilient (LR) cryptographic schemes. In recent years, some scholars have been engaged in this field. The research of leakage-resilient cryptography has become a hot topic in cryptography.


### 1.1. Related Work

The research results of leakage-resilient cryptography mainly focus on public key cryptosystem, which can be divided into the following models.


#### 1.1.1. Only Computation Leaks Information

The model is given by [8]. In this model, the complexity of the leakage function is unlimited and the total leakage is unlimited, but the leakage is only allowed to occur in the active part of the memory required by the current calculation. In particular, the attacker can choose a polynomial time function with bounded output to apply to the currently active state. In each round of calculation, the storage parts that are not accessed do not leak information, and only the storage parts that participate in the calculation have information leakage. A secure stream cipher scheme is proposed in [9]. They resist the information leakage about the internal state during the computation of each output block. In each step, the amount of leakage depends on the strength of the underlying pseudorandom generator. Pietrzak [10] relaxes the requirement of the pseudorandom function generator and only needs a weak pseudorandom function that can output pseudorandom value on random inputs. Based on the weak pseudorandom function, Pietrzak constructs a stream cipher that is simpler than [9].


#### 1.1.2. Bounded Leakage Model

In the cold-boot attacks, leakage does occur not only in the calculation process. In order to obtain security against cold-boot attacks, a bounded leakage model is proposed in [11]. In this model, the attacker can freely choose a valid computable function and get the output of the function. The basic requirement is that the output of the function does not disclose the entire key. In a word, in this model, any adversary can obtain information that is shorter than the key length. Under some trapdoor one-way function, Akavia et al. [11] give a secure leakage-resilient identity-based scheme and a public key encryption scheme. The two schemes do not increase the size of the secret key and do not introduce any complication of the natural encryption and decryption routines. In [12], a leakage-resilient public key encryption scheme (PKE) is obtained through a hash proof system (HPS). They give a generic construction of a public key encryption scheme that can resist key leakage from any hash proof system. The resulting scheme is as efficient as the underlying hash proof system and additional computational assumptions are not needed in their construction. After that, [13–16] give LR encryption schemes by HPS with some characteristics. Chen et al. [13] generalize HPS to include the characteristics of anonymity (anonymous HPS), and then use anonymous HPS to construct a leakage-resilient public key encryption scheme (LR-PKE). The concept of weak HPS is defined in [14], which shows that LR weak pseudorandom function, LR message authentication code and LR symmetric encryption scheme can be obtained if a one-way function exists. In [15], a lattice-based LR-PKE is proposed by using an updatable hash proof system. The work [16] gives an efficient public key cryptosystem with leakage-resilience, where plaintext length is independent of key leakage parameters. In another public key cryptosystem, Yu et al. [17] first proposed a certificate-based encryption scheme with leakage-resilience. In [17], the leakage of almost the entire encapsulated symmetric key can be tolerated.


#### 1.1.3. Continuous Leakage Model

When some information is leaked each time the private key is used, how the security of the schemes can be achieved? References [18, 19] solve the open problem proposed in [8], respectively, and propose the continuous leakage model (CLM). The requirement that only computation leaks information is not required for the continuous leakage considered in [18, 19]. In CLM, the key must be updated periodically and the necessary constraint is that the leakage between any two consecutive updates is bounded. In other words, the amount of key leakage in each period is limited, but the amount of key leakage in the whole operation process is infinite. Reference [18] gives IBE and public key encryption schemes with continual leakage-resilience under the decisional linear assumption or the symmetric external Diffie-Hellman assumption. Their core contribution is to show how to update the key. In [19], the key point is that the user may use some additional fresh local randomness to periodically refresh the secret key and not to affect the public key. They design a relation which is called continuous leakage-resilient (CLR) one-way relation (OWR). By the CLR-OWR, they propose CLR identification scheme, CLR signature, and CLR authenticated key agreement protocol.In [20], they explore the case that the memory of a system is divided into two parts and each of them works independently. The attacker can only get leakage information from one part at one time period. They call their security model as the split-state model. By split-state technology, they construct a dynamic secret sharing scheme against continuous leakage attack. Based on the same split-state technology, the work [21] shows that discrete log representations can resist continuous leakage attacks.Dual system encryption [22] gives a new way to achieve security of IBE and some related encryption schemes. In dual system encryption schemes, there are two kinds of ciphertext and key generation algorithms: normal and semifunctional. The key or ciphertext generated by a normal key generation algorithm or normal ciphertext generation algorithm is called normal key or normal ciphertext. The key or ciphertext generated by a semifunctional key generation algorithm or semifunctional ciphertext generation algorithm is called semifunctional key or semifunctional ciphertext. Normal ciphertext can be decrypted by a normal key or semifunctional key. The semifunctional ciphertext cannot be decrypted by the semifunctional key and can be decrypted by a normal key. Inspired by dual system encryption [22], several continuous leakage-resilience encryption schemes with advanced features are given in [23]. They propose fully secure IBE, HIBE, and ABE which are resilient to bounded leakage. These schemes can resist the leakage not only from the private key but also from the master key. In [24], an identity-based broadcast encryption scheme against continuous leakage is proposed. In reference [25], a hierarchical attribute-based encryption scheme with continuous leakage-resilience is proposed. In [26], an identity-based secure scheme against continuous leakage is designed in the standard model. Based on the q-ABDHE assumption, they first propose a CLR-IBE scheme with CPA security in the standard model. Based on their basic CLR-IBE scheme, they give a CLR-CCA secure IBE scheme with continuous leakage amplification. Different from the above schemes, Li et al. [27] extend the length of the key and master key and realize the leakage-resilience by using redundancy. Further, a key-policy attribute-based cryptosystem against continuous auxiliary input leakage is constructed.


### 1.2. Leakage-Resilient Signature

Signature is an important primitive in cryptography. As an important part of data security, a digital signature is used in data integrity verification, nonrepudiation and other aspects. Digital signature schemes with various characteristics have emerged, such as identity-based signature, proxy resignature, blind signature, designated verifier signature, and so on.As far as we know, there are few leakage-resilient signature schemes in the literature.The first secure signature scheme against bounded leakage is given in [28] in the random oracle model. The relative leakage rate of the scheme is almost 1. Based on general primitives (i.e., one-time signature scheme and noninteractive zero knowledge proof), the work [29] constructs leakage-resilient signature schemes in the standard model. As time goes by, the private key may leak more and more information. When the leakage of the private key comes to a certain value, the scheme may become insecure. In order to solve this problem, a continuous leakage-resilient signature is proposed in [18, 19].In [18, 19], the continuous leakage does not need the requirement that only computation leaks information. By the noninteractive zero knowledge proof system (NIZK), the work [30] gives another example of a continuous leakage-resilient signature. The key update algorithm in [30] breaks the second preimage resistance of the hash function H. Thus, they must introduce a new notion: (n, k)-independent preimage resistant hash function H, which is stronger than the notion of second preimage resistance.Galindo and Vivek [31] and Wu et al. [32] give CLR signature schemes under the general bilinear group assumption. It is generally considered that the bilinear group model is weaker than the standard model.


### 1.3. Motivation

Because identity-based signature does not need a digital certificate to verify the correctness of public keys and the authenticity of user identity, it solves the problem of management and distribution of digital certificates in traditional signature. Thus, it is widely used in wireless communication and other fields [33].In order to design an identity-based signature scheme against continuous leakage attacks in the standard model, we must consider the following factors. The private key of the scheme must be extensible. The private key can be easily updated. The security proof of the scheme can be obtained in the standard model. Fortunately, we do it.In this paper, we propose an identity-based signature scheme by using the dual encryption technique. The security of the scheme is proved under the standard model. The scheme can resist continuous key leakage. Referring to the idea of dual system signature [34], our scheme has the normal key and semifunctional keys. The overall concept of our scheme is shown in Figure 1.Figure 1
Overall concept of our scheme.


## 1.1. Related Work

The research results of leakage-resilient cryptography mainly focus on public key cryptosystem, which can be divided into the following models.


### 1.1.1. Only Computation Leaks Information

The model is given by [8]. In this model, the complexity of the leakage function is unlimited and the total leakage is unlimited, but the leakage is only allowed to occur in the active part of the memory required by the current calculation. In particular, the attacker can choose a polynomial time function with bounded output to apply to the currently active state. In each round of calculation, the storage parts that are not accessed do not leak information, and only the storage parts that participate in the calculation have information leakage. A secure stream cipher scheme is proposed in [9]. They resist the information leakage about the internal state during the computation of each output block. In each step, the amount of leakage depends on the strength of the underlying pseudorandom generator. Pietrzak [10] relaxes the requirement of the pseudorandom function generator and only needs a weak pseudorandom function that can output pseudorandom value on random inputs. Based on the weak pseudorandom function, Pietrzak constructs a stream cipher that is simpler than [9].


### 1.1.2. Bounded Leakage Model

In the cold-boot attacks, leakage does occur not only in the calculation process. In order to obtain security against cold-boot attacks, a bounded leakage model is proposed in [11]. In this model, the attacker can freely choose a valid computable function and get the output of the function. The basic requirement is that the output of the function does not disclose the entire key. In a word, in this model, any adversary can obtain information that is shorter than the key length. Under some trapdoor one-way function, Akavia et al. [11] give a secure leakage-resilient identity-based scheme and a public key encryption scheme. The two schemes do not increase the size of the secret key and do not introduce any complication of the natural encryption and decryption routines. In [12], a leakage-resilient public key encryption scheme (PKE) is obtained through a hash proof system (HPS). They give a generic construction of a public key encryption scheme that can resist key leakage from any hash proof system. The resulting scheme is as efficient as the underlying hash proof system and additional computational assumptions are not needed in their construction. After that, [13–16] give LR encryption schemes by HPS with some characteristics. Chen et al. [13] generalize HPS to include the characteristics of anonymity (anonymous HPS), and then use anonymous HPS to construct a leakage-resilient public key encryption scheme (LR-PKE). The concept of weak HPS is defined in [14], which shows that LR weak pseudorandom function, LR message authentication code and LR symmetric encryption scheme can be obtained if a one-way function exists. In [15], a lattice-based LR-PKE is proposed by using an updatable hash proof system. The work [16] gives an efficient public key cryptosystem with leakage-resilience, where plaintext length is independent of key leakage parameters. In another public key cryptosystem, Yu et al. [17] first proposed a certificate-based encryption scheme with leakage-resilience. In [17], the leakage of almost the entire encapsulated symmetric key can be tolerated.


### 1.1.3. Continuous Leakage Model

When some information is leaked each time the private key is used, how the security of the schemes can be achieved? References [18, 19] solve the open problem proposed in [8], respectively, and propose the continuous leakage model (CLM). The requirement that only computation leaks information is not required for the continuous leakage considered in [18, 19]. In CLM, the key must be updated periodically and the necessary constraint is that the leakage between any two consecutive updates is bounded. In other words, the amount of key leakage in each period is limited, but the amount of key leakage in the whole operation process is infinite. Reference [18] gives IBE and public key encryption schemes with continual leakage-resilience under the decisional linear assumption or the symmetric external Diffie-Hellman assumption. Their core contribution is to show how to update the key. In [19], the key point is that the user may use some additional fresh local randomness to periodically refresh the secret key and not to affect the public key. They design a relation which is called continuous leakage-resilient (CLR) one-way relation (OWR). By the CLR-OWR, they propose CLR identification scheme, CLR signature, and CLR authenticated key agreement protocol.In [20], they explore the case that the memory of a system is divided into two parts and each of them works independently. The attacker can only get leakage information from one part at one time period. They call their security model as the split-state model. By split-state technology, they construct a dynamic secret sharing scheme against continuous leakage attack. Based on the same split-state technology, the work [21] shows that discrete log representations can resist continuous leakage attacks.Dual system encryption [22] gives a new way to achieve security of IBE and some related encryption schemes. In dual system encryption schemes, there are two kinds of ciphertext and key generation algorithms: normal and semifunctional. The key or ciphertext generated by a normal key generation algorithm or normal ciphertext generation algorithm is called normal key or normal ciphertext. The key or ciphertext generated by a semifunctional key generation algorithm or semifunctional ciphertext generation algorithm is called semifunctional key or semifunctional ciphertext. Normal ciphertext can be decrypted by a normal key or semifunctional key. The semifunctional ciphertext cannot be decrypted by the semifunctional key and can be decrypted by a normal key. Inspired by dual system encryption [22], several continuous leakage-resilience encryption schemes with advanced features are given in [23]. They propose fully secure IBE, HIBE, and ABE which are resilient to bounded leakage. These schemes can resist the leakage not only from the private key but also from the master key. In [24], an identity-based broadcast encryption scheme against continuous leakage is proposed. In reference [25], a hierarchical attribute-based encryption scheme with continuous leakage-resilience is proposed. In [26], an identity-based secure scheme against continuous leakage is designed in the standard model. Based on the q-ABDHE assumption, they first propose a CLR-IBE scheme with CPA security in the standard model. Based on their basic CLR-IBE scheme, they give a CLR-CCA secure IBE scheme with continuous leakage amplification. Different from the above schemes, Li et al. [27] extend the length of the key and master key and realize the leakage-resilience by using redundancy. Further, a key-policy attribute-based cryptosystem against continuous auxiliary input leakage is constructed.


## 1.1.1. Only Computation Leaks Information

The model is given by [8]. In this model, the complexity of the leakage function is unlimited and the total leakage is unlimited, but the leakage is only allowed to occur in the active part of the memory required by the current calculation. In particular, the attacker can choose a polynomial time function with bounded output to apply to the currently active state. In each round of calculation, the storage parts that are not accessed do not leak information, and only the storage parts that participate in the calculation have information leakage. A secure stream cipher scheme is proposed in [9]. They resist the information leakage about the internal state during the computation of each output block. In each step, the amount of leakage depends on the strength of the underlying pseudorandom generator. Pietrzak [10] relaxes the requirement of the pseudorandom function generator and only needs a weak pseudorandom function that can output pseudorandom value on random inputs. Based on the weak pseudorandom function, Pietrzak constructs a stream cipher that is simpler than [9].


## 1.1.2. Bounded Leakage Model

In the cold-boot attacks, leakage does occur not only in the calculation process. In order to obtain security against cold-boot attacks, a bounded leakage model is proposed in [11]. In this model, the attacker can freely choose a valid computable function and get the output of the function. The basic requirement is that the output of the function does not disclose the entire key. In a word, in this model, any adversary can obtain information that is shorter than the key length. Under some trapdoor one-way function, Akavia et al. [11] give a secure leakage-resilient identity-based scheme and a public key encryption scheme. The two schemes do not increase the size of the secret key and do not introduce any complication of the natural encryption and decryption routines. In [12], a leakage-resilient public key encryption scheme (PKE) is obtained through a hash proof system (HPS). They give a generic construction of a public key encryption scheme that can resist key leakage from any hash proof system. The resulting scheme is as efficient as the underlying hash proof system and additional computational assumptions are not needed in their construction. After that, [13–16] give LR encryption schemes by HPS with some characteristics. Chen et al. [13] generalize HPS to include the characteristics of anonymity (anonymous HPS), and then use anonymous HPS to construct a leakage-resilient public key encryption scheme (LR-PKE). The concept of weak HPS is defined in [14], which shows that LR weak pseudorandom function, LR message authentication code and LR symmetric encryption scheme can be obtained if a one-way function exists. In [15], a lattice-based LR-PKE is proposed by using an updatable hash proof system. The work [16] gives an efficient public key cryptosystem with leakage-resilience, where plaintext length is independent of key leakage parameters. In another public key cryptosystem, Yu et al. [17] first proposed a certificate-based encryption scheme with leakage-resilience. In [17], the leakage of almost the entire encapsulated symmetric key can be tolerated.


## 1.1.3. Continuous Leakage Model

When some information is leaked each time the private key is used, how the security of the schemes can be achieved? References [18, 19] solve the open problem proposed in [8], respectively, and propose the continuous leakage model (CLM). The requirement that only computation leaks information is not required for the continuous leakage considered in [18, 19]. In CLM, the key must be updated periodically and the necessary constraint is that the leakage between any two consecutive updates is bounded. In other words, the amount of key leakage in each period is limited, but the amount of key leakage in the whole operation process is infinite. Reference [18] gives IBE and public key encryption schemes with continual leakage-resilience under the decisional linear assumption or the symmetric external Diffie-Hellman assumption. Their core contribution is to show how to update the key. In [19], the key point is that the user may use some additional fresh local randomness to periodically refresh the secret key and not to affect the public key. They design a relation which is called continuous leakage-resilient (CLR) one-way relation (OWR). By the CLR-OWR, they propose CLR identification scheme, CLR signature, and CLR authenticated key agreement protocol.In [20], they explore the case that the memory of a system is divided into two parts and each of them works independently. The attacker can only get leakage information from one part at one time period. They call their security model as the split-state model. By split-state technology, they construct a dynamic secret sharing scheme against continuous leakage attack. Based on the same split-state technology, the work [21] shows that discrete log representations can resist continuous leakage attacks.Dual system encryption [22] gives a new way to achieve security of IBE and some related encryption schemes. In dual system encryption schemes, there are two kinds of ciphertext and key generation algorithms: normal and semifunctional. The key or ciphertext generated by a normal key generation algorithm or normal ciphertext generation algorithm is called normal key or normal ciphertext. The key or ciphertext generated by a semifunctional key generation algorithm or semifunctional ciphertext generation algorithm is called semifunctional key or semifunctional ciphertext. Normal ciphertext can be decrypted by a normal key or semifunctional key. The semifunctional ciphertext cannot be decrypted by the semifunctional key and can be decrypted by a normal key. Inspired by dual system encryption [22], several continuous leakage-resilience encryption schemes with advanced features are given in [23]. They propose fully secure IBE, HIBE, and ABE which are resilient to bounded leakage. These schemes can resist the leakage not only from the private key but also from the master key. In [24], an identity-based broadcast encryption scheme against continuous leakage is proposed. In reference [25], a hierarchical attribute-based encryption scheme with continuous leakage-resilience is proposed. In [26], an identity-based secure scheme against continuous leakage is designed in the standard model. Based on the q-ABDHE assumption, they first propose a CLR-IBE scheme with CPA security in the standard model. Based on their basic CLR-IBE scheme, they give a CLR-CCA secure IBE scheme with continuous leakage amplification. Different from the above schemes, Li et al. [27] extend the length of the key and master key and realize the leakage-resilience by using redundancy. Further, a key-policy attribute-based cryptosystem against continuous auxiliary input leakage is constructed.


## 1.2. Leakage-Resilient Signature

Signature is an important primitive in cryptography. As an important part of data security, a digital signature is used in data integrity verification, nonrepudiation and other aspects. Digital signature schemes with various characteristics have emerged, such as identity-based signature, proxy resignature, blind signature, designated verifier signature, and so on.As far as we know, there are few leakage-resilient signature schemes in the literature.The first secure signature scheme against bounded leakage is given in [28] in the random oracle model. The relative leakage rate of the scheme is almost 1. Based on general primitives (i.e., one-time signature scheme and noninteractive zero knowledge proof), the work [29] constructs leakage-resilient signature schemes in the standard model. As time goes by, the private key may leak more and more information. When the leakage of the private key comes to a certain value, the scheme may become insecure. In order to solve this problem, a continuous leakage-resilient signature is proposed in [18, 19].In [18, 19], the continuous leakage does not need the requirement that only computation leaks information. By the noninteractive zero knowledge proof system (NIZK), the work [30] gives another example of a continuous leakage-resilient signature. The key update algorithm in [30] breaks the second preimage resistance of the hash function H. Thus, they must introduce a new notion: (n, k)-independent preimage resistant hash function H, which is stronger than the notion of second preimage resistance.Galindo and Vivek [31] and Wu et al. [32] give CLR signature schemes under the general bilinear group assumption. It is generally considered that the bilinear group model is weaker than the standard model.


## 1.3. Motivation

Because identity-based signature does not need a digital certificate to verify the correctness of public keys and the authenticity of user identity, it solves the problem of management and distribution of digital certificates in traditional signature. Thus, it is widely used in wireless communication and other fields [33].In order to design an identity-based signature scheme against continuous leakage attacks in the standard model, we must consider the following factors. The private key of the scheme must be extensible. The private key can be easily updated. The security proof of the scheme can be obtained in the standard model. Fortunately, we do it.In this paper, we propose an identity-based signature scheme by using the dual encryption technique. The security of the scheme is proved under the standard model. The scheme can resist continuous key leakage. Referring to the idea of dual system signature [34], our scheme has the normal key and semifunctional keys. The overall concept of our scheme is shown in Figure 1.Figure 1
Overall concept of our scheme.


## 2. Preliminaries

Definition 1.
Bilinear map
LetG and GT be multiplicative cyclic groups with prime order p. Suppose that g is a generator of G. e:G×G⟶GT is called a bilinear map if it satisfies the following three conditions:(1)
Computability: forg,h∈G, eg,h can be calculated effectively.(2)
Nondegeneracy:∃g∈G, eg,g≠1.(3)
Bilinearity: forg,h∈G and a,b∈Z∗, ega,hb=eg,hab.
Some notations: the size of the termW is denoted by W. The symbol ⋅ is used to denote the product of two vectors. Let ∗ denote the component-wise product of two elements. Let ⋅,⋅,⋅ denote vectors. Let ⋅,⋅,⋅ denote the set of some elements. If g∈G, υ⟶=<υ1,υ2,…,υn>∈Gn, a∈ZN and b⟶=<b1,b2,…,bn>∈ZNn, we use gb⟶ to denote gb1,gb2,…,gbn and use υ⟶a to denote υ1a,υ2a,…,υna. For υ⟶=<υ1,υ2,…,υn>∈Gn and ι⟶=<ι1,ι2,…,ιn>∈Gn, eυ⟶,ι⟶=∏i=1neυi,ιi∈GT.
In [35], the concept of bilinear groups with composite order is proposed. Suppose Ψ is an algorithm that generates bilinear groups with composite order. Ψ takes the safety parameter as input to generate a bilinear group Ω=N=p1p2p3,G,GT,e, in which p1,p2, and p3 are three different prime numbers. Logp1=Logp2=Logp3. G and GT are cyclic groups with order N. e is a bilinear mapping.
In addition, for the security parameterλ, both G and GT are computable in polynomial time. Gp1,Gp2 and Gp3, respectively, represents subgroups with order p1,p2 and p3. Gp1p2 represents subgroup with order Gp1p2. If hi∈Gpi and hj∈Gpj (i≠j), ehi,hj is an identity element in GT. For h1∈Gp1, h2∈Gp2 and g is a generator of G, gp1p2 can generate Gp3, gp1p3 can generate Gp2 and gp2p3 can generate Gp1. We may find α1,α2 such that h1=gp2p3α1, h2=gp1p3α2, and eh1,h2=egp2p3α1,gp1p3α2=egα1,gp3α2p1p2p3=1.
Three assumptions which are given in [22] will be used in our security proof.Assumption 1.
GivenD1=N,G,GT,e,g1,g3, T01=g1z and T11=g1zg2v where z,v∈ZN are randomly selected, any probabilistic polynomial time (PPT) adversary can only distinguish T01=g1z from T11=g1zg2v with only negligible advantage.
Adv1ψ,Aϑ denotes the advantage that adversary breaks the assumption 1. That is to say, Adv1ψ,Aϑ=|PrAD1,T01=1−PrAD1,T11=1|.
IfAdv1ψ,Aϑ is negligible for every PPT adversary, we say that assumption 1 holds.Assumption 2.
GivenD2=N,G,GT,e,g1,g3,g1zg2v,g2ug3ς (z,v,u,ς∈ZN), T0=g1ωg3σ and T1=g1ωg2κg3σ (ω,κ,σ∈ZN), any probabilistic polynomial time adversary can only distinguish T0=g1ωg3σ from T1=g1ωg2κg3σ with only negligible advantage.
Adv2ψ,Aϑ denotes the advantage that adversary breaks the assumption 2. That is to say, Adv2ψ,Aϑ=|PrAD2,T0=1−PrAD2,T1=1|.
IfAdv2ψ,Aϑ is negligible for every PPT adversary, we say that assumption 2 holds.Assumption 3.
GivenD3=N,G,GT,e,g1,g2,g3,g1αg2v,g1sg2u (α,s,v,u∈ZN), T0=eg1,g1αs and T1∈Gp1 (s∈ZN), any probabilistic polynomial time adversary can only distinguish T0=eg1,g1αs from T1∈Gp1 with only negligible advantage.
Adv3ψ,Aϑ denotes the advantage that adversary breaks the assumption 3. That is to say, Adv3ψ,Aϑ=|PrAD3,T0=1−PrAD3,T1=1|.
IfAdv3ψ,Aϑ is negligible for every PPT adversary, we say that assumption 3 holds.


## 3. Formal Description of Continuous Leakage-Resilient Identity-Based Signature

On the basis of [36], the formal description of continuous leakage-resilient identity-based signature scheme (CLR-IBS) is given. Our scheme consists of the following algorithms:Setup: the algorithm is a probabilistic polynomial time algorithm that is run by a private key generator (PKG). It inputs security parametersϑ and outputs public parameters params and master key msk.KeyGen: the algorithm is a probabilistic polynomial time algorithm that is run by a private key generator. The algorithm takes the public parametersmsk and the user’s identity ID as input and outputs the corresponding private key SKID of the user.KeyUpd: the algorithm takes the public parametersmsk and the private key SKID as input and outputs a new private key SKID^.Sign: the algorithm is a probabilistic polynomial time algorithm that is completed by the signer. It inputs the public parametersparams, the message m which is to be signed and the user’s private key SKID. It outputs the signature σ of the message m.Verify: the algorithm is a probabilistic polynomial time algorithm that is completed by the verifier. It takes the public parametersparams, user’s identity ID and the signature σ of the message m as input. Then, it judges whether the signature is valid. If the signature is valid, it outputs “accept.” Otherwise, it outputs “reject.”KeyGenSF: this algorithm is a probabilistic polynomial time algorithm that is run by PKG. The algorithm takes the public parametersparams and the user’s identity ID as input. It outputs the semifunctional private key SKID˜.The algorithm Setup, KeyGen, KeyUpd, and KeyGenSf are generated by PKG, and other algorithms are generated by users. KeyGenSf is only used in security proof.


## 4. Security Model of CLR-IBS

The security of CLR-IBS is defined by the gameGameR. Our scheme is existentially unforgeable under adaptive chosen message attack in the standard model.InGameR, the challenger ℬ holds a list ℒ=ℋ,ℐ,SK,ℒK which consists of handle, collection of identity, secret key and leakage amount, where ℋ, ℐ, SK, and ℒK are the handle’s space, identity’s space, secret key’s space, and the leakage amount’s space. Suppose ℋ=ℕ and ℒK=ℕ.The gameGameR is played by the adversary A and the challenger ℬ as follows.


### 4.1. Initializing

The challenger runs Setup to get the public parametersparams and the master key msk. It keeps msk as secret and gives params to the adversary. The handle h is set to 0. It adds an item 0,0,0,0 in ℒ.The adversaryA can query the following oracles:O−CreateID: given an identity ID, the challenger ℬ looks up the item with the identity ID in ℒ. If ID is in ℒ, it outputs ⊥. Otherwise, the challenger ℬ invokes KeyGen to create the private key SKID and adds the item h+1,ID,SKID,0 in ℒ. The challenger ℬ updates the handle h←h+1.O−Leakh,f: the adversary queries the leakage for a private key that has the handle h. The adversary selects a function f which takes the private key as input and gives the output with constant size. The function f is computable in polynomial time. If the challenger ℬ finds an item h,ID,SKID,L which has the handle h in list ℒ, the challenger ℬ checks if L+|fSKID|≤LSK, where LSK is the maximum of leakage for the private key. If it is true, it will give fSKID to the adversary and updates the tuple h,ID,SKID,L with h,ID,SKID,L+|fSKID| in the list ℒ. Otherwise, the challenger returns ⊥.O−Revealh: the adversary A queries the private key for handle h. The challenger checks whether the item with handle h is in list ℒ. If the item h,ID,SKID,L is in ℒ. The challenger gives the private key SKID to the adversary A and puts the identity ID into ℛ.O−KeyUpdh: for handle h, the adversary A queries the updated private key. The challenger checks whether the item with handle h is in list ℒ. If the item h,ID,SKID,L is in ℒ. The challenger ℬ runs the algorithm KeyUpd. ℬ gives the updated key SKID^ to the adversary A and updates the item h,ID,SKID,L with h,ID,SKID^,L. Otherwise, ℬ returns ⊥.O−Signm,ID: the adversary selects any identity ID and the message m which will be signed and asks the challenger to generate the signature σ about m by the identity ID.


### 4.2. Forgery

The adversary generates a forged signatureσ∗ about a message m∗ and the identity ID∗. If the following conditions are met, it is said that the adversary wins the game:(1)
σ∗ is a valid signature of a message m∗. That is to say, it can satisfy the signature verification algorithm Verify.(2)
The private key about the identityID∗ is not asked by the adversary.(3)
The adversary does not ask for the signatureσ∗s of the message m∗.If all PPT adversaries can only obtain negligible advantages inGameR, the CLR-IBS is said to be secure against private key leakage LSK.


## 4.1. Initializing

The challenger runs Setup to get the public parametersparams and the master key msk. It keeps msk as secret and gives params to the adversary. The handle h is set to 0. It adds an item 0,0,0,0 in ℒ.The adversaryA can query the following oracles:O−CreateID: given an identity ID, the challenger ℬ looks up the item with the identity ID in ℒ. If ID is in ℒ, it outputs ⊥. Otherwise, the challenger ℬ invokes KeyGen to create the private key SKID and adds the item h+1,ID,SKID,0 in ℒ. The challenger ℬ updates the handle h←h+1.O−Leakh,f: the adversary queries the leakage for a private key that has the handle h. The adversary selects a function f which takes the private key as input and gives the output with constant size. The function f is computable in polynomial time. If the challenger ℬ finds an item h,ID,SKID,L which has the handle h in list ℒ, the challenger ℬ checks if L+|fSKID|≤LSK, where LSK is the maximum of leakage for the private key. If it is true, it will give fSKID to the adversary and updates the tuple h,ID,SKID,L with h,ID,SKID,L+|fSKID| in the list ℒ. Otherwise, the challenger returns ⊥.O−Revealh: the adversary A queries the private key for handle h. The challenger checks whether the item with handle h is in list ℒ. If the item h,ID,SKID,L is in ℒ. The challenger gives the private key SKID to the adversary A and puts the identity ID into ℛ.O−KeyUpdh: for handle h, the adversary A queries the updated private key. The challenger checks whether the item with handle h is in list ℒ. If the item h,ID,SKID,L is in ℒ. The challenger ℬ runs the algorithm KeyUpd. ℬ gives the updated key SKID^ to the adversary A and updates the item h,ID,SKID,L with h,ID,SKID^,L. Otherwise, ℬ returns ⊥.O−Signm,ID: the adversary selects any identity ID and the message m which will be signed and asks the challenger to generate the signature σ about m by the identity ID.


## 4.2. Forgery

The adversary generates a forged signatureσ∗ about a message m∗ and the identity ID∗. If the following conditions are met, it is said that the adversary wins the game:(1)
σ∗ is a valid signature of a message m∗. That is to say, it can satisfy the signature verification algorithm Verify.(2)
The private key about the identityID∗ is not asked by the adversary.(3)
The adversary does not ask for the signatureσ∗s of the message m∗.If all PPT adversaries can only obtain negligible advantages inGameR, the CLR-IBS is said to be secure against private key leakage LSK.


## 5. Construction of CLR-IBS

Based on the composite order group of 3 primes, we propose the CLR-IBS scheme, which consists of six algorithms. SubgroupGp3 is used to randomize private keys. Subgroup Gp2 is only used to generate the semifunctional private key in the proof.


### 5.1. Setup

The algorithm randomly selectsg1,u1,h1,u2,h2∈Gp1, g3∈Gp3, x1,…,xn∈ZN, α,r∈ZN, y1,…,yn∈ZN, ρ⟶=ρ1,...,ρn+1∈ZNn+1, and ρn+2∈ZN, where n≥2 is an integer. The value of n is variable. If n is large, the leakage rate is high accordingly. The leakage rate is the ratio of leakage size to the size of a secret key. If n is small, the public key is short.The public parameters areparams=N,g1,g3,h1,u1,h2,u2,g1x1,…,g1xn,eg1,g1α and the master key is msk=F⟶1,F2=<g1y1,…,g1yn,g1α∏j=1ng1−xjyj>∗g3ρ⟶1,g3ρn+2.


### 5.2. KeyGen

For the identityID∈ZN. The algorithm randomly selects z1,…,zn∈ZN, ρ⟶′=ρ1′,...,ρn+1′∈ZNn+1, ρn+2′∈ZN and rID∈ZN. It generates the private key(1)SKID=K⟶1,K2,=F⟶1∗<g1z1,…,g1zn,u1IDh1rID∏j=1ng1−xjzj>∗g3ρ⟶′1,F2.g1rID.g3ρn+2′=<g1y1,…,g1yn,g1α∏j=1ng1−xjyj>∗g3ρ⟶1∗<g1z1,…,g1zn,u1IDh1rID∏j=1ng1−xjzj>∗g3ρ⟶′1,g3ρn+2.g1rID.g3ρn+2′=<g1y1+z1,...,g1yn+zn,g1αu1IDh1rID∏j=1ng1−xjyj+zj>∗g3ρ⟶1+ρ⟶′1,g1rID.g3ρn+2+ρn+2′.Denotewj=yj+zjj=1,…,n, ρ⟶″=ρ⟶1+ρ⟶′, and ρn+2″=ρn+2+ρn+2′. We get SKID=K⟶1,K2:(2)=<g1w1,…,g1wn,g1αu1IDh1rID∏j=1ng1−xjwj>∗g3ρ⟶″,g1rID∗g3ρn+2″


### 5.3. KeyUpd

The algorithm takes public parametersparams and the private key SKID as input and outputs a new private key SKID^. For the private key SKID=K⟶1,K2=<g1w1,…,g1wn,g1αu1IDh1rID∏j=1ng1−xjwj>∗g3ρ⟶″,g1rID∗g3ρn+2″, the algorithm selects randomly Δwj∈ZN (j∈1,2,…,n), Δρ⟶″=Δρ1″,Δρ2″,…,Δρn+1″∈ZNn+1, and Δρn+2″,ΔrID∈ZN. It gets the new private key.SKID^=<g1w1+Δw1,…,g1wn+Δwn,g1αu1IDh1−rID+ΔrID∏j=1ng1−xjwj+Δwj>∗g3ρ″⟶+Δρ⟶″,g1rID+ΔrID.g3Δρn+2″+Δρn+2″. Because Δwj∈ZNj=1,…,n, Δρ⟶″∈ZNn+1, and Δρn+2″,ΔrID∈ZN are all random, we know that wj+Δwjj=1,…,n, ρ⟶″+Δρ⟶″, and rID+ΔrID are random. The private keys SKID^ and SKID have the same distribution. Thus, the private key is updated.Denotewj′=wj+Δwjj=1,…,n, rID′=rID+ΔrID, ρ⟶‴=ρ⟶″+Δρ⟶″, and ρ‴n+2=ρn+2″+Δρn+2″. The updated private key is written as SKID^=<g1w1′,…,g1wn′,g1αu1IDh1−rID′∏j=1ng1−xjwj′>∗g3ρ⟶‴,g1rID′∗g3ρ‴n+2, which has the same form as the original private key SKID.


### 5.4. Sign

For the messagem∈ZN, the user ID chooses randomly rID′∈ZN and rm∈ZN and signs the message m with his private key SKID=K⟶1,K2.(3)σ=σ⟶1,σ2,σ3=K⟶1∗<1,…,1,u1IDh1rID′u2mh2rm>,K2⋅grID′,grm=<g1w1,...,g1wn,g1αu1IDh1rID+rID′u2mh2rm∏j=1ng1−xjwj>∗g3ρ′⟶,g1rID+rID′⋅g3ρn+2′,grm.


### 5.5. Verify

The receiver receives the signatureσ=σ⟶1,σ2,σ3 for the message m from the user ID. Then he verifies whether e<g1x1,…,g1xn,g1>,σ⟶1=eg1,g1α⋅eu1IDh1,σ2⋅eu2mh2,σ3.If the equation does not hold, then it outputs “reject.” Otherwise, it outputs “accept.”


### 5.6. KeyGenSf

First, the private key generator calls the normal private key generation algorithm to generate the normal private keySKID=K⟶1,K2. Second, a private key generator randomly selects γ⟶=γ1,...,γn+1∈ZNn+1 and γn+2∈ZN to generate the semifunctional private key SKID˜.(4)SKID˜=K⟶1∗g2γ⟶,K2∗g2γn+2=<g1w1,...,g1wn,g1αu1IDh1rID∏j=1ng1−xjwj>∗g3ρ⟶″∗g2γ⟶,g1rIDg3ρ″⟶n+2⋅g2γn+2.The signatures of a semifunctional private key and normal private key can all pass the verification algorithm. Semifunctional private key is only used for a security proof. In practical application, we will use the normal private key for signature.Correctness is as follows:(5)e<g1x1,...,g1xn,g1>,σ⟶1=e<g1x1,...,g1xn,g1>,<g1w1,...,g1wn,g1αu1IDh1rID+rID′u2mh2rm∏j=1ng1−xjwj>∗g3ρ⟶″=∏j=1neg1xj,g1wj⋅eg1,g1αu1IDh1rID+rID′u2mh2rm⋅eg1,∏j=1ng1−xjwj=∏j=1neg1,g1xjwj⋅eg1,g1αu1IDh1rID+rID′u2mh2rm.eg1,∏j=1ng1−xjwj=eg1,∏j=1ng1xjwj⋅eg1,g1αu1IDh1rID+rID′u2mh2rm⋅eg1,∏j=1ng1−xjwj=eg1,g1αu1IDh1rID+rID′u2mh2rm=eg1,g1α⋅eg1,u1IDh1rID+rID′u2mh2rm=eg1,g1α⋅eg1,u1IDh1rID+rID′⋅eg1,u2mh2rm=eg1,g1α⋅eg1rID+rID′,u1IDh1⋅eg1rm,u2mh2=eg1,g1α⋅eσ2,u1IDh1⋅eσ3,u2mh2.


## 5.1. Setup

The algorithm randomly selectsg1,u1,h1,u2,h2∈Gp1, g3∈Gp3, x1,…,xn∈ZN, α,r∈ZN, y1,…,yn∈ZN, ρ⟶=ρ1,...,ρn+1∈ZNn+1, and ρn+2∈ZN, where n≥2 is an integer. The value of n is variable. If n is large, the leakage rate is high accordingly. The leakage rate is the ratio of leakage size to the size of a secret key. If n is small, the public key is short.The public parameters areparams=N,g1,g3,h1,u1,h2,u2,g1x1,…,g1xn,eg1,g1α and the master key is msk=F⟶1,F2=<g1y1,…,g1yn,g1α∏j=1ng1−xjyj>∗g3ρ⟶1,g3ρn+2.


## 5.2. KeyGen

For the identityID∈ZN. The algorithm randomly selects z1,…,zn∈ZN, ρ⟶′=ρ1′,...,ρn+1′∈ZNn+1, ρn+2′∈ZN and rID∈ZN. It generates the private key(1)SKID=K⟶1,K2,=F⟶1∗<g1z1,…,g1zn,u1IDh1rID∏j=1ng1−xjzj>∗g3ρ⟶′1,F2.g1rID.g3ρn+2′=<g1y1,…,g1yn,g1α∏j=1ng1−xjyj>∗g3ρ⟶1∗<g1z1,…,g1zn,u1IDh1rID∏j=1ng1−xjzj>∗g3ρ⟶′1,g3ρn+2.g1rID.g3ρn+2′=<g1y1+z1,...,g1yn+zn,g1αu1IDh1rID∏j=1ng1−xjyj+zj>∗g3ρ⟶1+ρ⟶′1,g1rID.g3ρn+2+ρn+2′.Denotewj=yj+zjj=1,…,n, ρ⟶″=ρ⟶1+ρ⟶′, and ρn+2″=ρn+2+ρn+2′. We get SKID=K⟶1,K2:(2)=<g1w1,…,g1wn,g1αu1IDh1rID∏j=1ng1−xjwj>∗g3ρ⟶″,g1rID∗g3ρn+2″


## 5.3. KeyUpd

The algorithm takes public parametersparams and the private key SKID as input and outputs a new private key SKID^. For the private key SKID=K⟶1,K2=<g1w1,…,g1wn,g1αu1IDh1rID∏j=1ng1−xjwj>∗g3ρ⟶″,g1rID∗g3ρn+2″, the algorithm selects randomly Δwj∈ZN (j∈1,2,…,n), Δρ⟶″=Δρ1″,Δρ2″,…,Δρn+1″∈ZNn+1, and Δρn+2″,ΔrID∈ZN. It gets the new private key.SKID^=<g1w1+Δw1,…,g1wn+Δwn,g1αu1IDh1−rID+ΔrID∏j=1ng1−xjwj+Δwj>∗g3ρ″⟶+Δρ⟶″,g1rID+ΔrID.g3Δρn+2″+Δρn+2″. Because Δwj∈ZNj=1,…,n, Δρ⟶″∈ZNn+1, and Δρn+2″,ΔrID∈ZN are all random, we know that wj+Δwjj=1,…,n, ρ⟶″+Δρ⟶″, and rID+ΔrID are random. The private keys SKID^ and SKID have the same distribution. Thus, the private key is updated.Denotewj′=wj+Δwjj=1,…,n, rID′=rID+ΔrID, ρ⟶‴=ρ⟶″+Δρ⟶″, and ρ‴n+2=ρn+2″+Δρn+2″. The updated private key is written as SKID^=<g1w1′,…,g1wn′,g1αu1IDh1−rID′∏j=1ng1−xjwj′>∗g3ρ⟶‴,g1rID′∗g3ρ‴n+2, which has the same form as the original private key SKID.


## 5.4. Sign

For the messagem∈ZN, the user ID chooses randomly rID′∈ZN and rm∈ZN and signs the message m with his private key SKID=K⟶1,K2.(3)σ=σ⟶1,σ2,σ3=K⟶1∗<1,…,1,u1IDh1rID′u2mh2rm>,K2⋅grID′,grm=<g1w1,...,g1wn,g1αu1IDh1rID+rID′u2mh2rm∏j=1ng1−xjwj>∗g3ρ′⟶,g1rID+rID′⋅g3ρn+2′,grm.


## 5.5. Verify

The receiver receives the signatureσ=σ⟶1,σ2,σ3 for the message m from the user ID. Then he verifies whether e<g1x1,…,g1xn,g1>,σ⟶1=eg1,g1α⋅eu1IDh1,σ2⋅eu2mh2,σ3.If the equation does not hold, then it outputs “reject.” Otherwise, it outputs “accept.”


## 5.6. KeyGenSf

First, the private key generator calls the normal private key generation algorithm to generate the normal private keySKID=K⟶1,K2. Second, a private key generator randomly selects γ⟶=γ1,...,γn+1∈ZNn+1 and γn+2∈ZN to generate the semifunctional private key SKID˜.(4)SKID˜=K⟶1∗g2γ⟶,K2∗g2γn+2=<g1w1,...,g1wn,g1αu1IDh1rID∏j=1ng1−xjwj>∗g3ρ⟶″∗g2γ⟶,g1rIDg3ρ″⟶n+2⋅g2γn+2.The signatures of a semifunctional private key and normal private key can all pass the verification algorithm. Semifunctional private key is only used for a security proof. In practical application, we will use the normal private key for signature.Correctness is as follows:(5)e<g1x1,...,g1xn,g1>,σ⟶1=e<g1x1,...,g1xn,g1>,<g1w1,...,g1wn,g1αu1IDh1rID+rID′u2mh2rm∏j=1ng1−xjwj>∗g3ρ⟶″=∏j=1neg1xj,g1wj⋅eg1,g1αu1IDh1rID+rID′u2mh2rm⋅eg1,∏j=1ng1−xjwj=∏j=1neg1,g1xjwj⋅eg1,g1αu1IDh1rID+rID′u2mh2rm.eg1,∏j=1ng1−xjwj=eg1,∏j=1ng1xjwj⋅eg1,g1αu1IDh1rID+rID′u2mh2rm⋅eg1,∏j=1ng1−xjwj=eg1,g1αu1IDh1rID+rID′u2mh2rm=eg1,g1α⋅eg1,u1IDh1rID+rID′u2mh2rm=eg1,g1α⋅eg1,u1IDh1rID+rID′⋅eg1,u2mh2rm=eg1,g1α⋅eg1rID+rID′,u1IDh1⋅eg1rm,u2mh2=eg1,g1α⋅eσ2,u1IDh1⋅eσ3,u2mh2.


## 6. Security Proof

If the forgery signaturem∗,σ∗=σ⟶1∗,σ2∗,σ3∗ is valid, suppose z∈ZN and z=0modp1,1modp2,0modp3. The forgery signature can be divided into two types. Type I: σ⟶1∗z=1⟶n+1,σ2∗z=1,σ3∗z=1. Type II: σ⟶1∗z≠1⟶n+1 or σ2∗z≠1 or σ3∗z≠1.Theorem 1.
If Assumptions1–3 are true, the signature scheme given in this paper is leakage-resilient and secure in the standard model. The amount of private key leakage is LSK=n−2Λ−1λ, where λ=logp2 and n≥2 is a positive constant integer.Whenn is large, the tolerable leakage rate is high. When n is relatively small, the public parameters is also relatively short. The specific leakage performance analysis is given in Section 8.In general, we prove the security of the scheme by dual system encryption technology. A series of games are used to complete the proof. Suppose the adversary makesq1 private key extraction queries, q2 signature queries. Let q=q1+q2. GameR is the real security game. The other games are modified from the game GameR. The first game is a real security game and the adversary has only a negligible advantage in winning the last one. The adjacent two games are indistinguishable.These games are defined as follows:GameR:this is a real security game.Game0: it is similar to GameR, but it has some restrictions. When the adversary outputs the forged signature of the message m∗, it needs that ID∗≠IDimodp21≤i≤q1 and ID∗,m∗≠IDj,mjmodp21≤i≤q2, where IDi1≤i≤q1 is the ith inquired identity and IDj,mj is used for the jth signature query.Gamei (i∈1,q): in this game, for the previous i private key query, the challenger answers with the semifunctional private key (if it is a signature query, the challenger first calculates the corresponding semifunctional private key and then uses the signature algorithm to generate the signature). The rest is the same as Game0.Proof.
Through a series of gamesGameR and Gamei (i∈0,1,…,q), we use Lemmas 1–6 to prove the security. First, Lemma 1 is used to obtain the leakage bound. Second, we use Lemmas 2–6 to prove that these games are indistinguishable. Thus, the safety can be proved.Lemma 1.
The amount of private key leakage about our CLR-IBS can reachLSK=n−2Λ−1λ.Proof.
We use a conclusion in [18] to prove this lemma.
Conclusion 1 [18]: suppose that p is a prime number, n1≥n2≥2 (n1,n2∈N) and Φ⟵Zpn1. Let that X be a matrix (X⟵Zpn1×n2) and Y be also a matrix with rank 1 (Y⟵Rk1Zpn2×1). ε is used to represent a value that can be ignored. If f:Zpn1⟶W is a leakage function where |W|≤4⋅1−1/p⋅pn2−1⋅ε2, the statistical distance SDX,fX⋅Y,X,fΦ≤ε.
From conclusion 1, we can easily get the following Ratiocination 1.
Ratiocination 1: suppose thatp is a prime and n1≥3. Select δ⟶←Zpn1,τ⟶←Zpn1 and τ⟶′←Zpn1, such that τ⟶′ and δ⟶ are orthogonal modulo p by dot product. Let f be a leakage function mapping Zpm to W (i.e. f:Zpm⟶W). If |W|≤4⋅1−1/p⋅pn−1⋅ε2, the statistical distance SDδ⟶,fτ⟶′,δ⟶,fτ⟶ is negligible. That is to say, SDδ⟶,fτ⟶′,δ⟶,fτ⟶≤ε where ε is negligible.Proof.
By Conclusion 1, we setn2=n1−1, so n1=n2+1≥n2≥2. Thus, τ⟶ matches to Φ and the basis of the orthogonal space of δ⟶ matches to X. So, the distribution of τ⟶′ is the same as X⋅Y when Y←Rk1Zpn1−1×1. That is to say, Y is a matrix of n1−1 rows and 1 column with rank 1. Since δ⟶ is chosen randomly, X←Zpn1×n1−1 is determined by δ⟶. Thus, we conclude that SDδ⟶,fτ⟶′,δ⟶,fτ⟶=distX,fX⋅T,X,fΦ.
Letn2=n, p2=p and ε=p2−Λ. λ denotes logp2. The leakage size will be up to logW≤n−1logp2−2Λlogp2=n−2Λ−1logp2  =  n−2Λ−1λ. Therefore, we conclude that the leakage amount is up to LSK=L=n−2Λ−1λ.Lemma 2.
In the case of private key leakageLSK=n−2Λ−1λ, if there is an algorithm A (the adversary) such that |AdvAGameR−AdvAGame0|≥ε, we can construct an algorithm ℬ (the challenger) to break assumption 2 with a nonnegligible advantage.Proof.
First, givenℬ an instance D2=N,G,GT,e,g1,g3,g1zg2v,g2ug3ς, T0=g1ωg3σ and T1=g1ωg2κg3σ (ω,κ,σ∈ZN), ℬ plays GameR or Game0 with A. The challenger publishes the system parameters params=N,g1,g3,h1=g1b1,u1=g1a1,h2=g1b1,u2=g1a2,g1x1,…,g1xn,eg1,g1α to the adversary, where α,a1,a2,b1,b2∈ZN,x1,…,xn∈ZN are randomly selected. For any private key extraction query or signature query of the adversary, the challenger can use the master key to calculate.
Finally, suppose that the adversary generates a forged signatureσ∗=σ⟶1∗,σ2∗,σ3∗ of the user ID∗ about the message m∗. The adversary hopes that the forged signature can pass the verification. For 1≤i≤q1, ID∗=IDimodp2 and ID∗≠IDimodN, if a=gcdID∗,IDi and b=N/a, three cases are considered:(1)
a=p2p3,b=p1(2)
a=p1p2,b=p3(3)
a=p2,b=p1p3
Ifg2ug3ςa=1, the first case occurs and b=p1. Judge whether eTb,g1zg2v=1. If the equation holds, T∈Gp1p3. Otherwise, T∈Gp1p2p3.
Ifg2ug3ςa≠1, judge whether g1zg2va=1. If the equation holds, the second case occurs and b=p3. Then, judge whether eTb,g2ug3ς=1. If the equation holds, T∈Gp1p3. Otherwise, T∈Gp1p2p3.
Ifg2ug3ςa≠1 and g1zg2va≠1, the third case occurs and b=p1p3. Judge whether Tb=1. If the equation holds, T∈Gp1p3. Otherwise, T∈Gp1p2p3.
Similarly, if for somej where 1≤j≤q2, ID∗=IDjmodN, m∗=mjmodp2 and m∗≠mjmodN, the challenger can still break the assumption 2. The adversary outputs the forged signature σ∗=σ⟶1∗,σ2∗,σ3∗ of the use ID∗ about the message m∗, where ID∗≠IDimodp21≤i≤q1 and ID∗,m∗≠IDj,mjmodp21≤j≤q2.
Probability analysis: ifT∈Gp1p3, ℬ simulates the game Game0 properly. If T∈G, ℬ simulates the game GameR properly. Thus, |PrℬD2,T∈Gp1p3=0]−ℬD2,T∈G=0|=|AdvAGame0−AdvAGameR|≥ε.
In the case of private key leakageLSK=n−2Λ−1λ, if there is an adversary who can distinguish Game0 from GameR with an advantage ε that cannot be ignored, ℬ can break Assumption 2 with an advantage ε that cannot be ignored. This contradicts Assumption 2. Consequently, |AdvAGame0−AdvAGameR|≤ε. Thus, Lemma 2 holds.Lemma 3.
Under Assumption1 and in the case of private key leakage LSK=n−2Λ−1λ, the adversary (an algorithm A) can only output the forged signature of type II with negligible advantage in game Game0.Proof.
First, givenℬ an instance D1=N,G,GT,e,g1,g3, T0=g1z and T1=g1zg2v (z,v∈ZN), ℬ plays Game0 with A. The challenger publishes the system parameters params=N,g1,g3,h1=g1b1,u1=g1a1,h2=g1b1,u2=g1a2,g1x1,…,g1xn,eg1,g1α to the adversary, where α,a1,a2,b1,b2∈ZN, and x1,…,xn∈ZN are randomly selected. For any private key extraction query or signature query of the adversary, the challenger can use the master key to calculate.
Finally, suppose that the adversary generates the forged signatureσ∗=σ⟶1∗,σ2∗,σ3∗ of the user ID∗ about the message m∗.
σ∗=σ⟶1∗,σ2∗,σ3∗=<g1w1,...,g1wn,g1αu1ID∗h1rIDu2m∗h2rm∏j=1ng1−xjwj>∗g3ρ″⟶∗g2s⟶12,g1rID∗g3ρn+2″∗g2s22,g1rm.g2s32 The adversary hopes that the forged signature can pass the verification.
Furthermore, the challenger checks whether the forged signature satisfies the following equation:(6)e<Tx1,…,Txn,T>,σ⟶∗1=eg1,Tα⋅eg1a1ID∗+b1,σ2∗⋅eg1a2ID∗+b2,σ3∗
Obviously, ifT∈Gp1, the above equation is always true. If T∈Gp1p2, the equation also holds when the adversary forges the signature of type I with the probability ε.
If the adversary forges the signature of type II with the probabilityε, the equation holds if and only if s⟶12⋅<0,…,0,1>=s22a1ID∗+b1+s32a2m∗+b2modp2. In the whole game, the adversary will not get any information about a1,b1,a2,b2modp2. So, the probability that the equation holds is negligible.
That is to say, in the case of private key leakageLSK=n−2Λ−1λ, if there is an adversary who can output the forged signature of type II with an advantage ε that cannot be ignored, the equation does not hold. We judge that T∈Gp1p2.Lemma 4.
Under Assumption2 and in the case of private key leakage LSK=n−2Λ−1λ, if the adversary (an algorithm A) can output the forged signature of type II with negligible advantage in the game Gamek−1, A can also output the forged signature of type II with negligible advantage in game Gamek.Proof.
First, givenℬ an instance D2=N,G,GT,e,g1,g3,g1zg2v,g2ug3ς, T0=g1ωg3σ, T1=g1ωg2κg3σ (ω,κ,σ∈ZN), Y⟶=y1,…,yn+1∈Gp2n+1 and y∈Gp2, ℬ plays Gamek−1 or Gamek with A. The challenger publishes the system parameters params=N,g1,g3,h1=g1b1,u1=g1a1,h2=g1b1,u2=g1a2,g1x1,…,g1xn,eg1,g1α to the adversary, where α,a1,a2,b1,b2∈ZN, and x1,…,xn∈ZN are randomly selected. For any private key extraction query or signature query of the adversary, the challenger can use the master key to calculate.
For the adversary’s previousk−1 private key extraction queries, ℬ will generate a semifunctional private key. ℬ selects t1,…,tn+2∈Z randomly and returns SKID˜=g1w1g2ug3ςt1,…,g1wng2ug3ςtn,g1αuiIDih1rIDi∏j=1ng1−xjwjg2ug3ςtn+1>,g1rIDig2ug3ςtn+2. If it is a signature query, the challenger first calculates the corresponding private key and then uses the private key to calculate the corresponding signature. The following cases will be handled in this way.
For the adversary’s laterq−k private key extraction queries, ℬ selects t1,…,tn+2∈Z randomly and returns SKID=g1w1g3ςt1,...,g1wng3ςtn,g1αuiIDih1rIDi∏j=1ng1−xjwjg3ςtn+1>,g1rIDig3ςtn+2. If it is a signature query, the challenger first calculates the corresponding private key and then uses the private key to calculate the corresponding signature.
For the adversary’skth private key extraction query, ℬ selects w1,…,wn∈ZN, ri∈ZN randomly and returns SKID=<Tw1,…,Twn,g1α∏j=1ng1−xjwjTa1IDk+b1>g3ρ⟶,Tg3ρn+2.
IfT∈Gp1p3, the private key is normal. ℬ simulates the game Gamek−1 properly. If T∈G, the private key is semifunctional. ℬ simulates the game Gamek properly.
Finally, suppose that the adversary generates the forged signatureσ∗=σ⟶1∗,σ2∗,σ3∗ of the user ID∗ about the message m∗. σ∗=σ⟶1∗,σ2∗,σ3∗=<g1w1,...,g1wn,g1αu1ID∗h1rIDu2m∗h2rm∏j=1ng1−xjwj>∗g3ρ′⟶∗g2s⟶12,g1rID∗g3ρn+2′∗g2s22,g1rm∗g2s32. The adversary hopes that the forged signature can pass the verification.
Furthermore, the challenger checks whether the forged signature satisfies the following equation:(7)e<g1zg2vx1,…,g1zg2vxn,g1zg2v>,σ⟶∗1=eg1,g1zg2vα⋅eg1a1ID∗+b1,σ2∗⋅eg1a2ID∗+b2,σ3∗.
Probability analysis: ifT∈Gp1p3, ℬ simulates the game Gamek−1 properly. If the adversary outputs a forged signature of type I with an advantage that can be ignored, the equation also holds. Thus, the adversary outputs the forged signature of type II with an advantage that can also be ignored.
IfT∈Gp1p2p3, ℬ simulates the game Gamek properly. If the adversary outputs a forged signature of type I with an advantage ε that can be ignored, the equation also holds.
When the adversary forges the signature of type II with the probabilityε if and only if s⟶12.<0,…,0,1>=s22a1ID∗+b1+s32a2m∗+b2modp2, the equation also holds. In the whole game, the adversary gets information about a1,b1,a2,b2modp2 only by the kth query. Because ID∗≠IDimodp21≤i≤q1, ID∗,m∗≠IDj,mjmodp21≤j≤q2 and m∗=mjmodp2, the equation holds with a probability ε that can also be ignored.
That is to say, in the case of private key leakageLSK=n−2Λ−1λ, if there is an adversary in the game Gamek who can output the forged signature of type II with an advantage ε that cannot be ignored such that the equation does not hold, we judge that T∈Gp1p2p3.Lemma 5.
Under Assumption3 and in the case of private key leakage LSK=n−2Λ−1λ, the adversary (an algorithm A) can only output the forged signature of type I with negligible advantage in the game Gameq.Proof.
First, given the challengerℬ an instance D3=N,G,GT,e,g1,g2,g3,g1αg2v,g1sg2u, Y⟶=y1,…,yn+1∈Gp2n+1, y∈Gp2 and T (T=eg1,g1αs or T∈Gp1, where s∈ZN), ℬ plays Gameq with A.
The challenger publishes the system parametersparams=N,g1,g3,h1=g1b1,u1=g1a1,h2=g1b1,u2=g1a2,g1x1,…,g1xn,eg1,g1α to the adversary, where α,a1,a2,b1,b2∈ZN, and x1,…,xn∈ZN are randomly selected. For any private key extraction query or signature query of the adversary, the challenger can use the master key to calculate.
Finally, suppose that the adversary generates the forged signatureσ∗=σ⟶1∗,σ2∗,σ3∗ of the user ID∗ about the message m∗. σ∗=σ⟶1∗,σ2∗,σ3∗=<g1w1,…,g1wn,g1αu1ID∗h1rIDu2m∗h2rm∏j=1ng1−xjwj>∗g3ρ′⟶∗g2s⟶12,g1rID∗g3ρn+2′∗g2s22,g1rm∗g2s32. The adversary hopes that the forged signature can pass the verification.
Furthermore, the challenger checks whether the forged signature satisfies the following equation:(8)e<g1zg2vx1,…,g1zg2vxn,g1zg2v>,σ⟶∗1=T⋅eg1a1ID∗+b1,σ2∗⋅eg1a2ID∗+b2,σ3∗.
Probability analysis: according to Lemma4, if the adversary outputs forged signature of type II in game Gameq with an advantage ε, the adversary outputs forged signature of type I with an advantage ε.
IfT=eg1,g1αs, the equation also holds. If T≠eg1,g1αs, the equation does not hold. Whether the equation holds equals that whether T=eg1,g1αs. That is to say, in the case of private key leakage LSK=n−2Λ−1λ, the adversary A can only output the forged signature of type I with negligible advantage in the game Gameq.Lemma 6.
Under Assumption2 and in the case of private key leakage LSK=n−2Λ−1λ, if the adversary (an algorithm A) can only output the forged signature of type I with negligible advantage in the game Gamek, the adversary can only output the forged signature of type I with negligible advantage in the game Gamek−1.Proof.
First, given the challengerℬ an instance D2=N,G,GT,e,g1,g3,g1zg2v,g2ug3ς, Y⟶=y1,…,yn+1∈Gp2n+1, y∈Gp2 and T (T=g1ωg3σ or T=g1ωg2κg3σ, where ω,κ,σ∈ZN), ℬ plays Gamek−1 or Gamek with A.
The challenger publishes the system parametersparams=N,g1,g3,h1=g1b1,u1=g1a1,h2=g1b1,u2=g1a2,g1x1,…,g1xn,eg1,g1α to the adversary, where α,a1,a2,b1,b2∈ZN, and x1,…,xn∈ZN are randomly selected. For any private key extraction query or signature query of the adversary, the challenger can use the master key to calculate. It is similar to Lemma 4.
Finally, suppose that the adversary generates the forged signatureσ∗=σ⟶1∗,σ2∗,σ3∗ of the user ID∗ about the message m∗. σ∗=σ⟶1∗,σ2∗,σ3∗=<g1w1,…,g1wn,g1αu1ID∗h1rIDu2m∗h2rm∏j=1ng1−xjwj>∗g3ρ′⟶∗g2s⟶12,g1rID∗g3ρn+2′∗g2s22,g1rm∗g2s32. The adversary hopes that the forged signature can pass the verification.
Probability analysis: according to Lemma4, the adversary outputs forged signature of type II with an advantage ε. If T∈Gp1p3, ℬ simulates the game Gamek−1 properly. Thus, based on Assumption 2, the adversary outputs forged signature of type I with an advantage ε. ℬ simulates the game Gamek properly if and only if T∈Gp1p2p3.
That is to say, in the case of private key leakageLSK=n−2Λ−1λ, if the adversary (an algorithm A) can only output the forged signature of type I with a nonnegligible advantage, we can judge that T∈Gp1p2p3.


## 7. Continuous Leakage Resilience

If the private key of a cryptographic scheme cannot be updated, the leakage will exceed a certain bound with the passage of time, which will break the security of the scheme. In order to keep continuous leakage resilience, the private key must be updated periodically. By the algorithm KeyUpd given in Section5, our CLR-IBS scheme obtains continuous leakage resilience.Theorem 2.
Our CLR-IBS scheme can resist continuous leakage attacks of the private key under the standard model.Proof.
By the algorithm KeyUpd, we can obtain continuous leakage resilience which is similar to that of [25, 37]. The algorithm KeyUpd inputs the private key SKID and the system parameters params. Then, it outputs a new private key SKID^. In the algorithm KeyUpd, some extra values are added to the private key. Because the extra values are randomly selected from ZN, they have the same distribution with the old ones. Thus, SKID^ has the same distribution as the old ones. If the private key is updated periodically, continuous leakage resilience will be obtained.


## 8. Leakage Performance and Comparisons

In our scheme,p1,p2 and p3 are all prime numbers of λ bits. The length of the private key is 3n+3λ bits. The amount of private key leakage is at most n−2Λ−1λ bits. Here, n≥2 is a variable integer, which is used to obtain different leakage resilience. Λ is a normal number. The relative leakage rate of the private key is n−2Λ−1λ/3n+3λ=n−2Λ−1/3n+3.n is a variable. If we want to get a high relative leakage rate, we can select a larger number n. Thus, the leakage-resilience performance of the system is better. However, the private key becomes longer accordingly. If n is a small number, the relative leakage rate is also small. But the private key is also relatively short.Table1 shows the comparisons between the scheme in this paper and that in [36]. Table 1 shows the size and leakage-resilience of the private key.Table 1
The comparisons between our scheme and that in [36].
PerformanceIBS of [36]Our CLR-IBSLength of private key3×3λ3n+3λAmount of leakage-resilience0n−2Λ−1λThe paper [36] gives an IBS without leakage-resilience. We propose an IBS which can resist private key continuous leakage.In specific applications, we can set different values according to the specific requirement of the leakage rate. The leakage rate of the private key depends on the valuen. When the value is larger, the private key leakage rate of our scheme can reach 1/3.References [28, 29, 31] give secure signature schemes against bounded leakage. These schemes can tolerate almost the whole private key leakage. Reference [28] uses Fiat Shamir transform to prove the security under the random oracle model, while reference [29] proves the security by constructing general primitives (i.e. one-time signature scheme and noninteractive zero knowledge proof) under the standard model.References [18, 19, 32] construct continuous leakage-resilient signature schemes, respectively. In these schemes, the relative leakage rate of the private key is very small. Furthermore, reference [32] gives a continuous leakage-resilient signature scheme that is based on the bilinear group model. It is generally considered that the bilinear group model is weaker than the standard model.Table2 shows the comparisons of leakage performance and security performance of several LR signature schemes and ours, in which K-Linear represents K-Linear assumption, UOWHF represents universal one-way hash functions, HCRHF represents a homomorphic collision-resistant hash function family, A1, A2 and A3 stand the three static assumptions of our scheme, GBG represents the generic bilinear group model, GGM represents generic group model, STD M represents the standard model.Table 2
The comparisons of leakage performance and security performance of several schemes and ours.
SchemesDifficult hypothesisRelative leakage rateLeakage modelSecurity model[29]-1UOWHF1BLMSTD M[29]-2UOWHF1/4BLMSTD M[29]-3HCRHF1/2BLMSTD M[31]GBG1/2BLMGGM[19]K-linear1/(k + 1)CLMSTD M[32]GBGLog (logP)CLMGGMOursA1, A2, A31/3CLMSTD M


## 9. Conclusion

In this paper, the formal definition and security model of CLR-IBS are given. Furthermore, we propose a CLR-IBS scheme. The scheme can resist continuous leakage of the private key. The security of the scheme is proved by three static assumptions under the composite order bilinear group. The presented scheme has good leakage resilience. The private key leakage rate of the scheme can reach 1/3. Because ring signature also has good properties and application value, it is our next research direction to construct identity-based ring signature scheme with leakage resilience.



---

*Source: 8220259-2022-01-24.xml*