An Efficient and Generic Construction for Signal's Handshake (X3DH): Post-Quantum, State Leakage Secure, and Deniable

Keitaro Hashimoto; Shuichi Katsumata; Kris Kwiatkowski; Thomas Prest

Paper 2021/616

An Efficient and Generic Construction for Signal's Handshake (X3DH): Post-Quantum, State Leakage Secure, and Deniable

Keitaro Hashimoto, Shuichi Katsumata, Kris Kwiatkowski, and Thomas Prest

Abstract

The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype, Facebook Messenger among many others. The Signal protocol consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis (Eurocrypt'19) provided a concrete security model along with a generic construction based on simple building blocks that are instantiable from versatile assumptions, including post-quantum ones. In contrast, as far as we are aware, works focusing on the X3DH protocol seem limited. In this work, we cast the X3DH protocol as a specific type of authenticated key exchange (AKE) protocol, which we call a Signal-conforming AKE protocol, and formally define its security model based on the vast prior works on AKE protocols. We then provide the first efficient generic construction of a Signal-conforming AKE protocol based on standard cryptographic primitives such as key encapsulation mechanisms (KEM) and signature schemes. Specifically, this results in the first post-quantum secure replacement of the X3DH protocol on well-established assumptions. Similar to the X3DH protocol, our Signal-conforming AKE protocol offers a strong (or stronger) flavor of security, where the exchanged key remains secure even when all the non-trivial combinations of the long-term secrets and session-specific secrets are compromised. Moreover, our protocol has a weak flavor of deniability and we further show how to progressively strengthen it using ring signatures and/or non-interactive zero-knowledge proof systems. Finally, we provide a full-fledged, generic C implementation of our (weakly deniable) protocol. We instantiate it with several Round 3 candidates (finalists and alternates) to the NIST post-quantum standardization process and compare the resulting bandwidth and computation performances. Our implementation is publicly available.

Note: This is the full version of a preliminary work that appeared in PKC 2021.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published by the IACR in JOC 2022
DOI: 10.1007/s00145-022-09427-1
Keywords: the Signal protocol authenticated key exchange post-quantum
Contact author(s): hashimoto k au @ m titech ac jp
shuichi katsumata000 @ gmail com
thomas prest @ pqshield com
History: 2022-05-10: last of 3 revisions; 2021-05-17: received; See all versions
Short URL: https://ia.cr/2021/616
License: CC BY

BibTeX

@misc{cryptoeprint:2021/616,
      author = {Keitaro Hashimoto and Shuichi Katsumata and Kris Kwiatkowski and Thomas Prest},
      title = {An Efficient and Generic Construction for Signal's Handshake ({X3DH}): Post-Quantum, State Leakage Secure, and Deniable},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/616},
      year = {2021},
      doi = {10.1007/s00145-022-09427-1},
      url = {https://eprint.iacr.org/2021/616}
}