We formalise certificateless public-key updatable encryption (CLUE), a primitive that has yet to be defined in the public-key updatable encryption (PKUE) literature. Traditionally, PKUE allows outsourcing ciphertext key rotation to an untrusted host using a special token such that the ciphertext is updated to a distinct period known as an epoch. Key to security, the host does not learn anything about the underlying plaintext. In practice, applying PKUE in a public key infrastructure (PKI) requires trust in a third party producing the epoch public and secret keys, which is a clear violation of privacy if the key generator behaves maliciously or is corrupted. In this paper, we are concerned with reducing the trust in the PKI key generator and our chosen solution is to formalise our novel CLUE primitive, from PKUE and certificateless public key encryption (CL-PKE) primitives, as well as a security framework for CLUE. Moreover, we modify the certificateless encryption scheme proposed by Libert et al. (PKC 2006) and demonstrate the provable security of our CLUE scheme. To do so, we follow the modular approach given by Klooß et al. (EUROCRYPT'19) to reduce the security analysis to the standard setting.
Introduced by [
In practice, the public-key infrastructure (PKI) in which PKUE will be used as a building
block is a lot more involved than simply considering a data owner and a server. Traditionally,
digital certificates are associated with the public and secret key pairs to authenticate the
data owner (individual/organisation) in a public-key encryption scheme. An approach to
simplifying the public key and certificate management in a PKI is identity-based encryption
(IBE), a primitive introduced by [
To summarise, we deem CL-PKE to be a suitable candidate for a revised version of the PKUE primitive formally called certificateless public-key updatable encryption (CLUE). We do so with care considering both the security requirements of traditional CL-PKE (including inside and outside adversaries) and the intricacies of security modelling in PKUE arising from information inferred from corrupted tokens and epoch keys. We stress the CLUE primitive applies to any setting in which KGC generating cryptographic keys and the server performing updates are separate entities that cannot be trusted or instances where individuals want to reduce trust in the KGC. Therefore, our main motivation in defining CLUE is to support long-term outsourced storage in an environment with reduced trust, with the intent to preserve privacy on behalf of the data owner.
Contributions Our contributions are threefold: first, we introduce and formalise CLUE, a
certificateless public-key updatable encryption primitive, in Section 2. Secondly, we define
and model a new security notion (CLUE-IND-RCCA security) in Section 3 which captures the
indistinguishability of freshly generated and updated ciphertexts. Next, we propose a concrete
CLUE scheme in Section 4 which is an adaptation of the pairing-based CL-PKE scheme given
in [
Notation In the following, we define a certificateless public-key updatable encryption primitive. The scheme is defined by epochs of time in which the keys, token and ciphertext are associated with a given epoch in time and the ciphertext update algorithm rotates the ciphertext to encryption under a new epoch key using the token. In line with the literature, we denote the current epoch as , and use the subscript notation if we define multiple epochs at once with the range of time = {0, . . . , max} such that max is the last epoch in the scheme. Further, (, +1) are two consecutive epochs for any ∈ N and ˜ represents the challenge epoch in security games.
Definition 1 (CLUE). Given epochs identified by the space ℐ, plus the
message space ℳ, and ciphertext space , let a certificateless
publickey updatable encryption scheme be a tuple of nine algorithms ΠCLUE =
(Setup, Partial-SK-Extract, Set-Secret-Value, Set-SK, Set-PK, Set-Token, Enc, Dec, Upd) defined as
follows,
• Setup(1 ) →$ (, ) : The key generation centre (KGC) takes security parameter 1
as input and outputs public parameters and master secret key .
• Partial-SK-Extract(, , ID) → D : the KGC takes the public parameters , the
master secret key and identity ID ∈ ℐ for epoch as input and outputs partial
secret key D.1
• Set-Secret-Value(, ) →$ : the data owner takes the public parameters and the
current epoch that they are running the algorithm for as inputs and randomly chooses
secret value .
• Set-SK(, D, ) → : the data owner takes the public parameters , partial secret
key D and secret value as inputs and computes their secret key .
• Set-PK(, ) → : the data owner takes the public parameters and secret value
as inputs and computes their public key .
• Set-Token(, (, )) → Δ+1 : the data owner takes the public parameters plus
the current epoch public key and secret keys (, ) as inputs and computes (for epoch
identifier ID ) the update token Δ+1 to epoch ( + 1) which is sent to the server.
• Enc(, , , ID) →$ {, ⊥} : the data owner takes the public parameters ,
message ∈ ℳ, public key and identity ID as inputs and outputs the ciphertext
∈ for epoch or failure symbol ⊥ if public key does not have the correct
form.
• Dec(, , ) → {, ⊥} : the data owner takes the public parameters , ciphertext
and secret key as inputs and outputs the message or failure symbol ⊥.
• Upd(, , Δ+1) → {+1, ⊥} : the server takes the public parameters , ciphertext
and update token Δ+1 as inputs and outputs the updates ciphertext +1 for epoch
( + 1) or failure symbol ⊥.
1This algorithm is run once for each epoch and the KGC distributes the partial secret keys to the data owner in a
secure manner [
Definition 2 (Correctness). Given security parameter ∈ N, a certificateless updatable encryption scheme (ΠCLUE) formalised in Definition 1 is correct if, for any message ∈ ℳ and for any ∈ {1, . . . , max}, ∈ {0, . . . , max} with max > , there exists a negligible function negl such that the following holds with overwhelming probability.
⎡(, ) ← $ Setup(1 ); Pr ⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢D←←← $←$SSPeEeattnr--ctPSi(Kaecl(-rS,eKt,--VE,axl)tu;reaΔ(c,tI( D←,)S,);;et-To←,kIeDSne()t;-S,K(,,D+,1););⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥ ≥ 1 − negl(1 ). ⎣⎢{ ← Upd(, − 1 , Δ ) : ∈ { + 1, . . . , max}}; ⎦⎥
Dec(, max , max) = ⎤
Defining the security of a cryptographic primitive is often a complex process. For CLUE we want to combine the approach to security taken in CL-PKE with the intricacies of UE security modelling to capture the indistinguishability of ciphertexts deriving from fresh encryption and updates. The notion of security we settle on is CLUE-IND-RCCA (Definition 4) and we give an intuition of this notion in the full version of our work. Next, we provide an overview of the security experiment in which the adversary has access to oracles and the challenger records essential lists, both of which are key to capturing security given the challenging nuances of the update functionality in CLUE.
High-Level Idea We define ciphertext indistinguishability against replayable chosen ciphertext attacks for the CLUE primitive. This notion is formalised in Definition 1 through the security experiment ExpCΠLCULUEE-,IND-RCCA(1 ) given in Figure 2. Informally, the game is between a challenger and an adversary such that the latter can query the oracles detailed in Figures 1. To win the experiment, must distinguish the underlying message of the challenge ciphertext without possession of the corresponding epoch secret key, given only access to the relevant oracles and a challenge ciphertext. Security is satisfied if the adversary’s advantage in succeeding is negligible, as detailed in Definition 4.
Lists To initialise the CLUE-IND-RCCA security experiment, the challenger runs Init(1 )
which outputs the global state (GS) oracles have access to throughout. At the start, GS :=
(, 0, 0, Δ0, L, 0) contains the public parameters generated by the CLUE setup
algorithm; epoch secret and public keys (0, 0) respectively; initial update token ⊥ → Δ0;
set L := {ℒ, ℳ* , , , * } containing initially empty lists that the challenger is required to
maintain throughout the experiment in order to prevent from trivially winning and setting the
current epoch 0 → . List ℒ is maintained to keep a log of updated versions of honestly-generated
ciphertexts, and the corresponding epoch, that the adversary learns through calls to the relevant
oracle. List ℳ* tracks the challenge messages the adversary sends to the challenger. Further,
list records the epoch(s) in which the adversary has obtained an update token and tracks
the epoch(s) in which the adversary has obtained an epoch secret key or epoch partial secret
key. List tracks the epochs in which an adversary obtains an updated version of the
challengeciphertext through querying the ciphertext update oracle. We must extend this list to capture
additional information necessary to prevent an adversary from trivially winning in the security
experiment for Definition 4. Following the approach taken in [
Oracles Figure 1 provides formal descriptions of the initialisation phase a challenger runs
and the oracles an adversary has access to during the security experiment for Definition 4.
For clarity, we provide intuition and a definition of an important predicate utilised in UE
security modelling to prevent trivial wins. Informally, to prevent the decryption of an updated
challenge ciphertext, irrespective of whether the UE scheme is probabilistic or deterministic, a
useful predicate defined in [
for a valid ID0 ∈ ℐ 0 ← $ Set-Secret-Value(, 0) 0 ← Set-SK(, ID0, 0) 0 ← Set-PK(, 0) Δ0 ← ⊥ ← 0 L ∈ ∅ for the set of lists L := {ℒ, ℳ* , , , * } return GS GS := (, 0, 0, Δ0, L, 0) Dec() ← Dec(, , ) if ( ∈ ℳ* ) ∨ (isChallenge(, ) = true) then
return test else
return Upd( ) for = {+1, . . . , } do ← Upd(, , Δ ) ← return ℒ ← ℒ ∪ { (, )} if (Dec(, , ) = ∈ (isChallenge(, ) = true) then * ← * ∪ {} ℳ* ) ∨ Next() +1 ← $ Set-Secret-Value(, + 1) +1 ← Set-SK(, ID, +1) +1 ← Set-PK(, +1) Δ+1 ← Set-Token(, (, )) Update GS (, +1, +1, Δ+1, L, + 1) if ( ∈ ) ∨ ((, ) ∈ ℒ) then
(′, + 1) ← $ Upd(, Δ+1, ) ℒ ← ℒ ∪ { ( + 1, ′)} Corrupt-Token(* ) if * ≥ then
return ⊥ else
return Δ* ← ∪ { * } Corrupt-key(* ) if * ≥ then
return ⊥ else return *
* } ← ∪ { PSKE(* ) if ((* ≥ ) ∨ (* ∈ )) then
return ⊥ else
return D ← ∪ { * } = {Dec, Next, Upd, Corrupt-Token, Corrupt-Key}.
Recall that the CL-PKE adversarial model focuses on two types of adversaries, namely, an outside and inside (honest but curious KGC) attacker. We explicitly define the oracles in the set that these distinct adversaries possess during our security game. Explicitly, adversary has no access to the master secret key, however, they have access to all of the oracles described above. Conversely, adversary has implicit access to a master secret key, which means they can compute partial secret keys for their own use given the master secret key and therefore do not need access to oracle PSKE. Thus, has access to the set
ExpCΠLCULUEE-,IND-RCCA,(1 ) Initialise Global State GS ← $ Init(1 ); GS = (, 0, 0, Δ0, L, 0); ID ← Partial-SK-Extract(, , ID) for a valid epoch identity ID ∈ ℐ ← $ Set-Secret-Value(, ) ← Set-SK(, ID, ) ← Set-PK(, ) (0, 1, ) ← (, ) Some state information s if |0| ̸= |1| ∨ {0, 1} ̸∈ ℳ ∨ (0 = 1) then
return ⊥ else ← {$ 0, 1}, ← $ Enc(, , , ID), ℳ* ← ℳ * ∪ (0, 1); ← ∪ { };˜ ← { } ′ ← (, , ), if ( ∩ * = ∅) then
return ′
Else abort.
CLUE-IND-RCCA secure if an adversary participating in the security game of Figure 2 has a negligible advantage in 1 , defined as follows:
AdvCΠLCULUEE-,IND-RCCA(1 ) =|Pr[ExpCΠLCULUEE-,IND-RCCA,1(1 ) = 1]−
Pr[ExpCΠLCULUEE-,IND-RCCA,0(1 ) = 1]| ≤ negl(1 ).
In this Section, we present a concrete pairing-based CLUE scheme (ΠCLUE). Primarily, we chose
to present a concrete CLUE scheme to demonstrate that ΠCLUE is comparably eficient to other
certificateless updatable PKE schemes such as the CL-PRE scheme from [
Our choice for the update mechanism is a key-homomorphic pseudorandom function (KH-PRF)
FDDH. We chose this KH-PRF, not only for its desired homomorphic properties but also for its
use in previous UE schemes [
Definition 5 (CLUE Construction). Given security parameter ∈ N, epochs, identity space ℐ = {0, 1}* , message space ℳ = G1 and ciphertext space = G1 × G1, let groups (G1, G2) be cyclic (multiplicative) groups of prime order q (a 1 -bit prime). We define the CLUE scheme ΠCLUE = (Setup, Partial-SK-Extract, Set-Secret-Value, Set-SK, Set-PK, Set-Token, Enc, Dec, Upd) as follows, • Setup(1 ) →$ (, ) : Given the security parameter as input, the setup algorithm defines a symmetric bilinear map ^ : (G1 × G1) → G2 which is a Type pairing in Definition 6, Appendix B. The following choices are made.
1. Choose an arbitrary value ∈ G1 to be the generator of G1 such that we have the element = ^(, ) ∈ G2. 2. Given ← $ Z* chosen uniformly at random, set the master secret key = and set ′ = ∈ G1. 3. Choose three cryptographic hash functions used as follows2: ℋ1 : {0, 1}* → Z* ; ℋ2 : G2 → G1; ℋ3 : {0, 1}* → Z* .
Set = (, 1 , G1, G2, , ′, ^, ℋ1, ℋ2, ℋ3, , ℳ, ) to be the public
parameters and master secret key = ∈ Z* .
• Partial-SK-Extract(, , ID) → ID : Given ID ∈ {0, 1}* input as the identifier for
epoch , set the partial secret key as D = (( + ℋ1(ID))− 1 · ) ∈ G1. Secretly send
ID to the server over a secure broadcast channel.3
2Importantly, hash function ℋ2 difers from the CL-PKE scheme in [
Given step 1 in which it is determined that = , the following can be computed
2 · FDDH(− , ) = ∈ G1. Correctness holds as follows: 2 · FDDH(− , ) =
· FDDH(, ) · FDDH(− , ) = · FDDH( − , ) = .5 Note that
the data owner randomly chose during encryption, so knowledge of this enables
the computation of the message ( )− := .6
3. Use the epoch secret-key and public parameters (, ) in addition to the previous
two steps to compute = ℋ3(< ||||ID >) ∈ Z*. Message is accepted if
1 = (ℋ1(ID) + ′) from the computed value , else failure (⊥) is output.
• Upd(, , Δ+1) → {+1, ⊥} : recall the update token and ciphertext Δ+1 :=
(Δ′+1, +1), = (1, 2) respectively. The server must perform the following steps:
1. Check +1 = 1G2. Abort the update and output failure symbol ⊥ if this does not
hold. Note, validity holds with an honestly generated epoch public key: +1 =
(+1) = ()+1 = (1G2)+1.
2. Compute = ^(1, ID) = ∈ G2. See step 1 of the decryption algorithm for
correctness. Set 1+1 := 1.
4Let < · > denote an encoding of the bracket contents to a string {0, 1}* .
5To see the penultimate equation diferently, given the definition of the KH-PRF: FDDH( − , ) =
6Tℋh2e(tec)hn− ique=ofℋus2i(ng)t0he=coidrGre1s.ponding randomness for a given epoch to decrypt the ciphertext is utilised in
various UE schemes including [
We note that only the second component (2) of the ciphertext gets updated and the first
component (1) remains the same, in line with previous identity-based approaches used in
CL-PKE literature [
Conclusion In our first contribution of this paper, we formally defined a novel certificateless
public-key updatable encryption primitive CLUE to mitigate the risk of a malicious key
generation centre, when considering applications of a PKUE primitive in a public key infrastructure.
In our second contribution, we provided a security framework to model the first notion of
ciphertext indistinguishability in certificateless public key updatable schemes. In particular,
security against replayable chosen-ciphertext attacks from an adaptive adversary. Our third
contribution was to propose a concrete CLUE scheme (ΠCLUE) derived from a modified
pairingbased CL-PKE scheme [
Updatable encryption (UE) schemes [
Proxy re-encryption (PRE), first introduced by [
In this Section, we explain the intuition and assumptions required such that ciphertext indistinguishability is achieved for construction ΠCLUE from Section 4. We state further definitions and assumptions are required for security analysis, given in Section C, and note that proofs of the lemmas are omitted due to lack of space. To start, the first definition presented is used when defining the pairing map used in the construction ΠCLUE.
Definition 6 (Bilinear Maps). Let additive groups G1, G2 have prime order , such that G1 is
generated by , G2 is generated by , and multiplicative group G is also of prime order . A
pairing is a bilinear map ^ : G1 × G2 → G with the following properties,
1. Bilinearity: ∀, ∈ F* , ∀ ∈ G1, ∈ G2 : ^(, ) = ^(, );
2. Non-Degeneracy: ^ ̸= 1, that is, the mapping is not the identity map;
3. Computability: there exists an eficient algorithm to determine the output of map ^.
Definition 6 can be classified into three types, in line with [
Next we introduce the p-Bilinear Difie Hellman Inversion (p-BDHI) problem, which is used to prove the security of our construction in Section 4. The p-BDHI problem is stated as follows: Definition 7 (p-BDHI Problem). Given map ^ defined as in Definition 6 over groups (G1, G2, G ) and given {, , 2, . . . , } ∈ G1+1, the p-BDHI problem is considered hard if it is computationally intractable to compute ^(, )1/ ∈ G2 in polynomial time. Key-Homomorphic PRFs The update feature in CLUE is attained using a collision-resistant homomorphic hash function in the encryption process, which we model as a random oracle. For our construction, we assume the hash function ℋ2 : G2 → G1 is homomorphic, and we consider building the hash function from a key-homomorphic PRF.
Definition 8 (Key-Homomorphic PRF [
2. For every 1, 2 ∈ and every ∈ : F(1, ) ⊗ F(2, ) = F((1 ⊕ 2), ). Lemma 1. Given the KH-PRF used in ΠCLUE defined as FDDH : Z × G2 → G1 with = (Z, ⊕ ), = (G2, ⊗ ) the additive and multiplicative groups of prime order q respectively such that (G1, G2) are cyclic (multiplicative) groups of prime order , evaluation of the KH-PRF is FDDH(, ) = ℋ2(). Further, FDDH(1 + 2, ) = FDDH(1, ) · FDDH(1, ). That is, FDDH satisfies Definition 8. Then FDDH is a secure KH-PRF in the random oracle model assuming the hardness of the decisional Difie-Hellman problem in G1.
Updatable Encryption Assumptions Construction CLUE is designed with deterministic ciphertext updates, therefore, the security of ΠCLUE assumes the properties of randomnesspreserving re-encryption; the underlying CL-PKE scheme ΠPKE is tidy and simulatable token generation. The formal definitions of these properties are utilised in the security proof of Theorem 1 to argue that the indistinguishability of fresh and updated ciphertexts is satisfied. We present them below. Due to lack of space, we omit the proofs of Lemmas and defer the reader to the full version of this paper.
Given the updatable scheme CLUE is designed for deterministic updates, an updated ciphertext is randomness-preserving assuming CLUE encrypts with uniformly chosen randomness (Enc(, , , ID) and Enc(, , , ID; ) for uniformly chosen are identically distributed). If for all (, ) ← $ Setup(1 ); for all old and new epoch key pairs := (, ), +1 := (+1, +1) generated from running the Partial-SK-Extract, Set-Secret-Value, Set-SK, Set-PK algorithms in epoch and ( + 1) respectively; for all valid ciphertexts ∈ and for all tokens Δ+1← Set-Token(, (, )), we then have the following:
Enc(, Dec(, , ), +1, ID) = Upd(, , Δ+1).
Lemma 2. The scheme ΠCLUE satisfies randomness preserving re-encryption given in Definition 9.
Definition 10 (Randomness-Recoverable Tidy Encryption Scheme). A publickey encryption scheme is called randomness-recoverable if there is an associated eficient deterministic algorithm RDec(, , ) for epoch such that ∀(, ), , :RDec(, , Enc(, , ; )) = (, ). We call a randomnessrecoverable public-key encryption scheme tidy if ∀(, , ) :
RDec(, , ) = (, ) =⇒ Enc(, , ; ) = .
Lemma 3. The CL-PKE scheme ΠPKE implicit in ΠCLUE satisfies the randomness recoverable tidy encryption property given in Definition 10.
Assumption 1 (Reversible Update Tokens). Update token Δ− 1 is called a reverse token of Δ if for every pair of epoch keys (old = (old , old ), = (new , new )) in keyspace such that Δ ∈ supp(Set-Token(, old , new )), we have reversible token Δ− 1 ∈ supp(Set-Token(, new , old ).
Definition 11 (Simulatable Token Generation). The CLUE scheme ΠCLUE defined in Section 4 has simulatable token generation if the following properties hold: 1. There exists a PPT algorithm denoted Sim-Set-Token() which samples a pair of update tokens (Δ, Δ− 1) of the token and reverse token respectively. 2. For arbitrary (fixed) old := (old , old ) which is generated from running the Partial-SK-Extract, Set-Secret-Value, Set-SK, Set-PK algorithms, the following token (Δ) distributions are the same: • Distribution induced by running (Δ, · ) ← $ Sim-Set-Token(); • For epoch key new := (new , new ) the distribution is induced by running (Δ, · ) ← $ Set-Token(, old , new ).
token generation given in Definition 11. simulatable token and reversible
In this Section, we provide a sketch analysis of security for our construction ΠCLUE. Due to
lack of space, we provide an overview of our proof, deferring the reader to the full version
of this paper for a detailed proof of correctness and security. Observe that when proving
CLUE-IND-RCCA security of ΠCLUE to achieve ciphertext indistinguishability, we assume several
properties regarding the underlying building blocks. This proof method follows directly from
[
Theorem 1. Given ΠCLUE is a deterministic updatable encryption scheme satisfying randomnesspreserving tidy updates (Lemma 2); simulatable token generations (Lemma 4) and the underlying certificateless encryption scheme ΠPKE satisfies CLUE-IND-RCCA in an isolated epoch, then the construction ΠCLUE satisfies security notion CLUE-IND-RCCA assuming the intractability of the p-BDHI problem formalised in Definition 7 (Appendix B).
Sketch Proof. We take a two-step modular approach in proving Theorem 1, adapting
the techniques of [
In the second step of the proof we look at proving the security of the updatable construction
ΠCLUE over multiple epochs. In more detail, this part of the proof sees a series of hybrid games
H built for epochs ∈ {0, . . . , ^ + 1} of ΠCLUE where ^ is the maximum number of epochs
in which an adversary can query oracles (Figure 1). Suppose we have adversary against
ΠCLUE, defined in Section 3. We use to construct an adversary ℬ against the standard CL-PKE
construction ΠPKE [