Paper 2021/1187

Post-Quantum Signal Key Agreement with SIDH

Samuel Dobson and Steven D. Galbraith


In the effort to transition cryptographic primitives and protocols to quantum-resistant alternatives, an interesting and useful challenge is found in the Signal protocol. The initial key agreement component of this protocol, called X3DH, has so far proved more subtle to replace - in part due to the unclear security model and properties the original protocol is designed for. This paper defines a formal security model for the original signal protocol, in the context of the standard eCK and CK+ type models, which we call the Signal-adapted-CK model. We then propose a secure replacement for the Signal X3DH key exchange protocol based on SIDH, and provide a proof of security in the Signal-adapted-CK model, showing our protocol satisfies all security properties of the original Signal X3DH. We call this new protocol SI-X3DH. Our protocol refutes the claim of Brendel, Fischlin, Günther, Janson, and Stebila [Selected Areas in Cryptography (2020)] that SIDH cannot be used to construct a secure X3DH replacement due to adaptive attacks. Unlike the generic constructions proposed in the literature, our protocol achieves deniability without expensive machinery such as post-quantum ring signatures. It also benefits from the efficiency of SIDH as a key-exchange protocol, compared to other post-quantum key exchange protocols such as CSIDH.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Signal protocolauthenticated key exchangepost-quantum cryptographysupersingular elliptic curvesisogeniesSIDH
Contact author(s)
samuel dobson nz @ gmail com
s galbraith @ auckland ac nz
2022-03-03: last of 3 revisions
2021-09-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Samuel Dobson and Steven D.  Galbraith},
      title = {Post-Quantum Signal Key Agreement with SIDH},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1187},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.