Updatable Public Key Encryption in the Standard Model

Yevgeniy Dodis, Harish Karthikeyan, Daniel Wichs

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Forward security (FS) ensures that corrupting the current secret key in the system preserves the privacy or integrity of the prior usages of the system. Achieving forward security is especially hard in the setting of public-key encryption (PKE), where time is divided into periods, and in each period the receiver derives the next-period secret key from their current secret key, while the public key stays constant. Indeed, all current constructions of FS-PKE are built from hierarchical identity-based encryption (HIBE) and are rather complicated. Motivated by applications to secure messaging, recent works of Jost et al. (Eurocrypt’19) and Alwen et al. (CRYPTO’20) consider a natural relaxation of FS-PKE, which they term updatable PKE (UPKE). In this setting, the transition to the next period can be initiated by any sender, who can compute a special update ciphertext. This ciphertext directly produces the next-period public key and can be processed by the receiver to compute the next-period secret key. If done honestly, future (regular) ciphertexts produced with the new public key can be decrypted with the new secret key, but past such ciphertexts cannot be decrypted with the new secret key. Moreover, this is true even if all other previous-period updates were initiated by untrusted senders. Both papers also constructed a very simple UPKE scheme based on the CDH assumption in the random oracle model. However, they left open the question of building such schemes in the standard model, or based on other (e.g., post-quantum) assumptions, without using the heavy HIBE techniques. In this work, we construct two efficient UPKE schemes in the standard model, based on the DDH and LWE assumptions, respectively. Somewhat interestingly, our constructions gain their efficiency (compared to prior FS-PKE schemes from the same assumptions) by using tools from the area of circular-secure and leakage resilient public-key encryption schemes (rather than HIBE).

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 19th International Conference, TCC 2021, Proceedings
EditorsKobbi Nissim, Brent Waters, Brent Waters
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages32
ISBN (Print)9783030904555
StatePublished - 2021
Event19th International Conference on Theory of Cryptography, TCC 2021 - Raleigh, United States
Duration: Nov 8 2021Nov 11 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13044 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th International Conference on Theory of Cryptography, TCC 2021
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Updatable Public Key Encryption in the Standard Model'. Together they form a unique fingerprint.

Cite this