On the Implications from Updatable Encryption to Public-Key Cryptographic Primitives

Updatable encryption (UE) is a special type of symmetric-key encryption (SKE) that allows a third party to update ciphertexts while protecting plaintexts. Alamati et al. (CRYPTO 2019) showed a curious connection between UE and public-key encryption (PKE) that PKE can be constructed from UE. This implication result is somewhat surprising since it is well-known that PKE cannot be constructed from (ordinary) SKE in a black-box manner. In this paper, we continue to study the relationships between UE and other cryptographic primitives to obtain further insights into the existence and power of UE, and assumptions required for it. More specifically, we introduce some security properties that are natural to consider for UE (and are indeed satisfied by some existing UE schemes), and then investigate what types of public-key cryptographic primitives can be constructed from UE with the additional properties. Specifically, we show the following results: