the same session key $K$ that will be output by the honest receiver. Finally, if the honest receiver does not accept (i.e., $K = \perp$), then the output of the simulator is identical to that of the accuser $\mathcal{A}$ in the real world.

It remains to formally prove that Case (i) and Case (iii) also cannot impact the advantage of $D$. To this end, we construct a reduction $\mathcal{R}$ that simulates the view of the distinguisher in the strong global deniability game. As typical with GGM based proofs, the reduction $\mathcal{R}$ simulates the game by using indeterminates $\bar{x}$ instead of $x \in \mathbb{Z}_p$ and encodes the “polynomial” $\bar{x} \in \mathbb{Z}_p[X]$ instead of $x$. Moreover, rather than preparing a random injective labeling function $\Xi: \mathbb{Z}_p \to S$, $\mathcal{R}$ samples a uniformly random label $s \in S$ on-the-fly, conditioned on that it has never been sampled. Note that the indeterminates are associated to the labels in $S$ for which $\mathcal{A}$ and $D$ do not know the corresponding discrete logarithm. Concretely, the reduction $\mathcal{R}$ maintains a list $L$ where each tuple consists of a polynomial over $\mathbb{Z}_p$ and a label $S$. At the end of the game, $\mathcal{R}$ plugs in random points in $\mathbb{Z}_p$ into the indeterminates and computes all the polynomials. As long as the distinct polynomials do not compute to the same value, the simulation remains indistinguishable in the GGM. We finally prove that such a collision occurs with negligible probability by relying on the Schwartz-Zippel lemma.

More formally, there are only three ways in which a new indeterminate is created by $\mathcal{R}$.

1. When generating the one-time prekeys at the beginning of the game, $\mathcal{R}$ prepares, for $u \in \mathcal{H}$ and $t \in [L]$, a new indeterminate $\text{osk}_{u,t}$, samples a random label $\text{opk}_{u,t} \stackrel{S}{\leftarrow} S$ not included in the list $L$, and uses $\text{opk}_{u,t}$ instead. At the time the distinguisher $D$ receives $\text{aux}_D$, the reduction $\mathcal{R}$ samples $\text{osk}_{u,t} \stackrel{\mathbb{Z}_p}{\leftarrow} \mathbb{Z}_p$ and provides it to $D$ if it has not been used yet (i.e., if it is not erased from state). It then evaluates all the polynomials in the list $L$ by plugging in $\overline{\text{osk}}_{u,t} = \text{osk}_{u,t}$. It also prepares new indeterminates for the signed prekey $\text{spk}_u$ and proceeds similarly.

2. When the adversary makes a GGM oblivious sampling query, $\mathcal{R}$ prepares a new indeterminate $\bar{x}$, samples a random label $s \stackrel{S}{\leftarrow} S$ not included in the list $L$, and outputs $s$. It then updates the list $L \leftarrow L \cup (\bar{x}, s)$. By definition, $s$ is a $\text{Bad}_L$ label.

3. When the simulator is required to sample $\text{esk} \stackrel{S}{\leftarrow} \mathbb{Z}_p$ when $(s, r) \in \mathcal{H} \times C$ or $\mathcal{H} \times \mathcal{H}$, $\mathcal{R}$ instead first prepares a new indeterminate $\overline{\text{esk}}$ and samples a random label $\text{epk} \stackrel{S}{\leftarrow} S$ not included in the list $L$. We assume the simulator continues its execution using $\text{esk}$ and the reduction simulates the GGM group operation queries accordingly.

In addition, the reduction $\mathcal{R}$ slightly alters the behavior of the simulator when $(s, r) \in \mathcal{H} \times C$ and $\text{spk}_r$ is a $\text{Bad}_L$ label, and when $(s, r) \in \mathcal{H} \times \mathcal{H}$. Recall that in these cases, the original simulator simply skipped computing the input to the KDF and sampled random $(K \parallel \tau_{\text{conf}})$ from the range of the KDF. This reflected the fact that the simulator could not compute some of the Diffie-Hellman inputs to the KDF. In contrast, the reduction $\mathcal{R}$ will always compute this. For instance, when it needs to compute the Diffie-Hellman tuple between two $\text{Bad}_L$ labels $\text{opk}_{r,t}$ and $\text{spk}_s$, it first computes the polynomial $\text{osk}_{r,t} \cdot \text{spk}_s$, samples a random label $s \stackrel{S}{\leftarrow} S$ not included in the list $L$, and uses $s$. It then updates the list $L \leftarrow L \cup (\overline{\text{osk}}_{r,t} \cdot \overline{\text{spk}}_{s}, s)$. It then runs the KDF on the computed labels. It is clear that unless the distinguisher $D$ evaluates the KDF on the computed label, the reduction $\mathcal{R}$'s simulation is identical to the behavior of the simulator. This corresponds to the case where neither of $\text{Bad}_L$ labels become $\text{Good}_L$ labels once giving $\text{aux}_D$ to the distinguisher $D$. In particular, this proves that Case (i) and Case (iii) have negligible impact on $D$.

Lastly, at the end of the game, the reduction $\mathcal{R}$ samples random $x \stackrel{S}{\leftarrow} \mathbb{Z}_p$ for all indeterminate $\bar{x}$, respectively, and plugs it in the polynomials in the list $L$. If any of the distinct polynomials in the list $L$ evaluate to the same value, then $\mathcal{R}$ aborts. It can be checked that unless $\mathcal{R}$ aborts, it perfectly simulates the strong global deniability game. Moreover, noticing that all the polynomials in the list $L$ are of degree at most two, the probability $\mathcal{R}$ aborts is bounded by $(2Q_{\mathcal{A}} + Q_D)^2/p$ due to the Schwartz-Zippel lemma, where $Q_{\mathcal{A}}$ and $Q_D$ are the number of GGM oracle queries made by $\mathcal{A}$ and $D$, respectively. Since $p$ is exponentially large, the probability is upper bounded by a negligible function. This completes the proof for X3DH.

**Second half (PQXDH).** The proof for PQXDH is almost identical to above. Indeed, $\text{SimPreK}$, $\text{SimSt}_{\mathcal{H}}$ and $\text{SimSt}_{\mathcal{A}}$ are the same as before. The only difference is $\text{SimTrans}$, where we also take the KEM scheme into consideration. When the sender is honest, i.e., $s \in \mathcal{H}$, we can rely on the same proof as in the X3DH case since KEM. Encaps can be run publicly. It is only when the sender is malicious (i.e., $s \in C$) that $\text{SimTrans}$ performs an extra check. This stems from the fact that a malicious sender may send a malformed ciphertext and the simulator must be able to simulate the honest receiver's behavior without the decapsulation key. While it is almost identical to the $\text{SimTrans}$ constructed for the case of X3DH, we provide its description for completeness.

$\text{SimTrans}_{\mathcal{A}}(\text{isk}, \text{st}_{\text{Sim}}, (s, r, t))$: As explained above, we only focus on $(s, r) \in C \times \mathcal{H}$. For this case, the simulation first executes the malicious sender internally $(\rho, \text{st}_{\mathcal{A}}) \stackrel{S}{\leftarrow} \mathcal{A}(\text{isk}_s, \text{st}_{\mathcal{A}}, (s, r, t))$ using the accuser's state $\text{st}_{\mathcal{A}} \in \text{st}_{\text{Sim}}$. Here, the simulator updates $\text{st}_{\text{Sim}}$ by storing the updated $\text{st}_{\mathcal{A}}$. It then parses $(\text{epk}, \text{ct}, \tau_{\text{conf}}) \leftarrow \rho$ and checks if $\mathcal{A}$ ever made a random oracle query on input $(\text{ss} \parallel \text{ss}_{\text{KEM}}, \text{content})$ where $\text{content} := \text{ik}_s \parallel \text{ik}_r \parallel \text{prek}_{r,t} \parallel \text{epk} \parallel \text{ct}$, such that it computed $K \parallel \tau_{\text{conf}} := \text{KDF}(\text{ss} \parallel \text{ss}_{\text{KEM}}, \text{content})$ using $\text{aux}_{\text{Sim}} \in \text{st}_{\text{Sim}}$. If not, it simply outputs $(\perp, \rho, \text{st}_{\text{Sim}})$. Otherwise, it retrieves the first such tuple $(\text{ss} \parallel \text{ss}_{\text{KEM}}, K)$ under any canonical ordering and outputs $(K, \rho, \text{st}_{\text{Sim}})$.
Following a similar argument to before, we can check that the above simulation cannot alter the advantage of the distinguisher $D$ with all but a negligible probability. In particular, if the honest receiver accepts the handshake message $\rho$, then the malicious sender must have queried $(ss||ss_{KEM}, \text{content})$ such that $K||\tau_{conf} := \text{KDF}(ss||ss_{KEM}, \text{content})$. Indeed, due to the randomness of the KDF, for any fixed content, the probability that $\mathcal{A}$ can find an $ss||ss_{KEM}$ and $\tau_{conf}$ — without querying KDF($ss||ss_{KEM}, \text{content}$) — that satisfy the computation $K^*||\tau_{conf} := \text{KDF}(ss||ss_{KEM}, \text{content})$, for arbitrary $K^*$, is negligible. Hence, the simulator can output the same session key $K$ that will be output by the honest receiver. Note that the simulation does not (and can not, as it does not know the receiver secrets) check that, denoting $ss_{KEM}^* := \text{KEM.Decaps}(dk_{r,l}, ct)$, it holds that $ss_{KEM}^* = ss_{KEM}$. However, observe that if $ss_{KEM}^* \neq ss_{KEM}$, then, denoting $K^*||\tau_{conf}^* := \text{KDF}(ss||ss_{KEM}, \text{content})$, with all but negligible probability, we will have $\tau_{conf}^* \neq \tau_{conf}$, and therefore the honest receiver would not accept (i.e., $K = \perp$). Finally, if the honest receiver does not accept, then the output of the simulator is identical to the accuser $\mathcal{A}$ in the real world (due to Alg. 2, Lns. 21 and 24). This completes the second half of the proof. $\square$

## E.5. Strong HNJL Deniability of PQXDH for Accused Receivers

We here prove the strong HNJL deniability of the protocol PQXDH. Since the leakage functions supported in the strong local and global settings are the same, we only focus on strong global deniability.

**Lemma 10.** Assume the key derivation function KDF used by the PQXDH protocol is modeled as a random oracle, and the KEM scheme is correct. Then, the PQXDH protocol is strongly deniable for accused receivers, against malicious accusers, restricted to be classical senders, with respect to quantum distinguishers given access to leakage function $\mathcal{L}_{high}$, under the assumption that the accuser only accesses the random oracle classically, and where:

* For local deniability, leak = high;

* For global deniability, leak = high if one-time prekey bundles are never depleted; and leak = med otherwise, under the correctness of the KEM scheme.

*Proof.* Let $\mathcal{A}$ be the malicious accuser. We first define the simulator $\text{Sim}_{\mathcal{A}} = (\text{SimPre}_{\mathcal{A}}, \text{SimTrans}_{\mathcal{A}}, \text{SimSt}_{\mathcal{H}}, \text{SimSt}_{\mathcal{A}})$. At a high level, $\text{Sim}_{\mathcal{A}}$ will internally execute the accuser $\mathcal{A}$ and when $\mathcal{A}$ queries the random oracle, $\text{Sim}_{\mathcal{A}}$ will simply relay the query to its respective oracle. We describe $\text{Sim}_{\mathcal{A}}$ below.

$\text{SimPre}_{\mathcal{A}}((\text{ik}_u)_{u \in \mathcal{N}}, (\text{isk}_u)_{u \in \mathcal{C}}, (\text{prek}_u)_{u \in \mathcal{H}})$: First internally execute the adversary $((\text{prek}_u)_{u \in \mathcal{C}}, \text{st}_{\mathcal{A}}) \stackrel{s}{\leftarrow} \mathcal{A}((\text{ik}_u)_{u \in \mathcal{N}}, (\text{isk}_u)_{u \in \mathcal{C}}, (\text{prek}_u)_{u \in \mathcal{H}})$. Finally, output $((\text{prek}_u)_{u \in \mathcal{H}}, (\text{prek}_u)_{u \in \mathcal{C}}, \text{st}_{\mathcal{A}}, \text{st}_{\text{Sim}})$ with $\text{st}_{\text{Sim}} = ((\text{ik}_u, \text{prek}_u)_{u \in \mathcal{N}}, \text{st}_{\mathcal{A}}, \text{aux}_{\text{Sim}})$, where $\text{aux}_{\text{Sim}}$ includes all the queries $\mathcal{A}$ has made to the random oracle so far. Below, we assume $\text{aux}_{\text{Sim}}$ is updated every time the adversary or the simulator makes oracle queries.

$\text{SimTrans}_{\mathcal{A}}(\text{isk}, \text{st}_{\text{Sim}}, (s, r, t))$: Here, isk is either $\text{isk}_s$ or $\perp$, since we only consider the case $r \in \mathcal{H}$.

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

If $(s, r) \in \mathcal{H} \times \mathcal{H}$: Since both users are honest, we can use the same simulation (and indistinguishability proof) here as in standard HNJL global deniability (see Lemma 7).

