You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Leakage-Resilient Revocable Identity-Based Signature with Cloud Revocation Authority

Article type: Research Article

Authors: Wu, Jui-Di | Tseng, Yuh-Min; ∗ | Huang, Sen-Shan | TSAI, Tung-Tso

Affiliations: Department of Mathematics, National Changhua University of Education, Jin-De Campus, Chang-Hua City 500, Taiwan

Correspondence: [∗] Corresponding author.

Keywords: ID-based signature, leakage resilience, revocation, side-channel attack

DOI: 10.15388/20-INFOR406

Journal: Informatica, vol. 31, no. 3, pp. 597-620, 2020

Received October 2019
|
Accepted February 2020
|
Published: 2020
Get PDF open access

Abstract

Very recently, side-channel attacks have threatened all traditional cryptographic schemes. Typically, in traditional cryptography, private/secret keys are assumed to be completely hidden to adversaries. However, by side-channel attacks, an adversary may extract fractional content of these private/secret keys. To resist side-channel attacks, leakage-resilient cryptography is a countermeasure. Identity-based public-key system (ID-PKS) is an attractive public-key setting. ID-PKS settings not only discard the certificate requirement, but also remove the construction of the public-key infrastructure. For solving the user revocation problem in ID-PKS settings, revocable ID-PKS (RID-PKS) setting has attracted significant attention. Numerous cryptographic schemes based on RID-PKS settings have been proposed. However, under RID-PKS settings, no leakage-resilient signature or encryption scheme is proposed. In this article, we present the first leakage-resilient revocable ID-based signature (LR-RIBS) scheme with cloud revocation authority (CRA) under the continual leakage model. Also, a new adversary model of LR-RIBS schemes with CRA is defined. Under this new adversary model, security analysis is made to demonstrate that our LR-RIBS scheme with CRA is provably secure in the generic bilinear group (GBG) model. Finally, performance analysis is made to demonstrate that our scheme is suitable for mobile devices.

1Introduction

Identity-based public-key system (ID-PKS) (Shamir, 1984; Boneh and Franklin, 2001) not only discards the certificate requirement, but also removes the construction of the public-key infrastructure. In an ID-PKS setting, there are two roles, namely, users and a private key generator (PKG). A user’s identity information is regarded as the user’s public key. The PKG employs the user’s identity information to generate the user’s associated private key. For public-key settings, user revocation mechanisms are required to revoke the misbehaving or compromised users before the intended expiration date of their public keys. Typically, a conventional public-key setting adopts the certificate revocation list (CRL) (Housley et al., 2002) to manage the revoked users. In such a setting, each user has a public key and the associated certificate. Before employing a user’s public key, one must validate its associated certificate while looking up the CRL to ensure that the user’s certificate was not revoked. However, ID-PKS settings do not require the usage of certificates so that the CRL mechanism cannot be employed to the ID-PKS settings.

Recently, Tseng and Tsai (2012) proposed a revocable ID-PKS (RID-PKS) setting with a public channel. In the RID-PKS setting, a user’s private key includes two parts, namely, a secret key and a time update key. Initially, the PKG employs a user’s identity information to generate and send the associated secret key to the user using a secure channel. Also, the PKG generates the time update key by time period and the user’s identity information. Namely, for all non-revoked users, the PKG periodically generates and sends the associated time update keys to these users using a public channel. Subsequently, numerous cryptographic primitives based on RID-PKS settings were presented, such as revocable ID-based encryption (RIBE) (Tsai et al., 2012, 2013a) and revocable ID-based signature (RIBS) schemes (Tsai et al., 2013b; Hung et al., 2017). Furthermore, several RIBE and RIBS schemes (Li et al., 2015; Tseng et al., 2018; Jia et al., 2017) have been proposed to outsource the periodical generations of time update keys to a cloud revocation authority (CRA).

Quite recently, side-channel attacks have threatened all traditional cryptographic schemes because private/secret keys are assumed to be completely hidden to adversaries in traditional cryptography. By various kinds of side-channel attacks (Boneh et al., 1997; Kocher et al., 1999; Brumley and Boneh, 2005; Biham et al., 2008), an adversary can extract fractional content of private/secret keys participated in computation rounds. To resist side-channel attacks, leakage-resilient cryptography is a countermeasure while the design of leakage-resilient cryptographic schemes has attracted significant attention from researchers. For leakage-resilient cryptographic schemes, adversaries are allowed to extract fractional content of private/secret keys while these schemes still retain secure. However, no leakage-resilient RIBS scheme based on RID-PKS settings is proposed. In the article, our goal is to propose the first leakage-resilient RIBS (LR-RIBS) scheme.

1.1Related Work

Here, let us briefly review some leakage-resilient encryption and signature schemes based on conventional and ID-PKS settings.

According to the amount of leaked content of private/secret keys during the life time, the leakage model has two kinds, namely, bounded leakage model (Alwen et al., 2009) and continual leakage model (Brakerski et al., 2010). In a leakage-resilient cryptographic scheme under the bounded leakage model, the overall amount of leaked content has to be limited to a ratio or a fixed bit-length of private/secret keys. On the contrary, a leakage-resilient cryptographic scheme under the continual leakage model allows adversaries to continuously extract fractional content of private/secret keys so that its overall amount of leaked content is unlimited. For security robustness, a cryptographic scheme under the continual leakage model is stronger than that under the bounded leakage model. The properties of continual leakage model have four properties as below:

  • – Bounded leakage of single observation: A cryptographic scheme typically includes several computation rounds (i.e. observations). In each computation round, an adversary can extract fractional content of private/secret keys. Namely, adversaries can select a leakage function f for each computation round and then obtain the leakage information f(SK), where SK denotes the involved private/secret keys and the output information of f(SK) is bounded to λ bits.

  • – Only computation leakage: Adversaries are only allowed to extract fractional content of private/secret keys involved in the current computation round.

  • – Independent leakage: Any two leaked fractional contents of private/secret keys in various computation rounds are mutually independent. For achieving this property, a private/secret key must be updated before (or after) running each computation round.

  • – Overall unbounded leakage: The total amount of leakage information is overall unbounded. Indeed, by the independent leakage property, the total leakage amount of private/secret keys is not strict.

Under the continual leakage model, there are several leakage-resilient encryption and signature schemes based on the conventional public-key settings. In the generic bilinear group (GBG) model (Boneh et al., 2005), Kiltz and Pietrzak (2010) presented a leakage-resilient encryption scheme that allows adversaries to continually extract fractional content of secret/private keys. In Kiltz and Pietrzak’s scheme, each user’s secret key is divided into two components. After/before performing the decryption procedure, a receiver (user) must refresh two components of her/his secret key. The key idea of refreshing employs the multiplicative blinding technique which appeared in Kiltz and Pietrzak (2010). Based on this key idea, Galindo et al. (2016) presented an efficient leakage-resilient ElGamal public-key encryption scheme. Also, Galindo and Virek (2013) proposed the first leakage-resilient signature scheme under the continual leakage model. To improve the performance of their scheme, Tang et al. (2014) presented a modified leakage-resilient signature scheme by employing Boneh et al.’s short signature (Boneh et al., 2001).

Based on an ID-PKS setting, Brakerski et al. (2010) presented the first leakage-resilient ID-based encryption (LR-IBE) scheme under the continual leakage model. Subsequently, Yuen et al. (2012) presented an improvement on Brakerski et al.’s scheme in terms of computational costs. under the continual leakage model, Wu et al. (2016) proposed the first leakage-resilient ID-based signature (LR-IBS) scheme.

1.2Contribution and Organization

Up to date, no work has been published on leakage-resilient revocable ID-based signature (LR-RIBS) scheme. In the article, we present a new adversary model of LR-RIBS schemes with a cloud revocation authority (CRA) under the continual leakage model. In the adversary model, there are two types of adversaries, namely, Type I adversary (a curious CRA or an outsider) and Type II adversary (a revoked user). As compared with the adversary models of RIBS schemes presented in Tsai et al. (2013b), Hung et al. (2017), Jia et al. (2017), three new key leakage queries, namely, the key extract leak query, time key update leak query and signing leak query are added to our new adversary model. These added leak queries allow an adversary to continuously extract fractional content of private/secret keys participated in the computation rounds.

