Fast and Secure Updatable Encryption

Boyd, Colin; Davies, Gareth T.; Gjøsteen, Kristian; Jiang, Yao

doi:10.1007/978-3-030-56784-2_16

Colin Boyd¹⁰,
Gareth T. Davies ORCID: orcid.org/0000-0002-5935-5725¹¹,
Kristian Gjøsteen¹⁰ &
…
Yao Jiang¹⁰

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 12170))

Included in the following conference series:

Annual International Cryptology Conference

3794 Accesses
26 Citations
3 Altmetric

Abstract

Updatable encryption allows a client to outsource ciphertexts to some untrusted server and periodically rotate the encryption key. The server can update ciphertexts from an old key to a new key with the help of an update token, received from the client, which should not reveal anything about plaintexts to an adversary.

We provide a new and highly efficient suite of updatable encryption schemes that we collectively call $\mathsf {SHINE}$. In the variant designed for short messages, ciphertext generation consists of applying one permutation and one exponentiation (per message block), while updating ciphertexts requires just one exponentiation. Variants for longer messages provide much stronger security guarantees than prior work that has comparable efficiency. We present a new confidentiality notion for updatable encryption schemes that implies prior notions. We prove that $\mathsf {SHINE}$ is secure under our new confidentiality definition while also providing ciphertext integrity.

You have full access to this open access chapter, Download conference paper PDF

CCA Updatable Encryption Against Malicious Re-encryption Attacks

(R)CCA Secure Updatable Encryption with Integrity Protection

Updatable Encryption with Post-Compromise Security

1 Introduction

The past decades have demonstrated clearly that key compromise is a real threat for deployed systems. The standard technique for mitigating key compromise is to regularly rotate the encryption keys – generate new ones and switch the ciphertexts to encryption under the new keys. Key rotation is a well-established technique in applications such as payment cards [9] and cloud storage [16].

For a local drive or server, key rotation is feasible by decrypting and re-encrypting with a new key, since symmetric encryption operations are fast and parallelizable and bandwidth is often plentiful. When ciphertext storage has been outsourced to some (untrusted) cloud storage provider, bandwidth is often considerably more expensive than computation, and even for small volumes of data it may be prohibitively expensive to download, re-encrypt and upload the entire database even once. This means that key rotation by downloading, decrypting, re-encrypting and reuploading is practically infeasible.

An alternative approach to solving this problem is to use updatable encryption (UE), first defined by Boneh et al. [3] (henceforth BLMR). The user computes a token and sends it to the storage server. The token allows the server to update the ciphertexts so that they become encryptions under some new key. Although the token clearly depends on both the old and new encryption keys, knowledge of the token alone should not allow the server to obtain either key. In a typical usage of UE, the cloud storage provider will receive a new token on a periodic basis, and the provider then updates every stored ciphertext. The time period for which a given key is valid for is called an epoch.

In the past few years there has been considerable interest in extending the understanding of UE. A series of prominent papers [3, 12, 17, 21] have provided both new (typically stronger) security definitions and concrete or generic constructions to meet their definitions. (We make a detailed comparison of related work in Sect. 1.1 next.) An important distinction between earlier schemes is whether or not the token (and in particular its size) depends on the ciphertexts to be updated (and in particular the number of ciphertexts). Schemes for which a token is assigned to each ciphertext are ciphertext-dependent and were studied by Everspaugh et al. [12] (henceforth EPRS). If the token is independent of the ciphertexts to be updated, such as in BLMR [4], we have a ciphertext-independent^{Footnote 1} scheme. A clear and important goal is to limit the bandwidth required and so, in general, one should prefer ciphertext-independent schemes. Thus, as with the most recent work [17, 21], we focus on such schemes in this paper. The ciphertext update procedure, performed by the server, may be deterministic or randomized – note that in the latter case the server is burdened with producing (good) randomness and using it correctly.

Despite the considerable advances of the past few years, there remain some important open questions regarding basic properties of UE. In terms of security, various features have been added to protect against stronger adversaries. Yet it is not obvious what are the realistic and optimal security goals of UE and whether they have been achieved. In terms of efficiency, we only have a few concrete schemes to compare. As may be expected, schemes with stronger security are generally more expensive but it remains unclear whether this cost is necessary. In this paper we make contributions to both of these fundamental questions by defining new and stronger security properties and showing that these can be achieved with more efficient concrete UE schemes.

Security. The main security properties that one would expect from updatable encryption are by now well studied; however the breadth of information that is possible to protect in this context is more subtle than at first glance. Consider, for example, a journalist who stores a contact list with a cloud storage provider. At some point, the storage is compromised and an adversary recovers the ciphertexts. At this point, it may be important that the cryptography does not reveal which of the contacts are recent, and which are old. That is, it must be hard to decide if some ciphertext was recently created, or if it has been updated from a ciphertext stored in an earlier epoch.

So how do we define realistic adversaries in this environment? A natural first step for security in updatable encryption is confidentiality of ciphertexts – given a single ciphertext, the adversarial server should not be able to determine anything about the underlying plaintext. The security model here must take into account that this adversary could be in possession of a number of prior keys or update tokens, and snapshot access to the storage database in different epochs. The next step is to consider unlinkability between different epochs arising from the ciphertext update procedure: given a ciphertext for the current epoch, the adversary should not be able to tell which ciphertext (that existed in the previous epoch) a current ciphertext was updated from. Both of these properties can be naturally extended to chosen-ciphertext (CCA) security via provision of a decryption oracle.

These steps have been taken by prior work, but unfortunately even a combination of these properties is not enough to defend against our motivating example. Previous security definitions cannot guarantee that the adversary is unable to distinguish between a ciphertext new in the current epoch and an updated ciphertext from an earlier epoch. We give a single new security property that captures this requirement and implies the notions given in prior work. Therefore we believe that this definition is the natural confidentiality property that is required for updatable encryption.

An additional factor to consider is integrity: the user should be confident that their ciphertexts have not been modified by the adversarial server. While prior work has shown how to define and achieve integrity in the context of updatable encryption, a composition result of the style given by Bellare and Namprempre for symmetric encryption [2] – the combination of CPA security and integrity of ciphertexts gives CCA security – has been missing. We close this gap.

Efficiency and Functionality. Although UE is by definition a form of symmetric key cryptography, techniques from asymmetric cryptography appear to be needed to achieve the required functionality in a sensible fashion. All of the previous known schemes with security proofs use exponentiation in both the encryption and update functions, even for those with limited security properties. Since a modern database may contain large numbers of files, efficiency is critical both for clients who will have to encrypt plaintexts initially and for servers who will have to update ciphertexts for all of their users.

To bridge the gap between the academic literature and deployments of encrypted outsourced storage, it is crucial to design fast schemes. We present three novel UE schemes that not only satisfy our strong security definitions (CCA and ciphertext integrity), but in the vast majority of application scenarios are also at least twice as fast (in terms of computation each message block) as any previous scheme with comparable security level.

The ciphertext expansion of a scheme says how much the size of a ciphertext grows compared to the size of the message. For a cloud server that stores vast numbers of files, it is naturally crucial to minimize the ciphertext expansion rate. It is also desirable to construct UE schemes that can encrypt arbitrarily large files, since a client might want to upload media files such as images or videos. Prior schemes that have achieved these two properties have only been secure in comparatively weak models. Our construction suitable for long messages – enabling encryption of arbitrarily large files with almost no ciphertext expansion – is secure in our strong sense and is thus the first to bridge this gap.

1.1 Related Work

Security Models for UE. We regard the sequential, epoch-based corruption model of Lehmann and Tackmann [21] (LT18) as the most suitable execution environment to capture the threats in updatable encryption. In this model, the adversary advances to the next epoch via an oracle query. It can choose to submit its (single) challenge when it pleases, and it can later update the challenge ciphertext to the ‘current’ epoch. Further, the adversary is allowed to adaptively corrupt epoch (i.e. file encryption) keys and update tokens at any point in the game: only at the end of the adversary’s execution does the challenger determine whether a trivial win has been made possible by some combination of the corruption queries and the challenge.

LT18 introduced two notions: $\mathsf {IND} \text {-}\mathsf {ENC}$ asks the adversary to submit two plaintexts and distinguish the resulting ciphertext, while possibly having corrupted tokens (but of course not keys) linking this challenge ciphertext to prior or later epochs. Further, they introduced $\mathsf {IND} \text {-}\mathsf {UPD}$: the adversary provides two ciphertexts that it received via regular encryption-oracle queries in the previous epoch, and has to work out which one has been updated. They observed that plaintext information can be leaked not only through the encryption procedure, but also via updates. For schemes with deterministic updates, the adversary would trivially win if it could acquire the update token that takes the adversarially-provided ciphertexts into the challenge epoch, hence the definition for this setting, named $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UPD} $, is different from that for the randomized setting, named $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UPD} $.

LT18’s $\mathsf {IND} \text {-}\mathsf {UPD}$ definition was not the first approach to formalizing the desirable property of unlinkability of ciphertexts, which attempts to specify that given two already-updated ciphertexts, the adversary cannot tell if the plaintext is the same. Indeed EPRS ($\mathsf {UP}\text {-}\mathsf {REENC}$) and later KLR19 ($\mathsf {UP}\text {-}\mathsf {REENC}\text {-}\mathsf {CCA}$) also considered this problem, in the ciphertext-dependent update and CCA-secure setting respectively. KLR19 [17], § Appendix A] stated that “an even stronger notion [than $\mathsf {IND} \text {-}\mathsf {UPD} $] might be desirable: namely that fresh and re-encrypted ciphertexts are indistinguishable... which is not guaranteed by $\mathsf {UP}\text {-}\mathsf {REENC}$” – we will answer this open question later on in our paper.

In the full version of their work [4], BLMR introduced a security definition for UE denoted $\mathsf {update}$ – an extension of a model of symmetric proxy re-encryption. This non-sequential definition is considerably less adaptive than the later work of LT18, since the adversary’s key/token corruption queries and ciphertext update queries are very limited. Further, they only considered schemes with deterministic update algorithms.

EPRS [12] provided (non-sequential) definitions for updatable authenticated encryption, in the ciphertext-dependent setting. Their work (inherently) covered CCA security and ciphertext integrity (CTXT). These definitions were ambiguous regarding adaptivity: these issues have since been fixed in the full version [13].

KLR19 attempted to provide stronger security guarantees for ciphertext-independent UE than LT18, concentrating on chosen-ciphertext security (and the weaker replayable CCA) in addition to integrity of plaintexts and ciphertexts. We revisit these definitions later on, and show how a small modification to their INT-CTXT game gives rise to natural composition results.

In practice, LT18’s $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UPD} $ definition insists that the ciphertext update procedure $\mathsf {Upd}$ requires the server to generate randomness for updating each ciphertext. Further, a scheme meeting both $\mathsf {IND} \text {-}\mathsf {ENC}$ and $\mathsf {IND} \text {-}\mathsf {UPD}$ can still leak the epoch in which the file was uploaded (the ‘age’ of the ciphertext). While it is arguable that metadata is inherent in outsourced storage, the use of updatable encryption is for high-security applications, and it would not be infeasible to design a system that does not reveal meta-data, which is clearly impossible if the underlying cryptosystem reveals the meta-data.

