Paper 2020/222

Improving Speed and Security in Updatable Encryption Schemes

Dan Boneh and Saba Eskandarian and Sam Kim and Maurice Shih

Abstract

An updatable encryption scheme is a symmetric-key encryption scheme that supports key-rotation on ciphertexts. A server that hosts a user's encrypted data can use a user-provided update token to rotate the key under which the data is encrypted while not learning any information about the underlying data. This work's contributions are threefold. First, we introduce new definitions for updatable encryption (in the ciphertext-dependent setting) that capture desirable security properties not covered in prior work. Next, we construct two new updatable encryption schemes. The first construction relies only on symmetric cryptographic primitives but only supports a bounded number of key rotations. The second supports a (nearly) unbounded number of updates and relies on almost key-homomorphic PRFs. We construct an efficient almost key-homomorphic PRF from the Ring Learning with Errors (RLWE) assumption to concretely instantiate our second construction. Finally, we implement both constructions and compare their performance to prior work. Our RLWE-based construction outperforms an existing updatable encryption scheme based on the hardness of DDH in elliptic-curve groups by over 200x in speed. Our construction based only on symmetric primitives has the highest encryption throughput, approaching the performance of AES, and the highest decryption throughput on ciphertexts that were re-encrypted fewer than fifty times, at which point the RLWE construction dominates.