The first LR-RIBS scheme with CRA is proposed while the revocation functionality is outsourced to the CRA. By employing Kiltz and Pietrzak’s key refreshing idea (Kiltz and Pietrzak, 2010), the proposed LR-RIBS scheme with CRA allows adversaries to continuously gain fractional content of private/secret keys so that its overall amount of leaked content is unbounded and it possesses overall unbounded leakage property. Under the new adversary model and generic bilinear group (GBG) model (Boneh et al., 2005), security analysis is given to show that our LR-RIBS scheme is existential unforgeability against adaptive chosen-message (UF-LR-RIBS-ACMA) attacks of both Types I and II adversaries. Finally, performance analysis and comparisons are made to demonstrate that the proposed LR-RIBS scheme requires some additional computation costs than the previously proposed RIBS schemes. The point is that the proposed LR-RIBS scheme with CRA can resist side-channel attacks. By the simulation experiences (Lynn, 2015) on a smartphone, the proposed LR-RIBS scheme with CRA is still suitable for mobile devices.

The rest of the paper is organized as follows. In Section 2, preliminaries are given. In Section 3, we define the framework and adversary model of LR-RIBS schemes with CRA. In Section 4, we propose a secure LR-RIBS scheme with CRA under the continual leakage model. Section 5 demonstrates the security analysis of the proposed LR-RIBS scheme. In Section 6, we present the performance analysis and comparisons with the previously proposed RIBS schemes. Finally, conclusions are given in Section 7.

2Preliminaries

Several preliminaries are introduced in this section.

2.1Bilinear groups

Let G and GT be two multiplicative cyclic groups with (large) prime order p. Let g be a generator of G. An admissible bilinear map eˆ:G×G→GT possesses the following three properties:

  • 1. Non-degeneracy: eˆ(g,g)≠1.

  • 2. Bilinearity: for all r, s∈Zp∗, eˆ(gr,gs)=eˆ(g,g)rs.

  • 3. Computability: eˆ(g,g)rs can be computed efficiently for any r, s∈Zp∗.

For the detailed properties and settings with regard to bilinear groups, please refer to Boneh and Franklin (2001), Tsai et al. (2013b), Lynn (2015), Scott (2011).

2.2Generic Bilinear Group Model

By extending the generic group model presented by Shoup (1997), Boneh et al. (2005) introduced the generic bilinear group (GBG) model. Their GBG model is an adversary model played by adversaries and a challenger. In the GBG model, to perform various kinds of group operations, adversaries have to request the associated group oracles/queries to the challenger. Also, the challenger uses bit strings to denote group elements of G and GT. More precisely, the challenger employs two random injective functions ε:Zp→ξ and εT:Zp→ξT, respectively, to transform the elements of G and GT into bit strings in ξ and ξT. In addition, both ξ and ξT have p elements and are disjoint, namely |ξ|=|ξT|=p and ξ∩ξT=ϕ. The discrete logarithm problem on G or GT will be solved if the adversary discovers a collision encoding element of G or GT.

  • – Discrete logarithm problem: Let G and GT be two multiplicative cyclic groups of a large prime order p. Let g and eˆ(g,g) denote the generators of G and GT, respectively. Given a group element gz∈G or eˆ(g,g) ∈GT with unknown z∈Zp∗, the discrete logarithm problem in G and GT is that no probabilistic polynomial time (PPT) algorithm A may obtain z with a non-negligible probability (Boneh et al., 2005).

In the GBG model, there are three group operations, namely, the multiplication QG on G, the multiplication QT on GT, and the bilinear map Qp:G×G→GT, which is denoted by eˆ above. For any r, s∈Zp∗, we have the following properties:

  • – QG(ε(r),ε(s))→ε(r+smodp).

  • – QT(εT(r),εT(s))→εT(r+smodp).

  • – QP(ε(r),ε(s))→εT(rsmodp).

2.3Entropy of Leakage Content

In information theory, entropy is usually employed to measure the uncertainty of unknown private/secret values. Assume that W is a discrete random variable (i.e. secret value) and Pr[W=w] denotes the probability of W=w. The min-entropy of W is the estimation of W=w with the largest probability, namely, the worst-case predictability of W. Two types of min-entropies are defined as below:

  • • Min-entropy of W:

    H∞(X)=−log2(maxwPr[W=w]),

  • • Average conditional min-entropy of W under the condition Z=z:

    H˜∞(W|Z)=−log2(Ez←Z[maxwPr[W=w|Z=z]]).

To measure the entropy of a finite discrete random variable (secret value) with fractional leakage content, Dodis et al. (2008) derived the following consequence.

Lemma 1

Lemma 1(See Dodis et al., 2008).

Assume that a leakage function f:W→{0,1}λ takes as input a discrete random variable W and the maximal output bit-length is λ. Under the event f(W), the average conditional min-entropy of W is H˜∞(W|f(W))≧H∞(W)−λ.

By Lemma 1, Galindo and Virek (2013) derived the following consequence to measure the probability distribution of a polynomial with multiple random variables and leakage content.

Lemma 2

Lemma 2(See Galindo and Virek, 2013).

Let F∈Zp[W1,W2,…,Wn] be a non-zero polynomial. Its maximal output bit-length of fraction leakage content and degree are λ (0≦λ≦logp). and at most d, respectively. Let Pi be the associated probability distributions of Wi=wi, for i=1,2,…,n, that satisfy H∞(Pi)≧logp−λ. Thus, we have Pr[F(w1,w2,…,wn)=0]≦dp2λ if wi⟵PiZp (for i=1,2,…,n) are mutually independent. Therefore, Pr[F(w1,w2,…,wn)=0] is negligible if λ<logp−ω(loglogp).

3System Architecture, Framework and Adversary Model

Here, let us present the system architecture, framework and adversary model of LR-RIBS schemes with CRA. In an LR-RIBS scheme with CRA, there are three roles, namely, PKG, CRA and users. Several notations are defined as below:

  • • SPK: the PKG’s system public key.

  • • SSK: the PKG’s system secret key.

  • • TPK: the CRA’s time public key.

  • • TSK: the CRA’s time secret key.

  • • ID: a user’s identity, where ID∈{0,1}∗.

  • • Tt: a time period, for t=1,2,…,z, where z represents the number of periods.

  • • UTKID,t: the time update key of the user with identity ID at period Tt.

  • • USKID: the secret key of the user with identity ID.

  • • msg: a message.

  • • σ: a signature value.

Fig. 1

The system architecture of LR-RIBS schemes with CRA.

The system architecture of LR-RIBS schemes with CRA.

3.1System Architecture

The system architecture of LR-RIBS schemes with CRA is depicted in Fig. 1. Firstly, the PKG sets the system secret key SSK, the time secret key TSK and a total number z of periods T0,T1,…,Tz while computing public parameters PP and sending TSK to the CRA. The PKG employs SSK to generate the secret key USKID of the user with identity ID. By a secure channel, the PKG sends USKID to the user. For non-revoked user ID at time period Tt, the CRA employs TSK to generate the time update key UTKID,t. By a public channel (e.g. e-mail), the CRA sends UTKID,t to the user. Hence, a user’s private key consists of two parts, namely, USKID and UTKID,t. Suppose that the user (signer) with identity ID at period Tt would like to sign a message msg, the signer employs USKID and UTKID,t to generate a signature value σ and sends it to a verifier.

3.2Framework

To achieve overall unbounded leakage property (Galindo and Virek, 2013; Wu et al., 2016, 2018, 2019), a private/secret key must be split into two components. Additionally, each private/secret key participated in the associated algorithm is also refreshed before/after each algorithm invocation. In such a case, the PKG’s system secret key SSK, the CRA’s time secret key TSK and a user’s secret key USKID must, respectively, be split into two components. In the meantime, the PKG’s SSK must be refreshed before/after performing the key extract algorithm. Also, the CRA’s TSK and a user’s secret key USKID must be refreshed before/after performing the time key update and signing algorithms, respectively. In the following, we define the framework (syntax) of LR-RIBS schemes with CRA.

Definition 1.

An LR-RIBS scheme with CRA includes five algorithms as follows:

  • • System setup: The PKG first sets the system secret key SSK=(SSK0,1,SSK0,2), a time secret key TSK=(TSK0,1,TSK0,2) and z periods T0,T1,…,Tz while generating public parameters PP and sending TSK to the CRA using a secure channel. The PKG holds SSK=(SSK0,1, SSK0,2) and publishes PP.

  • • Key extract: In the i-th invocation of the Key extract algorithm, the PKG refreshes (SSKi−1,1,SSKi−1,2) to set the current system secret key (SSKi,1,SSKi,2). The PKG takes as input a user’s identity ID and generates the user’s associated secret key USKID. The PKG returns USKID to the user via a secure channel. Afterwards, the user sets her/his initial secret key USKID=(USKID,0,1,USKID,0,2).

  • • Time key update: In the j-th invocation of the Time key update algorithm, the CRA refreshes (TSKj−1,1,TSKj−1,2) to set the current time secret key (TSKj,1,TSKj,2). The CRA takes as input a user’s identity ID and a period Tt, and generates the user’s time update key UTKID,t. The CRA sends UTKID,t to the user via a public channel.

  • • Signing: In the k-th invocation of the Signing algorithm, the user ID refreshes (USKID,k−1,1,USKID,k−1,2) to set her/his current secret key (USKID,k,1,USKID,k,2). At period Tt, the user ID employs her/his current secret key (USKID,k,1,USKID,k,2) and time update key UTKID,t to generate a signature value σ on a message msg. The user outputs a signature tuple (ID,Tt,msg,σ).

  • • Verifying: Upon receiving (ID,Tt,msg,σ), the verifier returns either “accept” or “reject”.

