Paper 2019/1457

Fast and Secure Updatable Encryption

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


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 suite of updatable encryption schemes that we collectively call SHINE. In the variant designed for short messages, ciphertext generation consists of applying one permutation and one exponentiation (per message block), while updating ciphertexts requires just one exponentiation. Variants for longer messages provide much stronger security guarantees than prior work that has comparable efficiency. We present a new confidentiality notion for updatable encryption schemes that implies prior notions. We prove that SHINE is secure under our new confidentiality definition while also providing ciphertext integrity.

Note: Fixed the counterexample in Theorem 2.7, plus added explicit ciphertext length check to the IND-UE game syntax in Fig. 17. Document history is detailed in Section 1.4.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2020
updatable encryptioncloud storagekey rotation
Contact author(s)
davies @ uni-wuppertal de
2022-02-25: last of 3 revisions
2019-12-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Colin Boyd and Gareth T.  Davies and Kristian Gjøsteen and Yao Jiang},
      title = {Fast and Secure Updatable Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1457},
      year = {2019},
      doi = {10.1007/978-3-030-56784-2_16},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.