Cryptology ePrint Archive: Report 2021/769

Post-quantum asynchronous deniable key exchange and the Signal handshake

Jacquline Brendel and Rune Fiedler and Felix GŁnther and Christian Janson and Douglas Stebila

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 KEM-based replacement for the Signal handshake 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 schemes. Furthermore, we show how designated verifier signatures can be built by using chameleon hash functions in both full-domain-hash and Fiat--Shamir-style signature schemes, enabling efficient post-quantum instantiations. This provides the first efficient post-quantum realization of the Signal handshake with the same asynchronicity and security properties as the original Signal protocol.

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

Date: received 8 Jun 2021

Contact author: rune fiedler at cryptoplexity de

Available format(s): PDF | BibTeX Citation

Version: 20210609:062642 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]