Paper 2026/1014

Updatable Public-Key Encryption from FESTA

Abstract

Updatable public-key encryption (UPKE) is a cryptographic primitive that was proposed for secure messaging to provide forward secrecy in public-key settings. It extends standard public-key encryption with a key-update mechanism that lets anyone update a receiver’s public key and issue a corresponding token for updating the secret key. Unlike traditional forward secrecy where all past messages should remain secure after a key leakage, UPKEs guarantee security only as long as at least one honest update has occurred. While classically-secure efficient instantiations of UPKE are known from Diffie-Hellman assumptions, constructing \emph{efficient post-quantum secure} UPKE schemes with \emph{unbounded} updates remains an active research area. For example, prior lattice-based constructions have update tokens of size 1486 KiB. While isogeny group action based constructions offer acceptable sizes, their quantum security is still subject to debate. Designing efficient isogeny-based UPKEs, which are not based on group actions, is still an open problem. In this work, we propose a new isogeny-based UPKE that relies on a dimension-four version of the $\mathsf{FESTA}$ public-key encryption scheme. It allows an unbounded number of updates. Moreover, we provide a formal security proof based on the $\mathsf{CIST}^2$ problem introduced in $\mathsf{FESTA}$ and on the $\mathsf{IND\text{-}KLPT}$ assumption which states that outputs of the $\mathsf{KLPT}$ algorithm are indistinguishable from random isogenies of the same degree. Our UPKE is compact, with public keys, ciphertexts and update tokens of size 0.4 KiB, 2.13 KiB and 2.13 KiB, respectively; hence being the second most compact post-quantum UPKE after isogeny group action based ones. When compared to SILBE, the prior isogeny-based UPKE which did not rely on isogeny group actions, our UPKE is several orders of magnitude more efficient.