Paper 2022/739

Updatable Encryption from Group Actions

Antonin Leroux, Direction Générale de l'Armement
Maxime Roméas, ANSSI
Abstract

Updatable Encryption (UE) allows to rotate the encryption key in the outsourced storage setting while minimizing the bandwith used. The server can update ciphertexts to the new key using a token provided by the client. UE schemes should provide strong confidentiality guarantees against an adversary that can corrupt keys and tokens. This paper studies the problem of building UE in the group action framework. We introduce a new notion of Mappable Effective Group Action (MEGA) and show that we can build CCA secure UE from a MEGA by generalizing the SHINE construction of Boyd etal at Crypto 2020. Unfortunately, we do not know how to instantiate this new construction in the post-quantum setting. Doing so would solve the open problem of building a CCA secure post-quantum UE scheme. Isogeny-based group actions are the most studied post-quantum group actions. Unfortunately, the resulting group actions are not mappable. We show that we can still build UE from isogenies by introducing a new algebraic structure called Effective Triple Orbital Group Action (ETOGA). We prove that UE can be built from an ETOGA and show how to instantiate this abstract structure from isogeny-based group actions. This new construction solves two open problems in ciphertext-independent post-quantum UE. First, this is the first post-quantum UE scheme that supports an unbounded number of updates. Second, our isogeny-based UE scheme is the first post-quantum UE scheme not based on lattices. The security of this new scheme holds under an extended version of the weak pseudorandomness of the standard isogeny group action.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Updatable EncryptionGroup ActionsIsogeniesPost-Quantum Cryptography
Contact author(s)
antonin leroux @ polytechnique org
romeas @ lix polytechnique fr
History
2023-11-27: last of 2 revisions
2022-06-09: received
See all versions
Short URL
https://ia.cr/2022/739
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2022/739,
      author = {Antonin Leroux and Maxime Roméas},
      title = {Updatable Encryption from Group Actions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/739},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/739}},
      url = {https://eprint.iacr.org/2022/739}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.