Evolve and Revoke: A Secure and Efficient Conditional Proxy Re-Encryption Scheme with Ciphertext Evolution

1  Introduction

The prevalence of cloud computing [1] and the emergence of various fog computing [2] applications have changed our ways in the utilization, sharing, and value-added creation of information. In diversified Internet of Things (IoT) applications such as intelligent transportation systems [3] and healthcare management systems, IoT devices play a crucial role in the circulation and sharing of gathered information. Specifically, in the healthcare applications, the widespread use of wearable devices and various wireless sensors enables healthcare professionals to remotely monitor patients’ physiological data. The personal health data collected through IoT devices can serve as a valuable resource for medical research.

However, data owners might be concerned about data privacy and confidentiality when sharing their data in clouds. Another challenge is how to revoke user’s access privileges, so as to achieve forward security. Proxy Re-Encryption (PRE) schemes [4–10] are commonly adopted techniques for sharing data in cloud environments. A PRE scheme allows an authorized proxy like a fog node to convert a ciphertext intended for some person into another one designated for the other person. The proxy is viewed as a semi-trusted party and should not be able to learn any information about shared ciphertexts.

In 2007, Canetti and Hohenberger [11] presented the first Chosen-Ciphertext Attack (CCA)-secure PRE mechanism with bidirectionality allowing ciphertext conversion between both parties. Green and Ateniese [12] came up with an identity-based proxy re-encryption (IB-PRE) in the same year. Nevertheless, Weng et al. [13] pointed out that although PRE schemes had been widely used for delegated decryption, traditional PRE mechanisms could not provide fine-grained access control. To cope with this problem, they addressed the concept of conditional proxy re-encryption (C-PRE) in which ciphertexts can only be re-encrypted if received re-encryption key satisfies the predefined condition specified by its data owner. In 2009, Chu et al. [14] presented the conditional proxy broadcast re-encryption (CPBRE) to support broadcast decryption. In 2011, Shao et al. [15] proposed an IB-CPRE system suitable for the fine-grained access control over encrypted emails. In 2018, Zeng and Choo [16] introduced a sender-specified PRE (SS-PRE) which could be viewed as a variant of C-PREs. Their SS-PRE scheme restricts that a proxy can only re-encrypt ciphertexts from a specific sender. This approach effectively addresses the over-delegation problem of PRE.

In 2021, Yao et al. [17] presented a revocable proxy re-encryption scheme providing ciphertext evolution. Their scheme allows a data owner to delegate decryption rights to authorized users and periodically evolve ciphertexts to reach the goal of revoking user. In 2023, Yao et al. [18] came up with an IB-PRE system with the property of single-hop conditional delegation and supports multi-hop ciphertext evolution. Yet, both schemes fail to consider the key-escrow issue in identity-based setting. Combined with ciphertext-policy attribute-based encryption (CP-ABE), Worapaluk and Fugkeaw [19] proposed a blockchain-assisted PRE in 2023. Their scheme supports both user and attribute revocation with auditability. Nevertheless, the blockchain only stores the revoked attribute list, and thus does not achieve genuine ciphertext evolution. Moreover, their scheme lacks both formal security proofs and integrated security analyses of potential information leakage in blockchain-assisted PRE.

In 2025, Singh et al. [20] proposed a lightweight and revocable certificateless public key encryption without bilinear pairings. Although their scheme also offers the characteristic ciphertext evolution, it essentially is not a PRE mechanism and would be not well-suited for flexible data sharing in clouds. Considering the merits of certificateless public systems, Eltayieb et al. [21] proposed a certificateless PRE (CL-PRE) for data sharing in clouds. Nevertheless, their scheme only satisfies the security requirement of chosen plaintext attacks (CPA). Zhou et al. [22] further addressed a certificateless conditional PRE (CL-CPRE) scheme for data sharing in IoT clouds. Although their scheme provides the functionality of ciphertext evolution and dynamic user key-update, it achieves only CPA security and fails to support the user revocation.

Motivation and Contributions

In recent years, fog-assisted PRE schemes [23–26] have gained popularity in data sharing. It enables a data owner to encrypt data and then allows a semi-honest fog node (proxy) to re-encrypt it for authorized recipients. However, existing schemes still present several limitations and research gaps:

•   Incomplete functionality in C-PRE schemes: Prior C-PRE schemes [13–16] have provided fine-grained access control and hence solved the problem of over-delegation. However, they fail to consider the revocation problem and cannot support the functionality of ciphertext evolution, which is important to cloud ciphertext renewal.

