Paper 2025/2265

PRGUE Schemes: Efficient Updatable Encryption With Robust Security From Symmetric Primitives

Abstract

Securing sensitive data for long-term storage in the cloud is a challenging problem. Updatable encryption (UE) enables changing the encryption key of encrypted data in the cloud while the plaintext and all versions of the key remain secret from the cloud storage provider, making it an efficient alternative for companies that seek to outsource their data storage. The most secure UE schemes to date follow robust security models, such as the one by Boyd et al. from CRYPTO 2020, and rely exclusively on asymmetric cryptography, thus incurring a substantial performance cost. In contrast, the Nested UE construction of Boneh et al. from ASIACRYPT 2020 achieves much better efficiency with symmetric cryptography, but it provides weaker security guarantees. Boyd et al. further suggest that attaining robust UE security inherently requires the use of asymmetric cryptography. In this work, we show for the first time that symmetric UE schemes are not inherently limited in their security and can achieve guarantees on par with, and even beyond, Boyd’s UE model. To this end, we extend Boyd’s framework to encompass the class of ciphertext-dependent UE schemes and introduce indistinguishability-from-random (IND\$) as a stronger refinement of indistinguishability. While our IND\$ notion primarily streamlines the proofs of advanced security properties within the model, it yields practical privacy advantages: ciphertexts do not exhibit a recognizable structure that could otherwise distinguish them from arbitrary data. We then introduce two robustly secure symmetric UE constructions, tailored to different target security levels. Our schemes are built on a novel design paradigm that combines symmetric authenticated encryption with ciphertext re-randomization, leveraging for the first time the use of pseudorandom number generators in a one-time-pad style. This approach enables both robust security and high efficiency, including in AES-based implementations. Our first scheme, PUE-List, delivers encryption up to 600× faster than prior asymmetric schemes of similar robustness, while matching Boneh et al.’s efficiency and achieving the stronger security level of Boyd et al. Our second scheme, PUE-One, further boosts performance with constant-time decryption 24× faster than all previously known UE schemes, overcoming the main bottleneck in Boneh’s design, while trading off some security, yet still significantly surpassing the guarantees of Boneh’s Nested scheme.