Strongly Secure Updatable Encryption Requires Public-Key Cryptography
Marc Fischlin, Gözde Saçıak · IACR Communications in Cryptology · 2025
Updatable encryption (UE), introduced by Boneh et al. (Crypto 2013), enables a secure rotation of symmetric encryption keys for outsourced encrypted data, without needing to download, decrypt, and re-encrypt the data. Many existing UE schemes, however, use public-key operations for the update step. This work investigates whether truly symmetric UE schemes can achieve modern UE security notions such as IND-ENC (indistinguishability of encryption) or IND-UPD (indistinguishability of updates) without relying on public-key primitives. Alamati et al. (Crypto 2019) showed that randomized update steps in IND-UPD-secure UE schemes already necessitate public-key cryptography if the update step is independent of the ciphertext. However, the IND-UPD security notion is usually not required for scenarios in which the history of updates is known, such that one may still hope to derive an IND-ENC secure solution based on symmetric encryption. We argue here that this is illusory for IND-ENC solutions with optimal leakage. Optimal leakage refers to the ideal situation where update steps only allow the computation of ciphertexts in the forward direction and do not leak anything about the updated keys. We show that such schemes inherently rely on public-key cryptography.