•   Unresolved security issues in revocable schemes: Although the scheme introduced by Yao et al. [17] further supports the characteristics of revocability, their identity-based framework still suffers from the key-escrow problem. In a related work, Lin and Chen [23] proposed a revocable IB-PRE scheme for fog computing environments. Nevertheless, we observe that the scheme still has the over-delegation and key-escrow problems and fails to support ciphertext evolution.

To overcome these limitations and address the gaps in existing research, we propose a fog-assisted revocable C-PRE scheme with ciphertext evolution (R-CPRE-CE). Our work is motivated by the need for an integrated and secure mechanism that simultaneously solves the problem of over-delegation, revocability, ciphertext evolution, and key-escrow. The primary contributions of this paper are as follows:

•   Conditional re-encryption with user revocation: The proposed R-CPRE-CE scheme not only incorporates a predefined access condition to prevent over-delegation, but also uses a periodically updated time-key to efficiently revoke a user’s access privileges.

•   Ciphertext evolution for forward security: With ciphertext evolution, our R-CPRE-CE scheme allows cloud ciphertexts to be shared across time periods and fulfills forward security.

•   Elimination of the key-escrow problem: By employing an anonymous key generation technique, our R-CPRE-CE scheme effectively solves the inherent key-escrow problem in identity-based systems.

Although our R-CPRE-CE scheme builds upon similar concepts from previous PRE systems, it offers many advantages over the schemes of Yao et al. [17,18] and the Lin and Chen [23]. Specifically, the identity-based frameworks of Yao et al. [17,18] inherently suffer from the key-escrow problem. In contrast, the proposed R-CPRE-CE scheme eliminates this risk by employing an anonymous key generation technique. Furthermore, compared to the Lin-Chen system [23], our work provides better functionality by incorporating both conditional PRE to prevent over-delegation and a ciphertext evolution mechanism to ensure forward security. Computationally, the proposed system also demonstrates better performance, particularly in terms of the one-time access metric compared to Yao et al. [17], as detailed in Section 5.2.

The remaining parts of this paper are organized below. Section 2 briefly reviews some preliminaries in relation to the proposed scheme. We give the formal security model and definition for the proposed system in Section 3. A concrete R-CPRE-CE scheme is presented in Section 4. We analyze the security and performance of our scheme in Section 5. Finally, a conclusion is made in Section 7.

2  Preliminaries

This section introduces the essential cryptographic backgrounds and computational assumptions.

2.1 Bilinear Pairing

Let G1 and G2 be two cyclic groups of prime order p. Two generators g and g1 belong to G1. A symmetric bilinear pairing e:G1×G1→G2 satisfies the following three properties:

•   Bilinearity: If g∈G1 and a,b∈Zp, the equality e(ga,gb)=e(g,g)ab holds.

•   Non-degeneracy: For generators g,g1∈G1, we have that e(g,g1)≠1.

•   Computability: Let g,g1∈G1 and there exists a polynomial-time algorithm could calculate e(g,g1) efficiently.

2.2 The Problem of Decisional Bilinear Diffie-Hellman (DBDH)

Given (g,gf,gs,gk,γ), where g,gf,gs,gk∈G1, γ∈G2, and f,s,k∈Zp, the problem of DBDH is to determine if γ=e(g,g)fsk in which e:G1×G1→G2 is a symmetric bilinear pairing.

2.3 The Assumption of Decisional Bilinear Diffie-Hellman (DBDH)

The assumption of DBDH holds if any probabilistic polynomial-time adversary 𝒜 has a negligible advantage in solving the DBDH problem. The advantage of adversary 𝒜 is defined as:

Adv(𝒜)=|Pr[𝒜(g,gf,gs,gk,e(g,g)fsk)=1]−Pr[𝒜(g,gf,gs,gk,γ)=1]|≤ε

where ε is negligible.

3  The Proposed Scheme

This section outlines the system model, core algorithms, and security model of the proposed scheme.

3.1 System Model

The proposed R-CPRE-CE system includes three layers of participated parties and an additional Private Key Generator (PKG) for key generation. As shown in Fig. 1, the User Layer transmits the demand for ciphertext via the Proxy Layer to the Cloud Layer. Furthermore, the proxy also obtains re-encryption keys from the data owner, transforms cloud evolved ciphertexts, and forwards the result to users. In the fog computing environment, the proxy is usually composed of a group of distributed fog nodes.

Figure 1: The proposed R-CPRE-CE system model

3.2 Algorithm Definition

The algorithms utilized in the proposed scheme are defined as follows:

1.    Setup (1l)→(PP,Msk): Given a security parameter l, it generates the system’s public parameters PP and a master secret key Msk.

