Paper 2021/268

Puncture 'Em All: Updatable Encryption with No-Directional Key Updates and Expiring Ciphertexts

Daniel Slamanig and Christoph Striecks


Updatable encryption (UE) allows to periodically rotate encryption keys without the need to decrypt and re-encrypt already encrypted data. This is achieved by means of an update token that allows to perform the ciphertext update via any semi-trusted party. Unfortunately, apart from a recent UE construction from indistinguishability obfuscation (Nishimaki, ePrint'21), in all existing constructions the update token provides additional functionality and at least allows to downgrade keys. Such a leakage is undesirable and leads to rather involved and complex security models. A recent UE model due to Jiang (Asiacrypt'20), extending the model of Boyd et al. (Crypto'20), explicitly considers these directionality and leakage issues, and left open the construction of UE schemes where keys cannot be transformed via a token in any direction (aka UE schemes with "no-directional" key updates). In this work, we solve the problem via our threefold contribution: i) We introduce a simpler and cleaner UE CPA security notion extending prior models. It focuses on UE schemes with no-directional key updates and thus avoids the use of rather complex leakage profiles for UE. Moreover, it introduces the concept of expiry epochs, i.e., ciphertexts can lose the ability of being updatable after a certain time. This is determined at the time of encryption and inherently requires the no-directional key update feature of UE schemes. ii) We introduce a novel approach of constructing UE with no-directional key updates which significantly departs from previous ones and in particular views UE from the perspective of puncturable encryption (Green and Miers, S&P'15). As a stepping stone, we introduce a variant of puncturable encryption called ciphertext puncturable encryption (CPE). This turns out to be a useful abstraction on our way to construct UE and may be of independent interest. iii) Finally, we present a CPE instantiation from standard assumptions (i.e., the standard d-Lin assumption in prime-order bilinear groups) which via ii) yields the first UE scheme with no-directional key updates and expiry epochs from standard assumptions.

Note: This updated version contains new results, particularly, a novel construction of ciphertext puncturable encryption with sub-linear parameter sizes.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
Updatable EncryptionPuncturable Encryption
Contact author(s)
Christoph Striecks @ ait ac at
Daniel Slamanig @ ait ac at
2021-12-17: last of 2 revisions
2021-03-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Slamanig and Christoph Striecks},
      title = {Puncture 'Em All: Updatable Encryption with No-Directional Key Updates and Expiring Ciphertexts},
      howpublished = {Cryptology ePrint Archive, Paper 2021/268},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.