Paper 2024/499

CCA Secure Updatable Encryption from Non-Mappable Group Actions

Jonas Meers, Ruhr University Bochum
Doreen Riepel, University of California, San Diego

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 $\mathsf{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 $\mathsf{BIN}\text{-}\mathsf{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 $\mathsf{COM}\text{-}\mathsf{UE}$ extends $\mathsf{BIN}\text{-}\mathsf{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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. PQCrypto 2024
Updatable EncryptionGroup ActionsIsogeniesAlgebraic Group Action Model
Contact author(s)
jonas meers @ rub de
driepel @ ucsd edu
2024-04-01: approved
2024-03-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jonas Meers and Doreen Riepel},
      title = {CCA Secure Updatable Encryption from Non-Mappable Group Actions},
      howpublished = {Cryptology ePrint Archive, Paper 2024/499},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.