Revisiting Updatable Encryption: True Forward Security, Constructions and a Puncturable Perspective

Daniel Slamanig; Christoph Striecks

Paper 2021/268

Revisiting Updatable Encryption: True Forward Security, Constructions and a Puncturable Perspective

Daniel Slamanig

, AIT Austrian Institute of Technology

Christoph Striecks

, AIT Austrian Institute of Technology

Abstract

Updatable encryption (UE) allows to periodically rotate encryption keys without the need to decrypt and re-encrypt already encrypted data. In this work, we present an attack which is not covered by prior ciphertext-independent UE security notions and which seems problematic in practice; namely, an adversary would record available information (i.e., ciphertexts, all update tokens) in the lifetime of the system and simply would wait for a single key leakage. To mitigate such an attack, we require a more fine-grained ciphertext-update approach where ciphertexts are allowed to expire after some time. Our threefold contribution is as follows: a) First, we introduce a UE CPA security notion to allow fine-grained updatability. It focuses on UE schemes where the token can only forwardly update the ciphertext and thus reduces complexity compared to prior models. Additionally, 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 captures the above mentioned attack. b) Second, we present and prove secure the first UE scheme with such properties. We construct it from standard assumptions (e.g., the SXDH assumption in prime-order bilinear groups) using the well-known dual system paradigm. To overcome the hurdles towards UE with such strong properties, we require novel construction and adapted proof techniques. Noteworthy, our optimized UE scheme enjoys sublinear key and ciphertext sizes. c) Finally, as an extension, we introduce a novel approach of constructing UE which significantly departs from previous ones and in particular views UE from the perspective of puncturable encryption (Green and Miers, S&P'15). We introduce a variant of puncturable encryption called ciphertext-puncturable encryption (CPE) which generalizes UE and may be of independent interest.

Note: Major rewrite, title change.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Updatable Encryption Puncturable Encryption
Contact author(s): Daniel Slamanig @ ait ac at
Christoph Striecks @ ait ac at
History: 2022-10-07: last of 3 revisions; 2021-03-03: received; See all versions
Short URL: https://ia.cr/2021/268
License: CC BY

BibTeX

@misc{cryptoeprint:2021/268,
      author = {Daniel Slamanig and Christoph Striecks},
      title = {Revisiting Updatable Encryption: True Forward Security, Constructions and a Puncturable Perspective},
      howpublished = {Cryptology ePrint Archive, Paper 2021/268},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/268}},
      url = {https://eprint.iacr.org/2021/268}
}