Updatable Public-Key Encryption from FESTA

Andrea Basso; Tako Boris Fouotsa; Fatna Kouider; Péter Kutas; Luciano Maino; Laurane Marco

Paper 2026/1014

Updatable Public-Key Encryption from FESTA

Andrea Basso

, IBM Research - Zurich

Tako Boris Fouotsa

, University of Manchester

Fatna Kouider

, Eötvös Loránd University

Péter Kutas, Eötvös Loránd University and University of Birmingham

Luciano Maino

, University of Birmingham

Laurane Marco

, École Polytechnique Fédérale de Lausanne

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 an efficient post-quantum secure UPKE scheme with unbounded updates remains an open problem. In this work, we propose an isogeny-based UPKE that relies on a dimension-four version of the FESTA public-key encryption scheme. It is practically efficient and supports an unbounded amount of updates. Moreover, we provide a formal security proof based on a problem in isogeny-based cryptography that has received considerable scrutiny.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Isogenies Updatable Public-Key Encryption FESTA
Contact author(s): Andrea Basso @ ibm com
research @ borisfouotsa com
fatnakouider @ inf elte hu
kutasp @ gmail com
l maino @ bham ac uk
marco laurane @ outlook com
History: 2026-05-21: revised; 2026-05-20: received; See all versions
Short URL: https://ia.cr/2026/1014
License: CC BY

BibTeX

@misc{cryptoeprint:2026/1014,
      author = {Andrea Basso and Tako Boris Fouotsa and Fatna Kouider and Péter Kutas and Luciano Maino and Laurane Marco},
      title = {Updatable Public-Key Encryption from {FESTA}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1014},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1014}
}