Paper 2020/1593

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

Edward Eaton and David Jao and and Chelsea Komlo

Abstract

In this work, we present the first post-quantum secure Updatable Public-Key Encryption (UPKE) construction. UPKE has been proposed in the literature as a mechanism to improve the forward-secrecy and post-compromise security of secure messaging protocols, but the hardness of all existing constructions to date 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 presented in the literature as Symmetric and Asymmetric UPKE. At a fundamental level, these variants differ in how encryption and decryption keys are updated, and consequently impact the design and security model for quantum-safe constructions. We demonstrate that Asymmetric UPKE cannot be instantiated using existing isogeny-based constructions. We then describe a SIDH-based Symmetric UPKE construction that is possible in theory but requires improving existing mathematical limitations before a practical implementation is possible. Finally, we present a CSIDH-based Symmetric UPKE construction that can be instantiated using a parameter set in which the class group structure is fully known to ensure efficient uniform sampling and canonical representation to prevent leakage of secret keys. We discuss several open problems which are applicable to any cryptosystem with similar requirements for continuous operations over elements in the secret domain.