3.3Adversary Model (Security Notions)

By extending the adversary model (security notions) presented in the RIBS schemes (Tsai et al., 2013b; Hung et al., 2017; Jia et al., 2017), we present an adversary model of LR-RIBS schemes with CRA, which allows an adversary to extract fractional content of the private/secret keys. According to our framework, an adversary can extract fractional content of the PKG’s system secret key (SSKi,1,SSKi,2) in the i-th invocation of the Key extract algorithm. Also, an adversary can extract fractional content of the CRA’s time secret key (TSKj,1,TSKj,2) in the j-th invocation of the Time key update algorithm. In the k-th invocation of the Signing algorithm by the user ID at period Tt, an adversary can extract fractional content of the user’s secret key (USKID,k,1,USKID,k,2). Six leakage functions fKE,i, hKE,i, fTKU,j, hTKU,j, fS,k, hS,k are employed to model the leakage abilities. More precisely, the output is in the form of three pairs (fKE,i(SSKi,1), hKE,i(SSKi,2)), (fTKU,j(TSKj,1), hTKU,j(TSKj,2)) and (fS,k(USKID,k,1), hS,k(USKID,k,2)) to indicate, respectively, the fractional content of (SSKi,1, SSKi,2), (TSKj,1, TSKj,2) and (USKID,k,1, USKID,k,2). Also, we require that the output bit-string lengths of the six leakage functions are at most λ. For brevity, we introduce the following notation which will be used in the sequel:

  • – ΛfKE,i=fKE,i(SSKi,1).

  • – ΛhKE,i=hKE,i(SSKi,2).

  • – ΛfTKU,j=fTKU,j(TSKj,1).

  • – ΛhTKU,j=hTKU,j(TSKj,2).

  • – ΛfS,k=fS,k(USKID,k,1).

  • – ΛhS,k=hS,k(USKID,k,2).

In the adversary model of LR-RIBS schemes with CRA, there are two types of adversaries:

  • • Type I adversary AI (a curious CRA or an outsider): AI denotes a curious CRA or an outsider. AI is allowed to acquire the time update key UTKID,t for any user ID and period Tt. Meanwhile, AI can acquire the secret key USKID for any ID, except for the target identity ID∗. In addition, AI can extract fractional content of the target user’s secret key USKID∗ in the Signing algorithm and the PKG’s system secret key SSK in the Key extract algorithm.

  • • Type II adversary AII (a revoked user): AII denotes the adversary who was a legal user with identity ID∗ and has been revoked at period Tt∗. In such a case, AII is allowed to acquire the secret key USKID and time update key UTKID,t for any ID and Tt. But, AII is disallowed to acquire the time update key UTKID,t∗ for the target identity ID∗ at period Tt∗. In addition, AII can extract fractional content of the CRA’s time secret key TSK in the Time key update algorithm.

The following security game GLR-RIBS is used to model the adversary model (security notions) of LR-RIBS schemes with CRA.

Definition 2

Definition 2(GLR-RIBS).

For the LR-RIBS scheme with CRA, the game GLR-RIBS is used to model the interactions between an adversary A (AI or AII) and a challenger C. It is said that the LR-RIBS scheme with CRA is existential unforgeability against adaptive chosen-message attacks (UF-LR-RIBS-ACMA) if no probabilistic polynomial-time (PPT) adversary may win GLR-RIBS with a non-negligible probability. Three phases of GLR-RIBS are presented as below:

  • – Setup phase. The challenger C performs the System setup algorithm in Definition 1 to set a system secret key SSK=(SSK0,1,SSK0,2), a time secret key TSK=(TSK0,1,TSK0,2) and a total number z of periods T0,T1,…,Tz. Meanwhile, C sets and publishes public parameters PP. In addition, by a secure channel, C sends the time secret key TSK to the CRA. Also, if A is a Type I adversary, the time secret key TSK is sent to A.

  • – Query phase. The adversary A can request the following queries to C adaptively.

    • • Key extract query (ID): Upon receiving a user’s ID, C generates and sends the user’s corresponding secret key to A.

    • • Key extract leak query (i,fKE,i,hKE,i): Upon receiving two leakage functions fKE,i and hKE,i, C computes the fractional leakage content ΛfKE,i and ΛhKE,i of the PKG’s system secret key (SSKi,1,SSKi,2). Afterwards, C sends ΛfKE,i and ΛhKE,i to A. For the i-th Key extract query, A is allowed to request the Key extract leak query only once.

    • • Time key update query (ID,Tt): Upon receiving a user’s ID and a period Tt, C generates and sends the user’s time update key UTKID,t to A.

    • • Time key update leak query (j,fTKU,j,hTKU,j): Upon receiving two leakage functions fTKU,j and hTKU,j, C computes the fractional leakage content ΛfTKU,j and ΛhTKU,j of the CRA’s time secret key (TSKj,1, TSKj,2). Afterwards, C sends ΛfTKU,j and ΛhTKU,j to A. For the j-th Time key update query, A is allowed to request the Time key update leak query only once.

    • • Signing query (ID,Tt,msg): Upon receiving a message msg and a user’s ID at period Tt, C generates a signature value σ and returns (ID, Tt, msg, σ) to A.

    • • Signing leak query (ID, k, fS,k, hS,k): Upon receiving two leakage functions fS,k and hS,k, C computes the fraction leakage content ΛfS,k and ΛhS,k of the signer’s secret key (USKID,k,1, USKID,k,2), and returns ΛfS,k and ΛhS,k to A. In the k-th Signing query requested by the user ID, A is allowed to issue the Signing leak query only once.

  • – Forgery phase. The adversary A outputs a signature tuple (ID∗,Tt∗,msg∗,σ∗) and A wins GLR-RIBS if the following conditions hold.

    • (1) If A is a Type I adversary (a curious CRA or an outsider), the Key extract query on ID∗ cannot be requested.

    • (2) If A is a Type II adversary (a revoked user), the Time key update query on (ID∗, Tt∗) cannot be requested.

    • (3) The Signing query on (ID∗, Tt∗, msg∗) cannot be requested.

    • (4) The output of the Verifying algorithm on (ID∗, Tt∗, msg∗, σ∗) is “accept”.

4The Proposed LR-RIBS Scheme with CRA

