In this paper, we introduce the notion of a split key encapsulation mechanism (split KEM) to translate the desired key-reusability of a DH-based protocol to a KEM-based flow. We provide the relevant security notions of split KEMs and show how the formalism lends itself to lifting Signal's X3DH handshake to the post-quantum KEM setting without additional message flows.
Although the proposed framework conceptually solves the raised issues, instantiating it securely from post-quantum assumptions proved to be non-trivial. We give passively secure instantiations from (R)LWE, yet overcoming the above-mentioned insecurities under key reuse in the presence of active adversaries remains an open problem. Approaching one-sided key reuse, we provide a split KEM instantiation that allows such reuse based on the KEM introduced by Kiltz (PKC 2007), which may serve as a post-quantum blueprint if the underlying hardness assumption (gap hashed Diffie-Hellman) holds for the commutative group action of CSIDH (Asiacrypt 2018).
The intention of this paper hence is to raise awareness of the challenges arising when moving to KEM-based key exchange protocols with key-reusability, and to propose split KEMs as a specific target for instantiation in future research.
Category / Keywords: cryptographic protocols / post-quantum, key encapsulation mechanisms, key exchange, Signal protocol, X3DH Original Publication (in the same form): Selected Areas in Cryptography (SAC 2020) Date: received 25 Nov 2019, last revised 5 Oct 2020 Contact author: mail at jbrendel-info de Available format(s): PDF | BibTeX Citation Version: 20201005:151748 (All versions of this report) Short URL: ia.cr/2019/1356