Douglas Stebila

Post-quantum asynchronous deniable key exchange and the Signal handshake

Our core asynchronous deniable authenticated key exchange protocol, combining static and ephemeral key encapsulation schemes KEM1 and KEM2, and a designated verifier signature DVS.

Abstract

The key exchange protocol that establishes initial shared secrets in the handshake of the Signal end-to-end encrypted messaging protocol has several important characteristics: (1) it runs asynchronously (without both parties needing to be simultaneously online), (2) it provides implicit mutual authentication while retaining deniability (transcripts cannot be used to prove either party participated in the protocol), and (3) it retains security even if some keys are compromised (forward secrecy and beyond). All of these properties emerge from clever use of the highly flexible Diffie–Hellman protocol.

While quantum-resistant key encapsulation mechanisms (KEMs) can replace Diffie–Hellman key exchange in some settings, there is no replacement for the Signal handshake solely from KEMs that achieves all three aforementioned properties, in part due to the inherent asymmetry of KEM operations. In this paper, we show how to construct asynchronous deniable key exchange by combining KEMs and designated verifier signature (DVS) schemes, matching the characteristics of Signal. There are several candidates for post-quantum DVS schemes, either direct constructions or via ring signatures. This yields a template for an efficient post-quantum realization of the Signal handshake with the same asynchronicity and security properties as the original Signal protocol.

Keywords: authenticated key exchange, deniability, asynchronous, Signal protocol, post-quantum, designated verifier signatures

Reference

Jacqueline Brendel, Rune Fiedler, Felix Günther, Christian Janson, Douglas Stebila. Post-quantum asynchronous deniable key exchange and the Signal handshake. In Goichiro Hanaoka, Junji Shikata, Yohei Watanabe, editors, Proc. 25th International Conference on Practice and Theory of Public-Key Cryptography (PKC) 2022, LNCS, vol. 13178, pp. 3–34. Springer, March 2022.

Download

BibTeX

@inproceedings{PKC:BFGJS22,
 	Author = {Jacqueline Brendel and Rune Fiedler and Felix G{\" u}nther and Christian Janson and Douglas Stebila},
 	Booktitle = {Proc. PKC 2022},
 	Doi = {10.1007/978-3-030-97131-1_1},
 	Editor = {Goichiro Hanaoka and Junji Shikata and Yohei Watanabe},
 	Month = {March},
 	Note = {\url{http://eprint.iacr.org/2021/769}},
 	Pages = {3--34},
 	Publisher = {Springer},
 	Series = {LNCS},
 	Title = {Post-quantum asynchronous deniable key exchange and the {S}ignal handshake},
 	Volume = {13187},
 	Year = {2022}
 }

Funding

• Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2016-05146
• German Federal Ministry of Education and Research and the Hessian Ministry of Higher Education, Research, Science and the Arts within their joint support of the National Research Center for Applied Cybersecurity ATHENE
• German Research Foundation (DFG) Research Fellowship grant GU 1859/1-1
• Deutsche Forschungsgemeinschaft (DFG) – SFB 1119 – 236615297