2.    InitialKeyGen(PP,Msk,IDu)→sku: Given PP, Msk, and a user identity IDu, this algorithm generates the user’s initial private key sku.

3.    TimeUpdateKeyGen(PP,Msk,IDu,n)→tku,n: Given PP, Msk, IDu, and a time period n, this algorithm generates a corresponding time-update key tku,n.

4.    Encryption(PP,Y,IDO,skO,n,c,M)→(CTDO,TK): Given PP, a symmetric key Y, a data owner’s identity IDO, his initial private key skO, a time period n, an access condition c, and a message M, this algorithm outputs the original ciphertext CTDO and an evolution parameter TK. The condition c represents a meaningful bit-string such as a keyword, a timestamp or an attribute.

5.    Query(PP,IDR,Mname)→Θ: Given PP, a data user’s identity IDR, and the index of requested file Mname, this algorithm generates the corresponding query token Θ.

6.    ReKeyGen(PP,IDR,n′,skO,skO,n′′,c,Θ)→(AK,TK′O,n′): Given PP, an identity of data user IDR, the current time period n′, the data owner’s initial private key skO and the one skO,n′′ for the time period n′, an access condition c, and the query token Θ, it generates the re-encryption key AK and a corresponding evolution parameter TKO,n′′.

7.    Evolve(PP,CTDO,TK,TK′O,n′)→CTDO′: Given PP, an original ciphertext CTDO, and two evolution parameters (TK, TKO,n′′), it calculates the evolved ciphertext (CTDO′).

8.    Re-Encryption(PP,IDR,AK,CTDO′)→CTDR: Given PP, a data user’s identity IDR, a re-encryption key AK, and the evolved ciphertext CTDO′, it computes the re-encrypted ciphertext CTDR.

9.    Decryption(PP,sku,n′′,CTDO′/CTDR)→M: It can be divided into two cases, i.e., one for the data owner and the other for the data user. In general, given PP, a private key sku,n′′ for the current time period n′, and the evolved ciphertext CTDO′ or the re-encrypted ciphertext CTDR, the algorithm derives the symmetric key Y to recover the message M.

Correctness: The correctness property guarantees that (1) a legitimate user holding the valid private key for the current time period n′ can successfully decrypt the ciphertext, and (2) a revoked user whose identity has been invalidated is unable to correctly decrypt the ciphertext. Concretely speaking, given the public parameters (PP), a symmetric key (Y), current time period (n′), a user identity (IDu) with his/her initial private key (sku) and the one (sku,n′′) for the time period n′, an access condition (c), a re-encryption key (AK), evolution parameters (TK, TKO,n′′), a message (M), and Rn′, the set of revoked identities at time period n′, the proposed system should satisfy the following conditions:

•   Correctness of decryption:

For all users whose identities have not been revoked at time period n′, i.e., ∀ IDu∉ Rn′, the system ensures the correctness of decryption as follows:

–   Decryption by the Data Owner

(CTDO,TK)←Encryption(PP,Y,IDO,skO,n,c,M)

CTDO′←Evolve(PP,CTDO,TK,TKO,n′′)

Pr[Decryption1(CTDO′,skO,n′′)=M]=1

–   Decryption by the Data User

CTDR←Re−Encryption(PP,IDR,AK,CTDO′)

Pr[Decryption2(CTDR,skR,n′′)=M]=1

•   Correctness of revocation:

For all users whose identities have been revoked at time period n′, i.e., ∀ IDu∈Rn′, the system ensures the correctness of revocation as follows:

Pr[Decryption2(CTDR,skR,n)=M]≈0

3.3 Security Model

This section defines the security game of indistinguishability against adaptively chosen identity and chosen ciphertext attacks (IND-PrID-CCA), where PrID stands for Proxy Identity, between a probabilistic polynomial-time (PPT) adversary 𝒜 and a challenge ℬ. We will show that the proposed system is formally proven secure in the random oracle model under the DBDH assumption.

Definition 1: (IND-PrID-CCA) If no PPT adversary 𝒜 can win the following game against a challenger ℬ with non-negligible advantage, the proposed scheme achieves IND-PrID-CCA security

GameIND−PrID−CCA:

Setup. The challenger ℬ takes a security parameter l as input, runs Setup(1l) to generate public parameters PP and Msk. Then he sends PP to 𝒜.

Phase 1. The adversary 𝒜 adaptively makes polynomially many queries as follows:

–   Initial Private Key Query: 𝒜 selects an identity IDu and sends it to ℬ who runs InitialKeyGen(PP,Msk,IDu) to generate the initial private key sku which is then returned to 𝒜.