$\text{SimSt}_{\mathcal{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$.

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

It remains to analyze the distinguishing advantage of $D$. Regarding the simulation of prekeys, prekey bundles output by $\text{SimPre}_{\mathcal{A}}$ have exactly the same distribution as those output in the real world. It is also straightforward to see that the outputs of $\text{SimSt}_{\mathcal{H}}$ and $\text{SimSt}_{\mathcal{A}}$ in simulated executions are consistent with user states in real executions.

Regarding $\text{SimTrans}_{\mathcal{A}}$, for $(s, r) \in \mathcal{H} \times \mathcal{H}$, we can use the same analysis as in Lemma 7. Then there is only one other situation in which the simulator deviates from the algorithms executed in the real world. This is when $(s, r) \in \mathcal{C} \times \mathcal{H}$ and $\mathcal{A}$ makes a random oracle query on input $(ss||ss_{KEM}, \text{content})$ such that $K || \tau_{conf} = \text{KDF}(ss||ss_{KEM}, \text{content})$ for a given content $:= \text{ik}_s || \text{ik}_r || \text{prek}_r || \text{epk} || \text{ct}$, and where $\tau_{conf}$ is equal to that output by $\mathcal{A}$ in $\rho$. Note that if such an input was never queried, the honest receiver will not accept the handshake message $\rho$ as the equality check on Alg. 6, Ln. 19 will fail (with all but negligible probability). In particular, the simulation becomes identical to the real world.

The formal proof that the above simulation cannot alter the advantage of the distinguisher $D$ with all but a negligible probability is almost identical to that given for X3DH (cf. Lemma 9), and hence we here omit the details of the proof. $\square$
## E.6. PQXDH Modelling Gap

In our proposed BAKE model, all elements of a prekey bundle run out simultaneously. However, the actual specification of PQXDH is slightly different, as the last resort KEM key $ek_{r,⊥}$ may be used before one runs out of one time prekeys $opk_{r,t}$, and conversely, one may run out of $opk_{u,t}$'s but still have one time prekeys $ek_{r,t}$ available. Furthermore, a sender which receives $ek$ has no way of knowing if it is a last resort $ek_{r,⊥}$ or a one-time $ek_{r,t}$. We here clarify our simplification in the model does not harm the deniability results for PQXDH.

PQXDH's global deniability against classical distinguishers is only affected if both one-time keys $opk_{r,t}$ run out, and the last-resort $ek_{r,⊥}$ is used. Otherwise, even with full leakage from the accused user, the input to the KDF cannot be predicted by the distinguisher, and the session key is indistinguishable from a random key. If both one-time components of the prekey bundle run out, global deniability holds if leak = med, since $st_r$ contains the decapsulation key $dk_{r,⊥}$ and the DH secret spksec$_r$ (which is the secret leveraged in the DDH assumption when one runs out of keys $opk_{r,t}$). This holds for both standard and strong deniability against classical distinguishers.

On the other hand, deniability against quantum distinguishers only relies on the distinguishers' inability to decapsulate the KEM. If the last resort KEM encapsulation key $ek_{r,⊥}$ is used then HNJL deniability only holds if leak = med, since the client state contains the decapsulation key $dk_{r,⊥}$. Running out of $opk_{r,t}$ keys does not affect HNJL deniability.

Finally, we discuss the consequences of the sender not knowing if the receiver's $ek$ is a last-resort key. Note that local deniability holds for the sender even if an accusing receiver purposefully uses their last resort key, as only the global deniability of PQXDH is affected by prekeys running out, i.e., when both the sender and the receiver are accused. In this context, one would expect that both parties, where possible, regularly upload fresh prekey bundles, and delete old states, to guarantee deniability.

## F. Single to Multi-Challenge Deniability for Ring Signatures

In the following lemma we show that $(\bar{\mu}, \bar{\delta})$-deniability against adversaries making $Q$ challenge queries follows from $(\mu, \delta)$-deniability where the adversary is limited to a single challenge query.

**Lemma 11 (Single to Multi-Challenge Deniability).** If a ring signature scheme RS is $(\mu, \delta)$-deniable against adversaries performing a single signing query, then RS is $(\bar{\mu}, \bar{\delta})$-deniable against adversaries performing $Q$ queries, where $\bar{\mu} = \mu^Q$, and $\bar{\delta} \le \delta \cdot Q \cdot \mu^{Q-1}$.

Consequently, for deniability to hold in practice, using the NIST's recommended upper-bound $q_s = 2^{64}$ on the maximal number of signatures which may be queried from a single signer, it should hold that $\mu \le 1 + q_s^{-1}$, so that $\mu^{q_s} \le 2$. Note that it is intuitively natural that the adversary's success probability increases as it is allowed more queries, effectively extending its runtime. This does not diminish the "bit-security" of the scheme, which is generally understood as $\log(\frac{T}{\epsilon})$, where $T$ is the adversary's runtime and $\epsilon$ its success probability. Intuitively, the multiplicative factor $\mu$ bounds the additional advantage gained from increased queries, ensuring that the scheme's overall security level remains consistent.

The proof of Lemma 11 is given below.

*Proof.* Let us consider the deniability game for ring signatures $Game_{RS,b,\mathcal{A}}^{\text{Deny}}(1^{\lambda}, Q)$, where the adversary can adaptively make $Q$ queries to the challenge oracle, and thus get $Q$ signatures signed with $rsk_b$. For $j \in \{0, \dots, Q\}$ we define the hybrid game $\text{Hybrid}_j$, in which the adversary queries its signing oracle $Q$ times and, for $0 \le i \le Q - j$, the $i$-th query is signed using $rsk_0$; whereas for $i \ge Q - j + 1$, the $i$-th query is signed using $rsk_1$. Namely, $\text{Hybrid}_0$ is identical to $Game_{RS,0,\mathcal{A}}^{\text{Deny}}(1^{\lambda}, Q)$ whereas $\text{Hybrid}_Q$ is identical to $Game_{RS,1,\mathcal{A}}^{\text{Deny}}(1^{\lambda}, Q)$. Let $\mathcal{B}$ be an adversary against the single-query deniability of RS, and let $\mathcal{A}$ denote an adversary for the $Q$ query deniability game. We first show that, under the single-query deniability of RS, $\mathcal{A}$ cannot distinguish whether it is in $\text{Hybrid}_j$ or in $\text{Hybrid}_{j+1}$. Algorithm $\mathcal{B}$ receives as input a set of RS keypairs $(rvk_u, rsk_u)_{u \in [N]}$, which it forwards to $\mathcal{A}$. For $i \in [Q]$, consider the $i$-th query made by $\mathcal{A}$ to its signing oracle (simulated by $\mathcal{B}$). If $i < Q - j$ then $\mathcal{B}$ signs with identity key of index 0; if $i > Q - j$ then $\mathcal{B}$ signs with identity key of index 1; and for the $Q - j$-th query, $\mathcal{B}$ simply forwards the query to its own challenger, and sends the obtained signature back to $\mathcal{A}$.

Now if $\mathcal{A}$ outputs 0 (resp. 1), then $\mathcal{B}$ guesses that the RS signing key of index 0 (resp. of index 1) was used to sign its challenge signature, and outputs $b' := 0$ (resp. $b' := 1$). It follows that the probability $\mathcal{B}$ outputs 0 when its challenge bit was 0 (resp. 1) is exactly the probability that $\mathcal{A}$ outputs 0 in $\text{Hybrid}_j$ (resp. $\text{Hybrid}_{j+1}$). Hence, by the $(\mu, \delta)$-deniability of RS in the single query setting, it holds that $\Pr[0 \stackrel{s}{\leftarrow} \mathcal{A} | \text{Hybrid}_j] \le \mu \cdot \Pr[0 \stackrel{s}{\leftarrow} \mathcal{A} | \text{Hybrid}_{j+1}] + \delta$. By a simple recursion, we obtain:

$$ \Pr[0 \stackrel{s}{\leftarrow} \mathcal{A} | \text{Hybrid}_0] \le \mu^Q \cdot \Pr[0 \stackrel{s}{\leftarrow} \mathcal{A} | \text{Hybrid}_Q] + \delta \cdot Q \cdot \mu^{Q-1}. $$

Hence, RS is $(\mu^Q, \delta \cdot Q \cdot \mu^{Q-1})$-deniable against adversaries performing $Q$ signing queries. $\square$
# G. Proofs of Deniability for RingXKEM

In this section, we provide the proofs of varying levels of deniability attained by the RingXKEM protocol.

## G.1. Standard Local Deniability of RingXKEM

We here prove the standard local deniability of RingXKEM.

**Lemma 12.** If the underlying ring signature scheme RS is $(\mu, \delta)$-deniable, then the RingXKEM protocol is $(\mu, \delta)$-local deniable with respect to leakage function $L_{high}$, and disclosure function $D_{high}$.

*Proof.* Let us first define the simulator Sim:

SimPreK: $((ik_u)_{u \in N}, (isk_u)_{u \in C}, (\vec{prek}_u)_{u \in \mathcal{H}})$: For $u \in C$, run the PreKeyBundleGen algorithm, with the only difference that on L. 13 of the algorithm, the simulator does not discard the ring signature secret key, i.e., it computes $(\widehat{rvk}_u, \widehat{rsk}_u) \stackrel{s}{\leftarrow} \text{RS.KeyGen}(1^\lambda)$. Note that this is the only BAKE protocol considered in this article for which we use the fact that SimPreK deviates from the description of PreKeyBundleGen. This being said, the resulting prekey bundles and user state are still computed exactly as in a real execution:

$$ (\vec{prek}_u := (\text{prek}_{u,t})_{t \in [L] \cup \{\perp\}}, \text{st}_u := (D_{\text{kem}}, \widehat{rvk}_u, D_{\rho_\perp})) $$

Finally, output $((\vec{prek}_u)_{u \in \mathcal{H}}, (\vec{prek}_u, \text{st}_u)_{u \in C}, \text{st}_{\text{Sim}})$ with the latter value $\text{st}_{\text{Sim}} := ((ik_u, \vec{prek}_u)_{u \in N}, (isk_u, \text{st}_u)_{u \in C}, (\widehat{rvk}_u, \widehat{rsk}_u)_{u \in C})$. Below, for simplicity, we assume the simulator Sim always extracts the necessary public information from its state $\text{st}_{\text{Sim}}$.

SimTrans $(isk, \text{st}_{\text{Sim}}, (s, r, t))$: Here, recall isk is either $isk_s$ or $isk_r$ depending on $s \in C$ or $r \in C$, respectively.

If $(s, r) \in \mathcal{H} \times C$: The simulator extracts $isk_r := (dk_r, \widehat{rsk}_r)$ and $(\widehat{rvk}_r, \widehat{rsk}_r)$ from $\text{st}_{\text{Sim}}$. It runs Alg. 9, Lns. 7 to 10 as per the real sender algorithm (these steps do not require any sender secrets). It then uses the receiver's prekey ring signature secret key $\widehat{rsk}_r$ to compute the ring signature $\sigma \stackrel{s}{\leftarrow} \text{RS.Sign}(\widehat{rsk}_r, \text{content}, \{rvk_s, \widehat{rvk}_r\})$. Finally, it computes Alg. 9, Lns. 12 and 13, as per the real sender algorithm, and outputs $(K, \rho)$.

If $(s, r) \in C \times \mathcal{H}$: The simulator extracts $isk_s$ from $\text{st}_{\text{Sim}}$. It then simply runs $(K, \rho) \stackrel{s}{\leftarrow} \text{Send}(isk_s, ik_r, \text{prek}_{r,t})$ and outputs $(K, \rho)$.

SimSt$_{\mathcal{H}}$ $(isk_r, \text{st}_r)$: Parse $(D_{\text{kem}}, \widehat{rvk}_r, 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{kem}}[t] \neq \perp$. If $t \le L$, let $D_{\text{kem}}[t] \leftarrow \perp$. Output the updated $\text{st}_r$.

SimSt$_{C}$ $(\text{st}_{\text{Sim}})$: For $u \in C$, extract $\text{st}_u$ from $\text{st}_{\text{Sim}}$, parse $(D_{\text{kem}}, \widehat{rvk}_u, D_{\rho_\perp}) \leftarrow \text{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{kem}}[t] \leftarrow \perp$. Output $(\text{st}_u)_{u \in C}$.

It remains to analyze the distinguishing advantage of the distinguisher D. Regarding the simulation of prekeys, it is easy to see that prekey bundles output by SimPreK have exactly the same distribution as those output by the real PreKeyBundleGen algorithm. The only difference is that the simulator stores ring signing keys $(\widehat{rsk}_u)_{u \in C}$ in its state $\text{st}_{\text{Sim}}$ for future use. Since D does not have access to $\text{st}_{\text{Sim}}$, a real execution of PreKeyBundleGen is perfectly indistinguishable from the simulator's execution of SimPreK from D's view.

It is also straightforward to see that the outputs of $\text{SimSt}_\mathcal{H}$ and $\text{SimSt}_C$ in simulated executions are consistent with states updated in real executions.

Let us now consider the simulation of transactions. Since leak = high and disc = high, D is given as auxiliary inputs $\text{disc}_D := (isk_u, \text{st}_u^{\text{init}})_{u \in C}$ disclosed by accusing users, and $\text{leak}_D := (isk_u, \text{st}_u)_{u \in \mathcal{H}} = \mathcal{L}_{\text{high}}((isk_u)_{u \in \mathcal{H}}, (\text{st}_u)_{u \in \mathcal{H}})$.

If $(s, r) \in C \times \mathcal{H}$: Notice that $\rho$ output by SimTrans is computed by the real sender algorithm. Moreover, by correctness of the RingXKEM protocol, with all but negligible probability, the real receiver algorithm outputs the same key K output by SimTrans. Hence, the output of SimTrans is identical to the real world from D's view, even given $\text{disc}_D$ and $\text{leak}_D$.

If $(s, r) \in \mathcal{H} \times C$: Observe that the only difference with a real execution of the protocol is that the simulator uses the receiver's key $\widehat{rsk}_r$ instead of the sender's $\widehat{rsk}_s$ to compute the ring signature $\sigma$. However — in both real and simulated executions — the signature is for the ring $\{rvk_s, \widehat{rvk}_r\}$, i.e. the verification keys associated to $\widehat{rsk}_s$ and $\widehat{rsk}_r$. Hence, by deniability of RS, this difference cannot be detected by D except with negligible probability. Let us formalize this argument.

Let $\mathcal{B}$ be an adversary against the $(\mu(\lambda, Q), \delta(\lambda))$-deniability of RS, and let D denote an algorithm attempting to distinguish $\text{Game}_{\mathcal{D}, \mathcal{H}, \mathcal{L}_{\text{leak}}}(1^\lambda, \text{real})$ from $\text{Game}_{\mathcal{D}, \mathcal{H}, \mathcal{L}_{\text{leak}}}(1^\lambda, \text{sim})$. $\mathcal{B}$ samples a set of RS keypairs $((rvk_1, \widehat{rsk}_1), (\widehat{rvk}_1, \widehat{rsk}_1), \dots,$
(rvk<sub>N</sub>, rsk<sub>N</sub>), (rvk<sub>N</sub>, rsk<sub>N</sub>)), and a challenge bit mode $\stackrel{\$}{\leftarrow}$ {real, sim}. It then prepares the identity keys and prekeys of all users as per Alg. 8, using the aforementioned ring signature keys (and storing the secret keys {$\hat{rsk}_i$}$_{i \in [N]}$).

For $i \in [Q]$, consider the $i$-th query made by $D$ to $O_{\text{Local}}$. We denote the corresponding input to $O_{\text{Local}}$ as $(s, r, t)$. If $(s, r) \in \mathcal{H} \times \mathcal{C}$, then $\mathcal{B}$ computes $(ss_r, ct_r) \stackrel{\$}{\leftarrow} \text{KEM.Encaps}(ek_r)$; $(\hat{ss}_{r,t}, \hat{ct}_{r,t}) \stackrel{\$}{\leftarrow} \text{KEM.Encaps}(ek_{r,t})$; and content := $ik_s \| ik_r \| \text{prek}_{r,t} \| ct_r \| \hat{ct}_{r,t}$. Let us denote $id_0$ and $id_1$ the identities associated to rvk<sub>s</sub> and $\hat{rvk}_r$ respectively. $\mathcal{B}$ then sends $(\text{content}, id_0, id_1, \{rvk_s, \hat{rvk}_r\})$ to its challenger, and receives $\sigma^* \stackrel{\$}{\leftarrow} \text{RS.Sign}(\text{rsk}_{id_b}, \text{content}, \{rvk_s, rvk_r\})$ for some randomly sampled challenge bit $b \in \{0, 1\}$.

Observe that if $\mathcal{B}$'s challenge bit $b$ is 0 (resp. 1), then $D$'s view is exactly that of $\text{Game}_{D, \mathcal{H}, \mathcal{L}_{\text{high}}}^{\text{local}}(1^{\lambda}, \text{real})$ (resp. $\text{Game}_{D, \mathcal{H}, \mathcal{L}_{\text{high}}}^{\text{local}}(1^{\lambda}, \text{sim})$). Finally, $\mathcal{B}$ outputs $b' := 0$ if $D$'s output $\text{mode}' = \text{real}$, and 1 if $\text{mode}' = \text{sim}$. Hence, $\text{Pr}[b' = 0 | b = 1] = \text{Pr}[\text{mode}' = \text{real} | \text{Game}_{D, \mathcal{H}, \mathcal{L}_{\text{high}}}^{\text{local}}(1^{\lambda}, \text{sim})]$ and $\text{Pr}[b' = 0 | b = 0] = \text{Pr}[\text{mode}' = \text{real} | \text{Game}_{D, \mathcal{H}, \mathcal{L}_{\text{high}}}^{\text{local}}(1^{\lambda}, \text{real})]$. By the $(\mu, \delta)$-deniability of RS, we can conclude the proof, since, for $\beta \in \{0, 1\}$:

$$ \begin{align*} \Pr[b' = 0 | b = 0] &\le \mu(\lambda, Q) \cdot \Pr[b' = 0 | b = 1] + \delta(\lambda) \\ &\Leftrightarrow \Pr[\text{mode}' = \text{real} | \text{mode} = \text{real}] \le \mu(\lambda, Q) \cdot \Pr[\text{mode}' = \text{real} | \text{mode} = \text{sim}] + \delta(\lambda). \quad \square \end{align*} $$

## G.2. Standard Global Deniability of RingXKEM

We here prove the standard global deniability of RingXKEM.

**Lemma 13.** If the ring signature scheme RS is $(\mu, \delta)$-deniable, then the RingXKEM protocol is $(\mu, \delta)$-global deniable with respect to leakage function $\mathcal{L}_{\text{med}}$, and disclosure function $\mathcal{D}_{\text{high}}$.

*Proof.* For global deniability we simulate prekey bundles of all users, so that the simulator knows the secret keys for the RS verification keys in prekey bundles. Let us first define the simulator $\text{Sim} = (\text{SimPreK}, \text{SimTrans}, \text{SimSt}_{\mathcal{H}}, \text{SimSt}_{\mathcal{C}})$. We only need to consider the case $(s, r) \in \mathcal{H} \times \mathcal{H}$, since local deniability was proven in the previous section.

$\text{SimPreK}((ik_u)_{u \in \mathcal{N}}, (isk_u)_{u \in \mathcal{C}}, (\vec{prek}_u)_{u \in \mathcal{H}})$: We treat each user $u$ different depending on their role.

**For $u \in \mathcal{C}$:** Run the RingXKEM. PreKeyBundleGen algorithm, with the only difference that on Ln. 13 of the algorithm, the simulator does not discard the ring signature secret key, i.e., it computes $(\hat{rvk}_u, rsk_u) \stackrel{\$}{\leftarrow} \text{RS.KeyGen}(1^\lambda)$. The resulting prekey bundle $(\vec{prek}_u := (\text{prek}_{u,t})_{t \in [L] \cup \{\perp\}}, \text{st}_u := (D_{\text{kem}}, \hat{rvk}_u, D_{\rho_\perp}))$ is thus computed exactly as in a real execution.

**For $u \in \mathcal{H}$:** Parse the prekey bundle as $(ek_{u,t}, path_{u,t}, root_u, \sigma_{u,\text{root}}, \hat{rvk}_u)_{t \in [L] \cup \{\perp\}} \leftarrow \vec{prek}_u$. Sample $(\hat{rvk}_u^*, \hat{rsk}_u^*) \stackrel{\$}{\leftarrow} \text{RS.KeyGen}(1^\lambda)$, and replace $\hat{rvk}_u$ with $\hat{rvk}_u^*$, i.e. set $\hat{rvk}_u := \hat{rvk}_u^*$.

Finally, output $((\vec{prek}_u)_{u \in \mathcal{H}}, (\vec{prek}_u, \text{st}_u)_{u \in \mathcal{C}}, \text{st}_{\text{Sim}})$ with $\text{st}_{\text{Sim}} := ((ik_u, \vec{prek}_u)_{u \in \mathcal{N}}, (isk_u, \text{st}_u)_{u \in \mathcal{C}}, (\hat{rvk}_u, \hat{rsk}_u)_{u \in \mathcal{N}})$. Below, for simplicity, we assume the simulator $\text{Sim}$ always extracts the necessary public information from its state $\text{st}_{\text{Sim}}$.

$\text{SimTrans}(\text{st}_{\text{Sim}}, (s, r, t))$: We only consider $(s, r) \in \mathcal{H} \times \mathcal{H}$, hence the simulator has no user secrets. It first extracts $(\hat{rvk}_r, \hat{rsk}_r)$ from $\text{st}_{\text{Sim}}$, and runs Alg. 9, Lns. 7 to 10 as per the real sender algorithm (these steps do not require any sender secrets). It uses the receiver's prekey ring signature secret key $\hat{rsk}_r$ to compute the ring signature $\sigma \stackrel{\$}{\leftarrow} \text{RS.Sign}(\hat{rsk}_r, \text{content}, \{rvk_s, \hat{rvk}_r\})$. Finally, it computes Alg. 9, Lns. 12 and 13, as per the real sender algorithm, and outputs $(K, \rho)$.

It remains to analyze the distinguishing advantage of $D$ when $(s, r) \in \mathcal{H} \times \mathcal{H}$.

Regarding the simulation of prekeys, we first observe that, since the honest receiver's state $\text{st}_r := (D_{\text{kem}}, \hat{rvk}_r, D_{\rho_\perp})$ contains the original (non-simulated) verification key $\hat{rvk}_r$, if the accused receiver's state leaks, the distinguisher can easily distinguish real and simulated executions. Hence, we restrict the leakage function to $\mathcal{L}_{\text{med}}$, thereby ensuring that prekey bundles output by $\text{SimPreK}$ have exactly the same distribution as those output by the real RingXKEM. PreKeyBundleGen algorithm. The only difference is that, via this simulation, the simulator is able to store the secret ring signing keys $(\hat{rsk}_u)_{u \in \mathcal{N}}$ in its state $\text{st}_{\text{Sim}}$ for future use. Since $D$ does not have access to $\text{st}_{\text{Sim}}$, to it, a real execution of RingXKEM. PreKeyBundleGen is perfectly indistinguishable from the simulator's execution of $\text{SimPreK}$.

Let us now consider the simulation of transactions. Since $\text{leak} = \text{med}$ and $\text{disc} = \text{high}$, $D$ is given as auxiliary inputs $\text{disc}_D := (isk_u, \text{st}_u^{\text{init}})_{u \in \mathcal{C}}$ disclosed by accusing users, and $\text{leak}_D := (isk_u)_{u \in \mathcal{H}} = \mathcal{L}_{\text{med}}((isk_u)_{u \in \mathcal{H}}, (\text{st}_u)_{u \in \mathcal{H}})$. We only need to consider the case $(s, r) \in \mathcal{H} \times \mathcal{H}$. Observe that the only difference with a real execution of the protocol is that the simulator uses the receiver's key $\hat{rsk}_r$ instead of the sender's $\hat{rsk}_s$ to compute the ring signature $\sigma$. However, — in both real and simulated executions — the signature is for the ring $\{rvk_s, \hat{rvk}_r\}$, i.e. the verification keys associated to $\hat{rsk}_s$ and $\hat{rsk}_r$. By the deniability of RS, this difference cannot be detected by $D$ except with negligible probability. The formal proof for this is essentially identical to that of local deniability when $s \in \mathcal{H}$, we thus omit the details of the proof here. $\square$
### G.3. Strong Local and Global Deniability of RingXKEM for Accused Receivers

We here prove the strong local and global deniability of the protocol RingXKEM.

**Lemma 14.** Assume the key derivation function KDF used by the RingXKEM protocol is modeled as a random oracle, the KEM scheme is correct, and the SKE scheme is correct and robust. Then, the RingXKEM protocol is strongly local (resp. strongly global) deniable for accused receivers, against malicious accusers, restricted to be senders, with respect to leakage function $L_{high}$ (resp. $L_{med}$), under the assumption that the accuser only accesses the random oracle classically.

*Proof.* Let $\mathcal{A}$ be the malicious accuser. We first define the simulator $\text{Sim}_{\mathcal{A}} = (\text{SimPreK}_{\mathcal{A}}, \text{SimTrans}_{\mathcal{A}}, \text{SimSt}_{\mathcal{H}}, \text{SimSt}_{\mathcal{A}})$. At a high level, $\text{Sim}_{\mathcal{A}}$ will internally execute the accuser $\mathcal{A}$ and when $\mathcal{A}$ queries the random oracle, $\text{Sim}_{\mathcal{A}}$ will simply relay the query to its respective oracle. We describe $\text{Sim}_{\mathcal{A}}$ below.

$\text{SimPreK}_{\mathcal{A}}((\text{ik}_u)_{u \in \mathcal{N}}, (\text{isk}_u)_{u \in \mathcal{C}}, (\text{prek}_u)_{u \in \mathcal{H}})$: First internally execute the adversary $((\text{prek}_u)_{u \in \mathcal{C}}, \text{st}_{\mathcal{A}}) \stackrel{\$}{\leftarrow} \mathcal{A}((\text{ik}_u)_{u \in \mathcal{N}}, (\text{isk}_u)_{u \in \mathcal{C}}, (\text{prek}_u)_{u \in \mathcal{H}})$. Then, for $u \in \mathcal{H}$, parse $(\text{ek}_{u,t}, \text{path}_{u,t}, \text{root}_u, \sigma_{u,\text{root}}, \widehat{\text{rvk}}_u)_{t \in [L] \cup \{\perp\}} \leftarrow \text{prek}_u$. 

**If proving global deniability:** For $u \in \mathcal{H}$, sample $(\widehat{\text{rvk}}_u^*, \widehat{\text{rsk}}_u^*) \stackrel{\$}{\leftarrow} \text{RS.KeyGen}(1^{\lambda})$, and replace $\widehat{\text{rvk}}_u$ with $\widehat{\text{rvk}}_u^*$, i.e. $\widehat{\text{rvk}}_u := \widehat{\text{rvk}}_u^*$. Let $\widehat{\text{rsk}}_u := \widehat{\text{rsk}}_u^*$.

**Else (local):** For $u \in \mathcal{H}$, let $\widehat{\text{rsk}}_u := \perp$.

**End if.**

Finally, output $((\widehat{\text{prek}}_u)_{u \in \mathcal{H}}, (\widehat{\text{prek}}_u)_{u \in \mathcal{C}}, \text{st}_{\mathcal{A}}, \text{st}_{\text{Sim}})$ with $\text{st}_{\text{Sim}} = ((\text{ik}_u, \widehat{\text{prek}}_u)_{u \in \mathcal{N}}, \text{st}_{\mathcal{A}}, (\widehat{\text{rvk}}_u, \widehat{\text{rsk}}_u)_{u \in \mathcal{H}}, \text{aux}_{\text{Sim}})$, where $\text{aux}_{\text{Sim}}$ includes all the queries $\mathcal{A}$ has made to the random oracle so far. Below, we assume $\text{aux}_{\text{Sim}}$ is updated every time the adversary or the simulator makes oracle queries.

$\text{SimTrans}_{\mathcal{A}}(\text{isk}, \text{st}_{\text{Sim}}, (s, r, t))$: Here, isk is either isk$_s$ or $\perp$, since we only consider the case $r \in \mathcal{H}$.

If $(s, r) \in C \times \mathcal{H}$: First execute the malicious sender internally $(\rho, \text{st}_{\mathcal{A}}) \stackrel{\$}{\leftarrow} \mathcal{A}(\text{isk}_s, \text{st}_{\mathcal{A}}, (s, r, t))$ using the accuser's state $\text{st}_{\mathcal{A}} \in \text{st}_{\text{Sim}}$. Here, the simulator updates $\text{st}_{\text{Sim}}$ by storing the updated $\text{st}_{\mathcal{A}}$. Then parse $(\text{ct}_r, \widehat{\text{ct}}_r, \text{ct}_{\text{ske}}) \leftarrow \rho$ and check if $\mathcal{A}$ ever made a random oracle query on input $(\text{ss}_r \parallel \widehat{\text{ss}}_{r,t}, \text{content})$, where content := $\text{ik}_s \parallel \text{ik}_r \parallel \text{prek}_r \parallel \text{ct}_r \parallel \widehat{\text{ct}}_r$, such that $K \parallel K_{\text{ske}} := \text{KDF}(\text{ss}_r, \parallel \widehat{\text{ss}}_{r,t}, \text{content})$ using $\text{aux}_{\text{Sim}} \in \text{st}_{\text{Sim}}$. If not, simply output $(\perp, \rho, \text{st}_{\text{Sim}})$. Otherwise, under any canonical ordering, retrieve the first such tuple $(\text{ss}_r, \widehat{\text{ss}}_{r,t}, K, K_{\text{ske}})$, for which, denoting $\sigma := \text{SKE.Dec}(K_{\text{ske}}, \text{ct}_{\text{ske}})$, it holds that $[\text{RS.Verify}(\{\widehat{\text{rvk}}_s, \widehat{\text{rvk}}_r\}, \text{content}, \sigma) = 1]$. If none of the queried tuples satisfy this condition, then simply output $(\perp, \rho, \text{st}_{\text{Sim}})$. Otherwise, output $(K, \rho, \text{st}_{\text{Sim}})$.

If $(s, r) \in \mathcal{H} \times \mathcal{H}$: Since both users are honest, we can use the same simulation (and indistinguishability proof) here as in standard global deniability.

$\text{SimSt}_{\mathcal{H}}(\text{isk}_r, \text{st}_r)$: Parse $(D_{\text{kem}}, \widehat{\text{rvk}}_r, 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{kem}}[t] \neq \perp$. If $t \le L$, let $D_{\text{kem}}[t] \leftarrow \perp$. Output the updated $\text{st}_r$.

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

It remains to analyze the distinguishing advantage of D. Regarding the simulation of prekeys, for strong local deniability, prekey bundles output by $\text{SimPreK}_{\mathcal{A}}$ have exactly the same distribution as those output in the real world. For strong global deniability, this holds so long as honest receiver states do not leak (as was the case for standard global deniability), i.e., **leak = med**. The only difference is that the simulator is able to store the secret keys $(\widehat{\text{rsk}}_u)_{u \in \mathcal{H}}$ in its state $\text{st}_{\text{Sim}}$ for future use. Since D does not have access to $\text{st}_{\text{Sim}}$, a real execution of RingXKEM. PreKeyBundleGen is perfectly indistinguishable from the simulator's execution of $\text{SimPreK}_{\mathcal{A}}$ from D's view. It is also straightforward to see that the outputs of $\text{SimSt}_{\mathcal{H}}$ and $\text{SimSt}_{\mathcal{A}}$ in simulated executions are consistent with user states in real executions.

Regarding $\text{SimTrans}_{\mathcal{A}}$, notice that there are only two cases in which the simulator deviates from the algorithms executed in the real world.

**Case (i)** When $(s, r) \in C \times \mathcal{H}$ and $\mathcal{A}$ makes several random oracle queries on input $(\text{ss}_r \parallel \widehat{\text{ss}}_{r,t}, \text{content})$ such that $K \parallel K_{\text{ske}} := \text{KDF}(\text{ss}_r \parallel \widehat{\text{ss}}_{r,t}, \text{content})$ for a given content := $\text{ik}_s \parallel \text{ik}_r \parallel \text{prek}_r \parallel \text{ct}_r \parallel \widehat{\text{ct}}_r$. Note that if such an input was never queried, the honest receiver will not accept the handshake message $\rho$ as, by robustness of the SKE, the decryption of Alg. 10, Ln. 15 will fail (with all but negligible probability). In particular, the simulation becomes identical to the real world.

**Case (ii)** When $(s, r) \in \mathcal{H} \times \mathcal{H}$, since neither of the parties is in $C$, they both follow the protocol description, and the same arguments as for standard global deniability allow arguing indistinguishability of real and simulated executions.

The formal proof that the above simulation cannot alter the advantage of the distinguisher D with all but a negligible probability is almost identical to that given for X3DH (cf. Lemma 9), and hence we here omit the details of the proof. $\square$
### G.3.1. Attack on Strong Sender Deniability

Hashimoto et al. noticed that there are plausible attacks on strong sender deniability [Has+22, Remark 7.11]. Namely, a malicious receiver accuser can craft a malicious RS verification key $\hat{rvk}_r$ such that it can later prove that it does not know the signing key. This means that if a sender produces a ring signature $\sigma_S$ on the ring $\{rvk_s, \hat{rvk}_r\}$, the receiver can later convince a judge that it could not have generated $\sigma_S$, thus breaking deniability. While it may be possible to thwart such attacks by including a proof of signing key possession in the prekey bundle, we do not consider them in our work due to the high overhead of such proofs.

Note that this attack does not extend to X3DH or PQXDH. Indeed, in X3DH and PQXDH, if the malicious receiver provides a pre-key for which it does not know the associated secret key, then it is not able to compute the input $s$ to the KDF, from which keys are derived. This means that the accuser cannot exchange encrypted messages with the accused sender, and that the distinguisher cannot distinguish a session key honestly generated by the sender from a randomly sampled session key. Conversely, in RingXKEM, the malicious receiver can generate its prekeys with honest KEM keys, but an RS public key for which the secret is unknown. The KEM decapsulation key allows for decryption of the input for the KDF, so not knowing the RS signing key does not prevent the judge from recomputing the session key output by the KDF, whereas it prevents the sender from denying the ring signature.

## H. Deniability of SignXKEM

At PKC 2021, Hashimoto et al. proposed a post-quantum, signed Signal handshake protocol. As signatures typically provide the opposite of deniability (namely, non-repudiation), they suggested encrypting the signature to hide it from accusers [Has+21; Has+22]. In this section, we build on their proposal and develop the SignXKEM protocol. We add the Merkle Tree optimization described in [HKW25, Section 5.1]. We will first instantiate SignXKEM as a BAKE protocol using the syntax from Def. 1, after which we will discuss its deniability.

### H.1. The SignXKEM protocol

SignXKEM uses a KEM `KEM` and a (plain) signature scheme `Sig` for its identity keys and prekeys. Additionally, it uses a symmetric encryption scheme `SKE` and a Merkle Tree. The functions `SignXKEM.IdKeyGen`, `SignXKEM.PreKeyBundleGen`, `SignXKEM Send`, and `SignXKEM.Receive` are given by the `Algs. 8` to `10` respectively.

The basic functionality of the SignXKEM 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 a signature to authenticate the sender. The signature is encrypted using the derived encryption key, which allows us to obtain deniability as described in App. H.2.

To authenticate the prekey bundle, one could simply sign it; however, as post-quantum signature schemes typically have large signatures, this leads to significant storage requirements. The Merkle tree optimization was first proposed for RingXKEM (discussed in Sec. 5) by Hashimoto, Katsumata, and Wiggers [HKW25]. By constructing a Merkle tree from all KEM public keys $\hat{dk}_{u,t}$, we can replace prekey bundles' individual signatures by the path to the root and a single signature on the root of the tree. This amortizes the storage cost of post-quantum signatures over all prekey bundles that are uploaded by a single call to `SignXKEM.IdKeyGen`. Note that although we include the Merkle tree path in our description of prekey bundles $\text{prek}_{u,t}$, this path and the tree's root can be recomputed by the server from the uploaded prekey bundles (and thus do not need to be stored).

### H.2. Summary: Deniability of SignXKEM

We summarize the level of deniability that SignXKEM satisfies. See Tab. 1 for a complete overview. The formal statements are provided in Apps. H.3 and H.4.

**Local and global deniability.** For SignXKEM, the permitted levels of leakage and disclosure allowing to achieve local and global deniability depend on whether the last resort prekey is used. In particular, standard local and global deniability hold for $(\text{leak}, \text{disc}) = (\text{high}, \text{med})$ if one-time prekeys never run out; otherwise, one must restrict to $(\text{leak}, \text{disc}) = (\text{med}, \text{low})$.

This is because, to ensure that the signature authenticating the sender remains hidden from the distinguisher `D`, we once again rely on the fact that the input to the KDF, modelled as a random oracle, cannot be guessed by `D`. If this holds, then `D` cannot recompute the key $K_{Ske}$ allowing to decrypt the `SKE` ciphertext and recover the signature. However, for SignXKEM, if `D` knows the receiver's *initial* state, it can easily recompute the inputs to the KDF, whereas if `D` only gets the *updated* states, and only one-time prekey bundles are used — whose states are deleted after use — then `D` cannot guess the KDF input with all but negligible probability. Hence, so long as one-time prekeys are not depleted, and the distinguisher only gets *updated* states, (i.e., $(\text{leak}, \text{disc}) = (\text{high}, \text{med})$) local and global deniability hold. On the other hand, if the last-resort prekey is used, the associated state is not deleted, and hence even the receiver's *updated* state would allow `D` to compute the KDF's input. In this case, deniability holds for $(\text{leak}, \text{disc}) = (\text{med}, \text{low})$.
Both local and global deniability of SignXKEM hold even if both the accuser and the distinguisher are *quantum*, so long as KEM is PQ secure.

**Strong local and global deniability.** As was the case for RingXKEM, for strong (local and global) deniability, we are only able to prove deniability for the *receiver*; this holds with respect to the leakage function $\mathcal{L}_{\text{leak}}$ for leak = high if the one-time prekey bundles are never depleted, and leak = med otherwise. Again, as for RingXKEM, we can only prove strong deniability for the receiver in the *classical* ROM, while the malicious accuser and distinguisher may be quantum. The proof strategy is similar to that of strong deniability for PQXDH.

### H.3. Local and Global Deniability of SignXKEM

We prove that SignXKEM is local and global deniable for weak disclosure functions (where the initial state of accusing users is not revealed). Since the disclosure and leakage functions supported in the local and global settings are the same, we only focus on global deniability. The non-trivial part of the proof is when the sender is honest. In this case, we must argue that the sender's signature implicitly included in the handshake message $\rho$ cannot be later recovered by the distinguisher, as otherwise, deniability cannot hold. To this end, we use the fact that for weak disclosure functions (i.e., $\mathcal{D}_{\text{disc}}$ with disc $\in \{\text{low}, \text{med}\}$) the distinguisher only obtains the accuser's *updated* states. Specifically, once the (honest-but-curious) receiver deletes the decapsulation key included in the one-time prekey bundle, the handshake message from the honest sender should look random. This is why SignXKEM does not satisfy deniability for disclosure function $\mathcal{D}_{\text{high}}$: given high, the distinguisher can decrypt the encrypted signatures.

Below, we rely on the OW2H lemma [AHU19] (see App. B.2 for definition) to formally prove this against a quantum accuser and distinguisher in the QROM.

**Lemma 15.** Assume the key derivation function KDF is modeled as a random oracle and the KEM scheme is correct and IND-CPA secure, and the SKE scheme is correct, IND-CPA secure, and robust. Then, the SignXKEM protocol is globally deniable with respect to leakage function $\mathcal{L}_{\text{leak}}$ and disclosure function $\mathcal{D}_{\text{disc}}$ for leak = high and disc = med if the one-time prekey bundles are never depleted; and for leak = med and disc = low otherwise.

*Proof.* Let us first define the simulator $\text{Sim} = (\text{SimPreK}, \text{SimTrans}, \text{SimSt}_H, \text{SimSt}_C)$.

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

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

If $s \in \mathcal{H}$: It first runs $(\text{ss}_r, \text{ct}_r) \stackrel{s}{\leftarrow} \text{KEM.Encaps}(\text{ek}_r)$ and $(\text{ss}_{r,t}, \text{ct}_{r,t}) \stackrel{s}{\leftarrow} \text{KEM.Encaps}(\text{ek}_{r,t})$, and samples random keys $(K, K_{\text{ske}})$ from the range of the KDF. It then samples a random message $M$ having the same length as a signature $\sigma_s$ and runs $\text{ct}_{\text{ske}} \stackrel{s}{\leftarrow} \text{SKE.Enc}(K_{\text{ske}}, M)$. Lastly, it outputs $(K, \rho := (\text{ct}_r, \text{ct}_{r,t}, \text{ct}_{\text{ske}}))$. Note that even if $r \in \mathcal{C}$, the simulator does not require $\text{isk}_r$.

If $(s, r) \in \mathcal{C} \times \mathcal{H}$: It simply runs $(K, \rho) \stackrel{s}{\leftarrow} \text{SignXKEM Send}(\text{isk}_s, \text{ik}_r, \text{prek}_{r,t})$, and outputs $(K, \rho)$.

$\text{SimSt}_H(\text{isk}_r, \text{st}_r)$: Parse $(D_{\text{kem}}, 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{kem}}[t] \neq \perp$. If $t \le L$, let $D_{\text{kem}}[t] \leftarrow \perp$. Output the updated $\text{st}_r$.

$\text{SimSt}_C(\text{st}_{\text{Sim}})$: For $u \in \mathcal{C}$, extract $\text{st}_u$ from $\text{st}_{\text{Sim}}$, parse $(D_{\text{kem}}, D_{\rho_{\perp}}) \leftarrow \text{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{kem}}[t] \leftarrow \perp$. Output $(\text{st}_u)_{u \in \mathcal{C}}$.

It remains to analyze the distinguishing advantage of the distinguisher $D$, where we consider two cases as in the lemma statement.

**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{prek}_{u,t}$ for $t \in [L]$. In this case, $D$ is given as auxiliary information $\text{disc}_D := ((\text{isk}_u)_{u \in \mathcal{C}}, (\text{st}_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}})$.

