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

Fully Continuous Leakage-Resilient Certificate-Based Signcryption Scheme for Mobile Communications

Article type: Research Article

Authors: Tseng, Yuh-Min1; ∗ | Tsai, Tung-Tso2 | Huang, Sen-Shan1

Affiliations: [1] Department of Mathematics, National Changhua University of Education, Changhua 500, Taiwan | [2] Department of Computer Science and Engineering, National Taiwan Ocean University, Keelung 202, Taiwan

Correspondence: [∗] Corresponding author.

Keywords: leakage attacks, signcryption, certificate-based public key system, leakage resilience

DOI: 10.15388/22-INFOR506

Journal: Informatica, vol. 34, no. 1, pp. 199-222, 2023

Received September 2022
|
Accepted December 2022
|
Published: 2023
Get PDF open access

Abstract

Due to the popularity of mobile communication, many computing devices are exposed to remote environments without physical protection so that these devices easily suffer from leakage attacks (e.g., side-channel attacks). Under such leakage attacks, when a computing device performs some cryptographic algorithm, an adversary may acquire partial bits of secret keys participated in this cryptographic algorithm. To resist leakage attacks, researchers offer leakage-resilient cryptography as a solution. A signcryption scheme combines signing and encrypting processes to simultaneously provide both authentication and confidentiality, which is an important cryptographic primitive. Indeed, many leakage-resilient signcryption schemes under various public key system (PKS) settings were proposed. Unfortunately, these schemes still have two shortcomings, namely, bounded leakage resilience and conditionally continuous leakage resilience. In this paper, a “fully” continuous leakage-resilient certificate-based signcryption (FCLR-CBSC) scheme is proposed. Security analysis is formally proved to show that our scheme possesses both authentication and confidentiality against two types of adversaries in the certificate-based PKS setting. Performance analysis and simulation experience show that our scheme is suited to run on both a PC and a mobile device.

1Introduction

In the traditional public key system (PKS) setting (Rivest et al., 1978), a public-key infrastructure (PKI) needs to be established to create and manage each member’s certificate, which is used to validate the member’s public key. To lighten the PKI establishment cost, Boneh and Franklin (2001) presented a practical identity-based PKS (ID-PKS) setting with bilinear pairings, in which a member’s identity is regarded as the member’s public key and no certificate is needed. However, the ID-PKS setting suffers from a constitutional key escrow problem. In 2003, the certificateless PKS (CL-PKS) (Al-Riyami and Paterson, 2003) and the certificate-based PKS (CB-PKS) (Gentry, 2003) settings were constructed respectively to clear up the key escrow problem. Afterwards, the research of various cryptographic mechanisms under the CB-PKS and the CL-PKS settings have been thoroughly studied.

Typically, the security of these cryptographic mechanisms under these PKS settings mentioned above is dependent on the security of secret keys participated in these cryptographic mechanisms, and so these secret keys must be entirely concealed to adversaries. However, due to the popularity of mobile communication, many computing devices are exposed to remote environments without physical protection so that these devices easily suffer from leakage attacks (e.g. side-channel attacks) (Kocher et al., 1999; Brumley and Boneh, 2005; Biham et al., 2008). By leakage attacks, when a computing device performs some cryptographic algorithm, an adversary may acquire partial bits of secret keys participated in this algorithm. To resist such leakage attacks, researchers offer leakage-resilient cryptography as a solution. In the past, numerous leakage-resilient signature (LRS) schemes (Galindo and Virek, 2013; Wu et al., 2019; Tseng et al., 2020; Wu et al., 2020b), leakage-resilient encryption (LRE) schemes (Kiltz and Pietrzak, 2010; Galindo et al., 2016; Wu et al., 2018, 2020a; Tseng et al., 2022), and leakage-resilient authenticated key agreement protocols (Tseng et al., 2021; Peng et al., 2021; Tsai et al., 2022) under various PKS settings have been published in the literature.

For reducing communication and computation costs, a signcryption scheme (Zheng, 1997) combines signing and encrypting processes in a mechanism to simultaneously provide both authentication and confidentiality, which is an important cryptographic primitive. In the past, some signcryption schemes under various PKS settings have been proposed that include PKI-based signcryption (PKI-SC) schemes (Ullah et al., 2020; Ali et al., 2020), certificateless signcryption (CLSC) schemes (Khan et al., 2020; Wu et al., 2022) and certificate-based signcryption (CBSC) schemes (Ullah et al., 2019; Hussain et al., 2020). Nevertheless, these signcryption schemes mentioned above are unable to resist leakage attacks. Indeed, several leakage-resilient (LR) signcryption schemes under the CL-PKS and the CB-PKS settings have been proposed. However, these LR signcryption schemes still have two shortcomings, that is, bounded leakage resilience and conditionally continuous leakage resilience, which will be discussed later. Hence, in this paper, we aim to propose a “fully” continuous leakage-resilient certificate-based signcryption (FCLR-CBSC) scheme to remove the shortcomings of the previously proposed schemes.

1.1Related Work

Here, let’s introduce two types of leakage attack models, that is, bounded and continuous (i.e. unbounded). The bounded leakage attack model has an impractical property that entire leaked bits of a secret key are bounded in a fractional proportion of the secret key during the usage life of an LR algorithm (Alwen et al., 2009; Katz and Vaikuntanathan, 2009). In such a case, when the leaked bit number of the secret key exceeds the proportion, the secret key can no longer be used. Contrarily, the continuous leakage attack model allows adversaries to continuously obtain a secret key’s partial bits in each usage of the secret key during the usage life of the associated LR algorithm. Therefore, an LR cryptographic scheme against continuous leakage attacks has the unbounded leakage property and is more suitable for real practical environments (Kiltz and Pietrzak, 2010; Galindo and Virek, 2013).

As mentioned earlier, several LR signcryption schemes under the CL-PKS and the CB-PKS settings have been proposed to remove the key escrow problem. Here, let’s review these LR certificateless signcryption (LR-CLSC) (Zhou et al., 2016; Yang et al., 2019) and LR certificate-based signcryption (LR-CBSC) (Zhou et al., 2021) schemes. Zhou et al. (2016) adopted a non-interactive zero-knowledge mechanism to propose an LR-CLSC scheme. As we know, the usage of the non-interactive zero-knowledge mechanism is very time-consuming so that Zhou et al.’s scheme is unsuitable for mobile devices. Subsequently, Yang et al. (2019) presented an improvement on Zhou et al.’s scheme to remove the usage of the non-interactive zero-knowledge mechanism to achieve better performance. However, both schemes (Zhou et al., 2016; Yang et al., 2019) are only secure against bounded leakage attacks and cannot resist the attacks of adversaries with continuous leakage abilities.

To achieve continuous leakage-resilient property, Zhou et al. (2021) first presented a bounded LR-CBSC scheme and adopted the secret key update method proposed by Dodis et al. (2010) to obtain a “conditionally” continuous LR-CBSC (CCLR-CBSC) scheme. That is, by Dodis et al.’s secret key update method, a continuous version is constructed from the associated bounded LR cryptographic scheme. However, Kiltz and Pietrzak (2010) have previously shown that Dodis et al.’s secret key update method has a shortcoming in the sense that the key update process itself does not allow adversaries to leak any bits of the secret key even if the secret key actually participates in the computation of the key update method. Therefore, Zhou et al.’s scheme only possesses the “conditionally” continuous leakage-resilient property.

1.2Contributions

As mentioned earlier, the LR-CLSC schemes in Zhou et al. (2016), Yang et al. (2019) are only secure against bounded leakage attacks and the CCLR-CBSC scheme in Zhou et al. (2021) only possesses the “conditionally” continuous leakage-resilient property. In this paper, a “fully” CLR-CBSC (FCLR-CBSC) scheme is proposed. In our FCLR-CBSC scheme, there are two roles, namely, a trusted certificate authority (CA) and members. A member IDm sets the associated member secret key MSKm. The CA uses its own secret key CSK to compute the member’s certificate CTFm using the member IDm’s identity information and public key, and returns it back to the member IDm. By combining the adversary models of both the LR certificate-based signature (LR-CBS) scheme (Wu et al., 2019) and the LR certificate-based encryption (LR-CBE) scheme (Wu et al., 2020a), we define the adversary model of the FCLR-CBSC scheme. In this adversary model, there are two types of adversaries that include an uncertified member and the honest-but-curious CA.

Table 1

Comparisons between the related schemes and our scheme.

SchemeZhou et al.’s LR-CLSC scheme (2016)Yang et al.’s LR-CLSC scheme (2019)Zhou et al.’s CCLR-CBSC scheme (2021)Our proposed FCLR-CBSC scheme
PKS settingCL-PKSCL-PKSCB-PKSCB-PKS
Leakage of a member’s secret keyAllowedAllowedAllowedAllowed
Leakage of the system’s secret keyNot allowedNot allowedAllowedAllowed
Leakage modelBoundedBoundedConditionally continuousFully continuous

