Updatable Public-Key Encryption, Revisited

Joël Alwen; Georg Fuchsbauer; Marta Mularczyk

Paper 2025/175

Updatable Public-Key Encryption, Revisited

Joël Alwen, AWS Wickr

Georg Fuchsbauer, TU Wien

Marta Mularczyk, AWS Wickr

Abstract

We revisit Updatable Public-Key Encryption (UPKE), which was introduced as a practical mechanism for building forward-secure cryptographic protocols. We begin by observing that all UPKE notions to date are neither syntactically flexible nor secure enough for the most important multi-party protocols motivating UPKE. We provide an intuitive taxonomy of UPKE properties -- some partially or completely overlooked in the past -- along with an overview of known (explicit and implicit) UPKE constructions. We then introduce a formal UPKE definition capturing all intuitive properties needed for multi-party protocols. Next, we provide a practical pairing-based construction for which we provide concrete security bounds under a standard assumption in the random oracle and the algebraic group model. The efficiency profile of the scheme compares very favorably with existing UPKE constructions (despite the added flexibility and stronger security). For example, when used to improve the forward security of the Messaging Layer Security protocol [RFC9420], our new UPKE construction requires $\approx 1\%$ of the bandwidth of the next-most efficient UPKE construction satisfying the strongest UPKE notion previously considered.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in EUROCRYPT 2024
DOI: 10.1007/978-3-031-58754-2_1
Contact author(s): alwenjo @ amazon com
georg fuchsbauer @ tuwien ac at
mulmarta @ amazon com
History: 2025-02-07: approved; 2025-02-05: received; See all versions
Short URL: https://ia.cr/2025/175
License: CC BY

BibTeX

@misc{cryptoeprint:2025/175,
      author = {Joël Alwen and Georg Fuchsbauer and Marta Mularczyk},
      title = {Updatable Public-Key Encryption, Revisited},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/175},
      year = {2025},
      doi = {10.1007/978-3-031-58754-2_1},
      url = {https://eprint.iacr.org/2025/175}
}