–   Time-Update Key Query: 𝒜 sends an identity IDu and a time period n to the challenger ℬ who runs TimeUpdateKeyGen(PP,Msk,IDu,n) to generate the time-update key tku,n which is then returned to 𝒜.

–   Re-Encryption Key Query: 𝒜 selects two valid user identities (IDO,IDR), a time period n′, an access condition c, and an index of requested file Mname to ℬ. The challenger ℬ first runs InitialKeyGen(PP,Msk,IDO) and TimeUpdateKeyGen(PP,Msk,IDO,n′) to obtain the private key skO,n′′ for the time period n′. Then ℬ runs Query(PP,IDR,Mname) to obtain a query token Θ. Finally, the re-encryption key AK could be returned to 𝒜 by performing ReKeyGen(PP,IDR,n′,skO,skO,n′′,c,Θ).

–   Decryption Query: 𝒜 provides a valid user identity IDu and a ciphertext CTDR associated with a time period n′ for ℬ. The challenger ℬ first runs InitialKeyGen(PP,Msk,IDu) and TimeUpdateKeyGen(PP,Msk,IDu,n′) to obtain the private key sku,n′′ for the time period n′. Then ℬ runs Decryption(PP,sku,n′′,CTDR) to recover M and returns it to 𝒜.

Challenge. 𝒜 defines two symmetric keys (Y0,Y1) of equal length, a target user identity ID∗, a time period n∗, an access condition c∗, and the message M∗. Then ℬ utilizes (PP,Yλ,ID∗,n∗,c∗,M∗) where λ∈R{0,1} to generate a ciphertext CT∗=(C1∗,C2∗,C3∗,C4∗,CT1∗) and return it to 𝒜.

Phase 2. Upon getting CT∗, 𝒜 executes the queries of Phase 1, but the restrictions are as follows:

–   Initial private key queries for the target identity ID∗ are disallowed.

–   Whenever 𝒜 acts as a revoked user (holds its initial private key), it cannot query a time-update key of the target period n∗.

–   Re-encryption key queries involving ID∗ as an input are disallowed.

–   Decryption queries involving (ID∗, CT∗) as an input are disallowed.

–   The number of queries is bounded by qpk for initial private key queries, qtk for time-update key queries, qde for decryption queries, and qpr for re-encryption key queries.

Guess. When Phase 2 is finished, the adversary 𝒜 outputs a bit λ′. If λ′=λ, 𝒜 wins the game. The advantage of 𝒜 is defined as:

Adv(𝒜)=|Pr[λ′=λ]−12|

In the security model, we defined several query restrictions for the adversary capabilities to correctly reflect a realistic attack scenario while maintaining tractability of the security proof. For instance, in phase 2, an initial private key query for the target identity is disallowed. This is a standard assumption in IND-PrID-CCA security games, since the adversary holding the target private key can easily decrypt the ciphertext and trivially break the security. This restriction ensures that the adversary’s success advantage does not rely on possessing the target secret key. Furthermore, a decryption query involving the challenge ciphertext is disallowed. Such a restriction is crucial for modeling chosen-ciphertext attacks (CCA) where an adversary cannot directly submit the challenge ciphertext to decryption oracles. It simulates a circumstance where attackers cannot access the victim’s decryption device, but must rely on other queries to gain information.

Although these restrictions are standard in formal security models, it is important to consider their alignment with real world attack scenarios, particularly in a fog computing environment with multiple semi-trusted proxies. In practice, an adversary might compromise one or more fog nodes and attempt to use them as re-encryption or decryption oracles. Our security model implicitly addresses this by providing the adversary with more query capabilities. For instance, the adversary can request re-encryption keys for any non-challenge identity and decrypt any ciphertext except for the specific challenge ciphertext itself. This simulates a powerful attacker who has significant control over the network but has not yet compromised the specific target’s final decryption device or process. The core security of the challenge ciphertext relies on the cryptographic hardness of the underlying problem, even if the adversary can observe and manipulate other related ciphertexts through compromised proxies. To the best of our knowledge, no model can perfectly capture all real-world nuances. The IND-PrID-CCA model provides a well-accepted abstraction for demonstrating security against adaptive attacks in such distributed environments.

4  Construction of Proposed Scheme

Building upon the previously defined algorithms, we now present a concrete construction.

•   Setup(1l)→(PP,Msk)

Given a security parameter l, the Private Key Generator (PKG) outputs a master secret key Msk and the public parameters PP={G1,G2,g,p,e,Mpk,H1,H2,H3,H4,E(⋅),D(⋅)} defined as follows:

(1)   G1 and G2 are two prime-order multiplicative groups of the order p, g is a generator of G1, and e is a bilinear mapping function, e:G1×G1→G2.

