Cryptology ePrint Archive: Report 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 existing secure UE schemes in the bi-directional key updates setting are not secure in the backward-leak uni-directional key updates setting. Thus, security in the backward-leak uni-directional key updates setting is strictly stronger than security in the bi-directional key updates setting. This result is in sharp 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 existing uni-directional key updates setting. We call the existing uni-directional key updates ``forward-leak uni-directional'' key updates to distinguish two types of uni-directional key updates in this paper.

We also present 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 result solves the open problem left by Jiang (Asiacrypt 2020).

Category / Keywords: public-key cryptography / updatable encryption, key update, lattice,

Date: received 26 Feb 2021, last revised 15 Sep 2021

Contact author: ryo nishimaki zk at hco ntt co jp

Available format(s): PDF | BibTeX Citation

Note: The presentation was improved. (9/16/2021)

Version: 20210916:021712 (All versions of this report)

Short URL: ia.cr/2021/221


[ Cryptology ePrint archive ]