Paper 2021/221

The Direction of Updatable Encryption Does Matter

Ryo Nishimaki

Abstract

We introduce a new definition for key updates, called backward-leak uni-directional key updates, in updatable encryption (UE). This notion is a variant of uni-directional key updates for UE. We show that there exist UE schemes that are secure in the bi-directional key updates setting, but not secure in the backward-leak uni-directional key updates setting. This result is a contrast to the equivalence theorem by Jiang (Asiacrypt 2020), which says security in the bi-directional key updates setting is equivalent to security in the uni-directional key updates setting (we call the latter ``forward-leak uni-directional'' key updates to distinguish two types of uni-directional key updates in this paper). We also construct two UE schemes with the following features. - The first scheme is post-quantum secure in the backward-leak uni-directional key updates setting under the learning with errors assumption. - The second scheme is secure in the no-directional key updates setting and based on indistinguishability obfuscation and one-way functions. This solves the open problem left by Jiang at Asiacrypt 2020.

Note: Minor typo correction.