Paper 2025/1853

Compact, Efficient and CCA-Secure Updatable Encryption from Isogenies

Abstract

Updatable Encryption (UE) allows ciphertexts to be updated under new keys without decryption, enabling efficient key rotation. Constructing post-quantum UE with strong security guarantees is challenging: the only known CCA-secure scheme, COM-UE, uses bitwise encryption, resulting in large ciphertexts and high computational costs. We introduce $\mathsf{DINE}_\ell$, a family of compact and efficient CCA-secure isogeny-based post-quantum UE schemes parametrized by an integer $\ell$, achieving increasing security levels for $\ell = 3,4,8$. Each encryption, decryption, or update requires only a few power-of-2 isogeny computations in dimension 2. At NIST security level 1, $\mathsf{DINE}_\ell$ supports 28B messages, 480B ciphertexts, and $\ell\times336$B update tokens, significantly smaller than prior constructions. Our C implementation demonstrates practical performance, with updates in $\ell \times 15$ms, encryptions in 65ms, and decryptions in 155ms. Our design combines high-dimensional isogeny representations with the Deuring correspondence. We also introduce new algorithms for the Deuring correspondence which may be of independent interest. Moreover, the security of our scheme relies on new problems that might open interesting perspectives in isogeny-based cryptography.

Note: latest update, correct some errors in the security proof, takes into account the latest attacks against isogeny-based cryptography