Here, let us present the first LR-RIBS scheme with CRA that consists of five algorithms as below:

  • – System setup: The PKG runs the System setup algorithm to choose two groups G=⟨g⟩ and GT=⟨eˆ(g,g)⟩ of a large prime order p. The algorithm sets a total number z of periods T0,T1,…,Tz. Moreover, the algorithm performs the following steps to compute the system secret key SSK=(SSK0,1,SSK0,2), the time secret key TSK=(TSK0,1,TSK0,2) and public parameters PP.

    • (1) Choose a random integer α∈Zp∗, and compute the system secret key SSK = gα and the system public key SPK=eˆ(g,gα). Also, choose an integer α∈Zp∗ at random, and compute the initial system secret key (SSK0,1,SSK0,2)=(gα,SSK·g−a).

    • (2) Choose a random integer β∈Zp∗, and set the time secret key TSK = gβ and time public key TPK = eˆ(g,gβ).

    • (3) Choose six random integers u, v, w, x, y, z∈Zp∗, and set U=gu, V=gv, W=gw, X=gx, Y=gy and Z=gz.

    • (4) Set PP=(p,G,GT,eˆ,g,SPK,TPK,U,V,W,X,Y,Z).

    • (5) Finally, the PKG holds (SSK0,1,SSK0,2) and publishes PP while sending TSK to the CRA via a secure channel. Afterwards, the CRA selects a random integer b∈Zp∗, and uses TSK to set the initial time secret key (TSK0,1,TSK0,2)=(gb,TSK·g−b).

  • – Key extract: In the i-th invocation of the Key extract algorithm, the PKG sets the current system secret key (SSKi,1,SSKi,2) by refreshing (SSKi−1,1,SSKi−1,2). Afterwards, the PKG takes as input a user’s identity ID and carries out the following steps:

    • (1) Choose a random integer a∈Zp∗, and update the PKG’s system secret key (SSKi,1,SSKi,2)=(SSKi−1,1·ga,SSKi−1,2·g−a).

    • (2) Choose a random integer γ∈Zp∗, and compute QKID=gγ.

    • (3) Compute TID=STID(modp), where STID is the integer value of the bit string IDQKID. And compute the temporary information TIKE=SSKi,1·(U·VTID)γ and the user’s secret key USK ID=SSKi,2·TIKE.

    • (4) Finally, by a secure channel, the PKG sends USKID and QKID to the user. Upon receiving USKID and QKID,1, the user randomly selects an integer c∈Zp∗, and sets the user’s initial secret key (USKID,0,1,USKID,0,2)=(gc,USKID·g−c).

  • – Time key update: In the j-th invocation of the Time key update algorithm, the CRA sets the current time secret key (TSKj,1,TSKj,2) by refreshing (TSKj−1,1, TSKj−1,2). Afterwards, the CRA takes as input a user’s identity ID and a period Tt, and carries out the following steps:

    • (1) Choose a random integer b∈Zp∗, and update the CRA’s current time secret key (TSKi,1,TSKi,2)=(TSKi−1,1·gb,TSKi−1,2·g−b).

    • (2) Randomly select an integer η∈Zp∗, and compute QTKID,t=gη.

    • (3) Compute TTD=STTD(modp), where STTD is the integer value of the bit string ID||Tt||QTKID,t. And compute the temporary information TITKU=TSKj,1·(W·XTTD)η and the user’s time secret key UTKID,t=TSKj,2·TITKU.

    • (4) Finally, by a secure channel, the CRA sends UTKID,t and QTKID,t to the user.

  • – Signing: For the k-th invocation of the Signing algorithm, the user ID sets her/his current secret key (USKID,k,1, USKID,k,2) by refreshing (USKID,k−1,1, USKID,k−1,2). At period Tt, the user employs her/his current secret key (USKID,k,1, USKID,k,2) and time update key UTKID,t to output a signature tuple (ID,Tt,msg,σ) with σ=(σ1=QKID,σ2=QTKID,t,σ3,σ4) by carrying out the following steps:

    • (1) Choose a random integer c∈Zp∗, and update the signer’s secret key (USKID,k,1,USKID,k,2)=(USKID,k−1,1·gc,USKID,k,2·g−c).

    • (2) Choose a random integer δ∈Zp∗, and compute σ3=gδ, the temporary information TIS=USKID,k,1·UTKID,t·(Y·Zmsg)δ and σ4=USKID,k,2·TIS.

    • (3) Set the signature tuple (ID,Tt,msg,σ) with σ=(σ1=QKID,σ2=QTKID,t,σ3,σ4).

  • – Verifying: For a signature tuple (ID,Tt,msg,σ=(σ1,σ2,σ3,σ4)), the verifier compute TID=STID(modp) and TTD=STTD(modp), where STID and STTD are the integer values of the bit strings ID||σ1 and ID||Tt||σ2, respectively. The verifier outputs “accept” if the verifying equality eˆ(g,σ4)=SPK·TPK·eˆ(σ1,U·VTID)·eˆ(σ2,W·XTTD)·eˆ(σ3,Y·Zmsg) holds; otherwise outputs “reject”.

Here, let us discuss the correctness of the verifying equality. By the key refreshing procedures of those secret values employed in the proposed scheme, we have:

  • • SSK=SSK0,1·SSK0,2=⋯=SSKi−1,1·SSKi−1,2=SSKi,1·SSKi,2.

  • • TSK=TSK0,1·TSK0,2=⋯=TSKj−1,1·TSKj−1,2=TSKj,1·TSKj,2.

  • • USKID=USKID,0,1·USKID,0,2=⋯=USKID,k−1,1·USKID,k−1,2=USKID,k,1·USKID,k,2.

Hence, the equality is verified by

eˆ(g,σ4)=eˆ(g,USKID,k,2·USKID,k,1·UTKID,t·(Y·Zmsg)δ)=eˆ(g,USKID·UTKID,t·(Y·Zmsg)δ)=eˆ(g,USKID·(TSKj,2·TSKj,1·(W·XTTD)η)·(Y·Zmsg)δ)=eˆ(g,USKID·TSK·(W·XTTD)η·(Y·Zmsg)δ)=eˆ(g,(SSKi,2·SSKi,1·(U·VTID)γ)·TSK·(W·XTTD)η·(Y·Zmsg)δ)=eˆ(g,SSK·(U·VTID)γ·TSK·(W·XTTD)η·(Y·Zmsg)δ)=eˆ(g,SSK·TSK·(U·VTID)γ·(W·XTTD)η·(Y·Zmsg)δ)=eˆ(g,SSK)·eˆ(g,TSK)·eˆ(g,(U·VTID)γ)·eˆ(g,(W·XTTD)η)·eˆ(g,(Y·Zmsg)δ))=eˆ(g,SSK)·eˆ(g,TSK)·eˆ(gγ,U·VTID)·eˆ(gη,W·XTTD)·eˆ(gδ,Y·Zmsg)=eˆ(g,SSK)·eˆ(g,TSK)·eˆ(QKID,U·VTID)·eˆ(QTKID,t,W·XTTD)·eˆ(σ3,Y·Zmsg)=SPK·TPK·eˆ(σ1,U·VTID)·eˆ(σ2,W·XTTD)·eˆ(σ3,Y·Zmsg).

5Security Analysis

Let us analyse the security of our LR-RIBS scheme with CRA. By the adversary model (i.e. security game GLR-RIBS) of LR-RIBS schemes with CRA, there are two types of adversaries. In the GBG model, Theorem 1 demonstrates that our scheme is provably secure against Type I adversary. In Theorem 2, we prove that our scheme is also provably secure against Type II adversary.

Theorem 1.

In the GBG model, our LR-RIBS scheme with CRA possesses existential unforgeability under the UF-LR-RIBS-ACMA attack of Type I adversary (a curious CRA or an outsider).

Proof.

