Paper 2021/769

Post-quantum Asynchronous Deniable Key Exchange and the Signal Handshake

Jacqueline Brendel, Rune Fiedler, Felix Günther, Christian Janson, and Douglas Stebila


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 (DVS) schemes. 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.

Note: Major Changes of Version 1.2: Emphasized differences in the definition of deniability to prior work in Section 1 and Section 4. Extended comparison with concurrent work ([48] and [29]), especially in light of ring signatures and DVS being equivalent for our case. Ensured consistent syntax for semi-static keys in Section 7. Fixed bound for deniability reduction of SPQR to account for pseudorandomness of tPRF in Theorem 6.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2022
authenticated key exchangedeniabilityasynchronousSignal protocolpost-quantumdesignated verifier signatures
Contact author(s)
rune fiedler @ cryptoplexity de
2022-03-29: last of 3 revisions
2021-06-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jacqueline Brendel and Rune Fiedler and Felix Günther and Christian Janson and Douglas Stebila},
      title = {Post-quantum Asynchronous Deniable Key Exchange and the Signal Handshake},
      howpublished = {Cryptology ePrint Archive, Paper 2021/769},
      year = {2021},
      doi = {10.1007/978-3-030-97131-1_1},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.