Recent work by Jarecki et al. [15] considers the key wrap** entity as a separate entity from the data owner or the storage server. While this approach seems promising, their security model is considerably weaker than those considered in our work or the papers already mentioned in this section: the adversary must choose whether to corrupt the key management server (and get the epoch key) or the storage server (and get the update token) for each epoch, and thus it cannot dynamically corrupt earlier keys or tokens at a later stage.

Constructions of Ciphertext-Independent UE. The initial description of updatable encryption by Boneh et al. [3] was motivated by providing a symmetric-key version of proxy re-encryption (see below). BLMR imagined doing this in a symmetric manner, where each epoch is simply one period in which re-encryption (rotation) has occurred. Their resulting scheme, denoted $\mathsf {BLMR}$, deploys a key-homomorphic PRF, yet the nonce attached to a ciphertext ensures that $\mathsf {IND} \text {-}\mathsf {UPD}$ cannot be met (the scheme pre-dates the $\mathsf {IND} \text {-}\mathsf {UPD}$ notion).

The symmetric-Elgamal-based scheme of LT18, named $\mathsf {RISE}$, uses a randomized update algorithm and is proven to meet $\mathsf {IND} \text {-}\mathsf {ENC}$ and $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UPD} $ under DDH. These proofs entail a seemingly unavoidable loss – a cubic term in the total number of epochs – our results also have this factor. LT18 also presented an extended version of the scheme by BLMR, denoted $\mathsf {BLMR}+$, where the nonce is encrypted: they showed that this scheme meets a weak version of $\mathsf {IND} \text {-}\mathsf {UPD}$.

The aim of KLR19 was to achieve stronger security than BLMR, EPRS and LT18 in the ciphertext-independent setting: in particular CCA security and integrity protection. They observed that the structure of $\mathsf {RISE}$ ensures that ciphertext integrity cannot be achieved: access to just one update token allows the storage provider to construct ciphertexts of messages of its choice. Their generic constructions, based on encrypt-and-MAC and the Naor-Yung paradigm, are strictly less efficient than $\mathsf {RISE}$. We show how to achieve CCA security and integrity protections with novel schemes that are comparably efficient with $\mathsf {RISE}$.

Related Primitives. Proxy re-encryption (PRE) allows a ciphertext that is decryptable by some secret key to be re-encrypted such that it can be decrypted by some other key. Security models for PRE are closer to those for encryption than the strictly sequential outsourced-storage-centric models for UE, and as observed by Lehmann and Tackmann [21] the concepts of allowable corruptions and trivial wins for UE need considerable care when translating to the (more general) PRE setting. Unlinkability is not necessarily desired in PRE – updating the entire ciphertext may not be essential for a PRE scheme to be deemed secure – thus even after conversion to the symmetric setting, prior schemes [1, 7] cannot meet the indistinguishability requirements that we ask of UE schemes. Recent works by Lee [20] and Davidson et al. [10] have highlighted the links between the work of BLMR and EPRS and PRE, and in particular the second work gives a public-key variant of the (sequential) $\mathsf {IND} \text {-}\mathsf {UPD}$ definition of LT18. Myers and Shull [22] presented security models for hybrid proxy re-encryption, and gave a single-challenge version of the $\mathsf {UP}\text {-}\mathsf {IND} $ notion of EPRS. While the models are subtly different, the techniques for achieving secure UE and PRE are often similar: in particular rotating keys via exponentiation to some simple function of old and new key. Further, the symmetric-key PRE scheme of Sakurai et al. [25] is at a high level similar to $\mathsf {SHINE}$ (their all-or-nothing-transform as an inner layer essentially serves the same purpose as the ideal cipher in $\mathsf {SHINE}$), but in a security model that does not allow dynamic corruptions.

Tokenization schemes aim to protect short secrets, such as credit card numbers, using deterministic encryption and deterministic updates: this line of work reflects the PCI DSS standard [9] for the payment card industry. Provable security of such schemes was initially explored by Diaz-Santiago et al. [11] and extended to the updatable setting by Cachin et al. [6]. While much of the formalism in the model of Cachin et al. has been used in recent works on UE (in particular the epoch-based corruption model), the requirements on ciphertext indistinguishability are stronger in the UE setting, where we expect probabilistic encryption of (potentially large) files.

1.2 Contributions

Our first major contribution is defining the $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $ security notion, for ${(\mathsf {xx},\mathsf { atk})\in \{(\mathsf {det},\mathsf {CPA}),(\mathsf {rand},\mathsf {CPA}),(\mathsf {det},\mathsf {CCA})\}}$, and comprehensively analyzing its relation to other, existing^{Footnote 2} security notions ($\mathsf {xx} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf { atk} $, $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf { atk} $). Our single definition requires that ciphertexts output by the encryption algorithm are indistinguishable from ciphertexts output by the update algorithm. We show that our new notion is strictly stronger even than combinations of prior notions, both in the randomized- and deterministic-update settings under chosen-plaintext attack and chosen-ciphertext attack. This not only gives us the unlinkability desired by prior works, but also answers the open question posed by KLR19 mentioned on page 4. Figure 13 describes the relationship between our new notion $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $ and prior notions.

We slightly tweak KLR19’s definition of CTXT and CCA for UE and prove that ${\mathsf {det} \mathsf {IND} \text {-}{\mathsf {yy}}\text {-}\mathsf {CPA} ~+~\mathsf {INT} \text {-}\mathsf {CTXT} ~\Rightarrow ~\mathsf {det} \mathsf {IND} \text {-}{\mathsf {yy}}\text {-}\mathsf {CCA}}$ for $\mathsf {yy} \in \{\mathsf {UE}, \mathsf {ENC}, \mathsf {UPD} \}$. Combining this result with the relations from $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $ above, we thus show that the combination of $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ and $\mathsf {INT} \text {-}\mathsf {CTXT} $ yields $\mathsf {det} \mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf {CCA} $ for all $\mathsf {yy} \in \{\mathsf {UE}, \mathsf {ENC}, \mathsf {UPD} \}$.

Our second major contribution is in designing a new, fast updatable encryption scheme $\mathsf {SHINE}$. Our scheme is based on a random-looking permutation combined with the exponentiation map in a cyclic group, and comes in a number of variants: $\mathsf {SHINE0}$, $\mathsf {MirrorSHINE}$ (in our full version [5]) and $\mathsf {OCBSHINE}$, for small messages, medium-sized messages and arbitrarily large messages respectively. In Fig. 1, we provide a comparison of security, ciphertext expansion and efficiency between our new schemes and those from prior literature. We also further the understanding of schemes with deterministic update mechanisms. In particular, we identify the properties that are necessary of such schemes to meet a generalized version of our $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $ notion. Another important contribution is that we further improve on the existing epoch insulation techniques that have been used to create proofs of security in the strong corruption environment we pursue. These have been shown to be very useful for studying updatable encryption schemes, and we expect our new techniques to be useful in the future.

1.3 Further Discussion

We have had to make a number of practical design decisions for our new UE scheme $\mathsf {SHINE}$. The main idea is to permute the (combination of nonce and) message and then exponentiate the resulting value, with different mechanisms for enforcing ciphertext integrity depending on the flavor that is being used (which is in turn defined by the desired message length). In this subsection we give some motivation for why we believe that these choices are reasonable.

Deterministic Updates. Since we will require indistinguishability of ciphertexts, we know that the UE encryption algorithm should be randomized. The update algorithm may or may not be randomized, however. All known schemes indicate that randomized updates are more expensive than deterministic updates, but there is a small, well-understood security loss in moving to deterministic updates: an adversary with an update token in an appropriate epoch can trivially distinguish between an update of a known ciphertext and other ciphertexts in the next epoch. As a result, in the $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ case the adversary is only forbidden from obtaining one token compared to $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $. Furthermore, UE schemes with randomized updates cannot achieve CTXT and CCA security, which is possible for the deterministic-update setting. We believe that the minor CPA security loss is a small price to pay for stronger security (CTXT and CCA) and efficiency gain, in particular to reduce computations in the UE encryption and update algorithms and also improve ciphertext expansion.

Limited Number of Epochs. In many applications that we would like to consider, the user of the storage service will control when updates occur (perhaps when an employee with access to key material leaves the organisation, or if an employee loses a key-holding device): this indicates that the total number of key rotations in the lifetime of a storage system might be numbered in the thousands, and in particular could be considerably smaller than the number of outsourced files.

2 Preliminaries

Pseudocode ${\mathbf{return } ~ b'{\mathop {=}\limits ^{?}}b}$ is used as shorthand for ${\mathbf{if } ~ b'=b~\mathbf{then } ~\mathbf{return } ~1}$ // $\mathbf{else } ~\mathbf{return } ~0$, with an output of 1 indicating adversarial success. We use the concrete security framework, defining adversarial advantage as probability of success in the security game, and avoid statements of security with respect to security notions. In the cases where we wish to indicate that notion A implies notion B (for some fixed primitive), i.e. an adversary’s advantage against B carries over to an advantage against A, we show this by bounding these probabilities.

We follow the syntax of prior work [17], defining an Updatable Encryption ($\mathsf {UE}$) scheme as a tuple of algorithms $\{\mathsf {UE}.\mathsf {KG},\mathsf {UE}.\mathsf {TG},\mathsf {UE}.\mathsf {Enc},\mathsf {UE}.\mathsf {Dec},\mathsf {UE}.\mathsf {Upd} \}$ that operate in epochs, these algorithms are described in Fig. 2. A scheme is defined over some plaintext space $\mathcal {MS}$, ciphertext space $\mathcal {CS}$, key space $\mathcal {KS}$ and token space $\mathcal {TS}$. We specify integer $n+1$ as the (total) number of epochs over which a UE scheme can operate, though this is only for proof purposes. Correctness [17] is defined as expected: fresh encryptions and updated ciphertexts should decrypt to the correct message under the appropriate epoch key.

In addition to enabling ciphertext updates, in many schemes the token allows ciphertexts to be ‘downgraded’: performing some analog of the $\mathsf {UE}.\mathsf {Upd} $ operation on a ciphertext $\mathrm {C}$ created in (or updated to) epoch $\mathsf {e} $ yields a valid ciphertext in epoch $\mathsf {e} \text {-}1$. Such a scheme is said to have bi-directional ciphertext updates. Furthermore, for many constructions, the token additionally enables key derivation, given one adjacent key. If this can be done in both directions – i.e. knowledge of $\mathrm {k} _\mathsf {e} $ and $\varDelta _{\mathsf {e} +1}$ allows derivation of $\mathrm {k} _{\mathsf {e} +1}$ AND knowledge of $\mathrm {k} _{\mathsf {e} +1}$ and $\varDelta _{\mathsf {e} +1}$ allows derivation of $\mathrm {k} _{\mathsf {e}}$ – then such schemes are referred to by LT18 as having bi-directional key updates. If such derivation is only possible in one ‘direction’ then the scheme is said to have uni-directional key updates. Much of the prior literature on updatable encryption has distinguished these notions: we stress that all schemes and definitions of security considered in this paper have bi-directional key updates and bi-directional ciphertext updates.