(2)   A random value α∈Zp is selected and set as the master secret key, i.e., Msk=α. The master public key Mpk is then computed as Mpk=g1=gα.

(3)   H1, H2, H3, and H4 are four one-way hash functions satisfying that H1:{0,1}∗→G1, H2:{0,1}∗→G1, H3:{0,1}∗→G1, and H4:G2→G1.

(4)   E(⋅) and D(⋅) denote symmetric encryption and decryption functions, respectively.

•   InitialKeyGen(PP,Msk,IDu)→sku

The initial private key is generated through the interactive steps:

(1)   The registering user IDu selects random values ru,Zu∈Zp and computes:

Zu=gZu(1)

Ru=Zu⋅H2(IDu∥ru)(2)

(2)   IDu sends (IDu,Ru) to the PKG which then computes:

sku′=Ruα=(Zu⋅H2(IDu∥ru))α(3)

(3)   PKG returns sku′ to the user IDu who will compute:

sku1=sku′/g1zu=H2(IDu∥ru)α(4)

sku2=ru(5)

(4)   The user IDu sets his/her initial private key sku=(sku1,sku2).

(5)   The sku could be further verified for correctness using the following equation:

e(sku1,g)=e(H2(IDu∥ru),g1)(6)

•   TimeUpdateKeyGen(PP,Msk,IDu,n)→tku,n

The time-update key is generated through the interactive steps:

(1)   IDu sends (IDu,n) to the PKG which then computes:

tku,n=H1(IDu∥n)α(7)

(2)   PKG returns the time-update key tku,n to IDu.

(3)   The tku,n could be further verified for correctness using the following equation:

e(tku,n,g)=e(H1(IDu∥n),g1)(8)

(4)   IDu finally derives the private key sku,n for the time period n as

sku,n=sku1⋅tku,n=(H1(IDu∥n)⋅H2(IDu∥ru))α(9)

•   Encryption(PP,Y,IDO,skO,n,c,M)→(CTDO,TK)

Let M=(m1,m2,…,ms) be a message associated with the file index Mname, Y a chosen symmetric key, and c∈{0,1}∗ a predefined access condition. The Data Owner IDO selects a random value k∈Zp to compute the original ciphertext CTDO for M as follows:

(1)   Compute

C1=Y⋅e((H1(IDO∥n)⋅H2(IDO∥rO))k⋅skO2,g1)(10)

C2=gk⋅skO2(11)

C3,n=(H1(IDO∥n))skO2(12)

C4=H3(IDO∥c)k⋅skO2(13)

(2)   Compute an evolution parameter as

TK=g1k(14)

(3)   Set CT0=(C1,C2,C3,C4) and compute

CT1=(E(Y,m1),E(Y,m2),…,E(Y,ms))(15)

(4)   Output CTDO=(CT0,CT1)

The data owner IDO will store Mname with the corresponding access condition c, and sends (IDO,n,CTDO,TK,Mname) to the proxy. Upon receiving it, the proxy keeps (IDO,Mname) and forwards (IDO,n,CTDO,TK,Mname) to the cloud for storage.

•   Query(PP,IDR,Mname)→Θ

When a data user IDR requests the ciphertext stored in the cloud with respect to the file index Mname, he selects a random value ρ∈Zp to compute

Q=gρ(16)

Then (IDR,Q,Mname) is sent to the nearby proxy which generates a query token Θ=(IDR,Q) delivered to the data owner IDO.

•   ReKeyGen(PP,IDR,skO,skO,n′′,n′,c,Θ)→(AK,TK′O,n′)

After receiving the token Θ, IDO derives the re-encryption key AK by the following steps:

(1)   Select random values ω,x,π∈Zp.

(2)   Compute the hash value of the access condition c as

W=H3(IDO∥c)(17)

(3)   Compute the re-encryption key AK=(A1,A2,A3,A4) as

A1=Wx⋅g1ω(18)

A2=(skO,n′′)⋅g1ωH4(e(H1(IDR∥n′)⋅Qπ,g1))(19)

A3=e(gπ,g1)(20)

A4=gx(21)

(4)   Compute the evolution parameter TKO,n′′ for the current time period n′ as

TKO,n′′=(H1(IDO∥n′))skO2(22)

Subsequently, the data owner sends (AK,TKO,n′′) to the proxy which also transmits (IDO,TKO,n′′,Mname) to the cloud for ciphertext evolution.

•   Evolve(PP,CTDO,TK,TK′O,n′)→CTDO′

Upon receiving (IDO,TKO,n′′,Mname), the cloud server (CS) searches for stored {CTDO=(CT0,CT1),TKO,n} using Mname and then

