Paper 2024/120

K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures

Daniel Collins, École Polytechnique Fédérale de Lausanne
Loïs Huguenin-Dumittan, École Polytechnique Fédérale de Lausanne
Ngoc Khanh Nguyen, King's College London
Nicolas Rolin, Spuerkeess
Serge Vaudenay, École Polytechnique Fédérale de Lausanne

The Signal protocol and its X3DH key exchange core are regularly used by billions of people in applications like WhatsApp but are unfortunately not quantum-secure. Thus, designing an efficient and post-quantum secure X3DH alternative is paramount. Notably, X3DH supports asynchronicity, as parties can immediately derive keys after uploading them to a central server, and deniability, allowing parties to plausibly deny having completed key exchange. To satisfy these constraints, existing post-quantum X3DH proposals use ring signatures (or equivalently a form of designated-verifier signatures) to provide authentication without compromising deniability as regular signatures would. Existing ring signature schemes, however, have some drawbacks. Notably, they are not generally proven secure in the quantum random oracle model (QROM) and so the quantum security of parameters that are proposed is unclear and likely weaker than claimed. In addition, they are generally slower than standard primitives like KEMs. In this work, we propose an efficient, deniable and post-quantum X3DH-like protocol that we call K-Waay, that does not rely on ring signatures. At its core, K-Waay uses a split-KEM, a primitive introduced by Brendel et al. [SAC 2020], to provide Diffie-Hellman-like implicit authentication and secrecy guarantees. Along the way, we revisit the formalism of Brendel et al. and identify that additional security properties are required to prove a split-KEM-based protocol secure. We instantiate split-KEM by building a protocol based on the Frodo key exchange protocol relying on the plain LWE assumption: our proofs might be of independent interest as we show it satisfies our novel unforgeability and deniability security notions. Finally, we complement our theoretical results by thoroughly benchmarking both K-Waay and existing X3DH protocols. Our results show even when using plain LWE and a conservative choice of parameters that K-Waay is significantly faster than previous work.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. USENIX Security 2024
Contact author(s)
daniel collins @ epfl ch
lois huguenin-dumittan @ epfl ch
ngoc_khanh nguyen @ kcl ac uk
nicrolin @ hotmail fr
serge vaudenay @ epfl ch
2024-01-29: revised
2024-01-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Collins and Loïs Huguenin-Dumittan and Ngoc Khanh Nguyen and Nicolas Rolin and Serge Vaudenay},
      title = {K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2024/120},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.