3 Security Models for Updatable Encryption

We consider a number of indistinguishability-based confidentiality games and integrity games for assessing security of updatable encryption schemes. The environment provided by the challenger attempts to give as much power as possible to adversary $\mathcal {A} $. The adversary may call for a number of oracles, and after $\mathcal {A} $ has finished running the challenger computes whether or not any of the actions enabled a trivial win. The available oracles are described in Fig. 3. An overview of the oracles $\mathcal {A} $ has access to in each security game is provided in Fig. 4.

Confidentiality. A generic representation of all confidentiality games described in this paper is detailed in Fig. 5. The current epoch is advanced by an adversarial call to $\mathcal {O}{.}\mathsf {Next} $ – simulating $\mathsf {UE}.\mathsf {KG} $ and $\mathsf {UE}.\mathsf {TG} $ – and keys and tokens (for the current or any prior epoch) can be corrupted via $\mathcal {O}{.}\mathsf {Corr} $. The adversary can encrypt arbitrary messages via $\mathcal {O}{.}\mathsf {Enc} $, and update these ‘non-challenge’ ciphertexts via $\mathcal {O}{.}\mathsf {Upd} $. In CCA games, the adversary can additionally call decryption oracle $\mathcal {O}{.}\mathsf {Dec} $ (with some natural restrictions to prevent trivial wins). At some point $\mathcal {A} $ makes its challenge by providing two inputs, and receives the challenge ciphertext – and in later epochs can receive an updated version by calling $\mathcal {O}{.}\mathsf {Upd} {\tilde{\mathrm {C}}} $ (computing this value is actually done by $\mathcal {O}{.}\mathsf {Next} $, a call to $\mathcal {O}{.}\mathsf {Upd} {\tilde{\mathrm {C}}} $ returns it). $\mathcal {A} $ can then interact with its other oracles again, and eventually outputs its guess bit. The flag $\mathsf {phase}$ tracks whether or not $\mathcal {A} $ has made its challenge, and we always give the epoch in which the challenge happens a special identifier $\tilde{\mathsf {e}} $. If $\mathcal {A} $ makes any action that would lead to a trivial win, the flag $\mathsf {twf}$ is set as 1 and $\mathcal {A}$ ’s output is discarded and replaced by a random bit. We follow the bookkee** techniques of LT18 and KLR19, using the following sets to track ciphertexts and their updates that can be known to the adversary.

$\mathcal {L}$: List of non-challenge ciphertexts (from $\mathcal {O}{.}\mathsf {Enc} $ or $\mathcal {O}{.}\mathsf {Upd} $) with entries of form $(\mathtt {c},\mathrm {C},\mathsf {e})$, where query identifier $\mathtt {c}$ is a counter incremented with each new $\mathcal {O}{.}\mathsf {Enc} $ query.
$\tilde{\mathcal {L}}$: List of updated versions of challenge ciphertext (created via $\mathcal {O}{.}\mathsf {Next} $, received by adversary via $\mathcal {O}{.}\mathsf {Upd} {\tilde{\mathrm {C}}} $), with entries of form $(\tilde{\mathrm {C}},\mathsf {e})$.

Further, we use the following lists that track epochs only.

$\mathcal {C}$: List of epochs in which adversary learned updated version of challenge ciphertext (via $\mathsf {CHALL} $ or $\mathcal {O}{.}\mathsf {Upd} {\tilde{\mathrm {C}}} $).
$\mathcal {K}$: List of epochs in which the adversary corrupted the encryption key.
$\mathcal {T}$: List of epochs in which the adversary corrupted the update token.

All experiments necessarily maintain some state, but we omit this for readability reasons. The challenger’s state is $\mathbf {S} \leftarrow \{\mathcal {L},\tilde{\mathcal {L}},\mathcal {C},\mathcal {K},\mathcal {T} \}$, and the system state in the current epoch is given by $\mathsf {st} \leftarrow (\mathrm {k} _\mathsf {e},\varDelta _\mathsf {e},\mathbf {S},\mathsf {e})$.

An at-a-glance overview of $\mathsf {CHALL}$ for various security definitions is given in Fig. 7. For security games such as LT18’s $\mathsf {IND} \text {-}\mathsf {UPD}$ notion, where the adversary must submit as its challenge two ciphertexts (that it received from $\mathcal {O}{.}\mathsf {Enc} $) and one is updated, the game must also track in which epochs the adversary has updates of these ciphertexts. We will later specify a version of our new $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $ notion that allows the adversary to submit a ciphertext that existed in any epoch prior to the challenge epoch, not just the one immediately before: this introduces some additional bookkee** (discussed further in Sect. 3.2).

A note on nomenclature: the adversary can make its challenge query to receive the challenge ciphertext, and then acquire updates of the challenge ciphertext via calls to $\mathcal {O}{.}\mathsf {Upd} {\tilde{\mathrm {C}}} $, and additionally it can calculate challenge-equal ciphertexts via applying tokens it gets via $\mathcal {O}{.}\mathsf {Corr} $ queries.

When appropriate, we will restrict our experiments to provide definitions of security that are more suitable for assessing schemes with deterministic update mechanisms. For such schemes, access to the update token for the challenge epoch ($\varDelta _{\tilde{\mathsf {e}}}$) allows the adversary to trivially win $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf { atk} $ and $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $ for $\mathsf { atk} \in \{\mathsf {CPA},\mathsf {CCA} \}$. Note however that the definitions are not restricted to schemes with deterministic updates: such schemes are simply insecure in terms of $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf {CPA} $ and $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $.

Ciphertext Integrity. In ciphertext integrity (CTXT) game, the adversary is allowed to make calls to oracles $\mathcal {O}{.}\mathsf {Enc} $, $\mathcal {O}{.}\mathsf {Next} $, $\mathcal {O}{.}\mathsf {Upd} $ and $\mathcal {O}{.}\mathsf {Corr}$. At some point $\mathcal {A} $ attempts to provide a forgery via $\mathcal {O}{.}\mathsf {Try} $; as part of this query the challenger will assess if it is valid. We distinguish between the single-$\mathcal {O}{.}\mathsf {Try} $ case ($\mathsf {INT} \text {-}\mathsf {CTXT^s}$) and the multi-$\mathcal {O}{.}\mathsf {Try} $ case ($\mathsf {INT} \text {-}\mathsf {CTXT}$). Here, “valid” means decryption outputs a message (i.e. not $\perp $). In the single-$\mathcal {O}{.}\mathsf {Try} $ case, $\mathcal {A} $ can continue making oracle queries after its $\mathcal {O}{.}\mathsf {Try} $ query, however this is of no benefit since it has already won or lost. In the multi-$\mathcal {O}{.}\mathsf {Try} $ case, $\mathcal {A} $ can make any number of $\mathcal {O}{.}\mathsf {Try} $ queries: as long as it wins once, it wins the ciphertext integrity game. Formally, the definition of ciphertext integrity is given in Definition 1.

Definition 1

Let $\mathsf {UE} =\{\mathsf {UE}.\mathsf {KG},\mathsf {UE}.\mathsf {TG},\mathsf {UE}.\mathsf {Enc},\mathsf {UE}.\mathsf {Dec},\mathsf {UE}.\mathsf {Upd} \} $ be an updatable encryption scheme. Then the $\mathsf {INT} \text {-}\mathsf {CTXT} $ advantage of an adversary $\mathcal {A} $ against $\mathsf {UE}$ is defined as

$$ \mathbf {Adv}^{\mathsf {INT} \text {-}\mathsf {CTXT}}_{\mathsf {UE},~\mathcal {A}} (\lambda ) = \mathbf {Pr} [\mathbf {Exp}^{\mathsf {INT} \text {-}\mathsf {CTXT}}_{\mathsf {UE},~\mathcal {A}} =1]$$

where the experiment $\mathbf {Exp}^{\mathsf {INT} \text {-}\mathsf {CTXT}}_{\mathsf {UE},~\mathcal {A}} $ is given in Fig. 3 and Fig. 6. Particularly, if $\mathcal {A}$ is allowed to ask only one $\mathcal {O}{.}\mathsf {Try} $ query, denote such notion as $\mathsf {INT} \text {-}\mathsf {CTXT^s} $.

Note that $\mathsf {INT} \text {-}\mathsf {CTXT} $ trivially implies $\mathsf {INT} \text {-}\mathsf {CTXT^s}$. In the full version [5] we prove that $\mathsf {INT} \text {-}\mathsf {CTXT^s}$ implies $\mathsf {INT} \text {-}\mathsf {CTXT} $ too, with loss upper-bounded by the number of $\mathcal {O}{.}\mathsf {Try} $ queries. KLR19 define ciphertext integrity with one $\mathcal {O}{.}\mathsf {Try} $ query plus access to $\mathcal {O}{.}\mathsf {Dec} $, and the game ends when the $\mathcal {O}{.}\mathsf {Try} $ query happens. It is hard to prove the generic relation among CPA, CTXT and CCA using this formulation. Notice that decryption oracles give the adversary power to win the CTXT game even it only has one $\mathcal {O}{.}\mathsf {Try} $ query. The adversary can send its forgery to the decryption oracle to test if it is valid (if $\mathcal {O}{.}\mathsf {Dec} $ outputs a message and not $\bot $) – thus $\mathcal {A} $ can continue to send forgeries to $\mathcal {O}{.}\mathsf {Dec} $ until a valid one is found, and then send this as a $\mathcal {O}{.}\mathsf {Try} $ query (and win the game). So intuitively, a decryption oracle is equivalent to multiple $\mathcal {O}{.}\mathsf {Try} $ queries. Proving that all these variants of CTXT definitions are equivalent to each other is straightforward, with the loss upper-bounded by the sum of $\mathcal {O}{.}\mathsf {Try} $ queries and decryption queries.

Remark 1

The definition of $\mathsf {INT} \text {-}\mathsf {CTXT}$ is more natural for defining ciphertext integrity, however, it is easier to use $\mathsf {INT} \text {-}\mathsf {CTXT^s}$ notion to prove ciphertext integrity for specific UE schemes. As $\mathsf {INT} \text {-}\mathsf {CTXT} \iff \mathsf {INT} \text {-}\mathsf {CTXT^s} $, we use both definitions in this paper.

3.1 Existing Definitions of Confidentiality

Here we describe existing confidentiality notions given by LT18 and KLR19, including formal definitions for their $\mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf {CPA} $ and $\mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf {CCA} $ notions, respectively. (Note that KLR19 used UP-REENC to refer to the the unlinkability notion that we and LT18 call $\mathsf {IND} \text {-}\mathsf {UPD} $). We will define our new security notion in Sect. 4.1 and compare the relationship between all notions in Sect. 4.2.

Definition 2