(1)   Compute

C1′=C1⋅e(TKO,n′′/C3,n,TK)(23)

where CT0=(C1,C2,C3,C4).

(2)   Set the evolved ciphertext as CTDO′={CT0′=(C1′,C2,C3,C4),CT1} and deliver it to the proxy.

•   Re-Encryption(PP,IDR,AK,CTDO′)→CTDR

When the proxy gains the re-encryption key AK=(A1,A2,A3,A4) and TKO,n′′ from IDO and the evolved ciphertext CTDO′ from the CS, it performs the re-encryption process below:

(1)   Compute C1′ as

C1′′=C1′⋅e(A1,C2)/e(C4,A4)(24)

At this stage, the ciphertext and re-encryption key must associate with the same access condition c for the proxy to generate a valid re-encrypted ciphertext CTDR. In other words, this mechanism restricts the re-encryption privilege of the semi-trusted proxy, preventing it from illegally re-encrypting other unauthorized ciphertexts stored by the data owner in the CS.

(2)   Compute C2′′,C3′′,and C4′′ as

C2′′=C2=gk⋅skO2(25)

C3′′=A2=(skO,n′′)⋅g1ω/H4(e(H1(IDR∥n′)⋅Qπ,g1))(26)

C4′′=A3=e(gπ,g1)(27)

(3)   Output the ciphertext CTDR={CT0′′=(C1′′,C2′′,C3′′,C4′′),CT1} and send it to IDR. Fig. 2 illustrates the ciphertext evolution and re-encryption process across time periods.

Figure 2: Illustration of ciphertext evolution and re-encryption process across time periods

•   Decryption(PP,sku,n′′,CTDO′/CTDR)→M

The decryption process is classified into two cases. The first is performed by a data owner IDO with the following steps:

(1)   Computes the decryption key

Y=C1′′e(C2,skO,n′′)(28)

The correctness of Eq. (28) could be easily confirmed, since

C1′′e(C2,skO,n′′)=Y⋅e((H1(IDO∥n′)⋅H2(IDO∥rO))k⋅skO2,g1)e(gk⋅skO2,(H1(IDO∥n′)⋅H2(IDO∥rO))α)=Y.

(2)   Recover the message M by computing

{Mi=D(Y,E(Y,mi))}i=1,…,s(29)

The second is performed by the data user IDR with the following steps:

(1)   Compute the parameter E as

E=C3′′⋅H4(C4′′ρ⋅e(skR,n′′,g)e(H2(IDR∥rR),g1))=(skO,n′′)⋅g1ω(30)

(2)   Compute the decryption key

Y=C1′′e(E,C2′′)(31)

The correctness of Eq. (31) could be easily confirmed, since

C1′′e(E,C2′′)=Y⋅e((H1(IDO∥n′)⋅H2(IDO∥rO))k⋅skO2,g1)⋅e(g1ω,gk⋅skO2)e((H1(IDO∥n′)⋅H2(IDO∥rO))α⋅g1ω,gk⋅skO2)=Y⋅e((H1(IDO∥n′)⋅H2(IDO∥rO))k⋅skO2,g1)⋅e(g1ω,gk⋅skO2)e((H1(IDO∥n′)⋅H2(IDO∥rO))α,gk⋅skO2)⋅e(g1ω,gk⋅skO2)=Y

(3)   Recover the message M with Eq. (29).

5  Security Proof and Comparison

Based on previously defined security model, this section provides the formal security proof for the proposed R-CPRE-CE scheme. Meanwhile, some comparisons with similar systems are also made.

5.1 Security Proof

We show that the proposed R-CPRE-CE system is provably secure in the security notion of IND-PrID-CCA as Theorem 1. We prove the security of our scheme using a reductionist argument in the random oracle model (ROM). The core idea is to demonstrate that if a PPT adversary can break the IND-PrID-CCA security of our scheme, then we can construct an algorithm to solve the DBDH problem, which is assumed to be computationally intractable. In the ROM, an adversary must query a random oracle for a result rather than computing it independently. This model is a widely used idealization in cryptography and can simplify the proof of complex cryptographic protocols. When instantiating the random oracles with real world hash functions like Secure Hash Algorithm 3 (SHA-3), we follow common cryptographic practices to mitigate potential attacks. Specifically, the inputs to the hash functions are carefully structured, e.g., concatenating identities with nonces or other distinct values, to prevent collision attacks and other structural vulnerabilities that could arise from a naive implementation. Thus, we believe that such an instantiation will not introduce new weaknesses into our scheme. However, a true random oracle does not exist in the real world. A ROM-proven-secure scheme could also be insecure in the standard model. Extending our current mechanism to fulfill standard model security requires significant modifications and inevitably increases the computation complexity. Consequently, we leave the adaptation to achieve standard model security as our future work.