To realize the “fully” continuous leakage-resilient property, our scheme adopts the key update method proposed by Kiltz and Pietrzak (2010) to update the member IDm’s secret key MSKm and certificate CTFm participated in both the signcryption and the unsigncryption algorithms, and the CA’s secret key CSK participated in the certificate generation algorithm. In the process of the key update method, these secret keys or certificates are allowed to be leaked by an adversary so that our scheme has the fully continuous leakage-resilient property. Table 1 lists the comparisons between the LR-CLSC schemes in Zhou et al. (2016), Yang et al. (2019), the CCLR-CBSC scheme in Zhou et al. (2021) and our FCLR-CBSC scheme in terms of PKS setting, leakage of a member’s secret key, leakage of the system’s secret key and leakage model. It is obvious that only our scheme achieves the fully continuous leakage-resilient property and tolerates the leakages of both the system’s secret key and a member’s secret key. Finally, we employ the security proving method of the generic bilinear group (GBG) model (Boneh et al., 2005) to show that our scheme possesses both authentication and confidentiality against two types of adversaries in the CB-PKS setting. Also, performance analysis and simulation experience demonstrate that our scheme is suited to run on both a PC and a mobile device.

1.3Paper Structure

The remainder of this paper comprises six parts. Four preliminaries are introduced in Section 2. We define a new framework and security model of FCLR-CBSC schemes in Section 3. In Section 4, our FCLR-CBSC scheme is demonstrated. The security analysis of our scheme is given in Section 5. Performance analysis and conclusions are given in Sections 6 and 7, respectively.

2Preliminaries

2.1Bilinear Pairing Set

Let {g1,g2,G1,G2,p,eˆ} be a bilinear pairing set. The reader can refer to Boneh and Franklin (2001) for the parameter selections of the bilinear pairing set. g1 and g2 are, respectively, generators of the multiplicative groups G1 and G2 with the same prime order p. The bilinear pairing function eˆ:G1×G1→G2 satisfies three properties as presented below:

  • – Bilinear property: eˆ(g1x,g1y)=eˆ(g1,g1)xy, for any x,y∈Zp∗.

  • – Non-degenerate property: eˆ(g1,g1)=g2≠1.

  • – Computable property: eˆ(X,Y) can be effectively computed for any X,Y∈G1.

2.2Security Assumptions

Our proposed FCLR-CBSC scheme is based on two security assumptions as presented below:

  • – Strong-collision-resistant hash (SCRH) assumption: Let a hash function H:{0,1}∗→{0,1}l, l is a large integer, be strong-collision-resistant. Namely, it is difficult to get two different strings S1,S2∈{0,1}∗ such that H(S1)=H(S2).

  • – Discrete logarithm (DL) assumption: In the bilinear pairing set {g1,g2,G1,G2,p,eˆ} presented earlier, it is difficult to compute x∈Zp∗ for given g1x∈G1 or g2x∈G2.

2.3Generic Bilinear Group Model

The generic bilinear group (GBG) model (Boneh et al., 2005) is a security proving technique of cryptographic schemes. This GBG model is combined into the security game of a cryptographic scheme. In the security game played by an adversary and a challenger, the challenger first creates a bilinear pairing set {g1,g2,G1,G2,p,eˆ}. When the adversary performs operations in the bilinear pairing set, it must request the associated queries to the challenger that include the multiplicative query Q1 of G1, the multiplicative query Q2 of G2 and the bilinear pairing query Qeˆ. Additionally, the challenger sets two injective random mappings to respectively encode every element of G1 and G2 to a distinct bit string, namely, ζ1:Zp∗→ΨG1 and ζ2:Zp∗→ΨG2 that satisfy ΨG1∩ΨG2=∅ and |ΨG1|=|ΨG2|=p. The behaviours of three associated queries Q1, Q2 and Qeˆ, for x,y∈Zp∗, are defined as follows:

  • – Q1(ζ1(x),ζ1(y))→ζ1(x+ymodp).

  • – Q2(ζ2(x),ζ2(y))→ζ2(x+ymodp).

  • – Qeˆ(ζ1(x),ζ1(y))→ζ2(x·ymodp).

Note that ζ1(1) and ζ2(1) equal g1 and g2, respectively. Finally, the adversary would answer the DL problem on G1/G2 if it found any collision on G1/G2 after finishing the security game.

2.4Entropy Evaluation of Secret Keys

Later, we will employ the entropy evaluation of secret keys with partial leakage to establish the security theorems of the proposed scheme. Here, we first introduce two previous consequences. In 2008, Dodis et al. (2008) presented a result (Lemma 1 below) about the entropy evaluation of a secret key K under the leakage function F(K), where F:K→{0,1}ω and ω is the leakage bit size. Moreover, Galindo and Virek (2013) discussed the entropy evaluation of multiple secret keys to obtain the other result (Lemma 2 below).

Lemma 1.

Let K be a secret key and F:K→{0,1}ω be its associated leakage function, where ω is the leakage bit size. Under the leakage function F, we have H˜∞(K|F(K))≧H∞(K)−ω, where H∞ and H˜∞ denote the min-entropy and the average conditional min-entropy, respectively.

Lemma 2.

Let K1,K2,…,Kn be multiple secret keys participated in a computation formula. Let MVP∈Zp[K1,K2,…,Kn] denote a multiple-variable polynomial that has the degree d. Assume that PDi denotes the probability distribution of Ki=ki←Zp under a leakage function Fi with the leakage bit size ω. Thus, we have H∞(PDi)≧logp−ω, for i=1,2,…,n. When all PDi are mutually independent, we have Pr[MVP(K1=k1,K2=k2,…,Kn=kn)=0]≦(d/p)2ω, which is negligible if ω<(1−ε)logp, where ε is a positive fraction.

3Notations, Framework and Adversary Model

An FCLR-CBSC scheme composes of two roles, namely, a trusted certificate authority (CA) and members. A member IDm (a sender IDs or a receiver IDr) first sets the member’s secret key MSKm and first public key MPKm, and transmits (IDm, MPKm) to the CA. The CA uses a secret key CSK to compute and return the member’s certificate CTFm and second public key UPKm to the member IDm via a secure channel. By taking as input a message msg and the public key pair (MPKr,UPKr) of the receiver IDr, the sender IDs uses her/his certificate and secret key to compute a ciphertext CT and send (IDs, CT) to the receiver IDr. By taking as input a ciphertext CT and the public key pair (MPKs,UPKs) of the sender IDs, the receiver IDr returns msg if CT is “Valid”; otherwise returns “Invalid”. The system model of the FCLR-CBSC scheme is depicted in Fig. 1.

Fig. 1

The system model of an FCLR-CBSC scheme.

The system model of an FCLR-CBSC scheme.

To achieve fully continuous leakage-resilient property (Kiltz and Pietrzak, 2010; Galindo and Virek, 2013), every secret key or certificate in the system is partitioned into two parts, which must be updated before being participated in each computation round. Assume that the CA’s secret key CSK is initially partitioned into the beginning secret key pair (CSK1,0, CSK2,0). Additionally, let the CA’s current secret key pair be (CSK1,i−1,CSK2,i−1), which must be updated to (CSK1,i,CSK2,i) when it participates in the i-th invocation of the certificate generation algorithm. Note that we have CSK=CSK1,0·CSK2,0=⋯=CSK1,i−1·CSK2,i−1=CSK1,i·CSK2,i. For the same reason, the member IDm’s secret key MSKm and certificate CTFm are initially partitioned into the beginning secret key pair (MSKm,1,0, MSKm,2,0) and the certificate pair (CTFm,1,0, CTFm,2,0), respectively. Let the member IDm’s current secret key and certificate pairs be, respectively, (CTFm,1,j−1,CTFm,2,j−1) and (MSKm,1,j−1,MSKm,2,j−1), which must be updated to (CTFm,1,j,CTFm,2,j) and (MSKm,1,j,MSKm,2,j) when they participate in the j-th invocation of the signcryption or unsigncryption algorithm. Note that we have MSKm=MSKm,1,0·MSKm,2,0=⋯=MSKm,1,j−1·MSKm,2,j−1=MSKm,1,j·MSKm,2,j and CTFm=CTFm,1,0·CTFm,2,0=⋯=CTFm,1,j−1·CTFm,2,j−1=CTFm,1,j·CTFm,2,j.

In the following, we first present some symbols and notations used in the proposed FCLR-CBSC scheme. Subsequently, a new framework and adversary model of FCLR-CBSC schemes are defined.

3.1Symbols and Notations

For reference, the symbols and notations used in the proposed scheme are summarized in Table 2.

Table 2

Symbols and notations.

Symbols/notationsMeanings
PPSa public parameter set
CPKthe CA’s public key
CSKthe CA’s secret key
(CSK1,0,CSK2,0)the CA’s beginning secret key pair
(CSK1,i,CSK2,i)the CA’s i-th secret key pair
IDmthe identity of a member (a sender IDs or a receiver IDr)
(MPKm,UPKm)the public key pair of IDm
MSKmthe certificate of IDm
(MSKm,1,0,MSKm,2,0)the beginning secret key pair of IDm
(MSKm,1,j,MSKm,2,j)the j-th secret key pair of IDm
CTFmthe certificate of IDm
(CTFm,1,0,CTFm,2,0)the beginning certificate pair of IDm
(CTFm,1,j,CTFm,2,j)the j-th certificate pair of IDm
H()a hash function
SKE()/SKD()symmetric-key encryption/decryption functions
IDsthe identity of a sender (it is also a member)
IDrthe identity of a receiver (it is also a member)
msga message
CTa ciphertext

3.2Framework

