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.