Theorem 1: (Proof of IND-PrID-CCA)

Let H1,H2, and H3 be random oracles. Under the assumption of DBDH, the constructed R-CPRE-CE system fulfills the IND-PrID-CCA security. Concretely speaking, if there exists any PPT adversary 𝒜 breaking the IND-PrID-CCA security of our proposed scheme with a non-negligible advantage ε, under the query limits qtk, qde, and qpr, an algorithm ℬ that is able to solve the DBDH problem with the non-negligible advantage ε′ where

ε′≥εe(qtk+qpr+qde+1)

and e denotes the base of the natural logarithm.

Proof: Let (g,gf,gs,gk,γ) be a DBDH instance provided to ℬ, in which f,s,k∈Zp and γ∈G2. The proof shows how a challenger ℬ takes the advantage of adversary 𝒜 to decide whether γ equals to e(g,g)fsk or not.

Setup. The challenger ℬ first initializes Setup(1l) to generate PP={e,G1,G2,g,p,Mpk,H4,E(⋅),D(⋅)} and sends PP to the adversary 𝒜. The master public key Mpk is defined as P=gs, and the challenger ℬ does not know Msk=s.

Phase 1. The adversary 𝒜 adaptively makes polynomially many queries as follows:

–   H1(IDu∥n) Oracle: For any query to H1(IDu∥n), the challenger ℬ checks the maintained H1-table, i.e., HT1 using the index (IDu,n). If not found, ℬ randomly selects a bit bt∈{0,1} such that Pr[bt=1]=ψ, where ψ will be decided later. If bt=0, ℬ computes HO1=(gf)s1, in which s1∈Zp. If bt=1, ℬ calculates HO1=gs1. Finally, HT1 is updated as HT1∪{(IDu,n,bt,s1,HO1)}, and HO1 is returned to 𝒜.

–   H2(IDu∥ru) Oracle: For any query to H2(IDu∥ru), ℬ checks the maintained H2-table, i.e., HT2 using the index (IDu,ru). If not found, ℬ calculates HO2=gs2 in which s2∈Zp. Finally, HT2 is updated as HT2∪{(IDu,ru,s2,HO2)}, and HO2 is returned to 𝒜.

–   H3(IDu∥c) Oracle: For any query to H3(IDu∥c), ℬ checks the maintained H3-table, i.e., HT3 using the index (IDu,c). If not found, ℬ calculates HO3=gs3 in which s3∈Zp. Finally, HT3 is updated as HT3∪{(IDu,c,s3,HO3)}, and HO3 is returned to 𝒜.

–   Initial Private Key Query: For any initial private key queries of an identity IDu, the challenger ℬ uses IDu as an index to search for an entry (IDu,ru,s2,HO2) in HT2. If not found, ℬ simulates a query to the random oracle H2 on behalf of 𝒜 and then computes sku1=Ps2, sku2=ru, and sku=(sku1,sku2). Finally, ℬ returns sku to 𝒜.

–   Time-Update Key Query: For any time-update key queries of (IDu,n), the challenger ℬ searches the HT1 for an entry (IDu,n,bt,s1,HO1). If not found, ℬ simulates a query to the random oracle H1 on behalf of 𝒜. If bt=0, ℬ aborts. Otherwise, it computes tku,n=Ps1 and returns it to the adversary 𝒜.

–   Re-Encryption Key Query: For any re-encryption key queries of (IDO,IDR,n,c,Mname) where IDO≠IDR, and IDR is a non-revoked user, ℬ simulates the H3(IDO∥c) oracle, the initial private key, and the time-update key queries to obtain the user private key skO,n for the time period n, and then retrieves the corresponding entries from HT1, HT2, and HT3. If bt=0, the query is aborted. If not, ℬ chooses random values ρ,ω,x,π∈Zp to compute Q=gρ, W=HO3, A1=Wx⋅Pω, A2=(skO,n)⋅PωH4(e(H1(IDR∥n)⋅Qπ,P)), A3=e(gπ,P), and A4=gx. Finally, ℬ gives the re-encryption key AK=(A1,A2,A3,A4) to 𝒜.