Based on the frameworks of both the LR-CBS (Wu et al., 2019) and the LR-CBE (Wu et al., 2020a) schemes, a new framework of FCLR-CBSC schemes is defined as follows.

Definition 1.

An FCLR-CBSC scheme comprises five algorithms as presented below:

  • – Initialization: The CA runs this algorithm to compute the CA’s secret key CSK and system public key CPK while generating and publishing a public parameter set PPS. Additionally, the CA also partitions CSK to set the beginning secret key pair (CSK1,0,CSK2,0).

  • – Member secret key generation: A member IDm (a sender IDs or a receiver IDr) runs this algorithm to compute her/his secret key MSKm and first public key MPKm. Additionally, the member IDm partitions MSKm to set the beginning secret key pair (MSKm,1,0,MSKm,2,0). Finally, the member IDm sends (IDm,MPKm) to the CA.

  • – Certificate generation: Assume that the CA’s current secret key pair is (CSK1,i−1,CSK2,i−1). The CA first obtains a new current secret key pair (CSK1,i,CSK2,i) by updating (CSK1,i−1,CSK2,i−1). Upon receiving (IDm, MPKm) from the member IDm, the CA creates and returns the certificate CTFm and second public key UPKm to the member IDm. Upon receiving (CTFm, UPKm), the member IDm sets her/his beginning certificate pair (CTFm,1,0, CTFm,2,0) and public key pair (MPKm, UPKm).

  • – Signcryption: Assume that the sender IDs’s current certificate and secret key pairs are, respectively, (CTFs,1,j−1, CTFs,2,j−1) and (MSKs,1,j−1, MSKs,2,j−1). The sender IDs first obtains a new current certificate pair (CTFs,1,j, CTFs,2,j) and secret key pair (MSKs,1,j, MSKs,2,j) by updating (CTFs,1,j−1, CTFs,2,j−1) and (MSKs,1,j−1, MSKs,2,j−1), respectively. By taking as input a message msg and the public key pair (MPKr,UPKr) of the receiver IDr, the sender IDs runs this algorithm to return a ciphertext CT.

  • – Unsigncryption: Assume that the receiver IDr’s current certificate and secret key pairs are, respectively, (CTFr,1,k−1, CTFr,2,k−1) and (MSKr,1,k−1, MSKr,2,k−1). The receiver IDr first obtains a new current certificate pair (CTFr,1,k, CTFr,2,k) and secret key pair (MSKr,1,k, MSKr,2,k) by updating (CTFr,1,k−1, CTFr,2,k−1) and (MSKr,1,k−1, MSKr,2,k−1), respectively. By taking as input a ciphertext CT and the public key pair (MPKs,UPKs) of the sender IDs, the receiver IDr returns msg if CT is “Valid”; otherwise returns “Invalid”.

3.3Adversary Model

Here, six continuous leakage functions fCA,i, hCA,i, fSC,j, hSC,j, fUS,k and hUS,k are used to simulate the leakage abilities of adversaries. In the i-th invocation of the Certificate generation algorithm, an adversary could obtain partial bits of the CA’s current secret key pair (CSK1,i,CSK2,i) by fCA,i and hCA,i. In the j-th invocation of the Signcryption algorithm, an adversary could obtain partial bits of the sender IDs’s current certificate pair (CTFs,1,j, CTFs,2,j) and secret key pair (MSKs,1,j, MSKs,2,j) by fSC,j and hSC,j. In the k-th invocation of the Unsigncryption algorithm, an adversary could obtain partial bits of the receiver IDr’s current certificate pair (CTFr,1,k, CTFr,2,k) and secret key pair (MSKr,1,k, MSKr,2,k) by fUS,k and hUS,k. Let ω be the maximal leakage bit length for each leakage function. Let ΔfCA,i, ΔhCA,i, ΔfSC,j, ΔhSC,j, ΔfUS,k and ΔhUS,k, respectively, denote their outputs of the six leakage functions. Therefore, we have |ΔfCA,i|, |ΔhCA,i|, |ΔfSC,j|, |ΔhSC,j|, |ΔfUS,k|, |ΔhUS,k|≦ω and their inputs/outputs are presented as follows:

  • – ΔfCA,i=fCA,i(CSK1,i).

  • – ΔhCA,i=hCA,i(CSK2,i).

  • – ΔfSC,j=fSC,j(CTFs,1,j,MSKs,1,j).

  • – ΔhSC,j=hSC,j(CTFs,2,j,MSKs,2,j).

  • – ΔfUS,k=fUS,k(CTFr,1,k,MSKr,1,k).

  • – ΔhUS,k=hUS,k(CTFr,2,k,MSKr,2,k).

Based on the adversary models of both the LR-CBS (Wu et al., 2019) and the LR-CBE (Wu et al., 2020a) schemes, we define a new adversary model of FCLR-CBSC schemes. In the new adversary model, there are two types of adversaries (AI and AII) as presented below:

  • – AI: AI simulates an “uncertified member” who can set any member IDm’s secret key MSKm and first public key MPKm, but can obtain neither IDm’s certificate CTFm nor second public key UPKm. Indeed, AI can get partial bits of the CA’s current secret key pair (CSK1,i, CSK2,i) in the i-th invocation of the Certificate generation algorithm. Also, AI could obtain partial bits of the sender IDs’s current certificate pair (CTFs,1,j, CTFs,2,j) in the j-th invocation of the Signcryption algorithm. In the k-th invocation of the Unsigncryption algorithm, AI could obtain partial bits of the receiver IDr’s current certificate pair (CTFr,1,k,CTFr,2,k).

  • – AII: AII simulates an “honest-but-curious CA” who has the CA’s secret key CSK and produces any member IDm’s certificate CTFm and second public key UPKm, but AII can obtain neither the member IDm’s secret key MSKm nor first public key MPKm. Also, AII could obtain partial bits of the sender IDs’s current secret key pair (MSKs,1,j,MSKs,2,j) in the j-th invocation of the Signcryption algorithm. In the k-th invocation of the Unsigncryption algorithm, AII could obtain partial bits of the receiver IDr’s current secret key pair (MSKr,1,k, MSKr,2,k).

An FCLR-CBSC scheme must possess two security properties, namely, authentication of signing process and confidentiality of encrypting process, that are modelled by two security games as defined below.
Definition 2

Definition 2(Gauth).

The authentication property is modelled by the security game Gauth that is played by an adversary A (AI or AII) and a challenger B. We say that an FCLR-CBSC scheme has existential unforgeability against both continuous leakage and adaptive chosen-message attacks (EXUF-CLRACMA) if no probabilistic polynomial time (PPT) adversary A has a non-negligible advantage to win the following game Gauth.

  • – Setup. The challenger B runs the Initialization algorithm in Definition 1 to get the CA’s secret key CSK and public key CPK while generating and publishing a public parameter set PPS. Also, B partitions CSK to set the beginning secret key pair (CSK1,0, CSK2,0). Additionally, if A is of type AII, B sends CSK to AII.

  • – Queries. A may adaptively request the following queries to B at most η times.

    • • Member key generation query (IDm): B produces and returns the member IDm’s secret key MSKm and first public key MPKm.

    • • Member secret key query (IDm): B returns the member IDm’s secret key MSKm.

    • • Certificate generation query (IDm, MPKm): B returns the member IDm’s certificate CTFm and second public key UPKm.

    • • Certificate generation leak query (i, fCA,i, hCA,i): A may request this query only once. B returns ΔfCA,i=fCA,i(CSK1,i) and ΔhCA,i=hCA,i(CSK2,i).

    • • Public key retrieve query (IDm): B returns the member IDm’s public key pair (MPKm, UPKm).

    • • Public key replace query (IDm, (MPKm′, UPKm′)): B records the replacement.

    • • Signcryption query (msg, IDs, IDr): The sender IDs first obtains a new current certificate pair (CTFs,1,j, CTFs,2,j) and secret key pair (MSKs,1,j, MSKs,2,j) by updating (CTFs,1,j−1, CTFs,2,j−1) and (MSKs,1,j−1, MSKs,2,j−1), respectively. B returns a ciphertext CT.

    • • Signcryption leak query (IDs, j, fSC,j, hSC,j): A may request this query only once. B returns ΔfSC,j=fSC,j(CTFs,1,j,MSKs,1,j) and ΔhSC,j=hSC,j(CTFs,2,j,MSKs,2,j).

    • • Unsigncryption query (CT, IDr): The receiver IDr first obtains a new current certificate pair (CTFr,1,k, CTFr,2,k) and secret key pair (MSKr,1,k, MSKr,2,k) by updating (CTFr,1,k−1, CTFr,2,k−1) and (MSKr,1,k−1, MSKr,2,k−1), respectively. B returns the message msg.

    • • Unsigncryption leak query (IDr, k, fUS,k, hUS,k): A may request this query only once. B returns ΔfUS,k=fUS,k(CTFr,1,k,MSKr,1,k) and ΔhUS,k=hUS,k(CTFr,2,k,MSKr,2,k).

  • – Forgery. A creates a tuple (msg′, CT′=(σ′,C′,U′,IDs′, IDr′)). It is said that A wins Gauth if the following four conditions hold.

    • (1) For (msg′,CT′=(σ′,C′,U′,IDs′,IDr′)), the Unsigncryption algorithm returns “Valid”.

    • (2) The Signcryption query (msg′,IDs′,IDr′) has never been requested.

    • (3) If A is of type AI, the Certificate generation query (IDs′,MPKs′) has never been requested.

    • (4) If A is of type AII, neither the Member secret key query (IDs′), nor the Public key replace query (IDs′,(MPKs′,UPKs′)) have never been requested.

