Paper 2020/1282

Compact Authenticated Key Exchange in the Quantum Random Oracle Model

Abstract

Several quantum-resistant authenticated key exchange protocols (AKEs) have been proposed from supersingular isogeny and lattice. Most of their security analyses are conducted in the classical random oracle model, leaving their securities in the quantum random oracle model (QROM) as open problems. In this paper, we propose a generic construction of two-message AKE in QROM. It can be regarded as a QROM-secure version of X3LH [Xue et al. ASIACRYPT 2018], a generic AKE based on double-key PKE. We prove that, with some modification, the QROM security of X3LH can be reduced to the one-way security of double-key PKE. Aside from answering open problems on the QROM security of prior AKEs, such as SIAKE [Xu et al. ASIACRYPT 2019] based on supersingular isogeny, 2Kyber-AKE based on Module-LWE, and FSXY, we propose a new construction, CSIAKE, based on commutative supersingular isogeny. Our framework enjoys the following desirable features. First of all, it supports PKEs with non-perfect correctness. Secondly, the basic building block is compact and only requires one-wayness. Finally, the resulting AKE achieves the security in CK+ model as strong as X3LH, and the transformation overhead is low.