Paper 2020/1593

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

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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
isogeniespost-quantum cryptographypublic-key encryptionsecure messaging
Contact author(s)
ckomlo @ uwaterloo ca
History
2021-10-03: last of 5 revisions
2020-12-24: received
See all versions
Short URL
https://ia.cr/2020/1593
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1593,
      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{https://eprint.iacr.org/2020/1593}},
      url = {https://eprint.iacr.org/2020/1593}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.