Let $\mathsf {UE} =\{\mathsf {UE}.\mathsf {KG},\mathsf {UE}.\mathsf {TG},\mathsf {UE}.\mathsf {Enc},\mathsf {UE}.\mathsf {Dec},\mathsf {UE}.\mathsf {Upd} \} $ be an updatable encryption scheme. Then the $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf { atk} $ advantage, for $(\mathsf {xx},\mathsf { atk})\in \{(\mathsf {det},\mathsf {CPA}),(\mathsf {rand},\mathsf {CPA}),(\mathsf {det},\mathsf {CCA})\}$, of an adversary $\mathcal {A} $ against $\mathsf {UE}$ is defined as

$$ \mathbf {Adv}^{\mathsf {xx} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf { atk}}_{\mathsf {UE},~\mathcal {A}} (\lambda ) = \biggl |\mathbf {Pr} [\mathbf {Exp}^{\mathsf {xx} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf { atk} \text {-}1}_{\mathsf {UE},~\mathcal {A}} =1]-\mathbf {Pr} [\mathbf {Exp}^{\mathsf {xx} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf { atk} \text {-}0}_{\mathsf {UE},~\mathcal {A}} =1] \biggr |, $$

where the experiment $\mathbf {Exp}^{\mathsf {xx} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf { atk} \text {-}\mathrm {b}}_{\mathsf {UE},~\mathcal {A}} $ is given in Fig. 3, Fig. 5 and Fig. 8.

Definition 3

Let $\mathsf {UE} =\{\mathsf {UE}.\mathsf {KG},\mathsf {UE}.\mathsf {TG},\mathsf {UE}.\mathsf {Enc},\mathsf {UE}.\mathsf {Dec},\mathsf {UE}.\mathsf {Upd} \} $ be an updatable encryption scheme. Then the $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf { atk} $ advantage, for $(\mathsf {xx},\mathsf { atk})\in \{(\mathsf {det},\mathsf {CPA}),(\mathsf {rand},\mathsf {CPA}),(\mathsf {det},\mathsf {CCA})\}$, of an adversary $\mathcal {A} $ against $\mathsf {UE}$ is defined as

$$ \mathbf {Adv}^{\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf { atk}}_{\mathsf {UE},~\mathcal {A}} (\lambda ) = \Bigl |\mathbf {Pr} [\mathbf {Exp}^{\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf { atk} \text {-}1}_{\mathsf {UE},~\mathcal {A}} =1]-\mathbf {Pr} [\mathbf {Exp}^{\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf { atk} \text {-}0}_{\mathsf {UE},~\mathcal {A}} =1]\Bigr |, $$

where the experiments $\mathbf {Exp}^{\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf { atk} \text {-}\mathrm {b}}_{\mathsf {UE},~\mathcal {A}} $ are given in Fig. 3, Fig. 5 and Fig. 9.

We do not define $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CCA} $ or $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf {CCA} $ – these notions were formalized by KLR19. Note that trivial win via direct update (see Sect. 3.2) is never triggered in the $\mathsf {det} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CPA} $ game. Thus, $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CPA} $ is equivalent to $\mathsf {det} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CPA} $. For simplicity, we will often denote the notion $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CPA} $ as $\mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CPA} $.

Remark 2

LT18 defined $\mathsf {weak} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CPA} $ and $\mathsf {weak} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf {CPA} $ for analyzing $\mathsf {BLMR}+ $, a modification of BLMR’s scheme where the nonce is encrypted using symmetric encryption. In this notion, the adversary trivially loses if it obtains an update token linking the challenge epoch to the epoch before or after.

3.2 Trivial Win Conditions

Trivial Win Conditions in Confidentiality Games

Trivial Wins via Keys and Ciphertexts. The following is for analyzing all confidentiality games. We again follow LT18 in defining the epoch identification sets $\mathcal {C} ^*$, $\mathcal {K} ^*$ and $\mathcal {T} ^*$ as the extended sets of $\mathcal {C}$, $\mathcal {K}$ and $\mathcal {T}$ in which the adversary has learned or inferred information via its acquired tokens. These extended sets are used to exclude cases in which the adversary trivially wins, i.e. if $\mathcal {C} ^* \cap \mathcal {K} ^* \not =\emptyset $, then there exists an epoch in which the adversary knows the epoch key and a valid update of the challenge ciphertext. Note that the challenger computes these sets once the adversary has finished running. We employ the following algorithms of LT18 (for bi-directional updates):

Trivial Wins via Direct Updates. The following is for analyzing ${\mathsf {det} \mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf { atk}}$ security notions, for ${\mathsf {yy} \in \{\mathsf {UE},\mathsf {UPD} \}}$ and ${\mathsf { atk} \in \{\mathsf {CPA},\mathsf {CCA} \}}$, where the adversary provides as its challenge one or two ciphertexts that it received from $\mathcal {O}{.}\mathsf {Enc} $. The challenger needs to use $\mathcal {L} $ to track the information the adversary has about these challenge input values.

Define a new list $\mathcal {I} $ as the list of epochs in which the adversary learned an updated version of the ciphertext(s) given as a challenge input. Furthermore, define $\mathcal {I} ^* $ to be the extended set in which the adversary has learned or inferred information via token corruption. We will use this set to exclude cases which the adversary trivially wins, i.e. if $\mathcal {I} ^* \cap \mathcal {C} ^* \not =\emptyset $, then there exists an epoch in which the adversary knows the updated ciphertext of $\bar{\mathrm {C}} $ and a valid challenge-equal ciphertext. For deterministic updates, the adversary can simply compare these ciphertexts to win the game. In particular, if $\bar{\mathrm {C}} $ is restricted to come from $\tilde{\mathsf {e}}-1$ (recall the challenge epoch is $\tilde{\mathsf {e}} $), then the condition $\mathcal {I} ^* \cap \mathcal {C} ^* \not =\emptyset $ is equivalent to the win condition that LT18 used for $\mathsf {IND} \text {-}\mathsf {UPD} $: $\varDelta _{\tilde{\mathsf {e}}}\in \mathcal {T} ^* $ or $\mathcal {A}$ did $\mathcal {O}{.}\mathsf {Upd} (\bar{\mathrm {C}})$ in $\tilde{\mathsf {e}} $. Our generalization is necessary for a variant of $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $ that we define later in which the challenge ciphertext input can come from any prior epoch, and not just the epoch immediately before the one in which the challenge is made.

To compute $\mathcal {I}$, find an entry in $\mathcal {L} $ that contains challenge input $\bar{\mathrm {C}} $. Then for that entry, note the query identifier $\mathtt {c} $, scan $\mathcal {L} $ for other entries with this identifier, and add into list $\mathcal {I} $ all found indices: $\mathcal {I} \leftarrow \{\mathsf {e} \in \{0,\dots ,n\}| (\mathtt {c},\cdot ,\mathsf {e})\in \mathcal {L} \}.$ Then compute $\mathcal {I} ^*$ as follows:

Additionally, if the adversary submits two ciphertexts $\bar{\mathrm {C}} _0,\bar{\mathrm {C}} _1 $ as challenge (as in $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf { atk} $), we compute $\mathcal {I} _i, \mathcal {I} ^* _i, i\in \{0,1\}$ first and then use $\mathcal {I} ^* = \mathcal {I} ^* _0\cup \mathcal {I} ^* _1$ to check the trivial win condition. An example of trivial win conditions $\mathcal {K} ^* \cap \mathcal {C} ^* \not =\emptyset $ and $\mathcal {I} ^* \cap \mathcal {C} ^* \not =\emptyset $ is provided in the full version [5].

We do not consider this trivial win condition for the $\mathsf {ENC} $ notion, as there is no ciphertext in the challenge input value, i.e. $\mathcal {I} ^* =\emptyset $. Thus, the assessment $\mathcal {I} ^* \cap \mathcal {C} ^* \not =\emptyset $ in experiment $\mathbf {Exp}^{\mathsf {det} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf { atk} \text {-}\mathrm {b}}_{\mathsf {UE},~\mathcal {A}} $ (see Fig. 5) will never be true.

Trivial Wins via Decryptions. The following is for analyzing $\mathsf {det} \mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf {CCA} $ notions, for $\mathsf {yy} \in \{\mathsf {UE},\mathsf {ENC},\mathsf {UPD} \}$, where the adversary has access to $\mathcal {O}{.}\mathsf {Dec} $. We follow the trivial win analysis in KLR19: suppose the adversary knows a challenge ciphertext $(\tilde{\mathrm {C}},\mathsf {e} _{0})\in \tilde{\mathcal {L}} $ and tokens from epoch $\mathsf {e} _0+1$ to epoch $\mathsf {e} $, then the adversary can update the challenge ciphertext from epoch $\mathsf {e} _0$ to epoch $\mathsf {e} $. If $\mathcal {A} $ sends the updated ciphertext to $\mathcal {O}{.}\mathsf {Dec} $ this will reveal the underlying message, and $\mathcal {A} $ trivially wins the game: we shall exclude this type of attack.

Define $\tilde{\mathcal {L}} ^*$ to be the extended set of $\tilde{\mathcal {L}} $ in which the adversary has learned or inferred information via token corruption. Whenever $\mathcal {O}{.}\mathsf {Dec} $ receives a ciphertext located in $\tilde{\mathcal {L}} ^*$, the challenger will set the trivial win flag $\mathsf {twf}$ to be 1. The list $\tilde{\mathcal {L}} ^*$ is updated while the security game is running. After the challenge query happens, the challenger updates $\tilde{\mathcal {L}} ^*$ whenever an element is added to list $\tilde{\mathcal {L}} $ or a token is corrupted. In Fig. 10 we show how list $\tilde{\mathcal {L}} ^*$ is updated.

Trivial Win Conditions in Ciphertext Integrity Games. We again follow the trivial win analysis in KLR19. In ciphertext integrity games for updatable encryption, we do not consider the randomized update setting as the adversary can update an old ciphertext via a corrupted token to provide any number of new valid forgeries to the Try query to trivially win this game.

Trivial Wins via Keys. If an epoch key is corrupted, then the adversary can use this key to forge ciphertexts in this epoch. We exclude this trivial win: if the adversary provides a forgery in an epoch in list $\mathcal {K} ^* $, the challenger sets $\mathsf {twf}$ to 1.

Trivial Wins via Ciphertexts. Suppose the adversary knows a ciphertext $(\mathrm {C},\mathsf {e} _{0})\in \mathcal {L} $ and tokens from epoch $\mathsf {e} _0+1$ to epoch $\mathsf {e} $, then the adversary can provide a forgery by updating $\mathrm {C} $ to epoch $\mathsf {e}$. We shall exclude this type of forgeries.

Define $\mathcal {L} ^*$ to be the extended set of $\mathcal {L} $ in which the adversary has learned or inferred information via token corruption. If $\mathcal {O}{.}\mathsf {Try} $ receives a ciphertext located in $\mathcal {L} ^*$, the challenger will set $\mathsf {twf}$ to 1. The list $\mathcal {L} ^*$ is updated while the security game is running. Ciphertexts output by $\mathcal {O}{.}\mathsf {Enc} $ and $\mathcal {O}{.}\mathsf {Upd} $ are known to the adversary. Furthermore, whenever a token is corrupted, the challenger may update list $\mathcal {L} ^*$ as well. In Fig. 11 we show how list $\mathcal {L} ^*$ is updated.

