Abstract
The Signal protocol relies on a handshake protocol, formerly X3DH and now PQXDH, to set up secure conversations. One of its privacy properties, of value to Signal, is , allowing users to deny participation in communications. Prior analyses of deniability for these protocols, including post-quantum variants, use models highly tailored to the individual protocols and generally make ad-hoc adaptations to “standard” AKE definitions, obscuring the concrete deniability guarantees and complicating comparisons across protocols. Building on Hashimoto, Katsumata, and Wigger’s abstraction for Signal handshake protocols (USENIX’25), we address this gap by presenting a unified framework for analyzing their deniability. We analyze Signal’s classically secure X3DH and harvest-now-decrypt-later-secure PQXDH, and show the settings for which PQXDH is (un)deniable against harvest-now–later attacks, where a quantum judge retrospectively assesses the participation of classical users. We further analyze post-quantum alternatives like RingXKEM, whose deniability relies on ring signatures (RS). By introducing a novel metric inspired by differential privacy, we provide relaxed, pragmatic guarantees for deniability. Lastly, we also use this metric to define for RS, a relaxation of anonymity, allowing us to build an efficient RS from NIST-standardized Falcon (and MAYO), which is not anonymous, but is provably deniable. We believe this relaxation to have independent interest outside of the Signal handshake protocol.
Note: Updates from previous version. (July 14, 2025): We added results on the undeniability of PQXDH against malicious receiver when the distinguisher is quantum. We thank Rune Fielder (and Roman Langrehr) for sharing their recent paper CRYPTO’25 paper. We also updated the presentation of our Falcon-based ring signature, correctly highlighting the difference between Gandalf by Phillip Gajland, Jonas Janneck, and Eike Kiltz (CRYPTO’24).
