Paper 2026/2096

Perpetual Encryption

Abstract

Traditional public-key encryption (PKE) schemes have a static secret key. This means that the secret key owner can decrypt any old ciphertext in perpetuity. Schemes with changing secret keys, supporting so-called epochs, have been considered for a variety of reasons, such as post-compromise security or more simply supporting communication among a dynamically changing group. This complicates perpetuity, especially in settings where the epoch number itself is supposed to be confidential. We address this concern by introducing perpetual encryption (PE). The scheme leverages a trusted group manager to distribute states for each epoch such that: (1) without such a secret state, ciphertexts look pseudorandom and, hence, hide the epoch number; and (2) parties in a later epoch can still decrypt encryptions for old epochs in sublinear time (in the number of epochs). More stringently, we require that whenever a party in an earlier epoch decrypts to a message m then any party in a later epoch must arrive at the same message, even for adversarially crafted ciphertexts. We build an efficient, unbounded-epoch PE scheme based on anonymous PKE, hashing, and other standard symmetric primitives. We also extend our scheme to protect against malicious group managers, at the expense of limiting the maximum number of epochs. All our schemes have fixed-sized states and decryption times, independent of the number of epochs.