3.3 Firewall Technique

In order to prove security for updatable encryption in the epoch-based model with strong corruption capabilities, cryptographic separation is required between the epochs in which the adversary knows key material, and those in which it knows challenge-equal ciphertexts (acquired/calculated via queries to $\mathcal {O}{.}\mathsf {Upd} {\tilde{\mathrm {C}}} $ and $\mathcal {O}{.}\mathsf {Corr} (\varDelta )$). To ensure this, we follow prior work in explicitly defining the ‘safe’ or insulated regions, as we explain below. These regions insulate epoch keys, tokens and ciphertexts: outside of an insulated region a reduction in a security proof can generate keys and tokens itself, but within these regions it must embed its challenge while still providing the underlying adversary with access to the appropriate oracles. A thorough discussion of how we leverage these insulated regions in proofs is given in Sect. 5.3.

To understand the idea of firewalls, consider any security game (for bi-directional schemes) in which the trivial win conditions are not triggered. If the adversary $\mathcal {A} $ corrupts all tokens then either it never corrupts any keys or it never asks for a challenge ciphertext. Suppose that $\mathcal {A} $ does ask for a challenge ciphertext in epoch $\tilde{\mathsf {e}}$^{Footnote 3}. Then there exists an (unique) epoch continuum around $\tilde{\mathsf {e}}$ such that no keys in this epoch continuum, and no tokens in the boundaries of this epoch continuum are corrupted. Moreover, we can assume that all tokens within this epoch continuum are corrupted, because once the adversary has finished corrupting keys, it can corrupt any remaining tokens that do not ‘touch’ those corrupted keys. This observation is first used in the $\mathsf {IND} \text {-}\mathsf {UPD}$ proof of $\mathsf {RISE}$ provided by Lehmann and Tackmann [21], and Klooß et al. [17] provided an extended description of this ‘key insulation’ technique. We name these epoch ranges insulated regions and their boundaries to be firewalls.

Definition 4

An insulated region with firewalls $\mathsf {fwl} $ and $\mathsf {fwr} $ is a consecutive sequence of epochs $(\mathsf {fwl}, \ldots , \mathsf {fwr})$ for which:

no key in the sequence of epochs $(\mathsf {fwl}, \ldots , \mathsf {fwr})$ is corrupted;
the tokens $\varDelta _{\mathsf {fwl}}$ and $\varDelta _{\mathsf {fwr} +1}$ are not corrupted (if they exist);
all tokens $(\varDelta _{\mathsf {fwl} +1}, \ldots , \varDelta _{\mathsf {fwr}})$ are corrupted (if any exist).

We denote the firewalls bordering the special insulated region that contains $\tilde{\mathsf {e}} $ as $\hat{\mathsf {fwl}} $ and $\hat{\mathsf {fwr}} $ – though note that there could be (many, distinct) insulated regions elsewhere in the epoch continuum. Specifically, when the adversary asks for updated versions of the challenge ciphertext, the epoch in which this query occurs must also fall within (what the challenger later calculates as) an insulated region. In the full version [5] we give an algorithm for computing firewall locations. The list $\mathcal {FW}$ tracks, and appends a label to, each insulated region and its firewalls. Observe that if an epoch is a left firewall, then neither the key nor the token for that epoch are corrupted. From the left firewall, since we assume that all tokens are corrupted, track to the right until either a token is not corrupted or a key is.

4 On the Security of Updates

In this section we present a new notion of security for updatable encryption schemes, which we denote $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $. This notion captures both security of fresh encryptions (i.e. implies $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf { atk} $) and unlinkability (i.e. implies $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf { atk} $). We first explain the new notion and then describe its relation to previous notions. Then, we prove a generic relationship among CPA, CTXT and CCA to complete the picture for security notions for UE schemes.

4.1 A New Definition of Confidentiality

In the security game for $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $, the adversary submits one message and a ciphertext from an earlier epoch that the adversary received via a call to $\mathcal {O}{.}\mathsf {Enc} $. The challenger responds with either an encryption of that message or an update of that earlier ciphertext, in the challenge (current) epoch $\tilde{\mathsf {e}}$.

Definition 5

($\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $). Let $\mathsf {UE} =\{\mathsf {UE}.\mathsf {KG},\mathsf {UE}.\mathsf {TG},\mathsf {UE}.\mathsf {Enc},\mathsf {UE}.\mathsf {Dec},\mathsf {UE}.\mathsf {Upd} \} $ be an updatable encryption scheme. Then the $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $ advantage, for $(\mathsf {xx},\mathsf { atk})\in \{(\mathsf {det},\mathsf {CPA}),(\mathsf {rand},\mathsf {CPA}),(\mathsf {det},\mathsf {CCA})\}$, of an adversary $\mathcal {A} $ against $\mathsf {UE}$ is defined as

$$ \mathbf {Adv}^{\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk}}_{\mathsf {UE},~\mathcal {A}} (\lambda ) = \Bigl |\mathbf {Pr} [\mathbf {Exp}^{\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} \text {-}1}_{\mathsf {UE},~\mathcal {A}} =1]-\mathbf {Pr} [\mathbf {Exp}^{\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} \text {-}0}_{\mathsf {UE},~\mathcal {A}} =1]\Bigr |$$

where the experiment $\mathbf {Exp}^{\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} \text {-}\mathrm {b}}_{\mathsf {UE},~\mathcal {A}} $ is given in Fig. 3, Fig. 5 and Fig. 12.

Note that $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ is strictly stronger than $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $, since the adversary has strictly more capabilities. A generalized version of $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $, denoted $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} ^*\text {-}\mathsf { atk} $, is also given in Fig. 12. In this game the input challenge ciphertext can come from (i.e. be known to $\mathcal {A}$ in) any prior epoch, not just the epoch immediately before $\tilde{\mathsf {e}}$. Note that $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $ is a special case of $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} ^*\text {-}\mathsf { atk} $. Under some fairly weak requirements (that all schemes discussed in this paper satisfy) we can prove that $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $ implies $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} ^*\text {-}\mathsf { atk} $ – this analysis is given in the full version [5].

Remark 3

The definition of $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $ is more concise and intuitively easier to understand than $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} ^*\text {-}\mathsf { atk} $, however in the full version [5] we show that $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} \iff \mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} ^*\text {-}\mathsf { atk} $. This result and our generic proof techniques mean that all results in this paper that hold for $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $, also hold for $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} ^*\text {-}\mathsf { atk} $, and vice versa.

Remark 4

In the full version [5] we show that the $\mathsf {RISE}$ scheme presented by LT18 is $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ secure under DDH. While this result is perhaps unsurprising, the proof techniques we use are novel. We give an Oracle-DDH-like game that inherits the epoch-based nature of the updatable encryption security model, and then use this as a bridge to prove security.

4.2 Relations Among Security Notions

In Fig. 13 we show the relationship between the new and existing UE security notions. Note that our new notion is strictly stronger than the $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf { atk} $ and $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf { atk} $ notions presented in prior work, and is in fact stronger than the combination of the prior notions. Further, we show that the generic relation among CPA, CTXT and CCA, that CPA security coupled with ciphertext integrity implies CCA security, also holds for updatable encryption schemes.

Theorem 1

(Informal Theorem). The relationship among the security notions $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $, $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf { atk} $ and $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf { atk} $ are as in Fig. 13. The relationship is proven via Theorems in the full version [5] and due to space constraints we show Theorems 1.1 and Theorem 1.2 only.

Theorem 1.1

Let $\mathsf {UE} =\{\mathsf {UE}.\mathsf {KG},\mathsf {UE}.\mathsf {TG},\mathsf {UE}.\mathsf {Enc},\mathsf {UE}.\mathsf {Dec},\mathsf {UE}.\mathsf {Upd} \} $ be an updatable encryption scheme. For any $\mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CPA} $ adversary $\mathcal {A}$ against $\mathsf {UE}$, there exists an $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ adversary $\mathcal {B} _{1.1}$ against $\mathsf {UE}$ such that

$$ \mathbf {Adv}^{\mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CPA}}_{\mathsf {UE},~\mathcal {A}} (\lambda ) \le 2\cdot \mathbf {Adv}^{\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA}}_{\mathsf {UE},~\mathcal {B} _{1.1}} (\lambda ). $$

Proof

We construct a reduction $\mathcal {B} _{1.1}$ running the $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ experiment which will simulate the responses of queries made by the $\mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CPA} $ adversary $\mathcal {A}$. To provide a valid non-challenge ciphertext to its own challenger, $\mathcal {B} _{1.1}$ must run $\mathcal {A}$ out of step with its own game, so epoch 0 as far as $\mathcal {A}$ is concerned is actually epoch 1 for $\mathcal {B} _{1.1}$, and so on.

1.
$\mathcal {B} _{1.1}$ chooses $\mathrm {b} \xleftarrow {\$} \{0,1\}$.
2.
$\mathcal {B} _{1.1}$ receives the setup parameters from its $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ challenger, chooses $\mathrm {M} \xleftarrow {\$} \mathcal {MS} $ and calls $\mathcal {O}{.}\mathsf {Enc} (\mathrm {M})$ which returns some $\mathrm {C} ^0$. Then $\mathcal {B} _{1.1}$ calls $\mathcal {O}{.}\mathsf {Next} $ once and sends the setup parameters to $\mathcal {A}$.
3.
1. (a)
  Whenever $\mathcal {B} _{1.1}$ receives the queries $\mathcal {O}{.}\mathsf {Enc} ,\mathcal {O}{.}\mathsf {Upd} ,\mathcal {O}{.}\mathsf {Corr} $ from $\mathcal {A}$, $\mathcal {B} _{1.1}$ sends these queries to its $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ challenger, and forwards the responses to $\mathcal {A}$.
2. (b)
  Whenever $\mathcal {O}{.}\mathsf {Next} $ is called by $\mathcal {A}$, $\mathcal {B} _{1.1}$ randomly chooses a message $\mathrm {M} \xleftarrow {\$} \mathcal {MS} $ and calls $\mathcal {O}{.}\mathsf {Enc} (\mathrm {M})$ to receive some $\mathrm {C} ^{\mathsf {e}}$, and then calls $\mathcal {O}{.}\mathsf {Next} $.
4.
At some point, in epoch $\tilde{\mathsf {e}} $ (for its game), $\mathcal {B} _{1.1}$ receives the challenge query $(\bar{\mathrm {M}} _0,\bar{\mathrm {M}} _1)$ from $\mathcal {A}$. Then $\mathcal {B} _{1.1}$ sends the pair $(\bar{\mathrm {M}} _\mathrm {b},\mathrm {C} ^{\tilde{\mathsf {e}}-1})$ as challenge to its own $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ challenger. After receiving the challenge ciphertext, $\tilde{\mathrm {C}} _{\tilde{\mathsf {e}}}$, from its challenger, $\mathcal {B} _{1.1}$ sends $\tilde{\mathrm {C}} _{\tilde{\mathsf {e}}}$ to $\mathcal {A}$.
5.
$\mathcal {B} _{1.1}$ continues to answer $\mathcal {A}$ ’s queries using its own oracles, now including the challenge ciphertext update oracle $\mathcal {O}{.}\mathsf {Upd} {\tilde{\mathrm {C}}} $.
6.
Finally $\mathcal {B} _{1.1}$ receives the output bit $\mathrm {b} '$ from $\mathcal {A}$. If $\mathrm {b} = \mathrm {b} '$ then $\mathcal {B} _{1.1}$ returns 0. Otherwise $\mathcal {B} _{1.1}$ returns 1.