Definition 3

Definition 3(Gconf).

The confidentiality property is modelled by the security game Gconf that is played by an adversary A (AI or AII) and a challenger B. We say that an FCLR-CBSC scheme has indistinguishability of encryptions against both continuous leakage and chosen-ciphertext attacks (INDEN-CLCCA) if no PPT adversary A has a non-negligible advantage to win the following game Gconf.

  • – Setup. It is identical to the Setup in Definition 2.

  • – Queries. It is identical to the Queries in Definition 2.

  • – Challenge. A sends a receiver’s identity IDr′ and a message pair (msg0′, msg1′) to B. Then B randomly chooses a bit b′∈{0,1} and runs the Signcryption algorithm with (msgb′, IDs, IDr′) to create and return a ciphertext CT=(σ,C,U,IDs,IDr′) to A. Additionally, the following two conditions must hold.

    • (1) If A is of type AI, the Certificate generation query (IDr′, MPKr′) has never been requested.

    • (2) If A is of type AII, neither the Member secret key query (IDr′), nor the Public key replace query (IDr′, (MPKr′, UPKr′)) have been requested.

  • – Guess. A returns a bit b∈{0,1}. If b=b′, we say that A wins Gconf and its advantage is defined as AdvA=|Pr[b=b′]−1/2|.

4The Proposed FCLR-CBSC Scheme

