Paper 2021/538

A Composable Look at Updatable Encryption

Françoise Levy-dit-Vehel and Maxime Roméas

Abstract

Updatable Encryption (UE), as originally defined by Boneh et al. in 2013, addresses the problem of key rotation on outsourced data while maintaining the communication complexity as low as possible. The security definitions for UE schemes have been constantly updated since then. However, the security notion that is best suited for a particular application remains unclear. To solve this problem in the ciphertext-independent setting, we use the Constructive Cryptography (CC) framework defined by Maurer et al. in 2011. We define and construct a resource that we call Updatable Server-Memory Resource (USMR), and study the confidentiality guarantees it achieves when equipped with a UE protocol, that we also model in this framework. With this methodology, we are able to construct resources tailored for each security notion. In particular, we prove that IND-UE-RCCA is the right security notion for many practical UE schemes. As a consequence, we notably rectify a claim made by Boyd et al., namely that their IND-UE security notion is better than the IND-ENC+UPD notions, in that it hides the age of ciphertexts. We show that this is only true when ciphertexts can leak at most one time per epoch. We stress that UE security is thought of in the context of adaptive adversaries, and UE schemes should thus bring post-compromise confidentiality guarantees to the client. To handle such adversaries, we use an extension of CC due to Jost et al. and give a clear, simple and composable description of the post-compromise security guarantees of UE schemes. We also model semi-honest adversaries in CC. Our adaption of the CC framework to UE is generic enough to model other interactive protocols in the outsourced storage setting.