Paper 2019/1457

RISE and SHINE: Fast and Secure Updatable Encryption

Colin Boyd and Gareth T. Davies and Kristian Gjøsteen and Yao Jiang

Abstract

Updatable encryption allows a client to outsource ciphertexts to some untrusted server and periodically rotate the encryption key. The server can update ciphertexts from an old key to a new key with the help of an update token, received from the client, which should not reveal anything about keys or plaintexts to an adversary. We provide a new and highly efficient updatable encryption scheme called SHINE. Ciphertext generation consists of applying one permutation and one exponentiation (per message block), while updating ciphertexts requires just one exponentiation. We also define a new security notion for updatable encryption schemes that implies prior notions (for schemes with randomized and deterministic updates). We prove that SHINE and the previous best scheme, RISE, are secure under our new definition.