If $(s, r) \in \mathcal{C} \times \mathcal{H}$: notice that $\rho$ output by $\text{SimTrans}$ is computed by the real sender algorithm. Moreover, by correctness of the SignXKEM protocol, the real receiver algorithm outputs the same key $K$ output by $\text{SimTrans}$ with all but negligible probability. Hence, the output of $\text{SimTrans}$ is identical to the real world to a distinguisher $D$ even given $\text{disc}_D$ and $\text{leak}_D$.

If $s \in \mathcal{H}$: the main observation is that for disclosure function $\mathcal{D}_{\text{med}}$, $D$ only obtains the accuser's *updated* states. Specifically, whether $r$ be in $\mathcal{C}$ or in $\mathcal{H}$, once the (honest-but-curious / honest) receiver runs SignXKEM Receive $(\text{isk}_r, \text{st}_r, (\text{ik}_s, t, \rho))$, the one-time prekey secret $\text{dk}_{r,t}$ is deleted from its state $\text{st}_r$. Namely, $D$ does not have $\text{dk}_{r,t}$ to compute $\text{ss}_{r,t} := \text{KEM.Decaps}(\text{dk}_{r,t}, \text{ct}_{r,t})$ 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 $\mathcal{O}_{\text{Global}}$ queries to the oracle $\mathcal{O}_{\text{Global}}$. We first make a syntactical modification to the game when mode = real. In this mode, the game ran $(K, \rho) \stackrel{\epsilon}{\leftarrow} \text{SignXKEMSend}(\text{isk}_s, (\text{ik}_r, \text{prek}_{r,t}))$ and $(K', \text{st}_r) \stackrel{\epsilon}{\leftarrow} \text{SignXKEMReceive}(\text{isk}_r, \text{st}_r, (\text{ik}_s, t, \rho))$. We modify this so that the game no longer runs SignXKEMReceive but simply outputs $K$ instead of $K'$ and an updated $\text{st}_r$, where $\text{st}_r[t] \leftarrow \bot$ if $t \neq \bot$. Due to the correctness of SignXKEM, the view of D is identical with all but negligible probability. We denote this artificial receive algorithm by SignXKEMReceive'. We also define a modified sender algorithm SignXKEMSend' defined identical to SignXKEMSend except that, after computing $(\text{ss}_{r,t}, \text{ct}_{r,t}) \stackrel{\epsilon}{\leftarrow} \text{KEM.Encaps}(\text{ek}_{r,t})$, it samples $\text{ss}'_{r,t}$ randomly over KEM's session key space and overwrites $\text{ss}_{r,t}$ with $\text{ss}'_{r,t}$. Note that SignXKEMReceive' runs as expected on the output of SignXKEMSend', while SignXKEMReceive would output $\bot$ with overwhelming probability.

Now, let us define $\mathcal{Q}_{\text{Global}} + 1$ hybrid games, where $\text{Game}_{\mathcal{Q}_{\text{Global}}+1}$ is defined identical to the original global deniability game. The $i$-th ($i \in [\mathcal{Q}_{\text{Global}}]$) game $\text{Game}_i$ is defined identical to $\text{Game}_{i+1}$ except that when D queries $\mathcal{O}_{\text{Global}}$ for the $\mathcal{Q}_{\text{Global}} - i + 1$-th time, if $s \in \mathcal{H}$ and mode = real, the game computes the real transcript by running SignXKEMSend' and SignXKEMReceive' as opposed to running SignXKEMSend and SignXKEMReceive. Namely, in $\text{Game}_1$, SignXKEMSend' and SignXKEMReceive' are executed if mode = real and $\text{SimTrans}$ is executed if mode = sim, when D queries $\mathcal{O}_{\text{Global}}$ on input a sender $s \in \mathcal{H}$.

Notice that by the definition of SignXKEMSend', unless D queries the random oracle on input $\text{ss}_r \parallel \text{ss}_{r,t}$, context, the views in mode = real and sim are identical. Indeed, assuming no such query to the random oracle is made by D, in both modes the keys $(K, K_{\text{ske}})$ are random in the range of the KDF. It follows that, from D's view, $K_{\text{ske}}$ can take any value in the SKE key space. Furthermore, the robustness of SKE ensures that $\text{ct}_{\text{ske}}$ can only be decrypted using the same key $K_{\text{ske}}$ as was used for encryption. Hence, D has negligible probability of guessing $K_{\text{ske}}$ which would allow decrypting $\text{ct}_{\text{ske}}$, and, from the IND-CPA security of SKE, D has negligible advantage in distinguishing $\text{ct}_{\text{ske}}$ as computed when mode = real and when mode = sim. Now, since $\text{ss}_{r,t}$ is sampled uniformly at random from KEM's session key space (which is exponentially large compared to $t$ and the number of oracle queries made by D) and hidden from D, D cannot query the random oracle on input $\text{ss}_r \parallel \text{ss}_{r,t}$, context 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 $\text{ss}_r \parallel \text{ss}_{r,t}$, context 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 distinguish 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.

Hence, the advantage of D in $\text{Game}_1$ is negligible. Then, by assumption, there must exist an index $i^* \in [\mathcal{Q}_{\text{Global}}]$ such that the advantage of D changes by more than a non-negligible fraction $\epsilon/\mathcal{Q}_{\text{Global}}$ between $\text{Game}_{i^*}$ and $\text{Game}_{i^*+1}$. It remains to construct an adversary breaking KEM's IND-CPA security exploiting this fact.

Let $\mathcal{B}$ be an adversary against the IND-CPA security of KEM, given as input $(\text{ek}^*, (\text{ss}^*, \text{ct}_0^*))$, where $(\text{ek}^*, \text{dk}^*) \stackrel{\epsilon}{\leftarrow} \text{KEM.KeyGen}(1^\lambda)$; $(\text{ss}^*, \text{ct}_0^*) \stackrel{\epsilon}{\leftarrow} \text{KEM.Encaps}(\text{ek}^*)$ if the challenge bit $b_{\text{KEM}} = 0$ and $\text{ss}^* \stackrel{\epsilon}{\leftarrow} \mathcal{K}$ if $b_{\text{KEM}} = 1$.

$\mathcal{B}$ first samples a challenge bit mode $\stackrel{\epsilon}{\leftarrow} \{\text{real, sim}\}$, random $(s^*, r^*, t^*) \stackrel{\epsilon}{\leftarrow} \mathcal{H} \times \mathcal{N} \times [L]$, and prepares all the keys of the users as in $\text{Game}_{\mathcal{Q}_{\text{Global}}+1}$ except that it sets the $t^*$-th one-time prekey $\text{ek}_{r^*,r^*}$ of user $r^*$ as $\text{ek}^*$. $\mathcal{B}$ then simulates $\text{Game}_{i^*+1}$ up till the $(\mathcal{Q}_{\text{Global}} - i^*)$-th query to $\mathcal{O}_{\text{Global}}$ using the keys it has prepared at the beginning of the game. When D queries $\mathcal{O}_{\text{Global}}$ for the $(\mathcal{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 mode = real, it sets $(\text{ss}_{r^*,t^*}, \text{ct}_{r^*,t^*}) := (\text{ss}^*, \text{ct}_0^*)$ rather than using the KEM.Encaps algorithm, computes Alg. 9, Lns. 7 and 9 to 14, and outputs $(K, \rho)$. The rest of the game is identical to $\text{Game}_{i^*+1}$. When D outputs a guess bit mode', $\mathcal{B}$ outputs $[[\text{mode} = \text{mode'}]]$ as its guess for $b_{\text{KEM}}$.

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 $(\text{ss}_0^*, \text{ct}_0^*) \stackrel{\epsilon}{\leftarrow} \text{KEM.Encaps}(\text{ek}^*)$, and $\text{Game}_{i^*}$ if $\text{ss}_1^* \stackrel{\epsilon}{\leftarrow} \mathcal{K}$. From our assumption, since the advantage that D has against $\text{Game}_{i^*}$ and $\text{Game}_{i^*+1}$ differs by a non-negligible amount $\epsilon/\mathcal{Q}_{\text{Global}}$, $\mathcal{B}$'s advantage in the IND-CPA security game of the KEM is at least $\epsilon/(2N^2L\mathcal{Q}_{\text{Global}})$, which is non-negligible. However, this contradicts the assumption that KEM is IND-CPA secure, thus completing the proof for the case where one-time prekey bundles are not depleted.

**Case 2.** Let us now consider the case where the last resort prekey bundle is used. Since the last resort prekey secret $\text{dk}_{r,\bot}$ is not deleted from $r$'s state after having been used, if D were to obtain $r$'s state $\text{st}_r$, it would be able to decapsulate the KEM keys and distinguish real and simulated executions. Consequently, if the last resort prekey bundle is used, global deniability is only proven to hold for leakage function $\mathcal{L}_{\text{med}}$ and disclosure function $\mathcal{D}_{\text{low}}$. Indeed, these do not reveal any user states, so $\text{dk}_{r,\bot}$ remains unknown to D, and the same proof methodology as in Case 1 can be applied.

This completes the proof. □
## H.4. Strong Local and Global Deniability of SignXKEM for Accused Receivers

Since the leakage functions supported in the strong local and global settings are the same, we focus on global deniability.

It is clear that SignXKEM does not satisfy strong deniability since it is not even (standard) deniable if an accusing receiver's initial state is revealed to the distinguisher. However, it does satisfy some level of strong deniability for honest users that are receivers, that is, the accuser $\mathcal{A}$ is the sender (see Rem. 1). Thus, if one is using SignXKEM only as a receiver, then their deniability is guaranteed.

The proof for receiver deniability follows almost immediately from the proof given for strong local and global deniability of RingXKEM in App. G.3. To prove receiver deniability, the simulator must process the (possibly maliciously generated) handshake message $\rho = (ct_r, ct_{r,t}, ct_{ske})$ without the receiver's KEM decapsulation keys. The robustness of the SKE scheme guarantees that there is only one SKE key $K_{ske}$ that properly decrypts $ct_{ske}$. Since the KDF is modeled as a random oracle, the simulator searches for any input with output $K \parallel K_{ske}$. If so, it outputs $K$, so that the same $K_{ske}$ is used by the sender and the receiver. Since the proof is almost identical to that of RingXKEM, we omit the proof of the following lemma statement. We note that similarly to RingXKEM, we limit the quantum accuser to only access the random oracle classically (see discussion at the end of Sec. 5.3).

**Lemma 16.** Assume the key derivation function KDF is modeled as a quantum random oracle, the KEM scheme is correct, and the SKE scheme is correct and robust. Then, the SignXKEM protocol is strongly global deniable against malicious accusers, restricted to be senders, with respect to the leakage function $L_{leak}$ for $leak = high$ if the one-time prekey bundles are never depleted, and $leak = med$ otherwise, under the assumption that the accuser only accesses the random oracle classically.

# I. Omitted Details for Ring Signature Constructions

In this section, we include omitted details in the constructions of FalconRS and MayoRS.

## I.1. Falcon-based Ring Signature

In order to formalize the deniability of FalconRS, we introduce more thoroughly the different components underlying Falcon, and recall useful preliminaries for lattices.

### I.1.1. Lattices

In this section, we recall useful definitions and lemmas for instanciating Falcon. We follow notations from [GJK24a].

**Max-log distance.** We will make use of the max log distance between distributions through this section.

**Definition 24 (Max-log distance).** Let $\mathcal{P}, \mathcal{Q}$ two distributions over the same countable support $\text{Supp}(\mathcal{P})$. The max log distance between $\mathcal{P}$ and $\mathcal{Q}$ is

$$ \Delta_{\text{ML}}(\mathcal{P}, \mathcal{Q}) = \max_{x \in \text{Supp}(\mathcal{P})} |\log \mathcal{P}(x) - \log \mathcal{Q}(x)| $$

**Linear algebra.** We use lower (resp. upper) case bold fonts $\mathbf{v}$ (resp. $\mathbf{M}$) for vectors (resp. matrices). The vectors are in the column form and we use $v_i$ (resp. $\mathbf{m}_i$) to indicate the $i$-th entry (resp. column) of $\mathbf{v}$ (resp. $\mathbf{M}$).

For $\mathbf{v} \in \mathbb{Z}^n$, we note $\|\mathbf{v}\|_2$ its euclidean norm. For $\mathbf{M} \in \mathbb{Z}^{m \times m}$, we note $\|\mathbf{M}\|_{\text{GS}}$ the maximal 2-norm of the Gram-Schmidt orthogonalization of the column vectors of $\mathbf{M}$.

Throughout this work, for a fixed power-of-two $n$, we consider the polynomial ring $\mathcal{R} = \mathbb{Z}_q[x]/(x^n + 1)$. We also note

$$ \mathcal{R}_q = \mathcal{R}/(q\mathcal{R}). \text{ For a vector } \mathbf{u} \in \mathcal{R}_q^\ell, \bar{\mathbf{u}} \in \mathbb{Z}^{n\ell} = \begin{bmatrix} u_1 \\ \vdots \\ u_{n\ell} \end{bmatrix} \text{ the coefficient embedding of } \mathbf{u}. \text{ We define the norm of } \mathbf{u} \in \mathcal{R}_q^\ell \text{ as} \\ \|\mathbf{u}\| := \|\bar{\mathbf{u}}\|_2. $$

**Definition 25 (Anticirculant matrix).** For a polynomial $u \in \mathcal{R}$, the anticirculant matrix of $u$ is defined as

$$ \mathcal{A}(u) = \begin{bmatrix} u_1 & u_2 & \dots & u_n \\ -u_n & u_1 & \dots & u_{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ -u_2 & -u_3 & \dots & u_1 \end{bmatrix} $$
**Lattice.** A lattice in $m$-dimension Euclidean space $\mathbb{R}^m$ is a discrete set

$$ \Lambda(\mathbf{b}_1, \dots, \mathbf{b}_n) = \left\{ \sum_{i=1}^{n} x_i \mathbf{b}_i \mid x_i \in \mathbb{Z} \right\} $$

of all integral combinations of $n$ linearly independent vectors $\mathbf{b}_1, \dots, \mathbf{b}_n \in \mathbb{R}^m$.

We are specifically interested in NTRU lattices, that underly Falcon. They are defined over $\mathbb{R}^{2n}$ by polynomials $f, g \in \mathbb{R}$, and $h = g \cdot f^{-1}$ as the coefficient embeddings of the module

$$ \Lambda_h = \{(u, v) \in \mathbb{R}^2, \text{s.t. } u \cdot h + v = 0 \text{ mod } q\} $$

Equivalently, $\Lambda_h$ is generated by the columns of a matrix $\mathbf{B}_h = \begin{bmatrix} \mathbf{I}_n & 0 \\ \mathcal{A}(h) & q\mathbf{I}_n \end{bmatrix}$. A trapdoor for this lattice is a short basis

$$ \mathbf{B} = \begin{bmatrix} \mathcal{A}(f) & \mathcal{A}(F) \\ \mathcal{A}(g) & \mathcal{A}(G) \end{bmatrix} \quad \text{where the polynomials } f, g, F, G \in \mathbb{R} \text{ are relatively short and } f \cdot G - g \cdot F = 0 \text{ mod } q. $$

Falcon relies on a trapdoor sampler, that generates a short matrix $\mathbf{B}$.

**Definition 26** (NTRU trapdoor generation). An NTRU trapdoor generation algorithm $\text{TpdGen}()$ samples a public key $h \in \mathbb{R}_q \setminus \{0\}$, and a trapdoor $(f, g, F, G) \in \mathbb{R}^4$ such that $\mathbf{B}_h$ and $\mathbf{B}$ generate the same matrix and $\|\mathbf{B}_{f,h}\|_{\text{GS}} \le \alpha \cdot \sqrt{q}$.

We assume the ring $\mathbb{R}$, a target quality $\alpha \ge 1$, and a modulus $q$ are provided as public parameters.

**Gaussian sampling.** For a positive real $\sigma$, let $\rho_{\sigma}(\mathbf{z}) = \exp(-\frac{\|\mathbf{z}\|^2}{2\sigma^2})$. The discrete Gaussian distribution of standard deviation $\sigma$ over a lattice $\Lambda$, centered in $\mathbf{c}$, is defined by its probability distribution function $\mathcal{D}_{\Lambda, \sigma, \mathbf{c}}(\mathbf{z}) = \frac{\rho_{\sigma}(\mathbf{z}-\mathbf{c})}{\sum_{\mathbf{z}' \in \Lambda} \rho_{\sigma}(\mathbf{z}'-\mathbf{c})}$ for $\mathbf{z} \in \Lambda$. We may omit $\mathbf{c}$ when it is 0.

Falcon's security hinges on the sampling of Gaussian vectors over the public lattice generated by $\mathbf{B}_h$, by leveraging the trapdoor $\mathbf{B}$.

**Falcon's Gaussian sampler.** Falcon relies on the FFT Gaussian sampler [DP15; Pre15], and adapts it to cope with real-world constraints, by tail-cutting internal variables, using floating-point arithmetic, and introducing a polynomial approximation. Looking forward, while these approximations introduce some bias, we will prove the deniability of our scheme by bounding the bias of tail cuts with statical arguments, and operation approximations with relative errors.

### I.1.2. Formal Security Analysis

The proof of deniability of our scheme requires analyzing in depth the preimage sampler of Falcon, and notably the impact of tail cuts, floating points, and polynomial approximations.

We wish to prove that FalconRS is deniable for one signature ($Q = 1$), and rely on Lemma 11 to prove deniability for $Q$ signatures. We will show for this that tail cuts create a small discrepancy between the support of the concrete preimage sampler and the arbitrary elements sampled in Ln. 7 that translates into a small term $\delta$. The remaining biases introduced by floating point and approximations can then be analyzed with relative errors on distributions, and translate into the term $\mu$ of our deniability notion.

Before moving to a formal statement, we introduce notations for the preimage sampler, corresponding to the successive introduction of optimizations. We note PreSmp the concrete preimage of Falcon, with tail cuts, floating-point, polynomial approximation; PreSmp$^{\text{tl}}$ where only tail cuts are introduced; and finally PreSmp$^{\text{ideal}}$ the idealized preimage sampler, with no practical optimization.

**Theorem 1** (Deniability of FalconRS). FalconRS is $(\mu, \delta)$-deniable for $Q = 1$, assuming that $H$ is a random oracle, where $\mu = \exp(\Delta_f)^{2C} \cdot \exp(\Delta_{FFO})^{2C} \cdot \left(\frac{1+\varepsilon}{1-\varepsilon}\right)^{2C}$ and $\delta = 2^{-\lambda} + (1+\mu) \cdot \delta_{\text{tl}}$, where

* Noting $p_{\text{rej}} := \max_{\mathbf{B}} \text{Pr}[\| (u_j)_i, v + c \| > \beta; u_1 \leftarrow \chi_u, (u_0, v) \leftarrow \text{PreSmp}(\mathbf{B}, \sigma, -c), c \stackrel{s}{\leftarrow} \mathbb{R}_q]$ and take $C$ as the smallest integer verifying $(C \cdot 2^{-\kappa} + p_{\text{rej}})^C < 2^{-\lambda}$.

* $\Delta_f = \max_{\mathbf{B}, \sigma, c} \Delta_{\text{ML}}(\text{PreSmp}(\mathbf{B}, \sigma, c), \text{PreSmp}^{\text{tl}}(\mathbf{B}, \sigma, c))$

* $\Delta_{FFO} = \max_{\mathbf{B}, \sigma, c} \Delta_{\text{ML}}(\text{PreSmp}^{\text{ideal}}(\mathbf{B}, \sigma, c), \mathcal{D}_{\Lambda(\mathbf{B}), \sigma, c})$

* $\delta_{\text{tl}} = s + o(s^2)$ where

$$ \begin{aligned} -s &= 2C \cdot \left( 2e^{-\frac{\eta'^2}{2\sigma^2}} + 2n \cdot 2e^{-\frac{\eta^2}{2\sigma^2}} \cdot \frac{1+\varepsilon/(2n)}{1-\varepsilon/(2n)} \right) \\ -\eta, \eta' \text{ are the bounds used for the tail cuts performed in FalconRS respectfully for } \chi_u \text{ and within PreSmp} \end{aligned} $$

* $\varepsilon \in [0, 1)$ is such that $\sigma \ge \alpha \sqrt{q} \cdot \eta_{\varepsilon}(\mathbb{Z}^{2n})$.

*Proof.* We proceed with a series of hybrids starting from the game $\text{Game}_{\text{RS},0,\mathcal{A}}^{\text{Deny}}(1^{\lambda}, Q = 1)$.
**Hybrid<sub>1</sub>.** This is the original deniability game from Alg. 7 Game<sub>Deny RS,0, A</sub>(1<sup>λ</sup>, Q), where the first signer signs the message.

**Hybrid<sub>2</sub>.** In this hybrid, we constrain the number of restarts during signing to be at most C. Let us note $p_{rej} := \max_B \text{Pr}[\|(u_j)_i, v + c\| > \beta; z_1 \leftarrow \chi_u, (u_0, v) \leftarrow \text{PreSmp}(\mathbf{B}, \sigma, -c), c \leftarrow \mathcal{R}_q]$ and take C as the smallest integer verifying $(C \cdot 2^{-\kappa} + p_{rej})^C < 2^{-\lambda}$.

We can bound the probability of restart conditioned on previous restarts. After i restarts, the probability of starting again is bounded by:

* Sampling again a salt that was previously sampled: this happens with probability less than $i \cdot 2^{\kappa}$.

* When the salt is fresh, then c is sampled independently of the previous rejects and we can bound the probability of reject by $p_{rej}$.

The probability of performing more than C restarts can thus be bounded by $\prod_{i=0}^{C-1} (i \cdot 2^{\kappa} + p_{rej}) < (C \cdot 2^{\kappa} + p_{rej})^C$.

By definition of C, the probability of performing more than C restarts is thus bounded by $2^{-\lambda}$ and we deduce:

$$|\text{Adv}_{\mathcal{A}}^{\text{Hybrid}_1} - \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_2}| \le 2^{-\lambda}$$

**Hybrid<sub>3</sub>.** In this hybrid, we remove the use of floating-points and polynomial approximation in the sampler, i.e. we replace the use of PreSmp with PreSmp<sup>II</sup>.

Previous works [How+20; Pre17] noted that using polynomial approximations and floating-point simply introduced a small relative error compared to the original sampler.

For each of the C uses of the sampler, we note we have $\Delta_f = \max_{\mathbf{B}, \sigma, c} \Delta_{\text{ML}}(\text{PreSmp}(\mathbf{B}, \sigma, c), \text{PreSmp}^{\text{II}}(\mathbf{B}, \sigma, c))$, and we obtain

$$\text{Adv}_{\mathcal{A}}^{\text{Hybrid}_2} \le \exp(\Delta_f)^C \cdot \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_3}$$

**Hybrid<sub>4</sub>.** In this hybrid, we remove the tail cuts performed in the signing procedure, and replace the tailcut distributions by ideal ones. In particular, we replace PreSmp<sup>II</sup> with the idealized PreSmp<sup>ideal</sup>.

Tail cuts are performed in two places: (i) in the sampling of the $u_i$ at Ln. 7, and (ii) within the preimage sampler PreSmp<sup>II</sup>.

The tail cuts used in Falcon's preimage sampler are all within a sub-primitive called SamplerZ, that samples a Gaussian over $\mathbb{Z}$, for which we recall the ideal functionality in Alg. 12. In order to sample a preimage from $\mathcal{D}_{\Lambda(\mathbf{B}), \sigma, c}$ for a target c, the FFO sampler calls twice SamplerZ for each leaf of a secret tree. SamplerZ takes as input a standard deviation $\sigma$ and a center $\mu$ and should return an element sampled from $\mathcal{D}_{\mathbb{Z}, \sigma, \mu}$. For concrete implementation, the half-Gaussian $\chi$ is implemented using a CDT table that is tailcut. Let us note SamplerZ<sup>tc</sup> the sampler where $\chi$ is tailcut to an interval $[0, \eta]$. Equivalently, it implies that SamplerZ<sup>tc</sup> samples elements from the distribution $\mathcal{D}_{\mathbb{Z}, \sigma, \mu}$ tailcut to $\lfloor \mu \rfloor + [-\eta, \eta + 1]$.

<caption>**Algorithm 12** Falcon Gaussian sampler for $\mathcal{D}_{\mathbb{Z}, \sigma, \mu}$</caption>

1: **function** SamplerZ<sup>ideal</sup>(μ, σ') **then** Assume that σ' ∈ [σ<sub>min</sub>, σ<sub>max</sub>]
2: &nbsp;&nbsp;&nbsp;&nbsp;r ← μ - ⌊μ⌋
3: &nbsp;&nbsp;&nbsp;&nbsp;ccs ← σ<sub>min</sub>/σ'
4: &nbsp;&nbsp;&nbsp;&nbsp;**while** true **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;z<sub>0</sub> ← χ ▶ Half-Gaussian distribution of parameter σ<sub>max</sub>
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b ← {0, 1}
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;z := b + (2b - 1) · z<sub>0</sub>
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x := (z - r)<sup>2</sup> / (2σ<sup>2</sup>) - z<sub>0</sub><sup>2</sup> / (2σ<sub>max</sub><sup>2</sup>)
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if B<sub>css</sub>·exp(-x) = 1 **then**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return z + ⌊μ⌋

We rely on a lemma allowing to bound the statistical distance between $\mathcal{D}_{\mathbb{Z}, \sigma, \mu}$ and its tailcut version.

**Lemma 17** (Adapted from Lemma 4.3 and 4.4 of [Lyu12]). For any vector $\mathbf{v} \in \mathbb{R}^m$, $\mu \in \mathbb{R}^m$ and $r > 0$, $\sigma \ge \eta_\varepsilon(\mathbb{Z}^m)$, we have

$$\text{Pr}[|\langle \mathbf{z} - \mu, \mathbf{v} \rangle| \ge r; \mathbf{z} \leftarrow \mathcal{D}_{\mathbb{Z}^m, \sigma, \mu}] \le 2e^{-\frac{r^2}{2|\mathbf{v}|^2 \sigma^2}} \cdot \frac{1 + \varepsilon}{1 - \varepsilon}$$

As a special case for $m = 1$, $\mathbf{v} = 1$, we get:

$$\text{Pr}[|z - \mu| \ge r; z \leftarrow \mathcal{D}_{\mathbb{Z}, \sigma, \mu}] \le 2e^{-\frac{r^2}{2\sigma^2}} \cdot \frac{1 + \varepsilon}{1 - \varepsilon}$$

If $\mu = 0$, These formulas hold for $\varepsilon = 0$.
Proof. Looking at the proof of Lemma 4.3 in [Lyu12], we can see that it straightforwardly adapts to the case of non-centered Gaussians up to an additional factor $\frac{\rho_{\sigma}(\mathbb{Z}^m)}{\rho_{\sigma}(\mathbb{Z}^{m-\mu})}$.

Additionally, $\frac{\rho_{\sigma}(\mathbb{Z}^m)}{\rho_{\sigma}(\mathbb{Z}^{m-\mu})} \le \frac{1+\varepsilon}{1-\varepsilon}$ by [MR04, Lemma 4.4].

We can bound the probability of the tail cuts occuring in our scheme.

□

* First, the tailcut of $\chi_u$ has a probability bounded by $2e^{-\frac{\eta^2}{2\sigma^2}}$, and note that this distribution is sampled at most C times.

* The tail cuts in SamplerZ have a probability bounded by $2e^{-\frac{\eta^2}{2\sigma_{\max}^2}} \cdot \frac{1+\varepsilon}{1-\varepsilon}$, noticing that $\sigma_{\max} \ge \sigma_{\min} \ge \sigma/(\alpha\sqrt{q}) \ge \eta_{\varepsilon}(\mathbb{Z}^{2n}) \ge 2n \cdot \eta_{\varepsilon}(\mathbb{Z})$, and these distributions are sampled at most C $\cdot 2n$ times.

We deduce a bound on $\text{Adv}_{\mathcal{A}}^{\text{Hybrid}_3}$:

$$ \begin{aligned} & \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_3} \\ & \le \frac{1}{1 - C \cdot \left( 2e^{-\frac{\eta^2}{2\sigma^2}} + 2n \cdot 2e^{-\frac{\eta^2}{2\sigma_{\max}^2}} \cdot \frac{1+\varepsilon/(2n)}{1-\varepsilon/(2n)} \right)} \cdot \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_4} \\ & \le \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_4} + s + o(s^2) \end{aligned} $$

$$ \text{with } s = C \cdot \left( 2e^{-\frac{\eta^2}{2\sigma^2}} + 2n \cdot 2e^{-\frac{\eta^2}{2\sigma_{\max}^2}} \cdot \frac{1+\varepsilon/(2n)}{1-\varepsilon/(2n)} \right) < 1. $$

Hybrid$_5$. In this hybrid, we replace the preimage output of PreSmp$^{ideal}(\mathbf{B}_0, \sigma, -c')$ with $\mathcal{D}_{\Lambda(\mathbf{B}_0), \sigma, -c'}$.

We note that the FFO sampler used within Falcon does not perfectly sample from $\mathcal{D}_{\Lambda(\mathbf{B}_0), \sigma, -c'}$ for a target $c'$. Indeed, the use of discrete Gaussians internally slightly bias the sampler, due to their slightly varying mass depending on their center. We recall Lemma 18 bounding this difference for the Klein sampler, and argue by analogy that the FFO sampler distribution is close to $\mathcal{D}_{\Lambda(\mathbf{B}_0), \sigma, -c'}$.

**Lemma 18** (Relative error of Klein sampler [Pre15; Pre17]). Let $n$ a positive integer, and $\varepsilon \in (0, 1/4)$. Then, the relative error of the Klein sampler KleinSmp($\mathbf{B}$, $\sigma$, $c$) for any basis $\mathbf{B} \in \mathbb{Z}^{m \times n}$, standard deviation $\sigma \ge \eta_{\varepsilon}(\mathbb{Z}^n) \cdot \|\mathbf{B}\|_{\text{GS}}$, and arbitrary syndrome $c \in \mathbb{Z}^m$ is bounded by

$$ \Delta_{\text{ML}}(\text{KleinSmp}(\mathbf{B}, \sigma, c), \mathcal{D}_{\Lambda(\mathbf{B}), \sigma, c}) \le n \cdot \log \left( \frac{1 + \varepsilon/n}{1 - \varepsilon/n} \right) \approx 2\varepsilon. $$

We obtain:

$$ \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_4} \le \exp(\Delta_{\text{FFO}})^C \cdot \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_5}, $$

where we have that

$$ \Delta_{\text{FFO}} = \max_{\mathbf{B}, \sigma, c} \Delta_{\text{ML}}(\text{PreSmp}^{\text{ideal}}(\mathbf{B}, \sigma, c), \mathcal{D}_{\Lambda(\mathbf{B}), \sigma, c}). $$

Hybrid$_6$. In this hybrid, we exchange the roles of the users $u_0$ and $u_1$, i.e. instead of running the preimage sampler for user $u_0$, we sample a Gaussian from $\mathcal{D}_{\mathbb{Z}^n, \sigma}$ for user $u_1$ and run $\mathcal{D}_{\Lambda(\mathbf{B}_1), \sigma, -(c-h_0z_0)}$.

Concretely, we need to show that the signature distribution is close in these two cases, that is that the two distributions below are at a close distance:

* $(z_0, z_1, v + (c - h_0z_0))$ where $z_0 \leftarrow \mathcal{D}_{\mathbb{Z}^n, \sigma}$, $(z_1, v) \leftarrow \mathcal{D}_{\Lambda(\mathbf{B}_1), \sigma, -(c-h_0z_0)}$

* $(z_0, z_1, v + (c - h_1z_1))$ where $z_1 \leftarrow \mathcal{D}_{\mathbb{Z}^n, \sigma}$, $(z_0, v) \leftarrow \mathcal{D}_{\Lambda(\mathbf{B}_0), \sigma, -(c-h_1z_1)}$

We rely on Theorem 4.1 from [Gen+20].

**Lemma 19** (Adapted from Theorem 4.1 of [Gen+20]). For any $\varepsilon \in [0, 1]$, a full-rank lattice $\Lambda$, and $\sigma \ge \eta_{\varepsilon}(\Lambda)$, and matrix $\mathbf{T}$, any $c$ in $\mathbb{R}^n$, the max-log distance between the distributions

* $(x_0, x_1)$ where $x_1 \leftarrow \mathcal{D}_{\mathbb{Z}^n, \sigma}$ and $x_1 \leftarrow \mathbf{T} \cdot x_0 + \mathcal{D}_{\Lambda, \sigma, c-\mathbf{T} \cdot x_0}$

* $(x_0, x_1) \leftarrow \mathcal{D}_{\Lambda', \sigma, c}$ where $\Lambda' := \{(x_0, \mathbf{T} \cdot x_0 + x_1); x_0 \in \mathbb{Z}^n, x_1 \in \Lambda\}$

is bounded by $\log \frac{1+\varepsilon}{1-\varepsilon}$.
We conclude by applying twice Lemma 19 successively with the lattice of user 0 and then of user 1, and T successively being equal to $\mathcal{A}(-h_1)$ and $\mathcal{A}(-h_0)$. We conclude by noticing that the lattice $\Lambda'$ in Lemma 19 is equal in both cases:

$$ \begin{aligned} & \{(z_0, z_1, v - h_0 z_0) \text{ s.t. } h_1 z_1 + v = 0 \mod q\} \\ &= \{(z_0, z_1, v) \text{ s.t. } \sum_i h_i z_i + v = 0 \mod q\} \\ &= \{(z_0, z_1, v - h_1 z_1) \text{ s.t. } h_0 z_0 + v = 0 \mod q\} \end{aligned} $$

The max-log distance between the two signature distributions is then $2 \log \frac{1+\varepsilon}{1-\varepsilon}$.

Finally, by the properties of the max-log distance:

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_5} \le \left( \frac{1 + \varepsilon}{1 - \varepsilon} \right)^{2C} \cdot \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_6} $$

**Hybrid$_7$.** From this point, hybrids consist in re-establishing the concrete signing for user $u_1$. This hybrid replaces the distribution $\mathcal{D}_{\Lambda(B_1), \sigma, -c'}$ by PreSmp($B_1$, $\sigma, -c'$).

As for Hybrid$_5$, we obtain a bound

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_6} \le \exp(\Delta_{\mathrm{FFO}})^C \cdot \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_7} $$

**Hybrid$_8$.** This hybrid re-introduces the tail cuts.

Similarly to the analysis in Hybrid$_4$, we bound the probability of the tails that are cut. Then, by expressing the tailcut distribution as following the ideal distribution conditioned on a smaller support, we obtain

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_7} \le \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_8} + C \left( 2e^{-\frac{\eta'}{2\sigma^2}} + 2n \cdot 2e^{-\frac{\eta^2}{2\sigma_{\min}^2}} \cdot \frac{1 + \varepsilon/(2n)}{1 - \varepsilon/(2n)} \right). $$

**Hybrid$_9$.** This hybrid reintroduces floating-point and polynomial approximations.

As in Hybrid$_3$, we get

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_9} \le \exp(\Delta_f)^C \cdot \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_10} $$

**Hybrid$_{10}$.** We finally remove the constraint on the number of rejection restarts. The advantage of the adversary can only be increased by this change:

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_{10}} \le \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_{10}} $$

Hybrid$_{10}$ is exactly the Game$_{RS,1,\mathcal{A}}(1^{\lambda}, Q = 1)$ and we obtain the theorem statement by collecting all the bounds. □

### I.1.3. Concrete Parameters

We rely on the same ring, key generation, and preimage sampler as Falcon-512:

* the degree of the polynomial ring is $n = 512$, and modulo is $q = 12289$.

* the key quality is $\alpha = 1.17$.

* the signing standard deviation is $\sigma = 165.736617183$ (corresponding to $\varepsilon \approx 2^{-35.5}$ [GJK24a]).

* the salt are sampled from $\{0, 1\}^\kappa$ with $\kappa = 320$.

* The preimage sampler uses as implementation constants $\sigma_{\min} = 1.277833697$, $\sigma_{\max} = 1.8205$. For the internal randomness tailcut, $\eta = 18$.

For a ring of two users, we select the check bound as $\beta = 1.1 \cdot \sqrt{3n\sigma}$. We also pick the new tailcut parameter $\eta' := [\sqrt{70} \cdot \log(2) \cdot \sqrt{2} \cdot \sigma] \approx 1633$. We then evaluate the security of our scheme with the lattice-estimator.

As for the deniability of our scheme, we evaluate the different elements of Theorem 1,

* Following the analysis of [Pre+22, Section 2.5.2], the use of floating points and polynomial approximations introduces a small error: $\exp(\Delta_f) \le 1 + 2^{-31}$.

* By analogy with the Klein sampler, the bias of the FFO sampler is of the order $\exp(\Delta_{\mathrm{FFO}}) \le 1 + 2\varepsilon \approx 1 + 2^{-34.5}$.

* The probability of rejection can be evaluated with Theorem 1 to $p_{\mathrm{rej}} \approx 2^{-21.4}$. Then, it is sufficient to take $C = 6$ to ensure $(C \cdot 2^{-\kappa} + p_{\mathrm{rej}})^C \le 2^{-128}$ in Theorem 1.
**Lemma 20.** With the same notations as Theorem 1, $p_{rej} \le \exp(\Delta_f) \cdot \exp(\Delta_{FFO}) \cdot (\frac{1+\varepsilon}{1-\varepsilon}) \cdot p_{\beta} + \delta$ where we define $p_{\beta} = \text{Pr} [\| (z_j)_j, v \| > \beta; (z_0, z_1, v) \leftarrow \mathcal{D}_{\mathbb{Z}^{3n}, \sigma}]$.

Remark that $p_{\beta}$ can be bounded by $k^{3n} \cdot \exp(\frac{3n}{2}(1-k^2))$ where $k = \beta/(\sqrt{3n\sigma})$ using [Lyu12, Lemma 4.4].

*Proof.* As in the proof of Theorem 1, we can bound the effect of floating point, polynomial approximation, tail cuts, and the bias of the FFO sampler: $p_{rej} \le \Delta_f \cdot \Delta_{FFO} \cdot (\frac{1+\varepsilon}{1-\varepsilon}) \cdot p_{rej}^{\text{ideal}} + \delta$ where we define $p_{rej}^{\text{ideal}} = \max_B \text{Pr}[\| (z_j)_j, v + c \| > \beta; z_1 \leftarrow \mathcal{D}_{\mathbb{Z}^{3n}, \sigma}, (z_0, v + c) \leftarrow \mathcal{D}_{\Lambda(B), \sigma, -c}, c \stackrel{\$}{\leftarrow} \mathcal{R}_q]$.

Now, we rely on a lemma showing that the syndrome $c = h_1 \cdot z_1 + v$ is close to uniform when $(z_1, v)$ are Gaussians of parameter $\sigma$, to remove the conditioning on $c$ in $p_{rej}^{\text{ideal}}$.

**Lemma 21 (Adapted from Lemma 5.2 [GPV08], Cor. 2 [GJK24a]).** For $\varepsilon \in (0, \frac{1}{2})$, $\sigma \ge \eta_{\varepsilon}(\Lambda_h)$, consider the distributions $\mathcal{P} = \mathcal{U}(\mathcal{R}_q)$ and $\mathcal{Q}$ the distribution of $u \cdot h + v$, where $u, v \leftarrow \mathcal{D}_{\mathcal{R}, \sigma}$. Then,

$$ \Delta_{\text{ML}}(\mathcal{P}, \mathcal{Q}) \le \log \frac{1+\varepsilon}{1-\varepsilon} $$

Applying the above lemma, we deduce that $p_{rej}^{\text{ideal}} \le \frac{1+\varepsilon}{1-\varepsilon} \cdot p_{\beta}$, which concludes the proof. □

Following the above analysis of the terms of Theorem 1, we deduce that FalconRS is deniable with concrete terms:

$$ \mu = 1 + 2^{-27} $$

$$ \delta = 2^{-57} $$

## I.2. MAYO-based Ring Signature

We now formally introduce our ring signature based on MAYO. We reuse the same parameter names as the original MAYO specification [Beu+24]. Viewing MAYO as a hash-then-sign signature scheme, we can apply generic transformations from [AOS02] to obtain an efficient ring signature.

Recall that MAYO is designed over quadratic maps. It first chooses a map $\mathcal{P}: \mathbb{F}_q^n \to \mathbb{F}_q^m$ with trapdoor tp as public key, from which is derived a larger map $\mathcal{P}^*: \mathbb{F}_q^{kn} \to \mathbb{F}_q^m$. To sign message M we compute a target $\mathbf{t} = H(M, \text{salt})$ (where salt is a random value), and then we sample a preimage $u$ such that $\mathcal{P}^*(\mathbf{u}) = \mathbf{t}$, leveraging the trapdoor tp.

For the matter of abstraction and re-use within a ring signature, we proceed as for FalconRS and denote $\text{PreSmp}(\mathbf{tp}, \mathbf{t}) \to \mathbf{u}$ the random procedure of MAYO sampling a pre-image $\mathbf{u}$ given a target $\mathbf{t}$, that is sampling $\mathbf{u}$ such that $\mathcal{P}^*(\mathbf{u}) = \mathbf{t}$.

We finally describe in Alg. 13 the ring signature MayoRS obtained from MAYO using Abe, Ohkubo, and Suzuki transform.

### I.2.1. Security Analysis

**Theorem 2 (Unforgeability of MayoRS).** MayoRS is unforgeable assuming the unforgeability of MAYO.

Formally, let $\mathcal{A}$ be an adversary against the unforgeability of MayoRS making at most $Q_s$ calls to the signing oracle, at most $Q_H$ random oracle queries, and with at most $N$ generated keypairs. Then, there exists an adversary $\mathcal{B}$ against the unforgeability of MAYO, running in time $\mathcal{T}(\mathcal{B}) \approx \mathcal{T}(\mathcal{A})$, such that

$$ \text{Adv}_{\mathcal{A}}^{\text{RS-UF}} \le N \cdot Q_H \cdot \text{Adv}_{\mathcal{B}}^{\text{UF}} + 2^{-\kappa} \cdot Q_s \cdot (Q_s + Q_H) + 2^{-2\lambda} \cdot Q_H^2 $$

*Proof.* We proceed with a series of hybrids. Our proof roughly follows ideas presented in [LAZ19a], but improves the security loss by a factor $Q_H$ by guessing only one random oracle query, and then programming all subsequent ones, instead of guessing a pair. Additionally, we cover the introduction of a seed used for compressing the signatures when preimages are comparatively larger than seeds.

**Hybrid$_1$.** This is the original unforgeability game for a ring signature.

**Hybrid$_2$.** In this hybrid, we create a MAYO signing oracle $\text{OSign}_i$ for each keypair $(\text{sk}_i, \text{pk}_i)_{i \in [N]}$, and we reexpress the signing oracle of MayoRS as a function of the individual $\text{OSign}_i$. We assume the existence of separate random oracles $H_i$ used within $\text{OSign}_i$, and only accessible by the challenger.

First, we fix an arbitrary message $\mu^*$.

Then, whenever the ring signature signing oracle is called on input $(i, \text{RL}, \mathbf{M})$, we sample random elements $\mathbf{u}_j \stackrel{\$}{\leftarrow} \mathbb{F}_q^n$ for $j \ne i$, $(\text{salt}', \mathbf{u}_i) \leftarrow \text{OSign}_i(\mu^*)$, as well as $\mathbf{c}_0 \stackrel{\$}{\leftarrow} \mathbb{F}_q^m$, and we sequentially compute $\mathbf{c}_{j+1} \bmod N = H(j+1 \bmod N, \text{RL}, \mathbf{M}, \mathbf{c}_j + \mathcal{P}_j(\mathbf{u}_j))$ for $j \in [N-1]$.

Finally, we compute the seed $\mathbf{H} = \mathbf{H}(0, \text{RL}, \mathbf{M}, \mathbf{c}_{N-1} + \mathcal{P}_{N-1}(\mathbf{u}_{N-1}))$, sample a salt $\mathbf{salt} \leftarrow \{0, 1\}^{\kappa}$, and program the random oracle $\mathbf{H}(0, \text{seed}, \text{salt}) = \mathbf{c}_0$.
<caption>**Algorithm 13 MAYO-based ring signature scheme**</caption>

1: **function** MayoRS.KeyGen(1<sup>λ</sup>)
2: &nbsp;&nbsp;&nbsp;&nbsp;P, tp &larr; TpdGen()
3: &nbsp;&nbsp;&nbsp;&nbsp;return (rvk := P, rsk := tp)
4: **function** MayoRS.Sign(rsk<sub>i</sub>, M, RL := {rvk<sub>j</sub>}<sub>j</sub>)
5: &nbsp;&nbsp;&nbsp;&nbsp;tp<sub>i</sub> := rsk<sub>i</sub>; {P<sub>j</sub>}<sub>j</sub> := {rvk<sub>j</sub>}<sub>j</sub>
6: &nbsp;&nbsp;&nbsp;&nbsp;salt &larr; {0, 1}<sup>κ</sup>; t &larr; F<sub>q</sub><sup>m</sup>
7: &nbsp;&nbsp;&nbsp;&nbsp;ctx := (i + 1 mod N, RL, M, t)
8: &nbsp;&nbsp;&nbsp;&nbsp;if &lceil; i + 1 mod N = 0 &rceil; then
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;seed := H(0, RL, M, t) ∈ {0, 1}<sup>2λ</sup>; ctx := (0, seed, salt)
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c<sub>i+1</sub> mod N := H(ctx) ∈ F<sub>q</sub><sup>m</sup>
11: &nbsp;&nbsp;&nbsp;&nbsp;**for** j = i + 1, ..., N - 1, 0, ..., i - 1 **do**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u<sub>j</sub> &larr; F<sub>q</sub><sup>kn</sup>
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ctx := (j + 1 mod N, RL, M, c<sub>j</sub> + P<sub>j</sub><sup>*</sup>(u<sub>j</sub>))
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if &lceil; j + 1 mod N = 0 &rceil; then
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;seed := H(ctx) ∈ {0, 1}<sup>2λ</sup>; ctx := (0, seed, salt)
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c<sub>j+1</sub> mod N := H(ctx) ∈ F<sub>q</sub><sup>m</sup>
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u<sub>i</sub> := PreSmp.tp<sub>i</sub>, t - c<sub>i</sub>)
18: &nbsp;&nbsp;&nbsp;&nbsp;**return** sig := (salt, seed, {u<sub>j</sub>}<sub>j</sub>)
19: **function** MayoRS.Verify(RL := {rvk<sub>j</sub>}<sub>j</sub>, M, sig)
20: &nbsp;&nbsp;&nbsp;&nbsp;(salt, seed, {u<sub>i</sub>}<sub>i</sub>) := sig; {P<sub>i</sub>}<sub>i</sub> := {rvk<sub>i</sub>}<sub>i</sub>
21: &nbsp;&nbsp;&nbsp;&nbsp;c<sub>0</sub> := H(0, seed, salt) ∈ F<sub>q</sub><sup>m</sup>
22: &nbsp;&nbsp;&nbsp;&nbsp;**for** j = 0, ..., N - 2 **do**
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c<sub>j+1</sub> mod N := H(j + 1 mod N, RL, M, c<sub>j</sub> + P<sub>j</sub><sup>*</sup>(u<sub>j</sub>)) ∈ F<sub>q</sub><sup>m</sup>
24: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** &lceil; seed = H(0, RL, M, c<sub>N-1</sub> + P<sub>j</sub><sup>*</sup>(u<sub>N-1</sub>)) &rceil;

The view of the adversary is identical unless the random oracle $H$ has been queried on $(0, \text{seed}, \text{salt})$ before it is programmed, which happens with probability bounded by $2^{-\kappa} \cdot Q_s Q_H$, or in case the same $\text{salt}'$ is provided twice by $\text{OSign}_i$, which happens with probability bounded by $2^{-\kappa} Q_s^2$.

Hence,

$$ \left| \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_1} - \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_2} \right| \le 2^{-\kappa} \cdot Q_s \cdot (Q_s + Q_H) $$

$\text{Hybrid}_3$. In this hybrid, we assert that if $H(0, \text{seed}, \text{salt})$ is queried for some seed, then seed cannot be returned later by the random oracle.

The advantage loss is related to the preimage resistance of the hash-function $H$. Given that seed is sampled in $\{0, 1\}^{2\lambda}$, the probability to find a preimage for a seed is less than $Q_H \cdot 2^{-2\lambda}$. As the adversary can query up to $Q_H$ seeds, we obtain:

$$ \left| \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_2} - \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_3} \right| \le 2^{-2\lambda} \cdot Q_H^2 $$

$\text{Hybrid}_4$. In this hybrid, we guess the index of the hash in the adversary's forgery that was queried first. We start by sampling $u \leftarrow [Q_H]$. We abort the game in case the index $u$ does not correspond to the hash used in the forgery that was queried first to the random oracle.

This hybrid incurs a loss $Q_H$:

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_3} \le Q_H \cdot \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_4} $$

We assert that the first hash used in a forgery will be of the form $H(i^*, RL^*, M^*, e^*)$. Indeed, the previous hybrid ensured that the only hash taking an input with a different form (i.e. taking as input seed) cannot be the first one called by the adversary.

Looking forward, observe that a forged ring signature is composed of vectors $u_i^* \in F_q^n$ such that for any $i \in [N]$, we have $P_i(u_i^*) = e_i - c_i$, where $c_i$ is a hash of the form $H(i - 1 \bmod N, \cdot)$, and $e_i$ is used as input of a hash of the form $H(i, RL, M, e_i)$. By guessing the value of $e_i$ before the corresponding $c_i$ is defined, we will then be able to program the random oracle to choose $c_i$ so as to target any value for $e_i - c_i$.

$\text{Hybrid}_4$. In this hybrid, we additionally guess the value of $i^* \in [N]$.

This reduces the adversary's advantage by an additional factor $N$:

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_3} \le N \cdot \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_4} $$
**Hybrid$_5$.** In this hybrid, after $\mathbf{e}^*$ is defined, we program all the calls to the random oracle so that the values $\mathbf{e}^* - \mathbf{c}_i$ is equal to a target of the underlying signature for user $i^*$. Concretely, whenever the random oracle is called on some input $X$ and has to output a uniform $\mathbf{c} \in \mathbb{F}_q^m$, we take an arbitrary message $\mu$, different from $\mu^*$ and any other message previously chosen. We also choose an arbitrary salt. We then program $H(X) := \mathbf{e}^* - H_i(\mu, \text{salt})$.

As $H_i$ is a random oracle only accessible to the challenger, the view of the adversary is identically distributed in this game:

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_4} = \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_5} $$

**Conclusion.** Finally, we observe that when $\mathcal{A}$ wins the game Hybrid$_4$, they output a signature verifying $\mathcal{P}_{i^*}(\mathbf{u}_{i^*}) = \mathbf{e}^* - \mathbf{c}_i = H_i(\mu, \text{salt})$ for some $\mu$, salt that were sampled in Hybrid$_5$, i.e. a forgery for the $i^*$-th keypair.

We can hence reduce the probability of the adversary winning this game to the unforgeability of MAYO by replacing the $i^*$-th keypair by the one given by the unforgeability challenger against MAYO, and by aborting in case the corruption oracle is called on index $i^*$.

Formally, there exists an adversary $\mathcal{B}$ against the unforgeability of MAYO, running in time $\mathcal{T}(\mathcal{A}) \approx \mathcal{T}(\mathcal{B})$, such that:

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_5} \le \mathrm{Adv}_{\mathcal{B}}^{\mathrm{UF}} $$

□

**Theorem 3 (Deniability of MayoRS).** *MayoRS is (1, 2N · B)-deniable where $B = \frac{q^{k-(n-o)}}{q-1} + \frac{q^{m-ko}}{q-1}$, assuming one challenge query is allowed.*

*Proof.* In order to prove the deniability of MayoRS, we will show that we can replace the uniform sampling of non-signers, by the preimage sampling function of MAYO to make the signature procedure independent of the actual signer.

Looking in more detail at the preimage sampler of MAYO, we can see that given a target $\mathbf{t}$, it samples signatures of the form $(\mathbf{V} + \mathbf{X}\mathbf{O}^t, \mathbf{X})$, where $\mathbf{V} \in \mathbb{F}_q^{k \times (n-o)}$ is uniformly distributed, under the condition that an associated matrix $\mathbf{A} \in \mathbb{F}_q^{m \times ko}$ (derived from $\mathbf{V}$ and the keypair pk, sk) is full-rank, and $\mathbf{X}$ is uniformly sampled among the possible preimages of $\mathbf{t}$ of the form $(\mathbf{V} + \mathbf{X}\mathbf{O}^t, \mathbf{X})$.

It can be seen that when $\mathbf{t}$ is uniformly distributed and obtaining $\mathbf{V}, \mathbf{X}$ with the preimage sampler, then the joint distribution of (pk, sk, $\mathbf{V}$, $\mathbf{X}$, $\mathbf{t}$) is identical to first sampling (pk, sk, $\mathbf{V}$) such that the associated matrix $\mathbf{A}$ is full-rank, uniformly sampling $\mathbf{X}$, and taking $\mathbf{t}$ to be the evaluation of $\mathcal{P}$ on $(\mathbf{V} + \mathbf{X}\mathbf{O}^t, \mathbf{X})$.

Formally, we will introduce a series of hybrids to prove deniability, starting from the game where the signer $b$ is signing.

**Hybrid$_2$.** In this hybrid, we sample a matrix $\mathbf{V}_j$ for each user uniformly at random. When the signing oracle is called for the ring $(i, j)$ and signer $i$, we replace the random sampling of $\mathbf{u}_j$ by $(\mathbf{V}_j + \mathbf{X}\mathbf{O}^t, \mathbf{X})$, where $\mathbf{X}$ is uniformly sampled.

As we only allow one signing query, this change does not change the distribution of the view of the adversary, and there is no advantage loss as the preimage for user $j$ is still uniformly sampled.

$$ \mathrm{Pr} \left[ \mathrm{Game}_{\mathrm{RS},0,\mathcal{A}}^{\mathrm{Deny}} (1^\mathrm{d}, Q) = 0 \right] = \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_2} $$

**Hybrid$_3$.** In this hybrid, we replace the matrices $\mathbf{V}_i$ and individual keypairs and instead sample them such that each keypair and $\mathbf{V}_i$ has an associated matrix $\mathbf{A}_i$ that is full-rank.

Let us note $E$ the event that all the matrices $\mathbf{A}_j$ are full-rank. Then, we can reexpress the adversary's advantage in Hybrid$_2$:

$$ \begin{aligned} \mathrm{Pr} [\mathrm{Hybrid}_2(\mathcal{A}) = 0] &= \mathrm{Pr} [\mathrm{Hybrid}_2(\mathcal{A}) = 0 | E] \cdot \mathrm{Pr}[E] \\ &= \mathrm{Pr}[\mathrm{Hybrid}_3(\mathcal{A})=0] \\ &\quad + \mathrm{Pr} [\mathrm{Hybrid}_3(\mathcal{A}) = 0 | \neg E] \cdot \mathrm{Pr}[\neg E] \end{aligned} $$

We deduce an upper bound on the advantage loss between the Hybrid$_2$ and Hybrid$_3$:

$$ |\mathrm{Pr}[\mathrm{Hybrid}_2(\mathcal{A}) = 0] - \mathrm{Pr}[\mathrm{Hybrid}_3(\mathcal{A}) = 0]| \le \mathrm{Pr}[\neg E] \le N \cdot B $$

where $B = \frac{q^{k-(n-o)}}{q-1} + \frac{q^{m-ko}}{q-1}$ is the probability that a given $\mathbf{A}_j$ is full-rank, and the factor $N$ appears by union-bound.

**Hybrid$_4$.** In this hybrid, when user $i$ is signing for the ring $(i, j)$, we replace the use of the matrix $\mathbf{V}_j$ with MAYO's preimage sampler, i.e., we first sample a random target $\mathbf{t}_j$ for $\mathcal{P}(\mathbf{u}_j)$ and then sample $\mathbf{u}_j$ using MAYO's preimage sampler.

We show that this change does not affect the distribution of the view of the adversary.

First, the distribution of $(pk_j, sk_j, V_j)$ is identical to the distribution of $(pk_j, sk_j, V)$ where $V$ is the matrix used by MAYO's preimage sampler. Indeed, we can see that $V$ is also sampled such that $\mathbf{A}_i$ is full-rank, conditioning on the value of $(pk_j, sk_j)$.

Then, as observed in the introduction of this proof, it is equivalent to first sample $\mathbf{X}$ uniformly, then compute the corresponding $\mathbf{t}$, or to instead sample $\mathbf{t}$ uniformly first, and then compute $\mathbf{X}_j$. We thus conclude that $(\mathbf{X}, \mathbf{t})$ follow the same distribution in Hybrid$_3$ and Hybrid$_4$.

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_3} = \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_4} $$
**Hybrid<sub>5</sub>.** In this hybrid, when the signing oracle is called on user *i* for the ring (*i*, *j*), we instead sign with user *j*.

It is easy to see at this point that when **t**, **t<sub>j</sub>** are uniformly distributed, then (t - H(H(t) + t<sub>j</sub>), t<sub>j</sub>), is identically distributed to (t - H(t<sub>j</sub>), t<sub>j</sub> - H(t)), which is itself identically distributed to (t, t<sub>j</sub> - H(H(t<sub>j</sub>) + t)), i.e. we can inverse the sampling of the contributions of *i* and *j*.

Thus, this hybrid has no advantage loss:

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_4} = \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_5} $$

**Conclusion.** Observe that Hybrid<sub>5</sub> is the exact counterpart of Hybrid<sub>4</sub> by changing the user who signed. We can then reapply the hybrids Hybrid<sub>3</sub>, Hybrid<sub>2</sub>, Hybrid<sub>1</sub> in reverse order to obtain that:

$$ \left| \mathrm{Adv}_{\mathcal{A}}^{\mathrm{Hybrid}_5} - \mathrm{Pr} \left[ \mathrm{Game}_{\mathrm{RS},1,\mathcal{A}}^{\mathrm{Deny}}(1^{\lambda}, 1) = 0 \right] \right| \le N \cdot B $$

We finally conclude the proof by collecting all the bounds.

□

### I.2.2. Alternative Parameter Sets for MayoRS

As observed in Tab. 2, MAYO parameter sets proposed for standardization offer a rather low deniability, and we provide in this section alternative parameter sets that achieve higher deniability guarantees at the cost of larger public key and signature sizes.

Interestingly, we can rapidly increase the deniability of MAYO by increasing its parameter *k*. After adapting the parameters to balance the security loss and still achieve NIST security level I, we propose three new parameter sets MAYO*, MAYO** and MAYO***. We provide concrete values for the parameters (*n*, *m*, *o*, *k*, *q*) in Tab. 9.

<table><caption>Table 9: Alternative parameter sets for MAYO with higher deniability guarantees, aiming for NIST security level I. Recall that the parameter *B* translates into ($\mu = 1, \delta = 2 \cdot N \cdot B$)-deniability. Sizes are given in Tab. 2.</caption><thead><tr><th>Scheme</th><th>(n, m, o, k, q)</th><th>Parameter B</th></tr></thead><tbody><tr><td>MAYO*</td><td>(69, 69, 9, 9, 16)</td><td>2<sup>-52</sup></td></tr><tr><td>MAYO**</td><td>(70, 70, 9, 10, 16)</td><td>2<sup>-83</sup></td></tr><tr><td>MAYO***</td><td>(78, 78, 9, 12, 16)</td><td>2<sup>-124</sup></td></tr></tbody></table>