Cryptology ePrint Archive: Report 2021/1187

Post-Quantum Signal Key Agreement with SIDH

Samuel Dobson and Steven D. Galbraith

Abstract: 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.

Category / Keywords: cryptographic protocols / Signal protocol, authenticated key exchange, post-quantum cryptography, supersingular elliptic curves, isogenies, SIDH

Date: received 14 Sep 2021, last revised 20 Sep 2021

Contact author: samuel dobson nz at gmail com, s galbraith at auckland ac nz

Available format(s): PDF | BibTeX Citation

Version: 20210921:011018 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]