Paper 2021/559

A Fresh Approach to Updatable Symmetric Encryption

Andrés Fabrega, Ueli Maurer, and Marta Mularczyk

Abstract

Updatable encryption (UE) is symmetric encryption which additionally supports key rotation. UE was introduced for scenarios where a user stores encrypted data on a cloud and, in order to mitigate secret key leakage, periodically sends a short update token, which the cloud uses to re-encrypt stored data to a fresh key. A long line of research resulted in a wide variety of security properties UE schemes can provide, including confidentiality, integrity protection, and hiding metadata. Unfortunately, given the complexity and nuances in the definitions, different properties are difficult to compare for non-experts, making it hard to judge which scheme provides the best security-efficiency trade-off for a given application. In this work, we challenge the approach of defining UE as a primitive with a set of properties. As an alternative, we propose to treat UE as an interactive protocol, whose goal is to implement secure outsourced storage, using limited and imperfect resources (such as a small, leakable memory). To facilitate this approach, we introduce a framework that allows to easily formalize different security guarantees and available resources, making security-efficiency trade-offs of UE protocols easy to compare. We believe that our approach opens the way for many constructions of secure storage that are not compatible with the currently defined syntax of UE. Indeed, we propose two new protocols: one for the setting with adversaries who control randomness (an attack vector so far not considered for UE), and one for the setting with adversaries that actively tamper with memory. Both protocols provide stronger confidentiality guarantees than all existing UE schemes.