Abstract
In this paper we formalise public-key Updatable Encryption (PKUE), a primitive so far studied formally only in the symmetric setting. Defining UE in the public-key setting enables us to establish a new notion of security we call epoch confidentiality (EC) which considers the ability of an adversary to distinguish the public keys used in periods known as epochs and in turn reflects the leakage of the time in which a ciphertext was created. We propose a public-key UE construction and prove that it satisfies our new notion of security alongside a notion of ciphertext confidentiality such that efficiency is not affected by moving to the public-key setting.