–   Decryption Query: For any decryption queries of (IDu,CTDR,n′) where IDu is a valid user, ℬ simulates the initial private key and the time-update key queries to obtain the private key sku,n′′ for the time period n′. However, if the corresponding entry (IDu,n′,bt,s1,HO1) in HT1 satisfies that bt=0, it will be aborted. Otherwise, ℬ is capable of retrieving another entry (IDu,ru,s2,HO2) from HT2 and then calculating the private key sku,n′′=Ps1+s2 to run the decryption algorithm and return its result to 𝒜.

Challenge. 𝒜 chooses two symmetric keys (Y0,Y1) of equal length, the target user identity IDu∗, a time period n∗, an access condition c∗, and the message M∗=(m1∗,m2∗,…,ms∗). The challenger ℬ takes the input of (PP,Yλ,IDu∗,n∗,c∗,M∗) where λ∈R{0,1} to generate a challenge ciphertext CT∗=(C1∗,C2∗,C3∗,C4∗,CT1∗) for the adversary 𝒜 as follows:

1.    It can be assumed, without loss of generality, that 𝒜 has already chosen a random ru and queried the corresponding random oracles of IDu∗. If bt∗=1, the challenger ℬ aborts.

2.    Otherwise, ℬ can retrieve the associated (s1,s2,s3) from maintained tables and compute

C1∗=Yλ⋅γs1⋅ru⋅e((gk)s2⋅ru,P)

C2∗=(gk)ru

C3∗=(gf)s1⋅ru

C4∗=(gk)s3⋅ru

CT1∗=(E(Yλ,m1∗),E(Yλ,m2∗),…,E(Yλ,ms∗))

Phase 2. After getting the challenge ciphertext CT∗, the adversary 𝒜 will go on Phase 1 queries under the constraints defined in Definition 1.

Guess. At the end of Phase 2, 𝒜 outputs a bit λ′. If λ′=λ, the challenger ℬ outputs 1, indicating γ=e(g,g)fsk. Otherwise, it outputs 0, indicating γ≠e(g,g)fsk.

Analysis: The confidentiality of the proposed scheme is directly guaranteed by the hardness of the DBDH assumption. The core of this proof lies in how the challenger ℬ uses the ability of adversary 𝒜 to compromise confidentiality to solve the given DBDH instance. According to the challenge phase, as long as e(g,g)fsk=γ, the generated ciphertext CT∗ is correct, which indicates that the winning probability of 𝒜 is non-negligible. Namely, Adv(𝒜)=|Pr[λ′=λ]−1/2|≥ε. Conversely, whenever e(g,g)fsk≠γ, the ciphertext is invalid, and 𝒜 gains no advantage in suspecting the right λ. Consequently, Adv(𝒜)=|Pr[λ′=λ]|=1/2. Let Pr[Perfect] be the probability that the entire simulation game does not abort. The advantage of the challenger ℬ in solving the DBDH problem is thus given by the inequality below:

|Pr[(g,gf,gs,gk,e(g,g)fsk)=1]−Pr[(g,gf,gs,gk,γ)=1]|

≥|(1/2+ε)−1/2|⋅Pr[Perfect]=ε⋅Pr[Perfect]

To better estimate Pr[Perfect], we analyze the following event probabilities:

–   Pr[¬TkQ]: All time-update key queries are handled without aborting.

–   Pr[¬PrQ]: All re-encryption key queries are handled without aborting.

–   Pr[¬DeQ]: All decryption queries are handled without aborting.

–   Pr[¬Ch]: The challenge phase completes without aborting.

Since Pr[¬TkQ], Pr[¬PrQ], Pr[¬DeQ], and Pr[¬Ch] are independent events, the probability Pr[Perfect] can be expressed as

Pr[¬TkQ]⋅Pr[¬PrQ]⋅Pr[¬DeQ]⋅Pr[¬Ch]

To be precise, in any time-update key query, ℬ terminates when bt=0, meaning Pr[¬TkQ]≤Ψqtk. In any re-encryption key query, ℬ terminates when bt=0, meaning Pr[¬PrQ]≤Ψqpr. In any decryption query, ℬ terminates when bt=0, meaning Pr[¬DeQ]≤Ψqde. In the challenge phase, ℬ aborts provided that bt∗=1, i.e., Pr[¬Ch]≤(1−Ψ). By combining these probability events, we obtain

Pr[Perfect]≤(Ψ)qtk⋅(Ψ)qpr⋅(Ψ)qde⋅(1−Ψ)=(Ψ)qtk+qpr+qde⋅(1−Ψ)

By calculation, when Ψ is maximized at 1−1/(qtk+qpr+qde+1), the probability that the simulation process is perfect without aborting is at least 1/e(qtk+qpr+qde+1) where e is the base of natural logarithm. Therefore, the advantage ε′ of the challenger ℬ in breaking the problem of DBDH could be written as