Paper 2026/2164

On the Limits of LWE and PCE based UPKE

Abstract

Updatable Public-Key Encryption (UPKE) enables forward secrecy in asynchronous settings like secure group messaging. At EC'25, Albrecht, Benčina and Lai proposed the first plausibly post-quantum UPKE scheme supporting unlimited updates, based on permutation code equivalence (PCE) over finite fields and hollow lattice problems. However, it has impractically large public keys (4.8MiB) and ciphertexts (1.5MiB). In this work, we first replace the information-theoretic Hollow LHL with a computational assumption secure under binary-secret binary-error LWE, reducing key sizes by an order of magnitude. Second, we show that generalising to Module-LWE is not beneficial: PCE instances over $\mathbb{F}_{q^d}$ admit a linearisation attack via the $q$-Frobenius structure, enabling recovery of secret isometries unless code rates are inflated by $d$, negating any size benefit from module lattices. Third, we establish IND-CCA security in the model of Alwen, Fuchsbauer and Mularczyk (EC'24), but do not achieve `joiner security' like other post-quantum candidates. Finally, we introduce a heuristic multi-key variant using matrix-valued secret keys, enabling efficient encryption of $\ell$ bits per ciphertext. We define the Hinted SPCE assumption to capture the main cryptanalytic challenge and show that the performance gain is likely too small to justify adoption, unless the new assumption can be avoided. Overall, our `unlimited' scheme has update sizes 3.5 to 10 times larger than lattice-based schemes limited to $2^{20}$ updates, depending on the aggressiveness of parameter choices.