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

Shuichi Katsumata, Guilhem Niot, Ida Tucker, Thom Wiggers

► To cite this version:

Shuichi Katsumata, Guilhem Niot, Ida Tucker, Thom Wiggers. Comprehensive Deniability Analysis of Signal Handshake Protocols: X3DH, PQXDH to Fully Post-Quantum with Deniable Ring Signatures. 34th USENIX Conference on Security Symposium (USENIX Security '25), Aug 2025, Seattle, United States. 10.5555/3766078.3766427. hal-05444090

HAL Id: hal-05444090

https://hal.science/hal-05444090v1

Submitted on 6 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Comprehensive Deniability Analysis of Signal Handshake Protocols: X3DH, PQXDH to Fully Post-Quantum with Deniable Ring Signatures

Shuichi Katsumata ID 1,2

Guilhem Niot ID 1,3

Ida Tucker ID 1

Thom Wiggers ID 1

1 PQShield

2 AIST

3 Univ Rennes, CNRS, IRISA

August 27, 2025

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.

## Contents

<table><tr><td>1. Introduction</td><td>3</td></tr><tr><td>1.1. Contributions</td><td>3</td></tr><tr><td>1.2. Related Work</td><td>5</td></tr><tr><td>2. Modeling Signal Handshake Protocols and Problem Setting</td><td>6</td></tr><tr><td>2.1. Modeling Signal Handshake Protocols with Bundled AKEs</td><td>6</td></tr><tr><td>2.2. Deniability: Entities and Roles</td><td>7</td></tr><tr><td>2.3. Distinguisher Capabilities</td><td>7</td></tr><tr><td>2.4. Scopes of Deniability</td><td>8</td></tr><tr><td>2.5. Modeling Choices and Simplifications</td><td>8</td></tr><tr><td>3. Defining Deniable Bundled AKE Protocols</td><td>8</td></tr><tr><td>3.1. Overview of Our Deniability Definition</td><td>8</td></tr><tr><td>3.2. Deniability Against Honest-but-Curious Accusers</td><td>9</td></tr><tr><td>3.3. Deniability Against Malicious Accusers</td><td>11</td></tr><tr><td>4. Deniability of X3DH and PQXDH</td><td>12</td></tr><tr><td>4.1. The X3DH and PQXDH Protocols</td><td>12</td></tr><tr><td>4.2. Summary: Deniability of X3DH &amp; PQXDH</td><td>13</td></tr></table>
<table>
  <tbody>
    <tr>
      <td><b>5. Deniability of RingXKEM</b></td>
      <td><b>15</b></td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;5.1. Deniable Ring Signatures</td>
      <td>16</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;5.2. The RingXKEM protocol</td>
      <td>16</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;5.3. Summary: Deniability of RingXKEM</td>
      <td>18</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;5.4. Alternative BAKE from Plain Signatures</td>
      <td>18</td>
    </tr>
    <tr>
      <td><b>6. Ring Signatures from Falcon and MAYO</b></td>
      <td><b>19</b></td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;6.1. Falcon-Based Ring Signature</td>
      <td>19</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;6.2. MAYO-based Ring Signature</td>
      <td>20</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;6.3. Comparison with Previous Works on Ring Signatures</td>
      <td>21</td>
    </tr>
    <tr>
      <td><b>7. Efficiency Comparison</b></td>
      <td><b>21</b></td>
    </tr>
    <tr>
      <td><b>A. Basic Building Blocks</b></td>
      <td><b>27</b></td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;A.1. Symmetric Key Encryption</td>
      <td>27</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;A.2. Key Encapsulation Mechanisms</td>
      <td>28</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;A.3. Signature Schemes</td>
      <td>28</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;A.4. Ring Signature Schemes</td>
      <td>29</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;A.5. Merkle Trees</td>
      <td>29</td>
    </tr>
    <tr>
      <td><b>B. Cryptographic Models</b></td>
      <td><b>30</b></td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;B.1. Generic Group Model with Oblivious Sampling</td>
      <td>30</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;B.2. Quantum Random Oracle Model</td>
      <td>30</td>
    </tr>
    <tr>
      <td><b>C. Combinations of Leakage and Disclosure</b></td>
      <td><b>30</b></td>
    </tr>
    <tr>
      <td><b>D. Strong Implies Standard Deniability</b></td>
      <td><b>31</b></td>
    </tr>
    <tr>
      <td><b>E. Proof of Deniability of X3DH and PQXDH</b></td>
      <td><b>31</b></td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;E.1. Local Deniability of X3DH and PQXDH</td>
      <td>31</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;E.2. Global Deniability of X3DH</td>
      <td>32</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;E.3. Global Deniability of PQXDH</td>
      <td>33</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;E.4. Strong Local and Global Deniability of X3DH and PQXDH</td>
      <td>34</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;E.5. Strong HNJL Deniability of PQXDH for Accused Receivers</td>
      <td>37</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;E.6. PQXDH Modelling Gap</td>
      <td>38</td>
    </tr>
    <tr>
      <td><b>F. Single to Multi-Challenge Deniability for Ring Signatures</b></td>
      <td><b>38</b></td>
    </tr>
    <tr>
      <td><b>G. Proofs of Deniability for RingXKEM</b></td>
      <td><b>39</b></td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;G.1. Standard Local Deniability of RingXKEM</td>
      <td>39</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;G.2. Standard Global Deniability of RingXKEM</td>
      <td>40</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;G.3. Strong Local and Global Deniability of RingXKEM for Accused Receivers</td>
      <td>41</td>
    </tr>
    <tr>
      <td><b>H. Deniability of SignXKEM</b></td>
      <td><b>42</b></td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;H.1. The SignXKEM protocol</td>
      <td>42</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;H.2. Summary: Deniability of SignXKEM</td>
      <td>42</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;H.3. Local and Global Deniability of SignXKEM</td>
      <td>43</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;H.4. Strong Local and Global Deniability of SignXKEM for Accused Receivers</td>
      <td>45</td>
    </tr>
    <tr>
      <td><b>I. Omitted Details for Ring Signature Constructions</b></td>
      <td><b>45</b></td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;I.1. Falcon-based Ring Signature</td>
      <td>45</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;I.2. MAYO-based Ring Signature</td>
      <td>50</td>
    </tr>
  </tbody>
</table>
# 1. Introduction

The Signal protocol [MP16; PM16] does not just power the Signal app, it also underpins messaging apps such as WhatsApp [Wha23], Google RCS [Goo22], and Facebook Messenger [Met23], collectively serving billions of users. To initiate a conversation, Signal users perform a handshake protocol to establish a shared key, which is then used for encrypted communication via the Double Ratchet protocol [PM16]. This handshake was originally implemented as X3DH [MP16], based on Triple Diffie-Hellman [KP05]. In late 2023, as a step towards fully post-quantum (PQ) security, X3DH was replaced with PQXDH [KS23], offering protection against “harvest-now-decrypt-later” (HNDL) attacks. There also exist several proposals for fully PQ Signal handshake protocols [Bre+22; Col+24; Has+22; HKW25].

Until recently, analysis of Signal handshake protocols were performed in ad-hoc security models, sometimes deviating from the way they will be implemented in practice, e.g., assuming one-time prekey bundles never deplete. This made the concrete security properties attained unclear and hindered comparisons of the strengths and weaknesses of different protocols. Recently, Hashimoto, Katsumata, and Wiggers [HKW25] proposed *Bundled Authenticated Key Exchange (BAKE) protocols*, allowing to analyze existing Signal handshake protocols in a unified manner. This was a modification to the standard AKE definition, with a focus on a more general and formal handling of *prekey bundles*; a distinct component of Signal handshake protocols, allowing users to upload batches of key materials onto the server so that any sender can establish communication even when recipients are offline. This led to a more efficient PQ handshake protocol, RingXKEM, relying on ring signatures (RS) and Merkle trees, which could not have been captured in previous models.

The main goal of [HKW25] was to define a security model for BAKE, treating key indistinguishability and authentication properties. However, the issue of *deniability* — one of the key features of the original Signal protocol [KS23; MP16] — was left open. Deniability is a privacy property ensuring that the transcript of a communication session cannot serve as evidence that a user participated in said communication, even if another party attempts to frame them. This is particularly relevant in scenarios involving, e.g., oppressive regimes or whistleblowers, where participation alone can be incriminating. For Signal, deniability is integral to their protocol’s design [KS23; MP16]. Selecting the most suitable protocols thus requires not only considering key indistinguishability and authentication guarantees, but also placing equal emphasis on their deniability guarantees. However, as was the case with key indistinguishability and authentication, existing protocols have been analyzed using tailored deniability models [Bre+22; Col+24; FJ24; Has+22; Vat+20] — often treating protocols informally as AKE protocols and disregarding the implication of using prekey bundles — thereby giving incomplete analyses and complicating meaningful comparisons.

## 1.1. Contributions

In this work, we propose a unified framework for analyzing the deniability of BAKE protocols, thereby completing the formal treatment of Signal handshake protocols initiated by [HKW25]. We analyze X3DH and PQXDH, proving for the first time that PQXDH is deniable even against *quantum* distinguishers. Additionally, we examine the deniability of fully PQ BAKE protocols, such as RingXKEM, and provide instantiations of ring signatures based on NIST-standardized signatures, to encourage adoption. We will now detail these contributions.

**Unified deniability model.** We formally capture the deniability of general Signal handshake (i.e., BAKE) protocols, building upon prior work on the deniability of AKE [CF11; Dag+13; DGK06; UG15; UG18], and adaptations made for specific handshake protocols [Bre+22; Col+24; FJ24; Has+22; Vat+20]. Following the general approach common to existing simulation-based definitions, we define an *accuser*, who collects evidence which is provided to a *distinguisher*<fnref n="1" />, who, in turn, decides if the evidence could have been simulated by the accuser. Our model differentiates information that may leak from the accused user’s device, and evidence disclosed by accusers, to the distinguisher. We account for varying adversarial capabilities, distinguishing between honest-but-curious accusers (*standard* deniability) and malicious accusers (*strong* deniability), as did [Has+22]. We also introduce notions of *local* deniability, where an accused participant can deny having engaged in a BAKE protocol with the accuser, and a strictly stronger *global* deniability, which further ensures both participants can deny their involvement, even if the accuser is an outsider to the conversation. Our notions of deniability benefit from a hierarchical structure, allowing for ease of comparisons.

**Unique features of our model.** By adopting the BAKE formalism of [HKW25], we can capture the lifecycle of prekey bundles. Each batch of prekey bundles contains a number of *one-time* prekey bundles, and a single *last-resort* prekey bundle. One-time prekey bundles are deleted after use. The last-resort prekey bundle ensures recipient availability even if they are offline for extended amounts of time; it is only used if all one-time prekey bundles are used up, and is only deleted when a new batch of prekeys is uploaded [KS23; MP16]. Our model distinguishes deniability guarantees based on whether one-time prekeys are depleted, revealing interesting separations. For example, in X3DH and PQXDH, using last-resort prekeys does not affect local deniability, but does harm global deniability, just as it impacted key indistinguishability in [HKW25].

Moreover, we highlight that when a batch of prekey bundles is generated, a *user state* is generated — this was a unique feature of the BAKE formalism, allowing the secret information associated to each prekey bundle to be correlated. This state

<footnote n="1">¹Prior work has also used the term “Judge”; we prefer “distinguisher”, which better reflects its algorithmic (as opposed to human) nature.</footnote>
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).<fnref n="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 $\pi_{real}$ and simulated evidence $\pi_{sim}$ to be indistinguishable by the distinguisher $D$. That is, the statistical distance of the two distributions is close: $|\text{Pr}[D(\pi_{real}) = 0] - \text{Pr}[D(\pi_{sim}) = 0]|$. 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: $\text{Pr}[D(\pi_{real}) = 0] \approx \mu \cdot \text{Pr}[D(\pi_{sim}) = 0]$ for some multiplicative slack $\mu$ (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 prekey bundles are not depleted. Otherwise, deniability only holds if the distinguisher does not see the accused users' state (relevant to the conversation). This is because states associated with last-resort prekey-bundles are not immediately deleted after use; if the accused user's phone is seized before the next generation of a prekey bundle batch, this state leaks to the distinguisher and can be used to prove participation. This distinction highlights the advantage of using the BAKE framework [HKW25], accurately modeling prekey bundles.

We further prove that PQXDH is *standard* HNJL deniable by considering quantum distinguishers in the quantum random oracle model (QROM), consistent with its HNDL key-indistinguishability security. Finally, we show that, in the classical ROM<fnref n="3" />, PQXDH is strong HNJL deniable in case the accuser is limited to a malicious sender. However, as stated above, PQXDH is *not* strong HNJL deniable when the accuser is a malicious receiver.

**Analysis of fully PQ protocols.** We extend our study to Hashimoto et al.'s fully PQ RingXKEM [HKW25], which uses RSs. While they demonstrated its key indistinguishability properties, we finalize the security evaluation by proving deniability. Finally, we examine SignXKEM, a RingXKEM variant suggested in [Has+21], which replaces RSs by (plain) signatures, and show that it offers some level of deniability under limited leakage and disclosure, highlighting the precise nature of our model in capturing weaker notions of deniability. Table 1 summarizes the deniability of these protocols.

**Ring signature instantiations.** Proving the deniability of RingXKEM is straightforward if the underlying RS scheme is anony-
mous, but compact lattice-based RSs satisfying anonymity turn out difficult to construct; the most compact schemes [GJK24b;
LAZ19b] only provide roughly 30 bits of security for anonymity when instantiated with concrete parameters (see Sec. 6
for details). We observe that, thanks to our new metric for measuring the deniability of BAKE protocols, a weaker notion
than anonymity, coined *deniability* for RS, is sufficient for constructing deniable BAKE protocols. This relaxation enables
us to design PQ RS schemes for small ring sizes, based on the standardized signature Falcon [Pre+22], and the additional
signature candidate MAYO [Beu+24]. Our RS using Falcon is based on the generic lattice-based RS design by [GJK24b].
Our RS schemes are as compact as the state-of-the-art. We further provide implementations outperforming previous works by
a factor 32–66× for signing, and 146–1025× for verification. We note that, in line with the security proofs of the underlying
signatures, our proofs are in the classical random oracle model (ROM), but not in the QROM.

<footnote n="2">²To avoid confusion with the acronym of harvest-now-*decrypt*-later, we chose the term *judge*¹ as opposed to *distinguish*.</footnote>

<footnote n="3">³We leave it as future work to extend this result to the QROM.</footnote>
<table><caption>Table 1: Signal key exchange protocols and their deniability and security properties</caption><thead><tr><th rowspan="3">Protocol:</th><th colspan="8">Signal handshake protocol deniability properties</th><th colspan="2">Legend</th></tr><tr><th colspan="2">X3DH</th><th colspan="2">PQXDH</th><th colspan="2">PQXDH</th><th colspan="2">RingXKEM</th><th colspan="2">SignXKEM</th></tr><tr><th colspan="2">Classic A/D</th><th colspan="2">Classic A/D</th><th colspan="2">Classic A<br>Quantum D</th><th colspan="2">Classic or Quantum<br>A/D</th><th colspan="2">Classic or Quantum<br>A/D</th></tr><tr><th>Deniability Level</th><th colspan="2">Leakage leak disc</th><th colspan="2">Leakage leak disc</th><th colspan="2">Leakage leak disc QROM</th><th colspan="2">Leakage leak disc QROM</th><th colspan="2">Leakage leak disc QROM</th></tr></thead><tbody><tr><td>local</td><td>●</td><td>●</td><td>●</td><td>●</td><td>●</td><td>✓</td><td>●</td><td>●</td><td>●</td><td>✓</td></tr><tr><td>global</td><td>●</td><td>●</td><td>●</td><td>●</td><td>●</td><td>✓</td><td>●</td><td>●</td><td>●</td><td>✓</td></tr><tr><td>strong-local</td><td>●†</td><td>●</td><td>●†</td><td>●</td><td>●SO</td><td>?</td><td>●SO</td><td>?</td><td>●SO</td><td>?</td></tr><tr><td>strong-global</td><td>●†</td><td>●</td><td>●†</td><td>●</td><td>●SO</td><td>?</td><td>●SO</td><td>?</td><td>●SO</td><td>?</td></tr><tr><td>Security [HKW25]</td><td colspan="2">Classical</td><td colspan="4">Harvest-Now Decrypt-Later</td><td colspan="4">Fully post-quantum</td></tr></tbody></table><table><thead><tr><th>Icon</th><th>Last-resort prekey: No</th><th>Yes</th></tr></thead><tbody><tr><td>●</td><td>high</td><td>high</td></tr><tr><td>●</td><td>high</td><td>med</td></tr><tr><td>●</td><td>med</td><td>med</td></tr><tr><td>●</td><td>med</td><td>low</td></tr><tr><td>○</td><td>low</td><td>low</td></tr><tr><td>?</td><td colspan="2">Open problem</td></tr><tr><td>SO</td><td colspan="2">Accusers A restricted to being senders, no deniability otherwise.</td></tr><tr><td>†</td><td colspan="2">Proof using GGM.</td></tr></tbody></table>

**Example:** RingXKEM is local deniable with leakage leak = high and disclosure disc = high even if a last-resort prekey bundle was used. SignXKEM is local deniable with leak = high and disc = med, but restricted to leak = med and disc = low using a last resort prekey bundle.

**Remark:** For strong deniability, we always set disc = high, since we have no control over the information a malicious accuser may reveal.

## 1.2. Related Work

**Deniability of X3DH.** The introduction of Off-the-Record Messaging established deniability as a key feature for secure messaging [BGB04]. The Signal protocol adopted this goal in its X3DH handshake [MP16], analyzed by Vatandas et al. [Vat+20] under the simulation-based model of [DGK06] for AKEs. Their work proves offline deniability for X3DH under knowledge-of-exponent assumptions, and links the deniability of a communication session to the deniability of the key agreement protocol starting the session. This allows to extend results on the deniability of handshake protocols to the entire conversation.

**Deniability of PQXDH.** Signal's PQXDH protocol [KS23], deployed in 2023, combines the classical X3DH handshake with a PQ KEM. While not fully PQ, it provides key indistinguishability against “harvest-now-decrypt-later” adversaries, as analyzed in [Bha+24; FG25; HKW25]. The deniability guarantees of PQXDH were recently analyzed in [FJ24], viewing it as a specific handshake protocol proposed by [FG25]. The analysis assumes a classical distinguisher, leaving deniability guarantees against “harvest-now-judge-later” adversaries open; and only considers distinguishers either having no access to any secret key, or full access to all secret keys (of both accusing and accused; and for identity keys and prekeys). They hence do not capture scenarios where accusers disclose more information to the distinguisher than accused users. We also note that their model does not distinguish the attained deniability guarantees when one-time prekey bundles are, or are not, depleted. In a very recent work, Fiedler and Langrehr [FL25] showed the *undeniability* of X3DH and PQXDH when receivers are malicious, are provided as auxiliary input some hint on a Diffie-Hellman instance, and can maliciously generate their identity keys. More concretely, their result relies on the non-standard *hinted* computational Diffie-Hellman (CDH) problem which is difficult for a (classical) accuser running in time $T$ but easy for a (classical) distinguisher running in time $T' \gg T$. When the distinguisher is quantum, as in the case of HNJL deniability, we show that we can simply rely on the standard CDH problem.

**Deniability of fully PQ protocols.** Hashimoto et al. [Has+22] construct a PQ Signal handshake protocol from RSs, and show deniability against honest-but-curious quantum adversaries, using a simplification of the deniability model of [DGK06]. To prove deniability against malicious (classical) accusers, they require knowledge assumptions. In concurrent work, Brendel et al. [Bre+22] proposed a similar protocol based on designated verifier signatures, along with a new game-based deniability notion, which focuses solely on sender deniability but captures scenarios where judges may coerce users to reveal secret keys. Recently, Collins et al. [Col+24] introduced K-Waay, a protocol based on split-KEMs [Bre+20; Nio25]. They extend the framework of Brendel et al. to model receivers who hand over their entire state to the distinguisher. Collins et al. do not model one-time vs. last-resort prekey bundles, but rather suggest that, if prekey bundles run out, then the sender should reuse an old one. However, their deniability model does not capture prekey bundle reuse. Both [Bre+22; Col+24] only consider honest-but-curious accusers, and attain deniability against quantum distinguishers.

**A more detailed comparison.** We here outline differences between our deniability model for BAKE, and tailored deniability models from prior works. The primary differences are explained in Sec. 1.1. Compared to [Has+22; Vat+20], we allow the distinguisher to obtain leakage from honest users; accounting for scenarios where judges may coerce secret keys from accused users. The models introduced in [Bre+22; FJ24] allow judges to compromise secrets associated to identity keys and last resort prekeys of all users, and [Col+24] also capture the leakage of state associated to one-time prekeys. While our model captures these scenarios, it also differentiates which specific keys leak from accused as opposed to accusing users. Additionally, [Bre+22; Col+24] do not incorporate the simulation of prekey generation, and limit their study to
honest-but-curious adversaries. Global deniability is not captured by the models of [Bre+22; Col+24; Has+22; Vat+20]. Fiedler and Janson [FJ24] require deniability of prekey bundle uploads (i.e. of the general use of the Signal protocol), whereas we consider deniability within specific conversations, this results in different conclusions regarding the deniability guarantees of PQXDH.

**Scope of our work.** We focus on the deniability of *messages*. This means that like prior work (e.g., [Bre+22; Col+24]), we do not consider the deniability of registering or uploading prekey bundles. Our focus is the deniability of the handshake message and the computation of the resulting handshake key by both sender and receiver, even if there is evidence of registration. Other security notions than deniability can also enhance privacy in secure messaging. For instance, one can add sender/receiver privacy [Lun18; Mad+22], metadata protection [HKP22; TWG24], anonymity and unlinkability [PH10; Ung+15]. We leave the interplay of deniability and other privacy notions as an interesting future work. We also do not consider network-level adversaries. We believe countermeasures such as padding [Nik+19] or anonymous communication [DMS04; JSH24] to be complimentary to deniability, but leave their analysis open.

Lastly, deniability is not the only way to enhance privacy in secure messaging. For instance, one can add sender/receiver privacy [Lun18; Mad+22], metadata protection [HKP22; TWG24], anonymity and unlinkability [PH10; Ung+15].

## 2. Modeling Signal Handshake Protocols and Problem Setting

We model Signal handshake protocols as *bundled authenticated key exchange* (BAKE) protocols, introduced in [HKW25]. BAKE is a variant of the traditional AKE model allowing to formally model prekey bundles and user states. It is general enough to capture Signal's X3DH and PQXDH [KS23; MP16], among other constructions such as RingXKEM [HKW25] and variants [Bre+22; Has+21; Has+22]. In [HKW25], they defined *key indistinguishability* of BAKE, a fundamental security property for any key exchange protocol.

In this work, we define what it means for a BAKE to be *deniable*, a key security feature of Signal's X3DH and PQXDH protocols. Before introducing the formal definition of deniability, we recall the definition of a BAKE protocol and explain the high-level problem setting for deniability.

**Standard notations and definitions.** Let $\mathbb{Z}$ denote the natural numbers, and $\mathbb{Z}_N$ the natural numbers modulo $N$. If $P$ is a point on an elliptic curve, we denote multiplication by scalar $k$ as $[k]P$. We denote by $\lambda$ the security parameter, and by $[N]$ the set of integers $\{1, \dots, N\}$. Definitions of basic cryptographic primitives such as symmetric key encryption, signature schemes, and KEMs are deferred to App. A.

### 2.1. Modeling Signal Handshake Protocols with Bundled AKEs

We recall the definition of a BAKE protocol [HKW25].

**Definition 1.** A two-round *bundled authenticated key exchange* protocol BAKE consists of the following four probabilistic polynomial time (PPT) algorithms, where $L \in \text{poly}(\lambda)$.

BAKE.IdKeyGen($1^{\lambda}$) $\xrightarrow{S}$ (ik, isk): The identity key generation algorithm, on input security parameter $1^{\lambda}$, outputs identity public key ik and associated secret key isk.

BAKE.PreKeyBundleGen(isk$_{u}$) $\xrightarrow{S}$ ($\vec{prek}_{u}$, $st_{u}$): On input a user $u$'s identity secret key, outputs a number of prekey bundles $\vec{prek}_{u} = (\text{prek}_{u,t})_{t \in [L] \cup \{\perp\}}$, and a user state $st_{u}$. Prekey bundles with $t \neq \perp$ are called *one-time* prekey bundles, whereas $\text{prek}_{u,\perp}$ is called the *last-resort* prekey bundle. The state may for example include the (ephemeral) secret keys associated to public keys included in $\vec{prek}_{u}$.

BAKE Send(isk$_{s}$, ik$_{r}$, prek$_{r,t}$) $\xrightarrow{S}$ (K, $\rho$): On input a sender $s$'s identity secret key isk$_{s}$, the intended receiver $r$'s identity key ik$_{r}$, and a prekey bundle prek$_{r,t}$, outputs a session key K and a handshake message $\rho$.