By the framework defined in Section 3, a fully continuous leakage-resilient certificate-based signcryption (FCLR-CBSC) scheme is proposed below that comprises five algorithms.

  • – Initialization: The CA first create a bilinear pairing set {g1,g2,G1,G2,p,eˆ} described in Section 2. By running the following procedure, the CA computes her/his secret key CSK and public key CPK while generating and publishing a public parameter set PPS.

    • (1) Choose a random value s∈Zp∗, and compute the CA’s secret key CSK=g1s and public key CPK=eˆ(CSK,g1).

    • (2) Choose a random value t∈Zp∗, and set the CA’s beginning secret key pair (CSK1,0,CSK2,0)=(CSK·g1−t,g1t), where CSK=CSK1,0·CSK2,0 and the public key CPK is kept unchanged.

    • (3) Choose four random values w,x,y,z∈Zp∗, and compute W=g1w, X=g1x, Y=g1y and Z=g1z.

    • (4) Pick symmetric-key encryption and decryption functions, denoted by SKE and SKD.

    • (5) Pick a hash function H: {0,1}∗×G1→{0,1}l, where l is a large integer.

    • (6) Publish PPS={g1,g2,G1,G2,p,eˆ,CPK,W,X,Y,Z,SKE,SKD,H}.

  • – Member secret key generation: A member IDm (a sender IDs or a receiver IDr) first chooses a random value a∈Zp∗, and computes the member’s secret key MSKm=g1a and first public key MPKm=eˆ(MSKm,g1). The member chooses a random value b∈Zp∗ and computes the member IDm’s beginning secret key pair (MSKm,1,0,MSKm,2,0)=(MSKm·g1−b,g1b), where MSKm=MSKm,1,0·MSKm,2,0. Meanwhile, the member IDm sends (IDm, MPKm) to the CA.

  • – Certificate generation: Assume that the CA’s current secret key pair is (CSK1,i−1,CSK2,i−1). Upon receiving (IDm,MPKm) from the member IDm, the CA runs the following procedure.

    • (1) Choose a random value u∈Zp∗, and update the CA’s current secret key pair as (CSK1,i,CSK2,i)=(CSK1,i−1·g1−u,CSK2,i−1·g1u), where CSK=CSK1,i·CSK2,i=CSK1,i−1·CSK2,i−1 and the public key CPK is kept unchanged.

    • (2) Choose a random value v∈Zp∗, compute the member IDm’s second public key UPKm=g1v and set the member IDm’s public key pair (MPKm, UPKm).

    • (3) Set α=IDm||MPKm||UPKm, and compute a temporary value TVm=CSK1,i·(W·Xα)v and the member IDm’s certificate CTFm=CSK2,i·TVm.

    • (4) Return CTFm to the member IDm via a secure channel.

    Upon receiving CTFm, the member IDm chooses a random value c∈Zp∗ and sets her/his beginning certificate pair (CTFm,1,0,CTFm,2,0)=(CTFm·g1−c,g1c).

  • – Signcryption: Assume that the sender IDs’s current certificate and secret key pairs are, respectively, (CTFs,1,j−1, CTFs,2,j−1) and (MSKs,1,j−1, MSKs,2,j−1). The sender IDs would like to signcrypt a message msg to the receiver IDr with public key pair (MPKr, UPKr) by running the following procedure.

    • (1) Choose a random value d∈Zp∗, and update the two pairs above as (CTFs,1,j,CTFs,2,j)=(CTFs,1,j−1·g1d,CTFs,2,j−1·g1−d) and (MSKs,1,j,MSKs,2,j)=(MSKs,1,j−1·g1d,MSKs,2,j−1·g1−d), where CTFs=CTFs,1,j·CTFs,2,j=CTFs,1,j−1·CTFs,2,j−1 and MSKs=MSKs,1,j·MSKs,2,j=MSKs,1,j−1·MSKs,2,j−1. Note that the member IDs’s public key pair (MPKs,UPKs) is kept unchanged.

    • (2) Set α=IDr||MPKr||UPKr, select a random value β∈Zp∗, and compute U=g1β,K1=(MPKr)β and K2=(CPK·eˆ(UPKr,W·Xα))β.

    • (3) Set an encryption key K=K1⊕K2, and compute C=SKEK(msg) and δ=H(msg,C,U,IDs,IDr).

    • (4) Compute a temporary value TVS=CTFs,1,j·MSKs,1,j·(Y·Zδ)β.

    • (5) Compute a signature σ=CTFs,2,j·MSKs,2,j·TVS.

    • (6) Produce a ciphertext CT=(σ,C,U,IDs,IDr).

  • – Unsigncryption: Assume that the receiver IDr’s current certificate and secret key pairs are, respectively, (CTFr,1,k−1, CTFr,2,k−1) and (MSKr,1,k−1, MSKr,2,k−1). Given CT=(σ,C,U,IDs,IDr), the receiver IDr unsigncrypts CT to obtain the message msg and verify the signature σ by running the following procedure.

    • (1) Choose a random value f∈Zp∗, and update the two pairs above as (CTFr,1,k,CTFr,2,k)=(CTFr,1,k−1·g1f,CTFr,2,k−1·g1−f) and (MSKr,1,k,MSKr,2,k)=(MSKr,1,k−1·g1f,MSKr,2,k−1·g1−f), where CTFr=CTFr,1,k·CTFr,2,k=CTFr,1,k−1·CTFr,2,k−1 and MSKr=MSKr,1,k·MSKr,2,k=MSKr,1,k−1·MSKr,2,k−1. Note that the member IDr’s public key pair (MPKr,UPKr) is kept unchanged.

    • (2) Compute two temporary values TVK1=eˆ(U,MSKr,1,k) and TVK2=eˆ(U,CTFr,1,k).

    • (3) Compute K1′=TVK1·eˆ(U,MSKr,2,k) and K2′=TVK2·eˆ(U,CTFr,2,k).

    • (4) Set K′=K1′⊕K2′, and decrypt the message msg=SKDK′(C).

    • (5) Compute δ=H(msg,C,U,IDs,IDr), and set α=IDr|| MPKr ||UPKr.

    • (6) Verify the equality eˆ(g1,σ)=CPK·MPKs·eˆ(UPKs,W·Xα)·eˆ(U,Y·Zδ). If the equality holds, return msg and “Valid”; otherwise return “Invalid”.

    We can arrive at K′=K1′⊕K2′=K1⊕K2=K and eˆ(g1,σ)=CPK·MPKs·eˆ(UPKs,W·Xα)·eˆ(U,Y·Zδ) by the following equalities.

    • (1) K1′=TVK1·eˆ(U,MSKr,2,k)=eˆ(U,MSKr,1,k)·eˆ(U,MSKr,2,k)=eˆ(U,MSKr,1,k·MSKr,2,k)=eˆ(U,MSKr)=eˆ(g1β,MSKr)=eˆ(MSKr,g1)β=(MPKr)β=K1.

    • (2) K2′=TVK2·eˆ(U,CTFr,2,k)=eˆ(U,CTFr,1,k)·eˆ(U,CTFr,2,k)=eˆ(U,CTFr,1,k·CTFr,2,k)=eˆ(U,CTFr)=eˆ(g1β,CSK·(W·Xα)v)=eˆ(g1,CSK·(W·Xα)v)β=eˆ(g1,CSK)·eˆ(g1,(W·Xα)v)β=(CPK·eˆ(g1v,(W·Xα))β=(CPK·eˆ(UPKr,W·Xα))β=K2.

    • (3) eˆ(g1,σ)=eˆ(g1,CTFs,2,j·MSKs,2,j·TVS)=eˆ(g1,CTFs,2,j·MSKs,2,j·CTFs,1,j·MSKs,1,j·(Y·Zδ)β)=eˆ(g1,CTFs,1,j·CTFs,2,j·MSKs,1,j·MSKs,2,j·(Y·Zδ)β)=eˆ(g1,CTFs·MSKs·(Y·Zδ)β)=eˆ(g1,CSK·(W·Xα)v·MSKs·(Y·Zδ)β)=eˆ(g1,CSK)·eˆ(g1,(W·Xα)v)·eˆ(g1,MSKs)·eˆ(g1,(Y·Zδ)β)=CPK·eˆ(g1v,(W·Xα))·MPKs·eˆ(g1β,(Y·Zδ))=CPK·MPKs·eˆ(UPKs,W·Xα)·eˆ(U,Y·Zδ).

5Security Analysis

An FCLR-CBSC scheme must possess two security properties, namely, authentication of signing process and confidentiality of encrypting process, that are modelled by two security games Gauth and Gconf defined in Section 3.3. Both games are played by an adversary A (AI or AII) and a challenger B. Theorems 1 and 2 below show that our FCLR-CBSC scheme is EXUF-CLRACMA-secure against AI and AII in Gauth, respectively. Also, Theorems 3 and 4 show that the FCLR-CBSC scheme is INDEN-CLCCA-secure against AI and AII in Gconf, respectively.

Theorem 1.

Under the SCRH and DL assumptions in the GBG model, our FCLR-CBSC scheme is EXUF-CLRACMA-secure against AI in Gauth.

Proof.

AI and B play Gauth that comprises three phases as presented below.

  • – Setup. B runs the Initialization algorithm of the FCLR-CBSC scheme to create the CA’s secret key CSK and public key CPK while setting the public parameter set PPS={g1,g2,G1,G2,p,eˆ,CPK,W,X,Y,Z,SKE,SKD,H}. B also establishes six lists L1, L2, LMS, LMC, LSC and LH as defined below.

    • • L1 is used to record all elements (ΘG1,a,b,c, ΨG1,a,b,c) of G1, where ΘG1,a,b,c and ΨG1,a,b,c denote a multivariate polynomial and its associated bit string, respectively. The indices a, b, c mean the query-type a, b-th query and c-th element, respectively. Initially, six elements (Θg1, ΨG1,s,0,1), (ΘCSK, ΨG1,s,0,2), (ΘW, ΨG1,s,0,3), (ΘX, ΨG1,s,0,4), (ΘY, ΨG1,s,0,5) and (ΘZ, ΨG1,s,0,6) are put in L1.

    • • L2 is used to record all elements (ΘG2,a,b,c, ΨG2,a,b,c) of G2, where ΘG2,a,b,c and ΨG2,a,b,c denote a multivariate polynomial and the associated bit string, respectively. The indices a, b, c have the identical meanings as in L1. Initially, two elements (Θg2, ΨG2,s,0,1) and (ΘCPK, ΨG2,s,0,2) are put in L2.

    Note that AI can apply the following two rules to make converting between a bit string ΨG1,a,b,c/ΨG2,a,b,c and a multivariate polynomial ΘG1,a,b,c/ΘG2,a,b,c.

    • (1) Converting-1 (ΘG1,a,b,c/ΘG2,a,b,c): B returns ΨG1,a,b,c/ΨG2,a,b,c if ΘG1,a,b,c/ΘG2,a,b,c is found in L1/L2. Otherwise, B chooses a distinct bit string ΨG1,a,b,c/ΨG2,a,b,c and puts (ΘG1,a,b,c,ΨG1,a,b,c)/(ΘG2,a,b,c,ΨG2,a,b,c) in L1/L2.

    • (2) Converting-2 (ΨG1,a,b,c/ΨG2,a,b,c): B returns ΘG1,a,b,c/ΘG2,a,b,c if ΨG1,a,b,c/ΨG2,a,b,c is found in L1/L2. Otherwise, B terminates the game.

    • • LMS is used to record a member IDm’s secret key MSKm and her/his first public key MPKm by (IDm, ΘMSKm, ΘMPKm, replace), for m=1,…,n. Initially, B sets replace=0 to indicate that the member’s public key has never been replaced by the adversary.

    • • LMC is used to record a member IDm’s certificate CTFm and her/his second public key UPKm by (IDm, ΘCTFm, ΘUPKm, replace), for m=1,…,n. Also, B sets replace=0.

    • • LSC is used to record the content of running the Signcryption algorithm by (IDs,IDr,msg,ΘU,ΘK1,ΘK2,Θσ,C,Θδ).

    • • LH is used to record the input/output of the hash function H by (msg||C||ΨU||IDs||IDr,Ψδ).

  • – Query: AI may issue the following queries to B at most η times.

    • • Q1 query (ΨG1,q,k,r,ΨG1,q,k,s,ORER): For the k-th Q1, B runs the following procedure.

      • (1) Convert (ΨG1,q,k,r, ΨG1,q,k,s) to (ΘG1,q,k,r, ΘG1,q,k,s) in L1.

      • (2) Set ΘG1,q,k,t=ΘG1,q,k,r+ΘG1,q,k,s if ORER = “×”, and ΘG1,q,k,t=ΘG1,q,k,r−ΘG1,q,k,s if ORER = “/”.

      • (3) Convert ΘG1,q,k,t in L1 to return ΨG1,q,k,t.

    • • Q2 query (ΨG2,q,k,r, ΨG2,q,k,s, ORER): For the k-th Q2, B runs the following procedure.

      • (1) Convert (ΨG2,q,k,r, ΨG2,q,k,s) to (ΘG2,q,k,r, ΘG2,q,k,s) in L2.

      • (2) Set ΘG2,q,k,t=ΘG2,q,k,r+ΘG2,q,k,s if ORER=“×″, and ΘG2,q,k,t=ΘG2,q,k,r−ΘG2,q,k,s if ORER = “/”.

      • (3) Convert ΘG2,q,k,t in L2 to return ΨG2,q,k,t.

    • • Qeˆ query (ΨG1,q,k,r, ΨG1,q,k,s): For the k-th Qeˆ, B runs the following procedure.

      • (1) Convert (ΨG1,q,k,r, ΨG1,q,k,s) to (ΘG1,q,k,r, ΘG1,q,k,s) in L1.

      • (2) Set ΘG2,q,k,t=ΘG1,q,k,r·ΘG1,q,k,s.

      • (3) Convert ΘG2,q,k,t in L2 to return ΨG2,q,k,t.

    • • Member key generation query (IDm): B produces the member IDm’s secret key ΘMSKm and first public key ΘMPKm. B then puts (IDm, ΘMSKm, ΘMPKm, 0) in LMS. Also, B converts (ΘMSKm, ΘMPKm) in L1 to return (ΨMSKm, ΨMPKm).

    • • Member secret key query (IDm): If (IDm, ΘMSKm, ΘMPKm, 0) in LMS is found, B converts ΘMSKm in L1 to return ΨMSKm. Otherwise, B issues the Member key generation query (IDm) to return ΨMSKm.

    • • Certificate generation query (IDm, ΨMPKm): Assume that the CA has the i-th secret key pair (ΘCSK1,i, ΘCSK2,i). B runs the following procedure.

      • (1) Pick a new variate ΘUPKm in G1 as the second public key of the member IDm.

      • (2) Pick a new variate Θα in G1 and put (Θα, Ψα=IDm|| ΨMPKm|| ΨUPKm) in L1.

      • (3) Set ΘCTFm=ΘCSK+(ΘW+ΘX·Θα)·ΘUPKm and put (IDm, ΘCTFm, ΘUPKm, 0) in LMC.

      • (4) Convert (ΘCTFm, ΘUPKm) in L1 to return (ΨCTFm, ΨUPKm).

    • • Certificate generation leak query (i, fCA,i, hCA,i): AI can issue this query only once for the CA’s i-th secret key pair (ΘCSK1,i, ΘCSK2,i). B returns ΔfCA,i=fCA,i(ΘCSK1,i) and ΔhCA,i=hCA,i(ΘCSK2,i).

    • • Public key retrieve query (IDm): B finds IDm’s public key pair (ΘMPKm, ΘUPKm) by searching (IDm, ΘMSKm, ΘMPKm, 0) in LMS and (IDm, ΘCTFm, ΘUPKm, 0) in LMC. B converts (ΘMPKm, ΘUPKm) in L1 to return (ΨMPKm, ΨUPKm).

    • • Public key replace query (IDm, (ΨMPKm′, ΨUPKm′)): B converts (ΨMPKm′, ΨUPKm′) to (ΘMPKm′, ΘUPKm′). B modifies (IDm,−,ΘMPKm′,1) in LMS and (IDm,−,ΘUPKm′,1) in LMC.

    • • Signcryption query (msg, IDs, IDr): Assume that the sender IDs has the j-th certificate pair (ΘCTFs,1,j, ΘCTFs,2,j) and secret key pair (ΘMSKs,1,j, ΘMSKs,2,j). B runs the following procedure.

      • (1) Use IDr to find (IDr, ΘMSKr, ΘMPKr, replace) in LMS and (IDr, ΘCTFr, ΘUPKr, replace) in LMC, and convert (ΘMPKr, ΘUPKr) in L1 to (ΨMPKr, ΨUPKr).

      • (2) Set Ψα=IDr||ΨMPKr||ΨUPKr and convert Ψα in L1 to Θα.

      • (3) Choose a new variate ΘU in G1, and set ΘK1=ΘMPKr·ΘU and ΘK2=(ΘCPK+ΘUPKr·(ΘW+ΘX·Θα))·ΘU.

      • (4) Convert both ΘU and ΘK1 in L1, and ΘK2 in L2 to obtain ΨU, ΨK1 and ΨK2.

      • (5) Set ΨK=ΨK1⊕ΨK2 and C=SKEΨK(msg).

      • (6) Choose a new variate Θδ in G1, and set Ψδ=H(msg||C||ΨU||IDs||IDr), and put (Θδ, Ψδ) in L1.

      • (7) Set Θα=ΘCTFs+ΘMSKs+(ΘY+ΘZ·Θδ)·ΘU and convert Θδ in L1 to Ψσ.

      • (8) Put (IDs,IDr,msg,ΘU,ΘK1,ΘK2,Θσ,C,Θδ) in LSC.

      • (9) Return CT=(Ψσ,C,ΨU,IDs,IDr).

    • • Signcryption leak query (IDs, j, fSC,j, hSC,j): AI can issue this query only once for the member IDs’s j-th certificate pair (ΘCTFs,1,j, ΘCTFs,2,j) and secret key pair (ΘMSKs,1,j, ΘMSKs,2,j). B returns ΔfSC,j=fSC,j(ΘCTFs,1,j,ΘMSKs,1,j) and ΔhSC,j=hSC,j(ΘCTFs,2,j,ΘMSKs,2,j).

    • • Unsigncryption query (IDr, CT=(Ψσ,C,ΨU,IDs,IDr)): Assume that the receiver IDr has the k-th certificate pair (ΘCTFr,1,k, ΘCTFr,2,k) and secret key pair (ΘMSKr,1,k, ΘMSKr,2,k). B runs the following procedure.

      • (1) Use IDs to find (IDs, ΘMSKs, ΘMPKs, replace) in LMS and (IDs, ΘCTFs, ΘUPKs, replace) in LMC, and convert (ΘMPKs, ΘUPKs) in L1 to (ΨMPKs, ΨUPKs).

      • (2) Convert Ψσ and ΨU in L1 to Θσ and ΘU, respectively.

      • (3) Set ΘK1=ΘU·ΘMSKr and ΘK2=ΘU·ΘCTFr.

      • (4) Set Ψδ=H(msg||C||ΨU||IDs||IDr) and convert Ψδ in L1 to Θδ.

      • (5) Use IDs, IDr, ΘU, ΘK1, ΘK2, Θσ, C and Θδ to find (IDs,IDr,msg,ΘU,ΘK1,ΘK2,Θσ,C,Θδ) in LSC. If it is found, return msg and “Valid”.

    • • Unsigncryption leak query (IDr, k, fUS,k, hUS,k): AI can issue this query only once for the member IDr’s k-th certificate pair (ΘCTFr,1,k, ΘCTFr,2,k) and secret key pair (ΘMSKr,1,k, ΘMSKr,2,k). B returns ΔfUS,k=fUS,k(ΘCTFr,1,k,ΘMSKr,1,k) and ΔhUS,k=hUS,k(ΘCTFr,2,k, ΘMSKr,2,k).

  • – Forgery. AI produces a pair (msg′,CT′=(Ψσ′,C′,ΨU′,IDs′,IDr′)). Note that the Signcryption query (msg′, IDs′, IDr′) and the Certificate generation query (IDs′, MPKs′) have never been requested. If the Unsigncryption algorithm with (IDr′,CT′=(Ψσ′,C′,ΨU′,IDs′,IDr′)) returns msg and “Valid”, we say that AI wins Gauth.

As mentioned in Section 2.2, if an adversary found any collision of G1/G2, it would solve the discrete logarithm problem on G1/G2. In such a case, we first compute the sum amount of elements in L1 and L2, termed as |L1|+|L2|. By counting the added elements in both the Setup and Query phases, we have the inequality |L1|+|L2|≦6η because AI can request different queries to B η times and at most 6 elements are increased in L1/L2 after issuing a query. Additionally, for evaluating the entropy of secret keys with partial leakage, we must compute the maximal degrees of elements in L1 and L2, in which L1 and L2 have the maximal degrees 3 and 6, respectively.

Subsequently, let us compute the advantage AdvAI−N that AI wins Gauth without issuing leak queries. The advantage AdvAI−N comprises two probabilities as discussed below.

  • ■ Let Pr[Collision] be the probability that AI finds a collision in L1 or L2. Assume that there are r different variates in L1, which are denoted by r random values vi∈Zp∗ for i=1,2,…,r. Let ΘG1,j and ΘG1,k be two distinct elements in L1 and set ΘG1,l=ΘG1,j−ΘG1,k. If ΘG1,l(v1,v2,…,vr)=0, there exists a collision in L1. Because L1 has |L1|2 pairs of (ΘG1,j, ΘG1,k) and the maximal polynomial degree is 3, the probability that AI finds a collision in L1 is (3/p)|L1|2 by Lemma 2. For the same reason, the probability that AI finds a collision in L2 is (6/p)|L2|2. Because of |L1|+|L2|≦6η, we have the following inequality Pr[Collision]≦(3/p)|L1|2+(6/p)|L2|2≦(6/p)(|L0|+|L1|)2≦216η2/p.

  • ■ Let Pr[Forge] be the probability that AI forges a valid pair (msg′, CT′ = (Ψσ′, C′, ΨU′, IDs′, IDr′)). The valid pair satisfies eˆ(g1,σ′)=CPK·MPKs′·eˆ(UPKs′,W·Xα)·eˆ(U′,Y·Zδ) in the Unsigncryption algorithm, namely, Θg1·Θσ′=ΘCPK+ΘMPKs′+ΘUPKs′·(ΘW+ΘX·Θα)+ΘU′·(ΘY+ΘZ·Θδ). Let Θf=Θg1·Θσ′−ΘCPK+ΘMPKs′+ΘUPKs′·(ΘW+ΘX·Θα)+ΘU′·(ΘY+ΘZ·Θδ). Since Θf has degree 3, the probability of Θf=0 is 3/p by Lemma 2 so that we have Pr[Forge]=3/p.

By above, we have AdvAI−N=Pr[Collision]+Pr[Forge]≦216η2/p+3/p=O(η2/p), which is negligible if η=poly(logp).

Here, we compute the advantage AdvAI that AI wins Gauth when permitted to issue three types of leak queries, namely, Certificate generation leak query, Signcryption leak query and Unsigncryption leak query.

  • (1) By the Certificate generation leak query (i, fCA,i, hCA,i), AI gets partial bits of the CA’s i-th secret key pair (ΘCSK1,i, ΘCSK2,i), namely, ΔfCA,i=fCA,i(ΘCSK1,i) and ΔhCA,i=hCA,i(ΘCSK2,i) with |ΔfCA,i|, |ΔhCA,i|≦ω. According to the key update process (Kiltz and Pietrzak, 2010; Galindo and Virek, 2013), the CA’s i-th secret key pair satisfies the relations CSK=CSK1,0·CSK2,0=⋯=CSK1,i−1·CSK2,i−1=CSK1,i·CSK2,i. Meanwhile, the leakage bits of (ΘCSK1,i−1, ΘCSK2,i−1) and (ΘCSK1,i, ΘCSK2,i) are mutually independent, so that AI gets at most 2ω bits of CSK.

  • (2) By the Signcryption leak query (IDs, j, fSC,j, hSC,j), AI gets partial bits of the IDs’s j-th certificate pair (ΘCTFs,1,j, ΘCTFs,2,j), namely, ΔfSC,j=fSC,j(ΘCTFs,1,j) and ΔhSC,j=hSC,j(ΘCTFs,2,j) with |ΔfSC,j|, |ΔhSC,j|≦ω. According to the key update procedure, the IDs’s j-th certificate pair satisfies the relations CTFs=CTFs,1,0·CTFs,2,0=⋯=CTFs,1,j−1·CTFs,2,j−1=CTFs,1,j·CTFs,2,j. Thus, AI gets at most 2ω bits of CTFs.

  • (3) By the Unsigncryption leak query (IDr, k, fUS,k, hUS,k), AI gets partial bits of the IDr’s k-th certificate pair (ΘCTFr,1,k, ΘCTFr,2,k), namely, ΔfUS,k=fUS,k(ΘCTFr,1,k) and ΔhUS,k=hUS,k(ΘCTFr,2,k) with |ΔfUS,k|, |ΔhUS,k|≦ω. According to the key update procedure, the IDr’s k-th certificate pair satisfies the relations CTFr=CTFr,1,0·CTFr,2,0=⋯=CTFr,1,j−1·CTFr,2,j−1=CTFr,1,j·CTFr,2,j. Thus, AI gets at most 2ω bits of CTFr.

Due to the discussions above, we define three events as follows:

  • (1) Let EVCSK indicate the event that AI obtains CSK by ΔfCA,i and ΔhCA,i. Meanwhile, EVCSK‾ means EVCSK’s complement.

  • (2) Let EVCTF indicate the event that AI gets CTFm (i.e. CTFs or CTFr) by ΔfSC,j, ΔhSC,j, ΔfUS,k and ΔhUS,k. Meanwhile, EVCTF‾ means EVCTF’s complement.

  • (3) Let ESFV indicate the event that AI successfully forges a valid pair (msg′,CT′=(Ψσ′,C′,ΨU′,IDs′,IDr′)).

Hence, AdvAI has the inequality
AdvAI=Pr[ESFV]=Pr[ESFV∧(EVCSK∨EVCTF)]+Pr[ESFV∧(EVCSK‾∧EVCTF‾)]≦Pr[(EVCSK∨EVCTF)]+Pr[ESFV∧(EVSSK‾∧EVUDID‾)].

By the Certificate generation leak query, AI gets 2ω bits of CSK. Also, by the Signcryption leak query or Unsigncryption leak query, AI gets 2ω bits of CTFm (i.e. CTFs or CTFr). By Lemma 2, we have Pr[(EVCSK∨EVCTF)]≦AdvAI−N·22ω≦O((η2/p)·22ω) because of AdvAI−N=O(η2/p). Since Pr[ESFV∧(EVSSK‾∧EVUDID‾)] denotes that AI gets no information of both CSK and CTFm, we have Pr[ESFV∧(EVSSK‾∧EVUDID‾)]=AdvAI−N=O(η2/p). Therefore,

AdvAI≦Pr[(EVCSK∨EVCTF)]+Pr[ESFV∧(EVSSK‾∧EVUDID‾)]≦O((η2/p)·22ω)+O(η2/p)=O((η2/p)·22ω).
Finally, AdvAI is negligible if ω=poly(logp), by Lemma 2.  □

Theorem 2.

Under the SCRH and DL assumptions in the GBG model, our FCLR-CBSC scheme is EXUF-CLRACMA-secure against AII in Gauth.

Proof.

AII and B play Gauth that comprises three phases as presented below.

  • – Setup. It is identical to the Setup in Theorem 1. Because the adversary is of AII, B sends ΨCSK to AII.

  • – Queries. It is identical to the Queries in Theorem 1. Additionally, since AII possesses the CA’s secret key CSK, so that it can create any member IDm’s certificate CTFm and second public key UPKm. Thus, AII has no need to request the Certificate generation query and Certificate generation leak query.

  • – Forgery. AII produces a pair (msg′,CT′=(Ψσ′,C′,ΨU′,IDs′,IDr′)). Note that the Signcryption query (msg′, IDs′, IDr′), the Member secret key query (IDm) and the Public key replace query (IDm, (ΨMPKm′, ΨUPKm′)) have never been requested. If the Unsigncryption algorithm with (IDr′,CT′=(Ψσ′,C′,ΨU′,IDs′,IDr′)) returns msg and “Valid”, we say that AI wins Gauth.

Here, let’s compute the advantage AdvAII−N that AII wins Gauth without issuing leak queries. By Pr[Collision] and Pr[Forge] defined in Theorem 1, we have AdvAII−N=Pr[Collision]+Pr[Forge]≦216η2/p+3/p=O(η2/p), which is negligible if η=poly(logp). Next, we compute the advantage AdvAII that AII wins Gauth when permitted to issue two types of leak queries, namely, Signcryption leak query and Unsigncryption leak query.

  • (1) By the Signcryption leak query (IDs, j, fSC,j, hSC,j), AII gets partial bits of the IDs’s j-th secret key pair (MSKs,1,j, MSKs,2,j), namely, ΔfSC,j=fSC,j(MSKs,1,j) and ΔhSC,j=hSC,j(MSKs,2,j) with |ΔfSC,j|, |ΔhSC,j|≦ω. According to the key update procedure, the IDs’s j-th secret key pair satisfies the relations MSKs=MSKs,1,0·MSKs,2,0=⋯=MSKs,1,j−1·MSKs,2,j−1=MSKs,1,j·MSKs,2,j. Thus, AII gets at most 2ω bits of MSKs.

  • (2) By the Unsigncryption leak query (IDr, k, fUS,k, hUS,k), AII gets partial bits of the IDr’s k-th secret key pair (MSKr,1,k, MSKr,2,k), namely, ΔfUS,k=fUS,k(MSKr,1,k) and ΔhUS,k=hUS,k(MSKr,2,k) with |ΔfUS,k|, |ΔhUS,k|≦ω. According to the key update procedure, the IDr’s k-th secret key pair satisfies the relations MSKr=MSKr,1,0·MSKr,2,0=⋯=MSKr,1,j−1·MSKr,2,j−1=MSKr,1,j·MSKr,2,j. Thus, AII gets at most 2ω bits of MSKr.

Due to the discussions above, we define two events as follows:

  • (1) Let EVMSK indicate the event that AII obtains MSKm (i.e. MSKs or MSKr) by ΔfSC,j, ΔhSC,j, ΔfUS,k and ΔhUS,k. Meanwhile, EVMSK‾ denotes EVMSK’s complement.

  • (2) Let ESFV indicate the event that AII successfully forges a valid tuple (msg′,CT′=(Ψσ′,C′,ΨU′,IDs′,IDr′)).

Hence, AdvAII has the inequality
AdvAII=Pr[ESFV]=Pr[ESFV∧EVMSK]+Pr[ESFV∧EVMSK‾]≦Pr[EVMSK]+Pr[ESFV∧EVMSK‾].
By the Signcryption leak query or Unsigncryption leak query, AII gets 2ω bits of MSKm (i.e. MSKs or MSKr). By Lemma 2, we have Pr[EVMSK]≦AdvAII−N·22ω≦O((η2/p)·22ω). Since Pr[ESFV∧EVMSK‾] denotes that AII gets no information of MSKm, we have Pr[ESFV∧EVMSK‾]=AdvAII−N=O(η2/p). Therefore,
AdvAII≦Pr[EVMSK]+Pr[ESFV∧EVMSK‾]≦O((η2/p)·22ω)+O(η2/p)=O((η2/p)·22ω).
Finally, AdvAII is negligible if ω=poly(logp), by Lemma 2.  □

Theorem 3.

Under the SCRH and DL assumptions in the GBG model, our FCLR-CBSC scheme is INDEN-CLCCA-secure against AI in Gconf.

Proof.

AI and B play Gconf that comprises four phases as presented below:

  • – Setup. It is identical to the Setup in Theorem 1.

  • – Queries. It is identical to the Queries in Theorem 1.

  • – Challenge. AI sends a receiver’s identity IDr′ and a message pair (msg0′, msg1′) to B. Note that the Certificate generation query (IDr′, MPKr′) has never been requested. B randomly chooses a bit b′∈{0,1} and runs the Signcryption algorithm with (msgb′, IDs, IDr′) to produce and return a ciphertext CT=(σ,C,U,IDs,IDr′) to AI.

  • – Guess. AI returns a bit b∈{0,1}. We say that AI wins Gconf if b=b′. The advantage AdvAI is defined as |Pr[b=b′]−1/2|.

Let us compute the advantage AdvAI−N that AI wins Gconf without issuing leak queries. The advantage AdvAI−N comprises two probabilities as discussed below:

  • ■ Let Pr[Collision] be the probability that AI finds a collision in L1 or L2, which is the same with the probability Pr[Collision] in Theorem 1. Thus, we have the inequality Pr[Collision]≦216η2/p.

  • ■ Let Pr[Guess] be the probability that AI with no useful information outputs a correct bit b. Thus, we have Pr[Guess]=Pr[b=b′]=1/2.

Hence, we have the following inequality.
AdvAI−N=|Pr[b=b′]−1/2|=|Pr[Collision]+Pr[Guess]−1/2|≦216η2/p=O(η2/p).
Here, let’s compute the advantage AdvAI that AI wins Gconf when permitted to issue three types of leak queries, namely, Certificate generation leak query, Signcryption leak query and Unsigncryption leak query. As in the proof of Theorem 1, by the Certificate generation leak query, AI gets 2ω bits of CSK. Also, by the Signcryption leak query or the Unsigncryption leak query, AI gets 2ω bits of CTFm (i.e. CTFs or CTFr). By Lemma 2, we have AdvAI≦AdvAI−N·22ω≦O((η2/p)·22ω), which is negligible if ω=poly(logp).  □

Theorem 4.

Under the SCRH and DL assumptions in the GBG model, our FCLR-CBSC scheme is INDEN-CLCCA-secure against AII in Gconf.

Proof.

AII and B play Gconf that comprises four phases as presented below:

  • – Setup. It is identical to the Setup in Theorem 2.

  • – Queries. It is identical to the Queries in Theorem 2.

  • – Challenge. AII sends a receiver’s identity IDr′ and a message pair (msg0′, msg1′) to B. Note that neither the Member secret key query (IDr′) nor the Public key replace query (IDr′, (MPKr′, UPKr′)) has been requested. B randomly chooses a bit b′∈{0,1} and runs the Signcryption algorithm with (msgb′, IDs, IDr′) to produce and return a ciphertext CT=(σ,C,U,IDs,IDr′) to AII.

  • – Guess. AII returns a bit b∈{0,1}. We say that AII wins Gconf if b=b′. The advantage AdvAII is defined as |Pr[b=b′]−1/2|.

Here, let’s compute AdvAII−N that AII wins Gconf without request leak queries. By using Pr[Collision] and Pr[Guess] in the proof of Theorem 3, we get AdvAII−N=Pr[Collision]+Pr[Guess]≦216η2/p+3/p=O(η2/p) that is negligible if η=poly(logp). Subsequently, let us compute the advantage AdvAII that AII wins Gconf when permitted to issue two types of leak queries, namely, Signcryption leak query and Unsigncryption leak query. As in the proof of Theorem 2, AII gets 2ω bits of MSKm (i.e. MSKs or MSKr). By Lemma 2, we obtain AdvAII≦AdvAII−N·22ω≦O((η2/p)·22ω) that is negligible if ω=poly(logp).  □

6Performance Comparisons

Here, let’s evaluate the computation time of our FCLR-CBSC scheme in terms of Initialization, Member secret key generation, Certificate generation, Signcryption and Unsigncryption algorithms. By the simulation results in Xiong and Qin (2015), the notations (i.e. Tbpf and Texp) for two time-consuming computations and their running time are presented in Table 3. Additionally, the running time of the multiplication in G1 or G2 is negligible since it is more slighter than Tbpf and Texp. The simulation results in Xiong and Qin (2015) are evaluated under a PC with an Intel 1.80-GHz i7 CPU and a mobile device with an Intel 624-MHz PXA270 CPU. Meanwhile, the order p of both G1 and G2 is a 512-bit prime security level. The computation costs and the running time of five algorithms in our FCLR-CBSC scheme are listed in Table 4. By Table 4, it is obvious that our scheme performs efficiently on both a PC and a mobile device.

Table 3

Notationsand running time of two time-consuming operations.

OperationsNotationsRunning time on a PCRunning time on a mobile device
Bilinear pairing function eˆTbpf≈20 ms≈96 ms
Exponentiation in G1 or G2Texp≈7 ms≈31 ms
Table 4

Computation costs and running time of five algorithms.

AlgorithmsComputation costsRunning time on a PCRunning time on a mobile device
InitializationTbpf+7Texp69 ms313 ms
Member secret key generationTbpf+3Texp41 ms189 ms
Certificate generation7Texp49 ms217 ms
SigncryptionTbpf+8Texp76 ms344 ms
Unsigncryption7Tbpf+4Texp168 ms796 ms

7Conclusions

A practical FCLR-CBSC scheme was proposed in the paper. As compared with the previously proposed LR-CLSC and CLR-CBSC schemes, our scheme possesses the fully continuous leakage-resilient property. In our scheme, by the key update method participated in the Certificate generation, Signcryption and Unsigncryption algorithms of our scheme, respectively, an adversary is permitted to obtain partial bits of the CA’s secret key, and a sender/receiver’s certificate and secret key. Based on the SCRH and DL assumptions in the GBG model, four security theorems were formally shown that our scheme is EXUF-CLRACMA-secure and INDEN-CLCCA-secure against two types of adversaries (AI and AII) in the CB-PKS setting so that our scheme possesses both authentication of and confidentiality. Finally, performance analysis demonstrated that our scheme is performs efficiently on both a PC and a mobile device.

References

1 

Ali, I., Lawrence, T., Omala, A., Li, F. ((2020) ). An efficient hybrid signcryption scheme with conditional privacy-preservation for heterogeneous vehicular communication in VANETs. IEEE Transactions on Vehicular Technology, 69: (10), 11266–11280.

2 

Al-Riyami, S., Paterson, K. ((2003) ). Certificateless public key cryptography. In: ASIACRYPT’03, LNCS, Vol. 2894: , pp. 452–473.

3 

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

4 

Biham, E., Carmeli, Y., Shamir, A. ((2008) ). Bug attacks. In: Crypto’08, LNCS, Vol. 5157: , pp. 221–240.

5 

Boneh, D., Franklin, M. ((2001) ). Identity-based encryption from the Weil pairing. In: Crypto’01, LNCS, Vol. 2139: , pp. 213–229.

6 

Boneh, D., Boyen, X., Goh, E. ((2005) ). Hierarchical identity-based encryption with constant size ciphertext. In: Eurocrypt’05, LNCS, Vol. 3494: , pp. 440–456.

7 

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

8 

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.

9 

Dodis, Y., Haralambiev, K., Lopez-Alt, A., Wichs, D. ((2010) ). Cryptography resilient to continual memory leakage. In: 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 501–510.

10 

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

11 

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

12 

Gentry, C. ((2003) ). Certificate-based encryption and the certificate revocation problem. In: EUROCRYPT’03, LNCS, Vol. 2656: , pp. 272–293.

13 

Hussain, S., Ullah, I., Khattak, H., Adnan, M., Kumari, S., Ullah, S., Khan, M., Khattak, S. ((2020) ). A lightweight and formally secure certificate based signcryption with proxy re-encryption (CBSRE) for internet of things enabled smart grid. IEEE Access, 8: , 93230–93248.

14 

Katz, J., Vaikuntanathan, V. ((2009) ). Signature schemes with bounded leakage resilience. In: Asiacrypt’09, LNCS, Vol. 5912: , pp. 703–720.

15 

Khan, M., Ullah, I., Nisar, S., Noor, F., Qureshi, I., Khanzada, F., Amin, N. ((2020) ). An efficient and provably secure certificateless key-encapsulated signcryption scheme for flying ad-hoc network. IEEE Access, 8: , 36807–36828.

16 

Kiltz, E., Pietrzak, K. ((2010) ). Leakage resilient Elgamal encryption. In: Asiacrypt’10, LNCS, Vol. 6477: , pp. 595–612.

17 

Kocher, P., Jaffe, J., Jun, B. ((1999) ). Differential power analysis. In: Crypto’99, LNCS, Vol. 1666: , pp. 388–397.

18 

Peng, A.-L., Tseng, Y.-M., Huang, S.-S. ((2021) ). An efficient leakage-resilient authenticated key exchange protocol suitable for IoT devices. IEEE Systems Journal, 15: (4), 5343–5354.

19 

Rivest, R., Shamir, A., Adleman, L. ((1978) ). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21: (2), 120–126.

20 

Tsai, T.-T., Huang, S.-S., Tseng, Y.-M., Chuang, Y.-H., Hung, Y.-H. ((2022) ). Leakage-resilient certificate-based authenticated key exchange protocol. IEEE Open Journal of the Computer Society, 3: , 137–148.

21 

Tseng, Y.-M., Wu, J.-D., Huang, S.-S., Tsai, T.-T. ((2020) ). Leakage-resilient outsourced revocable certificateless signature with a cloud revocation server. Information Technology and Control, 49: (4), 464–481.

22 

Tseng, Y.-M., Chen, J.-L., Huang, S.-S. ((2021) ). A lightweight leakage-resilient identity-based mutual authentication and key exchange protocol for resource-limited devices. Computer Networks, 196: , 108246.

23 

Tseng, Y.-M., Huang, S.-S., Tsai, T.-T., Chuang, Y.-H., Hung, Y.-H. ((2022) ). Leakage-resilient revocable certificateless encryption with an outsourced revocation authority. Informatica, 33: (1), 151–179.

24 

Ullah, I., Alomari, A., Amin, N., Khan, M., Khattak, H. ((2019) ). An energy efficient and formally secured certificate-based signcryption for wireless body area networks with the internet of things. Electronics, 8: (10), 1171.

25 

Ullah, S., Li, X., Lan, Z. ((2020) ). A novel trusted third party based signcryption scheme. Multimedia Tools and Applications, 79: , 22749–22769.

26 

Wu, Y., Gong, B., Zhang, Y. ((2022) ). An improved efficient certificateless hybrid signcryption scheme for internet of things. Wireless Communications and Mobile Computing, 2022: , 6945004.

27 

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

28 

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.

29 

Wu, J.-D., Tseng, Y.-M., Huang, S.-S., Tsai, T.-T. ((2020) a). Leakage-resilient certificate-based key encapsulation scheme resistant to continual leakage. IEEE Open Journal of the Computer Society, 1: , 131–144.

30 

Wu, J.-D., Tseng, Y.-M., Huang, S.-S., Tsai, T.-T. ((2020) b). Leakage-resilient revocable identity-based signature with cloud revocation authority. Informatica, 31: (3), 597–620.

31 

Xiong, H., Qin, Z. ((2015) ). Revocable and scalable certificateless remote authentication protocol with anonymity for wireless body area networks. IEEE Transactions on Information Forensics and Security, 10: (7), 1442–1455.

32 

Yang, Q., Zhou, Y., Yu, Y. ((2019) ). Leakage-resilient certificateless signcryption scheme. In: GLOBECOM Workshops, pp. 1–6.

33 

Zheng, Y. ((1997) ). Digital signcryption or how to achieve cost (signature & encryption) cost (signature)+ cost (encryption). In: Annual International Cryptology Conference, LNCS, Vol. 1294: , pp. 165–179.

34 

Zhou, Y., Yang, B., Zhang, W. ((2016) ). Provably secure and efficient leakage-resilient certificateless signcryption scheme without bilinear pairing. Discrete Applied Mathematics, 204: , 185–202.

35 

Zhou, Y., Xu, Y., Qiao, Z., Yang, B., Zhang, M. ((2021) ). Continuous leakage-resilient certificate-based signcryption scheme and application in cloud computing. Theoretical Computer Science, 860: , 1–22.

Show more