Let AI denote a Type I adversary in the security game GLR-RIBS played with a challenger C. AI is allowed to request all queries in the security game GLR-RIBS while the number of queries issued by AI is at most q times. In the GBG model introduced in earlier section, there are three group queries (oracles) QG, QT and Qp. In such a case, the challenger C also responses the queries QG, QT and Qp issued by the adversary AI, where these queries are provided in the Query phase of GLR-RIBS. For GLR-RIBS on the proposed LR-RIBS scheme with CRA, three phases (Setup, Query and Forgery) are presented as below:

  • – Setup phase: The challenger C carries out the System Setup algorithm of our scheme to generate SSK, TSK, a total number z of periods T0,T1,…,Tz and PP=(p,G,GT,eˆ,g,SPK,TPK,U,V,W,X,Y,Z). Additionally, C constructs four lists LG, LT, LK and LTK to record the related parameters and results of the queries issued by the adversary.

    • • LG and LT are, respectively, employed to record all group elements of G and GT.

      • (1) LG contains pairs of the form (ΞGm,n,r,ξGm,n,r), where ΞGm,n,r represents an element (multivariate polynomial) in G and ξGm,n,r is the associated bit string. Here, m and n, respectively, denote the query type and the n-th query, and the index r represents the r-th element of G. Initially, nine pairs (Ξg,ξGI,1,1), (ΞU,ξGI,1,2), (ΞV,ξGI,1,3), (ΞW,ξGI,1,4), (ΞX,ξGI,1,5), (ΞY,ξGI,1,6), (ΞZ,ξGI,1,7), (ΞSSK,ξGI,1,8) and (ΞTSK,ξGI,1,9) are recorded in LG.

      • (2) LT contains pairs of the form (ΞTm,n,r,ξTm,n,r), where (ΞTm,n,r represents an element (multivariate polynomial) in G/GT and ξGm,n,r is the associated bit string. The meanings of the indices m, n and r are the same with those in LG. Initially, two pairs (ΞSPK,ξTI,1,1) and (ΞTPK,ξTI,1,2) are recorded in LT, where ΞSPK=Ξg·ΞSSK and ΞTPK=Ξg·ΞTSK.

      It is worth mentioning that C employs two rules to respond the transformation request as below:

      • (1) When C receives ΞGm,n,r/ΞTm,n,r, C looks for (ΞGm,n,r,ξGm,n,r)/(ΞTm,n,r,ξTm,n,r) in LG/LT. If so, C returns the associated bit string ξGm,n,r/ξTm,n,r. Otherwise, C randomly selects a distinct bit string ξGm,n,r/ξTm,n,r and returns it. Finally, C adds (ΞGm,n,r,ξGm,n,r)/(ΞTm,n,r,ξTm,n,r) in LG/LT.

      • (2) When C receives ξGm,n,r/ξTm,n,r in LG/LT, C returns the associated multivariate polynomial ΞGm,n,r/ΞTm,n,r if it is found. Otherwise, C terminates the game.

    • • LK contains tuples of the form (ID, ΞUSKID, ΞQKID), where the multivariate polynomials ΞUSKID and ΞQKID, respectively, denote the user’s USKID and QKID in the Key extract phase.

    • • LTK contains tuples of the form (ID, Tt, ΞUTKID,t, ΞQTKID,t), where the multivariate polynomials ΞUTKID,t and ΞQTKID,t, respectively, denote the user’s UTKID,t and QTKID,t in the Time key update phase.

    Finally, C sends these public parameters Ξg, ΞU, ΞV, ΞW, ΞX, ΞY, ΞZ, ΞSPK and ΞTPK to AI.

  • – Query phase: AI can request the following queries to C adaptively.

    • • Group query QG(ξGQ,i,1,ξGQ,i,2,OP): Upon receiving the i-th QG with a pair of bit strings (ξGQ,i,1, ξGQ,i,2) and an OP operation, C carries out the following steps:

      • (1) Transform ξGQ,i,1 and ξGQ,i,2, respectively, to gain the corresponding polynomials ΞGQ,i,1 and ΞGQ,i,2 in LG.

      • (2) Compute the resulting polynomial ΞGQ,i,3=ΞGQ,i,1+ΞGQ,i,2 if OP = “multiplication”, and ΞGQ,i,3=ΞGQ,i,1−ΞGQ,i,2 if OP = “division”.

      • (3) Transform and return the bit string ξGQ,i,3 of ΞGQ,i,3.

    • • Group query QT(ξTQ,i,1,ξTQ,i,2,OP): Upon receiving the i-th QT with a pair of bit strings (ξTQ,i,1, ξTQ,i,2) and an OP operation, C carries out the similar steps with QG and returns the bit string ξTQ,i,3.

    • • Pairing query QP(ξGP,i,1,ξGP,i,2): Upon receiving the i-th QP with a pair of bit strings (ξGP,i,1, ξGP,i,2), C carries out the following steps:

      • (1) Transform ξGP,i,1 and ξGP,i,2, respectively, to gain the corresponding polynomials ΞGP,i,1 and ΞGP,i,2.

      • (2) Compute the resulting polynomial ΞTP,i,1=ΞGP,i,1·ΞGP,i,2.

      • (3) Transform and return the bit string ξTP,i,1 of ΞTP,i,1.

    • • Key extract query (ID): Upon receiving the i-th Key extract query with a user’s ID, C looks for (ID, ΞUSKID, ΞQKID) in LK. If so, C returns two corresponding bit strings ξUSKID of ΞUSKID and ξQKID of ΞQKID to AI. Otherwise, C carries out the following steps:

      • (1) Choose a new variate ΞTGKE,i,1 in G.

      • (2) Set the polynomial ΞQKID=ΞTGKE,i,1 and ΞTID=ID||ΞQKID.

      • (3) Compute the user’s secret key ΞUSKID=ΞSSK+ΞTGKE,i,1·(ΞU+ΞV·ΞTID) while adding (ID, ΞUSKID, ΞQKID) in LK.

      • (4) Transform and return two corresponding bit strings ξUSKID of ΞUSKID and ξQKID of ΞQKID to AI.

    • • Key extract leak query (i,fKE,i,hKE,i): Upon receiving the i-th Key extract leak query with two leakage functions fKE,i and hKE,i, C returns the fraction leakage content ΛfKE,i and ΛhKE,i to AI, where ΛfKE,i=fKE,i(SSKi,1,a,γ) and ΛhKE,i=hKE,i(SSKi,2,a,γ,TIKE). Note that in the i-th Key extract query, AI is allowed to issue the Key extract leak query only once.

    • • Time key update query (ID, Tt): In the j-th Time key update query with ID and Tt, C looks for (ID, Tt, ΞUTKID,t, ΞQTKID,t) in LTK. If so, C returns two corresponding bit strings ξUTKID,t and ξQTKID,t to AI. Otherwise, C carries out the following steps:

      • (1) Choose a new variate ΞTGTKU,ID,t,1 in G.

      • (2) Set the polynomial ΞQTKID,t=ΞTGTKU,ID,t,1 and ΞTTD=ID||Tt||ΞQTKID,t.

      • (3) Set the user’s time update key ΞUTKID,t=ΞTSK+ΞTGTKU,ID,t,1·(ΞW+ΞX·ΞTTDID,t) while adding (ID,Tt,ΞUTKID,t,ΞQTKID,t) in LTK.

      • (4) Transform and return two corresponding bit strings ξUTKID,t of ΞUTKID,t and ξQTKID,t of ΞQTKID,t to AI.

      Note that AI is a curious CRA or an outsider who can gain the user’s time update key by the Time key update query. Hence AI has no need to request the Time key update leak query.

    • • Singing query (ID, Tt, msg): Upon receiving the k-th Signing query of the user ID, by taking the period Tt and the message msg as input, C carries out the following steps:

      • (1) By ID, look for (ID,ΞUSKID,ΞQKID) in LK.

      • (2) By ID and Tt, look for the time update key (ID,Tt,ΞUTKID,t,ΞQTKID,t) in LTK.

      • (3) Set Ξσ1=ΞQKID and Ξσ2=ΞQTKID,t.

      • (4) Choose a new variate ΞTGS,k,1 in G and set Ξσ3=ΞTGS,k,1.

      • (5) Set Ξσ4=ΞUSKID+ΞUTKID,t+ΞTGS,i,1·(ΞY+msg·ΞZ).

      • (6) Transform (Ξσ1, Ξσ2, Ξσ3, Ξσ4) to gain the corresponding bit strings (ξσ1, ξσ2, ξσ3, ξσ4) and return them to AI.

    • • Signing leak query (ID,k,fS,k,hS,k): Upon receiving the k-th Signing query of the user ID, by taking as input two leakage functions fS,k and hS,k, C returns the fraction leakage content ΛfS,k and ΛhS,k to AI, where ΛfS,k=fS,k(USKID,k,1,UTKID,t,c,δ) and ΛhS,k=hS,k(USKID,k,2,c,TIS). Note that for the k-th Signing query, AI is allowed to issue the Signing leak query only once.

  • – Forgery phase: AI outputs (ID∗, Tt∗, msg∗, (ξσ1∗, ξσ2∗, ξσ3∗, ξσ4∗)). AI is disallowed to request the Signing query (ID∗,Tt∗,msg∗). Since AI is a curious CRA or an outsider, AI may request the Time key update query (ID∗,Tt∗), but does not request the Key extract query (ID∗). C transforms (ξσ1∗, ξσ2∗, ξσ3∗, ξσ4∗) to gain the corresponding polynomials Ξσ1∗, Ξσ2∗, Ξσ3∗, Ξσ4∗ while setting TID∗=ID∗||ξσ1∗ and TTD∗=ID∗||Tt∗||ξσ2∗. If the equality Ξg·Ξσ4∗=ΞSPK+ΞkTPK+Ξσ1∗·(ΞU+TID∗·ΞV)+Ξσ2∗·(ΞW+TTD∗·ΞX)+Ξσ3∗·(ΞY+msg∗·ΞZ) holds, we say that AI wins the game GLR-RIBS.

For evaluating the probability that AI wins GLR-RIBS, let us first compute the number of group elements and the maximal degrees of polynomials in LG/LT.

  • (1) The number of group elements in LG and LT is at most 6q by the following evaluations:

    • • In the Setup phase, nine group elements are initially added in LG and two group elements are initially added in LT.

    • • For each QG, QT and QP query, three new group elements could be generated and added in LG or LT.

    • • In the Key extract query for a new user, two new group elements are generated and added in LG.

    • • In the Time key update query for a user at a period, two new group elements are generated and added in LG.

    • • In each Signing query, six new group elements are added in LG.

    The total number of QG, QT and QP queries is denoted by qO. Additionally, qKE, qTKU and qS, respectively, represent the numbers of the Key extract query, Time key update query and Signing query. In the Query phase, AI is allowed to request the queries at most q times. Therefore, we have |LG|+|LT|≦11+3qO+2qKE+2qTKU+6qS≦6q.

  • (2) The maximal degree of polynomials in LG is 3 because of the following reasons:

    • • In the Setup phase, since these polynomials Ξg, ΞU, ΞV, ΞW, ΞX, ΞY, ΞZ, ΞSSK and ΞTSK are new variates, they have degree 1. ΞSPK and ΞTPK have degree 2.

    • • In QG, ΞGQ,i,3 has the maximal degree of ΞGQ,i,1 or ΞGQ,i,2.

    • • In the Key extract query, ΞTGKE,i,1, ΞTID and ΞUSKID have degrees 1, 1 and 3, respectively.

    • • In the Time key update query, ΞQTKID,t, ΞTTD and ΞUTKID,t have degrees 1, 1 and 3, respectively.

    • • In the Signing query, ΞQKID and Ξσ4 have degrees 1 and 3, respectively.

  • (3) The maximal degree of polynomials in LT is 6 because of the following reasons:

    • • In the Setup phase, both ΞSPK and ΞTPK have degree 2.

    • • In QT, ΞTQ,i,3 has the maximal degree of ΞTQ,i,1 or ΞTQ,i,2.

    • • In QP, the maximal degree of ΞTP,i,1 in LT is 6 because the maximal degree of polynomials in LG is 3 and ΞTP,i,1=ΞGP,i,1·ΞGP,i,2.

If one of the following two cases occurs, we say that AI wins GLR-RIBS:

Case 1.

AI discovers a collision of group elements in LG or LT. Let n denote the total number of all variates in LG and LT. Now, C selects n random values vi∈Zp∗ for i=1,…,n. In this case, there exist two polynomials ΞGi and ΞGj, both in LG or both in LT, that satisfy ΞGi(v1,v2,…, vn) = ΞGj(v1,v2,…,vn).

Case 2.

AI outputs a correct signature (ID∗, Tt∗, msg∗, (ξσ1∗, ξσ2∗, ξσ3∗, ξσ4∗)) that satisfies Ξg·Ξσ4∗=ΞSPK+ΞTPK+Ξσ1∗·(ΞU+TID∗·ΞV)+Ξσ2∗·(ΞW+TTD∗·ΞX)+Ξσ3∗·(ΞY+msg∗·ΞZ), where TID∗=ID∗||ξσ1∗ and TTD∗=ID∗||Tt||ξσ2∗.

Let us evaluate AI’s advantage of winning GLR-RIBS without requesting Key extract leak query and Signing leak query. Note that AI is a curious CRA or an outsider who can gain the user’s time update key UTKID,t by the Time key update query. Hence, AI has no need to request the Time key update leak query. Subsequently, AI’s advantage in GLR-RIBS with requesting two kinds of leak queries (Key extract leak query and Signing leak query) is evaluated.

∙ Without requesting two kinds of leak queries: Under this circumstance, AI may request all the queries in GLR-RIBS except for the Key extract leak query and Signing leak query. In the following, let us discuss the probability that AI wins GLR-RIBS without requesting two kinds of leak queries.

Case 1.

The probability that AI discovers a collision of group elements in LG or LT is evaluated. Let ΞGi and ΞGj denote two distinct polynomials in LG. The collision probability is the probability that ΞGC=ΞGi−ΞGj is a zero polynomial, namely, ΞGC(v1,v2,…,vn)=0. By Lemma 2, the probability of ΞGC(v1,v2,…,vn)=0 is at most 3/p because there is no fraction leakage content (λ=0) and the maximal polynomial degree in LG is 3. We have that the probability of discovering a collision in LG is (3/p)|LG|2 since there are |LG|2 distinct pairs (ΞGi, ΞGj) in LG. By similar arguments, the probability that AI discovers a collision in LT is ((6/p)|LT|2. Moreover, the total number of group elements in LG and LT is at most 6q, namely, |LG|+|LT|≦6q. Then the probability of Case 1, denoted by Pr[Case 1], satisfies the inequality

Pr[Case 1]≦(3/p)|LG|2+(6/p)|LT|2≦(6/p)(|LG|+|LT|)2≦216q2/p.

Case 2.

Let us evaluate the probability that AI outputs a signature (ID∗, Tt∗, msg∗, (ξσ1∗, ξσ2∗, ξσ3∗, ξσ4∗)) that satisfies Ξf=ΞSPK+ΞTPK+Ξσ1∗·(ΞU+TID∗·ΞV)+Ξσ2∗·(ΞW+TTD∗·ΞX)+Ξσ3∗·(ΞY+msg∗·ΞZ)−Ξg·Ξσ∗4=0. The probability of outputting a correct signature is 5/p because the degree of Ξf is at most 5.

Let PrA−I−W denote the advantage that AI wins GLR-RIBS without requesting two kinds of leak queries. By Cases 1 and 2, we have the inequality

AdvA−I−W≦Pr[Case 1]+Pr[Case 2]≦216q2/p+5/p≦O(q2/p).

∙ With requesting two kinds of leak queries: Under this circumstance, AI is allowed to issue all the leak queries in GLR-RIBS. In the i-th key extract leak query with |fKE,i|≦λ and |hEK,i|≦λ, AI gains the fraction leakage content ΛfKE,i=fKE,i(SSKi,1,a,γ) and ΛhKE,i=hKE,i(SSKi,2,a,γ,TIKE) discussed as below.

  • ■ a, γ: In each Key extract query, a and γ are random values. Therefore, the leakage of a or γ is of no help to learn the system secret key SSK.

  • ■ (SSKi,1, SSKi,2): We have SSK = SSKi−1,1·SSKi−1,1=SSKi,1·SSKi,2. By the multiplicative blinding technique, the fraction leakage content of SSKi−1,1/SSKi−1,2 is independent of that of SSKi,1/SSKi,2. Hence, AI gains at most λ bits of SSK.

  • ■ TIKE: The temporary value TIKE is employed to compute the user’s secret key USKID. Since AI can obtain the entire USKID except for ID∗, TIKE is helpless for AI.

In the k-th Signing query of the user ID, by taking as input two leakage functions fS,k and hS,k with |fS,k|≦λ and |hS,k|≦λ, AI gains the fraction leakage content ΛfS,k = fS,k(USKID,k,1,UTKID,t,c,δ) and ΛhS,k=hS,k(USKID,k,2,c,TIS) discussed as below.

  • ■ c,δ: In each signing query, c and δ are random values. Therefore, the leakage about c and δ is of no help to learn the user’s secret key USKID.

  • ■ (USKID,k,1, USKID,k,2): We have USKID=USKID,k−1,1·USKID,k−1,2=USKID,k,1·USKID,k,2. By the multiplicative blinding technique, the fraction leakage content of USKID,k−1,1/USKID,k−1,2 is independent of that of USKID,k,1/USKID,k,2. Hence, AI gains at most λ bits of USKID.

  • ■ TIS: The temporary value TIS is used to generate the signature σ4. Since AI can obtain the entire σ4 by the Sign query, TIS is helpless for AI.

Let AdvA−I be the advantage that AI wins GLR-RIBS with requesting the Key extract leak query and Signing leak query. For forging a correct signature, let us discuss the useful leakage content of the target user’s secret USK and the system secret key SSK that consists of three events as below:

  • (1) ESSK denotes the event that AI knows the whole SSK by ΛfKE,i and ΛhKE,i, and its complement event is denoted by ESSK‾.

  • (2) EUSK denotes the event that AI knows the whole USKID by ΛfS,k and ΛhS,k, and its complement event is denoted by EUSK‾.

  • (3) ESF denotes the event that AI forges a correct signature.

Hence, the advantage AdvA−I is Pr[ESF] and satisfies the inequality
AdvA−I=Pr[ESF]=Pr[ESF∧(ESSK∨EUSK)]+Pr[ESF∧(ESSK‾∧EUSK‾)]=Pr[ESF∧ESSK]+Pr[ESF∧EUSK]+Pr[ESF∧ESSK‾∧EUSK‾]≦Pr[ESSK]+Pr[ESF∧EUSK]+Pr[ESF∧ESSK‾∧EUSK‾].

In our LR-RIBS scheme with CRA, the PKG employed SSK and a user’s information ID||QKID to generate the user’s secret key USKID by using the signature scheme in Galindo and Virek (2013). By Lemma 5 in Galindo and Virek (2013), we have Pr[ESSK] ≦ O((q2/p)·22λ). Next, AI may gain fractional content of USKID by the Signing leak query. Hence, Pr[ESF∧EUSK] is the probability that AI can get fractional content of USKID by ΛfS,k and ΛhS,k. Thus, we can gain the probability Pr[ESF∧EUSK] ≦ O((q2/p)·22λ). Finally, the event ESSK‾∧EUSK‾ is that AI can gain fractional content of (USKID,k,1, USKID,k,2) by ΛfS,k and ΛhS,k. In such a case, AI can gain at most λ bits about USKID, and so we have Pr[ESF∧ESSK‾∧EUSK‾] ≦ O((q2/p)·2λ). According to the events discussed above, we reach the inequality

AdvA−I=Pr[ESF]≦Pr[ESSK]+Pr[ESF∧EUSK]+Pr[ESF∧(ESSK‾∧EUSK‾)]≦O((q2/p)∗22λ)+O((q2/p)∗22λ)+O((q2/p)∗2λ).

Therefore, AdvA−I≦O((q2/p)∗22λ). Finally, by Lemma 2, AdvA−I is negligible if λ<logp−ω(loglogp).  □

Theorem 2.

In the GBG model, our LR-RIBS scheme with CRA possesses existential unforgeability under the UF-LR-RIBS-ACMA attack of Type II adversary (a revoked user).

Proof.

Let AII denote a Type II adversary in the security game GLR-RIBS played with a challenger C. Hence, AII may acquire the user’s secret key USKID and time update key UTKID,t for any ID at any period Tt, except for the target identity ID∗ at period Tt∗. For GLR-RIBS on the proposed LR-RIBS scheme with CRA, three phases (Setup, Query and Forgery) are described as below:

  • – Setup phase: The phase is the same with that of the proof in Theorem 1.

  • – Query phase: AII is allowed to issue the queries at most q times adaptively as below.

    • • QG, QT, QP, Key extract query, Time key update query, Singing query and Signing leak query are identical to these queries in Theorem 1. Note that AII is a revoked user who may acquire the user’s secret key USKID for any ID. Hence, AII has no need to request the Key extract leak query.

    • • Time key update leak query (j,fTKU,j,hTKU,j): Upon receiving the j-th Key Time key update leak query with fTKU,j and hTKU,j, C returns the fraction leakage content ΛfTKU,j=fTKU,j(TSKj,1,b,η) and ΛhTKU,j=hTKU,j(TSKj,2,b,η,TITKU) to AII. Note that for the j-th Time key update query, AII is allowed to request the Time key update leak query only once.

  • – Forgery phase: AII outputs (ID∗, Tt∗, msg∗, (ξσ1∗, ξσ2∗, ξσ3∗, ξσ4∗)). AII is a revoked user who may request the Key extract query (ID∗) to obtain USKID∗, but does not request the Time key update query (ID∗, Tt∗). C first transforms (ξσ1∗, ξσ2∗, ξσ3∗, ξσ4∗) to gain the corresponding polynomials Ξσ1∗, Ξσ2∗, Ξσ3∗ and Ξσ4∗. C sets TID∗=ID∗||ξσ1∗ and TTD∗=ID∗||Tt∗||ξσ2∗. If the equality Ξg·Ξσ4∗=ΞSPK+ΞTPK+Ξσ1∗·(ΞU+TID∗·ΞV)+Ξσ2∗·(ΞW+TTD∗·ΞX)+Ξσ3∗·(ΞY+msg∗·ΞZ) holds, we say that AII wins GLR-RIBS.

By the same arguments in Theorem 1, the total number of group elements in LG and LT is at most 6q, namely, |LG|+|LT|≦6q. The maximal polynomial degrees in LG and LT are 3 and 6, respectively. Let us evaluate AII’s advantage winning GLR-RIBS without requesting Time key update leak query and Signing leak query. Subsequently, AII’s advantage in GLR-RIBS with requesting two kinds of leak queries is evaluated.

∙ Without requesting two kinds of leak queries: Let PrA−II−W denote the advantage that AII wins GLR-RIBS without requesting two kinds of leak queries. By the similar discussions as Theorem 1, we have the inequality

AdvA−II−W≦Pr[Case 1]+Pr[Case 2]≦216q2/p+5/p≦O(q2/p).

Hence, AdvA−II−W is negligible if q=poly(logp).

∙ With requesting two kinds of leak queries: Under this circumstance, AII is allowed to request all queries in GLR-RIBS. For the j-th time key update leak query with fTKU,j and hTKU,j that satisfy |fTKU,j|≦λ and |hTKU,j|≦λ, AII can gain the fraction leakage content ΛfTKU,j=fTKU,j(TSKj,1,b,η) and ΛhTKU,j=hTKU,j(TSKj,2,b,η,TITKU) discussed below:

  • ■ b,η: In each time key update query, b and η are random values. Therefore, the leakage about b and η is of no help to learn the time secret key TSK.

  • ■ (TSKj,1,TSKj,2): For the time secret key TSK, we have TSK=TSKj−1,1·TSKj−1,1=TSKj,1·TSKj,2. By the multiplicative blinding technique, the fraction leakage content of TSKj−1,1/TSKj−1,2 is independent of that of TSKj,1/TSKj,2. Thus, AII gains at most λ bits of TSK.

  • ■ TITKU: The temporary value TITKU is employed to generate user’s time key UTKID,t. Since AII can obtain the whole UTKID,t by the time key update query, TITKU is helpless for AII.

For the k-th Signing leak query of the user ID, by taking as input two leakage functions fS,k and hS,k such that |fS,k|≦λ and |hS,k|≦λ, AII gains the fraction leakage content ΛfS,k=fS,k(USKID,k,1,UTKID,t,c,δ) and ΛhS,k=hS,k(USKID,k,2,c,TIS). Indeed, a revoked user has possessed the user secret key USKID. In particular, since the user’s time update key UTKID,t is not generated, the Signing leak query does not leak any content.

Let AdvA−II be the advantage that AII wins GLR-RIBS with requesting the time key update query. Since AII simulates a revoked user, she/he can obtain the target user’s secret key USKID. For forging a correct signature, let us discuss the helpful leakage content about the target user’s time key UTKID,t that consists of two events as below:

  • (1) ETSK denotes the event that AII gains the whole TSK by ΛfTKU,j and ΛhTKU,j, and ETSK‾ denotes the complement event of ETSK.

  • (2) ESF denotes the event that AII forges a correct signature.

Hence, the advantage AdvA−II is Pr[ESF] and satisfies the inequality
AdvA−II=Pr[ESF]=Pr[ESF∧ETSK]+Pr[ESF∧ETSK‾]≦Pr[ETSK]+Pr[ESF∧ETSK‾].

In the Time key update phase of our scheme, the CRA employed the time secret key TSK and a user’s content TTD=ID||Tt||QTKID,t to generate the user’s secret key UTKID,t by using the signature scheme in Galindo and Virek (2013). The probability Pr[ETSK] is identical to Pr[ESSK] in Theorem 1 so that we have Pr[ETSK]≦O((q2/p)∗22λ) Next, the event is that AII can gain at most λ bits of (TSKj,1, TSKj,2), we have Pr[ESF∧ETSK‾]≦O((q2/p)∗2λ). According to the events discussed above, we reach the inequality

AdvA−II≦Pr[ETSK]+Pr[ESF∧ETSK]≦O((q2/p)∗22λ)+O((q2/p)∗2λ).

Therefore, AdvA−II≦O((q2/p)∗22λ). Finally, by Lemma 2, AdvA−II is negligible if λ<logp−ω(loglogp).  □

6Performance Comparisons

Here, we compare the performance between previously proposed RIBS schemes (Tsai et al., 2013b; Jia et al., 2017) and our LR-RIBS scheme with CRA. In the following, four notations are defined respectively to represent four time-consuming operation costs of bilinear groups:

  • • Tbp: The executing cost of a bilinear map eˆ:G×G→GT.

  • • Tme: The executing cost of a scalar multiplication on an additive cycle group G or an exponentiation operation on a multiplicative cycle group G.

  • • Tex: The executing cost of an exponentiation operation on a multiplicative cycle group GT.

  • • Tmh: The executing cost of a map-to-point hash function operation in G.

Table 1

Executing costs (in milliseconds) of several operations on a PC and a smartphone.

PC (2.4 GHz processor)Smartphone (1 GHz processor)
Tbp7.5260
Tme2.834
Tex2.121
Tmh≅2.8≅34
Table 2

Performance comparisons between our LR-RIBS scheme with CRA and the previously proposed RIBS schemes.

Tsai et al.’s RIBS scheme (Tsai et al., 2013b)Jia et al.’s RIBS scheme (Jia et al., 2017)Our LR-RIBS scheme (Tsai et al., 2013b)
Resisting side-channel attacksNoNoYes
Overall unbounded leakage propertyNoNoYes
Outsourced revocation authorityNoYesYes
Key extract3TmeTme+Tmh7Tme
(Executing cost on PC)(8.4 ms)(5.6 ms)(19.6 ms)
Time key update3TmeTme+Tmh5Tme
(Executing cost on PC)(8.4 ms)(5.6 ms)(14 ms)
Signing2Tme2Tme+Tex5Tme
(Executing cost on Smartphone)(68 ms)(89 ms)(170 ms)
Verifying5Tbp2Tex+2Tmh+3Tbp3Tme+4Tbp
(Executing cost on Smartphone)(1300 ms)(890 ms)(1142 ms)

Indeed, the cost of the operation (additive/multiplicative) on an (additive/multiplicative) cyclic group G is smaller than Tbp, Tme, Tex and Tmh (Scott, 2011; Lynn, 2015), and so is negligible. The simulation experiences (Lynn, 2015) on a PC and a smartphone are employed as the benchmark costs of Tpb, Tme, Tex and Tmh. The simulation platform on both the PKG and CRA sides is an Intel Core-2 Quad Q6600 PC with 2.4 GHz processor and Ubuntu OS. Meanwhile, the simulation platform on the user side is a HTC Desire HD-A9191 smartphone with Qualcomm 1 GHz processor and Android 2.2 OS. Additionally, under the same security level with 1024-bit RSA system, an elliptic curve over a finite field E(Fq) are employed for bilinear pairing groups with a prime order p, where p and q are 160 and is 512 bits, respectively. Table 1 lists the executing cost (in milliseconds) of Tpb, Tme, Tex and Tmh on both a PC and a smartphone in Lynn (2015).

Table 2 lists the performance comparisons between two previously proposed RIBS schemes (Tsai et al., 2013b; Jia et al., 2017) and our LR-RIBS scheme with CRA in terms of resisting side-channel attacks, overall unbounded leakage property, outsourced revocation authority and the computation costs of four phases. In Tsai et al. (2013b), the PKG is responsible to carry out both the Key extract and Time key update phases. On the other hand, the scheme in Jia et al. (2017) and our scheme employ a CRA to outsource the functionality of user revocation. Note that the executing costs of both the Key extract and Time key update phases are measured under a PC while the executing costs of both the Signing and Verifying phases are measured under a smartphone.

By Table 2, although performing worse than the other two schemes in the computation costs, our scheme is still well suited for a smartphone with limited computing capability. We should emphasize that our scheme can resist side-channel attacks with overall unbounded leakage property, but the other two cannot.

7Conclusions

In the continual leakage model, we have defined a novel adversary model of LR-RIBS schemes with CRA. In the adversary model, Type I adversary (a curious CRA or an outsider) is allowed to extract fractional content of the target signer’s secret key and the PKG’s system secret key. Also, Type II adversary (a revoked user) is allowed to extract fractional content of the CRA’s time secret key. We have proposed the first LR-RIBS scheme with CRA and it possesses the overall unbounded leakage property. In the GBG model, security analysis demonstrated that the proposed LR-RIBS scheme with CRA is secure against Types I and II adversaries under the continual leakage model. Performance comparisons demonstrated that the proposed LR-RIBS scheme with CRA requires some additional computation costs than the previously proposed RIBS schemes. This point is that our scheme not only can resist side-channel attacks, but also is still suitable for mobile devices with limited computing capability.

References

1 

Alwen, J., Dodis, Y., Wichs, D. ((2009) ). Leakage-resilient public-key cryptography in the bounded-retrieval model. In: Advances in Cryptology – CRYPTO, LNCS, Vol. 5677: , pp. 36–54.

2 

Biham, E., Carmeli, Y., Shamir, A. ((2008) ). Bug attacks. In: Advances in Cryptology – CRYPTO, LNCS, Vol. 5157: , pp. 221–240.

3 

Boneh, D., Franklin, M. ((2001) ). Identity-based encryption from the Weil pairing. In: Advances in Cryptology – CRYPTO, LNCS, Vol. 2139: , pp. 213–229.

4 

Boneh, D., Demillo, R.A., Lipton, R.J. ((1997) ). On the importance of checking cryptographic protocols for faults. In: Advances in Cryptology – EUROCRYPT, LNCS, Vol. 1233: , pp. 37–51.

5 

Boneh, D., Lynn, B., Shacham, H. ((2001) ). Short signatures from the Weil pairing. In: Advances in Cryptology – ASIACRYPT, LNCS, Vol. 2248: , pp. 514–532.

6 

Boneh, D., Boyen, X., Goh, E.J. ((2005) ). Hierarchical identity-based encryption with constant size ciphertext. In: Advances in Cryptology – EUROCRYPT, LNCS, Vol. 3494: , pp. 440–456.

7 

Brakerski, Z., Kalai, Y.T., Katz, J., Vaikuntanathan, V. ((2010) ). Cryptography resilient to continual memory leakage. In: Proceedings of 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 501–510.

8 

Brumley, D., Boneh, D. ((2005) ). Remote timing attacks are practical. Computer Networks, 48: (5), 701–716.

9 

Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A. ((2008) ). Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing, 38: (1), 97–139.

10 

Galindo, D., Virek, S. ((2013) ). A practical leakage-resilient signature scheme in the generic group model. In: Proc. SAC’12, LNCS, Vol. 7707: , pp. 50–65.

11 

Galindo, D., Grobschadl, J., Liu, Z., Vadnala, P.K., Vivek, S. ((2016) ). Implementation of a leakage-resilient ElGamal key encapsulation mechanism. Journal of Cryptographic Engineering, 6: (3), 229–238.

12 

Housley, R., Polk, W., Ford, W., Solo, D. (2002). Internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile. IETF, RFC 3280.

13 

Hung, Y.-H., Tseng, Y.-M., Huang, S.-S. ((2017) ). Revocable ID-based signature with short size over lattices. Security and Communication Networks, 2017: . Article ID 7571201.

14 

Jia, X., He, D., Zeadally, S., Li, L. ((2017) ). Efficient revocable ID-based signature with cloud revocation server. IEEE Access, 5: , 2945–2954.

15 

Kiltz, E., Pietrzak, K. ((2010) ). Leakage resilient elgamal encryption. In: Advances in Cryptology – ASIACRYPT, LNCS, Vol. 6477: , pp. 595–612.

16 

Kocher, P., Jaffe, J., Jun, B. ((1999) ). Differential power analysis. In: Advances in Cryptology – CRYPTO, LNCS, Vol. 1666: , pp. 388–397.

17 

Li, J., Li, J., Chen, X., Jia, C., Lou, W. ((2015) ). Identity-based encryption with outsourced revocation in cloud computing. IEEE Transactions Computers, 64: (2), 425–437.

18 

Lynn, B. (2015). Java Pairing Based Cryptography Library (JPBC). [Online] Available: http://gas.dia.unisa.it/projects/jpbc/benchmark.html.

19 

Scott, M. ((2011) ). On the efficient implementation of pairing-based protocols. In: Proc. Cryptography and Coding, Vol. 7089. pp. 296–308.

20 

Shamir, A. ((1984) ). Identity-based cryptosystems and signature schemes. In: Advances in Cryptology – CRYPTO, LNCS, Vol. 196: , pp. 47–53.

21 

Shoup, V. ((1997) ). Lower bounds for discrete logarithms and related problems. In: Advances in Cryptology – EUROCRYPT, LNCS, Vol. 1233: , pp. 256–266.

22 

Tang, F., Li, H., Niu, Q., Liang, B. ((2014) ). Efficient leakage-resilient signature schemes in the generic bilinear group model. In: Proc. Information Security Practice and Experience, LNCS, Vol. 8434: , pp. 418–432.

23 

Tsai, T.-T., Tseng, Y.-M., Wu, T.-Y. ((2012) ). A fully secure revocable ID-based encryption in the standard model. Informatica, 23: (3), 481–499.

24 

Tsai, T.-T., Tseng, Y.-M., Wu, T.-Y. ((2013) a). Efficient revocable multi-receiver ID-based encryption. Information Technology and Control, 42: (2), 159–169.

25 

Tsai, T.-T., Tseng, Y.-M., Wu, T.-Y. ((2013) b). Provably secure revocable ID-based signature in the standard model. Security and Communication Networks, 6: (10), 1250–1260.

26 

Tseng, Y.-M., Tsai, T.-T. ((2012) ). Efficient revocable ID-based encryption with a public channel. Computer Journal, 55: (4), 475–486.

27 

Tseng, Y.-M., Tsai, T.-T., Huang, S.-S., Huang, C.-P. ((2018) ). Identity-based encryption with cloud revocation authority and its applications. IEEE Transactions on Cloud Computing, 6: (4), 1041–1053.

28 

Wu, J.-D., Tseng, Y.-M., Huang, S.-S. ((2016) ). Leakage-resilient ID-based signature scheme in the generic bilinear group model. Security and Communication Networks, 9: (17), 3987–4001.

29 

Wu, J.-D., Tseng, Y.-M., Huang, S.-S., Chou, W.C. ((2018) ). Leakage-resilient certificateless key encapsulation scheme. Informatica, 29: (1), 125–155.

30 

Wu, J.-D., Tseng, Y.-M., Huang, S.-S., Tsai, T.-T. ((2019) ). Leakage-resilient certificate-based signature resistant to side-channel attacks. IEEE Access, 7: (1), 19041–19053.

31 

Yuen, T.-H., Chow, S.S.M., Zhang, Y., Yiu, S.-M. ((2012) ). Identity-based encryption resilient to continual auxiliary leakage. In: Advances in Cryptology – EUROCRYPT, LNCS, Vol. 7237: , pp. 117–134.

Show more