BAKE Receive(isk$_{r}$, st$_{r}$, ik$_{s}$, t, $\rho$) $\rightarrow$ (K', st$_{r}$): The (deterministic) receiver algorithm, on input a receiver $r$'s identity secret key isk$_{r}$ and state st$_{r}$, a sender $s$'s identity key ik$_{s}$, with the identifier of the used prekey bundle $t \in [L] \cup \{\perp\}$, and a handshake message $\rho$, outputs a key $K'$ and an updated state st$_{r}$. Key agreement may fail, in which case $K' = \perp$, and the state is rolled back.

A BAKE protocol is a two-party protocol, with a server relaying communications. Unlike standard AKE protocols, BAKE supports prekey bundles, a feature central to Signal handshake protocols [KS23; MP16]. Prekey bundles, uploaded to a server, are pre-generated key material consumed during new communication setups, enabling senders to establish secure sessions with offline recipients, facilitating asynchronous communication. Prekey bundles are generally one-time use, which naively limits the number of handshakes. To ensure availability, even during extended recipient offline periods, a *last-resort prekey bundle* is used when the list of one-time bundles is depleted. This bundle, designated by the label $\perp$, is not deleted after use until the next PreKeyBundleGen is performed once back online. In protocol execution, the server first distributes all one-time prekey bundles; and only once these are exhausted is the last-resort prekey used [MP16].
## 2.2. Deniability: Entities and Roles

The entities involved in deniability are categorized as follows, following established terminologies, e.g., [CCH23; DGK06; Ung+15].

**Accused users:** The set of honest users, denoted as $\mathcal{H}$, whose goal is to deny their involvement in the BAKE protocol. An accused user can either be a sender or a receiver.

**(Insider) accusers:** The set of corrupted users, denoted as $C$, that communicate$^4$ with an accused user. Their goal is to prove that the accused user ran a BAKE protocol with them. We consider two levels of insider accusers: *honest-but-curious* accusers and *malicious* accusers. The former honestly follows the protocol description but may collect as much information as possible to accuse their peer; for instance, this captures a device injected by a malware, secretly storing all the states on the device while still using the official secure messaging application. In contrast, the latter considers much stronger accusers that can execute arbitrary code; capturing, e.g., devices running a modified secure messaging application.

**(Outsider) accuser:** An adversary aiming to prove that a pair of honest users communicated. This could be, e.g., the server or another user of the secure messaging application.

**Distinguisher:** An entity (often called “judge”) outputting a *verdict* on whether a user participated in a BAKE protocol.

## 2.3. Distinguisher Capabilities

The distinguisher determines whether an accused user participated in a BAKE protocol based on a transcript (i.e., prekey bundles and handshake message) and the session key $K$. It is important that $K$ also be deniable since it is used to exchange the actual payload of the secure messaging protocol [DGK06; Vat+20]. To make its verdict, the distinguisher may further be provided information through so-called *leakage* and *disclosure* functions. The former dictates how much information of the accused user leaks to the distinguisher, whereas the latter dictates how much information the accusing user discloses to the distinguisher. A BAKE protocol is more deniable if it allows leaking and disclosing more information to the distinguisher.

**Leakage function for accused users.** The amount of information leakage of an accused user is formalized using a function $\mathcal{L}_{leak}$. We consider three levels of leakage: *leak = low* is the weakest setting where no leakage occurs; *leak = med* leaks the identity secret key; and, *leak = high* leaks all secret information of the accused user.

**Definition 2.** The leakage function $\mathcal{L}_{leak}$ for the set $\mathcal{H}$ of accused users of a BAKE protocol is defined as follows:

$$ \mathcal{L}_{leak}((\text{isk}_u, \text{st}_u)_{u \in \mathcal{H}}) := \begin{cases} (\perp, \perp) & \text{if } \text{leak} = \text{low} \\ ((\text{isk}_u)_{u \in \mathcal{H}}, \perp) & \text{if } \text{leak} = \text{med} \\ ((\text{isk}_u, \text{st}_u)_{u \in \mathcal{H}}) & \text{if } \text{leak} = \text{high} \end{cases} $$

**Disclosure function for honest-but-curious accusers.** The amount of information disclosed by the honest-but-curious (insider) accusers is formalized using a function $\mathcal{D}_{disc}$. Similarly to the above, we consider three levels of disclosures: $disc = low$ is the weakest setting where the accuser only discloses its identity secret key; $disc = med$ additionally discloses its *current* state; lastly, $disc = high$ further discloses the *initial* state output by algorithm BAKE.PreKeyBundleGen. The third setting models an honest-but-curious accuser that follows the protocol description, but may store information without deleting it.$^5$

**Definition 3.** The disclosure function $\mathcal{D}_{disc}$ for the set $C$ of honest-but-curious (insider) accusers of a BAKE protocol is defined as follows:

$$ \mathcal{D}_{disc}((\text{isk}_u, \text{st}_u, \text{st}^{\text{init}}_u)_{u \in C}) := \begin{cases} ((\text{isk}_u)_{u \in C}, \perp, \perp) & \text{if } \text{disc} = \text{low} \\ ((\text{isk}_u, \text{st}_u)_{u \in C}, \perp) & \text{if } \text{disc} = \text{med} \\ ((\text{isk}_u, \text{st}_u, \text{st}^{\text{init}}_u)_{u \in C}) & \text{if } \text{disc} = \text{high} \end{cases} $$

**Disclosure function for malicious accusers.** Malicious accusers can deviate arbitrarily from the protocol, such as by maliciously generating prekeys, possibly without knowing the associated secrets. We thus assume the malicious accuser to always disclose their entire state $\text{st}_\mathcal{A}$. Note that despite the general unpredictability of malicious accusers, we require that $\text{st}_\mathcal{A}$ includes their identity secret keys, based on the assumption that they register a valid identity public key (cf. Sec. 2.5).

<footnote>$^4$Throughout the paper, for readability, we may say users $u$ and $v$ communicated with each other to mean that $u$ and $v$ participated in a BAKE protocol.</footnote>

<footnote>$^5$Considering initial state leakage for the accused user would imply that their device was tampered with. We do not consider such settings as deniability can be trivially lost through other means.</footnote>
## 2.4. Scopes of Deniability

Lastly, we consider two scopes of deniability: one focused on protecting individual users and the other on shielding the conversation between two users as a whole.

**Local deniability:** Allows an accused user, either a sender or a receiver, to deny participating in a BAKE protocol.

**Global deniability:** Further allows a pair of communicating accused users to simultaneously deny participating in a BAKE protocol. This implicitly accounts for outsider accusers, while local deniability considers only insider accusers.

Formalizing what it means to "deny participating" is one of our main technical contributions, which we explain in Sec. 3. At a high level, in a locally deniable protocol, a distinguisher may be convinced that either one of the users participated in the BAKE protocol, but cannot determine which one. Local deniability thus suffices when the accused user seeks only individual protection. In contrast, when both communicating users simultaneously seek deniability — such as in highly sensitive communications, like a journalist communicating with a source — global deniability is required. In such cases, the distinguisher cannot exclude the possibility that the communication was generated by an unrelated third party.

## 2.5. Modeling Choices and Simplifications

This subsection outlines the modeling choices and assumptions underpinning our work.

**Focus on deniability of protocol participation.** We do not aim to address the deniability of being a user of the secure messaging application. Specifically, user registration of identity keys and prekey bundle uploads may not be deniable. Our goal is to show that users using the app can plausibly deny participating in any communication. Such practical levels of deniability were also considered in, e.g., [Bre+22; Col+24].

**Honest registration of identity keys.** Similarly to other works on the deniability of Signal handshake protocols [Bre+22; Jia+22; Vat+20], we assume that users *honestly* generate their identity keys. This simplifies the definition and proofs of deniability while maintaining practical relevance. Works allowing maliciously generated identity keys [FJ24; Has+22] rely on strong knowledge type assumptions, forcing the proof to go through by pushing the burden onto the assumption. We can also rely on zero-knowledge proofs, guaranteeing that a registered identity public key has an associated identity secret key.

**Disclosure vs. leakage.** We assume that honest-but-curious accusers disclose *at least* as much as the information leaked from accused users, e.g., if the accused leak updated states, then so do the accusers. This highlights that accusers are expected to actively provide information to the distinguisher to incriminate the accused user, and limits the leakage and disclosure combinations we analyze. We summarize the combinations of leakage and disclosure we consider in App. C.

# 3. Defining Deniable Bundled AKE Protocols

We define the *deniability* of a BAKE protocol. The main novelty in our definitions is a new pragmatic metric for deniability, inspired by differential privacy and differential indistinguishability [Bac+15; Dwo+06; Mir+09], which may be of an independent interest. Looking ahead, our definition allows constructing a post-quantum BAKE protocol using a new efficient "deniable" ring signature based on the NIST-standardized Falcon.

## 3.1. Overview of Our Deniability Definition

Say an accused user wants to deny participating in a certain protocol, or, more formally, the user wants to prove that any *evidence* the distinguisher holds could have come from somebody else. In the context of a BAKE protocol, evidence is the protocol transcript (prekey bundles and handshake message) and the session key, cf. Sec. 2.3. A standard way to formalize this is to construct a *simulator* that can output simulated evidence indistinguishable from real evidence to a distinguisher [DNS98]. This has been used to define deniable AKEs, e.g., [DGK06]. We highlight that this simulator must not only exist but also be constructible in the real world [Pas03]. An accused user must convince the judge (i.e., distinguisher) by showing that such a simulator could have been actually used by the accuser.

We also use simulators to define deniability of a BAKE protocol, but with a twist, inspired by concepts in differential privacy and differential indistinguishability [Bac+15; Dwo+06; Mir+09]. Prior works required the real evidence $\pi_{\text{real}}$ and simulated evidence $\pi_{\text{sim}}$ to be *indistinguishable* by a distinguisher $D$. That is, they (informally) required the statistical distance to be close: $|\text{Pr}[D(\pi_{\text{real}}) = 0] - \text{Pr}[D(\pi_{\text{sim}}) = 0]| = \delta(\lambda)$ for some negligible function $\delta$. 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. As a concrete example, assume the evidence includes a ring signature $\sigma$ where the ring consists of two users: the accused $u$ and the accuser $v$. Roughly, prior definitions require that the probability of $u$ and $v$ outputting $\sigma$ is identical. We relax this so that there could be
a higher chance that u outputs $\sigma$, as long as v could have output $\sigma$. Put differently, while $\sigma$ is more likely to have come from u, we cannot deny the possibility that it came from v. This is sufficient for u to plausibly deny the conversation.

In order to formalize this idea, we introduce a multiplicative slack $\mu(\lambda)$, and only require a relaxed condition: $\Pr[D(\pi_{\text{real}}) = 0] \le \mu(\lambda) \cdot \Pr[D(\pi_{\text{sim}}) = 0] + \delta(\lambda)$. Technically, this means the two distributions are close in terms of the hockey-stick divergence [SV16]. While the original definition is recovered by setting $\mu(\lambda) = 1 + \text{negl}(\lambda)$, we obtain a relaxed definition by setting, say $\mu(\lambda) = 1 + 0.1$. This indicates that while the evidence is (roughly) 10% more likely to have come from the accused user, we cannot ignore the high possibility that the accuser outputs it by running the simulator.<fnref n="6" />

The benefit of relaxing the definition becomes clear when we later construct a post-quantum BAKE protocol based on ring signatures. We notice that while a ring signature based on the same parameter sets as Falcon [Pre+22] is insufficient for the standard notion of deniability, it is sufficient for the relaxed definition with a multiplicative slack $\mu(\lambda) = 1 + 2^{-27}$. See Sec. 5 and Sec. 6.1 for details.

## 3.2. Deniability Against Honest-but-Curious Accusers

We first define local and global deniability against honest-but-curious accusers,<fnref n="7" /> formally defined through a game in Alg. 1. The distinguisher D is given the set of identity keys and prekey bundles, and can adaptively query transcripts exchanged between users (cf. Ln. 16). At the end of the game, D is given the leakage and disclosed information of the accused and accusing users (cf. Lns. 19 to 21). It then outputs some bit b (e.g., a verdict of the judge). As discussed above, we require that the probability D outputs b in the real world (i.e., mode = real) is overwhelmingly likely to be within some multiplicative slack $\mu$ of the probability D outputs b in the simulated world (i.e., mode = sim). Importantly, our definition captures the deniability of last-resort prekey bundles as well (cf. Ln. 29).

The simulated world is defined using a simulator $\text{Sim} = (\text{SimPreK}, \text{SimTrans}, \text{SimSt}_H, \text{SimSt}_C)$. Below, for readability, we call the accused and accusing users as honest and corrupted users, denoted with $\mathcal{H}$ and $\mathcal{C}$, respectively. As shown in Ln. 13, $\text{SimPreK}$ simulates the prekey bundles of all the users. Importantly, we allow simulation of the honest users' prekey bundles as these are not necessarily tied to the identity key, which we assume to be honestly registered (see Sec. 2.5). As an example, assume a prekey bundle consisting of two public keys where one key is signed using the identity key, while the other is not. Generating the latter key can then be plausibly denied, as it could have been injected by an accuser.

Next, $\text{SimTrans}$ simulates the honest user's transcripts and session keys using only the accuser's secret information. Insider sender and receiver accusers are captured by Lns. 34 to 38, respectively. Outsider accusers, used for global deniability, are captured by Lns. 39 to 41, where no user secrets are provided to the simulator.

Lastly, $\text{SimSt}_H$ and $\text{SimSt}_C$ simulate the honest and corrupt user's state, which may be leaked and disclosed to the distinguisher, respectively.<fnref n="8" /> As the state is only used by the BAKE Receive algorithm, $\text{SimSt}_H$ is run when simulating an honest receiver r's updated state (cf. Ln. 42). Importantly, we do not allow $\text{SimSt}_H$ to take the sender information s (and hence simulation state $\text{st}_{\text{sim}}$) as input. This is because if receiver r's updated state depended on the sender s, the state may prove to the distinguisher that r was communicating with s. As an extreme example, consider a BAKE protocol where the updated state includes a signature on s under r's identity key; such a protocol where the updated state depends on the sender should not be considered deniable. On the other hand, we allow $\text{SimSt}_H$ to take the identity secret key $\text{isk}_r$ as input since, by definition of the BAKE PreKeyBundleGen algorithm, the state can depend on $\text{isk}_r$. Finally, we consider a one-shot simulation for the corrupted users, where $\text{SimSt}_C$ outputs the initial and updated states (cf. Ln. 18). As $\text{SimSt}_C$ can take the simulation state $\text{st}_{\text{sim}}$ as input, which can record all the oracle queries to $\mathcal{O}_{\text{ATK}}$, this is without loss of generality.

Formally, we define local and global deniability as follows.

**Definition 4 (Local deniability).** Let $\mathcal{N} := [N]$ for $N \in \mathbb{N}$ be the set of all users, $\mathcal{H} \subseteq \mathcal{N}$ such that $\mathcal{H} \ne \emptyset$ be the set of accused users, and $\mathcal{C} := \mathcal{N} \setminus \mathcal{H}$ be the set of accusers. Let $Q = \text{poly}(\lambda)$ be an upper bound on the number of oracle queries made by the distinguisher D.

A BAKE protocol is $(\mu, \delta)$-locally deniable against honest-but-curious accusers with respect to leakage function $\mathcal{L}_{\text{leak}}$ and disclosure function $\mathcal{D}_{\text{disc}}$ with leak, disc $\in \{\text{low}, \text{med}, \text{high}\}$, if there exists an efficient simulator $\text{Sim} = (\text{SimPreK}, \text{SimTrans}, \text{SimSt}_H, \text{SimSt}_C)$ such that for any efficient distinguisher D we have

$$ \Pr[\text{Game}_{\mathcal{D}, \mathcal{H}, \mathcal{L}_{\text{leak}}, \mathcal{D}_{\text{disc}}}^{\text{local}}(1^{\lambda}, \text{real}) = 0] \le \mu(\lambda, Q) \cdot \Pr[\text{Game}_{\mathcal{D}, \mathcal{H}, \mathcal{L}_{\text{leak}}, \mathcal{D}_{\text{disc}}}^{\text{local}}(1^{\lambda}, \text{sim}) = 0] + \delta(\lambda), $$

where $\text{Game}_{\mathcal{D}, \mathcal{H}, \mathcal{L}_{\text{leak}}, \mathcal{D}_{\text{disc}}}^{\text{local}}$ is given in Alg. 1.

**Definition 5 (Global deniability).** We define global deniability identically to local deniability in Def. 4 except that the distinguisher D plays the game $\text{Game}_{\mathcal{D}, \mathcal{H}, \mathcal{L}_{\text{leak}}, \mathcal{D}_{\text{disc}}}^{\text{global}}$ in Alg. 1.

<footnote n="6">⁶Note that we do not require the other direction: $\Pr[D(\pi_{\text{sim}}) = 0] \le \mu'(\lambda) \cdot \Pr[D(\pi_{\text{real}}) = 0] + \delta'(\lambda)$. We only care that if some verdict was made using a real evidence, then the same verdict could have been made on a simulated evidence.</footnote>

<footnote n="7">⁷As our definition implicitly captures outsider accusers, accusers will mean insider accusers in this section unless otherwise stated (cf. Sec. 2.2).</footnote>

<footnote n="8">⁸Put differently, we can ignore these simulators if $\text{leak} \in \{\text{low}, \text{med}\}$ or $\text{disc} = \text{low}$ (cf. Sec. 2.3).</footnote>
<caption>**Algorithm 1** Games for local and global deniability with respect to leakage function $\mathcal{L}_{leak}$, and disclosure function $\mathcal{D}_{disc}$.

**Boxed text** is only relevant to global deniability.</caption>

1: **function** Game$^{\text{ATK}}_{D, \mathcal{H}, \mathcal{L}_{\text{leak}}, \mathcal{D}_{\text{disc}}}$ (1$^{\lambda}$, mode)
2: &nbsp;&nbsp;&nbsp;&nbsp;C := $\mathcal{N} \setminus \mathcal{H}$
3: &nbsp;&nbsp;&nbsp;&nbsp;**for** user $u \in \mathcal{N}$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($ik_u$, $isk_u$) $\leftarrow$ BAKE.IdKeyGen(1$^{\lambda}$)
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;counter$_u$ := 0 ▶ Track how many prekey bundles are used
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $[u \in \mathcal{H}]$ **then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\vec{prek}_u$, $st_u$) $\leftarrow$ BAKE.PreKeyBundleGen($isk_u$)
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $[\text{mode} = \text{real}]$ **then**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** user $u \in \mathcal{C}$ **do**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\vec{prek}_u$, $st_u$) $\leftarrow$ BAKE.PreKeyBundleGen($isk_u$)
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{st}_{u}^{\text{init}}$ := $st_u$
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else** ▶ $\text{mode} = \text{sim}$
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▶ Simulate prekey bundles of accused users $\mathcal{H}$
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\vec{\text{prek}}_u$)$_{u \in \mathcal{H}}$, ($\vec{\text{prek}}_u$)$_{u \in \mathcal{C}}$, $\text{st}_{\text{Sim}}$) $\stackrel{\$}{\leftarrow}$ SimPreK($\vec{\text{prek}}_u$)$_{u \in \mathcal{N}}$, ($\text{isk}_u$)$_{u \in \mathcal{C}}$, ($\vec{\text{prek}}_u$)$_{u \in \mathcal{H}}$)
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\vec{\text{prek}}_u$)$_{u \in \mathcal{H}}$ $\leftarrow$ ($\vec{\text{prek}}_u$)$_{u \in \mathcal{H}}$
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{st}_D$ $\stackrel{\$}{\leftarrow}$ $\mathcal{D}^{\text{ATK}}$($\vec{\text{prek}}_u$)$_{u \in \mathcal{N}}$) ▶ $\mathcal{D}$ obtains transcripts
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $[\text{mode} = \text{sim}]$ **then**
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\text{st}_u$, $\text{st}_{u}^{\text{init}}$)$_{u \in \mathcal{C}}$ $\leftarrow$ SimSt$_C$($\text{st}_{\text{Sim}}$) ▶ Corrupted states
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;leak$_D$ := $\mathcal{L}_{\text{leak}}$($\text{isk}_u$, $\text{st}_u$)$_{u \in \mathcal{H}}$
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{disc}_D$ := $\mathcal{D}_{\text{disc}}$($\text{isk}_u$, $\text{st}_u$, $\text{st}_{u}^{\text{init}}$)$_{u \in \mathcal{C}}$
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{aux}_D$ := ($\text{leak}_D$, $\text{disc}_D$)
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$b$ $\stackrel{\$}{\leftarrow}$ $\mathcal{D}$($\text{st}_D$, $\text{aux}_D$) ▶ $\mathcal{D}$ outputs a bit $b \in \{0, 1\}$
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $b$
24: **function** $\mathcal{O}_{\text{ATK}}(s, r)$
25: &nbsp;&nbsp;&nbsp;&nbsp;**require** $[(s, r) \in \mathcal{N} \times \mathcal{N}] \wedge [(s \neq r)] \wedge [(s, r) \notin \mathcal{C} \times \mathcal{C}]$
26: &nbsp;&nbsp;&nbsp;&nbsp;**if** $[\text{ATK} = \text{Local}]$ **then** **require** $[(s, r) \notin \mathcal{H} \times \mathcal{H}]$
27: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;counter$_r$ $\leftarrow$ counter$_r$ + 1
28: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$t$ := counter$_r$
29: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $[t > L]$ **then** $t \leftarrow \perp$ ▶ Use last-resort prekey bundle
30: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $[\text{mode} = \text{real}]$ **then** ▶ Run real sender and receiver
31: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($K$, $\rho$) $\leftarrow$ BAKE Send($isk_s$, $ik_r$, $\text{prek}_{r,t}$)
32: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($K'$, $\text{st}_r$) $\leftarrow$ BAKE Receive($isk_r$, $\text{st}_r$, $ik_s$, $t$, $\rho$)
33: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else** ▶ $\text{mode} = \text{sim}$
34: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $[(s, r) \in \mathcal{H} \times \mathcal{C}]$ **then** ▶ Simulate with receiver secrets
35: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($K$, $\rho$, $\text{st}_{\text{Sim}}$) $\stackrel{\$}{\leftarrow}$ SimTrans($\text{isk}_r$, $\text{st}_{\text{Sim}}$, ($s, r, t$))
36: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else** ▶ Honest receiver
37: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $[(s, r) \in \mathcal{C} \times \mathcal{H}]$ **then** ▶ Simulate with sender secrets
38: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($K'$, $\rho$, $\text{st}_{\text{Sim}}$) $\stackrel{\$}{\leftarrow}$ SimTrans($\text{isk}_s$, $\text{st}_{\text{Sim}}$, ($s, r, t$))
39: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else** ▶ ($s, r) \in \mathcal{H} \times \mathcal{H}$ $\Rightarrow$ \text{ATK} = Global
40: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▶ Simulate without any secrets
41: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($K$, $K'$, $\rho$, $\text{st}_{\text{Sim}}$) $\stackrel{\$}{\leftarrow}$ SimTrans($\perp$, $\text{st}_{\text{Sim}}$, ($s, r, t$))
42: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{st}_r$ $\stackrel{\$}{\leftarrow}$ SimSt$_\mathcal{H}$($\text{isk}_r$, $\text{st}_r$) ▶ Update honest receiver state
43: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $[(s, r) \in \mathcal{H} \times \mathcal{C}]$ **then** return ($K$, $\rho$)
44: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else if** $[(s, r) \in \mathcal{C} \times \mathcal{H}]$ **then** return ($K'$, $\rho$)
45: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else** return ($K$, $K'$, $\rho$) ▶ ($s, r) \in \mathcal{H} \times \mathcal{H} \Rightarrow \text{ATK} = \text{Global}$
Above, we allow the multiplicative slack $\mu$ to depend on the number of queries $D$ makes. This allows for tighter analysis using a Falcon-based ring signature as Falcon also assumes an upper-bound on the number of signatures (i.e., $Q = 2^{64}$).

**Remark 1.** For simplicity, our model does not explicitly capture asymmetric deniability, but can be extended to do so. For instance, deniability for accused users who are always receivers can be modeled by restricting the distinguisher to query $O_{\text{ATK}}$ only on inputs $(s, r)$, where $r \in \mathcal{H}$. This scenario applies when $r$ never initiates conversations with unknown users. For some protocols discussed in this work, we demonstrate stronger deniability guarantees for accused receivers.

### 3.3. Deniability Against Malicious Accusers

We define strong local and global deniability, that is deniability against malicious accusers, similarly as above except that we explicitly consider an accuser algorithm $\mathcal{A}$ in the real world (cf. Alg. 2, Ln. 9, and Alg. 3, Ln. 11). Note that in Alg. 2, Ln. 9 we no longer assume prekey bundles are honestly generated. Moreover, the simulator $\text{Sim}_{\mathcal{A}}$ can depend on the accuser $\mathcal{A}$ — this is sufficient as an accused user can plea that an accuser was internally running $\text{Sim}_{\mathcal{A}}$.

We also make a subtle yet crucial design choice. Specifically, we only consider deniability of *successful* BAKE executions. If a malicious sender sends a handshake message $\rho$ which is not accepted (i.e., the honest receiver outputs $\perp$), then we do not require deniability (cf. Alg. 3, Lns. 19 to 24). This is because an accused user only needs to deny having sent a message to the sender using the established session key; if no keys were established, there is no need to deny. This allows us to get around an artificial theoretical obstacle in the proof: the simulator $\text{Sim}_{\text{Trans}}_{\mathcal{A}}$ no longer needs to know if $\rho$ output by the malicious sender is accepted, which it cannot know without the receiver's secret keys. Concretely, we allow $\text{Sim}_{\text{Trans}}_{\mathcal{A}}$ to output a simulated session key $K'^*$, *conditioned on* the receiver accepting — if the receiver rejects, then $K'^*$ is simply discarded by the game. Lastly, since $\text{Sim}_{\text{St}_{\mathcal{H}}}$ needs to simulate the honest receiver's updated state, the game rolls back the updated state after executing BAKE. Receive (cf. Alg. 3, Lns. 20 and 21).

We define strong local and global deniability as follows.

**Definition 6** (Strong local deniability). Let $N, \mathcal{H}, C, Q$ be defined as in Def. 4. A BAKE protocol is $(\mu, \delta)$-strongly local deniable against malicious accusers with respect to leakage function $\mathcal{L}_{\text{leak}}$ with $\text{leak} \in \{\text{low, med, high}\}$, if for any efficient accuser $\mathcal{A}$, there exists an efficient simulator $\text{Sim}_{\mathcal{A}} = (\text{Sim}_{\text{PreK}_{\mathcal{A}}}, \text{Sim}_{\text{Trans}_{\mathcal{A}}}, \text{Sim}_{\text{St}_{\mathcal{H}}}, \text{Sim}_{\text{St}_{\mathcal{A}}})$ such that for any efficient distinguisher $D$ we have

$$ \Pr \left[ \text{Game}_{\mathcal{A}, \mathcal{D}, \mathcal{H}, \mathcal{L}_{\text{leak}}}^{\text{strong-local}} (1^{\lambda}, \text{real}) = 0 \right] \leq \mu(\lambda, Q) \cdot \Pr \left[ \text{Game}_{\mathcal{A}, \mathcal{D}, \mathcal{H}, \mathcal{L}_{\text{leak}}}^{\text{strong-local}} (1^{\lambda}, \text{sim}) = 0 \right] + \delta(\lambda), $$

where $\text{Game}_{\mathcal{A}, \mathcal{D}, \mathcal{H}, \mathcal{L}_{\text{leak}}}^{\text{strong-local}}$ is given in Alg. 2.

**Algorithm 2** Games for strong local and global deniability with respect to a leakage function $\mathcal{L}_{\text{leak}}$. Shaded boxes highlight differences compared to standard deniability.

1: **function** Game<sup>strong-ATK</sup><sub>\mathcal{A},\mathcal{D},\mathcal{H},\mathcal{L}_{\text{leak}}</sub> (1<sup>λ</sup>, mode)
2: &nbsp;&nbsp;&nbsp;&nbsp;C := [N] \ H
3: &nbsp;&nbsp;&nbsp;&nbsp;**for** user u ∈ [N] **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(ik<sub>u</sub>, isk<sub>u</sub>) ← BAKE.IdKeyGen(1<sup>λ</sup>)
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;counter<sub>u</sub> := 0 ▷ Keep track of num prekey bundles used
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ||u ∈ H|| **then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(prẽk<sub>u</sub>, st<sub>u</sub>) ← BAKE.PreKeyBundleGen(isk<sub>u</sub>)
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ||mode = real|| **then** ▷ Adversarial prekey bundles
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((prẽk<sub>u</sub>)<sub>u∈C</sub>, st<sub>\mathcal{A}\right) ← <sup>s</sup><sub>\mathcal{A}\right</sub>( (ik<sub>u</sub>)<sub>u∈[N]</sub> , (isk<sub>u</sub>)<sub>u∈C</sub> , (prẽk<sub>u</sub>)<sub>u∈H</sub> )
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ||mode = sim|| **then**
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((prẽk<sup>*</sup><sub>u</sub>)<sub>u∈H</sub> , (prẽk<sub>u</sub>)<sub>u∈C</sub> , st<sub>Sim</sub>) ← SimPreK<sub>\mathcal{A}\right</sub>((ik<sub>u</sub>)<sub>u∈[N]</sub> , (isk<sub>u</sub>)<sub>u∈C</sub> , (prẽk<sub>u</sub>)<sub>u∈H</sub> )
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(prẽk<sub>u</sub>)<sub>u∈H</sub> ← (prẽk<sup>*</sup><sub>u</sub>)<sub>u∈H</sub> ▷ Simulate for accused H
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ D obtains transcripts exchanged between users
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;st<sub>D</sub> ← <sup>s</sup><sub>D<sup>ATK</sup></sub>((ik<sub>u</sub>, prẽk<sub>u</sub>)<sub>u∈[N]</sub>) ▷ cf. Alg. 3
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ||mode = sim|| **then**
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;st<sub>\mathcal{A}\right</sub> ← SimSt<sub>\mathcal{A}\right</sub>(st<sub>Sim</sub>) ▷ Simulate adversary state
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;leak<sub>D</sub> := L<sub>\mathcal{leak}\right</sub>((isk<sub>u</sub>, st<sub>u</sub>)<sub>u∈H</sub>)
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;aux<sub>D</sub> := (leak<sub>D</sub>, st<sub>\mathcal{A}\right</sub>)
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ D outputs b ∈ {0, 1} after obtaining leakage aux<sub>D</sub>
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b ← <sup>s</sup><sub>D</sub>(st<sub>D</sub>, aux<sub>D</sub>)
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return b
**Definition 7** (Strong global deniability). We define strong global deniability identically to strong local deniability in Def. 6, except that the distinguisher D plays the game Game<sub>strong-global</sub><sup>A,D,H,L<sub>leak</sub></sup> in Alg. 2.

**Algorithm 3** The oracle for strong local and global deniability games used in Alg. 2. Shaded boxes highlight differences compared to standard deniability. Boxed text is only relevant to global deniability. In Ln. 21, “_” indicates that st<sub>tmp</sub> is deleted and no longer used by the game.

1: **function** O<sub>ATK</sub>(s, r)
2: &nbsp;&nbsp;&nbsp;&nbsp;**require** ||(s, r) ∈ [N] × [N]|| ∧ ||(s ≠ r)|| ∧ ||(s, r) ∉ C × C||
3: &nbsp;&nbsp;&nbsp;&nbsp;**if** ||ATK = Local|| **then** require ||(s, r) ∉ H × H||
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;counter<sub>r</sub> ← counter<sub>r</sub> + 1
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**t** := counter<sub>r</sub>
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ||**t** > L|| **then** **t** ← ⊥ ▷ Use last-resort prekey bundle
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ||**mode** = real|| **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ||s ∈ H|| **then** ▷ Run sender
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(K, ρ) ← BAKE Send(isk<sub>s</sub>, ik<sub>r</sub>, prek<sub>r,t</sub>)
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else** ▷ s ∈ C<sub>s</sub>, malicious sender
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;⟨ρ, st<sub>A</sub>⟩ ← A(isk<sub>s</sub>, st<sub>A</sub>, (s, r, t))
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ||**r** ∈ H|| **then** ▷ Run receiver
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(K', st<sub>r</sub>) ← BAKE Receive(isk<sub>r</sub>, st<sub>r</sub>, (ik<sub>s</sub>, t, ρ))
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else** ▷ mode = sim
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ||(s, r) ∈ H × C|| **then** ▷ Simulate with receiver secrets
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(K, ρ, st<sub>Sim</sub>) ← SimTrans<sub>A</sub>(isk<sub>r</sub>, st<sub>Sim</sub>, (s, r, t))
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else** ▷ Honest receiver
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ||(s, r) ∈ C × H|| **then** ▷ Simulate with sender secrets
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(K'<sup>*</sup>, ρ, st<sub>Sim</sub>) ← SimTrans<sub>A</sub>(isk<sub>s</sub>, st<sub>Sim</sub>, (s, r, t))
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;st<sub>tmp</sub> := st<sub>r</sub> ▷ Copy state
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(K', _ ) ← BAKE Receive(isk<sub>r</sub>, st<sub>tmp</sub>, (ik<sub>s</sub>, t, ρ))
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ Replace with simulated key if receiver accepts
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ||**K'** ≠ ⊥|| **then**
24: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**K'** ← K'<sup>*</sup>
25: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else** ▷ (s, r) ∈ H × H ⇒ ATK = Global
26: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ Simulate without any secrets
27: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(K, K', ρ, st<sub>Sim</sub>) ← SimTrans<sub>A</sub>(st<sub>Sim</sub>, (s, r, t))
28: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;st<sub>r</sub> ← SimSt<sub>H</sub>(isk<sub>r</sub>, st<sub>r</sub>) ▷ Update honest receiver state
29: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** ||(s, r) ∈ H × C|| **then** return (K, ρ)
30: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else if** ||(s, r) ∈ C × H|| **then** return (K', ρ)
31: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else** return (K, K', ρ) ▷ (s, r) ∈ H × H ⇒ ATK = Global

# 4. Deniability of X3DH and PQXDH

X3DH is the original handshake protocol used by Signal [MP16], based on Triple Diffie-Hellman [KP05]. In 2023, Signal rolled out a variant PQXDH [MP16], which adds a post-quantum KEM key exchange to X3DH, securing against harvest-now, decrypt-later (HNDL) adversaries. In this section, we examine the deniability of X3DH and PQXDH.

## 4.1. The X3DH and PQXDH Protocols

In Alg. 4, we give the identity key generation algorithm and the algorithm that is used for prekey bundle generation in X3DH and PQXDH as described by Hashimoto, Katsumata, and Wiggers [HKW25]. PQXDH is a strict extension to X3DH; functionality that is exclusive to PQXDH is marked with a **gray dotted box**. The classic key agreement for both consists of Diffie-Hellman (DH) with combinations of the sender and receiver's long-term identity keys, the receiver's prekey bundle's signed DH prekey, and, if not using a last-resort prekey bundle, one-time DH prekey, and an ephemeral DH key generated by the sender (cf. Lns. 7 to 14). PQXDH simply adds a KEM key exchange to X3DH, as shown in Ln. 15.

The description of the Send and Receive algorithms for X3DH and PQXDH are given in Algs. 5 and 6, respectively, where PQXDH-specific functionality is marked with a **gray dotted box**. Note that we follow the description given by [HKW25, Section 4], which adds a confirmation tag in lieu of modeling the sending of an encrypted message as in Signal's documentation. In practice, Signal uses the Double Ratchet algorithm to send this message; internally, it contains a MAC that achieves the same functionality. Hashimoto et al. write that Signal is considering similar changes to add better separation between the
**Algorithm 4 X3DH and $\overline{\text{PQXDH}}$ identity key and prekey bundle generation algorithms [HKW25].**

**PQXDH**-exclusive code is marked like this.

1: **function** $\overline{\text{PQX}}$<sub>3DH</sub>.IdKeyGen($1^{\lambda}$)
2: &nbsp;&nbsp;&nbsp;&nbsp;$\overline{\text{isk}} \leftarrow Z_p^S; \overline{\text{isk}} := [\overline{\text{isk}}]G$
3: &nbsp;&nbsp;&nbsp;&nbsp;($vk, sk) \leftarrow \text{Sig.KeyGen}(1^{\lambda})$
4: &nbsp;&nbsp;&nbsp;&nbsp;**return** ($\overline{\text{isk}}$; $(\overline{\text{isk}}, vk)$, $\text{isk} := (\overline{\text{isk}}, sk)$)

1: **function** $\overline{\text{PQX}}$<sub>3DH</sub>.PreKeyBundleGen($\text{isk}_u$)
2: &nbsp;&nbsp;&nbsp;&nbsp;($\overline{\text{isk}}_u, sk_u) \leftarrow \text{isk}_u$
3: &nbsp;&nbsp;&nbsp;&nbsp;$D_{\text{prek}}, D_{\rho_{\perp}} := \emptyset$ ▷ Initialize empty lists
4: &nbsp;&nbsp;&nbsp;&nbsp;▷ Generate what Signal calls the signed prekey
5: &nbsp;&nbsp;&nbsp;&nbsp;spksec<sub>u</sub> $\leftarrow Z_p; \text{spk}_u := [\text{spksec}]G$
6: &nbsp;&nbsp;&nbsp;&nbsp;$\sigma_{\text{spk}_u} \leftarrow \text{Sig.See}(sk_u, \text{spk}_u)$
7: &nbsp;&nbsp;&nbsp;&nbsp;▷ Create the L one-time prekey bundles
8: &nbsp;&nbsp;&nbsp;&nbsp;**for** $t \in [L]$ **do**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{osk}_{u,t} \leftarrow Z_p; \text{opk}_{u,t} := [\text{osk}_{u,t}]G$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(\text{ek}_{u,t}, \text{dk}_{u,t}) \leftarrow \text{KEM.KeyGen}(1^{\lambda})$
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\sigma_{\text{ek}_{u,t}} \leftarrow \text{Sig.See}(\text{sk}_u, \text{ek}_{u,t})$
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prek<sub>u,t</sub> := $(\text{spk}_u, \sigma_{\text{spk}_u}, \text{opk}_{u,t}, [\text{ek}_{u,t}, \sigma_{\text{ek}_{u,t}}])$
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$D_{\text{prek}}[t] \leftarrow (\text{prek}_{u,t}, (\text{spksec}_u, \text{osk}_{u,t}, [\text{dk}_{u,t}]))$
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ Set up the last-resort prekey bundle
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(\text{ek}_{u,\perp}, \text{dk}_{u,\perp}) \leftarrow \text{KEM.KeyGen}(1^{\lambda})$
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\sigma_{\text{ek}_{u,\perp}} \leftarrow \text{Sig.See}(\text{sk}_u, \text{ek}_{u,\perp})$
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prek<sub>u,\perp</sub> := $(\text{spk}_u, \sigma_{\text{spk}_u}, \perp, [\text{ek}_{u,\perp}, \sigma_{\text{ek}_{u,\perp}}])$
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$D_{\text{prek}}[L+1] \leftarrow (\text{prek}_{u,\perp}, (\text{spksec}_u, \perp, [\text{dk}_{u,\perp}]))$
19: &nbsp;&nbsp;&nbsp;&nbsp;**return** $(\overline{\text{prek}}_u, \text{st}_u := (D_{\text{prek}}, D_{\rho_{\perp}}))$

PQXDH and Double Ratchet protocols. For a detailed comparison between Alg. 5, the Signal documentation, and Signal's implementation, refer to [HKW25, Appendix C].

**Algorithm 6** shows the algorithm used by receivers in X3DH and PQXDH. The key computation is analogous to that in the Send algorithm given by Alg. 5; however, to prevent replay attacks, the Receive algorithm additionally records a list of messages received. For details about this protection measure, refer to Hashimoto, Katsumata, and Wiggers [HKW25, Sec. 4].

## 4.2. Summary: Deniability of X3DH & PQXDH

We summarize the levels of deniability satisfied by X3DH and PQXDH. See Tab. 1 for a complete overview, and recall that the level of deniability can be sorted based on the leakage function $L_{\text{leak}}$ and disclosure function $D_{\text{disc}}$, where (leak, disc) dictates the amount of secret information given to the distinguisher (cf. Sec. 2.3). For the formal statements, see App. E.

**Local deniability.** Both protocols achieve the highest level of local deniability (i.e., $(\text{leak}, \text{disc}) = (\text{high}, \text{high}))$. For X3DH, this matches our intuition since the sender and receiver hold a symmetric role in the generation of the session key $K$. This is also the case for PQXDH: the honest sender remains deniable since KEM.Encaps can be run publicly; the honest receiver remains deniable since, assuming an honest-but-curious accusing sender, (informally) the accuser knows the outcome of KEM.Decaps. Importantly, we show that local deniability of PQXDH holds even if the accuser is classical but the distinguisher is quantum (i.e., HNJL security).

**Global deniability.** Global deniability is more nuanced. If the accused users never deplete their one-time prekey bundles, both protocols achieve the highest level of global deniability (i.e., $(\text{leak}, \text{disc}) = (\text{high}, \text{high}))$. However, if the accused user used their last-resort prekey bundle, it can only support global deniability with $(\text{leak}, \text{disc}) = (\text{med}, \text{high})$, i.e., the accused user cannot deny if its user state $\text{st}_u$ leaks to the distinguisher.

At a high level, to argue X3DH is globally deniable, the session key and handshake message $(K, \rho)$ must be simulatable without relying on any secret of the sender and receiver. In case the sender's one-time prekey bundle is used, this follows from $K$ being KDF-derived from a DH agreement between a one-time prekey $\text{opk}_r$ and an ephemeral key $\text{epk}$ (cf. Alg. 5, Ln. 14). Namely, since the secrets of $\text{opk}_r$ and $\text{epk}$ are deleted from the receiver and sender states respectively, a distinguisher cannot distinguish between a correctly generated $K$ and a randomly sampled $K$ by an outside accuser, assuming the hardness of DDH. In contrast, when a last-resort prekey bundle is used, key $K$ can be derived by a distinguisher holding both the receiver's $\text{isk}_r$
<caption>**Algorithm 5** The $\overline{\text{PQX}}$DH and X3DH Send algorithm [HKW25].</caption>

1: **function** $\overline{\text{PQX}}$3DH Send(isk$_s$, ik$_r$, prek$_r$)
2: &nbsp;&nbsp;&nbsp;&nbsp;($\overline{\text{isk}}$$_s$, sk$_s$) ← isk$_s$; ($\overline{\text{ik}}$$_r$, vk$_r$) ← ik$_r$
3: &nbsp;&nbsp;&nbsp;&nbsp;▷ opk$_r$ = ⊥ if prek$_r$ is a last-resort key bundle
4: &nbsp;&nbsp;&nbsp;&nbsp;($\text{spk}$$_r$, σ$_{\text{spk}}$$_r$, opk$_r$, $\overline{\text{ek}}$$_r$, σ$_{\text{ek}}$$_r$) ← prek$_r$
5: &nbsp;&nbsp;&nbsp;&nbsp;require $[\text{Sig}.\text{Verify}(vk_r, \text{spk}_r, \sigma_{\text{spk}_r}) = 1]$
6: &nbsp;&nbsp;&nbsp;&nbsp;require $[\text{Sig}.\text{Verify}(vk_r, ek_r, \sigma_{\text{ek}}_r) = 1]$
7: &nbsp;&nbsp;&nbsp;&nbsp;esk ← $\overline{\mathbb{Z}}$$_p$, epk := [esk]G
8: &nbsp;&nbsp;&nbsp;&nbsp;ss$_1$ := $[\overline{\text{isk}}$$_s]$spk$_r$
9: &nbsp;&nbsp;&nbsp;&nbsp;ss$_2$ := [esk]ik$_r$
10: &nbsp;&nbsp;&nbsp;&nbsp;ss$_3$ := [esk]spk$_r$
11: &nbsp;&nbsp;&nbsp;&nbsp;ss := ss$_1$ || ss$_2$ || ss$_3$
12: &nbsp;&nbsp;&nbsp;&nbsp;if $[\text{opk}}_r \neq \perp]$ then ▷ One-time prekey bundle
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ss$_4$ := [esk]opk$_r$
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ss := ss$_1$ || ss$_2$ || ss$_3$ || ss$_4$
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\overline{\text{ss}}$$_{KEM}$, ct) ← KEM Encaps(ek$_r$)
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;content := ik$_s$ || ik$_r$ || prek$_r$ || epk || ct
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$K$ || $\tau_{\text{conf}}$ := KDF(ss$_1$ $[\overline{\text{ss}}$$_{KEM}$], content)
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\rho$ := (epk, $\overline{\text{ct}}$, $\overline{\tau}$$_{conf}$) ▷ Handshake message
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return ($K$, $\rho$)

<caption>**Algorithm 6** The $\overline{\text{PQX}}$DH and X3DH Receive algorithm [HKW25].</caption>

1: **function** $\overline{\text{PQX}}$3DH Receive(isk$_r$, st$_r$, ik$_s$, t, $\rho$)
2: &nbsp;&nbsp;&nbsp;&nbsp;($\overline{\text{isk}}$$_r$, sk$_r$) ← isk$_r$; ($\overline{\text{ik}}$$_s$, vk$_s$) ← ik$_s$
3: &nbsp;&nbsp;&nbsp;&nbsp;($D_{\text{prek}}$, $D_{\rho}$$_{⊥}$) ← st$_r$
4: &nbsp;&nbsp;&nbsp;&nbsp;if $[t \neq \perp]$ then ▷ One-time prekey bundle
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;require $[D_{\text{prek}}[t] \neq \perp]$ ▷ Check if unused.
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\text{prek}$$_{r,t}$, ($\text{spksec}$$_r$, osk$_r,t$, $\overline{\text{dk}}$$_{r,t}$)) ← $D_{\text{prek}}[t]$
7: &nbsp;&nbsp;&nbsp;&nbsp;else ▷ Last-resort prekey bundle (i.e., $t = \perp$)
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;require $[\rho \notin D_{\rho}$$_{⊥}]$ ▷ Check $\rho$ is not replayed.
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$D_{\rho}$$_{⊥}$ ← $D_{\rho}$$_{⊥}$ ∪ {$\rho$}
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\text{prek}$$_{r,t}$, ($\text{spksec}$$_r$, $\perp$, $\overline{\text{dk}}$$_{r,t}$))) ← $D_{\text{prek}}[t]$
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\text{epk}$, $\overline{\text{ct}}$, $\overline{\tau}$$_{conf}$) ← $\rho$
12: &nbsp;&nbsp;&nbsp;&nbsp;ss$_1$ := [$\text{spksec}$$_r$]ik$_s$; ss$_2$ := [$\overline{\text{isk}}$$_r$]epk
13: &nbsp;&nbsp;&nbsp;&nbsp;ss$_3$ := [$\text{spksec}$$_r$]epk; ss := ss$_1$ || ss$_2$ || ss$_3$
14: &nbsp;&nbsp;&nbsp;&nbsp;if $[t \neq \perp]$ then ▷ One-time prekey bundle
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ss$_4$ := [osk$_r,t$]epk; ss := ss$_1$ || ss$_2$ || ss$_3$ || ss$_4$
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\overline{\text{ss}}$$_{KEM}$) ← KEM Decaps(dk$_r,t$, ct)
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;content := ik$_s$ || ik$_r$ || prek$_r,t$ || epk || ct
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$K$ || $\tau'$$_{conf}$ := KDF(ss$_1$ $[\overline{\text{ss}}$$_{KEM}$], content)
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;require $[\tau_{\text{conf}} = \tau'$$_{conf}]$
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ Delete prekey bundle if not last-resort
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $[t \neq \perp]$ then $D_{\text{prek}}[t]$ ← $\perp$
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;st$_r$ ← ($D_{\text{prek}}$, $D_{\rho}$$_{⊥}$)
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return ($K$, st$_r$)
and $st_r$, which includes $spksec_r$ (see Alg. 6, Lns. 12 and 13). Hence, accused users can only leak their identity secret key (i.e., leak = med).

Global deniability of PQXDH is shown quite differently and relies on the IND-CPA security of the KEM. This is because against a *quantum* distinguisher, the argument used above fails; DDH is no longer hard.<fnref n="9" /> We show deniability by the session key $K$ being KDF-derived from KEM key $ss_{KEM}$ (cf. Alg. 5, Ln. 16). As long as the distinguisher cannot decrypt the ciphertext ct included in $\rho$, $K$ remains indistinguishable.

**Strong local and global classical deniability.** Unlike previous works relying on knowledge type assumptions, we rely on the generic group model (GGM) [Sho97] to show strong (local and global) deniability. Knowledge assumptions assume the existence of knowledge extractors, for which there exist no concrete constructions. The resulting simulators are hence not efficiently implementable, which violates the requirements of [Pas03], requiring accusers the ability to show the existence of such simulator to the judge in practice. While GGM is an idealized model, it allows to concretely write down a simulator assuming a *generic* accuser, aligning better with the notion of deniability. Indeed, GGM has been used by Signal's private group system [CPZ20], giving us more confidence in generic accusers.

We can straightforwardly prove strong local and global deniability of X3DH in the GGM with the same level of information leakage and disclosure considered by non-strong deniability. One limitation, however, is that GGM assumes a prime-order group, whereas X3DH uses the non-prime-order X25519. We can get around this by either relying on a prime-order group such as Ristretto, used by Signal's private group system [CPZ20], or extending GGM to work over non-prime groups. We leave these considerations for future work.

Similarly, we show strong local and global deniability of PQXDH against a classical accuser and a *classical* distinguisher.

**Strong HNJL local and global deniability for receivers.** For strong (local and global) HNJL deniability of PQXDH, we are only able to prove deniability for the *receiver*; see the paragraph below for a discussion on why the deniability of the *sender* breaks. In fact, we can only prove strong deniability for the receiver in the *classical* ROM, while still enabling quantum capability to the distinguisher. In the classical ROM, the proof is quite natural using the observation in Sec. 3.3, that is, the simulator need only simulate when the (honest) receiver accepts. Indeed, for the receiver to accept, the KDF, modeled as a random oracle, must have output a key and a confirmation tag $K \parallel \tau_{conf}$, since the receiver must recompute the same tag $\tau_{conf}$ as the sender to accept. If such a key $K$ exists, the simulator simply outputs $K$. Unfortunately, it is unclear how to extend our proof to work in the *quantum* ROM. Our proof hinges on the simulator observing the input/output of the random oracle, however, in the QROM, such measurement may affect the malicious accuser's quantum state, leading to a different behavior from the real world. We leave it as an open problem to prove fully post-quantum receiver strong deniability.

**Attack on strong HNJL deniability for senders.** Interestingly, the situation changes when considering strong deniability for senders. We observe that there is an attack on strong sender deniability if the distinguisher is *quantum* while the accuser and simulator are classical, regardless of the classical or quantum ROM. Namely, a malicious receiver can craft a public key $spk_r$ in its prekey bundle, such that it can later prove that it does not know the associated secret key $spksec_r$. For instance, it can hash to a random group element so that it does not know the associating secret exponent. This means that if a handshake message contains a key $K$ and tag $\tau_{conf}$ derived from inputs $ss_1, ss_2, ss_3$, and $ss_4$ (if the last resort prekey is not used), that are correctly computed, then these must have been computed with the sender's secrets. The key difference here compared to deniability in the classical setting is in the distinguisher's ability to tell that $ss_1, ss_2, ss_3$, and $ss_4$ are correctly computed. Indeed, a distinguisher with quantum capabilities can compute the secrets associated to sender and receiver public keys, and simply recompute these values to check, and thereby decide whether the transcript was produced by the sender.
As explained above, a similar attack does not work if the malicious accuser is a sender, since without knowledge of the secret keys, the sender cannot compute a tag $\tau_{conf}$ that passes the receiver's check on Alg. 6 Ln. 19.

**Remark 2.** In our BAKE model, all elements of a pre-key bundle run out simultaneously. However, in the actual specification of PQXDH, last resort KEM keys may be used before one runs out of one time prekeys $opk_{r,t}$ and vice versa. This does not harm our deniability results for PQXDH. As this follows from the same argument as above, only with more case distinctions, we refer the interested reader to App. E.6.

# 5. Deniability of RingXKEM

RingXKEM is a PQ Signal handshake protocol by Hashimoto, Katsumata, and Wiggers [HKW25], using ring signatures to simultaneously ensure authentication and deniability. This is an optimized protocol based on [Bre+22; Has+21; Has+22] where receiver bandwidth and storage requirements on the server are reduced by using Merkle trees for the authentication of prekey bundles.

<footnote n="9">⁹Against classical D, global deniability of PQXDH follows from X3DH.</footnote>
<caption>**Algorithm 7** Game for the deniability of RS.</caption>

1: **function** Game<sub>RS,b, A</sub><sup>Deny</sup> (1<sup>λ</sup>, Q)
2: &nbsp;&nbsp;&nbsp;&nbsp;**for** user $u \in [N]$ **do** ($rvk_u, rsk_u$) $\leftarrow^S$ RS.KeyGen(1<sup>λ</sup>)
3: &nbsp;&nbsp;&nbsp;&nbsp;**q** := 0 ▷ *Number of queries made*
4: &nbsp;&nbsp;&nbsp;&nbsp;**return** $b \leftarrow^S \mathcal{A}^{O_{RS,Sign}(\cdot, \cdot, \cdot)}((rvk_u, rsk_u)_{u \in [N]})$
5: **function** $O_{RS,Sign}(M, u_0, u_1)$
6: &nbsp;&nbsp;&nbsp;&nbsp;**require** $[(u_0, u_1) \in [N] \times [N]] \wedge [[q < Q]]$
7: &nbsp;&nbsp;&nbsp;&nbsp;**q** $\leftarrow q + 1$
8: &nbsp;&nbsp;&nbsp;&nbsp;**return** $\sigma \leftarrow^S$ RS.Sign($rsk_{u_0}, M, \{rvk_{u_0}, rvk_{u_1}\}$)

## 5.1. Deniable Ring Signatures

We first recall the syntax of ring signatures. Standard notions of correctness and unforgeability are provided in App. A.4.

**Definition 8 (Ring Signatures).** A ring signature (RS) scheme consists of three PPT algorithms:

RS.KeyGen(1<sup>λ</sup>) $\xrightarrow{\delta}$ (rvk, rsk): On input the security parameter 1<sup>λ</sup>, it outputs a pair of keys (rvk, rsk).

RS.Sign(rsk, M, RL) $\xrightarrow{\delta}$ sig: On input a secret key rsk, a message M, and a list of public keys equipped with some canonical ordering, i.e., a *ring*, RL = {rvk<sub>1</sub>, ..., rvk<sub>N</sub>}, it outputs a signature sig.

RS.Verify(RL, M, sig) $\rightarrow 1/0$: On input a ring RL = {rvk<sub>1</sub>, ..., rvk<sub>N</sub>}, a message M, and a signature sig, it outputs 1 if the signature is valid and 0 otherwise.

**Deniability: weakening anonymity.** The standard notion of anonymity guarantees that signatures produced using two secret keys are indistinguishable. While sufficient, we observe that, thanks to our new metric for measuring the deniability of BAKEs in terms of the hockey-stick divergence, we can relax anonymity (cf. Sec. 3.1). Informally, we only care that signatures remain *deniable*; the signatures do not provide hard evidence about which secret key was used to sign a message.

**Definition 9 (Deniability).** Let $\mu: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{R}^+$ be a positive-valued function and $Q = \text{poly}(\lambda)$ an upper bound on the number of signing queries. A ring signature scheme is $(\mu, \delta)$-deniable if for any $N = \text{poly}(\lambda)$, and efficient adversary $\mathcal{A}$,

$$ \Pr \left[ \text{Game}_{\text{RS},0,\mathcal{A}}^{\text{Deny}}(1^{\lambda}, Q) = 0 \right] \leq \mu(\lambda, Q) \cdot \Pr \left[ \text{Game}_{\text{RS},1,\mathcal{A}}^{\text{Deny}}(1^{\lambda}, Q) = 0 \right] + \delta, $$

with $\delta = \text{negl}(\lambda)$, and where $\text{Game}_{\text{RS},b, \mathcal{A}}^{\text{Deny}}$ is defined in Alg. 7.

As alluded to in Sec. 3.1, the main benefit of our new definition is that it provides justification to formally use “reasonably” anonymous RSs. Indeed, we show that an RS based on the NIST-standardized Falcon [Pre+22] is deniable with a multiplicative slack $\mu = 1 + 2^{-27}$; if we used the standard notion of anonymity, this translates to a mere 27-bits of security. This indicates that deniability is a more fine-grained notion than anonymity, allowing to split up the distinguishing probability $\delta_{\text{anon}}$ of anonymity into $\mu$ and $\delta$ of deniability. What we uncover is that if $\delta_{\text{anon}}$ can be “absorbed” into $\mu$, we can maintain a negligibly small $\delta$, sufficient for deniability applications. We believe our new definition to be of an independent interest.

## 5.2. The RingXKEM protocol

The RingXKEM protocol, ignoring the Merkle tree optimization, can be summarized as a key exchange using an ephemeral KEM key for forward secrecy, a long-term KEM identity key to authenticate the receiver, and an RS to authenticate the sender. Each user generates a pair of RS keys (rvk, rsk) as part of their identity key. An RS verification key $rvk$ is also added to the prekey bundles, however the associated secret $rsk$ is never used, and immediately disposed of after generation. In contrast to other elements in the prekey bundle, $rvk$ is not authenticated for deniability. The sender authenticates by signing the handshake message for the ring of $rvk_s$ and $rvk_r$.

Signaling each prekey bundle for authentication would be costly, due to the size of PQ signatures. Hashimoto, Katsumata, and Wiggers [HKW25] thus proposed an optimization, where a Merkle tree of KEM public keys $dk_{u,t}$ replaces individual signatures with a path to the root and a single signature on the root. This amortizes storage costs across all prekey bundles uploaded by a single call to PreKeyBundleGen. Note that although we include the Merkle tree path in our description of prekey bundles, the server can recompute the path and tree root from uploaded bundles, eliminating the need to store them.

In Alg. 8 we show the details for the identity key generation and prekey bundle generation algorithms for RingXKEM. Any functionality exclusive to either algorithm is marked by grey dotted boxes for RingXKEM and by plain dash-dotted boxes for SignXKEM. The algorithms defining the RingXKEM Send and Receive algorithms are given in Algs. 9 and 10.
<caption>**Algorithm 8** RingSignXKEM's identity key and prekey bundle generation algorithms.</caption>

1: **function** RINGSIGNXKEM.IdKeyGen(1<sup>l</sup>)
2: &nbsp;&nbsp;&nbsp;&nbsp;(ek, dk) $\leftarrow$ KEM.KeyGen (1<sup>l</sup>)
3: &nbsp;&nbsp;&nbsp;&nbsp;($\hat{r}$vk, $\hat{r}$sk) $\leftarrow$ RS Sign KeyGen (1<sup>l</sup>)
4: &nbsp;&nbsp;&nbsp;&nbsp;**return** (ik := (ek, $\hat{r}$vk), isk := (dk, $\hat{r}$sk))
5: **function** RINGSIGNXKEM.PreKeyBundleGen(isk<sub>u</sub>)
6: &nbsp;&nbsp;&nbsp;&nbsp;(dk<sub>u</sub>, $\hat{r}$sk<sub>u</sub>) $\leftarrow$ isk<sub>u</sub>
7: &nbsp;&nbsp;&nbsp;&nbsp;D<sub>kem</sub>, D<sub>ρ⊥</sub> := ∅ $\triangleright$ Initialize empty lists
8: &nbsp;&nbsp;&nbsp;&nbsp;**for** t $\in$ [L] $\cup$ {⊥} **do**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\hat{e}$k<sub>u,t</sub>, $\hat{d}$k<sub>u,t</sub>) $\leftarrow$ KEM.KeyGen (1<sup>l</sup>)
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▲ Create and sign Merkle tree
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(root<sub>u</sub>, tree<sub>u</sub>) $\leftarrow$ MerkleTree(($\hat{e}$k<sub>u,t</sub>)<sub>t$\in$L</sub> $\cup$ {⊥})
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\sigma_{u,root}$ $\leftarrow$ RS Sign Sign ($\hat{r}$sk<sub>u</sub>, root<sub>u</sub>, { $\hat{r}$vk<sub>u</sub>})
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\hat{r}$vk<sub>u</sub>, $_{⊥}$) $\leftarrow$ RS.KeyGen (1<sup>l</sup>) $\triangleright$ Discard rsk
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** t $\in$ [L] **do** $\triangleright$ One-time prekey bundles
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;path<sub>u,t</sub> $\leftarrow$ getMerklePath(tree<sub>u</sub>, t)
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prek<sub>u,t</sub> := ($\hat{e}$k<sub>u,t</sub>, path<sub>u,t</sub>, root<sub>u</sub>, $\sigma_{u,root}$, $\hat{r}$vk<sub>u</sub>)
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;D<sub>kem</sub>[t] $\leftarrow$ (prek<sub>u,t</sub>, $\hat{d}$k<sub>u,t</sub>)
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▲ Last-resort prekey bundle t = ⊥
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;path<sub>u,⊥</sub> $\leftarrow$ getMerklePath(tree<sub>u</sub>, L + 1)
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prek<sub>u,⊥</sub> := ($\hat{e}$k<sub>u,⊥</sub>, path<sub>u,⊥</sub>, root<sub>u</sub>, $\sigma_{u,root}$, $\hat{r}$vk<sub>u</sub>)
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;D<sub>kem</sub>[L + 1] $\leftarrow$ (prek<sub>u,⊥</sub>, $\hat{d}$k<sub>u,⊥</sub>)
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $\left(\begin{array}{l} \tilde{\text{prek}}_{u} := (\text{prek}_{u,t})_{t \in [L] \cup \{\perp\}}, \\ \text{st}_{u} := (D_{\text{kem}}, \hat{r}v_{k}, D_{\rho_{\perp}})\end{array}\right)$

<caption>**Algorithm 9** The RingSignXKEM Send algorithm</caption>

1: **function** RINGSIGNXKEM Send(isk<sub>s</sub>, ik<sub>r</sub>, prek<sub>r</sub>)
2: &nbsp;&nbsp;&nbsp;&nbsp;($\hat{d}$s<sub>s</sub>, $\hat{r}$sk<sub>s</sub>) $\leftarrow$ isk<sub>s</sub>; (ek<sub>r</sub>, $\hat{r}$vk<sub>r</sub>) $\leftarrow$ ik<sub>r</sub>
3: &nbsp;&nbsp;&nbsp;&nbsp;($\hat{e}$k<sub>r</sub>, path<sub>r</sub>, root<sub>r</sub>, $\sigma_{r,root}$, $\hat{r}$vk<sub>r</sub>) $\leftarrow$ prek<sub>r</sub>
4:
5: &nbsp;&nbsp;&nbsp;&nbsp;**require** $\llbracket$ ReconstructRoot($\hat{e}$k<sub>r</sub>, path<sub>r</sub>) $\rrbracket$ = root<sub>r</sub> $\rrbracket$
6: &nbsp;&nbsp;&nbsp;&nbsp;**require** $\llbracket$ RS Sign Verify($\hat{r}$vk<sub>r</sub>, { $\hat{r}$vk<sub>r</sub> }, $\hat{e}$k<sub>r</sub>, $\sigma_{r,root}$) $\rrbracket$ = 1 $\rrbracket$
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\hat{ss}$<sub>r</sub>, ct<sub>r</sub>) $\leftarrow$ KEM.Encaps(ek<sub>r</sub>)
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($\hat{ss}$<sub>r</sub>, $\hat{ct}$<sub>r</sub>) $\leftarrow$ KEM.Encaps(ek<sub>r,t</sub>)
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;context := ik<sub>s</sub> $\Vert$ ik<sub>r</sub> $\Vert$ prek<sub>r,t</sub> $\Vert$ ct<sub>r</sub> $\Vert$ $\hat{ct}$<sub>r</sub>
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$K \Vert K_{ske}$ := KDF($\hat{ss}$<sub>r</sub> $\Vert \hat{ss}$<sub>r</sub>, context)
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\sigma_{s}$ $\leftarrow$ RS Sign Sign ($\hat{r}$sk<sub>s</sub>, context, { $\hat{r}$vk<sub>s</sub>, $\hat{r}$vk<sub>r</sub>})
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ct<sub>ske</sub> $\leftarrow$ SKE.Enc($K_{ske}$, $\sigma_{s}$) $\triangleright$ Mask signature
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\rho$ := (ct<sub>r</sub>, $\hat{ct}$<sub>r</sub>, ct<sub>ske</sub>)
14: &nbsp;&nbsp;&nbsp;&nbsp;**return** (K, $\rho$)
<caption>**Algorithm 10 The RingSignXKEM Receive algorithm**</caption>

1: **function** RINGSIGNXKEM Receive(isk_r, st_r, ik_s, t, ρ)
2: &nbsp;&nbsp;&nbsp;&nbsp;`(dk_r, rk_r) ← isk_r; (ek_s, rk_s) ← ik_s`
3: &nbsp;&nbsp;&nbsp;&nbsp;`(D_kem, rk_r, D_ρ_⊥) ← st_r`
4: &nbsp;&nbsp;&nbsp;&nbsp;`(ct_r, ck_r, ct_ske) ← ρ`
5: &nbsp;&nbsp;&nbsp;&nbsp;▷ Check t^th^ prekey bundle was not deleted.
6: &nbsp;&nbsp;&nbsp;&nbsp;**require** [[D_kem[t] ≠ ⊥]]
7: &nbsp;&nbsp;&nbsp;&nbsp;**if** [[t = ⊥]] **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**require** [[(ct_r, ck_r) ∈ D_ρ_⊥]] ▷ Prevent replays
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;D_ρ_⊥ ← D_ρ_⊥ ∪ { (ct_r, ck_r) }
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(prek_r,t, dk_r,t) ← D_kem[t]
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ss_r := KEM.Decaps(dk_r, ct_r)
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ss_r := KEM.Decaps(dk_r,t, ct_r)
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;content := ik_s || ik_r || prek_r,t || ct_r || ck_r
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;K || K_ske := KDF(ss_r || ss_r, content)
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;σ_s := SKE.Dec(K_ske, ct_ske) ▷ Unmask signature
16: &nbsp;&nbsp;&nbsp;&nbsp;**require** [[RS Sign, Verify(vk_s, {rvk_s, rk_r}, content, σ_s) = 1]]
17: &nbsp;&nbsp;&nbsp;&nbsp;**if** [[t ≠ ⊥]] **then**
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;D_kem[t] ← ⊥ ▷ Delete prekey bundle
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;st_r ← (D_kem, rk_r, D_ρ_⊥)
20: &nbsp;&nbsp;&nbsp;&nbsp;**return** (K, st_r)

## 5.3. Summary: Deniability of RingXKEM

We summarize the level of deniability that RingXKEM satisfies. See Tab. 1 for a complete overview. The formal statements are provided in App. G.

**Local and global deniability.** RingXKEM achieves the highest level of local deniability. This matches our intuition since, due to the deniability of RS, the signature included in the senders' handshake message, which authenticates the sender, does not reveal which key (among rvk_s and ^rvk_r) was used to sign, so that either the sender or the receiver could have produced it.

We further have global deniability, thanks to the RS key rvk in the prekey bundle not being authenticated. Specifically, the simulator, given prekey bundles of honest users, can substitute the verification key rvk_r with one for which it knows the associated secret key. It can then easily compute the required ring signature and simulate the communication of two honest users. However, note that the receiver's state st_r := (D_kem, rk_r, D_ρ_⊥) contains the (non-simulated) verification key ^rvk_r, as such, if the this state leaks, the distinguisher can easily tell apart real and simulated executions. Hence, global deniability holds so long as the honest receiver's state does not leak, i.e., for leak = med.

Both local and global deniability of RingXKEM hold even if both the accuser and the distinguisher are quantum, so long as RS's deniability holds against quantum adversaries.

**Strong local and global deniability.** The situation for strong (local and global) deniability is less clear. Firstly, we are only able to prove deniability for the receiver; see App. G.3.1 for a discussion on why the deniability of the sender breaks (see also Rem. 1). In fact, we can only prove strong deniability for the receiver in the classical ROM, while still enabling quantum capability to the malicious accuser and distinguisher. In the classical ROM, the proof is quite natural using the observation in Sec. 3.3, that is, the simulator need only simulate when the (honest) receiver accepts. Indeed, for the receiver to accept, the KDF, modeled as a random oracle, must have output keys $K \parallel K_{ske}$ for which the ciphertext ct_ske in the (possibly maliciously generated) handshake message $\rho$ decrypts correctly, yielding a valid signature of content for the ring $\{rvk_s, \overline{rvk_r}\}$. If such keys exist, the simulator simply outputs $K$.

Unfortunately, it is unclear how to extend our proof to work in the quantum ROM. Our proof hinges on the simulator observing the input/output of the random oracle, however, in the QROM, such measurement may affect the malicious accuser's quantum state, leading to a different behavior from the real world. We leave it as an open problem to prove fully post-quantum receiver strong deniability.

## 5.4. Alternative BAKE from Plain Signatures

At the cost of a loss in deniability, one can use plain digital signatures instead of ring signatures. Such a scheme was suggested in [Has+21], and benefits from being more efficient and simpler to implement. A description of the resulting scheme, which we call SignXKEM, is given in Algs. 8 to 10. The key difference from RingXKEM is that a (plain) signature is used to authenticate the sender. SignXKEM offers a limited notion of deniability, relying on the IND-CPA security of the KEM and
SKE schemes to hide the sender's no-longer-deniable signature. The level of deniability is provided in Tab. I, where the formal statements are provided in App. H. It is worth noting that SignXKEM is the only protocol presented in this work where one must restrict the information disclosed by accusers for deniability to hold, even in the (standard) local setting. Indeed, if one cannot assume secure key erasure, this protocol may not be satisfactory. As such, this protocol may not provide deniability if one is communicating with untrusted peers.

# 6. Ring Signatures from Falcon and MAYO

In this section, we introduce two novel 2-user ring signatures achieving our deniability notion from Sec. 5.1. The goal is to design optimized 2-ring signatures based on NIST standards, for an increased potential of adoption. We identified two strong candidate signature schemes: the standardized signature Falcon [Pre+22], and the additional signature candidate MAYO [Beu+24]. Both of these schemes have short signatures, and thus great potential for compact ring signatures.

## 6.1. Falcon-Based Ring Signature

This section provides a high-level description for our Falcon-based ring signature, based on the generic lattice-based RS design by [GJK24b] instantiated with Falcon-specific components. Formal definitions are given in App. I.1.

Falcon is a hash-and-sign signature scheme standardized by NIST. It is built over NTRU lattices, that is lattices generated using a uniform-looking polynomial $h = g \cdot f^{-1}$ where $f, g$ are short polynomials in the ring $\mathcal{R}_q = \mathbb{Z}_q[x]/(x^n + 1)$. Key generation calls an NTRU trapdoor sampler TpdGen() to obtain a public polynomial $h$, and a trapdoor basis $\mathbf{B}$ for the corresponding NTRU lattice. Then, to sign a message $M$, one samples a salt $\mathbf{salt}$, and computes a target $c = H(\mathbf{M}, \mathbf{salt})$ from a hash function. The trapdoor then allows for sampling a short preimage $(u, v) = \text{PreSmp}(\mathbf{B}, \sigma, -c)$ in the NTRU lattice of $c$, i.e. such that $h \cdot u + v = c$. The signature is $(\mathbf{salt}, u)$. Verification first recovers $v = c - h \cdot u$ from $c = H(\mathbf{M}, \mathbf{salt})$, and verifies the shortness of $(u, v)$, i.e. that $\|(u, v)\| \le \beta$.

### 6.1.1. Ring Signature Construction

We propose a ring signature FalconRS built from Falcon, and overcome theoretical limitations of previous works [GJK24b; LAZ19b] as it seems impossible to prove standard anonymity when using Falcon components. We instead aim for our relaxed deniability notion.

Our RS scheme samples a public polynomial $h_i \in \mathcal{R}_q$ and trapdoor $\mathbf{B}_i$ for each ring user $i \in [N]$. Signing is modified to find a preimage of $c$ for an aggregation of the public keys: we sample $v$, $(u_i)_{i \in [N]}$ such that $c = v + \sum_i h_i \cdot u_i$ knowing only the trapdoor for a single $h_i$. This aggregation is inspired by ring trapdoor functions [BK10], although lattices allow further optimization: we can reuse coordinate $v$ for all signers and omit it in the final signature since it can be recovered from $c$ and the $u_i$. This optimization was recently analyzed in [GJK24b], proposing a generic lattice-based RS construction called Gandalf.<fnref n="10" />

Concretely, when party $i$ signs, it first samples the contribution for other parties as discrete Gaussians of parameter $\sigma$, i.e., $u_j \stackrel{\$}{\leftarrow} \chi_u$ for $j \neq i$ ($\chi_u$ is tailcut to $[-\eta', \eta']$ for implementation purposes). It then samples $(u_i, v) \stackrel{\$}{\leftarrow} \text{PreSmp}(\mathbf{B}_i, \sigma, -c')$, where $c' = H(\mathbf{M}, \mathbf{salt}) - \sum_{j \neq i} u_j \cdot h_j$, to complete the signature $\text{sig} = (u_i)_{i \in [N]}$. Leveraging the fact $(u_i, v)$ appears as Gaussian distributed when $c'$ is uniform, we can show that the signature distribution is roughly independent of the signer, ensuring deniability. To cover the larger number of elements in the ring signature, we introduce a new verification bound $\beta_{\text{sig}}$. The construction is formalized in Alg. 11.

### 6.1.2. Security Analysis and Parameters

FalconRS uses the same base parameters as Falcon-512. The ring verification bound $\beta_{\text{sig}}$ is set to $1.1 \cdot \sqrt{3n\sigma}$ to bound the norm of two user contributions.

**Unforgeability.** FalconRS can be proven unforgeable in an analogous manner to Falcon [GJK24a], reducing to the same NTRU and RSIS assumptions, though the SIS bound is increased by a factor $\sqrt{k+1}/\sqrt{2}$, and its preimage space is of dimension $k+1$ for rings of $k$ users. This leads to a core-SVP security of 111 bits; a reasonable degradation over the 120 bits of Falcon.

**Deniability.** Proving anonymity appears unfeasible for an RS based on the Falcon parameters, as the distribution of signatures is at a non-negligible distance from the ideal one. Instead, we show that FalconRS is deniable. We defer the formal statement to App. I.1.2, and provide the intuition here.

The real signature distribution differs from the ideal one for two reasons: (i) the convolution of discrete Gaussians only approximates a discrete Gaussian with larger parameters, and (ii) the use of approximations in internal computations (tail

<footnote n="10">¹⁰Note that [GJK24b] instantiates their generic construction Gandalf using a trapdoor sampler from Antrag [Esp+23] and a preimage sampler from Mitaka [Esp+22]. Their concrete RS instantiation is also called Gandalf. Below, to avoid confusion, we always mean the concrete instantiation when referring to Gandalf.</footnote>
<caption>**Algorithm 11** Falcon-based ring signature scheme</caption>

1: **function** FalconRS.KeyGen($1^{\lambda}$)
2: &nbsp;&nbsp;&nbsp;&nbsp;h, B $\stackrel{\$}{\leftarrow}$ TpdGen() &gt; Sample lattice generator h, and trapdoor
3: &nbsp;&nbsp;&nbsp;&nbsp;**return** (rvk := h, rsk := B)
4: **function** FalconRS.Sign(rsk$_i$, M, RL := {rvk$_j$}$_j$)
5: &nbsp;&nbsp;&nbsp;&nbsp;B := rsk$_i$; {h$_j$}$_j$ := {rvk$_j$}$_j$
6: &nbsp;&nbsp;&nbsp;&nbsp;salt $\stackrel{\$}{\leftarrow}$ {0, 1}$^k$; c := H(salt, RL, M) ∈ $\mathbb{R}_q$
7: &nbsp;&nbsp;&nbsp;&nbsp;**for** j $\neq i$ **do** u$_j$$\stackrel{\$}{\leftarrow}$ $\chi_u$ $\succ$ $\chi_u$ is $\mathbb{D}_{\mathbb{Z}^n, \sigma, 0}$ tailcut to [-$\eta'$, $\eta'$]
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c' := t - $\sum_{j \neq i} h_j \cdot u_j$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(u$_i$, v) := PreSmp(B, $\sigma$, -c') $\succ$ Pre-image sampling
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $\|\|((u_j)_i, v + c')\|\| > \beta_{\text{sig}}$ **then** restart $\succ$ Too large
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** sig := (salt, {u$_j$}$_j$)
12: **function** FalconRS.Verify(RL := {rvk$_j$}$_j$, M, sig)
13: &nbsp;&nbsp;&nbsp;&nbsp;(salt, {u$_i$}$_i$) := sig; {h$_i$}$_i$ := {rvk$_i$}$_i$
14: &nbsp;&nbsp;&nbsp;&nbsp;c := H(salt, RL, M) ∈ $\mathbb{R}_q$
15: &nbsp;&nbsp;&nbsp;&nbsp;v := c - $\sum_i h_i \cdot u_i$ $\succ$ Compute v such that c = v + $\sum_i h_i \cdot u_i$
16: &nbsp;&nbsp;&nbsp;&nbsp;**return** $\|\|((u_i)_i, v)\|\| \le \beta_{\text{sig}}$ $\succ$ Verify pre-image shortness

cuts, floating points, and polynomial approximations). The use of tail cuts translates to a statistical distance characterized by the deniability term $\delta$. Falcon cuts tails with probability roughly $2^{-70}$, and we similarly select the tailcut parameter $\eta'$ of $\chi_u$ to ensure a negligible tailcut probability of $2^{-70}$ (i.e. $\eta' := \lceil \sqrt{70 \cdot \log(2)} \cdot \sqrt{2} \cdot \sigma \rceil = 1633$). This guarantees a small term $\delta$. Interestingly, the other approximations introduce a relative error in the signature distribution, so that the probability of sampling a given signature is multiplied by a factor close to 1. These are absorbed by the multiplicative slack $\mu$, which exactly captures such factors between probabilities.

We formalize and evaluate the errors introduced by each approximation in App. I.1.3, obtaining that FalconRS is $(\mu, \delta)$-deniable for $\mu = 1 + 2^{-27}$ and $\delta = 2^{-57}$. We note that our analysis readily applies to Gandalf [GJK24b], which chooses a different trapdoor generator and preimage sampler to instantiate the generic construction of [GJK24b]. While Gandalf initially claimed an anonymity of $2^{-70}$, an updated version acknowledged a proof flaw and an anonymity of only $2^{-30}$. Alternatively, Gandalf can be proven *deniable*, with roughly the same $\mu, \delta$ as FalconRS.

## 6.2. MAYO-based Ring Signature

We provide a second RS construction based on MAYO, a candidate in NIST's Call for Additional Signature Schemes. Viewing MAYO as a hash-then-sign signature scheme, we can apply generic transformations from [AOS02] to obtain an efficient RS. We analyze parameter sets proposed for standardization and provide alternative ones achieving higher deniability.

MAYO is designed over quadratic maps. At a high level, it chooses a map $\mathcal{P} : \mathbb{F}_q^n \to \mathbb{F}_q^m$ with trapdoor tp, as public and secret keys respectively, from which is derived a larger map $\mathcal{P}^* : \mathbb{F}_q^{kn} \to \mathbb{F}_q^m$. To sign message M, one computes a target $\mathbf{t} = H(M, \mathbf{salt})$ (where $\mathbf{salt}$ is a random value), and samples a preimage $u$ such that $\mathcal{P}^*(\mathbf{u}) = \mathbf{t}$, leveraging the trapdoor tp. The final signature is $\mathbf{sig} := (\mathbf{salt}, \mathbf{u})$.

The transform by Abe, Ohkubo, and Suzuki [AOS02] allows us to generically turn MAYO into an RS. We defer the full description to App. I.2. Analogously to FalconRS, the final MayoRS ring signature includes a pre-image $\mathbf{u} \in \mathbb{F}_q^{kn}$ for each ring user, as well as a seed generating a target. In the two-user setting, the signature size is thus roughly doubled over MAYO.

### 6.2.1. Security Analysis and Parameters

We here overview the unforgeability and deniability of MayoRS, deferring formal statements and proofs to App. I.2.1.

**Unforgeability.** Using the generic transform of [AOS02], we reduce the unforgeability of MayoRS to that of MAYO. We note that there is a loss in the reduction, linear in the number of random oracle queries made by the adversary. This does not, we consider, lead to an improved attack.

**Deniability.** We prove deniability of MayoRS by observing that first sampling a target $\mathbf{t}$ then a pre-image $\mathbf{u}$ of $\mathbf{t}$ is roughly equivalent to first sampling $\mathbf{u} \leftarrow \mathbb{F}_q^{kn}$ and taking $\mathbf{t} = \mathcal{P}^*(\mathbf{u})$. A small portion $B$ of the vectors $\mathbf{u}$ cannot be sampled in the first scenario. Adjusting for the number of system participants $N$, this leads to deniability with $(\mu = 1, \delta = 2N \cdot B)$, where $2N$ is a tightness slack.

One could directly use the parameters from the MAYO specification, but $MAYO_1$ and $MAYO_2$ achieve rather low deniability, so we provide three alternative parameter sets for NIST level I, with different trade-offs in size and deniability. We denote them MAYO\*, MAYO\*\*, and MAYO\*\*\* and detail their parameters in App. I.2.2.
We compare the sizes and performance of FalconRS and MayoRS with the original schemes in Tabs. 2 and 3. Ring signature sizes and computation times are all approximately doubled over the base scheme. We also include deniability guarantees achieved by each scheme. We provide implementations<fnref n="11" /> and compare our RSs to prior works in Sec. 6.3. Our constructions are as compact as the state-of-the-art, and built on more scrutinized schemes. Additionally, our implementations largely outperform the state-of-the-art, by factors 32–66× for signing, 146–1025× for verification.

<table><caption>Table 2: Sizes and deniability $(\mu, \delta)$ of FalconRS and MayoRS depending on the base scheme, aiming for NIST level I.</caption><thead><tr><th>Base Scheme</th><th>(μ, δ)</th><th>PK</th><th>Sig</th><th>2-RSig</th></tr></thead><tbody><tr><td>Falcon-512</td><td>1 + 2<sup>-27</sup>, 2<sup>-57</sup></td><td>897 B</td><td>666 B</td><td>1288 B</td></tr><tr><td>MAYO<sub>1</sub></td><td>1, 2N · 2<sup>-36</sup></td><td>1168 B</td><td>321 B</td><td>650 B</td></tr><tr><td>MAYO<sub>2</sub></td><td>1, 2N · 2<sup>-36</sup></td><td>5488 B</td><td>180 B</td><td>368 B</td></tr><tr><td>MAYO*</td><td>1, 2N · 2<sup>-52</sup></td><td>1569 B</td><td>335 B</td><td>677 B</td></tr><tr><td>MAYO**</td><td>1, 2N · 2<sup>-83</sup></td><td>1591 B</td><td>374 B</td><td>756 B</td></tr><tr><td>MAYO***</td><td>1, 2N · 2<sup>-124</sup></td><td>1771 B</td><td>492 B</td><td>992 B</td></tr></tbody></table>

<table><caption>Table 3: Performance of normal and 2-ring versions of Falcon and MAYO. Experiments executed on a Ryzen Pro 7 5850U @ 3GHz. Numbers are in Megacycles (Mc).</caption><thead><tr><th rowspan="2">Scheme</th><th rowspan="2">Keygen</th><th colspan="2">Sign</th><th colspan="2">Verify</th></tr><tr><th>normal</th><th>2-ring</th><th>normal</th><th>2-ring</th></tr></thead><tbody><tr><td>Falcon-512</td><td>6.2 Mc</td><td>0.26 Mc</td><td>0.74 Mc</td><td>0.02 Mc</td><td>0.04 Mc</td></tr><tr><td>MAYO<sub>1</sub></td><td>0.24 Mc</td><td>0.88 Mc</td><td>1.1 Mc</td><td>0.17 Mc</td><td>0.28 Mc</td></tr><tr><td>MAYO<sub>2</sub></td><td>0.65 Mc</td><td>1.1 Mc</td><td>1.5 Mc</td><td>0.09 Mc</td><td>0.16 Mc</td></tr></tbody></table>

## 6.3. Comparison with Previous Works on Ring Signatures

Several works introduced post-quantum ring signatures in the past. They provide different tradeoffs in terms of public key size versus signature size. We consider the lattice-based ring signatures Falafl [BKP20], DualRing-LB [Yue+21], Raptor [LAZ19b] and Gandalf [GJK24b]. We additionally consider the isogeny-based ring signature Calamari [BKP20], although the comparison should be made cautiously as isogenies provide different tradeoffs than lattices (in the security assumption, compactness, efficiency).

None of these schemes are based on a standardized scheme, except for Raptor which is based on Falcon. We also note that Gandalf and Raptor only achieve a non-negligible anonymity of the order $2^{-30}$, while they could be proven deniable as per Def. 9 – further demonstrating the applicability of our notion.

Only some of these works provide publicly available and optimized C implementations: Raptor [LAZ19b], Calamari and Falafl [BKP20]. DualRing-LB only provides a Python proof of concept<fnref n="12" />, and Gandalf had no implementation at the time of writing this article<fnref n="13" />.

We provide concrete size and performance numbers in Tab. 5 and Tab. 6. These tables, together with Tab. 2, Tab. 3, highlight that our proposals FalconRS and MayoRS are as compact as previous works based on non-standard schemes, and that our implementations largely outperform all previous available post-quantum ring signature implementations.

## 7. Efficiency Comparison

Though RingXKEM has better deniability than SignXKEM, we need to consider the cost in terms of bandwidth and runtime. In Sec. 6, we already discussed performance metrics for the proposed ring signatures. As they are well under typical network latencies, we will conclude that all primitives considered are computationally efficient; though Hashimoto, Katsumata, and Wiggers [HKW25, Sec. 6] also discussed bandwidth, they did not consider SignXKEM and only instantiated RingXKEM with Gandalf [GJK24b].

<footnote n="11">¹¹Available as an artifact through DOI 10.5281/zenodo.15571694</footnote>

<footnote n="12">¹²https://github.com/thyuen/dualring.git</footnote>

<footnote n="13">¹³It has since been implemented in [GHJ25], and their code is available at https://github.com/vincentvhb/shadowfax/blob/main/Gandalf/.</footnote>

<footnote n="14">¹⁴https://github.com/zhenfeizhang/raptor/tree/37d78152bbca69b27b13a184347ceaec8ffbd69f</footnote>
<table><caption>Table 5: Sizes of concurrent ring signature schemes, and whether they achieve a negligible anonymity for concretely selected parameters.</caption><thead><tr><th>Scheme</th><th>PK</th><th>2-RSig</th><th>Negligible<br>anonymity</th></tr></thead><tbody><tr><td>Gandalf</td><td>896 B</td><td>1236 B</td><td>×</td></tr><tr><td>Raptor</td><td>900 B</td><td>2532 B</td><td>×</td></tr><tr><td>Calamari</td><td>64 B</td><td>3662 B</td><td>✓</td></tr><tr><td>DualRing-LB</td><td>2496 B</td><td>3877 B</td><td>✓</td></tr><tr><td>Falafl</td><td>4096 B</td><td>30 016 B</td><td>✓</td></tr></tbody></table>

<table><caption>Table 6: Performance of prior works on ring signatures, to compare with our instantiations from Tab. 3. Experiments executed on a Ryzen Pro 7 5850U @ 3GHz. Numbers are in Megacycles (Mc).</caption><thead><tr><th>Scheme</th><th>Keygen</th><th>Sign<br>2-ring</th><th>Verify<br>2-ring</th></tr></thead><tbody><tr><td>Raptor<sup>14</sup></td><td>27.1 Mc</td><td>5 Mc</td><td>2 Mc</td></tr><tr><td>Calamari [BKP20]</td><td>119.5 Mc</td><td>46 581 Mc</td><td>41 250 Mc</td></tr><tr><td>Falafl [BKP20]</td><td>0.1 Mc</td><td>163 Mc</td><td>76 Mc</td></tr></tbody></table>

Table 7 compares instantiations of RingXKEM and SignXKEM, as well as an overview of how far from (currently) standardized cryptography the instantiations are. All schemes use a verification key as identity public key; RingXKEM and SignXKEM additionally use a KEM public key. We show the sizes using Kyber-1024 following PQXDH, as well as with Kyber-512 which matches the security of the (ring) signature scheme. The X3DH prekey bundle consists of two ECDH public keys and a signature, PQXDH adds a KEM public key and a signature. For RingXKEM and SignXKEM, the prekey bundle is a KEM public key, a Merkle tree authentication path, a signature on the root of this tree, and, for RingXKEM, an RS verification key. The X3DH handshake message is an ECDH public key and an authentication tag; PQXDH adds a KEM ciphertext. For RingXKEM and SignXKEM, this message is an encrypted (ring) signature and two ciphertexts.

We can clearly see in the table that the reduction in deniability by switching from RingXKEM to SignXKEM only leads to a modest decrease in transmission sizes, typically less than 1 kB. Due to the Merkle tree optimization proposed in [HKW25], the increase in server storage requirements for the prekey bundles is only about 1 kB in total. The RingXKEM instantiation based on NIST standard Falcon [Pre+22] is also close in bandwidth requirements to the instantiation based on Gandalf [GJK24b] relying on the trapdoor sampler of Antrag [Esp+23] and a preimage sampler of Mitaka [Esp+22].

<table><caption>Table 7: Practicality of deniable Signal handshake protocols. Batch size *L* = 100, sizes in bytes.</caption><thead><tr><th rowspan="2">Protocol</th><th rowspan="2">Fully PQ</th><th rowspan="2">KEX</th><th rowspan="2">Authentication<br>Primitive</th><th rowspan="2">Identity<br>public key</th><th colspan="2">Prekey bundle</th><th rowspan="2">Handshake<br>message</th><th rowspan="2">Underlying Crypto</th></tr><tr><th>Individual</th><th>L-key storage</th></tr></thead><tbody><tr><td>X3DH</td><td>×</td><td>X25519</td><td>XEd25519 [Per16]</td><td>32</td><td>128</td><td>3296</td><td>64</td><td>Derived from X25519</td></tr><tr><td>PQXDH</td><td>×</td><td>DH+Kyber-1024</td><td>XEd25519 [Per16]</td><td>32</td><td>1696</td><td>166 496</td><td>1632</td><td>Derived from X25519</td></tr><tr><td>RingXKEM</td><td>✓</td><td>Kyber-512</td><td>Gandalf [GJK24b]</td><td>1696</td><td>2582</td><td>81 526</td><td>2804</td><td>Based on Antrag and Mitaka</td></tr><tr><td>RingXKEM</td><td>✓</td><td>Kyber-1024</td><td>Gandalf [GJK24b]</td><td>2464</td><td>3350</td><td>158 326</td><td>4404</td><td>Based on Antrag and Mitaka</td></tr><tr><td>RingXKEM</td><td>✓</td><td>Kyber-512</td><td>FalconRS</td><td>1697</td><td>2619</td><td>81 563</td><td>2856</td><td>Based on Falcon</td></tr><tr><td>RingXKEM</td><td>✓</td><td>Kyber-1024</td><td>FalconRS</td><td>2465</td><td>3387</td><td>158 363</td><td>4456</td><td>Based on Falcon</td></tr><tr><td>RingXKEM</td><td>✓</td><td>Kyber-512</td><td>MAYO*</td><td>2369</td><td>2960</td><td>81 904</td><td>2245</td><td>Based on MAYO</td></tr><tr><td>RingXKEM</td><td>✓</td><td>Kyber-1024</td><td>MAYO*</td><td>3137</td><td>3728</td><td>158 704</td><td>3845</td><td>Based on MAYO</td></tr><tr><td>SignXKEM</td><td>✓</td><td>Kyber-512</td><td>Falcon [Pre+22]</td><td>1697</td><td>1722</td><td>80 666</td><td>2202</td><td>NIST standard</td></tr><tr><td>SignXKEM</td><td>✓</td><td>Kyber-1024</td><td>Falcon [Pre+22]</td><td>2465</td><td>2490</td><td>157 466</td><td>3802</td><td>NIST standard</td></tr><tr><td>SignXKEM</td><td>✓</td><td>Kyber-512</td><td>MAYO<sub>1</sub> [Beu+24]</td><td>1968</td><td>1377</td><td>80 321</td><td>1857</td><td>NIST on-ramp R2</td></tr><tr><td>SignXKEM</td><td>✓</td><td>Kyber-1024</td><td>MAYO<sub>1</sub> [Beu+24]</td><td>2736</td><td>2145</td><td>157 121</td><td>3457</td><td>NIST on-ramp R2</td></tr><tr><td>SignXKEM</td><td>✓</td><td>Kyber-512</td><td>MAYO<sub>2</sub> [Beu+24]</td><td>6288</td><td>1236</td><td>80 180</td><td>1716</td><td>NIST on-ramp R2</td></tr><tr><td>SignXKEM</td><td>✓</td><td>Kyber-1024</td><td>MAYO<sub>2</sub> [Beu+24]</td><td>7056</td><td>2004</td><td>156 980</td><td>3316</td><td>NIST on-ramp R2</td></tr></tbody></table>
# Acknowledgments

This paper is partially based on results obtained from a project, JPNP24003, commissioned by the New Energy and Industrial Technology Development Organization (NEDO). We thank the USENIX reviewers for valuable feedbacks on the definition of strong deniability. We also thank Rune Fiedler for sharing his recent paper [FL25], leading us to notice that PQXDH is not HNJL deniable against malicious receivers; as well as Vadim Lyubashevsky and Felix Günther for pointing out an oversight in our proof of global deniability for RingXKEM, leading us to downgrade the permitted leakage for this setting. Lastly, we thank Phillip Gajland, Jonas Janneck, and Eike Kiltz for helping us better understand Gandalf.

# Ethic Considerations

The security and privacy properties of Signal's handshake protocol is relied on by many. This makes it relevant and important to understand and make comparisons between the deniability properties of (proposals for) Signal handshake protocols.

**Risks and risk mitigation.** As prior work has thoroughly investigated the security of X3DH and PQXDH, we deemed any risk of finding previously unknown vulnerabilities exceedingly unlikely. If any significant issues had been found, we would have coordinated with Signal developers on how to best protect Signal's users, both of the Signal app itself, and other users of Signal including Facebook Messenger, WhatsApp, and others, with responsible disclosure practices.

**Benefits.** Signal is transitioning towards full post-quantum security. We aim to contribute to this by providing new results and a model for comparing relevant deniability properties.

# Open Science

The deniability model for Bundled AKE protocols is documented in this paper. For the proposed Falcon- and MAYO-based Ring signature schemes, we have experimental implementations made available in our artifact. It also includes prior ring signature implementations [BKP20; LAZ19b] adapted with our benchmark code. There are no other datasets or implementations relevant to this paper.

# References

[ABN10] Michel Abdalla, Mihir Bellare, and Gregory Neven. "Robust Encryption." In: *TCC 2010*. Ed. by Daniele Micciancio. Vol. 5978. LNCS. Springer, Berlin, Heidelberg, Feb. 2010, pp. 480–497. DOI: 10.1007/978-3-642-11799-2_28 (cit. on p. 28).

[AHU19] Andris Ambainis, Mike Hamburg, and Dominique Unruh. "Quantum Security Proofs Using Semi-classical Oracles." In: *CRYPTO 2019, Part II*. Ed. by Alexandra Boldyreva and Daniele Micciancio. Vol. 11693. LNCS. Springer, Cham, Aug. 2019, pp. 269–295. DOI: 10.1007/978-3-030-26951-7_10 (cit. on pp. 30, 34, 43, 44).

[AOS02] Masayuki Abe, Miyako Ohkubo, and Koutarou Suzuki. "1-out-of-n Signatures from a Variety of Keys." In: *ASIACRYPT 2002*. Ed. by Yuliang Zheng. Vol. 2501. LNCS. Springer, Berlin, Heidelberg, Dec. 2002, pp. 415–432. DOI: 10.1007/3-540-36178-2_26 (cit. on pp. 20, 50).

[Bac+15] Michael Backes, Aniket Kate, Sebastian Meiser, and Tim Ruffing. "Secrecy Without Perfect Randomness: Cryptography with (Bounded) Weak Sources." In: *ACNS 2015*. Ed. by Tal Malkin, Vladimir Kolesnikov, Allison Bishop Lewko, and Michalis Polychronakis. Vol. 9092. LNCS. Springer, Cham, June 2015, pp. 675–695. DOI: 10.1007/978-3-319-28166-7_33 (cit. on pp. 4, 8).

[Beu+24] Ward Beullens, Fabio Campos, Sofía Celi, Basil Hess, and Matthias J. Kannwischer. *MAYO*. Tech. rep. available at https://csrc.nist.gov/Projects/pqc-dig-sig/round-2-additional-signatures. National Institute of Standards and Technology, 2024 (cit. on pp. 4, 19, 22, 50).

[BF01] Dan Boneh and Matthew K. Franklin. "Identity-Based Encryption from the Weil Pairing." In: *CRYPTO 2001*. Ed. by Joe Kilian. Vol. 2139. LNCS. Springer, Berlin, Heidelberg, Aug. 2001, pp. 213–229. DOI: 10.1007/3-540-44647-8_13 (cit. on p. 30).

[BGB04] Nikita Borisov, Ian Goldberg, and Eric Brewer. "Off-the-record communication, or, why not to use PGP." In: *Proceedings of the 2004 ACM workshop on Privacy in the electronic society*. CCS04: 11th ACM Conference on Computer and Communications Security 2004 (Washington DC USA). New York, NY, USA: ACM, Oct. 28, 2004, pp. 77–84. ISBN: 9781581139686. DOI: 10.1145/1029179.1029200. URL: https://otr.cypherpunks.ca/otr-wpes.pdf (cit. on p. 5).
[Bha+24] Karthikeyan Bhargavan, Charlie Jacomme, Franziskus Kiefer, and Rolfe Schmidt. "Formal verification of the PQXDH Post-Quantum key agreement protocol for end-to-end secure messaging." In: USENIX Security 2024. Ed. by Davide Balzarotti and Wenyuan Xu. USENIX Association, Aug. 2024. url: https://www.usenix.org/conference/usenixsecurity24/presentation/bhargavan (cit. on p. 5).

[BK10] Zvika Brakerski and Yael Tauman Kalai. A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model. Cryptology ePrint Archive, Report 2010/086. 2010. url: https://eprint.iacr.org/2010/086 (cit. on p. 19).

[BKP20] Ward Beullens, Shuichi Katsumata, and Federico Pintore. "Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices." In: ASIACRYPT 2020, Part II. Ed. by Shiho Moriai and Huaxiong Wang. Vol. 12492. LNCS. Springer, Cham, Dec. 2020, pp. 464–492. doi: 10.1007/978-3-030-64834-3_16 (cit. on pp. 21–23, 29).

[Bre+20] Jacqueline Brendel, Marc Fischlin, Felix Günther, Christian Janson, and Douglas Stebila. "Towards Post-Quantum Security for Signal's X3DH Handshake." In: SAC 2020. Ed. by Orr Dunkelman, Michael J. Jacobson Jr., and Colin O'Flynn. Vol. 12804. LNCS. Springer, Cham, Oct. 2020, pp. 404–430. doi: 10.1007/978-3-030-81652-0_16 (cit. on p. 5).

[Bre+22] Jacqueline Brendel, Rune Fiedler, Felix Günther, Christian Janson, and Douglas Stebila. "Post-quantum Asynchronous Deniable Key Exchange and the Signal Handshake." In: PKC 2022, Part II. Ed. by Goichiro Hanaoka, Junji Shikata, and Yohei Watanabe. Vol. 13178. LNCS. Springer, Cham, Mar. 2022, pp. 3–34. doi: 10.1007/978-3-030-97131-1_1 (cit. on pp. 3, 5, 6, 8, 15).

[CCH23] Daniel Collins, Simone Colombo, and Loïs Huguenin-Dumittan. Real World Deniability in Messaging. Cryptology ePrint Archive, Report 2023/403. 2023. url: https://eprint.iacr.org/2023/403 (cit. on p. 7).

[CF11] Cas Cremers and Michele Feltz. One-round Strongly Secure Key Exchange with Perfect Forward Secrecy and Deniability. Cryptology ePrint Archive, Report 2011/300. 2011. url: https://eprint.iacr.org/2011/300 (cit. on p. 3).

[Col+24] Daniel Collins, Loïs Huguenin-Dumittan, Ngoc Khanh Nguyen, Nicolas Rolin, and Serge Vaudenay. "K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures." In: USENIX Security 2024. Ed. by Davide Balzarotti and Wenyuan Xu. USENIX Association, Aug. 2024. url: https://www.usenix.org/conference/usenixsecurity24/presentation/collins (cit. on pp. 3, 5, 6, 8).

[CPZ20] Melissa Chase, Trevor Perrin, and Greg Zaverucha. "The Signal Private Group System and Anonymous Credentials Supporting Efficient Verifiable Encryption." In: ACM CCS 2020. Ed. by Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna. ACM Press, Nov. 2020, pp. 1445–1459. doi: 10.1145/3372297.3417887 (cit. on p. 15).

[Dag+13] Özgür Dagdelen, Marc Fischlin, Tommaso Gagliardoni, Giorgia Azzurra Marson, Arno Mittelbach, and Cristina Onete. "A Cryptographic Analysis of OPACITY - (Extended Abstract)." In: ESORICS 2013. Ed. by Jason Crampton, Sushil Jajodia, and Keith Mayes. Vol. 8134. LNCS. Springer, Berlin, Heidelberg, Sept. 2013, pp. 345–362. doi: 10.1007/978-3-642-40203-6_20 (cit. on p. 3).

[DGK06] Mario Di Raimondo, Rosario Gennaro, and Hugo Krawczyk. "Deniable authentication and key exchange." In: ACM CCS 2006. Ed. by Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati. ACM Press, Oct. 2006, pp. 400–409. doi: 10.1145/1180405.1180454 (cit. on pp. 3, 5, 7, 8).

[DMS04] Roger Dingledine, Nick Mathewson, and Paul F. Syverson. "Tor: The Second-Generation Onion Router." In: USENIX Security 2004. Ed. by Matt Blaze. USENIX Association, Aug. 2004, pp. 303–320. doi: 10.21236/ada465464. url: http://www.usenix.org/publications/library/proceedings/sec04/tech/dingledine.html (cit. on p. 6).

[DNS98] Cynthia Dwork, Moni Naor, and Amit Sahai. "Concurrent Zero-Knowledge." In: 30th ACM STOC. ACM Press, May 1998, pp. 409–418. doi: 10.1145/276698.276853 (cit. on p. 8).

[DP15] Léo Ducas and Thomas Prest. Fast Fourier Orthogonalization. Cryptology ePrint Archive, Report 2015/1014. 2015. url: https://eprint.iacr.org/2015/1014 (cit. on p. 46).

[Dwo+06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. "Calibrating Noise to Sensitivity in Private Data Analysis." In: TCC 2006. Ed. by Shai Halevi and Tal Rabin. Vol. 3876. LNCS. Springer, Berlin, Heidelberg, Mar. 2006, pp. 265–284. doi: 10.1007/11681878_14 (cit. on pp. 4, 8).

[Esp+22] Thomas Espitau, Pierre-Alain Fouque, François Gérard, Mélissa Rossi, Akira Takahashi, Mehdi Tibouchi, Alexandre Wallet, and Yang Yu. "Mitaka: A Simpler, Parallelizable, Maskable Variant of Falcon." In: EUROCRYPT 2022, Part III. Ed. by Orr Dunkelman and Stefan Dziembowski. Vol. 13277. LNCS. Springer, Cham, May 2022, pp. 222–253. doi: 10.1007/978-3-031-07082-2_9 (cit. on pp. 19, 22).
[Esp+23] Thomas Espitau, Thi Thu Quyen Nguyen, Chao Sun, Mehdi Tibouchi, and Alexandre Wallet. "Antrag: Annular NTRU Trapdoor Generation - Making Mitaka as Secure as Falcon." In: *ASIACRYPT 2023, Part VII*. Ed. by Jian Guo and Ron Steinfeld. Vol. 14444. LNCS. Springer, Singapore, Dec. 2023, pp. 3–36. doi: 10.1007/978-981-99-8739-9_1 (cit. on pp. 19, 22).

[FG25] Rune Fiedler and Felix Günther. "Security Analysis of Signal's PQXDH Handshake." In: *PKC 2025, Part II*. Ed. by Tibor Jager and Jiaxin Pan. Vol. 15675. LNCS. Springer, Cham, May 2025, pp. 137–169. doi: 10.1007/978-3-031-91823-0_5 (cit. on p. 5).

[FJ24] Rune Fiedler and Christian Janson. "A Deniability Analysis of Signal's Initial Handshake PQXDH." In: *Proceedings on Privacy Enhancing Technologies 2024* (Oct. 2024), pp. 907–928. doi: 10.56553/popets-2024-0148 (cit. on pp. 3, 5, 6, 8).

[FL25] Rune Fiedler and Roman Langrehr. "On Deniable Authentication against Malicious Verifiers." In: *To appear in proceedings of CRYPTO 2025: 45th Annual International Cryptology Conference, Santa Barbara, CA, USA*. Santa Barbara, CA, USA, 2025 (cit. on pp. 4, 5, 23).

[Gen+20] Nicholas Genise, Daniele Micciancio, Chris Peikert, and Michael Walter. "Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography." In: *PKC 2020, Part I*. Ed. by Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas. Vol. 12110. LNCS. Springer, Cham, May 2020, pp. 623–651. doi: 10.1007/978-3-030-45374-9_21 (cit. on p. 48).

[GHJ25] Phillip Gajland, Vincent Hwang, and Jonas Janneck. *Shadowfax: A Deniability-Preserving AKEM Combiner*. Cryptology ePrint Archive, Paper 2025/154. 2025. URL: https://eprint.iacr.org/2025/154 (cit. on p. 21).

[GJK24a] Phillip Gajland, Jonas Janneck, and Eike Kiltz. *A Closer Look at Falcon*. Cryptology ePrint Archive, Paper 2024/1769. 2024. URL: https://eprint.iacr.org/2024/1769 (cit. on pp. 19, 45, 49, 50).

[GJK24b] Phillip Gajland, Jonas Janneck, and Eike Kiltz. "Ring Signatures for Deniable AKEM: Gandalf's Fellowship." In: *CRYPTO 2024, Part I*. Ed. by Leonid Reyzin and Douglas Stebila. Vol. 14920. LNCS. Springer, Cham, Aug. 2024, pp. 305–338. doi: 10.1007/978-3-031-68376-3_10 (cit. on pp. 4, 19–22).

[Goo22] Google. *Messages End-to-End Encryption Overview*. Technical paper. Feb. 2022. URL: https://www.gstatic.com/messages/papers/messages_e2ee.pdf (cit. on p. 3).

[GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. "Trapdoors for hard lattices and new cryptographic constructions." In: *40th ACM STOC*. Ed. by Richard E. Ladner and Cynthia Dwork. ACM Press, May 2008, pp. 197–206. doi: 10.1145/1374376.1374407 (cit. on p. 50).

[Has+21] Keitaro Hashimoto, Shuichi Katsumata, Kris Kwiatkowski, and Thomas Prest. "An Efficient and Generic Construction for Signal's Handshake (X3DH): Post-Quantum, State Leakage Secure, and Deniable." In: *PKC 2021, Part II*. Ed. by Juan Garay. Vol. 12711. LNCS. Springer, Cham, May 2021, pp. 410–440. doi: 10.1007/978-3-030-75248-4_15 (cit. on pp. 4, 6, 15, 18, 42).

[Has+22] Keitaro Hashimoto, Shuichi Katsumata, Kris Kwiatkowski, and Thomas Prest. "An Efficient and Generic Construction for Signal's Handshake (X3DH): Post-quantum, State Leakage Secure, and Deniable." In: *Journal of Cryptology* 35.3 (July 2022), p. 17. doi: 10.1007/s00145-022-09427-1 (cit. on pp. 3, 5, 6, 8, 15, 42).

[HKP22] Keitaro Hashimoto, Shuichi Katsumata, and Thomas Prest. "How to Hide MetaData in MLS-Like Secure Group Messaging: Simple, Modular, and Post-Quantum." In: *ACM CCS 2022*. Ed. by Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi. ACM Press, Nov. 2022, pp. 1399–1412. doi: 10.1145/3548606.3560679 (cit. on p. 6).

[HKW25] Keitaro Hashimoto, Shuichi Katsumata, and Thom Wiggers. "Bundled Authenticated Key Exchange: A Concrete Treatment of (Post-Quantum) Signal's Handshake Protocol." In: *USENIX Security 2025*. to appear. USENIX, Jan. 13, 2025. URL: https://eprint.iacr.org/2025/040 (cit. on pp. 1, 3–6, 12–16, 21, 22, 42).

[How+20] James Howe, Thomas Prest, Thomas Ricosset, and Mélissa Rossi. "Isochronous Gaussian Sampling: From Inception to Implementation." In: *Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020*. Ed. by Jintai Ding and Jean-Pierre Tillich. Springer, Cham, Apr. 2020, pp. 53–71. doi: 10.1007/978-3-030-44223-1_4 (cit. on p. 47).

[Ica09] Thomas Icart. "How to Hash into Elliptic Curves." In: *CRYPTO 2009*. Ed. by Shai Halevi. Vol. 5677. LNCS. Springer, Berlin, Heidelberg, Aug. 2009, pp. 303–316. doi: 10.1007/978-3-642-03356-8_18 (cit. on p. 30).

[Jia+22] Shaoquan Jiang, Yeow Meng Chee, San Ling, Huaxiong Wang, and Chaoping Xing. "A new framework for deniable secure key exchange." In: *Inf. Comput.* 285.PB (May 2022). ISSN: 0890-5401. doi: 10.1016/j.ic.2022.104866. URL: https://doi.org/10.1016/j.ic.2022.104866 (cit. on p. 8).
[JSH24] Kee Jefferys, Maxim Shishmarev, and Simon Harman. *Session: End-To-End Encrypted Conversations With Minimal Metadata Leakage*. Tech. rep. Session, July 2024 (cit. on p. 6).

[KP05] Caroline Kudla and Kenneth G. Paterson. "Modular Security Proofs for Key Agreement Protocols." In: *ASI-ACRYPT 2005*. Ed. by Bimal K. Roy. Vol. 3788. LNCS. Springer, Berlin, Heidelberg, Dec. 2005, pp. 549–565. DOI: 10.1007/11593447_30 (cit. on pp. 3, 12).

[KS23] Ehren Kret and Rolfe Schmidt. *The PQXDH Key Agreement Protocol*. Protocol documentation. Oct. 18, 2023. URL: https://signal.org/docs/specifications/pqxdh/ (cit. on pp. 3, 5, 6).

[LAZ19a] Xingye Lu, Man Ho Au, and Zhenfei Zhang. (*Linkable*) Ring Signature from Hash-Then-One-Way Signature. Cryptology ePrint Archive, Report 2019/567. 2019. URL: https://eprint.iacr.org/2019/567 (cit. on p. 50).

[LAZ19b] Xingye Lu, Man Ho Au, and Zhenfei Zhang. "Raptor: A Practical Lattice-Based (Linkable) Ring Signature." In: *ACNS 2019*. Ed. by Robert H. Deng, Valérie Gauthier-Umaña, Martín Ochoa, and Moti Yung. Vol. 11464. LNCS. Springer, Cham, June 2019, pp. 110–130. DOI: 10.1007/978-3-030-21568-2_6 (cit. on pp. 4, 19, 21, 23).

[LPS23] Helger Lipmaa, Roberto Parisella, and Janno Siim. "Algebraic Group Model with Oblivious Sampling." In: *TCC 2023, Part IV*. Ed. by Guy N. Rothblum and Hoeteck Wee. Vol. 14372. LNCS. Springer, Cham, Nov. 2023, pp. 363–392. DOI: 10.1007/978-3-031-48624-1_14 (cit. on p. 30).

[Lun18] Joshua Lund. *Technology preview: Sealed sender for Signal*. Oct. 2018. URL: https://signal.org/blog/sealed-sender/ (cit. on p. 6).

[Lyu12] Vadim Lyubashevsky. "Lattice Signatures without Trapdoors." In: *EUROCRYPT 2012*. Ed. by David Pointcheval and Thomas Johansson. Vol. 7237. LNCS. Springer, Berlin, Heidelberg, Apr. 2012, pp. 738–755. DOI: 10.1007/978-3-642-29011-4_43 (cit. on pp. 47, 48, 50).

[Mad+22] Varun Madathil, Alessandra Scafuro, István András Seres, Omer Shlomovits, and Denis Varlakov. "Private Signaling." In: *USENIX Security 2022*. Ed. by Kevin R. B. Butler and Kurt Thomas. USENIX Association, Aug. 2022, pp. 3309–3326. URL: https://www.usenix.org/conference/usenixsecurity22/presentation/madathil (cit. on p. 6).

[Mer87] Ralph C. Merkle. "A Digital Signature Based on a Conventional Encryption Function." In: *CRYPTO '87*. Ed. by Carl Pomerance. Vol. 293. LNCS. Springer, Berlin, Heidelberg, Aug. 1987, pp. 369–378. DOI: 10.1007/3-540-48184-2_32 (cit. on p. 29).

[Met23] Meta, Inc. *Messenger End-to-End Encryption Overview*. Technical white paper. Dec. 6, 2023. URL: https://engineering.fb.com/wp-content/uploads/2023/12/MessengerEnd-to-EndEncryptionOverview_12-6-2023.pdf (cit. on p. 3).

[Mir+09] Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil P. Vadhan. "Computational Differential Privacy." In: *CRYPTO 2009*. Ed. by Shai Halevi. Vol. 5677. LNCS. Springer, Berlin, Heidelberg, Aug. 2009, pp. 126–142. DOI: 10.1007/978-3-642-03356-8_8 (cit. on pp. 4, 8).

[MP16] Moxie Marlinspike and Trevor Perrin. *The X3DH Key Agreement Protocol*. Protocol documentation. Nov. 4, 2016. URL: https://signal.org/docs/specifications/x3dh/ (cit. on pp. 3, 5, 6, 12).

[MR04] Daniele Micciancio and Oded Regev. "Worst-Case to Average-Case Reductions Based on Gaussian Measures." In: *45th FOCS*. IEEE Computer Society Press, Oct. 2004, pp. 372–381. DOI: 10.1109/FOCS.2004.72 (cit. on p. 48).

[Nik+19] Kirill Nikitin, Ludovic Barman, Wouter Lueks, Matthew Underwood, Jean-Pierre Hubaux, and Bryan Ford. "Reducing Metadata Leakage from Encrypted Files and Communication with PURBs." In: *PoPETs 2019.4* (Oct. 2019), pp. 6–33. DOI: 10.2478/popets-2019-0056 (cit. on p. 6).

[Nio25] Guilhem Niot. *Practical Deniable Post-Quantum X3DH: A Lightweight Split-KEM for K-Waay*. Cryptology ePrint Archive, Paper 2025/853. 2025. URL: https://eprint.iacr.org/2025/853 (cit. on p. 5).

[Pas03] Rafael Pass. "On Deniability in the Common Reference String and Random Oracle Model." In: *CRYPTO 2003*. Ed. by Dan Boneh. Vol. 2729. LNCS. Springer, Berlin, Heidelberg, Aug. 2003, pp. 316–337. DOI: 10.1007/978-3-540-45146-4_19 (cit. on pp. 8, 15).

[Per16] Trevor Perrin. *The XEdDSA and VXEdDSA Signature Schemes*. documentation. Oct. 20, 2016. URL: https://signal.org/docs/specifications/xeddsa/ (cit. on p. 22).

[PH10] A Pfitzmann and Marit Hansen. "A terminology for talking about privacy by data minimization: Anonymity, Unlinkability, Undetectability, Unobservability, Pseudonymity, and Identity Management." In: *34 (Jan. 2010)*. URL: http://dud.inf.tu-dresden.de/literatur/Anon_Terminology_v0 (cit. on p. 6).
[PM16] Trevor Perrin and Moxie Marlinspike. *The Double Ratchet Algorithm*. Protocol documentation. Nov. 20, 2016. URL: https://signal.org/docs/specifications/doubleratchet/ (cit. on p. 3).

[Pre15] Thomas Prest. "Gaussian sampling in lattice-based cryptography." Theses. Ecole normale supérieure - ENS PARIS, Dec. 2015. URL: https://theses.hal.science/tel-01245066 (cit. on pp. 46, 48).

[Pre17] Thomas Prest. "Sharper Bounds in Lattice-Based Cryptography Using the Rényi Divergence." In: *ASI-ACRYPT 2017, Part I*. Ed. by Tsuyoshi Takagi and Thomas Peyrin. Vol. 10624. LNCS. Springer, Cham, Dec. 2017, pp. 347-374. DOI: 10.1007/978-3-319-70694-8_13 (cit. on pp. 47, 48).

[Pre+22] Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. *FALCON*. Tech. rep. available at https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022. National Institute of Standards and Technology, 2022 (cit. on pp. 4, 9, 16, 19, 22, 49).

[Sho97] Victor Shoup. "Lower Bounds for Discrete Logarithms and Related Problems." In: *EUROCRYPT'97*. Ed. by Walter Fumy. Vol. 1233. LNCS. Springer, Berlin, Heidelberg, May 1997, pp. 256-266. DOI: 10.1007/3-540-69053-0_18 (cit. on pp. 15, 30).

[SV16] Igal Sason and Sergio Verdú. "f-Divergence Inequalities." In: *IEEE Transactions on Information Theory* 62.11 (2016), pp. 5973-6006. DOI: 10.1109/TIT.2016.2603151 (cit. on pp. 4, 9).

[TWG24] Elkana Tovey, Jonathan Weiss, and Yossi Gilad. "Distributed PIR: Scaling Private Messaging via the Users' Machines." In: *ACM CCS 2024*. Ed. by Bo Luo, Xiaojing Liao, Jun Xu, Engin Kirda, and David Lie. ACM Press, Oct. 2024, pp. 1967-1981. DOI: 10.1145/3658644.3670350 (cit. on p. 6).

[UG15] Nik Unger and Ian Goldberg. "Deniable Key Exchanges for Secure Messaging." In: *ACM CCS 2015*. Ed. by Indrajit Ray, Ninghui Li, and Christopher Kruegel. ACM Press, Oct. 2015, pp. 1211-1223. DOI: 10.1145/2810103.2813616 (cit. on p. 3).

[UG18] Nik Unger and Ian Goldberg. "Improved Strongly Deniable Authenticated Key Exchanges for Secure Messaging." In: *PoPETs* 2018.1 (Jan. 2018), pp. 21-66. DOI: 10.1515/popets-2018-0003 (cit. on p. 3).

[Ung+15] Nik Unger, Sergej Dechand, Joseph Bonneau, Sascha Fahl, Henning Perl, Ian Goldberg, and Matthew Smith. "SoK: Secure Messaging." In: *2015 IEEE Symposium on Security and Privacy*. IEEE Computer Society Press, May 2015, pp. 232-249. DOI: 10.1109/SP.2015.22 (cit. on pp. 6, 7).

[Vat+20] Nihal Vatandas, Rosario Gennaro, Bertrand Ithurburn, and Hugo Krawczyk. "On the Cryptographic Deniability of the Signal Protocol." In: *ACNS 2020, Part II*. Ed. by Mauro Conti, Jianying Zhou, Emiliano Casalicchio, and Angelo Spognardi. Vol. 12147. LNCS. Springer, Cham, Oct. 2020, pp. 188-209. DOI: 10.1007/978-3-030-57878-7_10 (cit. on pp. 3, 5-8).

[WB19] Riad S. Wahby and Dan Boneh. "Fast and simple constant-time hashing to the BLS12-381 elliptic curve." In: *IACR TCHES* 2019.4 (2019), pp. 154-179. ISSN: 2569-2925. DOI: 10.13154/tches.v2019.i4.154-179. URL: https://tches.iacr.org/index.php/TCHES/article/view/8348 (cit. on p. 30).

[Wha23] WhatsApp. *WhatsApp Encryption Overview*. Technical white paper. Sept. 27, 2023. URL: https://www.whatsapp.com/security/WhatsApp-Security-Whitepaper.pdf (cit. on p. 3).

[Yue+21] Tsz Hon Yuen, Muhammed F. Esgin, Joseph K. Liu, Man Ho Au, and Zhimin Ding. "DualRing: Generic Construction of Ring Signatures with Efficient Instantiations." In: *CRYPTO 2021, Part I*. Ed. by Tal Malkin and Chris Peikert. Vol. 12825. LNCS. Virtual Event: Springer, Cham, Aug. 2021, pp. 251-281. DOI: 10.1007/978-3-030-84242-0_10 (cit. on p. 21).

[Zha22] Mark Zhandry. "To Label, or Not To Label (in Generic Groups)." In: *CRYPTO 2022, Part III*. Ed. by Yevgeniy Dodis and Thomas Shrimpton. Vol. 13509. LNCS. Springer, Cham, Aug. 2022, pp. 66-96. DOI: 10.1007/978-3-031-15982-4_3 (cit. on p. 30).

# A. Basic Building Blocks

In this section, we provide definitions of basic cryptographic building blocks used to construct Signal handshake protocols.

## A.1. Symmetric Key Encryption

We review the definition of symmetric key encryption (SKE).

**Definition 10 (Symmetric Key Encryption).** A symmetric key encryption scheme SKE with secret key space $\mathcal{K}$ is given by two PPT algorithms SKE.Enc and SKE.Dec as follows:
SKE.Enc($K, m$) $\rightarrow$ ct: On input a secret key $K \in \mathcal{K}$ and a message $m$, outputs a ciphertext ct.

SKE.Dec($K, ct$) $\rightarrow$ $m/\perp$: On input a secret key $K$ and a ciphertext ct, outputs a message $m$ or $\perp$ indicating decryption failure.

**Definition 11 (Correctness).** An SKE is correct if for all $K \in \mathcal{K}$ and messages $m$, we have $\text{SKE.Dec}(K, \text{SKE.Enc}(K, m)) = m$.

**Definition 12 (IND-CPA Security).** We define the advantage of $\mathcal{A}$ against the IND-CPA security game as follows:

$$ \text{Adv}_{\text{SKE}, \mathcal{A}}^{\text{IND-CPA}}(1^{\lambda}) := \left| \Pr \left[ \begin{array}{l} b \stackrel{s}{\leftarrow} \{0, 1\} \\ K \stackrel{s}{\leftarrow} \mathcal{K}, \\ (m_0, m_1) \stackrel{s}{\leftarrow} \mathcal{A}(1^{\lambda}); \\ \text{ct} \stackrel{s}{\leftarrow} \text{Enc}(K, m_b), \\ b' \stackrel{s}{\leftarrow} \mathcal{A}(\text{ct}) \end{array} \right] - \frac{1}{2} \right| $$

An SKE is IND-CPA secure if the advantage is negligible for any efficient adversary $\mathcal{A}$.

We also require an SKE to be robust [ABN10], i.e., no ciphertext should validly decrypt under two distinct secret keys (even if the decryption results are distinct).

**Definition 13 (Robustness).** We define the advantage of $\mathcal{A}$ against the robustness game as follows:

$$ \text{Adv}_{\text{SKE}, \mathcal{A}}^{\text{Robust}}(1^{\lambda}) := \Pr \left[ \begin{array}{l} K \neq K' \\ \wedge \text{Dec}(K, \text{ct}) \neq \perp \\ \wedge \text{Dec}(K', \text{ct}) \neq \perp \end{array} \right] (\text{ct}, K, K') \stackrel{s}{\leftarrow} \mathcal{A}(1^{\lambda}) $$

An SKE is robust if the advantage is negligible for any efficient adversary $\mathcal{A}$.

## A.2. Key Encapsulation Mechanisms

We review the definition of key encapsulation mechanism (KEM).

**Definition 14 (KEM).** A key encapsulation mechanism scheme KEM with session key space $\mathcal{K}$ consists of three PPT algorithms (KEM.KeyGen, KEM.Encaps, KEM.Decaps), where:

KEM.KeyGen($1^{\lambda}$) $\xrightarrow{s}$ (ek, dk): On input the security parameter $1^{\lambda}$, outputs a pair of keys (ek, dk).

KEM.Encaps(ek) $\xrightarrow{s}$ (ss, ct): On input an encapsulation key ek, outputs a session key ss $\in \mathcal{K}$ and a ciphertext ct.

KEM.Decaps(dk, ct) $\rightarrow$ ss: On input a decapsulation key dk and a ciphertext ct, outputs a session key ss $\in \mathcal{K}$.

**Definition 15 (Correctness).** A KEM is correct if for all $\lambda \in \mathbb{N}$, it holds that $\Pr[\text{KEM.Decaps}(dk, ct) = ss] \ge 1 - \text{negl}(\lambda)$, where we have $(ek, dk) \xleftarrow{s} \text{KEM.KeyGen}(1^{\lambda})$ and $(ss, ct) \xleftarrow{s} \text{KEM.Encaps}(ek)$.

**Definition 16 (IND-ATK Security).** For $\text{ATK} \in \{\text{CPA, CCA}\}$, we define the advantage of $\mathcal{A}$ against the IND-ATK security game as follows:

$$ \text{Adv}_{\text{KEM}, \mathcal{A}}^{\text{IND-ATK}}(1^{\lambda}) := \left| \Pr \left[ \begin{array}{l} b \stackrel{s}{\leftarrow} \{0, 1\}, \\ (\text{ek}, \text{dk}) \stackrel{s}{\leftarrow} \text{KEM.KeyGen}(1^{\lambda}), \\ (\text{ss}_0, \text{ct}) \stackrel{s}{\leftarrow} \text{KEM.Encaps}(\text{ek}), \\ \text{ss}_1 \stackrel{s}{\leftarrow} \mathcal{K}, \\ b' \stackrel{s}{\leftarrow} \mathcal{A}^{\text{OATK}}(\text{ek}, \text{ss}_b, \text{ct}) \end{array} \right] - \frac{1}{2} \right| $$

where

$$ O_{\text{ATK}} = \begin{cases} \perp & \text{if } \text{ATK} = \text{CPA} \\ \text{KEM.Decaps(dk, \cdot)} & \text{if } \text{ATK} = \text{CCA} \end{cases} $$

When $\text{ATK} = \text{CCA}$, $\mathcal{A}$ is not allowed to query the challenge ciphertext ct to $O_{\text{CCA}}$. A KEM is IND-ATK secure if the advantage is negligible for any efficient adversary $\mathcal{A}$.

## A.3. Signature Schemes

We review the definition of digital signatures.

**Definition 17 (Signature Schemes).** A signature scheme with message space $\mathcal{M}$ consists of the following three PPT algorithms (Sig.KeyGen, Sig.Sign, Sig.Verify):

Sig.KeyGen($1^{\lambda}$) $\xrightarrow{s}$ (vk, sk): On input the security parameter $1^{\lambda}$, outputs a pair of keys (vk, sk).

Sig.Sign(sk, M) $\xrightarrow{\sigma}$: On input a signing key sk and a message $M \in \mathcal{M}$, outputs a signature $\sigma$.

Sig.Verify(vk, M, $\sigma$) $\rightarrow$ $\{0, 1\}$: On input a verification key vk, a message M and a signature $\sigma$, outputs a verification bit.
**Definition 18 (Correctness).** A signature scheme is correct if for all $\lambda \in \mathbb{N}$ and messages $M \in \mathcal{M}$, we have $\text{Sig}_\text{Verify}(vk, M, \sigma) = 1$, where $(vk, sk) \stackrel{\$}{\leftarrow} \text{Sig}_\text{KeyGen}(1^\lambda)$ and $\sigma \stackrel{\$}{\leftarrow} \text{Sig}_\text{Sign}(sk, M)$.

**Definition 19 (EUF-CMA Security).** We define the advantage of $\mathcal{A}$ against the EUF-CMA security game as follows:

$$ \text{Adv}_{\text{SIG}, \mathcal{A}}^{\text{EUF-CMA}}(1^{\lambda}) := \Pr \left[ \begin{array}{l} \text{Sig}_\text{Verify}(vk, M, \sigma) = 1 \\ \wedge M \notin \mathcal{L} \end{array} \middle| \begin{array}{l} (vk, sk) \stackrel{\$}{\leftarrow} \text{Sig}_\text{KeyGen}(1^{\lambda}); \\ (M, \sigma) \stackrel{\$}{\leftarrow} \mathcal{A}^{\text{Sign}(sk, \cdot)}(vk) \end{array} \right] $$

where $\mathcal{O}_{\text{Sign}}(\cdot) := \text{Sig}_\text{Sign}(sk, \cdot)$ is the signing oracle and $\mathcal{L}$ is the set of messages that $\mathcal{A}$ submitted to $\mathcal{O}_{\text{Sign}}$. A signature scheme is EUF-CMA-secure if the advantage is negligible for any efficient adversary $\mathcal{A}$.

## A.4. Ring Signature Schemes

We recall standard correctness and unforgeability definitions for ring signatures.

**Definition 20 (Correctness).** A ring signature is correct if for all $\lambda \in \mathbb{N}$, $N = \text{poly}(\lambda)$, $j \in [N]$, and message $M$, we have $\text{RS}_\text{Verify}(\text{RL}, M, \text{sig}) = 1$, where for $i \in [N]$, $(\text{rvk}_i, \text{rsk}_i) \stackrel{\$}{\leftarrow} \text{RS}_\text{KeyGen}(1^\lambda)$, $\text{RL} := \{\text{rvk}_1, \dots, \text{rvk}_N\}$, and $\text{sig} \stackrel{\$}{\leftarrow} \text{RS}_\text{Sign}(\text{rsk}_j, M, \text{RL})$.

**Definition 21 (Unforgeability).** We define the advantage of $\mathcal{A}$ against the unforgeability game as a game played between $\mathcal{A}$ and a challenger:

(i) The challenger generates key pairs $(\text{rvk}_i, \text{rsk}_i) \stackrel{\$}{\leftarrow} \text{RS}_\text{KeyGen}(1^\lambda)$ for $i \in [N]$. It sets $\text{VK} := (\text{rvk}_i)_{i \in [N]}$, initializes two empty sets SL and CL, and provides SL to $\mathcal{A}$;

(ii) $\mathcal{A}$ can make signing and corruption queries an arbitrary polynomial number of times:

* (sign, $i$, M, RL): The challenger checks if $\text{rvk}_i \in \text{RL}$, and if so, computes the signature with $\text{sig} \stackrel{\$}{\leftarrow} \text{RS}_\text{Sign}(\text{rsk}_i, M, RL)$. The challenger provides $\text{sig}$ to $\mathcal{A}$ and adds $(i, M, RL)$ to SL;

* (corrupt, $i$): The challenger adds $\text{rvk}_i$ to CL and returns $\text{rsk}_i$ to $\mathcal{A}$.

(iii) $\mathcal{A}$ outputs $(\text{RL}^*, \text{M}^*, \text{sig}^*)$. If $\text{RL}^* \in \text{VK} \setminus \text{CL}$, $(\cdot, \text{M}^*, \text{RL}^*) \notin \text{SL}$, and $\text{RS}_\text{Verify}(\text{RL}, M, \text{sig}) = 1$, then we say the adversary $\mathcal{A}$ wins.

The advantage of $\mathcal{A}$ is defined as $\text{Adv}_{\text{RS}, \mathcal{A}}^{\text{Unf}}(1^\lambda) = \text{Pr}[\mathcal{A} \text{ wins}]$. A ring signature scheme $\text{RS}$ is unforgeable if the advantage is negligible for any $N = \text{poly}(\lambda)$ and efficient adversary $\mathcal{A}$.

## A.5. Merkle Trees

A Merkle tree [Mer87] allows to prove membership in a set by hashing a list of elements $A = (a_0, \dots, a_N)$ into one hash value root. At a later point, one can efficiently prove to a third party that an element $a_i$ was included in the list $A$. We rely on a specific construction based on [BKP20] which allows us to hide the position in the list. Looking ahead, this allows us to hide the prekey bundle index being used, that is, to hide how many times a prekey bundle has been used.

**Definition 22.** A Merkle tree consists of PPT algorithms (MerkleTree, getMerklePath, ReconstructRoot) with access to a hash function $\mathcal{H}_{\text{Coll}}: \{0, 1\}^* \to \{0, 1\}^{2\lambda}$.

MerkleTree($A$) $\to$ (root, tree): On input a list of (at most) $2^k$ elements $A = (a_1, \dots, a_{2^k})$, with $k \in \mathbb{N}$, it constructs a binary tree of height $k$ with $\{\ell_i = \mathcal{H}_{\text{Coll}}(a_i)\}_{i \in [2^k]}$ as its leaf nodes, and where every internal node $h$ with children $h_{\text{left}}$ and $h_{\text{right}}$ equals the hash digest of $(h_{\text{left}}, h_{\text{right}})_{\text{lex}}$, where the subscript lex indicates the lexicographical order (or any other total order on binary strings).$^{15}$ It then outputs the root root of the Merkle tree, as well as a description of the entire tree tree.

getMerklePath(tree, $i$) $\to$ path: On input the description of a Merkle tree tree and an index $i \in [2^k]$, it outputs the list path, which contains the sibling of $\ell_i$, as well as the sibling of any ancestor of $\ell_i$, ordered by decreasing height.

ReconstructRoot($a$, path) $\to$ root: On input an element $a$ in the list of elements $A = (a_1, \dots, a_{2^k})$ and path $= (n_1, \dots, n_k)$, it outputs a reconstructed root $\text{root}' = h_k$, which is calculated by putting $h_0 = \mathcal{H}_{\text{Coll}}(a)$ and defining $h_i$ for $i \in [k]$ recursively as $h_i = \mathcal{H}_{\text{Coll}}((h_{i-1}, n_i)_{\text{lex}})$.

If the hash function $\mathcal{H}_{\text{Coll}}$ that is used in the Merkle tree is collision resistant, then we have that the Merkle tree construction is binding. Formally, we have the following.

**Lemma 1 (Binding).** There is an efficient extractor algorithm that, given the description tree of a Merkle tree (having root root and constructed using the list of elements $A$) and $(b, \text{path})$ such that $b \notin A$ and ReconstructRoot($b, \text{path}$) = root, outputs a collision for the hash function $\mathcal{H}_{\text{Coll}}$.

Lastly, the use of the lexicographical order to concatenate two children nodes in the Merkle tree construction implies that the output path of the algorithm getMerklePath hides the index $i \in [N]$ given as input. As we do not formally use this in our work, we refer to [BKP20, Lemma 2.10] for more details.

<footnote>$^{15}$While it is standard to consider the concatenation $h_{\text{left}}||h_{\text{right}}$, this slight modification allows to show index hiding (cf. [BKP20, Lemma 2.10]).</footnote>
# B. Cryptographic Models

In this section, we give some details on cryptographic models used in proofs, namely the generic group model and the quantum random oracle model.

## B.1. Generic Group Model with Oblivious Sampling

We recall the generic group model (GGM) by Shoup [Sho97] (i.e., random representation model) using the notations from Zhandry [Zha22]. Moreover, we extend the GGM with oblivious sampling following [LPS23]. This allows us to model adversaries that may sample group elements without knowing the corresponding discrete log.

Let $S \subset \{0, 1\}^*$ be a set of strings of cardinality at least $p \in \mathbb{N}$. Let $\Xi: \mathbb{Z}_p \to S$ be a random injective function called the labeling function. Let $D: \mathbb{Z}_p \to \{0, 1\}$ be an arbitrary efficiently sampleable distribution. All parties, including the adversary, the challenger, and subalgorithms, are able to make the following queries:

**Labeling queries** On input $x \in \mathbb{Z}_p$ from a party, it outputs the string $\Xi(x) \in S$.

**Group operations** On input $(s_1, s_2, a_1, a_2) \in S^2 \times \mathbb{Z}_p^2$ from a party, it first checks if there exists $x_1, x_2 \in \mathbb{Z}_p$ such that $\Xi(x_1) = s_1$ and $\Xi(x_2) = s_2$. If not it outputs $\perp$. Otherwise, it outputs $\Xi(a_1x_1 + a_2x_2) \in S$.

**Oblivious sampling** On invocation, it samples $x \stackrel{s}{\leftarrow} D$ and outputs $\Xi(x) \in S$.

All queries are assumed to have unit costs. Above, $\Xi(x)$ represents $g^x$ in the real world, where $g$ is a fixed generator of the group. For instance, given $s = \Xi(x)$, a party can compute the representation of $g^{ax}$ for some $a \in \mathbb{Z}_p$, by querying $(s, s, a/2, a/2)$ to the group operation oracle. For simplicity, we sometimes simply write that a party performs a group operation oracle query on input $(s, a)$. Lastly, $D$ allows us to model the party's knowledge of the exponent for an obliviously sampled group element. In this paper, for simplicity, we always assume $D$ is the uniform distribution over $\mathbb{Z}_p$. However, in general, we only require $D$ to be some distribution over $\mathbb{Z}_p$ with sufficient min-entropy.

Admissible encodings are one approach to oblivious sampling. They are efficiently computable functions $E$ from $\mathbb{Z}_p$ to elliptic curve groups that are regular (small preimage sizes) and preimage sampleable (given an element in the image of $E$, one can efficiently recover its whole preimage). Concrete constructions for admissible encodings are given in e.g. [BF01; Ica09; WB19].

## B.2. Quantum Random Oracle Model

We recall the result by Ambainis, Hamburg, and Unruh [AHU19]. As in the classical setting, it allows us to argue that if a reduction programs the (quantum) random oracle on a sufficiently random point, then an adversary learns nothing about the programmed point.

**Definition 23 (Punctured oracle).** Let $S \subset \mathcal{X}$ be a set. Let $f_S: \mathcal{X} \to \{0, 1\}$ be a predicate that returns 1 if and only if $x \in S$. A punctured oracle $H \setminus S$ of $H: \mathcal{X} \to \mathcal{Y}$ runs as follows: on input $x$, computes whether $x \in S$ in an auxiliary qubit, measures it, runs $H(x)$, and returns the result. Let FIND denote the event that any of the measurement returns 1.

**Lemma 2 (Semi-classical OW2H).** Let $\mathcal{G}, \mathcal{H}: \mathcal{X} \to \mathcal{Y}$ be random functions, let $z$ be a random value, and let $S \subset \mathcal{X}$ be a random set such that $\forall x \notin S, \mathcal{G}(x) = \mathcal{H}(x)$. ($\mathcal{G}, \mathcal{H}, S, z$) may have arbitrary joint distribution. Then, for all quantum algorithms $\mathcal{A}$ on input $z$ issuing at most $q$ oracle queries, output either 0 or 1 with the following guarantee:

$$ \left| \Pr[1 \stackrel{s}{\leftarrow} \mathcal{A}^{[\mathcal{G}\rangle}(z)] - \Pr[1 \stackrel{s}{\leftarrow} \mathcal{A}^{[\mathcal{H}\rangle}(z)] \right| \le 2 \cdot \sqrt{q \cdot \Pr[\text{FIND} \mid b \stackrel{s}{\leftarrow} \mathcal{A}^{[\mathcal{G}\setminus S\rangle}(z)]}. \quad (1) $$

In particular, if for each $x \in \mathcal{X}$, $\Pr[x \in S] \le \epsilon$ (conditioned on $z$, on other oracles $\mathcal{A}$ has access to, and on other outputs of $H$), then we have

$$ \Pr[\text{FIND} \mid b \stackrel{s}{\leftarrow} \mathcal{A}^{[\mathcal{G}\setminus S\rangle}(z)] \le 4q \cdot \epsilon. $$

# C. Combinations of Leakage and Disclosure

Table 8 depicts the combinations of leakage and disclosure which we consider.
<table><caption>Table 8: Secret information available to the distinguishing judge. $\mathcal{H}$ and $\mathcal{C}$ denote the accused and (honest-but-curious) accusing users, respectively.</caption><thead><tr><th>$\mathcal{L}_{\text{leak}}$<br>for $h$ in $\mathcal{H}$</th><th>$\mathcal{D}_{\text{disc}}$<br>for $c$ in $\mathcal{C}$</th><th>leak disc</th><th>The judge gets:</th></tr></thead><tbody><tr><td>(⊥, ⊥) (isk<sub>c</sub>, st<sub>c</sub>, st<sub>c</sub><sup>init</sup>)</td><td>⊥</td><td>high</td><td>No information from accused users.<br>All accuser secrets, including initial state.</td></tr><tr><td>(isk<sub>h</sub>, ⊥) (isk<sub>c</sub>, st<sub>c</sub>, st<sub>c</sub><sup>init</sup>)</td><td>med</td><td>high</td><td>Accused users identity secret key.<br>All accuser secrets, including initial state.</td></tr><tr><td>(isk<sub>h</sub>, st<sub>h</sub>) (isk<sub>c</sub>, st<sub>c</sub>, st<sub>c</sub><sup>init</sup>)</td><td>high</td><td>high</td><td>Accused users identity secret key and state.<br>All accuser secrets, including initial state.</td></tr><tr><td>(isk<sub>h</sub>, ⊥) (isk<sub>c</sub>, ⊥, ⊥)</td><td>med</td><td>low</td><td>Identity secret key of all users.</td></tr><tr><td>(isk<sub>h</sub>, st<sub>h</sub>) (isk<sub>c</sub>, st<sub>c</sub>, ⊥)</td><td>high</td><td>med</td><td>Identity secret key and states of all users.</td></tr></tbody></table>

## D. Strong Implies Standard Deniability

In this section, we demonstrate that, as one would expect, deniability against malicious adversaries implies deniability against honest but curious adversaries.

**Lemma 3** (Strong Local Deniability $\Rightarrow$ (Standard) Local Deniability). If a two-round bundled authenticated key exchange protocol BAKE is strongly local deniable for accused users $\mathcal{H} \subseteq \mathcal{N}$ against malicious accusers $\mathcal{C} := \mathcal{N} \setminus \mathcal{H}$ with respect to a leakage function $\mathcal{L}_{\text{leak}}$ with $\text{leak} \in \{\text{low}, \text{med}, \text{high}\}$, then it is locally deniable for accused users $\mathcal{H}$ against honest-but-curious accusers $\mathcal{C}$ for the same leakage function $\mathcal{L}_{\text{leak}}$, and for any disclosure function $\mathcal{D}_{\text{disc}}$.

*Proof.* We will prove this by contradiction. The intuition of the proof is as follows: we show that we can construct an accuser for the malicious security game that is equivalent to the local honest security game. If this accuser has negligible advantage, no accuser can exist that has non-negligible advantage in the local honest security game.

We assume BAKE is not (standard) local deniable for accused users $\mathcal{H}$ for some leakage function $\mathcal{L}_{\text{leak}}$ with $\text{leak} \in \{\text{low}, \text{med}, \text{high}\}$ and for any disclosure function $\mathcal{D}_{\text{disc}}$. That is, for any simulator $\text{Sim} = (\text{SimPreK}, \text{SimTrans})$, there exists a distinguisher D for which $\text{Adv}_{\mathcal{D}, \mathcal{H}, \mathcal{L}_{\text{leak}}, \mathcal{D}_{\text{disc}}}(1^\lambda)$ is non-negligible.

Let us now describe an accuser $\mathcal{A}$ for the strong deniability game. If mode = real, then, on input $((\text{isk}_u)_{u \in \mathcal{N}}, (\text{isk}_u)_{u \in \mathcal{C}}, (\text{prek}_u)_{u \in \mathcal{H}}, \text{st}_\mathcal{A}))$, $\mathcal{A}$ runs the honest prekey generation algorithm $(\text{prek}_u, \text{st}_u) \stackrel{\$}{\leftarrow} \text{BAKE.PreKeyBundleGen}(\text{isk}_u)$ for all $u \in \mathcal{C}$ and outputs $((\text{prek}_u)_{u \in \mathcal{C}}, \text{st}_\mathcal{A}) := (\text{isk}_u, \text{st}_u^{\text{init}} := \text{st}_u)_{u \in \mathcal{C}})$. When $\mathcal{A}$ is invoked within oracle $\mathcal{O}_{\text{strong-local}}(s, r)$ for $(s, r) \in \mathcal{N} \times \mathcal{H}$, it executes $(\mathcal{K}, \rho) \stackrel{\$}{\leftarrow} \text{BAKE Send}(\text{isk}_s, \text{ik}_r, \text{prek}_{r,t})$, where note that this is well-defined as we have $\text{isk}_s \in \text{st}_\mathcal{A}$. The accuser then outputs $(\rho, \text{st}_\mathcal{A})$.

For the sake of contradiction, let us assume an arbitrary simulator $\text{Sim}_\mathcal{A} = (\text{SimPreK}_\mathcal{A}, \text{SimTrans}_\mathcal{A})$ for the malicious deniability game, and that, for any distinguisher $D'$, $\text{Adv}_{D', \mathcal{L}_{\text{leak}}}(1^\lambda)$ is negligible. Due to the way we defined the accuser $\mathcal{A}$ (namely to honestly execute the protocol), $\text{Sim}_\mathcal{A}$ can be viewed as a simulator $\text{Sim}$ against the local honest deniability game. Moreover, the information leaked from accused users by $\mathcal{L}_{\text{leak}}$ is the same in both games, while the information disclosed by $\mathcal{A}$ to $D'$ in $\text{st}_\mathcal{A}$ contains (at least) the information output by $\mathcal{D}_{\text{disc}}$ for the corresponding disc $\in \{\text{low}, \text{med}, \text{high}\}$.

Even in the most restricted leakage setting, the distinguisher $D'$ in the local malicious deniability game obtains $\text{st}_\mathcal{A} = (\text{isk}_u, \text{st}_u^{\text{init}})_{u \in \mathcal{C}}$. Therefore, if any $D'$ has negligible advantage given the output of $\mathcal{L}_{\text{leak}}$, so does any $D'$ against the local honest deniability game given the output of $\mathcal{L}_{\text{leak}}$. However, this contradicts our assumption made at start of the proof, completing the proof. □

## E. Proof of Deniability of X3DH and PQXDH

In this section, we provide the proofs of varying levels of deniability attained by the X3DH and PQXDH protocols.

### E.1. Local Deniability of X3DH and PQXDH

We prove that X3DH is locally deniable against honest-but-curious accusers (i.e., those who follow the protocol description) even if the distinguisher obtains all secret information of the users.

**Lemma 4.** The X3DH protocol is locally deniable with respect to leakage function $\mathcal{L}_{\text{high}}$, and disclosure function $\mathcal{D}_{\text{high}}$.
*Proof.* Let us first define the simulator $Sim = (SimPreK, SimTrans, SimSt_H, SimSt_C)$:

SimPreK: $(\mathbf{ik}_u)_{u \in \mathcal{N}}, (\mathbf{isk}_u)_{u \in \mathcal{C}}, (\mathbf{prek}_u)_{u \in \mathcal{H}}$: For $u \in \mathcal{C}$, run $(\mathbf{prek}_u, \mathbf{st}_u) \leftarrow X3DH$. PreKeyBundleGen($\mathbf{isk}_u$), and output $((\mathbf{prek}_u)_{u \in \mathcal{H}}, ((\mathbf{prek}_u, \mathbf{st}_u))_{u \in \mathcal{C}}, \mathbf{st}_{Sim})$ with $\mathbf{st}_{Sim} = ((\mathbf{ik}_u, \mathbf{prek}_u)_{u \in \mathcal{N}}, (\mathbf{isk}_u, \mathbf{st}_u)_{u \in \mathcal{C}})$. Below, for simplicity, we assume the simulator $Sim$ always extracts the necessary public information from its state $\mathbf{st}_{Sim}$.

SimTrans($\mathbf{isk}, \mathbf{st}_{Sim}, (s, r, t)$): Here, recall $\mathbf{isk}$ is either $\mathbf{isk}_s$, $\mathbf{isk}_r$, or $\perp$ depending on $s \in \mathcal{C}$, $r \in \mathcal{C}$, or $(s, r) \in \mathcal{H} \times \mathcal{H}$, respectively.

If $(s, r) \in \mathcal{H} \times \mathcal{C}$: First sample $\mathbf{esk} \stackrel{s}{\leftarrow} \mathbb{Z}_p$ and set $\mathbf{epk} := [\mathbf{esk}]G$. Then extract the signed prekey secret $\mathbf{spksec}_r$ from $\mathbf{st}_r \in \mathbf{st}_{Sim}$, and compute

$$ (\mathbf{ss}_1, \mathbf{ss}_2, \mathbf{ss}_3, \mathbf{ss}_4) := ([\mathbf{spksec}_r] \bar{\mathbf{ik}}_s, [\mathbf{esk}] \bar{\mathbf{ik}}_r, [\mathbf{esk}] \mathbf{spk}_r, [\mathbf{esk}] \mathbf{opk}_{r,t}), $$

where note that such $\mathbf{st}_r$ exists as $r \in \mathcal{C}$. Finally, compute Alg. 5, Lns. 16 to 18 and output $(K, \rho)$.

If $(s, r) \in \mathcal{C} \times \mathcal{H}$: Simply run $(K, \rho) \stackrel{s}{\leftarrow} X3DH Send(\mathbf{isk}_s, \mathbf{ik}_r, \mathbf{prek}_{r,t})$, and output $(K, \rho)$.

SimSt_H($\mathbf{isk}_r, \mathbf{st}_r$): Parse $(D_{\text{prek}}, D_{\rho_{\perp}}) \leftarrow \mathbf{st}_r$ and delete the last unused one-time state, i.e., let $t$ be the smallest index $s.t. D_{\text{prek}}[t] \neq \perp$. If $t \le L$, let $D_{\text{prek}}[t] \leftarrow \perp$. Output the updated $\mathbf{st}_r$.

SimSt_C($\mathbf{st}_{Sim}$): For $u \in \mathcal{C}$, extract $\mathbf{st}_u$ from $\mathbf{st}_{Sim}$, parse $(D_{\text{prek}}, D_{\rho_{\perp}}) \leftarrow \mathbf{st}_u$ and delete ephemeral secrets associated to used prekeys, i.e., for $t \in [\text{counter}_u]$, with $t \le L$, let $D_{\text{prek}}[t] \leftarrow \perp$. Output $(\mathbf{st}_u)_{u \in \mathcal{C}}$.

Recall that querying $(s, r) \in \mathcal{H} \times \mathcal{H}$ is only allowed in the global deniability game (see App. E.2 for details), hence, it remains to analyze the distinguishing advantage of $D$ given as auxiliary information $\text{disc}_D := ((\mathbf{isk}_u)_{u \in \mathcal{C}}, (\mathbf{st}_u^{\text{init}})_{u \in \mathcal{C}})$ disclosed by accusing users, and $\text{leak}_D = ((\mathbf{isk}_u)_{u \in \mathcal{H}}, (\mathbf{st}_u)_{u \in \mathcal{H}}) = \mathcal{L}_{\text{high}}((\mathbf{isk}_u)_{u \in \mathcal{H}}, (\mathbf{st}_u)_{u \in \mathcal{H}})$. First, for the case $(s, r) \in \mathcal{H} \times \mathcal{C}$, notice that $\mathbf{ss}_2, \mathbf{ss}_3, \mathbf{ss}_4$ are generated exactly as in the real world. Moreover, the simulated $\mathbf{ss}_1 = [\mathbf{spksec}_r] \bar{\mathbf{ik}}_s$ has the same distribution as the real world $\mathbf{ss}_1 = [\bar{\mathbf{isk}}_s] \mathbf{spk}_r$. Hence, the output of SimTrans is identical to real world outputs from $D$'s view, even given $\text{disc}_D$ and $\text{leak}_D$. Next, for the case $(s, r) \in \mathcal{C} \times \mathcal{H}$, notice that $\rho$ output by SimTrans is computed exactly by the real sender algorithm. Moreover, by correctness of the X3DH protocol, the real receiver algorithm outputs the same key $K$ output by SimTrans. Finally, it is straightforward to see that user states updated by $\text{SimSt}_H$ and $\text{SimSt}_C$ in simulated executions are consistent with real executions. Hence, no $D$ has any distinguishing advantage as desired. This completes the proof. □

The only difference between PQXDH and X3DH is that PQXDH additionally has a KEM key $\mathbf{ss}_{KEM}$ in the key derivation. As explained in Sec. 4.2, this does not affect local deniability of PQXDH.

**Lemma 5.** *The PQXDH protocol is locally deniable with respect to leakage function $\mathcal{L}_{\text{high}}$, and disclosure function $\mathcal{D}_{\text{high}}$, under the correctness of the KEM scheme. Importantly, this holds even for classical accusers and quantum distinguishers.*

*Proof.* The proof is almost identical to that given for X3DH (cf. Lemma 4). Indeed, $\text{SimPreK}$ is the same as before. The only difference is $\text{SimTrans}$, where we also take the KEM scheme into consideration. However, since KEM.Encaps can be run publicly, the honest sender remains deniable and provides no distinguishing advantage to $D$. Moreover, by the correctness of the KEM scheme, the simulator does not need to have the honest receiver's decapsulation key to know the outcome of KEM.Decaps. Specifically, adding a KEM to X3DH does not impact deniability. Since, assuming correctness of the underlying primitives, the simulation is perfect in both cases $((s, r) \in \mathcal{C} \times \mathcal{H})$, and $(s, r) \in \mathcal{H} \times \mathcal{C})$, deniability holds for both classical and quantum distinguishers. This completes the proof. □

## E.2. Global Deniability of X3DH

We prove that X3DH is globally deniable against honest-but-curious accusers. The protocol remains deniable even against distinguishers obtaining all secret information of the user if the one-time prekeys are never depleted. Otherwise, if the last-resort prekey bundle is used, then it remains deniable against distinguishers only obtaining the long-term identity secret key of the accused (i.e., leak = med). It is worth mentioning that only the sessions between honest senders and receivers using the last-resort prekey bundle become undeniable against full leakage — sessions using one-time prekey bundles remain deniable as expected.

**Lemma 6.** Assume the key derivation function KDF is modeled as a random oracle and the DDH assumption holds. Then, the X3DH protocol is globally deniable for honest users $\mathcal{H} \subseteq \mathcal{N}$ against honest-but-curious accusers $C := \mathcal{N} \setminus \mathcal{H}$ with respect to disclosure function $\mathcal{D}_{\text{high}}$, and leakage function $\mathcal{L}_{\text{leak}}$ for leak = high if the one-time prekey bundles are never depleted; and for leak = med otherwise.
*Proof.* Let us first define the simulator $Sim = (SimPreK, SimTrans, SimSt_H, SimSt_C)$. It is defined identically to that of Lemma 4 with the only exception that we have to further specify the description of $SimTrans$ on input $(s, r) \in \mathcal{H} \times \mathcal{H}$ as these cases were excluded in the local deniability game.

$SimTrans(\text{st}_{\text{Sim}}, (s, r, t))$: As explained above, we only describe the simulation for $(s, r) \in \mathcal{H} \times \mathcal{H}$. Simply sample a random group element $\text{epk} \stackrel{s}{\leftarrow} \mathbb{G}$, sample random $K \parallel \tau_{\text{conf}}$ from the range of the KDF, compute Alg. 5, Ln. 18, and output $(K, K, \rho)$. Namely, skip computing the input to the KDF.

It remains to analyze the distinguishing advantage of the distinguisher $D$, where we consider two cases as in the lemma statement. Since we proved (perfect) local deniability when leak = high, and disc = high in Lemma 4, we only focus on the transcript indistinguishability when $D$ queries $(s, r) \in \mathcal{H} \times \mathcal{H}$ to its oracle.

*Case 1.* Let us first consider the case where the one-time prekey bundles are not depleted: we always have a one-time prekey $\text{opk}_{u,t}$ for $t \in [L]$ and the sender always computes the secret key $K$ by including $\text{ss}_4$ in the KDF. In this case, $D$ is given as auxiliary information $\text{disc}_D := ((\text{isk}_u)_{u \in \mathcal{C}}, (\text{st}^{\text{init}}_u)_{u \in \mathcal{C}})$ disclosed by accusing users, and $\text{leak}_D := ((\text{isk}_u)_{u \in \mathcal{H}}, (\text{st}_u)_{u \in \mathcal{H}}) = \mathcal{L}_{\text{high}}((\text{isk}_u)_{u \in \mathcal{H}}, (\text{st}_u)_{u \in \mathcal{H}})$. The main observation is that once the receiver $r \in \mathcal{H}$ runs X3DH.Receive($\text{isk}_r, \text{st}_r$, ($\text{isk}_s, t, \rho$)), the one-time prekey secret $\text{osk}_t$ is deleted from its state $\text{st}_r$. Namely, $D$ does not have $\text{osk}_{r,t}$ nor $\text{esk}$ to compute $\text{ss}_4 = [\text{esk}]\text{opk}_{r,t} = [\text{osk}_{r,t}]\text{epk}$ after the session is established. We formalize this argument below.

For the sake of contradiction, assume $D$ has a non-negligible advantage $\epsilon$ and makes at most $Q_{\text{Global}}$ queries to the oracle $O_{\text{Global}}$. We first make a syntactical modification to the game when mode = real; recall that in this case, the game first ran $(K, \rho) \leftarrow X3DH Send(\text{isk}_s, (\text{isk}_r, \text{prek}_{r,t}))$ and $(K', \text{st}_r) \stackrel{s}{\leftarrow} X3DH Receive(\text{isk}_r, \text{st}_r, (\text{isk}_s, t, \rho))$. We modify this so that the game no longer runs X3DH Receive but simply outputs $K$ instead of $K'$ and an updated $\text{st}_r$, where $\text{st}_r[t] \leftarrow \perp$ if $t \neq \perp$. Due to correctness, this does not alter the view of $D$. For the sake of explanation, we denote this artificial receive algorithm by X3DH Receive' below. We also define a modified sender algorithm X3DH Send' defined identical to X3DH Send except that it samples $\text{ss}_4$ randomly in $\mathbb{G}$ as opposed to computing it as $[\text{esk}]\text{opk}_{r,t}$. Note that X3DH Receive' runs as expected on the output of X3DH Send', while X3DH Receive would output $\perp$ with overwhelming probability.

Now, let us define $Q_{\text{Global}} + 1$ hybrid games. We define $\text{Game}_{Q_{\text{Global}}+1}$ identical to the original global deniability game. The $i$-th ($i \in [Q_{\text{Global}}]$) game $\text{Game}_i$ is defined identical to $\text{Game}_{i+1}$ except that when $D$ queries $O_{\text{Global}}$ for the $Q_{\text{Global}} - i + 1$-th time, if the input is $(s, r) \in \mathcal{H} \times \mathcal{H}$, and if mode = real, the game computes the real transcript by running X3DH Send' and X3DH Receive' as opposed to running the original functions X3DH Send and X3DH Receive. Namely, in $\text{Game}_1$, X3DH Send' and X3DH Receive' are executed if mode = real and $SimTrans$ is executed if mode = sim, when $D$ queries $O_{\text{Global}}$ on input $(s, r) \in \mathcal{H} \times \mathcal{H}$. Notice that by the definition of X3DH Send, unless $D$ queries the random oracle on input $\text{ss}_1 \parallel \text{ss}_2 \parallel \text{ss}_3 \parallel \text{ss}_4$, the views in mode = real and sim are identical. However, since $\text{ss}_4$ is sampled uniformly at random from $\mathbb{Z}_p$ and hidden from $D$, this cannot occur with all but negligible probability. Hence, the advantage of $D$ in $\text{Game}_1$ is negligible. Then, by assumption, there must exist an index $i^* \in [Q_{\text{Global}}]$ such that the advantage of $D$ changes by more than a non-negligible fraction $\epsilon/Q_{\text{Global}}$ between $\text{Game}_{i^*}$ and $\text{Game}_{i^*+1}$. It remains to construct a DDH solver exploiting this fact.

Let $\mathcal{B}$ be an adversary against the DDH problem, given as input $(A, B, C) = ([a]G, [b]G, [c]G)$, where $c$ is $c = ab$ if $b_{\text{DDH}} = 0$ and $c \stackrel{s}{\leftarrow} \mathbb{Z}_p$ if $b_{\text{DDH}} = 1$. $\mathcal{B}$ first samples a challenge bit $b \stackrel{s}{\leftarrow} \{0, 1\}$, random $(s^*, r^*, t^*) \stackrel{s}{\leftarrow} \mathcal{H} \times \mathcal{H} \times [L]$, and prepares all the keys of the users as in $\text{Game}_{Q_{\text{Global}}+1}$ except that it sets the $t^*$-th one-time prekey $\text{opk}_{r^*, t^*}$ of user $r^*$ as $\mathcal{B}$ then simulates $\text{Game}_{i^*+1}$ up till the $(Q_{\text{Global}} - i^*)$-th query to $O_{\text{Global}}$ using the keys it has prepared at the beginning of the game. When $D$ queries $O_{\text{Global}}$ for the $(Q_{\text{Global}} - i^* + 1)$-th time on input $(s, r)$, $\mathcal{B}$ checks if $(s, r) = (s^*, r^*)$ and the $t^*$-th one-time prekey bundle of the receiver $r^*$ is going to be used. If not, it aborts the game. Otherwise, if $\mathcal{B}$ sampled $b = 0$ as the challenge bit, it first sets $\text{epk} = B$ rather than sampling it on its own (see Alg. 5, Ln. 7). It then computes $\text{ss}_1, \text{ss}_2, \text{ss}_3$ using the keys it sampled at the beginning of the game, where note that $\mathcal{B}$ knows all the discrete logarithms except for those of $\text{opk}_{r^*, t^*}$ and $\text{epk}$. Finally, it sets $\text{ss}_4 = C$, computes Alg. 5, Lns. 16 to 18, and outputs $(K, \rho)$. The rest of the game is identical to $\text{Game}_{i^*+1}$. When $D$ outputs a guess bit $b'$, $\mathcal{B}$ outputs $[b = b']$ as its guess for $b_{\text{DDH}}$.

It remains to analyze the advantage of $\mathcal{B}$. With probability $1/N^2L$, the guess $(s^*, r^*, t^*)$ made by $\mathcal{B}$ is correct. Moreover, the above game simulated by $\mathcal{B}$ is identical to $\text{Game}_{i^*+1}$ if $C = [ab]G$ and $\text{Game}_{i^*}$ if $C = [c]G$ for a random $c \stackrel{s}{\leftarrow} \mathbb{Z}_p$. From our assumption, since the advantage $D$ has against $\text{Game}_{i^*}$ and $\text{Game}_{i^*+1}$ differs by a non-negligible amount $\epsilon/Q_{\text{Global}}$, $\mathcal{B}$ solves the DDH problem with a non-negligible advantage of at least $\epsilon/(2N^2LQ_{\text{Global}})$. However, this contradicts the DDH assumption, thus completing the proof.

*Case 2.* The second case is where a last-resort prekey bundle is used. Unlike in Case 1, we can no longer embed the DDH problem into $\text{ss}_4$ as $\text{opk}_{u,\perp} = \perp$. To this end, we restrict the leakage given to $D$ as leak = med in order to embed the DDH problem into $\text{ss}_3 = [\text{esk}]\text{spk}_r = [\text{spksec}_r]\text{epk}$ instead. Following an almost identical hybrid argument as in Case 1, we can prove that no distinguisher $D$ can have non-negligible advantage in the global deniability game under the DDH assumption. $\square$

## E.3. Global Deniability of PQXDH

We prove two types of global deniability for PQXDH. While the accuser is always assumed to be classical, the distinguisher may be classical or quantum, where the latter captures HNJL deniability.
**Lemma 7.** Assume the key derivation function KDF is modeled as a random oracle. Then, the PQXDH protocol is globally deniable with respect to disclosure function $D_{\text{high}}$, and leakage function $L_{\text{leak}}$, for:

* leak = high if one-time prekey bundles are never depleted; and leak = med otherwise, under the DDH assumption;

* leak = high if one-time prekey bundles are never depleted; and leak = med otherwise, under the correctness of the KEM scheme and the existence of an efficient DL solver.

The latter case can handle deniability against a classical accuser and a quantum distinguisher.

*Proof.* The first (classical) part of the proof follows immediately from the proof of local deniability of the PQXDH protocol (cf. Lemma 5) and the proof of global deniability of the X3DH protocol (cf. Lemma 6). Indeed, from Lemma 5, we only need to specify the description of SimTrans on input $(s, r) \in \mathcal{H} \times \mathcal{H}$ as these cases were excluded in the local deniability game. An exact same proof following Lemma 6 suffices as deniability holds regardless of the KEM scheme, as anybody can produce a valid ciphertext.

For the HNJL part of the proof, where the distinguisher is quantum, local deniability is immediate. Indeed, the simulator's output is exactly the output of a real execution, no computational assumptions are required for deniability to hold. Hence, even a quantum D cannot distinguish real from simulated executions. For the case $(s, r) \in \mathcal{H} \times \mathcal{H}$, using the proof strategy of Lemma 6, we need to argue that a quantum D cannot guess the input $(ss \parallel ss_{\text{KEM}}, \text{content})$ to the KDF (modeled as a random oracle), with all but negligible probability. Observe that content is known to D; and a quantum D, who can compute discrete logarithms, could efficiently compute inputs $ss_1, ss_2, ss_3$ (and $ss_4$, if $\text{opk}_{r,t} \neq \perp$), and hence $ss$. However, so long as the KEM is proven post-quantum secure, $ss_{\text{KEM}}$ is indistinguishable from random from D's view, and can take any value in the KEM's session key space (which is exponentially large compared the number of oracle queries D can perform). Hence, D cannot query the random oracle on input $(ss \parallel ss_{\text{KEM}}, \text{content})$ with all but negligible probability. This holds both in the classical setting, and in the QROM, by applying the OW2H lemma [AHU19]. Indeed, let us denote $q$ the maximum number of (quantum) oracle queries made by D, $k$ the size of the KEM's session key space, and $S_{\text{BAD}}$ the set of values $(ss \parallel ss_{\text{KEM}}, \text{content})$ for which D's view differs in the real and simulated execution modes. Note that $|S_{\text{BAD}}| \le t$. Then for any input $x$, $\text{Pr}[x \in S_{\text{BAD}}] \le \frac{t}{k-q+1}$. Now, by applying Lemma 2, we can upper bound the probability $p_{\text{find}}$ that D, given access to the quantum random oracle, queries an element in $S_{\text{BAD}}$: $p_{\text{find}} \le \frac{4qt}{k-q+1}$. This allows us to bound the probability that D can tell appart real and simulated executions in the QROM by $p_{\text{dist}} \le 4q\sqrt{\frac{t}{k-q+1}}$, which is negligible in the security parameter. $\square$

## E.4. Strong Local and Global Deniability of X3DH and PQXDH

Strong local deniability of X3DH and PQXDH almost directly follows from their global counterparts so we only provide their security statement below. As explained in Sec. 4.2, we can only show PQXDH is classically strong local deniable.

**Lemma 8.** Assume the underlying group used by the X3DH and PQXDH protocols is a generic group of prime order $p$, and the key derivation function KDF is modeled as a random oracle. Then, the two protocols are strongly local deniable for honest users $\mathcal{H} \subseteq \mathcal{N}$ against malicious accusers $C := \mathcal{N} \setminus \mathcal{H}$ with respect to leakage function $L_{\text{high}}$. Importantly, the accusers and distinguisher are classical.

Below, we prove that X3DH and PQXDH are (classically) strongly global deniable. The leakages supported are the same as for standard (non-strong) global deniability (see Apps. E.2 and E.3).

**Lemma 9.** Assume the underlying group used by the X3DH and PQXDH protocols is a generic group of prime order $p$ and the key derivation function KDF is modeled as a random oracle. Then, the two protocols are strongly global deniable for honest users $\mathcal{H} \subseteq \mathcal{N}$ against malicious accusers $C := \mathcal{N} \setminus \mathcal{H}$ with respect to leakage function $L_{\text{leak}}$ for leak = high if the one-time prekeys are never depleted and for leak = med otherwise. Importantly, the accusers and distinguisher are classical.

*Proof.* We prove the statement in two parts: one proof for X3DH and another for PQXDH.

**First half (X3DH).** Let $\mathcal{A}$ be the malicious accuser. We first define the simulator $\text{Sim}_{\mathcal{A}} = (\text{Sim}_{\text{Pre}\mathcal{A}}, \text{Sim}_{\text{Trans}\mathcal{A}}, \text{Sim}_{\text{St}_{\mathcal{H}}}, \text{Sim}_{\text{St}_{\mathcal{A}}})$. Recall in the GGM with oblivious sampling (see App. B.1), every party, including the simulator $\text{Sim}_{\mathcal{A}}$ and the distinguisher D have access to the GGM oracles.

At a high level, $\text{Sim}_{\mathcal{A}}$ will internally execute the accuser $\mathcal{A}$ and when $\mathcal{A}$ queries the GGM and random oracles, $\text{Sim}_{\mathcal{A}}$ will simply relay them to its respective oracles. Assume the GGM oracle is queried a total of $Q$ times by all parties, including the challenger of the game. Since $\text{Sim}_{\mathcal{A}}$ can observe all the oracle queries made by $\mathcal{A}$, when $\mathcal{A}$ outputs a label $s \in S \subset \{0, 1\}^*$, representing a group element $\mathbb{G}$, $\text{Sim}_{\mathcal{A}}$ can efficiently compute the unique labels $(s_i, s'_i)_{i \in [Q]}$ for $Q' \le Q$ and non-zero coefficients $(\alpha_i, \alpha'_i)_{i \in [Q']}$ in $\mathbb{Z}_p$ such that $\Xi^{-1}(s) = \sum_{i \in [Q']}(\alpha_i \cdot \Xi^{-1}(s_i) + \alpha'_i \cdot \Xi^{-1}(s'_i))$, where $s_i$ (resp. $s'_i$) is an output of the GGM labeling (resp. oblivious sampling) oracle. Here, recall $\Xi: \mathbb{Z}_p \to S$ is the random injective function sampled within the GGM. Below, given a label $s \in S$ from $\mathcal{A}$, we call $s$ a Good$_L$ label if $s$ does not contain any coefficients $\alpha'_i$, and call it a Bad$_L$ label otherwise. That is, if $s$ contains labels output by the GGM oblivious sampling oracle, then we deem it a
Bad$_L$ label, (informally) indicating that neither $\text{Sim}_A$ nor $\mathcal{A}$ knows $\Xi^{-1}(s) \in \mathbb{Z}_p$. Moreover, it is clear that for any $\text{Good}_L$ label $s \in S$, $\text{Sim}_A$ can efficiently compute the unique $x \in \mathbb{Z}_p$ such that $\Xi(x) = s$. We will use these facts to describe the simulator $\text{Sim}_A$ below.

**SimPreK$_A$**($\text{ik}_u$)$_{u \in N}$, ($\text{isk}_u$)$_{u \in C}$, ($\text{prek}_u$)$_{u \in \mathcal{H}}$): It first internally executes the adversary $((\text{prek}_u)_{u \in C}, \text{st}_A) \stackrel{s}{\leftarrow} \mathcal{A}$($\text{ik}_u$)$_{u \in N}$, ($\text{isk}_u$)$_{u \in C}$, ($\text{prek}_u$)$_{u \in \mathcal{H}}$). It then outputs $((\text{prek}_u)_{u \in \mathcal{H}}$, ($\text{prek}_u$)$_{u \in C}$, $\text{st}_A$, $\text{st}_{\text{Sim}}$) with $\text{st}_{\text{Sim}} = ((\text{ik}_u, \text{prek}_u)_{u \in N}, \text{st}_A, \text{aux}_{\text{Sim}})$, where $\text{aux}_{\text{Sim}}$ includes all the queries $\mathcal{A}$ has made to the GGM and random oracles so far. Below, we assume $\text{aux}_{\text{Sim}}$ is updated every time the adversary or the simulator makes oracle queries.

**SimTrans$_A$**($\text{isk}$, $\text{st}_{\text{Sim}}$, $(s, r, t)$): Here, recall $\text{isk}$ is either $\text{isk}_s$, $\text{isk}_r$, or $\perp$ depending on $s \in C$, $r \in C$, or $(s, r) \in \mathcal{H} \times \mathcal{H}$, respectively.

If $(s, r) \in \mathcal{H} \times C$: First retrieve the prekey bundle $(\text{spk}_r, \sigma_{\text{spk}_r}, \text{opk}_{r,t}) \leftarrow \text{prek}_{r,t}$ of the malicious receiver, sample $\text{esk} \stackrel{s}{\leftarrow} \mathbb{Z}_p$ and query the GGM labelling oracle to receive $\text{epk} := \Xi(\text{esk}) \in S$. Then check if $\text{spk}_r$ is a Good$_L$ label using $\text{aux}_{\text{Sim}} \in \text{st}_{\text{Sim}}$. If so, compute the unique signed prekey secret $\text{spksec}_r \in \mathbb{Z}_p$ such that $\Xi(\text{spksec}_r) = \text{spk}_r$. Then query the GGM group operation oracle on the tuples $(\bar{\text{ik}}_s, \text{spksec}_r)$, $(\bar{\text{ik}}_r, \text{esk})$, $(\text{spk}_r, \text{esk})$, and $(\text{opk}_{r,t}, \text{esk}) \in \mathbb{Z}_p \times S$ to obtain labels $(s_1, s_2, s_3, s_4) \in S^4$. Set

$$ (\text{SS}_1, \text{SS}_2, \text{SS}_3, \text{SS}_4) := (s_1, s_2, s_3, s_4), $$

compute the remaining Alg. 5, Lns. 16 to 18, and output $(K, \rho, \text{st}_{\text{Sim}})$. Above, we note that if $\text{opk}_{r,t} = \perp$ (i.e., the last-resort prekey bundle), then the simulator simply ignores generation of $s_4$.

Otherwise, if $\text{spk}_r$ is a Bad$_L$ label, Sample random $(K \| \tau_{\text{conf}})$ from the range of the KDF, compute Alg. 5, Lns. 17 and 18, and output $(K, \rho, \text{st}_{\text{Sim}})$. Namely, skip computing the input to the KDF.

If $(s, r) \in C \times \mathcal{H}$: First execute the malicious sender internally $(\rho, \text{st}_A) \stackrel{s}{\leftarrow} \mathcal{A}(\text{isk}_s, \text{st}_A, (s, r, t))$ using the accuser's state $\text{st}_A \in \text{st}_{\text{Sim}}$. Here, the simulator updates $\text{st}_{\text{Sim}}$ by storing the updated $\text{st}_A$. Then parse $(\text{epk}, \tau_{\text{conf}}) \leftarrow \rho$ and check if $\mathcal{A}$ ever made a random oracle query on input $(\text{ss}, \text{content})$, where content := $\text{ik}_s \| \text{ik}_r \| \text{prek}_{r,t} \| \text{epk}$, such that $K \| \tau_{\text{conf}} := \text{KDF}(\text{ss}, \text{content})$ using $\text{aux}_{\text{Sim}} \in \text{st}_{\text{Sim}}$. If not, simply output $(\perp, \rho, \text{st}_{\text{Sim}})$. Otherwise, retrieve the first such tuple $(\text{ss}, K)$ under any canonical ordering and output $(K, \rho, \text{st}_{\text{Sim}})$.

If $(s, r) \in \mathcal{H} \times \mathcal{H}$: First sample $\text{esk} \stackrel{s}{\leftarrow} \mathbb{Z}_p$ and query the GGM labelling oracle to receive $\text{epk} := \Xi(\text{esk}) \in S$. Then sample random $(K \| \tau_{\text{conf}})$ from the range of the KDF, compute Alg. 5, Lns. 17 and 18, and output $(K, K, \rho)$. Namely, skip computing the input to the KDF.

**SimSt$_H$**($\text{isk}_r$, $\text{st}_r$): Parse $(D_{\text{prek}}, D_{\rho_\perp}) \leftarrow \text{st}_r$ and delete the last unused one-time state, i.e., let $t$ be the smallest index $s.t. D_{\text{prek}}[t] \neq \perp$. If $t \le L$, let $D_{\text{prek}}[t] \leftarrow \perp$. Output the updated $\text{st}_r$.

**SimSt$_A$**($\text{st}_{\text{Sim}}$): Extract $\text{st}_A$ from $\text{st}_{\text{Sim}}$. Output $\text{st}_A$.

It remains to analyze the distinguishing advantage of D. Notice that there are only three cases in which the simulator deviates from the algorithms executed in the real world.

**Case (i):** When $(s, r) \in \mathcal{H} \times C$ and $\text{spk}_r$ is a Bad$_L$ label. Since $\mathcal{A}$ (and hence D) does not know $\text{spksec}_r$ or $\text{esk}$, the Diffie-Hellman value $\text{ss}_3$ remains hidden. Specifically, the output of the KDF remains indistinguishable from random.

**Case (ii):** When $(s, r) \in C \times \mathcal{H}$ and $\mathcal{A}$ makes several random oracle queries on input $(\text{ss}, \text{content})$ such that $K \| \tau_{\text{conf}} := \text{KDF}(\text{ss}, \text{content})$ for a given content := $\text{ik}_s \| \text{ik}_r \| \text{prek}_{r,t} \| \text{epk}$. Note that if such an ss was never queried, the honest receiver will not accept the handshake message $\rho$ as the verification of Alg. 6, Ln. 19 will fail (with all but negligible probability). In particular, the simulation becomes identical to the real world.

**Case (iii):** When $(s, r) \in \mathcal{H} \times \mathcal{H}$, $\mathcal{A}$ (and hence D) does not know $\text{esk}$. If the sender uses the last-resort prekey bundle, then assuming the state of accused users is not leaked to D, the Diffie-Hellman value $\text{ss}_3$ remains hidden. Note that this is the only case where leaking honest users' state will cause the simulation to fail, as it would allow D to recompute the input to the KDF from $\rho$. It could then trivially see that the simulator sampled $(K \| \tau_{\text{conf}})$ randomly (as opposed to using the KDF). Hence, for global deniability, we can only simulate for leakage leak = med if the one-time prekeys are depleted.

More formally, the fact that Case (ii) cannot impact the distinguisher D's advantage follows immediately from the fact that KDF is a random oracle. Indeed, if $\text{ss} \neq \text{ss}'$, and denoting that $K \| \tau_{\text{conf}} := \text{KDF}(\text{ss}, \text{content})$, and that $K' \| \tau'_{\text{conf}} := \text{KDF}(\text{ss}', \text{content})$, since KDF is a random oracle, it holds that $\tau_{\text{conf}} \neq \tau'_{\text{conf}}$ with overwhelming probability. Moreover, if the honest receiver accepts, then the malicious sender must have queried $(\text{ss}, \text{content})$ such that $K \| \tau_{\text{conf}} := \text{KDF}(\text{ss}, \text{content})$. Indeed, due to the randomness of the KDF, for any fixed value of content, the probability that $\mathcal{A}$ can find an ss and $\tau_{\text{conf}}$ — without querying KDF($\text{ss}, \text{content}$) — satisfying $K^* \| \tau_{\text{conf}} := \text{KDF}(\text{ss}, \text{content})$, for arbitrary $K^*$, is negligible. Hence, the simulator can output