Paper 2020/1593

Towards Post-Quantum Updatable Public-Key Encryption via Supersingular Isogenies

Edward Eaton, David Jao, Chelsea Komlo, and Youcef Mokrani


We present the first post-quantum secure Key-Updatable Public-Key Encryption (UPKE) construction. UPKE has been proposed as a mechanism to improve the forward secrecy and post-compromise security of secure messaging protocols, but the hardness of all existing constructions rely on discrete logarithm assumptions. We focus our assessment on isogeny-based cryptosystems due to their suitability for performing a potentially unbounded number of update operations, a practical requirement for secure messaging where user conversations can occur over months, if not years. We begin by formalizing two UPKE variants in the literature as Symmetric and Asymmetric UPKE, which differ in how encryption and decryption keys are updated. We argue that Asymmetric UPKE constructions in the literature cannot be straightforwardly instantiated using SIDH nor CSIDH. We then describe a SIDH construction that partially achieves the required security notions for Symmetric UPKE, but due to existing mathematical limitations, cannot provide fine-grained forward secrecy. Finally, we present a CSIDH Symmetric UPKE construction that requires a parameter set in which the class group structure is fully known. We discuss open problems which are applicable to any cryptosystem with similar requirements for continuous operations over the secret domain.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
isogeniespost-quantum cryptographypublic-key encryptionsecure messaging
Contact author(s)
ckomlo @ uwaterloo ca
2021-10-03: last of 5 revisions
2020-12-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Edward Eaton and David Jao and Chelsea Komlo and Youcef Mokrani},
      title = {Towards Post-Quantum Updatable Public-Key Encryption via Supersingular Isogenies},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1593},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.