We now bound the advantage of $\mathcal {B} _{1.1}$. The point is that whenever $\mathcal {B} _{1.1}$ returns a random encryption to $\mathcal {A}$, $\mathcal {B} _{1.1}$’s probability of winning is exactly 1/2 because the bit $\mathrm {b} '$ from $\mathcal {A}$ is independent of its choice of $\mathrm {b} $. This happens with probability 1/2. However, when $\mathcal {B} _{1.1}$ returns a “correct” value to $\mathcal {A}$ (an encryption of $\bar{\mathrm {M}} _0$ or $\bar{\mathrm {M}} _1$), then $\mathcal {B} _{1.1}$’s probability of winning is the same as the probability that $\mathcal {A}$ wins. First note that, as usual,

$$ \mathbf {Adv}^{\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA}}_{\mathsf {UE},\mathcal {B} _{1.1}} = |\mathbf {Pr} [\mathbf {Exp}^{\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} \text {-}1}_{\mathsf {UE},~\mathcal {B} _{1.1}} = 1] - \mathbf {Pr} [\mathbf {Exp}^{\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} \text {-}0}_{\mathsf {UE},~\mathcal {B} _{1.1}} = 1]|. $$

We claim that $\mathbf {Pr} [\mathbf {Exp}^{\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} \text {-}1}_{\mathsf {UE},~\mathcal {B} _{1.1}} = 1] = 1/2$ because in this case $\tilde{\mathrm {C}} _{\tilde{\mathsf {e}}}$ is independent of $\mathrm {b} $ and so $\mathrm {b} '$ must also be independent of $\mathrm {b} $. Then we have:

$\square $

The three separation arrows at the top of Fig. 13 are all demonstrated in the same manner. Begin with a scheme $\mathsf {UE} $ that meets both of the two notions at the very top of the figure. All algorithms for $\mathsf {UE} '$ are the same as for $\mathsf {UE} $, except $\mathsf {UE} '.\mathsf {Enc} $ is defined by modifying $\mathsf {UE}.\mathsf {Enc} $ to append the epoch number in which the ciphertext was initially created (and $\mathsf {UE} '.\mathsf {Dec} $ ignores this appended value). This does not affect an adversary’s ability to win the $\mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf { atk} $ or $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf { atk} $ games but trivially breaks $\mathsf {xx} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf { atk} $ security.

Generic Composition. The following theorem tells the relation among CPA, CTXT and CCA security. The full proof is given in the full version [5].

Theorem 1.2

Let $\mathsf {UE} =\{\mathsf {UE}.\mathsf {KG},\mathsf {UE}.\mathsf {TG},\mathsf {UE}.\mathsf {Enc},\mathsf {UE}.\mathsf {Dec},\mathsf {UE}.\mathsf {Upd} \} $ be an updatable encryption scheme. For any $\mathsf {det} \mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf {CCA} $ adversary $\mathcal {A}$ against $\mathsf {UE}$, there exists an $\mathsf {INT} \text {-}\mathsf {CTXT} $ adversary $\mathcal {B} _{1.2a}$ and an $\mathsf {det} \mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf {CPA} $ adversary $\mathcal {B} _{1.2b}$ against $\mathsf {UE}$ such that

$$ \mathbf {Adv}^{\mathsf {det} \mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf {CCA}}_{\mathsf {UE},~\mathcal {A}} (\lambda )\le 2\mathbf {Adv}^{\mathsf {INT} \text {-}\mathsf {CTXT}}_{\mathsf {UE},~\mathcal {B} _{1.2a}} (\lambda )+\mathbf {Adv}^{\mathsf {det} \mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf {CPA}}_{\mathsf {UE},~\mathcal {B} _{1.2b}} (\lambda ) $$

where $\mathsf {yy} \in \{\mathsf {UE},\mathsf {ENC},\mathsf {UPD} \}$.

Proof sketch

The proof is adapted from the proof of Theorem 3.2 of Bellare and Namprempre [2]. We modify the $\mathsf {det} \mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf {CCA} $ game such that in the new game the decryption oracle will answer $\bot $ if the input is a fresh ciphertext.

In more detail, suppose $\mathcal {A}$ is an adversary playing the new game, then we can then construct a reduction playing $\mathsf {det} \mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf {CPA} $ game and simulating the responses to $\mathcal {A}$. To answer decryption oracle queries made by $\mathcal {A}$, the reduction performs bookkee** for ciphertexts and messages to successfully respond to the decryption of already-existing ciphertexts, or simply replying $\bot $ for the decryption of fresh ciphertexts. So the advantage of winning the new game is upper-bounded by the $\mathsf {det} \mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf {CPA} $ advantage.

Furthermore, notice that two games are identical until a valid fresh ciphertext is sent to the decryption oracle. Which means the probability of an adversary these games is upper-bounded by the probability that a valid fresh forgery is produced: this successful adversary can win the $\mathsf {INT} \text {-}\mathsf {CTXT}$ game. Therefore, the difference between the new game and the original $\mathsf {det} \mathsf {IND} \text {-}\mathsf {yy} \text {-}\mathsf {CCA} $ game can be upper-bounded by the $\mathsf {INT} \text {-}\mathsf {CTXT}$ advantage. $\square $

5 The $\mathsf {SHINE}$ Schemes

We now describe our new UE scheme $\mathsf {SHINE}$ (Secure Homomorphic Ideal-cipher Nonce-based Encryption). The encryption algorithm uses a permutation to obfuscate the input to the exponentiation function. Updating a ciphertext simply requires exponentiation once by the update token, which itself is the quotient of the current epoch key and the previous epoch key. The scheme comes in three flavors: $\mathsf {SHINE0}$ is presented in Fig. 14 and takes in short messages and only uses a single permutation. The second flavor, $\mathsf {MirrorSHINE}$, is provided in the full version [5] and runs two different permutations with the same input. The third flavor $\mathsf {OCBSHINE}$ is given in Fig. 16 and is for applications with arbitrarily long messages, using a family of permutations.

We discuss implementation details of the $\mathsf {SHINE}$ schemes in Sect. 5.6. In particular, for each scheme in the $\mathsf {SHINE}$ suite, it is necessary to embed the output of the permutation (a regular block cipher) into an appropriate DDH-hard group.

Our proofs of security, given as Theorem 2 (Theorem 3), bound an adversary’s $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ ($\mathsf {INT} \text {-}\mathsf {CTXT^s}$) advantage by DDH (CDH), and are provided in the ideal cipher model. Furthermore, combining the results of Theorem 1.2, Theorem 2 and Theorem 3, we have that the suite of $\mathsf {SHINE}$ schemes (i.e. $\mathsf {SHINE0}$, $\mathsf {MirrorSHINE}$ and $\mathsf {OCBSHINE}$) are $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CCA} $ secure.

5.1 Construction of $\mathsf {SHINE}$ Schemes

via Zero Block: . Suppose a message space of $\mathcal {MS} =\{0,1\}^\mathrm {m} $ and random nonce space $\mathcal {N} =\{0,1\}^{\mathrm {v}}$. The encryption algorithm feeds as input to the permutation a nonce, the message, and a zero string. The decryption algorithm will return $\bot $ if the decrypted value does not end with $0^\mathrm {t} $. The $\mathsf {SHINE0} $ scheme is defined in Fig. 14. If ciphertext integrity is not required (or file/ciphertext integrity is performed in some other manner), then $\mathsf {SHINE0}$ without the zero block results in a scheme (denoted $\mathsf {SHINE0} [\mathsf {CPA} ]$) that is still $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ secure.

for Long Messages via Checksum: . The schemes $\mathsf {SHINE0}$ and $\mathsf {MirrorSHINE}$ both require that the message space be smaller than the size of an element of the exponentiation group. This ciphertext expansion is undesirable in many practical scenarios, and so we wish to construct a $\mathsf {SHINE}$ scheme which gives us (almost) no ciphertext expansion and can be applied to arbitrarily long messages. We build a new $\mathsf {SHINE}$ scheme, $\mathsf {OCBSHINE}$, with these properties.

The construction of $\mathsf {OCBSHINE}$ is inspired by the authenticated encryption scheme OCB [24]. Different from OCB mode, the nonce is encrypted inside the ciphertext instead of sending it along with the ciphertext. In order to determine the length of the last message block, the encryption algorithm of OCB mode removes some bits of the last ciphertext block to reveal this information. However in our setting, the output of the permutations are (mapped to) the input of the exponentiation function: thus all bits of permutation outputs must be included. Therefore, $\mathsf {OCBSHINE}$ includes the length of the last message block in the first ciphertext component. If ciphertext integrity is not required, then $\mathsf {OCBSHINE}$ can be improved by removing the last ciphertext block.

$\mathsf {OCBSHINE}$ is formally defined in Fig. 16 and the encryption process is pictorially represented in Fig. 15; we give an intuitive description here. Suppose the blocksize is m, and assume the encryption algorithm $\mathsf {OCBSHINE}.\mathsf {Enc} $ has input message $\mathrm {M} $. By “partition $\mathrm {M} $ into $\mathrm {M} _1,\dots ,\mathrm {M} _{l}$” we mean setting $l \leftarrow \max \{\lceil |\mathrm {M} |/m \rceil , 1\}$ and dividing $\mathrm {M} $ into $l $ blocks, i.e. $\mathrm {M} _{1},\dots ,\mathrm {M} _{l}$, where $|\mathrm {M} _{1}|=\dots =|\mathrm {M} _{l-1}|=m$. The last message block $\mathrm {M} _{l}$ is padded with zeros to make it length m before computing the permutation output and the checksum, i.e $\mathrm {M} _{l}\Vert 0^*$ with $|\mathrm {M} _{l}\Vert 0^*|=m$. Let $a=\lceil \log (m)\rceil $, so the length of $\mathrm {M} _{l}$ ($|\mathrm {M} _{l}|\le m$) can be written as an a-bit representation.

Let Perm(m) be the set of all permutations on $\{0,1\}^m$. Randomly choose $\uppi _0\xleftarrow {\$} $Perm(m), and use this permutation to randomize the concatenation of the nonce $\mathrm {N} $ and an a-bit representation of the last message block length. Then, index the (random) permutations used to encrypt message blocks by the nonce and a counter. Let Perm(S, m) be the set of all map**s from S to permutations on $\{0,1\}^m$. Suppose the nonce space is $\mathcal {N} =\{0,1\}^{m-a}$, $S=\mathcal {N} \times \mathbb {N}^* \times \{0,1\}$, for each $(\mathrm {N} \in \mathcal {N},i\in \mathbb {N}^*,b\in \{0,1\})$, set ${\uppi }_{\mathrm {N} \Vert i\Vert b}\xleftarrow {\$} $Perm$(\mathcal {N} \times \mathbb {N}^*\times \{0,1\},m)$, which form a random permutation family: we use these permutations to randomize message blocks and the checksum.

