CCA Secure Updatable Encryption from Non-Mappable Group Actions

Abstract

Ciphertext-independent updatable encryption (UE) allows to rotate encryption keys and update ciphertexts via a token without the need to first download the ciphertexts. Although, syntactically, UE is a symmetric-key primitive, ciphertext-independent UE with forward secrecy and post-compromise security is known to imply public-key encryption (Alamati, Montgomery and Patranabis, CRYPTO 2019).

Constructing post-quantum secure UE turns out to be a difficult task. While lattices offer the necessary homomorphic properties, the introduced noise allows only a bounded number of updates. Group actions have become an important alternative, however, their structure is limited. The only known UE scheme by Leroux and Roméas (IACR ePrint 2022/739) uses effective triple orbital group actions which uses additional algebraic structure of CSIDH. Using an ideal cipher, similar to the group-based scheme SHINE (Boyd et al., CRYPTO 2020), requires the group action to be mappable, a property that natural isogeny-based group actions do not satisfy. At the same time, other candidates based on non-commutative group actions suffer from linearity attacks.

For these reasons, we explicitly ask how to construct UE from group actions that are not mappable. As a warm-up, we present BIN-UE which uses a bit-wise approach and is CPA secure based on the well-established assumption of weak pseudorandomness and in the standard model. We then construct the first actively secure UE scheme from post-quantum assumptions. Our scheme COM-UE extends BIN-UE via the Tag-then-Encrypt paradigm. We prove CCA security in the random oracle model based on a stronger computational assumption. We justify the hardness of our new assumption in the algebraic group action model.