Cryptology ePrint Archive: Report 2020/1593

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

Edward Eaton and David Jao and 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.

Category / Keywords: public-key cryptography / isogenies, post-quantum cryptography, public-key encryption, secure messaging

Date: received 21 Dec 2020, last revised 3 Oct 2021

Contact author: ckomlo at uwaterloo ca

Available format(s): PDF | BibTeX Citation

Version: 20211003:175309 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]