5.2 Security - $\mathsf {SHINE}$ is $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA},\mathsf {INT} \text {-}\mathsf {CTXT},\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CCA} $ Secure

All three $\mathsf {SHINE}$ schemes, i.e. $\mathsf {SHINE0}$, $\mathsf {MirrorSHINE}$ and $\mathsf {OCBSHINE}$, have the same security properties, and the proofs are very similar for each flavor. We refer to $\mathsf {SHINE}$ to mean the family containing all these three schemes. In Theorem 2, we show that $\mathsf {SHINE}$ is $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ in the ideal cipher model, if DDH holds. In Theorem 3, we show that $\mathsf {SHINE}$ is $\mathsf {INT} \text {-}\mathsf {CTXT^s} $, and therefore $\mathsf {INT} \text {-}\mathsf {CTXT}$ ($\mathsf {INT} \text {-}\mathsf {CTXT}$ and $\mathsf {INT} \text {-}\mathsf {CTXT^s}$ are equivalent, recall Sect. 3), in the ideal cipher model, if CDH holds. The loss incurred by this proof is the normal $(n+1)^3$ (or $(n+1)^2$ for $\mathsf {INT} \text {-}\mathsf {CTXT}$) and also the number of encryption queries the adversary makes before it makes its challenge: to avoid the issues described in Sect. 5.3 we not only need to guess the locations of the challenge firewalls but also the ciphertext that the adversary will submit as its challenge.

The ideal cipher model, a version of which was initially given by Shannon [26] and shown to be equivalent to the random oracle model by Coron et al. [8], gives all parties access to a permutation chosen randomly from all possible key-permutation possibilities of appropriate length. The $\mathsf {SHINE}$ schemes exponentiate the output of the permutation by the epoch key to encrypt, so our reduction can ‘program’ the transformation from permutation outputs to group elements.

In the following two Theorems we detail the security properties met by $\mathsf {SHINE}$, i.e. $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $, $\mathsf {INT} \text {-}\mathsf {CTXT} $ and thus $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CCA} $. Note that this is the strongest known security property for updatable encryption schemes with deterministic updates. In Sect. 5.3 we discuss the challenges that arise in the proofs of these two theorems, and in Sect. 5.4 and Sect. 5.5 we describe the novel techniques and methods used in the proofs. Full proofs are provided in the full version [5].

Theorem 2

($\mathsf {SHINE} $ is $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $). Let $\mathsf {SHINE} \in \{\mathsf {SHINE0}, \mathsf {MirrorSHINE},$

$ \mathsf {OCBSHINE} \}$ be the UE scheme described above. For any ideal cipher model adversary $\mathcal {A} $ (that makes max $\mathrm {Q_E} $ encryption queries before its challenge), there exists an adversary $\mathcal {B} _{2}$ such that

Theorem 3

($\mathsf {SHINE} $ is $\mathsf {INT} \text {-}\mathsf {CTXT^s}$ ). Let $\mathsf {SHINE} \in \{\mathsf {SHINE0}, \mathsf {MirrorSHINE},$

$ \mathsf {OCBSHINE} \}$ be the UE scheme described above. For any ideal cipher model adversary $\mathcal {A} $ (that makes max $\mathrm {Q_E} $ encryption queries before calling $\mathcal {O}{.}\mathsf {Try} $), there exists an adversary $\mathcal {B} _{3}$ such that

Remark 5

Combining the results of Theorem 1.2, Theorem 2 and Theorem 3, we have that $\mathsf {SHINE}$ is $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CCA} $.

5.3 Proof Challenges in Schemes with Deterministic Updates

In each variant of $\mathsf {SHINE}$ all ciphertext components are raised to the epoch key, so the update mechanism transforms a ciphertext for epoch $\mathsf {e}$ to one for $\mathsf {e} +1$ by raising this value to $\frac{\mathrm {k} _{\mathsf {e} +1}}{\mathrm {k} _{\mathsf {e}}}$. We now highlight the difficulties in creating security proofs for such ‘single-component’ updatable encryption schemes. Randomness is used in creation of the initial ciphertext (via $\mathrm {N}$) but updates are completely deterministic, and thus in any reduction it is necessary to provide consistent ciphertexts to the adversary (i.e. the $\mathrm {N}$ value must be consistent). The (cryptographic) separation gained by using the firewall technique (see Sect. 3.3 for discussion and definition) assists with producing (updates of) non-challenge ciphertexts, but embedding any challenge value while also providing answers to the $\mathcal {O}{.}\mathsf {Corr}$ queries of the underlying adversary is very challenging.

The regular key insulation technique as introduced by LT18 – where the reduction constructs one hybrid for each epoch – does not work. Specifically, in any reduction to a DDH-like assumption, it is not possible to provide a challenge ciphertext in a left or right sense (to the left of this challenge ciphertext are of some form, and to the right of this challenge ciphertext are of some other form) if the underlying adversary asks for tokens around the challenge epoch: deterministic updates mean that tokens will make these ciphertexts of the same form and this gap will be easily distinguishable.

We counteract this problem by constructing a hybrid argument across insulated regions. This means that in each hybrid, we can embed at one firewall of the insulated region, and simulate all tokens within that insulated region to enable answering queries to both $\mathcal {O}{.}\mathsf {Upd} $ and $\mathcal {O}{.}\mathsf {Upd} {\tilde{\mathrm {C}}}$. The reduction’s distinguishing task is thus ensured to be at the boundaries of the insulated regions, the firewalls, so any (non-trivial) win for the underlying adversary is ensured to carry through directly to the reduction.

5.4 Proof Method for Confidentiality: Constructing a Hybrid Argument Across Insulated Regions

The confidentiality proof of $\mathsf {SHINE0}$ is extendable to $\mathsf {MirrorSHINE}$ and $\mathsf {OCBSHINE}$, so we only show proof method of $\mathsf {SHINE0}$. We now explain how we bound the advantage of any adversary playing the $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ game for $\mathsf {SHINE0}$ by the advantage of a reduction playing DDH.

We apply the firewall technique to set up hybrid games such that in hybrid i, we embed within the i-th insulated region: this means that to the left of the i-th insulated region the game responds with the $\mathrm {b} =1$ case of the $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ experiment, and to the right of the i-th insulated region it gives an encryption of the challenge input message as output, i.e. $\mathrm {b} =0$. This means we have one hybrid for each insulated region, moving left-to-right across the epoch space.

We construct a reduction $\mathcal {B} $ playing the DDH experiment in hybrid i. Initially, $\mathcal {B} $ guesses the location of the i-th insulated region. If the underlying adversary has performed a corrupt query within this insulated region that would lead to the reduction failing, the reduction aborts the game. In the full version [5] we detail a dedicated algorithm for checking this event.

In particular, within the insulated region, the reduction can simulate challenge ciphertexts and non-challenge ciphertexts using its DDH tuple. Furthermore, ciphertexts can be moved around within the insulated region by tokens.

Remark 6

We note that the problem of challenge insulation in schemes with deterministic updates was also observed independently by Klooß et al. [18] § B.2]. Their solution (though in the different context of CCA security of UE with certain properties) is to form a hybrid argument with a hybrid for each epoch, and essentially guess an epoch r which is the first token ‘after’ the hybrid index that the adversary has not corrupted, and use the inherent ‘gap’ in the adversary’s knowledge continuum to replace challenge updates across this gap with encryptions of just one of the challenge messages. It is not clear if this approach would work for showing $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UE} \text {-}\mathsf {CPA} $ (or $\mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CPA} $) of $\mathsf {SHINE0}$. We conjecture that even if it were possible to construct a reduction in this vein, our approach enables a more direct proof: in particular we do not need to assume specific additional properties of the UE scheme in question for it to work.

5.5 Proof Method for Integrity

The integrity proof of $\mathsf {SHINE0}$ is extendable to $\mathsf {MirrorSHINE}$ and $\mathsf {OCBSHINE}$, so we only show proof method of $\mathsf {SHINE0}$.In the $\mathsf {INT} \text {-}\mathsf {CTXT^s}$ game, the challenger will keep a list of consistent values for ciphertexts (i.e. the underlying permutation output $\uppi (\mathrm {N} \Vert \mathrm {M} \Vert 0^l)$). Suppose $\tilde{\mathrm {C}} $ is a forgery attempt sent to the $\mathcal {O}{.}\mathsf {Try} $ query in epoch $\tilde{\mathsf {e}} $. Let $\tilde{c}=(\tilde{\mathrm {C}})^{1/\mathrm {k} _{\tilde{\mathsf {e}}}}$ be the underlying permutation output. We claim that if $\tilde{c}$ is a new value, then the adversary wins the game with negligible probability; if $\tilde{c}$ is a value that existed before, then the probability that the adversary wins the game can be bounded by the advantage.

If $\tilde{c}$ is a new value, since $\uppi $ is a random permutation, then the $\mathsf {INT} \text {-}\mathsf {CTXT^s}$ challenger simulates the preimage of $\tilde{c}$ under $\uppi $ to be a random string. So the probability that this random string ends with a (fixed length) zero block is negligible, and this carries over to the probability that the adversary wins the $\mathsf {INT} \text {-}\mathsf {CTXT^s}$ game. If $\tilde{c}$ is an already-existing value, and suppose this event happens with probability p. We construct a reduction playing the CDH game such that it wins CDH game with probability $p\cdot \frac{1}{\mathrm {Q_E} (n+1)^2}$. Similar to the proof method of confidentiality, we construct a reduction playing the CDH experiment by guessing the location of the firewalls around the challenge epoch. The reduction embeds the CDH value and simulates the $\mathsf {INT} \text {-}\mathsf {CTXT^s}$ game, using any successfully-forged ciphertext to compute the CDH output to its CDH challenger.

5.6 Implementing the $\mathsf {SHINE}$ Schemes

In the proofs of Theorem 2 and Theorem 3, we require that $\uppi $ is a random (unkeyed) permutation which must be followed by a map** to an appropriate group for exponentiation by the epoch key. For the permutation we do not need any specific and strong properties that are provided by modern constructions of block ciphers and sponges. As far as the proof goes, and in practice, the property that we want from this permutation is that given a ciphertext and the inverse of the epoch key $\mathrm {k} _\mathsf {e} $, the only way to extract useful information about the message is to apply the inverse permutation $\uppi ^{-1}$. The random permutation model (or ideal cipher model) is thus the tool we need here to create a simple interface for this aspect of our proof.

The different members of the $\mathsf {SHINE}$ family are suited to different application scenarios. The variants $\mathsf {SHINE0}$ and $\mathsf {MirrorSHINE}$ are best suited to cases where messages are of small, fixed size, such as customer credentials (or phone contact details, to return to the motivating example in the Introduction). For applications with longer messages (i.e. larger than the size of the exponentiation group), $\mathsf {OCBSHINE}$ is considerably faster and we will assume that these choices are made in our implementation suggestions. This removes any need for larger groups in order to encrypt longer messages. Using larger groups would not only carry a significant performance penalty, but also force us to construct custom large blocklength block ciphers. Although this can be done (and has been for RSA groups [14], where our approach would not work), the analysis is tricky.

