Comprehensive Deniability Analysis of Signal Handshake Protocols: X3DH, PQXDH to Fully Post-Quantum with Deniable Ring Signatures

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 deniability, 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 Wiggers'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-judge-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. We also use this metric to define deniability 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. This is the full version of a paper appearing in the proceedings of the 34th USENIX Security Symposium (USENIX Security '25). This version additionally includes formal statements and proofs for the Deniable BAKE protocols considered in this work, as well as additional details and proofs for our ring signature constructions. is then updated after each key exchange. For an example, in X3DH and PQXDH, the secret associated to the one-time prekey bundle is removed after the receiver completes the key exchange. Leakage of a users' updated state may thus reveal how many handshake protocols it has executed as a receiver. We require that said leakage does not expose the sender identities for those handshakes, preserving deniability with respect to the communicating parties. As deniability under standard AKE formalism do not track persistent user states, this subtlety is absent in prior definitions. See Sec. 1.2 for more details. Harvest now judge later. Extending beyond classical deniability, we consider deniability against quantum accusers and distinguishers. We also consider scenarios -relevant today -where the accuser is classical, but the distinguisher is quantum. Indeed, transcripts stored now could later be exploited when quantum capabilities become available, a risk we term "harvest-now-judge-later" (HNJL). 2 Surprisingly, while harvest-now-decrypt-later attacks have garnered significant attention, particularly for the PQXDH protocol, no prior work provides this level of analysis for deniability. We close this gap and prove PQXDH to be deniable against HNJL attacks in a setting where the accusers are limited to be honest-but-curious. More interestingly though, against malicious receiver accusers, we show PQXDH to be undeniable, showing that protocols may become undeniable when the distinguisher is more powerful than the accuser. Intuitively, using the powerful distinguisher, a weak accuser can "prove" to the distinguisher that it could not have computed some secret known to the sender. This is akin to a recent result by Fiedler and Langrehr [FL25], where they show X3DH and PQXDH to be undeniable when the running time of the (classical, polynomial time) accuser is shorter compared to the (classical, polynomial time) distinguisher, and when all parties have access to some extra auxiliary input. A pragmatic metric for deniability. We introduce a novel measure for deniability inspired by concepts in differential privacy and differential indistinguishability [Bac+15; Dwo+06; Mir+09]. Prior works required the real evidence 𝜋 real and simulated evidence 𝜋 sim to be indistinguishable by the distinguisher D. That is, the statistical distance of the two distributions is close: While sufficient, we observe this level of deniability to be overly conservative. In practice, the accused user only needs to prove that a simulator could have generated the evidence, not that the simulator outputs evidence with the same probability as the accused user. We thus only require a relaxed condition: for some multiplicative slack 𝜇 (possibly non-negligibly) close to 1. Technically, this means the two distributions are close in terms of the hockey-stick divergence [SV16]. As discussed later, this new pragmatic metric for deniability is the key enabler for building efficient PQ (deniable) ring signatures from NIST-standardized signatures. Analysis of X3DH and PQXDH. In the classical setting, we prove that both X3DH and PQXDH attain the highest level of (standard and strong) deniability one may hope for, so long as one-time pre