[Resource Topic] 2021/268: Puncture 'Em All: Updatable Encryption with No-Directional Key Updates and Expiring Ciphertexts

Welcome to the resource topic for 2021/268

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

Authors: Daniel Slamanig, 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.

ePrint: https://eprint.iacr.org/2021/268

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .