Douglas Stebila

Towards post-quantum security for Signal's X3DH handshake

Communication flow for a split KEM

Abstract

Modern key exchange protocols are usually based on the Diffie–Hellman (DH) primitive. The beauty of this primitive, among other things, is its potential reusage of key shares: DH shares can be either used once as an ephemeral key or used in multiple runs as a (semi-)static key. Since DH-based protocols are insecure against quantum adversaries, alternative solutions have to be found when moving to the post-quantum setting. However, most post-quantum candidates, including schemes based on lattices and even supersingular isogeny DH, are not known to be secure under key reuse. In particular, this means that they cannot be necessarily deployed as an immediate DH substitute in protocols.

In this paper, we introduce the notion of a split key encapsulation mechanism (split KEM) to translate the desired properties of a DH-based protocol, namely contributiveness and key-reusability, to a KEM-based protocol flow. We provide the relevant security notions of split KEMs and show that the formalism lends itself to lift Signal's X3DH to the post-quantum KEM setting. While the proposed framework conceptually solves the raised issues, we did not succeed in providing a strongly-secure, post- quantum instantiation of a split KEM yet. The intention of this paper hence is to raise further awareness of the challenges arising when moving to KEM-based key exchange protocols with contributiveness and key-resusability, and to enable others to start investigating potential solutions.

Keywords: key encapsulation mechanisms, key exchange, post-quantum, Diffie–Hellman

Reference

Jacqueline Brendel, Marc Fischlin, Felix Günther, Christian Janson, Douglas Stebila. Towards post-quantum security for Signal's X3DH handshake. In Michael J. Jacobson Jr., Orr Dunkelman, Colin O’Flynn, editors, Selected Areas in Cryptography (SAC) 2020, LNCS, vol. 12804, pp. 404–430. Springer, October 2020. © Springer.

Download

BibTeX

@inproceedings{SAC:BFGJS20,
 	Author = {Jacqueline Brendel and Marc Fischlin and Felix G{\" u}nther and Christian Janson and Douglas Stebila},
 	Booktitle = {Proc. 27th Conference on Selected Areas in Cryptography (SAC) 2020},
 	Doi = {10.1007/978-3-030-81652-0_16},
 	Editor = {Michael J. Jacobson Jr. and Orr Dunkelman and Colin O’Flynn},
 	Month = {October},
 	Note = {Cryptology ePrint Archive, Report 2019/1356. \url{http://eprint.iacr.org/2019/1356}},
 	Pages = {404--430},
 	Publisher = {Springer},
 	Series = {LNCS},
 	Title = {Towards post-quantum security for {S}ignal's {X3DH} handshake},
 	Volume = {12804},
 	Year = {2020}
 }

Funding

• Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2016-05146
• NSERC Discovery Accelerator Supplement grant RGPIN-2016-05146
• German Research Foundation (DFG) as part of project S4 within the CRC 1119 CROSSING
• German Research Foundation (DFG) as part of project P2 within the CRC 1119 CROSSING
• German Research Foundation (DFG) as part of project D.2 within the RTG 2050 "Privacy and Trust for Mobile Users"
• German Research Foundation (DFG) Research Fellowship grant GU 1859/1-1
• National Science Foundation (NSF) grants CNS-1526801 and CNS-1717640