No-Directional and Backward-Leak Uni-Directional Updatable Encryption Are Equivalent

Abstract

Updatable encryption (UE) enables the cloud server to update the previously sourced encrypted data to a new key with only an update token received from the client. Two interesting works have been proposed to clarify the relationships among various UE security notions. Jiang (ASIACRYPT 2020) proved the equivalence of every security notion in the bi-directional and uni-directional key update settings and further, the security notion in the no-directional key update setting is strictly stronger than the above two. In contrast, Nishimaki (PKC 2022) proposed a new definition of uni-directional key update that is called the backward-leak uni-directional key update, and showed the equivalence relation by Jiang does not hold in this setting. We present a detailed comparison of every security notion in the four key update settings and prove that the security in the backward-leak uni-directional key update setting is actually equivalent to that in the no-directional key update setting. Our result reduces the hard problem of constructing no-directional key update UE schemes to the construction of those with backward-leak uni-directional key updates.