Instantiating the Ideal Permutation. The message block in $\mathsf {SHINE0}$, $\mathsf {MirrorSHINE}$ and the final message block in $\mathsf {OCBSHINE}$ must be appropriately padded to allow application of the permutation. The permutation could be deployed using a variable-output-length sponge construction, a block cipher or an authenticated encryption scheme with a fixed key and suitably large nonce space. In practice, we suggest to instantiate the random permutation with a block cipher of a suitable block length. AES has only 128-bit blocks which does not match the minimum required size of the group, so we instead suggest block ciphers such as Threefish, or original Rijndael, allowing block lengths of 256 or 512 bits.

Map** to Elliptic Curve Group. We would like to instantiate our groups using elliptic curves. Using modern techniques it is always possible to find a suitable curve over a field with a size matching the block length of the ideal permutation, but using standard curves like NIST P-256 or P-521 seems desirable. A standard approach [19] is to embed bit strings in the X-coordinate of a point as follows. Note that close to half the field elements are X-coordinates of points. Given a field of size q, we consider a t-bit block as an integer $x_0$ and find a small integer u such that $u2^t+x_0$ is the X-coordinate of a curve point. If $\log q - t$ is between 8 and 9, this will fail to terminate with probability around $2^{-256}$ under reasonable assumptions.

With this approach we could use Threefish with 512-bit blocks together with NIST P-521 curve. If we want to use 256-bit blocks from Threefish, or original Rijndael, together with NIST P-256 curve, we can use a standard block cipher iteration trick [23] to reduce the block length from 256 bits, so that embedding in the X-coordinate still works, as follows. With block length $t+\tau $, concatenate a t-bit block with $\tau $ leading zeros and apply the block cipher until the $\tau $ leading bits of the result are all zeros. Discard these zeros to get a t-bit block. This is fairly cheap as for our purposes 8 or 9 bits will do.

Note that we have constructed an injective embedding of a block into an elliptic curve, not a bijection as assumed in our proofs. When we sample group elements in our proof, we must take care to sample points in the image of our embedding, but this can be done cheaply.

Notes

1.
Note that Boneh et al. [4], § Definition 7.6] use ciphertext-independence to mean that the updated ciphertext should have the same distribution as a fresh ciphertext (i.e. independent of the ciphertext in the previous epoch) – we follow the nomenclature of Lehmann and Tackmann [21].
2.
The notions $\mathsf {IND} \text {-}\mathsf {ENC}$, $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UPD} $ and $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UPD} $ (which we denote as $\mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CPA} $, $\mathsf {rand} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf {CPA} $ and $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf {CPA} $, resp.) are from LT18. The notions $\mathsf {UP}\text {-}\mathsf {IND} \text {-}\mathsf {CCA} $ and $\mathsf {UP}\text {-}\mathsf {REENC}\text {-}\mathsf {CCA} $ ($\mathsf {det} \mathsf {IND} \text {-}\mathsf {ENC} \text {-}\mathsf {CCA} $ and $\mathsf {det} \mathsf {IND} \text {-}\mathsf {UPD} \text {-}\mathsf {CCA} $, resp.) are from KLR19. LT18 and KLR19 both build upon the definitions given by EPRS.
3.
In the situation that the adversary does not corrupt any keys to the left or the right (or both) of the challenge epoch, the insulated region thus extends to the boundary (or boundaries) of the epoch continuum.

References

Ateniese, G., Fu, K., Green, M., Hohenberger, S.: Improved proxy re-encryption schemes with applications to secure distributed storage. In: Proceedings of NDSS 2005. The Internet Society (2005). https://doi.org/10.1145/1127345.1127346
Bellare, M., Namprempre, C.: Authenticated encryption: relations among notions and analysis of the generic composition paradigm. J. Cryptol. 21(4), 469–491 (2008). https://doi.org/10.1007/s00145-008-9026-x
Article MathSciNet MATH Google Scholar
Boneh, D., Lewi, K., Montgomery, H., Raghunathan, A.: Key homomorphic PRFs and their applications. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 410–428. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_23
Chapter Google Scholar
Boneh, D., Lewi, K., Montgomery, H.W., Raghunathan, A.: Key homomorphic PRFs and their applications. IACR Cryptology ePrint Archive, Report 2015/220 (2015). http://eprint.iacr.org/2015/220
Boyd, C., Davies, G.T., Gjøsteen, K., Jiang, Y.: Fast and secure updatable encryption. IACR Cryptology ePrint Archive, Report 2019/1457 (2019). https://eprint.iacr.org/2019/1457
Cachin, C., Camenisch, J., Freire-Stögbuchner, E., Lehmann, A.: Updatable tokenization: formal definitions and provably secure constructions. In: Kiayias, A. (ed.) FC 2017. LNCS, vol. 10322, pp. 59–75. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70972-7_4
Chapter Google Scholar
Canetti, R., Hohenberger, S.: Chosen-ciphertext secure proxy re-encryption. In: Ning, P., di Vimercati, S.D.C., Syverson, P.F. (eds.) Proceedings of ACM CCS 2007, pp. 185–194. ACM (2007). https://doi.org/10.1145/1315245.1315269
Coron, J.-S., Patarin, J., Seurin, Y.: The random oracle model and the ideal cipher model are equivalent. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 1–20. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_1
Chapter Google Scholar
Council, P.S.S.: Data security standard (PCI DSS v3.2.1) (2018). https://www.pcisecuritystandards.org/
Davidson, A., Deo, A., Lee, E., Martin, K.: Strong post-compromise secure proxy re-encryption. In: Jang-Jaccard, J., Guo, F. (eds.) ACISP 2019. LNCS, vol. 11547, pp. 58–77. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-21548-4_4
Chapter Google Scholar
Diaz-Santiago, S., Rodríguez-Henríquez, L.M., Chakraborty, D.: A cryptographic study of tokenization systems. In: Obaidat, M.S., Holzinger, A., Samarati, P. (eds.) Proceedings of SECRYPT 2014, pp. 393–398. SciTePress (2014). https://doi.org/10.5220/0005062803930398
Everspaugh, A., Paterson, K., Ristenpart, T., Scott, S.: Key rotation for authenticated encryption. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 98–129. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_4
Chapter Google Scholar
Everspaugh, A., Paterson, K.G., Ristenpart, T., Scott, S.: Key rotation for authenticated encryption. IACR Cryptology ePrint Archive, Report 2017/527 (2017). http://eprint.iacr.org/2017/527
Gentry, C., O’Neill, A., Reyzin, L.: A unified framework for trapdoor-permutation-based sequential aggregate signatures. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10770, pp. 34–57. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76581-5_2
Chapter Google Scholar
Jarecki, S., Krawczyk, H., Resch, J.K.: Updatable oblivious key management for storage systems. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) Proceedings of ACM CCS 2019, pp. 379–393. ACM (2019). https://doi.org/10.1145/3319535.3363196
Kallahalla, M., Riedel, E., Swaminathan, R., Wang, Q., Fu, K.: Plutus: scalable secure file sharing on untrusted storage. In: Chase, J. (ed.) Proceedings of FAST 2003. USENIX (2003). https://doi.org/10.5555/1090694.1090698
Klooß, M., Lehmann, A., Rupp, A.: (R)CCA secure updatable encryption with integrity protection. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part I. LNCS, vol. 11476, pp. 68–99. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_3
Chapter Google Scholar
Klooß, M., Lehmann, A., Rupp, A.: (R)CCA secure updatable encryption with integrity protection. IACR Cryptology ePrint Archive, Report 2019/222 (2019). https://eprint.iacr.org/2019/222
Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48(177), 203–209 (1987)
Article MathSciNet Google Scholar
Lee, E.: Improved security notions for proxy re-encryption to enforce access control. In: Lange, T., Dunkelman, O. (eds.) LATINCRYPT 2017. LNCS, vol. 11368, pp. 66–85. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25283-0_4
Chapter Google Scholar
Lehmann, A., Tackmann, B.: Updatable encryption with post-compromise security. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 685–716. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_22
Chapter Google Scholar
Myers, S., Shull, A.: Practical revocation and key rotation. In: Smart, N.P. (ed.) CT-RSA 2018. LNCS, vol. 10808, pp. 157–178. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76953-0_9
Chapter Google Scholar
Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 120–126 (1978)
Article MathSciNet Google Scholar
Rogaway, P., Bellare, M., Black, J., Krovetz, T.: OCB: a block-cipher mode of operation for efficient authenticated encryption. In: Reiter, M.K., Samarati, P. (eds.) Proceedings of ACM CCS 2001, pp. 196–205. ACM (2001). https://doi.org/10.1145/501983.502011
Sakurai, K., Nishide, T., Syalim, A.: Improved proxy re-encryption scheme for symmetric key cryptography. In: Proceedings of IWBIS 2017, pp. 105–111. IEEE (2017). https://doi.org/10.1109/IWBIS.2017.8275110
Shannon, C.E.: Communication theory of secrecy systems. Bell Syst. Tech. J. 28(4), 656–715 (1949)
Article MathSciNet Google Scholar

Download references

Acknowledgements

This research was funded by the Research Council of Norway under Project No. 248166. The second author is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement 802823. We would like to thank Frederik Armknecht, Håvard Raddum and Mohsen Toorani for fruitful discussions in the initial stages of this project, and anonymous reviewers for a number of useful suggestions for improvement.

Author information

Authors and Affiliations

Norwegian University of Science and Technology, NTNU, Trondheim, Norway
Colin Boyd, Kristian Gjøsteen & Yao Jiang
Bergische Universität Wuppertal, Wuppertal, Germany
Gareth T. Davies

Authors

Colin Boyd
View author publications
You can also search for this author in PubMed Google Scholar
Gareth T. Davies
View author publications
You can also search for this author in PubMed Google Scholar
Kristian Gjøsteen
View author publications
You can also search for this author in PubMed Google Scholar
Yao Jiang
View author publications
You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Gareth T. Davies , Kristian Gjøsteen or Yao Jiang .

Editor information

Editors and Affiliations

UC San Diego, La Jolla, CA, USA
Daniele Micciancio
Cornell Tech, New York, NY, USA
Thomas Ristenpart

Rights and permissions

Reprints and permissions

Copyright information

About this paper

Cite this paper

Boyd, C., Davies, G.T., Gjøsteen, K., Jiang, Y. (2020). Fast and Secure Updatable Encryption. In: Micciancio, D., Ristenpart, T. (eds) Advances in Cryptology – CRYPTO 2020. CRYPTO 2020. Lecture Notes in Computer Science(), vol 12170. Springer, Cham. https://doi.org/10.1007/978-3-030-56784-2_16

Download citation

DOI: https://doi.org/10.1007/978-3-030-56784-2_16
Published: 10 August 2020
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-56783-5
Online ISBN: 978-3-030-56784-2
eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

International Association for Cryptologic Research (opens in a new tab)