# Revisiting PQ WireGuard: A Comprehensive Security Analysis With a New Design Using Reinforced KEMs

Keitaro Hashimoto, Shuichi Katsumata, Guilhem Niot, Thom Wiggers

► To cite this version:

Keitaro Hashimoto, Shuichi Katsumata, Guilhem Niot, Thom Wiggers. Revisiting PQ WireGuard: A Comprehensive Security Analysis With a New Design Using Reinforced KEMs. S&P 2026 - 47th IEEE Symposium on Security and Privacy, May 2026, SAN FRANCISCO, United States. hal-05444065

HAL Id: hal-05444065

https://inria.hal.science/hal-05444065v1

Submitted on 6 Jan 2026

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

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

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Revisiting PQ WireGuard:
A Comprehensive Security Analysis With a New Design Using Reinforced KEMs
Full Version

Keitaro Hashimoto*, Shuichi Katsumata*†, Guilhem Niot†, Thom Wiggers†

*National Institute of Advanced Industrial Science and Technology (AIST), Tokyo, Japan

†PQShield, https://pqshield.com

*Abstract*—WireGuard is a VPN based on the Noise protocol, known for its high performance, small code base, and unique security features. Recently, Hülsing et al. (IEEE S&P'21) presented post-quantum (PQ) WireGuard, replacing the Diffie-Hellman (DH) key exchange underlying the Noise protocol with key-encapsulation mechanisms (KEMs). Since WireGuard requires the handshake message to fit in one UDP packet of size roughly 1200 B, they combined Classic McEliece and a modified variant of Saber. However, as Classic McEliece public keys are notoriously large, this comes at the cost of severely increasing the server's memory requirement. This hinders deployment, especially in environments with constraints on memory (allocation), such as a kernel-level implementations.

In this work, we revisit PQ WireGuard and improve it on three fronts: design, (computational) security, and efficiency. As KEMs are semantically but not syntactically the same as DH key exchange, there are many (in hindsight) ad-hoc design choices being made, further amplified by the recent finding on the binding issues with PQ KEMs (Cremers et al., CCS'24). We redesign PQ WireGuard addressing these issues, and prove it secure in a new computational model by fixing and capturing new security features that were not modeled by Hülsing et al. We further propose reinforced KEM (RKEM) as a natural building block for key exchange protocols, enabling a PQ WireGuard construction where the server no longer needs to store Classical McEliece keys, reducing public key memory by 190 to 390×. In essence, we construct a RKEM named Rebar to compress two ML-KEM-like ciphertexts which may be of an independent interest.

# 1. Introduction

WireGuard [3] is a VPN protocol available for all major operating systems. It offers an efficient one-roundtrip, mutually authenticated handshake protocol following the “IK” pattern of the Noise protocol [4], based on the Diffie-Hellman (DH) key exchange. Compared to other VPNs like OpenVPN [5] or IPsec [6], it is well-known for its high performance and small code base. It implements the

entire protocol in the Linux kernel and is “cryptographically opinionated” [3] by only allowing a small set of modern cryptographic primitives.

In addition, WireGuard offers several unique security properties, those not typically considered by traditional handshake protocols and other VPNs, such as session-key uniqueness, Denial of Service (DoS) mitigation, identity hiding, and so on. These security properties, informally laid out in the original work by Donenfeld [3], has been formally (and partially) analyzed in the computational model by Dowling and Paterson [7] and Lipp et al. [8], and in the symbolic model by Donenfeld and Milner [9].

With the continuing demand for transitioning to post-quantum cryptography, Hülsing et al. [1] recently proposed a *post-quantum* variant of WireGuard (PQ WireGuard). The main technical contribution of PQ WireGuard is in the successful replacement of the DH key exchange with key-encapsulation mechanisms (KEMs). At a theoretical level, it is well-understood that one can emulate (almost) any DH key exchange by KEMs, however, this is no longer the case when considering real-world constraints.

WireGuard's handshake is designed to have as little state as possible. Additionally, it operates over UDP for performance, which does not transparently handle too-large packets. This means it requires its handshake messages to fit into a single UDP packet, which max out at 1232 B for IPv6. This makes the creation of a post-quantum version of WireGuard challenging, because the main post-quantum KEM, ML-KEM [10], is too large to replace DH within this limit. Hülsing et al. [1] overcome this by combining two different KEMs: Classic McEliece [11] and a modified, IND-CPA version of Saber [12]. Capitalizing on Classic McEliece's small ciphertext sizes and the fact that its large (long-term) public keys do not need to be transmitted during the protocol, Hülsing et al. fit the handshake in a single UDP packet. Lastly, they analyzed their PQ WireGuard's security both in the computational and symbolic models previously used by WireGuard [7], [9].
## 1.1. Our Contribution

In this paper, we revisit the PQ WireGuard protocol by Hülsing et al., improving it on three fronts: design, computational security, and efficiency. Concretely, we provide a leaner generic construction of PQ WireGuard based on a novel primitive, coined as *reinforcing* KEMs (RKEM); a special type of KEMs explained shortly. Our PQ WireGuard, instantiated with a novel lattice-based RKEM, replaces the client-side long-term public key that was a Classic McEliece key with a much shorter ML-KEM-like key. This reduces the server's public key memory requirements by 190 to $390 \times$, making PQ WireGuard easier to deploy and operate, especially in environments with constraints on memory (allocation), such as WireGuard's kernel-level implementations. We show that PQ WireGuard and RKEM are practical by implementing them and measuring their performance; our implementation and measurement results are available online.

We explain our three contributions in more detail below.

*Design.* At a high level, WireGuard is a simple DH key exchange protocol; however, under the hood, it is quite involved. Technically, it follows the “IK” pattern of the Noise protocol [4], where the exchanged session key is systematically derived by a key derivation function (KDF), taking as input the cryptographic materials generated within the protocol. In addition, a hash chain is locally maintained, authenticating the views of the client and server. WireGuard further supports an optional pre-shared (symmetric) key (PSK) to be used, enhancing the security in case all other secrets are compromised. An interested reader may refer to the detailed description in Fig. 1 for a better intuition.

While Hülsing et al. [1] replaced the DH messages by KEM public keys and ciphertexts, (in hindsight) these were handled in an ad-hoc manner. The issue is that while a KEM may *semantically* replace DH key exchange, it is *syntactically* quite different, raising the question of which values should be absorbed, and in what order, into the KDF and hash chain. This issue is further amplified by how Hülsing et al. used PSKs. They now had to use it much earlier in the protocol since, unlike a DH key exchange, a KEM lacks client-side authentication in the first round; a property used by WireGuard to attain DoS protection. This lead Hülsing et al. to absorb the PSK *twice* into the KDF (cf. Fig. 1). While, subsequently, there was work on *post-quantum* (PQ) Noise [13], it did not incorporate the later-discovered concerns surrounding KEM binding [2] nor discuss how to use PSKs. Consequently, while the “IK” pattern of Noise readily yields WireGuard, no such analog exists in the post-quantum setting.

In our work, we revisit Hülsing et al.'s PQ WireGuard and systemically handle the KEM public keys and ciphertexts, leading to a more streamlined design. As an independent interest, we also show how to translate our findings to PQ Noise, naturally bypassing the KEM binding issue [2].

*Computational security.* As mentioned above, PQ Wire-Guard aims to be as secure as WireGuard, offering several unique security notions. While Hülsing et al. analyzed most

of these notions in their symbolic model, only a basic security notion (i.e., key indistinguishability) was analyzed in their computational model. As a correct computational proof gives stronger security guarantees by making fewer idealizing assumptions, – a point also highlighted by Hülsing et al. – our aim is to make the computational model as (or even more) expressive as the symbolic model.

In our work, we revisit the computational model by Hülsing et al. [1], which they based on those by Dowling and Paterson [7], and formalize the remaining security notions that were covered by the symbolic model. For some notions (e.g., identity hiding), our computational model provides better security guarantee since these were only symbolically analyzed on a sub-protocol of PQ WireGuard [1].

In fact, we notice a subtle bug in the previous computational models [1], [7] due to the handling of the PSKs in the *post-specified peer model*, rendering their security proof incomplete. Unlike standard mutually-authenticated key exchange, in PQ WireGuard, the server identifies and authenticates the identity of the client *during* the protocol. For completeness, this issue is detailed in Sec. A.1. In our work, we fix this by explicitly defining the server as a two-step algorithm, consisting of an *identification phase* followed by a *key-derivation phase*. The former is used by the server to identify and authenticate the client, and the latter is used to complete the key exchange with the identified client. This not only fixes the subtle issue in the formalization but also turns out to be essential for defining DoS security.

Lastly, we explicitly define *entity authentication* (e.g., security against *key-compromise impersonation* attacks) as a stand-alone security requirement following recent works [14], [15], as opposed to implicitly handling them through key indistinguishability. This allows capturing a broader authentication guarantee; even those which may not necessarily contradict key indistinguishability such as unknown key share (UKS) attacks. Indeed, due to the aforementioned KEM binding issue, we observe an explicit attack on Hülsing et al.'s PQ WireGuard when instantiating it with general KEMs (see Sec. B for the details).<fnref n="1" /> This is akin to the KEM re-encapsulation attack on Signal's PQXDH protocol [16].

*Efficiency.* In PQ WireGuard, the server uses the client's long-term and ephemeral KEM keys $pk_C$ and $pk_e$, respectively, to create the second handshake message (i.e., ciphertexts $ct_C$ and $ct_e$). Since $|ct_C| + |ct_e|$ must fit in a single UDP packet to comply with WireGuard's design choice, maxing out at 1232 B for IPv6, Hülsing et al. could not rely on ML-KEM which would result in size $2 \times 768$ B. Instead, they relied on Classic McEliece [11] for a very small $ct_C$, and a modified, IND-CPA-secure version of Saber [12] for a modest sized $ct_e$. As Classic McEliece has very large public key size, the downside is its high server memory footprint, which may be an issue when operating in memory constrained environments.

<footnote n="1">1. We note that this does not contradict their symbolic proof, because they analyze a slightly different PQ WireGuard computing the key chain value $C_5$ from $ct_C$ instead of $ct_e$. By their modeling of KEM ciphertexts this binds public key $pk_C$ [2, Sec. 5.1], thwarting the UKS attack.</footnote>
As our final contribution, we introduce reinforcing KEMs (RKEM). This is a concise abstraction of how the server uses the client public keys. Informally, this is a special KEM whose security of the long-term public key pk<sub>C</sub> can be reinforced by an ephemeral public key pk<sub>e</sub>. While running two independent KEMs in parallel is one naive construction of an RKEM, as used in PQ WireGuard, it is clearly wasteful since the ephemeral pk<sub>e</sub> does not need to be as secure as pk<sub>C</sub>. For instance, RKEM does not need to be secure when pk<sub>C</sub> is maliciously generated since this does not relate to any PQ WireGuard security. However, the naive RKEM construction would be secure under such unnecessary scenarios.

In our work, we construct a novel ML-KEM inspired RKEM called Rebar whose ciphertext is roughly 40% smaller than running two ML-KEM, allowing to fit comfortably in a single UDP packet. As the long-term public key is reduced to roughly 1.4kB, this leads to a 190 to 390× saving in server's public key memory requirement. Technically, we give a generic construction of a CCA secure RKEM from a one-way secure reinforced double-message PKE (RPKE<sub>2</sub>) by applying the Fujisaki-Okamoto (FO) transform [17] (cf. Fig. 7) in the quantum random oracle model (QROM). We then construct a lattice-based RPKE<sub>2</sub>, resembling the multi-recipient adaptation [18] of ML-KEM [19], with a novel twist. We believe our RKEM to be useful in other handshake protocols that have mutual KEM-based authentication, e.g., FSXY [20], [21], SKEME/IKEv2 [6], [22], and KEMTLS-PDK [23].

**1.2. Related Work**

We have already discussed prior work on (PQ) Wire-Guard [1], [3], [7]–[9]. As described above WireGuard builds on Noise protocols [4]. The first attempt at PQ Noise was in [24], which was later developed further by Angel et al. into PQ Noise [13]. Both proposals do not consider Noise’s PSK extension and pre-date KEM misbinding attacks [2]. Hülsing et al. [1]’s PQ WireGuard was further developed into the Rosenpass application [25], which instead of integrating PQ KEMs into WireGuard itself runs a “side-car” key exchange protocol, and then injects keys as PSKs into an otherwise still classically-secure WireGuard session. The authors took a more conservative approach to its key schedule, and include all public keys and ciphertexts, cutting off the flaws we found in [1]. However, it still uses Classic McEliece, and its side-car design results in additional overhead. An alternative approach to PQ WireGuard was put forward by Raynal [26], who proposed using now-broken signature scheme Rainbow [27] for authentication. As Rainbow has very large public keys like McEliece, this presents the same implementation hurdles. Some commercial VPN services now offer “PQ” WireGuard-based VPNs [28], [29], though few public details are available. This is seemingly done through the PSK mechanism in WireGuard with an out-of-band PQ key exchange. It is not clear what exact security is provided or what protocol is used.

Other work on PQ VPN protocols includes several forks of OpenVPN [30]–[32]. As OpenVPN is based on

TLS 1.3 [33], this amounts to integrating PQ TLS [34]. PQ extensions to the IKEv2 AKE [35] underlying IPsec [6] have been studied in the symbolic model [36], and its performance measured [37]. There are further proposals for PQ mechanisms at the IETF [38], [39]. A standard was also published for integrating optional PSKs (like in WireGuard) [40].

Related to our reinforced KEM, Xue et al. [41] proposed a similar primitive called *double-key* KEM (2KEM). While it builds on similar motivations, 2KEM still views the two KEM keys symmetrically, and their proposed lattice-based 2KEM essentially runs two ML-KEMs in parallel.

**1.3. Concurrent and Independent Work**

At USENIX Security 2025, Lafourcad et al. [42] put forward a new formal, symbolic analysis of PQ WireGuard using SAPIC+ [43], as well as showing how PQ WireGuard can be hybridized. In their analysis they independently found the UKS attack and PQ WireGuard’s reliance on additional assumptions on KEMs. They propose a fix, concatenating static public keys to the PSK value in the computation of transcript value $H_4$. Similarly to the original PQ WireGuard by Hülsing et al. [1], they still include the PSK twice in the key computations. In contrast, in our streamlined design of PQ WireGuard, we only have one inclusion. Additionally, they argue that WireGuard’s design assumption that identity public keys are *usually* unknown to adversaries in the real world is unjust; without this assumption, the MAC values break identity hiding. Lafourcad et al. insert the PSK into the computation of these anti-DoS MACs to prove identity hiding without this assumption, a countermeasure that was suggested in the original paper by Donenfeld [3]. The downside is that this seems to go against the purpose of the anti-DoS feature as now the recipient needs to perform public-key operations to identify the sender to look up the appropriate PSK. In this work we model and prove identity hiding preserving the assumption that public keys are hidden from the adversary, and additionally prove *unlinkability* of independent sessions between users.

We were recently made aware that Beguinet et al. [44] constructed an efficient lattice-based 2KEM named Maul. Unlike the 2KEM proposed by Xue et al. [41], they exploit the asymmetry in the security strengths of the two KEMs being combined. While the terminologies are different, the targeted security properties of their 2KEM is identical to those of RKEM. The design of Maul and Rebar are similar at a high level. In more detail, Rebar additionally performs bit-dropping on the reinforcing (i.e., ephemeral) public key, and also relies on standard Gaussians while Maul relies on sum of uniforms (cf. Sec. 8.1). The way security is proven is also different: while Rebar is constructed following the standard FO transform, breaking it down into the two T and $U_m^\lambda$ transforms [45], Maul is constructed from a tailored FO transform. Lastly, while we show the usefulness of RKEM using PQ WireGuard as a leading concrete example, they use it to build general bilateral and unilateral AKE protocols
in two- and three-message variants (corresponding to weak and full forward secrecy).

## 2. Preliminaries

### 2.1. Notation

For a set $\mathcal{M}$, we denote $m \stackrel{\$}{\leftarrow} \mathcal{M}$ as the process of sampling uniformly random over $\mathcal{M}$. We may make the uniform distribution explicit by denoting $\mathcal{U}(\mathcal{M})$. For a randomized algorithm $f: \mathcal{X} \times \mathcal{R} \to \mathcal{Y}$, $y \stackrel{\$}{\leftarrow} f(x)$ denotes the process of executing $f$ on $x$ with randomness $r \stackrel{\$}{\leftarrow} \mathcal{R}$. We write $y = f(x; r)$ when fixing the randomness $r$, and write $y \in f(x)$ to denote that $\exists r \in \mathcal{R}$ such that $y = f(x; r)$. We further write $f(\mathcal{X})$ for the set $\{f(x; r) | (x, r) \in \mathcal{X} \times \mathcal{R}\}$, where “|” is interpreted as “such that”. $\Pr[X:Y]$ denotes the probability that event $Y$ occurs on the randomness of variable $X$. For $a, x \in \mathbb{N}$, $a \stackrel{\pm}{\leftarrow} x$ is a shorthand for $a \leftarrow a+x$. We use this for sets $S, X$ such that $S \stackrel{\pm}{\leftarrow} X$ denotes $S \leftarrow S \cup X$. $\oplus$ denotes the XOR operation over bit strings. Lastly, a random variable $y$ following distribution $D_y$ over support $\mathcal{Y}$ has high min-entropy if $\max_{y \in \mathcal{Y}} \Pr_{y' \stackrel{\$}{\leftarrow} D_y}[y = y']$ is negligible.

### 2.2. Lattices

**Cyclotomic Rings.** Let $d$ be a power-of-two integer and $q$ a prime. Let $R = \mathbb{Z}[x]/(x^d + 1)$ be the cyclotomic ring of degree $d$ and denote $R_q = R \mod q$. For a real matrix $M \in \mathbb{R}^{k \times l}$, we note $s_1(M)$ and call spectral norm of $M$ the value $\max_{x \neq 0} \frac{\|M \cdot x\|}{\|x\|}$, where $\|\cdot\|$ denotes the $L_2$-norm. The spectral norm of $M$ is also the (unique non-negative) square root of the largest eigenvalue of $M \cdot M^\top$. We recall that if $M$ is symmetric, then its singular values are the square roots of its eigenvalues. If $B \in \mathbb{R}^{k \times l}$ has its entries in $\mathbb{R}$, we identify $B$ with its associated anti-circulant matrix $M \in \mathbb{Z}^{nk \times nt}$ and abusively say that the spectral norm of $B$ is the spectral norm of $M$.

**Hardness Assumption.** In this work, we rely on the standard module learning with errors (MLWE) problem along with (a generalization of) the recent hint MLWE problem by Kim et al. [46], stating that MLWE remains hard even if some leakage of the secret is provided.

**Definition 1 (MLWE).** Let $n, k, q$ be integers and $\chi, \chi'$ be probability distributions over $R_q$. The advantage $\text{Adv}_A^{\text{MLWE}}(1^\lambda)$ of an adversary $\mathcal{A}$ against the Module Learning with Errors (MLWE$_{q,n,k,\chi,\chi'}$) problem is defined as:

$$|\Pr[\mathcal{A}(\mathbf{A}, \mathbf{A} \cdot \mathbf{s} + \mathbf{x}) = 1] - \Pr[\mathcal{A}(\mathbf{A}, \mathbf{b}) = 1]|,$$

where $(\mathbf{A}, \mathbf{b}, \mathbf{s}, \mathbf{x}) \stackrel{\$}{\leftarrow} R_q^{n \times k} \times R_q^k \times \chi^k \times \chi'^n$. The MLWE$_{q,n,k,\chi,\chi'}$ assumption states that any efficient adversary $\mathcal{A}$ has negligible advantage.

Above, we may assume the noise $x$ has entries sampled from different distributions, i.e., the $i$-th entry of $x$ is sampled from $\chi'_i$. In which case, we may write $\text{MLWE}_{q,n,k,\chi, (\chi_i)_{i \in [n]}}$.

The following is a slight generalization of the original hint-MLWE problem [46], formally introduced by [47].

**Definition 2 (hint-MLWE).** Let $n, k, \ell, q$ be integers, $\chi$ and $\tilde{\chi}$ be probability distributions over $R_q$ and $\mathcal{F}$ be a probability distribution over $R_q^{\ell \times (n+k)}$. The advantage $\text{Adv}_A^{\text{hint-MLWE}}(1^\lambda)$ of an adversary $\mathcal{A}$ against the Hint Module Learning with Errors (hint-MLWE$_{q,n,k,\ell,\chi,\tilde{\chi},\mathcal{F}}$) problem is defined as:

$$|\Pr[\mathcal{A}(\mathbf{A}, \mathbf{A} \cdot \mathbf{s} + \mathbf{x}, \mathbf{M}, \mathbf{h}) = 1] - \Pr[\mathcal{A}(\mathbf{A}, \mathbf{b}, \mathbf{M}, \mathbf{h}) = 1]|, \\ \text{where } (\mathbf{A}, \mathbf{b}, \mathbf{s}, \mathbf{x}, \mathbf{M}) \stackrel{\$}{\leftarrow} R_q^{n \times k} \times R_q^k \times \chi^k \times \chi^n \times \mathcal{F}. \\ \text{Moreover, the hint is defined as } \mathbf{h} = \mathbf{M}[\begin{bmatrix} \mathbf{s} \\ \mathbf{x} \end{bmatrix}] + \mathbf{z} \text{ where } \\ \mathbf{z} \stackrel{\$}{\leftarrow} \tilde{\chi}^\ell. \text{ The hint-MLWE}_{q,n,k,\ell,\chi,\tilde{\chi},\mathcal{F}} \text{ assumption states that any efficient adversary } \mathcal{A} \text{ has negligible advantage.}$$

Lastly, we recall the following result which establishes the hardness of the hint-MLWE problem based on the MLWE problem. This is a simple adaptation of the original proof [46], formally appearing in [47]. Below, we denote $D_\sigma$ as a discrete Gaussian distribution with standard deviation $\sigma$.

**Theorem 1 (Hardness of hint-MLWE).** For any integers $n, k, \ell, q$, $d$, let $\mathcal{F}$ be a probability distribution over $R_q^{\ell \times (n+k)}$, $\chi$ and $\tilde{\chi}$ be discrete Gaussian distributions $D_{\sigma_1}$ and $D_{\sigma_2}$, respectively, and $B, \sigma$ a positive real such that

$$\Pr[s_1(\mathbf{M} \cdot \mathbf{M}^\top) < B : \mathbf{M} \stackrel{\$}{\leftarrow} \mathcal{F}] \geq 1 - \text{negl}(\lambda),$$

and $\sigma = \omega(\sqrt{\log d})$ and $\frac{1}{\sigma^2} = 2 \cdot \left( \frac{1}{\sigma_1^2} + \frac{B}{\sigma_2^2} \right)$. Under these conditions, the hint-MLWE$_{q,n,k,\ell,\chi,\tilde{\chi},\mathcal{F}}$ problem is as hard as the MLWE$_{q,n,k,D_\sigma}$ problem.

### 2.3. Rounding

In our work, we use the rounding definition used by Kyber [19]. Below, we briefly recall their definition.

For an even (resp. odd) positive integer $q$, we define $x' = x \mod \pm q$ to be the unique element $x'$ in the range $-\frac{q}{2} < x' \le \frac{q}{2}$ (resp. $-\frac{q-1}{2} < x' \le \frac{q-1}{2}$) such that $x' = x \mod q$. For any positive integer $q$, we define $x' = x \mod +q$ to be the unique element $x'$ in the range $0 \le x' < q$ such that $x' = x \mod q$. We simply write $x \mod q$ when the representation is not important. Also, for an element in $x \in \mathbb{Q}$, $\lfloor x \rfloor$ denotes the rounding to the nearest integer, where in case of a tie, we take the larger integer.

Compression and Decompression. We define the following compression and decompression algorithms for positive integers $d$ and $q$ such that $d < \lfloor \log_2(q) \rfloor$:

$$\text{Compress}_q : \mathbb{Z}_q \to \mathbb{Z}_{2^d} \\ x \mapsto \lfloor \frac{2^d}{q} \cdot x \rfloor \quad \text{mod } +2^d.$$

$$\text{Decompress}_q : \mathbb{Z}_{2^d} \to \mathbb{Z}_q \\ y \mapsto \lfloor \frac{q}{2^d} \cdot y \rfloor.$$

For these functions, we have the following:
**Lemma 1.** Let $d$ and $q$ be positive integers such that $d < \lceil \log_2(q) \rceil$. Then, for any $x \in \mathbb{Z}_q$, we have

$$|x' - x \bmod \pm q| \le \lfloor \frac{q}{2^{d+1}} \rfloor,$$

where $x' = \text{Decompress}_q(\text{Compress}_q(x, d), d)$.

When, $\text{Compress}_q$ or $\text{Decompress}_q$ is used with $x \in \mathbb{R}_q$ or $x \in \mathbb{R}_q^k$, the procedure is applied to each coefficient individually.

## 2.4. Quantum Tools

The following is taken from [48], slightly adapted as in [49].

**Lemma 2 (Generic Distinguishing Problem with Bounded Probabilities).** Let $S$ be a finite set. Let $F: \mathcal{X} \to \{0, 1\}$ be the following function: for each $x \in \mathcal{X}$, $F(x) = 1$ with probability $\delta_x \le \delta$ and $F(x) = 0$ otherwise. Let $Z: \mathcal{X} \to \{0, 1\}$ be the zero function, that is $Z(x) = 0$ for all $x$. For any unbounded-time quantum adversary $\mathcal{A}$ making at most $Q$ quantum queries to $F$ or $Z$, we have

$$|\Pr[\mathcal{A}^{F(\cdot)}() = 1] - \Pr[\mathcal{A}^{Z(\cdot)}() = 1]| \le 8 \cdot (Q+1)^2 \cdot \delta.$$

Following [50], we model a quantum random oracle $\mathcal{O}: \{0, 1\}^n \to \{0, 1\}^m$ as a mapping $|x\rangle|y\rangle \to |x\rangle|y \oplus \mathcal{O}(y)\rangle$, where $\mathcal{O}$ is a uniformly sampled random function. In the quantum random oracle model (QROM), all parties can evaluate $\mathcal{O}$ in superposition. Below are some useful lemmas in the QROM used in prior works [51]–[53].

**Lemma 3.** Let $\ell$ be a positive integer. Let $\mathcal{X}$ and $\mathcal{Y}$ be finite sets. Let $H_{\text{prf}}: \{0, 1\}^\ell \times \mathcal{X} \to \mathcal{Y}$ and $H_q: \mathcal{X} \to \mathcal{Y}$ be two independent quantum random oracles. Then for any unbounded-time quantum adversary $\mathcal{A}$ making at most $Q$ quantum queries to the random oracles, we have

$$|\Pr[s \stackrel{\$}{\leftarrow} \{0, 1\}^\ell : \mathcal{A}^{H_{\text{prf}}(\cdot, \cdot), H_{\text{prf}}(s, \cdot)}() = 1| \\ - \Pr[\mathcal{A}^{H_{\text{prf}}(\cdot, \cdot), H_q(\cdot)}() = 1]| \le Q \cdot 2^{-\frac{\ell}{2}+1}.$$

**Lemma 4 (Oneway to Hiding, simplified).** Let $\mathcal{X}$ and $\mathcal{Y}$ be finite sets and $S \subseteq \mathcal{X}$ a random set. Let $G, H: \mathcal{X} \to \mathcal{Y}$ be random functions satisfying $G(x) = H(x)$ for all $x \notin S$. Let $z$ be an arbitrary bit string. ($S, G, H, z$ may have an arbitrary joint distribution).

Let $\mathcal{A}$ be a binary-output algorithm making at most $Q$ oracle queries. Let $\mathcal{B}^H$ be a quantum algorithm that on input $z$ does the following: sample $i \stackrel{\$}{\leftarrow} [Q]$, run $\mathcal{A}^{H(\cdot)}(z)$ until (just before) the $i$-th query, measure all query input registers in the computational basis, output the set $\mathcal{T}$ of measurement outcomes.

Let

$$P_{\text{left}} := \Pr_{H,z} [\mathcal{A}^{H(\cdot)}(z) = 1], \quad P_{\text{right}} := \Pr_{G,z} [\mathcal{A}^{G(\cdot)}(z) = 1],$$

$$P_{\text{guess}} := \Pr_{H,G,S,z} [\mathcal{T} \stackrel{\$}{\leftarrow} \mathcal{B}^{G(\cdot)}(z) : S \cap \mathcal{T} \neq \emptyset].$$

Then,

$$|P_{\text{left}} - P_{\text{right}}| \le 2 \cdot Q \cdot \sqrt{P_{\text{guess}}}.$$

## 2.5. General Cryptographic Primitives

**2.5.1. Key Derivation Functions.** In the protocol construction we use key derivation functions, which map arbitrary-length keys and labels to an output KDF: $\mathcal{K} \times \mathcal{L} \to \mathcal{X}$.

We require a KDF to be dual-PRF-secure [54], [55] and collision resistant.

**Definition 3 (Dual-PRF-Security).** A KDF is PRF-secure (in the first input) if for any efficient adversary $\mathcal{A}$, the following advantage is negligible:

$$|\Pr[k \stackrel{\$}{\leftarrow} \mathcal{K}: \mathcal{A}^{\text{KDF}(k, \cdot)}() = 1] - \Pr[\mathcal{A}^{R(\cdot)}() = 1]|,$$

where $R(\cdot)$ is sampled uniformly over all functions mapping $\mathcal{L}$ to $\mathcal{X}$. Moreover, a KDF is dual-PRF-secure if we further have the above for the second input: KDF($\cdot, \ell$) for a randomly sampled $\ell \stackrel{\$}{\leftarrow} \mathcal{L}$ is indistinguishable from a truly random function mapping $\mathcal{K}$ to $\mathcal{X}$.

**Definition 4 (Collision Resistance).** A KDF is collision-resistant if for any efficient adversary $\mathcal{A}$, the following advantage is negligible:

$$\Pr \left[ (s, s', m, m') \stackrel{\$}{\leftarrow} \mathcal{A}(1^{\lambda}) : \begin{array}{l} \text{KDF}(s, m) = \text{KDF}(s', m') \land (s, m) \neq (s', m') \end{array} \right].$$

**2.5.2. Authenticated Encryption with Associated Data.**

We recall the definition of an AEAD.

**Definition 5 (AEAD).** An authenticated encryption with associated data (AEAD) with key, nonce, header, and message spaces $\mathcal{K}, \mathcal{N} = \{0, 1\}^\ell, \mathcal{H} \subseteq \{0, 1\}^*$, and $\mathcal{M} \subseteq \{0, 1\}^*$, respectively, consists of the following algorithms.

**AEAD.Enc($k, N, H, M$) → $C$:** On input a key $k \in K$, a nonce $N \in \mathcal{N}$, a header $H \in \mathcal{H}$ and a message $M \in \mathcal{M}$, it outputs a ciphertext $C \in \{0, 1\}^*$.

**AEAD.Dec($k, N, H, C$) → $M$:** On input a key $k \in K$, a nonce $N \in \mathcal{N}$, a header $H \in \mathcal{H}$, and a ciphertext $C \in \{0, 1\}^*$, it outputs a message $M \in \mathcal{M}$ or $\perp \notin \mathcal{M}$ indicating decryption failure.

We require an AEAD to be correct, IND-CPA secure, and INT-CTXT secure [56].

**Definition 6 (Correctness).** An AEAD is correct if $\text{AEAD.Dec}(k, N, H, \text{AEAD.Enc}(k, N, H, M)) = M$ holds 1 for all $k, N, H, M$ in the appropriate spaces.

**Definition 7 (IND-CPA Security).** An AEAD is IND-CPA secure if for any efficient adversary $\mathcal{A}$, the following advantage is negligible:

$$|\Pr[k \stackrel{\$}{\leftarrow} \mathcal{K}: \mathcal{A}^{\mathcal{O}_{\text{Enc}}(k, \cdot, \cdot, \cdot)}(1^{\lambda}) = 1] - \Pr[\mathcal{A}^{\$}(\cdot, \cdot, \cdot)}(1^{\lambda}) = 1]|,$$

where on query $(N, H, M)$, $\mathcal{O}_{\text{Enc}}(k, \cdot, \cdot, \cdot)$ outputs $\text{AEAD.Enc}(k, N, H, M)$ and $\$ (\cdot, \cdot, \cdot)$ outputs a random bit string with length $|M|$. When queried on the same input twice, the oracles are assumed to output to the previous value.
**Definition 8 (INT-CTXT Security).** An AEAD is INT-CTXT secure if for any efficient adversary $\mathcal{A}$, the following advantage is negligible:

$$ \Pr \left[ k \stackrel{\$}{\leftarrow} \mathcal{K}, (N^*, H^*, C^*) \stackrel{\$}{\leftarrow} \mathcal{A}^{\mathcal{O}_{\text{Enc}}(k, \cdot, \cdot, \cdot)}(1^{\lambda}) : \text{AEAD.Dec}(k, N^*, H^*, C^*) \neq \perp \land (N^*, H^*, C^*) \notin \mathcal{Q}, \right] $$

where on input $(N, H, M)$, $\mathcal{O}_{\text{Enc}}(k, \cdot, \cdot, \cdot)$ outputs AEAD.Enc$(k, N, H, M)$, and $\mathcal{Q}$ is the list of $(N, H, M)$ that $\mathcal{A}$ submitted to oracle $\mathcal{O}_{\text{Enc}}$.

**2.5.3. Key Encapsulation Mechanisms.** We recall the definition of a KEM.

**Definition 9 (KEM).** A key encapsulation mechanism (KEM) an efficiently sampleable key space $\mathcal{K}$ consists of the following algorithms.

**KEM.KeyGen (1^λ) → (pk, sk):** On input the security parameter $1^λ$, it outputs a public and secret key pair (pk, sk).

**KEM.Enc (pk) → (ct, ss):** On input a public key pk, it outputs a ciphertext ct and a key ss ∈ $\mathcal{K}$.

**KEM.Dec (sk, ct) → ss:** On input a secret key sk and a ciphertext ct, it outputs a key ss ∈ $\mathcal{K}$.

We require a KEM to be correct with all but probability $\delta$. This is set to be negligible in the instantiation.

**Definition 10 (δ-Correctness).** A KEM is $\delta$-correct if for any $\lambda \in \mathbb{N}$, we have $\Pr[ss = \text{Dec}(sk, ct)] \ge 1 - \delta$, where the probability is taken over $(pk, sk) \stackrel{\$}{\leftarrow} \text{KeyGen}(1^\lambda)$ and $(ct, ss) \stackrel{\$}{\leftarrow} \text{Enc}(pk)$.

We further require the SPR-CCA security for KEMs [49].

**Definition 11 (SPR-CCA Security).** For a simulator $S$, we define the advantage $\text{Adv}_{\text{KEM},\mathcal{A}}^{\text{SPR-CCA}}(\lambda)$ of $\mathcal{A}$ against the SPR-CCA security game as follows:

$$ \Pr \left[ \begin{array}{l} b \stackrel{\$}{\leftarrow} \{0, 1\}, \\ (pk, sk) \stackrel{\$}{\leftarrow} \text{KEM.KeyGen}(1^{\lambda}), \\ (ct_0, ss_0) \stackrel{\$}{\leftarrow} \text{KEM.Encaps}(pk); \quad : b = b' \\ (ct_1, ss_1) \stackrel{\$}{\leftarrow} S(1^{\lambda}) \times \mathcal{K}, \\ b' \stackrel{\$}{\leftarrow} \mathcal{A}^{\mathcal{O}_{\text{Dec}}(sk, \cdot)}(ek, ct_b, ss_b) \end{array} \right] - \frac{1}{2} \right] $$

where on input ct, $\mathcal{O}_{\text{Dec}}(sk, \cdot)$ outputs KEM. Dec(sk, ct), and $\mathcal{A}$ is not allowed to query the challenge ciphertexts $ct_0$ and $ct_1$ to $\mathcal{O}_{\text{Dec}}$. A KEM is SPR-CCA secure if there exists an efficient simulator $S$ such that $\text{Adv}_{\text{KEM},\mathcal{A}}^{\text{SPR-CCA}}(\lambda) = \text{negl}(\lambda)$ for any efficient adversary $\mathcal{A}$.

# 3. Reviewing PQ WireGuard by Hülsing et al.

We briefly review the design and security of PQ Wire-Guard [1], a post-quantum adaptation of WireGuard [3].

## 3.1. Construction Overview

Recall that WireGuard is based on the Noise [4] “IKpsk2” pattern. This is a one-roundtrip DH key exchange between a

client and server,<fnref n="2" /> where the client knows the server's long-term public key, while the server learns the client's identity after the initial handshake message. A pre-shared key (PSK) can be mixed into the key exchange, making the protocol more secure in case all other secrets are compromised. Following the design of Noise (with the pre-shared key extension [4, Sec. 9]), the transmitted ephemeral DH keys are hashed with the shared secrets in a *key chain* ($C_i$'s), and a separate *hash chain* ($H_i$'s) of all messages is computed and confirmed through AEAD ciphertexts in both messages. (Note that although it will appear that some processing steps could be merged, the systematic, piecewise processing relates to the token-processing-based nature of Noise protocols.)

At a high level, PQ WireGuard by Hülsing et al. [1] replaces the DH components with KEMs, using Classic McEliece 460896 for the long-term keys and a modified, IND-CPA version of Saber for the ephemeral keys. A detailed description of PQ WireGuard, and on how the key and hash chains evolve is provided in Fig. 1. The timestamp prevents replay attacks; the server keeps track of the greatest timestamp received per client and discards messages containing timestamps less than or equal to it [3, Sec. 5.1]. This lets the server avoid DoS from half-open connections, as each client message can only open one connection. MAC tags m1, m2 are further used to prevent DoS attacks from drive-by attackers and spoofed initiators, letting WireGuard avoid having to do public-key operations on such message. Tag m1, keyed with the client's public key, proves that the server is familiar with the client's identity (assuming that the public key is not widely disseminated, as is often the case in practice). Tag m2 is keyed with a *cookie* value only used when the server is under load. If cookies are to be used but not provided, the server will first reply with a randomized value derived from its public key and a short-term secret. It is sent encrypted using a key derived from the server's public key and the source IP; otherwise it is just 16 zero bytes [3, Sec. 5.3]. A response using a correct, non-zero cookie proves that the client actually receives messages at its specified source IP address. Lastly, values $lbl_1,lbl_2,lbl_3$ are distinct fixed strings stemming from the Noise protocol [3, Sec. 5.4]. Here, we note that if the server's public key is unknown to the adversary, then the cookie value has high min-entropy (i.e., it cannot be guessed by the adversary).

Most relevant to the context of our paper is the key schedule of Hülsing et al. [1]. Since KEMs come with both a public key pk and a ciphertext ct, they are syntactically quite different from DH key exchanges, and as such, the key and hash chains evolve quite differently. Their protocol mixes only $pk_e$ and $ct_e$ in the key chain, and only $pk_s$, $pk_e$, $ct_e$, and (an AEAD encryption of) $pk_C$ and $ct_C$ in the hash chain. They further add another use of the PSK to the computation of $K_{\text{time}}$ to authenticate the time message (in lieu of static-static DH key exchange, which KEMs do not support), resulting in mixing in PSK twice into the key chain.

<footnote n="2">2. While “client” and “server” is used throughout this section for readability, “initiator” and “responder” would be the more general term. This is terminology we use in Sec. 4.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1. Description of PQ WireGuard by Hülsing et al. [1] and ours in the left column. Variant-specific functionality is boxed. Our protocol based on standard KEMs is identical to Hülsing et al.'s, except for the header information in the second to last AEAD ciphertext, marked in green. The middle and right columns show the key schedule (i.e., evolution of the key and hash chains and generated cryptographic keys $K$); KDF$_i$-labeled transitions indicate domain-separated calls to KDF. The green insets show the computations for our protocol when using KEM instead of RKEM.</figcaption></figure>

We note that while [1] uses a NAXOS-like construction and protect against bad randomness, we simplify our analysis and presentation by assuming secure random generation.

Looking ahead, since $pk_C$ (or $ct_C$) is not hashed into the key chain, PQ WireGuard of Hülsing et al. [1] is susceptible against unknown key share (UKS) attacks. In their symbolic model, they prove it secure against it by hashing $ct_C$. While the proof requires the KEM to satisfy some binding properties [2], this holds in their way of modeling KEM. See Sec. B for more details.

## 3.2. Security Properties

PQ WireGuard aims to achieve the same level of security as WireGuard, even against quantum adversaries. While a formal definition is given in Sec. 4, we provide a brief overview here. The baseline security property is key indistinguishability, requiring that the established session key is pseudorandom. This should hold even if the adversary compromises any (non-trivial) combination of the secret information held by the parties.

It further aims to achieve several unique properties: session key uniqueness, entity authentication, identity hiding, and DoS mitigation [1, Sec. II-B]. The first notion requires the established keys to be unique, and the second requires that the parties communicate with their intended peer, implying that no adversary can impersonate another party through key-compromise impersonation (KCI) or unknown key share (UKS) attacks. The third notion requires that the transcript alone does not leak the communicating parties (i.e., the long-term keys) to the adversary.

Lastly, while the DoS mitigation entails many meanings, in [1], it is the requirement that the first client handshake message is authenticated. This allows a server to reject forged messages without having to explicitly respond to an unauthenticated client. Concretely, looking at PQ WireGuard in Fig. 1, `ltk` is an AEAD encryption of (the hash of the) client public key $pk_C$. The server, first decrypts $H(pk_C)$, and checks if any of the client public key in memory hashes to this value. If so it identifies its peer as $pk_C$, and otherwise, it halts. As PSK is used to derive the AEAD key, an adversary without knowledge of PSK cannot impersonate the client.
Hülsing et al. [1] analyze all the security properties above in their symbolic model using the Tamarin prover, building on the symbolic model by [9]. In contrast, only key-indistinguishability (and, implicitly, some authentication notion) is analyzed in their computational model, building on the model by [7].

# 4. Computational Model for PQ WireGuard

We provide a formal computational (i.e., game-based) security model for PQ WireGuard.

## 4.1. Syntax and Execution Environment

We formally define the key exchange protocol used by PQ WireGuard as a WGKE protocol: a one-roundtrip protocol where an initiator (i.e., client) starts the conversation, and a responder (i.e., server) talks back once. As explained in Sec. 1.1, the responder algorithm is split into two phases ResIdentify and ResDer, making the post-specified peer model explicit. Below, we assume $\epsilon$ is a special symbol denoting an empty string. This is used for instance to make it clear that pre-shared keys psk are optional inputs.

**Definition 12.** A WGKE protocol consists of the following algorithms, where $\mathcal{K}$ and $\mathcal{K}_{\text{psk}}$ are the session key and pre-shared key spaces, respectively.

**KeyGen(1$^{\lambda}$) → (lpk, lsk):** On input the security parameter $1^{\lambda}$, it outputs a public and secret key pair (lpk, lsk).

**Init(lsk$_i$, lpk$_r$, psk) → (m$_1$, st):** The initiator on input its secret key lsk$_i$, the responder's public key lpk$_r$, and a pre-shared key psk $\in \mathcal{K}_{\text{psk}} \cup \{\epsilon\}$, outputs a first message m$_1$ and a session state st.

**ResIdentify(lsk$_r$, m$_1$) → lpk$_i$ or $\perp$:** The responder on input its secret key lsk$_r$ and a first message m$_1$, outputs either the intended initiator's public key lpk$_i$, or $\perp$ indicating that the initiator could not be identified.

**ResDer(lsk$_r$, lpk$_i$, m$_1$, psk) → (K, m$_2$):** The responder on input its secret key lsk$_r$, intended initiator's public key lpk$_i$, a first message m$_1$, and a pre-shared key psk $\in \mathcal{K}_{\text{psk}} \cup \{\epsilon\}$, outputs a session key K and a second message m$_2$.

**InitDer(lsk$_i$, m$_2$, st, psk) → K:** The initiator on input secret key lsk$_i$, a second message m$_2$, a session state st, and a pre-shared key psk $\in \mathcal{K}_{\text{psk}} \cup \{\epsilon\}$, outputs a session key K.

We consider a unified computational (i.e., game-based) security model, formally described in Fig. 3, capturing the various types of security guarantees. Each party $u \in \mathbb{N}$ possess a public and secret key pair (lpk$_u$, lsk$_u$), and as in [3, Sec. 2], u is identified by its public key lpk$_u$ and parties are unable to register an existing public key. For convenience, we assume a function $\pi_{\text{userid}}$ mapping lpk$_u$ to a party $u \in \mathbb{N}$ maintained by the game.

The game allows an initiator and a responder to establish a key exchange session. However, as an initiator and responder may have diverging views on the session, the game creates an instance ilD $\in \mathbb{N}$ for each of them and keeps track of the following associated information.

**role[iID] ∈ {init, resp}:** instance ilD's role, i.e., whether the instance acts as the initiator or the responder.

**(Init[iID], Resp[iID]) ∈ $\mathbb{N} \cup \{\epsilon\} \times \mathbb{N}$:** the identities of the initiator and the responder relative to the instance ilD. The initiator may be $\epsilon$, modeling the fact that WireGuard allows the server to learn the client's identity during the protocol.

**psk[iID]:** the pre-shared key psk used by the instance ilD, where psk = $\epsilon$ if it is unused.

**sent[iID]:** the message sent by the instance ilD.

**recv[iID]:** the message received by the instance ilD.

**key[iID]:** the session key computed by the instance ilD. This is set to $\perp$ if ilD fails to establish a key or $\epsilon$ if the session has not either started or finished yet.

While there are other information kept tracked by the game (i.e., corruption states), they are explained when needed. We also denote $\mathcal{S}_{\text{ilD}} \subset \mathbb{N}$ as all the instances generated in the game (cf. Fig. 3). Following prior AKE definitions [57]–[61], we use the notion of partners to define the set of trivial attacks; since there are two instances ilD, ilD' that may share the same session key, we need a mechanism to identify them. While there are various ways to define the predicate Partner, we use the following simplistic form as they are equivalent for natural protocols (cf. [61]).

**Definition 13 (Partner).** The predicate Partner ilD, ilD' holds true if and only if $\forall$ ilD, ilD' $\in \mathcal{S}_{\text{ilD}}$, we have $[[\text{role}[ilD] \neq \text{role}[ilD']]] \wedge [[\text{key}[ilD] = \text{key}[ilD']] \notin \{\epsilon, \perp\}]$.

Lastly, we require WGKE to be correct. This requires that when all the users in the system honestly execute the WGKE protocol without the adversary tampering the protocol messages, then they derive an identical session key all but with a negligible probability. Formally, we model this through a game between a passive adversary $\mathcal{P}$ and a challenger. Here, a passive adversary $\mathcal{P}$ can arbitrary interact with the users under the restriction that it must honestly deliver the protocol messages. For instance, if an initiator $i$ outputs a first message m$_1$ to a receiver $r$, then $\mathcal{P}$ cannot invoke the receiver $r$ on anything other than m$_1$.

**Definition 14 (Correctness).** We define the correctness game in Fig. 2 and define the advantage of a passive adversary $\mathcal{P}$ as

$$ \text{Adv}_{\text{WGKE}, \mathcal{P}}^{\text{CORR}}(1^{\lambda}) := \text{Pr} \left[ \text{Game}_{\text{WGKE}, \mathcal{P}}^{\text{CORR}}(1^{\lambda}) = 1 \right]. $$

We say a WGKE protocol is correct if $\text{Adv}_{\text{WGKE}, \mathcal{P}}^{\text{CORR}}(1^{\lambda}) = \text{negl}(\lambda)$ for any efficient passive adversary $\mathcal{P}$.

## 4.2. Security Guarantees

We now explain the four types of security guarantees satisfied by PQ WireGuard: authentication, DoS mitigation, identity hiding, and key indistinguishability.

### 4.2.1. Entity Authentication.
In [1], [7], authentication was not defined explicitly and was merely a means to break key indistinguishability. This is why attacks such as UKS attacks
<figure><img src="image_3.png" /><figcaption>Figure 2. Correctness game where $O^*$ denotes the set $\{O_{\text{Init}}, O_{\text{InitDer}}, O_{\text{ResDer}}\}$ defined in Fig. 4.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 3. Games for match soundness, DoSSec security, identity hiding, and key indistinguishability, where $\mathcal{O} \in \{\text{MATCH}, \text{DoSSec}, \text{IDHIDE}, \text{KIND}\}$. $\mathcal{O}$ denotes the set of all oracles in Fig. 4 excluding $\mathcal{O}_{\text{Test}}^{\text{IDHIDE}}$. $\mathcal{O}^*$ denotes the set of oracles $\mathcal{O}_{\text{Test}}^{\text{IDHIDE}}$, $\mathcal{O}_{\text{RevSessKey}}$, $\mathcal{O}_{\text{RevLSK}}$, $\mathcal{O}_{\text{RevState}}$, and $\mathcal{O}_{\text{RevPSK}}$.</figcaption></figure>

were not captured in their computational models as they do not necessarily break key indistinguishability.

Following recent AKE definitions [14], [15], we model this explicitly via a game called *match soundness*. At a high level, this defines the expected behavior of partnered instances (i.e., instances with the same session key). Citing from [14], *implicit authentication* requires “should there be an instance iID that possesses the same session key as instance iID', then the owner of instance iID' must be the identity designated as the peer of instance iID.” Indeed, this covers UKS and KCI attacks. Moreover, our model captures session key uniqueness as sessions have at most one partner.

**Definition 15 (Match Soundness).** We define the predicate $\text{Match}(S_{\text{iID}})$ holds true if and only if

$$ \forall \text{iID}, \text{iD}', \text{iD}'' \in S_{\text{iID}}, $$

1) If $[[\text{Partner}(\text{iID}, \text{iD}')] = \text{true}]$, then $[[\text{Init}[\text{iID}] = \text{Init}[\text{iD}')] \land [[\text{Resp}[\text{iID}] = \text{Resp}[\text{iD}']]]]$.

2) If $[[\text{Partner}(\text{iID}, \text{iD}')] = \text{Partner}(\text{iID}, \text{iD}'')] = \text{true}]$, then $[[\text{iID}'] = \text{iD}'']]$.

Formally, WGKE is *match sound* if $\text{Adv}_{\text{WGKE},\mathcal{A}}^{\text{MATCH}}(1^{\lambda}) := \text{Pr}[\text{Game}_{\text{WGKE},\mathcal{A}}^{\text{MATCH}}(1^{\lambda}) = 1]$ (cf. Fig. 3) is negligible for all efficient $\mathcal{A}$.

**4.2.2. DoS Mitigation.** We aim to address DoS attacks in which an adversary attempts to create load and half-open connections on the server by transmitting forged client messages and thereby eliciting responses that require expensive operations to craft. Following the symbolic model of PQ-WireGuard by [1], we require that an adversary cannot pass ResIdentify (which only identifies the sender) without knowledge of the PSK. To formalize this requirement, we introduce the DoSSec security game defined in Fig. 3 with the predicate in Def. 16. In this game, the responder is guaranteed to execute ResDer (i.e., send a message and derive a session key, possibly $\perp$, after running ResIdentify) at most $L$ times, provided that an initiator with the correct PSK has been executed $L$ times. This definition relies on the following observation: the adversary may obtain legitimate client messages via the $\mathcal{O}_{\text{Init}}$ oracle and forward them to the server, thereby eliciting valid responses. Such behavior is not regarded as a DoS attack, as the messages are legitimately generated by the client for session establishment. Instead, the adversary is deemed successful if it can cause the server to produce $L+1$ responses, namely, at least one more than the number of legitimate initiations by the client. The DoSSec security therefore captures the requirement that the responder maintains no half-open connections beyond those explicitly requested by the client.

**Definition 16 (DoS Security).** We define the predicate $\text{DoSSec}$ such that $\text{DoSSec}(S_{\text{iID}})$ holds true if and only if $\forall i, j \in \mathcal{U}_{\text{Hon}}$ such that $\text{RevPSK}[\{i, j\}] = \text{false}$, $|\text{RESP}_{i,j}| \le |\text{INIT}_{i,j}|$ holds, where

$$ \text{INIT}_{i,j} := \left\{ \begin{array}{ll} \text{iID} & \text{iID} \in S_{\text{iID}} \land \text{role}[\text{iID}] = \text{init} \\ & \land \text{Init}[\text{iID}] = i \land \text{Resp}[\text{iID}] = j \end{array} \right\}, \text{and} \\ \text{RESP}_{i,j} := \left\{ \begin{array}{ll} \text{iID} & \text{iID} \in S_{\text{iID}} \land \text{role}[\text{iID}] = \text{resp} \\ & \land \text{Init}[\text{iID}] = i \land \text{Resp}[\text{iID}] = j \land \text{key}[\text{iID}] \neq \epsilon \end{array} \right\}. $$

Formally, WGKE is *DoS secure* if $\text{Adv}_{\text{WGKE},\mathcal{A}}^{\text{DoSSec}}(1^{\lambda}) := \text{Pr}[\text{Game}_{\text{WGKE},\mathcal{A}}^{\text{DoSSec}}(1^{\lambda}) = 1]$ (cf. Fig. 3) is negligible for all efficient $\mathcal{A}$.

**4.2.3. Identity Hiding.** Identity hiding ensures that a passive adversary cannot identify the communicating parties as long as their public keys are unrevealed; this is a required assumption since MAC tags, keyed with the public keys, are included in the transcript. We model this by only giving the number of parties $|\mathcal{U}_{\text{Hon}}|$ to the adversary. In fact, our model captures a stronger property *unlinkability* that has not been formalized even in the symbolic models [1], [9], further requiring that an adversary cannot tell if two session executions were from the same parties. We note that this
<figure><img src="image_5.png" /><figcaption>Figure 4. Oracles used in the security games. Above, if any condition in **require** does not hold, then it immediately returns $\perp$.</figcaption></figure>

holds even if the associated session keys and session states leak, modeling the fact that identity hiding is a property that solely relies on the security of the identity key.

Formally, WGKE is identity hiding if $\text{Adv}_{\text{WGKE},A}^{\text{IDHIDE}}(1^{\lambda}) := |2 \cdot \text{Pr}[\text{Game}_{\text{WGKE},A}^{\text{IDHIDE}}(1^{\lambda}) = 1] - 1|$ (cf. Fig. 3) is negligible for all efficient $\mathcal{A}$.

**4.2.4. Key Indistinguishability.** We define it similarly to prior works [1], [7] which use eCK [62]-style modeling with ephemeral key reveals, with the following differences:

(i) We fix a subtle bug in the security game by accurately modeling the post-specified peer model via Residentify.

(ii) We allow malicious public keys to be registered.

(iii) We model weak forward secrecy, as opposed to full.

Weak forward secrecy (wFS) guarantees that the session key remains secure even if the public keys are compromised at a later point as long as the adversary is passive during session establishment. In contrast, full forward secrecy (fFS) allows the adversary to actively interfere with the session. [1] proved PQ WireGuard satisfies fFS by adding an explicit key-confirmation message from the initiator to the responder, making the protocol three-rounds in total.

In our work, we keep our analysis consistent with Wire-Guard [3], without running such explicit key-confirmation (though WireGuard defers responder traffic until it has received an initiator message serving as key-confirmation). However, we highlight that we can modularly achieve the same fFS result as [1], [7] since an wFS protocol with implicit authentication can be upgraded to satisfy fFS by adding explicit key-confirmation [14], [63], [64]. The formal definition of our key indistinguishability appears in Sec. A.2.

# 5. PQ WireGuard from Reinforced KEM

We introduce a new primitive called *reinforced* KEM (RKEM) as a natural building block for many key exchange protocols. We then propose a leaner design of PQ WireGuard compared to Hülsing et al. [1]'s design and prove it secure under our new computational model.

## 5.1. Introducing Reinforced KEM

An RKEM allows to *reinforce* the security of the public key pk with a *reinforcing* public key rpk. To give more context, one can think of rpk as an ephemeral public key epk used in a key exchange protocol, where recall epk provides additional security when the (long-term) public key is compromised. It is informative to keep this correspondence in mind when reading the requirements of RKEM below.

**Definition 17.** A reinforced KEM (RKEM) with an efficiently sampleable key space $\mathcal{K}$ consists of the following algorithms.

**KeyGen(1^λ) → (pk, sk):** On input the security parameter $1^λ$, it outputs a (standard) public and secret key pair (pk, sk).

**RKeyGen(pk) → (rkp, rsk):** On input a public key pk, it outputs a *reinforcing* public and secret key pair (rkp, rsk). We assume pk defines the set of reinforced public keys $\mathcal{RPK}(pk)$, whose set membership can be efficiently checked.

**REnc(pk, rpk) → (ct, ss):** On input a standard and reinforcing public key pair (pk, rpk), it outputs a ciphertext ct and a key ss $\in \mathcal{K}$.

**RDec(sk, rsk, ct) → ss:** On input a standard and reinforcing secret key pair (sk, rsk) and a ciphertext ct, it outputs a key ss $\in \mathcal{K}$.

**Definition 18** (*δ*-Correctness). We say that RKEM is *δ*-correct if for any $\lambda \in \mathbb{N}$, we have
$\Pr[\text{ss} = \text{RDec}(\text{sk}, \text{rsk}, \text{ct})] \ge 1 - \delta$, where the probability is taken over $(\text{pk}, \text{sk}) \stackrel{\$}{\leftarrow} \text{KeyGen}(1^{\lambda})$, $(\text{rk}, \text{rsk}) \stackrel{\$}{\leftarrow} \text{RKeyGen}(\text{pk})$, and $(\text{ct}, \text{ss}) \stackrel{\$}{\leftarrow} \text{REnc}(\text{pk}, \text{rk})$.

Also, we require KeyGen (resp. RKeyGen) and REnc to output (resp. reinforcing) public keys and session keys that have high min-entropy under honest execution, respectively.

We further require an RKEM to satisfy two types of CCA-like security, each associated to the standard and reinforced public keys. The first requires a strong level of security for the standard public key, reflecting the fact that reinforcing keys cannot harm the security. In short, even a maliciously generated reinforcing public key rpk' should not weaken the security of the standard public key. That is, a ciphertext generated with $(\text{pk}^*, \text{rk}^')$ remains secure as long as $\text{pk}^*$ is not compromised. This holds even giving access to a decryption oracle using $\text{sk}^*$. Moreover, the ciphertext must be simulatable without knowing $\text{pk}^*$; a property necessary for identity hiding. This notion is akin to SPR-CCA security of standard KEMs [49].

<figure><img src="image_6.png" /><figcaption>Figure 5. Security games for an RKEM. The core differences between the SPR-CCA security and IND-RCCA security are highlighted in **blue**.</figcaption></figure>

**Definition 19 (SPR-CCA Security).** For a simulator $\mathcal{S}$, we define the advantage of $\mathcal{A}$ against the strong pseudorandom-

ness under chosen-ciphertext attack (SPR-CCA) security game as follows:

$$ \mathrm{Adv}_{\mathrm{RKEM}, \mathcal{A}}^{\mathrm{SPR-CCA}}(1^{\lambda}) := \left| 2 \cdot \mathrm{Pr} \left[ \mathrm{Game}_{\mathrm{RKEM}, \mathcal{A}}^{\mathrm{SPR-CCA}}(1^{\lambda}) = 1 \right] - 1 \right|, $$

where $\mathrm{Game}_{\mathrm{RKEM}, \mathcal{A}}^{\mathrm{SPR-CCA}}(1^{\lambda})$ is defined in Fig. 5. We say RKEM is SPR-CCA *secure* if there exists an efficient simulator $\mathcal{S}$ such that $\mathrm{Adv}_{\mathrm{RKEM}, \mathcal{A}}^{\mathrm{SPR-CCA}}(\lambda) = \mathrm{negl}(\lambda)$ for any efficient adversary $\mathcal{A}$.

The second requires that the reinforcing public key provides additional security in case the *honestly generated* standard public key is compromised. This reflects the reinforcing nature of rpk. We note that we do not require strong pseudorandomness as this is not required by PQ WireGuard, i.e., rpk is not tied to the initiator's identity.

**Definition 20 (IND-RCCA Security).** We define the advantage of $\mathcal{A}$ against the *indistinguishable against reinforced chosen-ciphertext attack* (IND-RCCA) security game as follows:

$$ \mathrm{Adv}_{\mathrm{RKEM}, \mathcal{A}}^{\mathrm{IND-RCCA}}(1^{\lambda}) := \left| 2 \cdot \mathrm{Pr} \left[ \mathrm{Game}_{\mathrm{RKEM}, \mathcal{A}}^{\mathrm{IND-RCCA}}(1^{\lambda}) = 1 \right] - 1 \right|, $$

where $\mathrm{Game}_{\mathrm{RKEM}, \mathcal{A}}^{\mathrm{IND-RCCA}}(1^{\lambda})$ is defined in Fig. 5. We say RKEM is IND-RCCA *secure* if $\mathrm{Adv}_{\mathrm{RKEM}, \mathcal{A}}^{\mathrm{IND-RCCA}}(\lambda) = \mathrm{negl}(\lambda)$ for any efficient adversary $\mathcal{A}$.

Notice that running two standard KEMs in parallel is one naive way to construct an RKEM. That is, RKeyGen outputs a standard KEM key, and REnc generates two KEM ciphertexts with session keys $ss_1, ss_2$ and sets $ss := H_1(ss_1, H_2(ss_2))$ for some hash functions $H_1, H_2$.<fnref n="3" /> Indeed, this is the implicit RKEM used in a typical key exchange protocol, including PQ WireGuard, where recall rpk act as an ephemeral public key. However, this RKEM is *strictly* more secure than what RKEM requires. Since the two KEMs are symmetrical, it does not exploit the asymmetry in the security strength required by pk and rpk; that is, no security is required when mixing rpk with a *maliciously generated* pk. Looking ahead, in Sec. 6, we show how to construct a more efficient RKEM that takes advantage of this asymmetry.

## 5.2. Building PQ WireGuard from RKEM

The protocol description and key schedule of our PQ WireGuard is depicted in the left and right columns of Fig. 1, respectively. We explain our design in a bottom-up fashion.

Similarly to how the “IKpsk2” Noise pattern [4] yields WireGuard, we hope to explain PQ WireGuard as a particular PQ Noise pattern. However, as explained in Sec. 1.1, PQ Noise [13] does not incorporate the later-discovered concerns surrounding KEM binding [2] nor discusses how to use PSKs. To this end, we streamline the design of PQ Noise by slightly changing the key schedule to ensure randomized keys without relying on KEM binding [2]. In short, we require the inclusion of all public keys in the key schedule, where

<footnote n="3">3. We intentionally compute $ss$ in a cascaded manner to be consistent with the key schedule in (PQ) WireGuard (cf. Fig. 1).</footnote>
more details are given in Sec. F. This also then matches the behavior for ephemeral public keys in classic Noise extended with PSK, which hashes them to ensure randomized keys; the key computations for PSK itself also follow classic Noise.

At this point, our PQ WireGuard based on KEMs simply follows the “IKpsk1” PQ Noise pattern. The protocol description (i.e., left column of Fig. 1) is almost identical to Hülsing et al. [1]’s. The only difference is the key schedule depicted in the right column with 'green' insets, derived naturally from the (streamlined) PQ Noise pattern. Note that it is not the “IKpsk2” pattern as in WireGuard. This is because to authenticate the time message, as identified by [1], we must process the PSK earlier.

Lastly, as the way we chain the two KEM ciphertexts is exactly the naive instantiation of RKEM explained in the previous section, we can simply bundle them together to arrive at our desired PQ WireGuard based on RKEMs. For completeness, we explain how to extend PQ Noise with RKEM in Sec. F.

## 5.3. Security of Our RKEM-based PQ WireGuard

We prove the security of our PQ WireGuard. The details on key indistinguishability are provided in Sec. C; the proof follows closely to [1], [7]. Below, we first show the authentication guarantee.

**Theorem 2.** *Our PQ WireGuard satisfies match soundness if KDF is collision-resistant and RKEM outputs reinforcing public and session keys with high min-entropy.*

*Proof.* Since we assume a collision-resistant KDF, the keys $pk_S$, $rpk$, $pk_C$ input to the KDF by two instances iID and iID' such that $key[iID] = key[iID'] \notin \{\epsilon, \perp\}$ must be identical. The first property of match soundness then follows from the restriction role[iID] $\ne$ role[iID'] for partners. Moreover, the second property in case role[iID] = resp (resp. role[iID] = init) immediately follows from the high min-entropy of the RKEM reinforcing public (resp. session) key. □

We next show DoS security, where the proof assumes a feature of WireGuard [3, Sec. 5.1], preventing replay attacks by only accepting monotonically increasing timestamps.

**Theorem 3.** *Our PQ WireGuard is DoS secure if KDF is PRF secure and AEAD is INT-CTXT secure.*

*Proof.* Assume an initiator is executed L times and generated $time_i := AEAD.Enc(K_{6,i}, H_{6,i}, t_{now,i})$ for $i \in [L]$. As psk is unknown and KDF is PRF secure, each $K_{6,i}$ is distributed uniformly at random. Then, relying on the INT-CTXT security of the AEAD, no responder can accept more than L (distinct) AEAD outputs. □

Lastly, we show identity hiding. For this, the MAC is assumed to output pseudorandom tags. Otherwise, different sessions between the same parties may become linkable by observing the tags m1, keyed by the public keys. As Hülsing et al. [1] symbolically analyzed identity hiding on a subprotocol of their PQ WireGuard, this assumption was not

documented. In our work, we rely on the fact that WireGuard uses HMAC [3, Sec. 5.4] which can be viewed as a PRF. Moreover, we assume the hash function H is a random oracle in the proof. While the proof can be completed in the standard model assuming that H is a seeded randomness extractor, we choose to analyze it otherwise as it more accurately models the practical instantiation. Indeed, in WireGuard [3, Sec. 5.4], H is an unkeyed BLAKE2s [65].

**Theorem 4.** *Our PQ WireGuard is identity hiding if the KEM and RKEM are SPR-CCA secure and their (standard) public keys have high min-entropy, AEAD is IND-CPA secure, KDF is dual-PRF secure, MAC is instantiated by an HMAC, and the hash function H is modeled as a random oracle.*

*Proof.* To prove the theorem, we will show that the responses of Test-queries are independent of the initiator's and responder's long-term keys, i.e., the challenge bit b. In the identity hiding game, the adversary can make multiple Test-queries. Let $q_T$ and $q_H$ be the maximum number of Test-queries and random oracle queries made by the adversary. To prove all responses of Test-queries are independent of the challenge bit, we consider the following sequence of games. In the following, let $N = |U|$ be the number of honest users in the system.

**Game0:** This game is identical to the original IDHIDE security game. We thus have

$$ \Pr[\text{Game}_0 = 1] = \Pr[\text{Game}_{\text{WGKE},A}^{\text{IDHIDE}} = 1]. $$

**Game1,0:** In this game, we change how the KEM ciphertexts and session key ($ct_S$, $ss_S$) are generated. When a Test-query is made, if the challenge bit is $b=0$, a random $ss_S$ and simulated $ct_S$ generated with the simulator $S(1^\lambda)$ are used to answer the query. We can prove $Game_0$ and $Game_{1,0}$ are indistinguishable assuming the SPR-CCA security of KEM. To this end, we consider the following sub-hybrids between $Game_0$ and $Game_{1,0}$.

**Game0,t,0:** For the 1st through t-th Test-queries, if the challenge bit b is 0, a random $ss_S$ and simulated $ct_S$ are used to answer the Test-queries. Note that $Game_{0,0,0} = Game_0$ and $Game_{0,q_T,0} = Game_{1,0}$

We will construct a reduction $B_{1,0}$ that breaks the SPR-CCA security of KEM as follows.

$B_{1,0}$ receives a tuple $(pk^*, ct^*, ss^*)$ from its challenger. Then, $B_{1,0}$ samples a random $\hat{r} \leftarrow_S [N]$, which is the guess of the responder to the t-th Test-query, and $t \leftarrow_S [q_T]$. Then, it samples the challenge bit b and generates the long-term key pairs as follows. For the user $\hat{r}$, $B_{1,0}$ uses $pk^*$ as its long-term public key, and for all the other parties, $B_{1,0}$ computes the long-term key pairs correctly. Finally, $B_{1,0}$ invokes A and answers the queries made by A as follows:

* $O_{\text{Test}}^{\text{IDHIDE}}(i_0, r_0, i_1, r_1)$: If this is the t-th Test-query and $r_0 = \hat{r}$, $B_{1,0}$ responds as in the previous game except that $(ct^*, ss^*)$ is used as $(ct_S, ss_S)$ if $b=0$. Else if this is the t-th Test-query and $r_0 \ne \hat{r}$, $B_{1,0}$ aborts. Else, $B_{1,0}$ responds as in the previous game.

* $O_{\text{RevLSK}}(u)$: If $u = \hat{r}$ is queried, $B_{1,0}$ aborts. Otherwise, $B_{1,0}$ responds as in the previous game.
• $\mathcal{O}_{\text{CreatePSK}}(u)$, $\mathcal{O}_{\text{RevPSK}}(u)$, $\mathcal{O}_{\text{RevState}}(\text{idD})$, $\mathcal{O}_{\text{RevSessKey}}(\text{idD})$: $\mathcal{B}_{1,0}$ responds as in the previous game.

Finally, $\mathcal{A}$ outputs a guess $b'$. If $b = b'$, $\mathcal{B}_{1,0}$ outputs 0, else outputs 1 as its guess. If $\mathcal{B}_{1,0}$ does not abort, $\mathcal{B}_{1,0}$ perfectly simulates game $\text{Game}_{0,t-1,0}$ (resp. $\text{Game}_{0,t,0}$) to $\mathcal{A}$ when the challenge $(ct^*, ss^*)$ is the ciphertext and real key (resp. a simulated ciphertext and a random key). Also, the probability $\mathcal{B}_{1,0}$ does not abort is $1/N$ because there are $N$ candidates of the tested responder. Thus, we have

$$|\text{Pr}[\text{Game}_0 = 1] - \text{Pr}[\text{Game}_{1,0} = 1]| = N q_T \cdot \text{Adv}_{\text{KEM}, \mathcal{B}_{1,0}}^{\text{SPR-CCA}}(1^{\lambda}).$$

**Game$_{1,1}$:** In this game, we change how the KEM ciphertexts and session key $(ct_S, ss_S)$ are generated. When a Test-query is made, if the challenge bit is $b = 1$, a random $ss_S$ and simulated $ct_S$ generated with the simulator $S(1^{\lambda})$ are used to answer the query. Due to the same argument as in $\text{Game}_{1,0}$, we can prove $\text{Game}_{1,0}$ and $\text{Game}_{1,1}$ are indistinguishable assuming the SPR-CCA security of KEM, and we have

$$|\text{Pr}[\text{Game}_{1,0} = 1] - \text{Pr}[\text{Game}_{1,1} = 1]| \le N q_T \cdot \text{Adv}_{\text{KEM}, \mathcal{B}_{1,1}}^{\text{SPR-CCA}}(1^{\lambda}).$$

**Game$_{2,0}$:** In this game, we change how the RKEM ciphertexts and session key $(ct, ss)$ are generated. When a Test-query is made, if the challenge bit is $b = 0$, a random $ss$ and simulated $ct$ generated with the simulator $S(1^{\lambda}, \text{rpk}')$ are used, where $\text{rpk}'$ is the reinforcing public key generated during this Test-query. We can prove $\text{Game}_{1,1}$ and $\text{Game}_{2,0}$ are indistinguishable assuming the SPR-CCA security of RKEM. To this end, we consider the following sub-hybrid between $\text{Game}_{1,1}$ and $\text{Game}_{2,0}$.

**Game$_{1,t,0}$:** For the 1st through $t$-th Test-queries, a random $ss$ and simulated $ct$ are used if $b = 0$. Note that $\text{Game}_{1,0,0} = \text{Game}_{1,1}$ and $\text{Game}_{1,t,0} = \text{Game}_{2,0}$

We will construct a reduction $\mathcal{B}_{2,0}$ that breaks the SPR-CCA security of RKEM as follows.

$\mathcal{B}_{2,0}$ receives a challenge public key $pk^*$ from its challenger. $\mathcal{B}_{2,0}$ then samples the challenge bit $b$, a random $\hat{i} \leftarrow^s [N]$ and $t \leftarrow^s [q_T]$ and generates the long-term key pairs as follows. For the user $\hat{i}$, $\mathcal{B}_{2,0}$ uses $pk^*$ as its long-term public key, and for all the other parties, $\mathcal{B}_{2,0}$ computes the long-term key pairs correctly. Finally, $\mathcal{B}_{2,0}$ invokes $\mathcal{A}$ and answers the queries made by $\mathcal{A}$ as follows:

• $\mathcal{O}_{\text{Test}}^{\text{IDHIDE}}(i_0, r_0, i_1, r_1)$: If this is the $t$-th Test-query and $i_0 = \hat{i}$, $\mathcal{B}_{2,0}$ responds as in the previous game except that, if the challenge bit is $b = 0$, it generates $\text{rpk}$ and submits it to its challenger. It then receives $(ct^*, ss^*)$, and sets $(ct, ss) := (ct^*, ss^*)$ instead of generating them on its own. If this is the $t$-th Test-query but $i_0 \neq \hat{i}$, $\mathcal{B}_{2,0}$ aborts. Otherwise, $\mathcal{B}_{2,0}$ responds as in the previous game.

• $\mathcal{O}_{\text{RevLSK}}(u)$: If $u = \hat{i}$ is queried, $\mathcal{B}_{2,0}$ aborts. Otherwise, $\mathcal{B}_{2,0}$ responds as in the previous game.

• $\mathcal{O}_{\text{CreatePSK}}(u)$, $\mathcal{O}_{\text{RevPSK}}(u)$, $\mathcal{O}_{\text{RevState}}(\text{idD})$, $\mathcal{O}_{\text{RevSessKey}}(\text{idD})$: $\mathcal{B}_{2,0}$ responds as in the previous game.

If $\mathcal{A}$ outputs a guess $b'$, $\mathcal{B}_{2,0}$ outputs 0 if $b = b'$ and 1 otherwise as its guess. If $\mathcal{B}_{2,0}$ does not abort, $\mathcal{B}_{2,0}$ perfectly simulates game $\text{Game}_{1,t-1,0}$ (resp. $\text{Game}_{1,t,0}$) to $\mathcal{A}$ when the challenge $(ct^*, ss^*)$ is the ciphertext and real key (resp. a simulated ciphertext and a random key). Also, the probability

$\mathcal{B}_{2,0}$ does not abort is $1/N$ because there are $N$ candidates of the tested initiator. Thus, we have

$$|\text{Pr}[\text{Game}_{1,1} = 1] - \text{Pr}[\text{Game}_{2,0} = 1]| = N q_T \cdot \text{Adv}_{\text{RKEM}, \mathcal{B}_{2,0}}^{\text{SPR-CCA}}(1^{\lambda}).$$

**Game$_{2,1}$:** In this game, we change how the RKEM ciphertexts and session key $(ct_S, ss_S)$ are generated with the simulator $S(1^{\lambda}, \text{rpk}')$. When a Test-query is made, if the challenge bit is $b = 1$, a random $ss$ and simulated $ct$ are used to answer the query. Due to the same argument that prove the indistinguishability of $\text{Game}_{1,1}$ and $\text{Game}_{2,0}$, we can prove $\text{Game}_{2,0}$ and $\text{Game}_{2,1}$ are indistinguishable assuming the SPR-CCA security of RKEM, and we have

$$|\text{Pr}[\text{Game}_{2,0} = 1] - \text{Pr}[\text{Game}_{2,1} = 1]| \le N q_T \cdot \text{Adv}_{\text{KEM}, \mathcal{B}_{2,1}}^{\text{SPR-CCA}}(1^{\lambda}).$$

**Game$_{3,0}$:** In this game, we change how AEAD keys are generated. When a Test-query is made, the game samples random $K_{1\text{tk}}$ and $C_4$ instead of computing them with the KDF. Since $ss_S$ is chosen uniformly at random in the previous game, the dual-PRF security guarantees that $\text{Game}_{2,1}$ and $\text{Game}_{3,0}$ are indistinguishable. Since $q_T$ Test-queries are made, we have

$$|\text{Pr}[\text{Game}_{2,1} = 1] - \text{Pr}[\text{Game}_3 = 1]| \le q_T \cdot \text{Adv}_{\text{KDF}, \mathcal{B}_{3,0}}^{\text{PRF}}(1^{\lambda}).$$

**Game$_{3,1}$:** In this game, we change how AEAD keys are generated. When a Test-query is made, the game samples a random $C_5$ instead of computing it with the KDF. Since $C_4$ is chosen uniformly at random in the previous game, the dual-PRF security guarantees that $\text{Game}_{3,0}$ and $\text{Game}_{3,1}$ are indistinguishable. Since $q_T$ Test-queries are made, we have

$$|\text{Pr}[\text{Game}_{3,0} = 1] - \text{Pr}[\text{Game}_{3,1} = 1]| \le q_T \cdot \text{Adv}_{\text{KDF}, \mathcal{B}_{3,1}}^{\text{PRF}}(1^{\lambda}).$$

**Game$_{3,2}$:** In this game, we change how AEAD keys are generated. When a Test-query is made, the game samples a random key $K_{\text{time}}$ instead of computing it with the KDF. Since $C_5$ is chosen uniformly at random in the previous game, the dual-PRF security guarantees that $\text{Game}_{3,1}$ and $\text{Game}_{3,2}$ are indistinguishable. Since $q_T$ Test-queries are made, we have

$$|\text{Pr}[\text{Game}_{3,1} = 1] - \text{Pr}[\text{Game}_{3,2} = 1]| \le q_T \cdot \text{Adv}_{\text{KDF}, \mathcal{B}_{3,2}}^{\text{PRF}}(1^{\lambda}).$$

**Game$_{3,3}$:** In this game, we change how AEAD keys are generated. When a Test-query is made, the game samples a random key $K_{\text{empty}}$ instead of computing it with the KDF. Since $ss$ is chosen uniformly at random in this game, the dual-PRF security guarantees that $\text{Game}_{3,2}$ and $\text{Game}_{3,3}$ are indistinguishable. Since $q_T$ Test-queries are made, we have

$$|\text{Pr}[\text{Game}_{3,2} = 1] - \text{Pr}[\text{Game}_{3,3} = 1]| \le q_T \cdot \text{Adv}_{\text{KDF}, \mathcal{B}_{3,3}}^{\text{PRF}}(1^{\lambda}).$$

**Game$_{4}$:** In this game, the AEAD ciphertexts $\text{ltk}$, $\text{time}$, $\text{rkem}$ and $\text{empty}$ are replaced with a random bit-string of length $|\text{H}(\text{pk}_C)|$, $|t_{\text{now}}|$ and $|ct|$, respectively. Since the AEAD keys $K_{1\text{tk}}$, $K_{\text{time}}$ and $K_{\text{empty}}$ are chosen uniformly at random in the previous game, the IND-CPA security guarantees that $\text{Game}_{3,3}$ and $\text{Game}_4$ are indistinguishable. Since there are $3 \cdot q_T$ AEAD ciphertexts, we have

$$|\text{Pr}[\text{Game}_{3,3} = 1] - \text{Pr}[\text{Game}_4 = 1]| \le 3q_T \cdot \text{Adv}_{\text{AEAD}, \mathcal{B}_4}^{\text{IND-CPA}}(1^{\lambda}).$$
**Game5:** In this game, the MAC key $H(lb_{13}||pk_S)$ is replaced with a uniformly random key for all tested responders. Here, note that $lb_{13}$ is a fixed value across the system [3, Sec. 5.4]. In the classical ROM, the probability that an adversary notices this change is easily bounded by $q_H \cdot p$, where $p$ is the maximum probability of any outcome of the server's long-term public key $pk_S$. In the QROM, we can instead use the semi-classical One-Way to Hiding [53] to bound this by $4 \cdot q_H \cdot \sqrt{p}$; we note that the semi-classical variant gives tighter bounds compared to Lemma 4 which would give us an additional $\sqrt{q_H}$. Since we assume that the server's long-term public key $pk_S$ has high min-entropy (i.e., $p = \text{negl}(\lambda)$), we have

$$|\text{Pr}[\text{Game}_4 = 1] - \text{Pr}[\text{Game}_5 = 1]| = \text{negl}(\lambda).$$

**Game6:** In this game, the MAC key $H(lb_{13}||pk_C)$ is replaced with a uniformly random key for all tested initiators. Following the same argument as in Game5, we have the following assuming the high min-entropy of the client's long-term public key $pk_C$:

$$|\text{Pr}[\text{Game}_5 = 1] - \text{Pr}[\text{Game}_6 = 1]| = \text{negl}(\lambda).$$

**Game7:** In this game, the MAC tag $m1$ is replaced with a random value. Since we assume MAC is instantiated with HMAC and HMAC is a PRF, the output of MAC is indistinguishable from a random value. Therefore, the two games are indistinguishable. Since at most $2q_T$ MAC tags $m1$ are generated through Test-queries in total, we have

$$|\text{Pr}[\text{Game}_6 = 1] - \text{Pr}[\text{Game}_7 = 1]| \le 2q_T \cdot \text{Adv}_{\text{HMAC}, B_5}^{\text{PRF}}(\lambda).$$

**Game8:** In this game, if the challenged users use a non-zero cookie value, the MAC key $H cookie)$ is replaced with a random key. Recall that when cookie is a non-zero value, it has high min-entropy conditioned that the server's long-term public key $pk_S$ has high min-entropy (cf. Sec. 3.1). Therefore, following the same argument as in Game5, the two games are indistinguishable, and we have

$$|\text{Pr}[\text{Game}_7 = 1] - \text{Pr}[\text{Game}_8 = 1]| = \text{negl}(\lambda).$$

**Game9:** In this game, if the challenged users use a non-zero cookie value, the MAC tag $m2$ is replaced with a random value. Since we assume MAC is instantiated with HMAC and HMAC is a PRF, the output of MAC is indistinguishable from a random value. Therefore, the two games are indistinguishable. Since at most $2q_T$ MAC tags $m2$ are generated through Test-queries in total, we have

$$|\text{Pr}[\text{Game}_8 = 1] - \text{Pr}[\text{Game}_9 = 1]| \le 2q_T \cdot \text{Adv}_{\text{HMAC}, B_6}^{\text{PRF}}(\lambda).$$

In Game9, the responses of Test-queries are independent of the public keys of the initiator and responder, i.e., the challenge bit $b$. Therefore, $\text{Pr}[\text{Game}_9 = 1] = 1/2$. Combining all arguments together, we obtain

$$\begin{aligned} \text{Adv}_{\text{WGKE}, A}^{\text{IDHIDE}}(\lambda) & \le 2Nq_T \cdot (\text{Adv}_{\text{KEM}, B_1}^{\text{SPR-CCA}}(\lambda) + \text{Adv}_{\text{RKEM}, B_1}^{\text{SPR-CCA}}(\lambda)) \\ & + q_T \cdot (4\text{Adv}_{\text{KDF}, B_3}^{\text{PRF}}(\lambda) + 3\text{Adv}_{\text{AEAD}, B_4}^{\text{IND-CPA}}(\lambda)) \\ & + 2q_T \cdot (\text{Adv}_{\text{HMAC}, B_5}^{\text{PRF}}(\lambda) + \text{Adv}_{\text{HMAC}, B_6}^{\text{PRF}}(\lambda)) + \text{negl}(\lambda). \end{aligned}$$

□

We note in Game8 and Game9 above, we implicitly restrict the adversary to query the test oracle $O^{\text{IDHIDE}}_{\text{Test}}$ so that cookie is either a fixed string or not for both challenged initiators, as otherwise, there would be a trivial distinguishing attack observing $m2$.

# 6. Generic Construction of Reinforced KEM

We show how to construct the desired CCA secure RKEM by applying the Fujisaki-Okamoto (FO) transform [17] to a specific one-way (OW) secure PKE called a reinforced double-message PKE (RPKE2).4 Once this “right” definition of RPKE2 is set in place, we can naturally apply the FO transform, with a security proof following closely to those used by standard KEMs. Notably, the security proof is given in the QROM, building on the recent progress in FO-based KEMs, e.g., [49], [51], [66], [67].

## 6.1. Reinforced Double-Message PKE

Similarly to an RKEM, an RPKE2 comes with a reinforcing public key rpk to strengthen the security of the standard public key pk. The main difference is that RPKE2 is capable of encrypting and decrypting two messages, each corresponding to pk and rpk, as opposed to a single session key as in RKEM. We further require an RPKE2 to come with a half decryption algorithm $RHalfDec_2$, allowing to decrypt the message for pk. More formally, we have the following.

**Definition 21.** A reinforced double-message PKE (RPKE2) with message space $\mathcal{M}$ consists of the following algorithms. $\text{KeyGen}_2(1^\lambda) \to (\text{pk}, \text{sk})$: On input the security parameter $1^\lambda$, it outputs a (standard) public and secret key pair $(\text{pk}, \text{sk})$.

$\text{RKeyGen}_2(\text{pk}) \to (\text{rpk}, \text{rsk})$: On input a public key pk, it outputs a reinforcing public and secret key pair $(\text{rpk}, \text{rsk})$. We assume pk defines the set of reinforced public keys $\mathcal{RPK}(\text{pk})$, whose set membership can be efficiently checked. $\text{REnc}_2(\text{pk}, \text{rpk}, \mu, \mu_r) \to \text{ct}$: On input a standard and reinforcing public key pair $(\text{pk}, \text{rpk})$ and two messages $(\mu, \mu_r) \in \mathcal{M} \times \mathcal{M}$, it outputs a ciphertext ct.

$\text{RHalfDec}_2(\text{sk}, \text{ct}) \to \mu$: On input a standard secret key sk and a ciphertext ct, it outputs a message $\mu \in \mathcal{M}$.

$\text{RDec}_2(\text{sk}, \text{rsk}, \text{ct}) \to (\mu, \mu_r)$: On input a standard and reinforcing secret key pair $(\text{sk}, \text{rsk})$ and a ciphertext ct, it outputs two messages $(\mu, \mu_r) \in \mathcal{M} \times \mathcal{M}$.

We require a RPKE2 to be correct with overwhelming probability over the random choice of the keys and encryption algorithm.

**Definition 22** ($\delta_c$-Correctness). We say that RPKE2 is $\delta_c$-correct if for any $\lambda \in \mathbb{N}$, the following is greater than equal to $1 - \delta$:

$$\text{Exp} \left[ \max_{[\mu, \mu_r) \in \mathcal{M} \times \mathcal{M}} \text{Pr} \left[ (\mu, \mu_r) = \text{RDec}_2(\text{sk}, \text{rsk}, \text{REnc}_2(\text{pk}, \text{rpk}, \mu, \mu_r)) \right] \right],$$

4. While the RPKE2 requires some level of indistinguishability flavor, we call it one-way secure to be consistent with prior works on FO transforms.
1: function $\overline{\text{KeyGen}_2}(1^\lambda)$
2: $\left(\text{pk}, \text{sk}\right) \stackrel{\$}{\leftarrow} \text{KeyGen}_2(1^\lambda)$

3: $\left.\begin{array}{l} \text{return } \text{pk} \end{array}\right.$

4: function $\overline{\text{RKeyGen}_2}(\text{pk})$

5: $\left(\text{rpk}, \text{rsk}\right) \stackrel{\$}{\leftarrow} \text{RKeyGen}_2(\text{pk})$

6: $\left.\begin{array}{l} \text{return } \text{rpk} \end{array}\right.$

7: function $\overline{\text{REnc}_2}(\text{pk}, \text{rpk}, \mu, \mu_r)$
8: $r := \text{F}(\text{rpk}, \mu, \mu_r)$
9: $\text{ct} := \text{REnc}_2(\text{pk}, \text{rpk}, \mu, \mu_r; r)$
10: $\left.\begin{array}{l} \text{return } \text{ct} \end{array}\right.$

11: function $\overline{\text{RDec}_2}(\text{sk}, \text{rsk}, \text{ct})$

12: $\left(\mu', \mu'_r\right) \stackrel{\$}{\leftarrow} \text{RDec}_2(\text{sk}, \text{rsk}, \text{ct})$

13: $\left.\begin{array}{l} \text{return } \mu' \end{array}\right.$

<caption>Figure 8. The T transform: a deterministic $\overline{\text{RPKE}_2} := \text{T}[\text{RPKE}_2, \text{F}]$ from a probabilistic $\overline{\text{RPKE}_2}$ and a hash function F.</caption>

**6.2.1. T Transform: Probabilistic RPKE<sub>2</sub> ⇒ Deterministic RPKE<sub>2</sub>.** This transforms a probabilistic RPKE<sub>2</sub> into a deterministic RPKE<sub>2</sub>, formally depicted in Fig. 8. Derandomization is done by deterministically deriving the encryption randomness via a hash of the reinforcing public key and two messages (cf. Ln. 8).

As in the standard PKE setting, the T transform preserves the CX-IND security of disjoint simulatability (cf. Def. 25). Looking ahead, we directly establish the statistical disjointness of our lattice-based $\overline{\text{RPKE}}_2$ from the MLWE assumption (cf. Fig. 7). The following theorem establishes the security of the T transform.

**Theorem 5.** Let RPKE<sub>2</sub> be a probabilistic RPKE<sub>2</sub> that is CX-IND and OW-XCPA secure for $X \in \{\emptyset, \mathbb{R}\}$. Then, $\overline{\text{RPKE}}_2 = \text{T}[\text{RPKE}_2, \text{F}]$ in Fig. 8 is CX-IND secure for $X \in \{\emptyset, \mathbb{R}\}$ in the QROM.

Formally, for all $X \in \{\emptyset, \mathbb{R}\}$, any quantum adversary $\mathcal{A}$ against CX-IND security of RPKE<sub>2</sub> making at most $Q_F$ queries to the random oracle F, there exists quantum adversaries $\mathcal{B}_1$ against CX-IND security and $\mathcal{B}_2$ against OW-XCPA security of RPKE<sub>2</sub> such that

$$ \text{Adv}_{\overline{\text{RPKE}}_2, \mathcal{A}}^{\text{CX-IND}}(1^{\lambda}) \le 2 \cdot Q_F \cdot \sqrt{\text{Adv}_{\overline{\text{RPKE}}_2, \mathcal{B}_2}^{\text{OW-XCPA}}(1^{\lambda}) + \text{Adv}_{\overline{\text{RPKE}}_2, \mathcal{B}_1}^{\text{CX-IND}}(1^{\lambda})} $$

*Proof Sketch.* The proof is almost identical to those in the standard PKE setting [49], [51], [66], [67]. In particular, the oneway to hiding lemma [53] allows us to argue that sampling an encryption randomness $r$ uniformly random is indistinguishable from setting it as $r := \text{F}(\text{rpk}, \mu, \mu_r)$, assuming the hardness of the OW security of the probabilistic RPKE<sub>2</sub>. The full proof is in Sec. D.1. $\square$

**6.2.2. $U_m^\lambda$ Transform: Deterministic $\overline{\text{RPKE}}_2 \Rightarrow \text{RKEM}$.** This transforms a OW secure deterministic $\overline{\text{RPKE}}_2$ into a CCA secure RKEM with implicit rejection, formally depicted in Fig. 9. Namely, when the underlying $\overline{\text{RPKE}}_2$ fails the re-encryption check (i.e., decryption fails), we output a random value derived by seeds included in the secret keys, as opposed to outputting a special $\perp$ symbol indicating an explicit decryption failure.

As in the standard PKE setting, the resulting RKEM is SPR-CCA and IND-RCCA secure if the underlying deterministic $\overline{\text{RPKE}}_2$ is disjoint-simulatable.

**Theorem 6.** Let RPKE<sub>2</sub> be a probabilistic RPKE<sub>2</sub>. Let $\overline{\text{RPKE}}_2$ be a derandomized $\text{T}[\text{RPKE}_2, \text{F}]$ in Fig. 8 such that it is $\delta_{\text{hc}}$-half and $\delta_{\text{c}}$-correct and disjoint-simulatable. Then, RKEM := $U_m^\lambda[\overline{\text{RPKE}}_2, \text{H}, \text{H}_{\text{prf}}]$ in Fig. 9 is $\delta_{\text{c}}$-correct, SPR-CCA, and IND-RCCA secure in the QROM.

1: function KeyGen(1^λ)
2:   (pk, sk') $\stackrel{\$}{\leftarrow}$ KeyGen2(1^λ)
3:   s $\stackrel{\$}{\leftarrow}$ {0, 1}^l
4:   sk := (sk', s)
5:   $\left.\begin{array}{l} \text{return } \text{pk}, \text{sk} \end{array}\right.$

6: function RKeyGen(pk)
7:   (rpk, rsk') $\stackrel{\$}{\leftarrow}$ RKeyGen2(pk)
8:   s<sub>r</sub> $\stackrel{\$}{\leftarrow}$ {0, 1}^l
9:   rsk := (rsk', s<sub>r</sub>)
10:  $\left.\begin{array}{l} \text{return } \text{rpk}, \text{rsk} \end{array}\right.$

11: function $\overline{\text{REnc}}(\text{pk}, \text{rpk})$

12: $\left(\mu, \mu_r\right) \stackrel{\$}{\leftarrow} \mathcal{M} \times \mathcal{M}$

13: $\text{ct} := \text{REnc}_2(\text{pk}, \text{rpk}, \mu, \mu_r)$

14: $\text{ss} := \text{H}(\text{rpk}, \mu, \mu_r)$

15: $\left.\begin{array}{l} \text{return } \text{(ct, ss)} \end{array}\right.$

16: function $\text{RDec}(\text{sk}, \text{rsk}, \text{ct})$

17: $\text{parse} (\text{sk}', s) \leftarrow \text{sk}$

18: $\text{parse} (\text{rsk}', s_r) \leftarrow \text{rsk}$

19: $\left(\mu', \mu'_r\right) \stackrel{\$}{\leftarrow}$ $\overline{\text{RDec}}_2(\text{sk}', \text{rsk}', \text{ct})$
20: $\left.\begin{array}{l} \text{if } \llbracket \mu' = \perp \rrbracket \lor \llbracket \mu'_r = \perp \rrbracket \lor \\ \phantom{\text{if }} \llbracket \text{ct} \neq \overline{\text{REnc}}_2(\text{pk}, \text{rpk}, \mu', \mu'_r) \rrbracket \\ \phantom{\text{if }} \text{then} \end{array}\right.$

21: $\left.\begin{array}{l} \text{return } \text{ss} := \\ \phantom{\text{return }} \text{H}_{\text{prf}}(s, s_r, \text{rpk}, \text{ct}) \end{array}\right.$

22: $\left.\begin{array}{l} \text{return } \text{ss} := \text{H}(\text{rpk}, \mu', \mu'_r) \end{array}\right.$

<caption>Figure 9. The $U_m^\lambda$ transform: an RKEM := $U_m^\lambda[\overline{\text{RPKE}}_2, \text{H}, \text{H}_{\text{prf}}]$ from a deterministic $\overline{\text{RPKE}}_2 := \text{T}[\text{RPKE}_2, \text{F}]$ (cf. Fig. 8).</caption>

Formally, for any quantum adversary $\mathcal{A}$ against SPR-CCA security of RKEM making at most $Q_{\text{dec}}$, $Q_{\text{rpk}}$ queries to the decapsulation and reinforced key generation oracles, respectively, and $Q_F$, $Q_H$, $Q_{H_{\text{prf}}}$ queries to the random oracles F, H, $H_{\text{prf}}$, respectively, there exists a quantum adversary $\mathcal{B}$ against CR-IND security of RPKE<sub>2</sub> such that

$$ \begin{aligned} \text{Adv}_{\text{RKEM}, \mathcal{A}}^{\text{SPR-CCA}}(1^{\lambda}) \le \text{Adv}_{\overline{\text{RPKE}}_2, \mathcal{B}}^{\text{CR-IND}}(1^{\lambda}) + \text{Disj}_{\overline{\text{RPKE}}_2}(1^{\lambda}) \\ + 4 \cdot (\delta_{\text{hc}} + Q_{\text{rpk}} \cdot \delta_{\text{c}}) + (Q_{\text{dec}} + Q_{H_{\text{prf}}}) \cdot 2^{-\frac{\ell}{2}+2} \\ + 16 \cdot (Q_F + Q_{\text{dec}} + 2)^2 \cdot (\delta_{\text{hc}} + Q_{\text{rpk}} \cdot \delta_{\text{c}}) \\ + 16 \cdot (Q_F + Q_H + 2)^2 \cdot (\delta_{\text{hc}} + Q_{\text{rpk}} \cdot \delta_{\text{c}}). \end{aligned} $$

Moreover, for any adversary $\mathcal{A}$ against IND-RCCA security of RKEM making at most $Q_{\text{dec}}$ queries to the decapsulation oracle and $Q_F$, $Q_H$, $Q_{H_{\text{prf}}}$ queries to F, H, $H_{\text{prf}}$, respectively, there exists a quantum adversary $\mathcal{B}$ against C-IND security of $\overline{\text{RPKE}}_2$ such that

$$ \begin{aligned} \text{Adv}_{\text{RKEM}, \mathcal{A}}^{\text{IND-RCCA}}(1^{\lambda}) \le \text{Adv}_{\overline{\text{RPKE}}_2, \mathcal{B}}^{\text{C-IND}}(1^{\lambda}) + \text{Disj}_{\overline{\text{RPKE}}_2}(1^{\lambda}) \\ + 4 \cdot \delta_{\text{c}} + (Q_{\text{dec}} + Q_{H_{\text{prf}}}) \cdot 2^{-\frac{\ell}{2}+2} \\ + 16 \cdot (Q_F + Q_{\text{dec}} + 2)^2 \cdot \delta_{\text{c}} + 16 \cdot (Q_F + Q_H + 2)^2 \cdot \delta_{\text{c}}. \end{aligned} $$

*Proof Sketch.* We provide the full proof in Sec. D.2 and provide a proof sketch below. Correctness is directly inherited from the underlying $\overline{\text{RPKE}}_2$. Below, we only focus on SPR-CCA security since the proof of IND-RCCA security is analogous. Our high level proof strategy follows those of [49, Theorem 4.1], which is also an extension of those used in [51], [66], [67]. The main difference is that our challenge ciphertext may be generated with respect to a malicious reinforcing public key.

We first modify $\overline{\text{RPKE}}_2$ to be perfectly correct by tweaking the random oracle F (cf. Fig. 8) to only output randomness that leads to correct (half) decryption. This is possible relying on (half) correctness. Now, let us consider the following two functions:

$$ g_L(\text{rpk}, \mu, \mu_r) := (\text{rpk}, \overline{\text{REnc}}_2(\text{pk}, \text{rpk}, \mu, \mu_r)) $$

$$ g_{\neg L}(\text{rpk}, \mu, \mu_r) := (\text{rpk}, \overline{\text{REnc}}_2(\text{pk}, \text{rpk}, \mu, \mu_r), \mu_r). $$

If $\text{rpk} \in L$, $g_L$ is injective due to perfect correctness, where recall $L$ is the list of honestly generated rpks (cf. Fig. 5).
<table><caption>TABLE 1. PARAMETERS AND NOTATIONS WHERE ALL THE HASH FUNCTIONS ARE MODELED AS RANDOM ORACLES. SEE SEC. 2.3 FOR THE DEFINITIONS OF Compress_q AND Decompress_q.</caption><thead><tr><th>Notation</th><th>Explanation</th></tr></thead><tbody><tr><td>(R<sub>q</sub>, d)</td><td>Polynomial ring with prime modulus q and degree d</td></tr><tr><td>(n, k)</td><td>Dimension of public matrix A ∈ R<sub>q</sub><sup>n×k</sup></td></tr><tr><td>d<sub>r</sub></td><td>Amount of bits after compressing rk such that d<sub>r</sub> &lt; ⌈log<sub>2</sub>(q)⌋</td></tr><tr><td>(d<sub>u</sub>, d<sub>c</sub>, d<sub>v1</sub>)</td><td>Amount of bits after compressing ct such that d<sub>a</sub> &lt; ⌈log<sub>2</sub>(q)⌋ with a ∈ {u, v<sub>0</sub>, v<sub>1</sub>}</td></tr><tr><td>(χ, χ<sub>s</sub>, χ<sub>t</sub>)</td><td>Noise distributions over R<sub>q</sub></td></tr><tr><td>Compress<sub>q</sub></td><td>Rounding operations from Kyber [19]</td></tr><tr><td>Decompress<sub>q</sub></td><td></td></tr><tr><td>[·]<sup>q/2</sup></td><td>Compression function [a]<sup>q/2</sup> := Compress<sub>q</sub>(a, 1)</td></tr><tr><td>G<sub>Decomp</sub></td><td>Hash function for randomized decompression<br>G<sub>Decomp</sub>: b̄ ∈ Z<sub>d<sub>q</sub></sub><sup>nd</sup> → {b̄' ∈ R<sub>q</sub><sup>n</sup> | Compress<sub>q</sub>(b̄', d<sub>r</sub>) = b̄}</td></tr><tr><td>G</td><td>Hash function G: {0, 1}<sup>256</sup> → R<sub>q</sub><sup>n×k</sup></td></tr><tr><td>G<sub>r</sub></td><td>Hash function G<sub>r</sub>: M → Z<sub>d<sub>v1</sub></sub><sup>q</sup></td></tr></tbody></table>

However, for a maliciously generated rpk $\notin L$, $g_L$ may not be injective as correctness is no longer guaranteed. This is why we introduce $g_{\neg L}$, a function guaranteed to be injective relying only on perfect half-correctness. We can then simulate the quantum random oracle $H(rpk, \mu, \mu_r)$ as $H_L \circ G_L(rpk, \mu, \mu_r)$ if rpk $\in L$ and as $H_{\neg L} \circ g_{\neg L}(rpk, \mu, \mu_r)$ otherwise, where $H_L$ and $H_{\neg L}$ are two independent random oracles that are only accessible to the adversary via querying $H$.

Now, assume an adversary queries a challenge ciphertext ct* on a maliciously generated rpk' $\in \neg L$; we ignore the case rpk' $\in L$ as it is trivial. Notice the key is generated as $ss^* := H_{\neg L} \circ g_{\neg L}(rkp', \mu^*, \mu_r^*) = H_{\neg L}(rkp, REnc_2(rpk, rpk, \mu^*, \mu_r^*), \mu_r^*) = H_{\neg L}(rkp, ct^*, \mu_r^*)$. Relying on CR-IND security of RPKE<sub>2</sub>, a ct* is indistinguishable from the simulator's output ct* $\stackrel{\$}{\leftarrow} S(1^\lambda, rpk', \mu_r^*)$. Moreover, the simulated ct* is an invalid ciphertext due to statistical disjointness. Since the adversary can only learn the outputs of $H_{\neg L}$ on valid ciphertexts, $ss^*$ is information theoretically hidden from the adversary. This completes the proof. □

# 7. Our Lattice-based Reinforced KEM: Rebar

In this section, we construct a lattice-based OW secure RPKE<sub>2</sub>. The construction is given in Fig. 10, where the notations are summarized in Tab. 1. Our desired CCA secure RKEM, Rebar, is then obtained by applying the T and U<sub>m</sub><sup>L</sup> transforms from Sec. 6.2.

At a high-level, our construction resembles the multi-recipient adaptation [18] of ML-KEM [19]. It uses MLWE samples $A \cdot s + x$ for both the public key b and reinforcing key b<sub>r</sub>. Then, it encrypts a pair of messages $(\mu, \mu_r)$ to the two keys by sampling a fresh MLWE sample $u = r^\top \cdot A + z^\top$ and two polynomials $v_0 = r^\top \cdot b + z + \mu \cdot [q/2]$, $v_1 = r^\top \cdot b_r + z_r + \mu_r \cdot [q/2]$. Our security model considers the possibility that the reinforcing key is chosen maliciously, which could undermine security. We resolve this challenge by deriving a uniform vector $\Delta$ from $\mu$ and masking $v_1$ with it to prevent extracting information from $v_1$ without knowing the secret key of b as well. On top of that, we introduce rounding optimizations, with the novel rounding of the reinforcing public key and reliance on a randomized decompression $G_{Decomp}$ to preserve security.

$$
\begin{align*}
1: \quad & \mathbf{function} \ KeyGen_2(1^\lambda) \\
2: \quad & \qquad \mathbf{seed}_A \stackrel{\$}{\leftarrow} \{0, 1\}^{256} \\
3: \quad & \qquad \mathbf{A} := G(\mathbf{seed}_A) \in R_q^{n \times k} \\
4: \quad & \qquad (\mathbf{s}, \mathbf{x}) \stackrel{\$}{\leftarrow} \chi^k \times \chi^n \\
5: \quad & \qquad \mathbf{b} := \mathbf{A} \cdot \mathbf{s} + \mathbf{x} \\
6: \quad & \qquad \mathbf{pk} := (\mathbf{seed}_A, \mathbf{b}) \\
7: \quad & \qquad \mathbf{sk} := (\mathbf{seed}_A, \mathbf{s}) \\
8: \quad & \quad \mathbf{return} (\mathbf{pk}, \mathbf{sk}) \\
9: \quad & \mathbf{function} \ RKeyGen_2(\mathbf{pk}) \\
10: \quad & \qquad \mathbf{parse} (\mathbf{seed}_A, \mathbf{b}) \leftarrow \mathbf{pk} \\
11: \quad & \qquad \mathbf{A} := G(\mathbf{seed}_A) \\
12: \quad & \qquad (\mathbf{s}_r, \mathbf{x}_r) \stackrel{\$}{\leftarrow} \chi^k \times \chi^n \\
13: \quad & \qquad \mathbf{b}_r := \mathbf{A} \cdot \mathbf{s}_r + \mathbf{x}_r \\
14: \quad & \qquad \overline{\mathbf{b}_r} := \text{Compress}_q(\mathbf{b}_r, d_{b_r}) \\
15: \quad & \quad \mathbf{return} (\mathbf{rk}, \mathbf{rsk}) := (\overline{\mathbf{b}_r}, \mathbf{s}_r) \\
16: \quad & \mathbf{function} \ REnc_2(\mathbf{pk}, \mathbf{rk}_k, \mu, \mu_r) \\
17: \quad & \qquad \mathbf{parse} ((\mathbf{seed}_A, \mathbf{b}), \mathbf{b}_r) \leftarrow (\mathbf{pk}, \mathbf{rk}_k) \\
18: \quad & \qquad \mathbf{A} := G(\mathbf{seed}_A) \\
19: \quad & \qquad \mathbf{b}_r^* := G_{Decomp}(\mathbf{b}_r, d_{b_r}) \\
20: \quad & \qquad (\mathbf{r}, \mathbf{z}, \mathbf{z}_r) \stackrel{\$}{\leftarrow} \chi_r^\top \times \chi_r^k \times \chi_z \times \chi_r \\
21: \quad & \quad \mathbf{return} (\mu', \mu_r') \\
22: \quad & \quad \mathbf{Delta} := G_r(\mu') \\
23: \quad & \quad \mathbf{u} := \mathbf{r}^\top \cdot \mathbf{A} + \mathbf{z}^\top \\
24: \quad & \quad v_0 := \mathbf{r}^\top \cdot \mathbf{b} + z + \mu \cdot [q/2] \\
25: \quad & \quad v_1 := \mathbf{r}^\top \cdot \mathbf{b}_r^* \\
26: \quad & \quad + z_r + \mu_r \cdot [q/2] \\
27: \quad & \quad \overline{\mathbf{u}} := \text{Compress}_q(\mathbf{u}, d_u) \\
28: \quad & \quad \overline{v_0} := \text{Compress}_q(v_0, d_{v_0}) \\
29: \quad & \quad \overline{v_1} := \text{Compress}_q(v_1, d_{v_1}) \\
30: \quad & \quad \mathbf{return} \text{ct} := (\overline{\mathbf{u}}, \overline{v_0}, \overline{v_1} \oplus \mathbf{Delta})
\end{align*}
$$

$$
\begin{align*}
31: \quad & \mathbf{function} \ RDec_2(\mathbf{sk}, \mathbf{rsk}, \mathbf{ct}) \\
32: \quad & \qquad \mathbf{parse} ((\mathbf{seed}_A, \mathbf{s}), \mathbf{s}_r) \leftarrow (\mathbf{sk}, \mathbf{rsk}) \\
33: \quad & \qquad \mathbf{parse} (\overline{\mathbf{u}}, \overline{v_0}, \overline{v_1}) \leftarrow \mathbf{ct} \\
34: \quad & \qquad \mathbf{Delta} := G_r(\mu') \\
35: \quad & \qquad \overline{\mathbf{u}} := \text{Decompress}_q(\overline{\mathbf{u}}, d_u) \\
36: \quad & \qquad \overline{v_0} := \text{Decompress}_q(\overline{v_0}, d_{v_0}) \\
37: \quad & \qquad \overline{v_1} := \text{Decompress}_q(\overline{v_1} \oplus \mathbf{Delta}, \\
38: \quad & \qquad \qquad \qquad d_{v_1}) \\
39: \quad & \qquad \mathbf{\mu}' := [\overline{v_0} - \overline{\mathbf{u}}^\top \cdot \mathbf{s}]_{q/2} \\
40: \quad & \qquad \mathbf{\mu}' := [\overline{v_1} - \overline{\mathbf{u}}^\top \cdot \mathbf{s}_r]_{q/2} \\
41: \quad & \qquad \mathbf{return} (\mathbf{\mu}', \mathbf{\mu}_r')
\end{align*}
$$

<caption>Figure 10. Our lattice-based (probabilistic) RPKE<sub>2</sub> with hash functions G and G<sub>r</sub>. RHalfDec<sub>2</sub> is the same as RDec<sub>2</sub> except that it terminates on Ln. 39 and returns $\mu'$.</caption>

## 7.1. OW-(R)CPA Security

OW-CPA and OW-RCPA security of RPKE<sub>2</sub> follows immediately from the C-IND and CR-IND security, respectively, which we show in Sec. 7.2. Below, note that hash functions G, G<sub>r</sub>, G<sub>Decomp</sub> are all modeled as a (quantum) random oracle.

OW-CPA security.

**Theorem 7 (OW-CPA Security).** *The (probabilistic) RPKE<sub>2</sub> in Fig. 10 is OW-CPA in the QRROM assuming the hardness of the MLWE<sub>q,n,k,χ,χ</sub> and MLWE<sub>q,k+1,n,χ<sub>r</sub>,(χ<sub>i</sub>)<sub>i∈{k+1}</sub></sub> assumptions, where $\chi_i := \chi_r$ for all $i \in [k]$ and $\chi_{k+1} := \chi_z$. Formally, there exists an efficient simulator $\mathcal{S}$ such that for any quantum adversary $\mathcal{A}$ against C-IND security of RPKE<sub>2</sub> making at most $Q_{G_r}$ queries to the random oracle $G_r$, there exists quantum adversaries $\mathcal{B}_1$ against the MLWE<sub>q,n,k,χ,χ</sub> problem and $\mathcal{B}_2$, $\mathcal{B}_3$ against the MLWE<sub>q,k+1,n,χ<sub>i</sub>,(χ<sub>i</sub>)<sub>i∈{k+1}</sub></sub> problem such that*

$$
\text{Adv}_{\text{RPKE}_2, \mathcal{A}}(1^{\lambda}) \le \text{Adv}_{\mathcal{B}_1}^{\text{MLWE}}(1^{\lambda}) + 2 \cdot Q_{G_r} \cdot \sqrt{\text{Adv}_{\mathcal{B}_2}^{\text{MLWE}}(1^{\lambda}) + \frac{1}{|\mathcal{M}|}} \\
+ \text{Adv}_{\mathcal{B}_3}^{\text{MLWE}}(1^{\lambda}) + \frac{1}{|\mathcal{M}|}.
$$

*Proof.* The proof follows almost identically to the proof of C-IND security, which we later show in Thm. 9. Concretely, we go through the same game transitions from Game<sub>0</sub> to Game<sub>7</sub> in Thm. 9, where the only modification is that the adversary $\mathcal{A}$ outputs a message $\mu'$, as opposed to a bit $b'$ at the end of the game. In Game<sub>7</sub>, the challenge message $\mu^*$ is information theoretically hidden from $\mathcal{A}$, and the advantage of $\mathcal{A}$ is at most $\frac{1}{|\mathcal{M}|}$. Collecting all the bounds, we arrive at the theorem statement. □
OW-CPA security. Below, we rely on the hint-MLWE<sub>q,k+1,n,χ,χ<sub>z</sub>,F</sub> problem, where F is a distribution over $R_q^{1×(k+n+1)}$ that outputs $[x^T | -s^T | 0]$ with $(s, x) \stackrel{s}{\leftarrow} \chi^k \times \chi^n$.

**Theorem 8 (OW-RCPA Security).** *The (probabilistic) RPKE<sub>2</sub> in Fig. 10 is OW-RCPA in the QROM assuming the hardness of the hint-MLWE<sub>q,k+1,n,χ,χ<sub>z</sub>,F</sub> assumption.*

Formally, there exists an efficient simulator $S_r$ such that for any quantum adversary $\mathcal{A}$ against OW-CPA security of RPKE<sub>2</sub>, there exist quantum adversaries $\mathcal{B}_1$ against the MLWE<sub>q,k,n,χ,χ</sub> problem and $\mathcal{B}_2$ against the hint-MLWE<sub>q,k+1,n,χ<sub>r</sub>,χ<sub>z</sub>,F</sub> problem such that

$$ \mathrm{Adv}_{\mathrm{RPKE}_{2,\mathcal{A}}(1^{\lambda})}^{\mathrm{OW-CPA}} \le \mathrm{Adv}_{\mathcal{B}_1}^{\mathrm{MLWE}}(1^{\lambda}) + \mathrm{Adv}_{\mathcal{B}_2}^{\mathrm{hint-MLWE}}(1^{\lambda}) + \frac{1}{|\mathcal{M}|}. $$

*Proof.* The proof follows almost identically to the proof of CR-IND security, which we later show in Thm. 7. Concretely, we go through the same game transitions from Game<sub>0</sub> to Game<sub>5</sub> in Thm. 7, where the only modification is that the adversary $\mathcal{A}$ outputs a message $\mu'_r$, as opposed to a bit $b'$ at the end of the game. In Game<sub>5</sub>, the challenge message $\mu_r^*$ is information theoretically hidden from $\mathcal{A}$, and the advantage of $\mathcal{A}$ is at most $\frac{1}{|\mathcal{M}|}$. Collecting all the bounds, we arrive at the theorem statement. □

To apply the T transform, our lattice-based RPKE<sub>2</sub> must satisfy OW-(R)CPA and C(R)-IND security (cf. Def. 24 and 25); see Fig. 7 for the overview. As the proof of OW security follows naturally from the proof of IND security, we refer the formal statement to Sec. E.

## 7.2. Ciphertext (R-)Indistinguishability

The following two theorems establish the C-IND and CR-IND security, respectively. Below, we rely on the hint-MLWE<sub>q,k+1,n,χ,χ<sub>z</sub>,F</sub> problem as defined in the previous section.

**Theorem 9 (C-IND Security).** *The (probabilistic) RPKE<sub>2</sub> in Fig. 10 is C-IND in the QROM assuming the hardness of the MLWE<sub>q,n,k,χ,χ</sub> and MLWE<sub>q,k+1,n,χ<sub>r</sub>,(χ<sub>i</sub>)<sub>i∈{k+1}</sub></sub> assumptions, where $\chi_i := \chi_r$ for all $i \in [k]$ and $\chi_{k+1} := \chi_z$.

Formally, there exists an efficient simulator $S$ such that for any quantum adversary $\mathcal{A}$ against C-IND security of RPKE<sub>2</sub> making at most $Q_{G_r}$ queries to the random oracle $G_r$, there exists quantum adversaries $\mathcal{B}_1, \mathcal{B}_4$ against the MLWE<sub>q,n,k,χ,χ</sub> problem and $\mathcal{B}_2, \mathcal{B}_3$ against the MLWE<sub>q,k+1,n,χ,(χ<sub>i</sub>)<sub>i∈{k+1}</sub></sub> problem such that

$$ \mathrm{Adv}_{\mathrm{RPKE}_{2,\mathcal{A}}(1^{\lambda})}^{\mathrm{C-IND}} \le \mathrm{Adv}_{\mathcal{B}_1}^{\mathrm{MLWE}}(1^{\lambda}) + 2 \cdot Q_{G_r} \cdot \sqrt{\mathrm{Adv}_{\mathcal{B}_2}^{\mathrm{MLWE}}(1^{\lambda}) + \frac{1}{|\mathcal{M}|}} \\ + \mathrm{Adv}_{\mathcal{B}_3}^{\mathrm{MLWE}}(1^{\lambda}) + \mathrm{Adv}_{\mathcal{B}_4}^{\mathrm{MLWE}}(1^{\lambda}). $$

**Theorem 10 (CR-IND Security).** *The (probabilistic) RPKE<sub>2</sub> in Fig. 10 is CR-IND in the QROM assuming the hardness of the hint-MLWE<sub>q,k+1,n,χ<sub>r</sub>,χ<sub>z</sub>,F</sub> assumption.*

Formally, for any quantum adversary $\mathcal{A}$ against CR-IND security of RPKE<sub>2</sub>, there exist quantum adversaries $\mathcal{B}_1$ and

$\mathcal{B}_3$ against the MLWE<sub>q,k,n,χ,χ</sub> problem, and $\mathcal{B}_2$ against the hint-MLWE<sub>q,k+1,n,χ<sub>r</sub>,χ<sub>z</sub>,F</sub> problem such that

$$ \mathrm{Adv}_{\mathrm{RPKE}_{2,\mathcal{A}}(1^{\lambda})}^{\mathrm{CR-IND}} \le \mathrm{Adv}_{\mathcal{B}_1}^{\mathrm{MLWE}}(1^{\lambda}) \\ + \mathrm{Adv}_{\mathcal{B}_2}^{\mathrm{hint-MLWE}}(1^{\lambda}) + \mathrm{Adv}_{\mathcal{B}_3}^{\mathrm{MLWE}}(1^{\lambda}) + \mathrm{negl}(\lambda). $$

*Proof Sketch.* We provide the full proof in Secs. E.1 and E.2 and provide a proof sketch below. Let us first consider C-IND security. We define the simulator $S$ as follows: on input $(1^{\lambda}, \mathrm{rk}, \mu_r)$, it samples random $(\mathbf{u}, v_0, v_1) \stackrel{s}{\leftarrow} R_q^k \times R_q \times R_q$, and outputs a simulated ciphertext as $(\bar{\mathbf{u}}, \bar{v}_0, \bar{v}_1) := (\mathrm{Compress}_q(\mathbf{u}, d_u), \mathrm{Compress}_q(v_0, d_{v_0}), \mathrm{Compress}_q(v_1, d_{v_1}))$. Proving that this is indistinguishable from the real game follows from the key observation that $\bar{v}_1$ is one-time padded with $\Delta = G_r(\mu)$, where $\mu$ is encrypted under the standard public key. Notably, while the adversary possesses a reinforcing secret key, $\bar{v}_1$ looks pseudorandom since $(\bar{\mathbf{u}}, \bar{v}_0)$ is pseudorandom under the MLWE assumption.

CR-IND security is quite different since the adversary has the standard secret key $sk^* = (\mathrm{seed}_\mathcal{A}, s)$. Namely, we must prove that $\mu_r^*$ remains hidden even if it can half decrypt the ciphertext. The key observation is that we can rewrite $v_0$ (i.e., the component associated to $s$) as $v_0 - \mu'_r \cdot [q/2] = \mathbf{r}^T \cdot \mathbf{b} + z = \mathbf{r}^T \cdot (\mathbf{A} \cdot \mathbf{s} + \mathbf{x}) + z = \mathbf{u} \cdot \mathbf{s} - \mathbf{z}^T \cdot \mathbf{s} + \mathbf{r}^T \cdot \mathbf{x} + z$, where $\mu'$ is the adversarially chosen message. Let us denote the underlined component as the hint $h$. Then the above shows that given $\mathbf{u}$ and $h$, we can simulate $v_0$ from $s$, and this hint $h$ is exactly what the hint-MLWE provides. Notably, given an hint-MLWE instance $(\mathbf{u}, v_1, h)$, the simulator simulates the challenge ciphertext component $v_0$ using $s$. As hint-MLWE stipulates that $(\mathbf{u}, v_1)$ is pseudorandom, this completes the proof. Note that $G_{\mathrm{Decomp}}$ is used to argue $\mathbf{b}_r^*$ in $v_1$ is distributed uniformly random, required to correctly invoke hint-MLWE. □

## 7.3. Remaining Properties

To complete the transform (cf. Fig. 7), it remains to prove that our deterministic RPKE<sub>2</sub> = T[RPKE<sub>2</sub>, F] satisfies statistical disjointness and (half)-correctness. As these are simple statistical properties, we refer the details to Secs. E.3 and E.4. By construction, we note that RKEM outputs standard and reinforcing public keys and session keys that have high min-entropy.

## 8. Implementation and Experiments

We first discuss how we instantiated and implemented our RKEM, Rebar, and our experiments with PQ WireGuard, followed by a discussion of benchmark results. Our implementations of PQ WireGuard, Rebar, and collected measurement data are available at github.com/pqwg/experiment.

### 8.1. Parameters and Instantiation of Our RKEM

Parameters of Rebar are chosen targeting NIST level I security with a 256-bit message space, overwhelming correctness and statistical disjointness. The hardness of MLWE is evaluated using the Lattice Estimator tool [68]. For
<table><caption>TABLE 2. INSTANTIATIONS OF PQ-WIREGUARD. HANDSHAKE TIME IS FOR AN INITIATOR. MESSAGE SIZES EXCLUDE OVERHEAD.</caption><thead><tr><th rowspan="2">Name</th><th colspan="3">Identity</th><th colspan="2">Per-peer identity storage</th><th colspan="2">Message size</th><th rowspan="2">Handshake time</th></tr><tr><th>Client</th><th>Server</th><th>Ephemeral</th><th>Client</th><th>Server</th><th>Initial</th><th>Response</th></tr></thead><tbody><tr><td>Classic</td><td>X25519</td><td>X25519</td><td>X25519</td><td>32 B</td><td>32 B</td><td>64 B</td><td>64 B</td><td>33.602 ms</td></tr><tr><td>PQWG [1]</td><td>McEliece 460896</td><td>McEliece 460896</td><td>Dagger [1]</td><td>524 160 B</td><td>524 160 B</td><td>1084 B</td><td>1148 B</td><td>36.292 ms</td></tr><tr><td>PQWG (Ours)</td><td>Rebar</td><td>McEliece 460896</td><td>Rebar</td><td>524 160 B</td><td>1376 B</td><td>1052 B</td><td>1088 B</td><td>36.887 ms</td></tr></tbody></table>

hint-MLWE, we follow prior works [69]–[71], and use the MLWE parameters provided by its proven reduction for Gaussian secrets [47] with the estimator. Concretely, we bound overwhelmingly the spectral norm of the hint matrix $M$ in the hint $h = M [s^\top \ x^\top]^\top + z$ by a constant $B$, and compute a reduced MLWE standard deviation $\sigma_{red}^{-2} = \frac{1}{\sigma^2} + \frac{B^2}{\sigma_r^2}$. In our case, $M$ is composed of Gaussian sampled polynomials, previously studied in [72]. Note that we can improve sizes and efficiency relying on sums of uniforms instead of Gaussians as in [71] while relying on heuristic security of hint-MLWE. As we aimed for more conservative and robust parameters, we chose Gaussians.

We base the implementation of Rebar on the reference implementation of ML-KEM from PQClean [73]. Notably we change the NTT algorithm to tackle our different modulus $q$, and use discrete Gaussian sampling based on reverse cumulative distribution tables (RCDT) as in [74] for $\chi, \chi_r, \chi_z$. Its implementation remains simpler and easier to verify than NTRU-based KEMs [75], [76]. All secret-dependent operations are constant-time.

We compute the RCDT constants with 72-bit precision as prescribed in [77]. This analysis relies on Rényi divergence which applies to the search games OW-CPA and OW-RCPA. For C-IND and CR-IND, this slightly modifies the distributions used in hint-MLWE and MLWE. As the concrete security of these assumptions mainly relies on the entropy of the input distributions, we argue that this precision does not substantially affect our concrete security.

We compare the performance against reference implementation of ML-KEM-512 used for forward secrecy and ephemeral key exchange in Tab. 3. Note that as RKEM encapsulations target two public keys, KEM.Encaps needs to be called twice for equivalent use.

<table><caption>TABLE 3. PERFORMANCE AND SIZES OF ML-KEM VERSUS REBAR. BENCHMARKS WERE OBTAINED ON AN INTEL CORE-i7 12700H CPU.</caption><thead><tr><th colspan="3">ML-KEM-512</th><th colspan="3">Rebar</th></tr><tr><th>Operation</th><th>Cycles</th><th>Size</th><th>Operation</th><th>Cycles</th><th>Size</th></tr></thead><tbody><tr><td>KEM.KeyGen</td><td>60 364</td><td>800 B</td><td>KeyGen</td><td>239 557</td><td>1376 B</td></tr><tr><td></td><td></td><td></td><td>RKeyGen</td><td>239 717</td><td>864 B</td></tr><tr><td>2 × KEM.Encaps</td><td>136 660</td><td>1536 B</td><td>REnc</td><td>658 294</td><td>1088 B</td></tr><tr><td>2 × KEM.Decaps</td><td>175 800</td><td></td><td>RDec</td><td>708 649</td><td></td></tr></tbody></table>

## 8.2. Integration in WireGuard and Experiments

Our implementation of PQ WireGuard is based on the most up-to-date version of the WireGuard kernel module

(Linux 6.14). We modified the protocol messages and cryptographic computations according to our description in Sec. 5.2. We use this implementation for all instantiations (including Classic); the difference in symmetric operations (ChaCha20-Poly1305 for AEAD and Blake2 for hashes) should be negligible compared to asymmetric operations and network overhead. For the KEMs, we use the kernel-ready implementations of Classic McEliece and Dagger from [1] and the implementation of Rebar described above. In the implementation of Rebar we were careful to limit the amount of stack memory used to fit in kernel restrictions.

For benchmarking, we follow the approach from [23], [34], [78], [79]. We create a virtualized network environment based on Linux network namespaces, set the bandwidth to 1000 Mbps and use the netem network emulator to add 30.9 ms of latency as a representation of a reasonably high-quality network link. Measurements are obtained by logging the time it takes to complete the handshake. We changed the rekey interval, so that WireGuard performs a handshake every 5 seconds. We measured 1500 handshakes on an AWS c5d.4xlarge instance with 16 cores and 32 GiB of memory, running Amazon Linux 2023 with kernel 6.12.25-32.101. Tab. 2 shows the message sizes and the initiator's handshake times for different instantiations of WireGuard. The results in the table show that the handshake times for the classically instantiated handshake are slightly faster, but that PQ WireGuard's performance is similar while requiring much less server memory. RKEM performs slightly slower than Dagger, but it should be noted that the implementations of Dagger and Classic McEliece are heavily optimized using AVX2, unlike the reference implementation of Rebar. Further optimizing RKEM remains for future work. Finally, note that using RKEM gives the necessary space to use PQ-X25519 hybrids. This uses an additional 64 B in both messages, bringing them up to 1232 B and 1212 B respectively. The limit for UDP is 1232 B; with McEliece-Dagger, there are less than 64 bytes remaining for hybridization.

## Acknowledgements

We thank the anonymous reviewers and shepherd for their comments. This paper is partially based on results obtained from a project, JPNP24003, commissioned by the New Energy and Industrial Technology Development Organization (NEDO).
## References

[1] A. Hülsing, K.-C. Ning, P. Schwabe, F. J. Weber, and P. R. Zimmermann, "Post-quantum WireGuard," in *2021 IEEE Symposium on Security and Privacy*, IEEE Computer Society Press, May 2021, pp. 304–321. DOI: 10.1109/SP40001.2021.00030.

[2] C. Cremers, A. Dax, and N. Medinger, "Keeping up with the KEMs: Stronger security notions for KEMs and automated analysis of KEM-based protocols," in *ACM CCS 2024*, ACM, Oct. 2024, pp. 1046–1060. DOI: 10.1145/3658644.3670283.

[3] J. A. Donenfeld, "WireGuard: Next generation kernel network tunnel," in *NDSS 2017*, Updated version: https://www.wireguard.com/papers/wireguard.pdf, The Internet Society, 2017. DOI: 10.14722/ndss.2017.23160.

[4] T. Perrin, "Noise protocol framework," Tech. Rep., Jul. 11, 2018. Accessed: Apr. 2, 2025. [Online]. Available: https://noiseprotocol.org/noise.html.

[5] "OpenVPN," Accessed: May 30, 2025. [Online]. Available: https://openvpn.net/.

[6] K. Seo and S. Kent, *Security Architecture for the Internet Protocol*, RFC 4301, Dec. 2005. DOI: 10.17487/RFC4301. [Online]. Available: https://www.rfc-editor.org/info/rfc4301.

[7] B. Dowling and K. G. Paterson, "A cryptographic analysis of the WireGuard protocol," in *ACNS 2018*, ser. LNCS, vol. 10892, Springer, Jul. 2018, pp. 3–21. DOI: 10.1007/978-3-319-93387-0_1.

[8] B. Lipp, B. Blanchet, and K. Bhargavan, "A Mechanised Cryptographic Proof of the WireGuard Virtual Private Network Protocol," Inria Paris, Research Report RR-9269, Apr. 2019, p. 50. [Online]. Available: https://inria.hal.science/hal-02100345.

[9] J. A. Donenfeld and K. Milner, "Formal verification of the wireguard protocol," Jun. 7, 2017. Accessed: Apr. 2, 2025. [Online]. Available: https://www.wireguard.com/papers/wireguard-formal-verification.pdf.

[10] NIST, "Module-lattice-based key-encapsulation mechanism standard," NIST, Tech. Rep., Aug. 13, 2024. DOI: 10.6028/NIST.FIPS.203.

[11] M. R. Albrecht, D. J. Bernstein, T. Chou, C. Cid, J. Gilcher, T. Lange, V. Maram, I. von Maurich, R. Misoczki, R. Niederhagen, K. G. Paterson, E. Persichetti, C. Peters, P. Schwabe, N. Sendrier, J. Szefer, C. J. Tjhai, M. Tomlinson, and W. Wang, "Classic McEliece," National Institute of Standards and Technology, Tech. Rep., 2022, available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions.

[12] J.-P. D'Anvers, A. Karmakar, S. S. Roy, F. Vercauteren, J. M. B. Mera, M. Van Beirendonck, and A. Basso, "SABER," National Institute of Standards and Technology, Tech. Rep., 2020, available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions.

[13] Y. Angel, B. Dowling, A. Hülsing, P. Schwabe, and F. J. Weber, "Post quantum noise," in *ACM CCS 2022*, ACM, Nov. 2022, pp. 97–109. DOI: 10.1145/3548606.3560577.

[14] C. Delpech de Saint Guilhem, M. Fischlin, and B. Warinschi, "Authentication in key-exchange: Definitions, relations and composition," in *CSF 2020 Computer Security Foundations Symposium*, IEEE Computer Society Press, 2020, pp. 288–303. DOI: 10.1109/CSF49147.2020.00028.

[15] K. Gellert, K. Gjøsteen, H. Jacobsen, and T. Jager, "On optimal tightness for key exchange with full forward secrecy via key confirmation," in *CRYPTO 2023*, ser. LNCS, vol. 14084, Springer, Aug. 2023, pp. 297–329. DOI: 10.1007/978-3-031-38551-3_10.

[16] E. Kret and R. Schmidt, "The PQXDH key agreement protocol," Tech. Rep., Oct. 18, 2023. [Online]. Available: https://signal.org/docs/specifications/pqxdh/.

[17] E. Fujisaki and T. Okamoto, "Secure integration of asymmetric and symmetric encryption schemes," in *CRYPTO '99*, ser. LNCS, vol. 1666, Springer, Aug. 1999, pp. 537–554. DOI: 10.1007/3-540-48405-1_34.

[18] S. Katsumata, K. Kwiatkowski, F. Pintore, and T. Prest, "Scalable ciphertext compression techniques for post-quantum KEMs and their applications," in *ASIACRYPT 2020*, ser. LNCS, vol. 12491, Springer, Dec. 2020, pp. 289–320. DOI: 10.1007/978-3-030-64837-4_10.

[19] P. Schwabe, R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, G. Seiler, D. Stehlé, and J. Ding, "CRYSTALS-KYBER," National Institute of Standards and Technology, Tech. Rep., 2022, available at https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022.

[20] A. Fujioka, K. Suzuki, K. Xagawa, and K. Yoneyama, "Practical and post-quantum authenticated key exchange from one-way secure key encapsulation mechanism," in *ASIACCS 13*, ACM Press, May 2013, pp. 83–94. DOI: 10.1145/2484313.2484323.

[21] A. Fujioka, K. Suzuki, K. Xagawa, and K. Yoneyama, "Strongly secure authenticated key exchange from factoring, codes, and lattices," *DCC*, vol. 76, no. 3, pp. 469–504, 2015. DOI: 10.1007/s10623-014-9972-2.

[22] H. Krawczyk, "SKEME: A versatile secure key exchange mechanism for internet," in *NDSS '96*, IEEE Computer Society, Feb. 1996, pp. 114–127. DOI: 10.1109/NDSS.1996.492418.

[23] P. Schwabe, D. Stebila, and T. Wiggers, "More efficient post-quantum KEMTLS with pre-distributed public keys," in *ESORICS 2021*, ser. LNCS, vol. 12972, Springer, Oct. 2021, pp. 3–22. DOI: 10.1007/978-3-030-88418-5_1.

[24] T. Perrin, *KEM-based hybrid forward secrecy for noise*, revision 1, unofficial/unstable, Nov. 17, 2018. [Online]. Available: https://github.com/noiseprotocol/noise_hfs/blob/025f0f60cb3b94ad75b68e3a4158b9aac234f8cb/output/noise_hfs.pdf.
[25] K. Varner, B. Lipp, W. Zaeske, L. Schmidt, and P. Dua, "Rosenpass," 2024-08-28. [Online]. Available: https://rosenpass.eu/whitepaper.pdf.

[26] M. Raynal, PQ-WireGuard: We did it again! Presentation at NIST PQC Standardization Conference, 2021. Accessed: Apr. 2, 2025. [Online]. Available: https://csrc.nist.gov/Presentations/2021/pq-wireguard-we-did-it-again.

[27] J. Ding, M.-S. Chen, A. Petzoldt, D. Schmidt, B.-Y. Yang, M. J. Kannwischer, and J. Patarin, "Rainbow," National Institute of Standards and Technology, Tech. Rep., 2020, available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions.

[28] Mullvad VPN. "Quantum-resistant tunnels with Wire-Guard," Accessed: Apr. 2, 2025. [Online]. Available: https://mullvad.net/en/help/quantum-resistant-tunnels-with-wireguard.

[29] NordVPN. "Post-quantum encryption explained." The NordLynx protocol is based on WireGuard, Accessed: Apr. 2, 2025. [Online]. Available: https://support.nordvpn.com/hc/en-us/articles/30046321712529-NordVPN-Post-quantum-encryption-explained.

[30] D. Stebila and M. Mosca, "Post-quantum key exchange for the internet and the open quantum safe project," in SAC 2016, ser. LNCS, vol. 10532, Springer, Aug. 2016, pp. 14–37. DOI: 10.1007/978-3-319-69453-5_2.

[31] M. van Heesch, N. van Adrichem, T. Attema, and T. Veugen, Towards quantum-safe VPNs and internet, Cryptology ePrint Archive, Report 2019/1277, 2019. [Online]. Available: https://eprint.iacr.org/2019/1277.

[32] K. Eastbrook, K. Kane, B. LaMacchia, D. Shumow, G. Zaverucha, and C. Paquin, "Post-quantum cryptography VPN," Accessed: Jun. 1, 2025. [Online]. Available: https://www.microsoft.com/en-us/research/project/post-quantum-crypto-vpn/.

[33] E. Rescorla, The Transport Layer Security (TLS) Protocol Version 1.3, RFC 8446, Aug. 2018. DOI: 10.17487/RFC8446.

[34] T. Wiggers, "Post-quantum TLS," Ph.D. dissertation, Radboud University, NL, Jan. 9, 2024. DOI: 2066/300702.

[35] C. Kaufman, P. E. Hoffman, Y. Nir, P. Eronen, and T. Kivinen, Internet Key Exchange Protocol Version 2 (IKEv2), RFC 7296, Oct. 2014. DOI: 10.17487/RFC7296. [Online]. Available: https://www.rfc-editor.org/info/rfc7296.

[36] S.-L. Gazdag, S. Grundner-Culemann, T. Guggemos, T. Heider, and D. Loebenberger, "A formal analysis of IKEv2's post-quantum extension," in ACM CSAC, ser. ACSAC '21, Virtual Event, USA: ACM, 2021, pp. 91–105. DOI: 10.1145/3485832.3485885.

[37] D. Herzinger, S.-L. Gazdag, and D. Loebenberger, "Real-world quantum-resistant ipsec," in SIN, vol. 1, 2021, pp. 1–8. DOI: 10.1109/SIN54109.2021.9699255.

[38] P. Kampanakis and G. Ravago, "Post-quantum Hybrid Key Exchange with ML-KEM in the Internet Key Exchange Protocol Version 2 (IKEv2)," IETF, I-D draft-ietf-ipsecme-ikev2-mlkem-00, May 2025. [Online]. Available: https://datatracker.ietf.org/doc/draft-ietf-ipsecme-ikev2-mlkem/00/.

[39] T. Reddy, K. V. Smyslov, and S. Fluhrer, "Signature Authentication in the Internet Key Exchange Version 2 (IKEv2) using PQC," IETF, I-D draft-ietf-ipsecme-ikev2-pqc-auth-02, Apr. 2025. [Online]. Available: https://datatracker.ietf.org/doc/draft-ietf-ipsecme-ikev2-pqc-auth/02/.

[40] S. Fluhrer, P. Kampanakis, D. McGrew, and V. Smyslov, Mixing Preshared Keys in the Internet Key Exchange Protocol Version 2 (IKEv2) for Post-quantum Security, RFC 8784, Jun. 2020. DOI: 10.17487/RFC8784.

[41] H. Xue, X. Lu, B. Li, B. Liang, and J. He, "Understanding and constructing AKE via double-key key encapsulation mechanism," in ASIACRYPT 2018, ser. LNCS, vol. 11273, Springer, Dec. 2018, pp. 158–189. DOI: 10.1007/978-3-030-03329-3_6.

[42] P. Lafourcad, D. Mahmoud, S. Ruhault, and A. Taleb, "A tale of two worlds, a formal story of wireguard hybridization," in USENIX Security 2025, L. Bauer and G. Pellegrino, Eds., 2025. [Online]. Available: https://eprint.iacr.org/2025/1179.

[43] V. Cheval, C. Jacomme, S. Kremer, and R. Kün nemann, "SAPIC+: Protocol verifiers of the world, unite!" In USENIX Security 2022, USENIX Associa- tion, Aug. 2022, pp. 3935–3952. [Online]. Available: https://www.usenix.org/conference/usenixsecurity22/ presentation/cheval.

[44] H. Beguinet, C. Chevalier, G. Lebrun, T. Legavre, T. Ricosset, M. Roméas, and E. Sageloli, "DAKE: Bandwidth-Efficient (U)AKE from Double-KEM," Preprint, 2025.

[45] D. Hofheinz, K. Hövelmanns, and E. Kiltz, "A modu lar analysis of the Fujisaki-Okamoto transformation," in TCC 2017, ser. LNCS, vol. 10677, Springer, Nov. 2017, pp. 341–371. DOI: 10.1007/978-3-319-70500-2_12.

[46] D. Kim, D. Lee, J. Seo, and Y. Song, "Toward practical lattice-based proof of knowledge from hint-MLWE," in CRYPTO 2023, ser. LNCS, vol. 14085, Springer, Aug. 2023, pp. 549–580. DOI: 10.1007/978-3-031-38554-4_18.

[47] T. Espitau, G. Niot, and T. Prest, "Flood and submerse: Distributed key generation and robust threshold sig-nature from lattices," in CRYPTO 2024, ser. LNCS, vol. 14926, Springer, Aug. 2024, pp. 425–458. DOI: 10.1007/978-3-031-68394-7_14.

[48] K. Hövelmanns, E. Kiltz, S. Schäge, and D. Unruh, "Generic authenticated key exchange in the quantum random oracle model," in PKC 2020, ser. LNCS, vol. 12111, Springer, May 2020, pp. 389–422. DOI: 10.1007/978-3-030-45388-6_14.

[49] K. Xagawa, "Anonymity of NIST PQC round 3 KEMs," in EUROCRYPT 2022, ser. LNCS, vol. 13277, Springer, 2022, pp. 551–581. DOI: 10.1007/978-3-031-07082-2_20.
[50] D. Boneh, Ö. Dagdelen, M. Fischlin, A. Lehmann, C. Schaffner, and M. Zhandry, "Random oracles in a quantum world," in *ASIACRYPT 2011*, ser. LNCS, vol. 7073, Springer, Dec. 2011, pp. 41–69. DOI: 10.1007/978-3-642-25385-0_3.

[51] T. Saito, K. Xagawa, and T. Yamakawa, "Tightly-secure key-encapsulation mechanism in the quantum random oracle model," in *EUROCRYPT 2018*, ser. LNCS, vol. 10822, Springer, 2018, pp. 520–551. DOI: 10.1007/978-3-319-78372-7_17.

[52] H. Jiang, Z. Zhang, L. Chen, H. Wang, and Z. Ma, "IND-CCA-secure key encapsulation mechanism in the quantum random oracle model, revisited," in *CRYPTO 2018*, ser. LNCS, vol. 10993, Springer, Aug. 2018, pp. 96–125. DOI: 10.1007/978-3-319-96878-0_4.

[53] A. Ambainis, M. Hamburg, and D. Unruh, "Quantum security proofs using semi-classical oracles," in *CRYPTO 2019*, ser. LNCS, vol. 11693, Springer, Aug. 2019, pp. 269–295. DOI: 10.1007/978-3-030-26951-7_10.

[54] M. Bellare, "New proofs for NMAC and HMAC: Security without collision-resistance," in *CRYPTO 2006*, ser. LNCS, vol. 4117, Springer, Aug. 2006, pp. 602–619. DOI: 10.1007/11818175_36.

[55] M. Bellare and A. Lysyanskaya, "Symmetric and dual PRFs from standard assumptions: A generic validation of a prevailing assumption," *Journal of Cryptology*, vol. 37, no. 4, p. 33, Oct. 2024. DOI: 10.1007/s00145-024-09513-6.

[56] P. Rogaway, "Authenticated-encryption with associated-data," in *ACM CCS 2002*, ACM, Nov. 2002, pp. 98–107. DOI: 10.1145/586110.586125.

[57] A. Fujioka, K. Suzuki, K. Xagawa, and K. Yoneyama, "Strongly secure authenticated key exchange from factoring, codes, and lattices," in *PKC 2012*, ser. LNCS, vol. 7293, Springer, May 2012, pp. 467–484. DOI: 10.1007/978-3-642-30057-8_28.

[58] T. Jager, E. Kiltz, D. Riepel, and S. Schäge, "Tightly-secure authenticated key exchange, revisited," in *EU-ROCRYPT 2021*, ser. LNCS, vol. 12696, Springer, Oct. 2021, pp. 117–146. DOI: 10.1007/978-3-030-77870-5_5.

[59] K. Hashimoto, S. Katsumata, K. Kwiatkowski, and T. Prest, "An efficient and generic construction for Signal's handshake (X3DH): Post-quantum, state leakage secure, and deniable," *Journal of Cryptology*, vol. 35, no. 3, p. 17, Jul. 2022. DOI: 10.1007/s00145-022-09427-1.

[60] J. Brendel, R. Fiedler, F. Günther, C. Janson, and D. Stebila, "Post-quantum asynchronous deniable key exchange and the Signal handshake," in *PKC 2022*, ser. LNCS, vol. 13178, Springer, Mar. 2022, pp. 3–34. DOI: 10.1007/978-3-030-97131-1_1.

[61] C. Brzuska, C. Cremers, H. Jacobsen, D. Stebila, and B. Warinschi, *Falsifiability, composability, and comparability of game-based security models for key exchange protocols*, Cryptology ePrint Archive, Report 2024/1215, 2024. [Online]. Available: https://eprint.iacr.org/2024/1215.

[62] B. A. LaMacchia, K. Lauter, and A. Mityagin, "Stronger security of authenticated key exchange," in *ProvSec 2007*, ser. LNCS, vol. 4784, Springer, Nov. 2007, pp. 1–16. DOI: 10.1007/978-3-540-75670-5_1.

[63] M. Bellare, D. Pointcheval, and P. Rogaway, "Authenticated key exchange secure against dictionary attacks," in *EUROCRYPT 2000*, ser. LNCS, vol. 1807, Springer, May 2000, pp. 139–155. DOI: 10.1007/3-540-45539-6_11.

[64] H. Krawczyk, "HMQV: A high-performance secure Diffie-Hellman protocol," in *CRYPTO 2005*, ser. LNCS, vol. 3621, Springer, Aug. 2005, pp. 546–566. DOI: 10.1007/11535218_33.

[65] J.-P. Aumasson, S. Neves, Z. Wilcox-O'Hearn, and C. Winnerlein, "BLAKE2: Simpler, smaller, fast as MD5," in *ACNS 2013*, ser. LNCS, vol. 7954, Springer, Jun. 2013, pp. 119–135. DOI: 10.1007/978-3-642-38980-1_8.

[66] K. Xagawa and T. Yamakawa, "(Tightly) QCCA-secure key-encapsulation mechanism in the quantum random oracle model," in *PQCrypto 2019*, Springer, 2019, pp. 249–268. DOI: 10.1007/978-3-030-25510-7_14.

[67] X. Liu and M. Wang, "QCCA-secure generic key encapsulation mechanism with tighter security in the quantum random oracle model," in *PKC 2021*, ser. LNCS, vol. 12710, Springer, May 2021, pp. 3–26. DOI: 10.1007/978-3-030-75245-3_1.

[68] M. R. Albrecht, R. Player, and S. Scott, *On the concrete hardness of learning with errors*, Cryptology ePrint Archive, Report 2015/046, 2015. [Online]. Available: https://eprint.iacr.org/2015/046.

[69] M. F. Esgin, T. Espitau, G. Niot, T. Prest, A. Sakzad, and R. Steinfeld, "Plover: Masking-friendly hash-and-sign lattice signatures," in *EUROCRYPT 2024*, ser. LNCS, vol. 14657, Springer, May 2024, pp. 316–345. DOI: 10.1007/978-3-031-58754-2_12.

[70] R. Del Pino, S. Katsumata, M. Maller, F. Mouhartem, T. Prest, and M.-J. O. Saarinen, "Threshold raccoon: Practical threshold signatures from standard lattice assumptions," in *EUROCRYPT 2024*, ser. LNCS, vol. 14652, Springer, May 2024, pp. 219–248. DOI: 10.1007/978-3-031-58723-8_8.

[71] Y. Dodis, D. Jost, S. Katsumata, T. Prest, and R. Schmidt, *Triple ratchet: A bandwidth efficient hybrid-secure signal protocol*, Cryptology ePrint Archive, Paper 2025/078, 2025. [Online]. Available: https://eprint.iacr.org/2025/078.

[72] G. Niot, *Practical deniable post-quantum X3DH: A lightweight split-KEM for K-Waay*, Cryptology ePrint Archive, Paper 2025/853, 2025. [Online]. Available: https://eprint.iacr.org/2025/853.

[73] M. J. Kannwischer, P. Schwabe, D. Stebila, and T. Wiggers, "Improving software quality in cryptography standardization projects," in *IEEE EuroS&P 2022 Workshops*, USA: IEEE, 2022, pp. 19–30. DOI: 10.
1109/EuroSPW55150.2022.00010. [Online]. Available: https://eprint.iacr.org/2022/337.

[74] T. Prest, P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Ricosset, G. Seiler, W. Whyte, and Z. Zhang, “FALCON,” National Institute of Standards and Technology, Tech. Rep., 2022, available at https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022.

[75] P.-A. Fouque, P. Kirchner, T. Pornin, and Y. Yu, “BAT: Small and fast KEM over NTRU lattices,” IACR TCHES, vol. 2022, no. 2, pp. 240–265, 2022. DOI: 10.46586/tches.v2022.i2.240-265.

[76] J. Zhang, D. Feng, and D. Yan, “NEV: Faster and smaller NTRU encryption using vector decoding,” in ASIACRYPT 2023, ser. LNCS, vol. 14444, Springer, Dec. 2023, pp. 157–189. DOI: 10.1007/978-981-99-8739-9_6.

[77] T. Prest, “Sharper bounds in lattice-based cryptography using the Rényi divergence,” in ASIACRYPT 2017, ser. LNCS, vol. 10624, Springer, Dec. 2017, pp. 347–374. DOI: 10.1007/978-3-319-70694-8_13.

[78] C. Paquin, D. Stebila, and G. Tamvada, “Benchmarking post-quantum cryptography in TLS,” in PQCrypto 2020, Springer, 2020, pp. 72–91. DOI: 10.1007/978-3-030-44223-1_5.

[79] P. Schwabe, D. Stebila, and T. Wiggers, “Post-quantum TLS without handshake signatures,” in ACM CCS 2020, ACM, Nov. 2020, pp. 1461–1480. DOI: 10.1145/3372297.3423350.

[80] C. J. F. Cremers and M. Feltz, “Beyond eCK: Perfect forward secrecy under actor compromise and ephemeral-key reveal,” in ESORICS 2012, ser. LNCS, vol. 7459, Springer, Sep. 2012, pp. 734–751. DOI: 10.1007/978-3-642-33167-1_42.

[81] M. Zhandry, “Secure identity-based encryption in the quantum random oracle model,” in CRYPTO 2012, ser. LNCS, vol. 7417, Springer, Aug. 2012, pp. 758–775. DOI: 10.1007/978-3-642-32009-5_44.

# Appendix A. Omitted Details of Security Model

## A.1. Subtle Issue in Prior Computational Model

We provide a self-contained explanation on the subtle issue in how Dowling and Paterson [7] and Hülsing et al. [1] handle the pre-shared keys (PSKs) in the post-specified peer model. This renders their computational model ill-defined, and consequently, making their proofs incomplete.

They base their computational model on Cremers and Feltz [80], allowing to capture post-specified peers, and extends it to handle pre-shared keys. Using their notations, an adversary can query the oracle Create$(i, j, role)$ on input role = resp to set up responder $i$'s $s$-th session $\pi_i^s$, where $i$'s intended communication partner $\pi_i^s$.pid is set to $j$. To

model post-specified peer, $j = \perp$ is allowed. Moreover, the PSK used by the session $\pi_i^s$ is set as $\pi_i^s.psk \leftarrow \overline{\text{PSK}}_i[j]$, where the content of $\overline{\text{PSK}}_i[j]$ is set when the adversary queries the oracle CreatePSK($i, j$).

The issue with this is that the oracle CreatePSK($i, j$) implicitly assumes an input $i, j \neq \perp$ since it is supposed to generate a PSK between parties $i$ and $j$. However, this means that $\overline{\text{PSK}}_i[j]$ with $j = \perp$ is undefined. As a result, Create($i, j, role$) cannot define $\pi_i^s.psk$ when $j = \perp$. In words, the responder's PSK cannot be set when the initiator is unknown, and there is no simple mechanism for the game to update it when the initiator becomes known.

In our work, we fix this subtle issue by the ResIdentify algorithm. The game explicitly runs ResIdentify to identify the initiator, and only then defines the PSK of the session (cf. Fig. 4, Ln. 34). Importantly, the responder's PSK remains undefined either before executing ResIdentify or ResIdentify fails to identify the initiator.

## A.2. Key Indistinguishability

To formalize key indistinguishability, the security game needs to know what secret information are revealed. To do this, the game keeps track of the adversary's knowledge by managing the following lists. Note that every list except for RevPSK is initialized with false, and set to true when the associated secret information is revealed. This is because pre-shared secrets are optional; RevPSK is initialized with true and only set to false once $O_{CreatePSK}$ is queried.

RevSessKey[iID] is true if the session key of instance iID is revealed.

RevIK[$u$] is true if the long-term secret key of $u$ is revealed.

RevState[iID] is true if the session state of iID is revealed.

RevPSK[{ $u, v$ }] becomes false if the pre-shared key for $u$ and $v$ is generated, and is set to true when revealed.

*Security covered by our definition.* We define key indistinguishability similarly to [1], [7] that uses eCK [62]-style modeling with ephemeral key reveals. The following set of common security guarantees are covered:

**Security against Maximal exposure attack:** Session keys remains secure against an adversary compromising any non-trivial combinations of the long-term secret key, session state, and pre-shared key. As the responder has no session state, we assume the adversary always compromises the responder's long-term secret key as long as it does not trivialize the game. Note that this implicitly captures security against key-compromise impersonation (KCI) attacks, where an adversary compromising a party's long-term key and tries to impersonate another party against him.

**(Weak) forward security:** The session key of a party remains secure against an adversary that does not compromise the long-term secret key of the peer (and the session state when the role of the tested instance is initiator). Note that full forward security (fFS) considers the scenario where the secret information of the peer can be compromised after the session key has been computed. As explained in Sec. 4.2, we can achieve fFS by adding explicit key-confirmation.

<footnote n="5">5. In our work, we refer to a session as an *instance*.</footnote>
**Formal definition.** Key indistinguishability is defined with respect to a predicate safe<sub>WGKE</sub> that checks whether an adversary performed an attack that trivializes the game, where note that the aforementioned attacks are allowed. We require that the session key of the tested instance ilD<sup>*</sup> is indistinguishable from random if safe<sub>WGKE</sub>(ilD<sup>*</sup>) = true.

**Definition 26.** Let $i^* := \text{Init}[\text{ilD}^*]$ and $r^* := \text{Resp}[\text{ilD}^*]$ and let $\mathfrak{P}(\text{ilD}^*) := \{i \in S_{\text{ilD}} | \text{Partner}(\text{ilD}^*, i\text{D}) = \text{true}\}$ be the partner instances of the tested instance ilD<sup>*</sup>.

We define the predicate safe<sub>WGKE</sub> such that safe<sub>WGKE</sub>(ilD<sup>*</sup>) holds true if and only if RevSessKey[ilD<sup>*</sup>] = false, $\forall i\text{D} \in \mathfrak{P}(ilD^*)$: RevSessKey[ilD] = false, and one of the following conditions is satisfied:

**Case (1-1):** $|\mathfrak{P}(ilD^*)| = 1$ and RevPSK[{$i^*, r^*$}] = false (i.e., ilD<sup>*</sup> has a partner and the used pre-shared key is not compromised);

**Case (1-2):** $|\mathfrak{P}(ilD^*)| = 1$ and RevLSK[$i^*$] = false (i.e., ilD<sup>*</sup> has a partner and the initiator's long-term secret key is not compromised);

**Case (1-3):** $|\mathfrak{P}(ilD^*)| = 1$ and RevState[ilD<sup>*</sup>] = false (i.e., ilD<sup>*</sup> has a partner and the initiator's session state is not compromised);

**Case (2-1):** role[ilD<sup>*</sup>] = init, $|\mathfrak{P}(ilD^*)| = 0$, RevLSK[$r^*$] = false and RevState[ilD<sup>*</sup>] = false (i.e., ilD<sup>*</sup> has no partner and the responder's long-term secret key and the initiator's session state are not compromised)<sup>6</sup>;

**Case (2-2):** role[ilD<sup>*</sup>] = resp, $|\mathfrak{P}(ilD^*)| = 0$, RevLSK[$i^*$] = false (i.e., ilD<sup>*</sup> has no partner and the initiator's long-term secret key is not compromised).

Then, WGKE is key indistinguishable for the predicate safe<sub>WGKE</sub> if Adv<sub>WGKE,A</sub><sup>KIND</sup> := $|2 \cdot \text{Pr}[\text{Game}_{\text{WGKE},A}^{\text{KIND}}(1^\lambda) = 1] - 1|$ (cf. Fig. 3) is negligible for all efficient A.

## Appendix B.

### UKS Attack Without Proper Key Schedule

We provide a simple UKS attack on the PQ WireGuard by Hülsing et al. [1], as depicted in Fig. 1. More formally, we explain an attack that breaks match soundness (cf. Def. 15). The attack relies on a KEM such that for a (possibly malicious) ($pk^*, sk^*$) and ct generated as (ct, ss) $\stackrel{\$}{\leftrightarrow}$ KEM. Enc($pk^*$), it is easy to construct ct' such that ss = KEM. Dec(sk', ct') for an honestly generated ($pk^*, sk^*$). That is, a KEM that is not LEAK/MAL-BIND-K-PK [2].

The adversary invokes the initiator and compromises its long-term and ephemeral public keys $pk_C$ and $pk_e$. It also compromises the long-term public key of the responder $pk_S$, and PSK if it is used. It then decrypts $ct_S$, derives the key $K_{1tk}$, and generates a modified $1tk'$ injecting another long-term public key $pk_A$, and computes the associated $time'$. When the server replies, it decrypts $ct_A$ and $ct_e$, and performs the above “re-encapsulation” attack on KEM to prepare $ct_C$, encapsulating the same secret as $ct_A$. It then replaces the server message with $ct_C$ and prepares $skem'$ and empty'.

As the key chain ($C_i$) does not take as input $pk_C$ nor $ct_C$, the client and server derive the same session key $K_{out}$. However, since the server believes it's talking to A, this breaks the first requirement of match soundness.

We note that in their symbolic model [1], the key chain value $C_5$ is computed from $ct_C$ instead of $ct_e$. As the session key is now tied to $ct_C$, the above attack, injecting $ct_A$ no longer works. Nevertheless, the KEM is still required to be LEAK/MAL-BIND-K,CT-PK [2] secure (which is satisfied by how they model KEMs). In our work, we simply include $pk_C$ in the key chain to rely on no extra assumption.

## Appendix C.

### Key-Indistinguishability of Our PQ WireGuard

In this section, we provide the formal proof of key indistinguishability of our PQ WireGuard based on RKEM.

**Theorem 11.** Our PQ WireGuard is key indistinguishable if it is match-sound (cf. Thm. 2), KEM is SPR-CCA secure, RKEM is SPR-CCA and IND-RCCA secure, and KDF is dual-PRF secure.

*Proof.* Let A be an adversary that plays the security game Game<sub>A</sub><sup>KIND</sup> (1<sup>λ</sup>) and let $\epsilon$ be its advantage. In order to prove the theorem, we show that our PQ WireGuard is secure against all cases listed in Def. 26. For each case, we construct an algorithm that breaks one of the underlying assumptions by using A as a subroutine. Let $N = |U|$ be the number of honest users in the system and M be the upper bound of NumiD (i.e., the maximum number of ilD generated by A).

We present a security proof structured as a sequence of games. Without loss of generality, we assume that A always issues $O_{\text{Test}}$-query. Regardless of the cases caused by A, all proofs share a common game sequence Game<sub>0</sub> and Game<sub>1</sub> as described below.

**Game<sub>0</sub>:** This game is identical to the original KIND security game. We thus have

$$ \Pr[\text{Game}_0 = 1] = \Pr[\text{Game}_{\text{WGKE},A}^{\text{KIND}} = 1]. $$

**Game<sub>1</sub>:** This game is identical to Game<sub>0</sub>, except that it aborts if the predicate Match returns false. Since we proved that WGKE is match-sound, we have

$$ |\Pr[\text{Game}_0 = 1] - \Pr[\text{Game}_1 = 1]| \le \text{Adv}_{\text{WGKE},A}^{\text{MATCH}}(\lambda). $$

In the following, we can assume that the tested instance ilD<sup>*</sup> has a unique partner if it exists.

We now divide the game sequence depending on the case made by the adversary A. Regardless of the cases, we prove that $\epsilon_1$ is negligible, which in particular implies that $\epsilon_0$ is also negligible. Formally, this is shown in Lemmas 5 to 9 provided below. We first complete the proof of the theorem. Specifically, by combining all the lemmas together,

<footnote n="6">6. This is the only case where we consider the responder's long-term secret key to be uncompromised.</footnote>
we obtain the following bound, where we take the maximum value inside $\{\dots\}$:

$$ \mathrm{Adv}_{\mathrm{WGKE},A}^{\mathrm{KIND}}(\lambda) \le \mathrm{negl}(\lambda) + \mathrm{Adv}_{\mathrm{WGKE},A}^{\mathrm{MATCH}}(\lambda) + \left\{ \begin{array}{l} 3N^2 \cdot \mathrm{Adv}_{B_1}^{\mathrm{PRF}}(\lambda) \\ NM \cdot (\mathrm{Adv}_{\mathrm{RKEM},B_2}^{\mathrm{SPR-CCA}}(\lambda) + 2\mathrm{Adv}_{\mathrm{KDF},B_2'}^{\mathrm{PRF}}(\lambda)) \\ NM^2 \cdot (\mathrm{Adv}_{\mathrm{RKEM},B_3}^{\mathrm{IND-RCCA}}(\lambda) + 2\mathrm{Adv}_{\mathrm{KDF},B_3'}^{\mathrm{PRF}}(\lambda)) \\ NM \cdot (\mathrm{Adv}_{\mathrm{RKEM},B_4}^{\mathrm{SPR-CCA}}(\lambda) + 4\mathrm{Adv}_{\mathrm{KDF},B_4'}^{\mathrm{PRF}}(\lambda)) \\ NM \cdot (\mathrm{Adv}_{\mathrm{RKEM},B_5}^{\mathrm{SPR-CCA}}(\lambda) + 2\mathrm{Adv}_{\mathrm{KDF},B_5'}^{\mathrm{PRF}}(\lambda)) \end{array} \right\} \quad \square $$

It remains to prove Lemmas 5 to 8.

*Proof of Case (1-1): PSK is not leaked.*

**Lemma 5.** For any efficient adversary $\mathcal{A}$, there exists a reduction $B_1$ that breaks the PRF security of KDF such that

$$ \left| \mathrm{Pr}[\mathrm{Game}_1 = 1] - \frac{1}{2} \right| \le 3M^2 \cdot \mathrm{Adv}_{\mathrm{KDF},B_1}^{\mathrm{PRF}}(\lambda). $$

*Proof.* We present the rest of the sequence of games from game Game$_2$.

**Game$_2$:** This game guesses two instances that will be tested and be partnered to the tested instance. At the beginning of the game, it chose $iD_i$ and $iD_r$ at random from $[M]$. Let $E_{\text{Tested}}$ be the event that the tested instance $iD^*$ satisfies either $iD^* = iD_i$ or $iD^* = iD_r$ and $iD_i$ and $iD_r$ are partner (W.l.o.g, we can assume $iD_i$ is an initiator and $iD_r$ is a responder). Since the $E_{\text{Tested}}$ event can be efficiently checked, the game outputs a random bit as soon as it detects that $E_{\text{Tested}}$ does not occur. The probability is $\mathrm{Pr}[E_{\text{Tested}}] = 1/M^2$, so we have

$$ \left| \mathrm{Pr}[\mathrm{Game}_2 = 1] - \frac{1}{2} \right| = \frac{1}{M^2} \left| \mathrm{Pr}[\mathrm{Game}_1 = 1] - \frac{1}{2} \right|. $$

**Game$_3$:** In this game, when the users $i^* = \mathrm{Init}[iD^*]$ and $r^* = \mathrm{Resp}[iD^*]$ compute their session keys, $C_6$ is replaced with a uniformly random value. If $E_{\text{Tested}}$ occurs, since we consider case (1-1), the PSK $\mathrm{psk}_{i^*,j^*}$ is not leaked. Further, PSK is chosen uniformly at random by definition. Therefore, due to the PRF security of KDF, there exists a reduction $B_1$ such that

$$ \left| \mathrm{Pr}[\mathrm{Game}_2 = 1] - \mathrm{Pr}[\mathrm{Game}_3 = 1] \right| \le \mathrm{Adv}_{\mathrm{KDF},B_1}^{\mathrm{PRF}}(\lambda). $$

**Game$_4$:** In this game, when $iD_i$ and $iD_r$ compute their session keys, $C_7$ is replaced with a uniformly random value. Since $C_6$ is chosen uniformly at random now, due to the dual-PRF security of KDF, there exists a reduction $B'_1$ such that

$$ \left| \mathrm{Pr}[\mathrm{Game}_3 = 1] - \mathrm{Pr}[\mathrm{Game}_4 = 1] \right| \le \mathrm{Adv}_{\mathrm{KDF},B'_1}^{\mathrm{PRF}}(\lambda). $$

**Game$_5$:** In this game, $iD_i$ and $iD_r$ replace $K_{\text{out}}$ with a uniformly random value. Since $C_7$ is chosen uniformly at random, due to the dual-PRF security of KDF, there exists a reduction $B'_2$ such that

$$ \left| \mathrm{Pr}[\mathrm{Game}_4 = 1] - \mathrm{Pr}[\mathrm{Game}_5 = 1] \right| \le \mathrm{Adv}_{\mathrm{KDF},B'_2}^{\mathrm{PRF}}(\lambda). $$

In game Game$_5$, the session key $K_{\text{out}}$ is an independent and uniformly random value. Since our PQ WireGuard satisfies match soundness (cf. Thm. 2), the only instance that share the same $K_{\text{out}}$ must be the tested instance and its partner (i.e., $iD_i$ and $iD_r$ conditioning on $E_{\text{Tested}}$). Since the adversary cannot reveal the tested session key and its partner by definition, the tested session key looks random to the adversary regardless of the challenge bit $b$. Therefore, we conclude that $\mathrm{Pr}[\mathrm{Game}_5 = 1] = 1/2$. Combining all arguments together, we obtain

$$ \left| \mathrm{Pr}[\mathrm{Game}_1 = 1] - \frac{1}{2} \right| \le 3M^2 \cdot 3\mathrm{Adv}_{\mathrm{KDF},B_1}^{\mathrm{PRF}}(\lambda). $$

*Proof of Cases (1-2): initiator's long-term key is not leaked.*

**Lemma 6.** For any efficient adversary $\mathcal{A}$, there exists a reduction $B_2$ that breaks the SPR-CCA security of RKEM and $B'_2$ that breaks the PRF security of KDF such that

$$ \left| \mathrm{Pr}[\mathrm{Game}_1 = 1] - \frac{1}{2} \right| \le NM \cdot (\mathrm{Adv}_{\mathrm{RKEM},B_2}^{\mathrm{SPR-CCA}}(\lambda) + 2\mathrm{Adv}_{\mathrm{KDF},B_2'}^{\mathrm{PRF}}(\lambda)). $$

*Proof.* We present the rest of the sequence of games from game Game$_2$.

**Game$_2$:** This game guesses a responder instance and its initiator, which will be the tested instance and its partner. At the beginning of the game, it chose $iD_r$ at random from $[M]$ and $i$ at random from $\mathcal{U}$. Let $E_{\text{Tested}}$ be the event that $\mathrm{Init}[iD^*] = \hat{i}$ and either $iD_r = iD^*$ (when role $[iD^*] = \mathrm{resp}$) or $iD_r$ is a partner of $iD^*$ (when role $[iD^*] = \mathrm{init}$). Since $E_{\text{Tested}}$ is an efficiently checkable event, the game outputs a random bit as soon as it detects that event $E_{\text{Tested}}$ does not occur. The probability the choice made by $\mathcal{A}$ is correctly guessed with probability $1/NM$, so we have

$$ \left| \mathrm{Pr}[\mathrm{Game}_2 = 1] - \frac{1}{2} \right| = \frac{1}{NM} \left| \mathrm{Pr}[\mathrm{Game}_1 = 1] - \frac{1}{2} \right|. $$

**Game$_3$:** In this game, we modify how the user $\hat{i}$ computes the session key. Let $(ct_C, ss_C) \stackrel{\$}{\leftarrow} \mathrm{REnc}(pk_{\hat{i}}, rpk_{\hat{i}})$ be the RKEM key-ciphertext pair generated by the instance $iD_r$ with the user $\hat{i}$'s long-term key $pk_{\hat{i}}$ and some $rpk_{\hat{i}}$ generate by the $\hat{i}$'s initiator instance. Then, when $iD'$ such that $\mathrm{Init}[iD'] = \hat{i}$ and its session state has a secret key of $rpk_{\hat{i}}$ is invoked with $ct_C$, it uses the key $ss_C$ that was generated by $iD_r$ instead of decrypting $ct_C$. If decryption errors do not occur in RKEM, the two games are identical. Hence,

$$ \left| \mathrm{Pr}[\mathrm{Game}_2 = 1] - \mathrm{Pr}[\mathrm{Game}_3 = 1] \right| = \mathrm{negl}(\lambda). $$

**Game$_4$:** In this game, we modify the way the responder instance $iD_r$ computes the RKEM session key and ciphertext. Let rpk be the RKEM reinforcing public key received by $iD_r$. $iD_r$ samples a random RKEM secret $ss_C$ and simulates $ct_C$ with the simulator $S(1^{\lambda}, rpk)$ instead of computing $(ct_C, ss_C) \stackrel{\$}{\leftarrow} \mathrm{REnc}(pk_{\hat{i}}, rpk)$. Note that due to the modification we made in the previous game, when $\hat{i}$ receives $ct_C$
and decrypts it with rpk's secret key, it also uses the random key $ss_C$ generated by $ilD_r$. Since we consider the case (1-2), the long-term secret key of the user $\hat{i}$, who is the initiator of the tested instance, is never leaked if $E_{\text{Tested}}$ occurs. Thus, due to the SPR-CCA security of RKEM, $Game_3$ and $Game_4$ are indistinguishable. More precisely, we can construct an algorithm $B_2$ breaking the SPR-CCA security of RKEM as follows.

$B_2$ receives a challenge public key $pk^*$ from its challenger. $B_2$ then samples a random $(\hat{i}, ilD_r) \stackrel{\$}{\leftarrow} [N] \times [M]$ and generates the long-term key pairs as follows. For the user $\hat{i}$, $B_2$ uses $pk^*$ as its long-term public key, and for all the other parties, $B_2$ computes the long-term key pairs correctly. Finally, $B_2$ invokes $\mathcal{A}$ and answers the queries made by $\mathcal{A}$ as follows:

* $O_{\text{Init}}(i, r):$ $B_2$ responds as in the previous game except that it generates a reinforcing public key rpk through $O_{\text{RKeyGen}}$ oracle.

* $O_{\text{Res}}(r, m_1)$: Let ilD be the assigned ilD and rpk be the received reinforcing public key in $m_1$.

- If $\text{Init}[ilD] = \hat{i}$ and $ilD = ilD_r$, then $B_2$ responds as in the previous game except that it outputs rpk to its challenger, receives $(ct^*, ss^*)$, and sets $(ct_C, ss_C) := (ct^*, ss^*)$ instead of generating them on its own.

- Otherwise, $B_2$ responds as in the previous game.

* $O_{\text{InitDer}}(ilD, m_2)$: Depending on the value of $i = \text{Init}[ilD]$, it performs the following:

- If $i = \hat{i}$, then $B_2$ checks if $ct = ct^*$. If so, it responds as in the previous game (i.e., it uses $ss := ss^*$). Otherwise, if $ct \neq ct^*$, then it sends $ct$ and its reinforcing public key rpk to $O_{\text{MalDec}}$ oracle and receives back $ss'$. $B_2$ then responds with $ss'$.

- If $i \neq \hat{i}$, then $B_2$ responds as in the previous game since it knows both the long-term secret key and reinforcing public secret key.

* $O_{\text{CreatePSK}}(u)$, $O_{\text{RevLSK}}(u)$, $O_{\text{RevPSK}}(u)$, $O_{\text{RegisterPK}}(u)$, $\text{RevState}(ilD)$, $\text{RevSessKey}(ilD)$, $\text{Test}(ilD)$: $B_2$ responds as in the previous game. Here, note that since we consider case (1-2), $B_2$ can answer all the $O_{\text{RevLSK}}$-query since $\mathcal{A}$ never queries $\text{RevLSK}(\hat{i})$ conditioning on $E_{\text{Tested}}$ not occurring, which is the only query that $B_2$ cannot answer.

If $\mathcal{A}$ outputs a guess $b'$, $B_2$ outputs 1 if $b = b'$ and 0 otherwise as its guess. It can be checked that $B_2$ perfectly simulates game $Game_3$ (resp. $Game_4$) to $\mathcal{A}$ when the answer in the challenge phase is the real key and ciphertext (resp. a random key and a simulated ciphertext). Thus, we have

$$|\Pr[Game_3 = 1] - \Pr[Game_4 = 1]| \le \text{Adv}_{\text{RKEM}, B_2}^{\text{SPR-CCA}}(\lambda).$$

**Game 5:** We change how $ilD_r$ (and its partner instance) computes $C_7$. In this game, a uniformly random value is used as $C_7$ instead of computing it as KDF($ss_C$, $C_6$). Due to the modification we made in the previous game, $ss_C$ is chosen uniformly at random. Therefore, by the PRF security of KDF, the two games are indistinguishable. Thus, we have

$$|\Pr[Game_4 = 1] - \Pr[Game_5 = 1]| \le \text{Adv}_{\text{KDF}, B_2}^{\text{PRF}}(\lambda).$$

**Game 6:** In this game, a uniformly random value is used as $K_{\text{out}}$. Due to the modification we made in the previous game, $C_7$ is chosen uniformly at random. Also, since our PQ WireGuard satisfies Match soundness, only $ilD_i$ and $ilD_r$ have the same $C_7$. Therefore, by the dual-PRF security of KDF, the two games are indistinguishable. Thus, we have

$$|\Pr[Game_5 = 1] - \Pr[Game_6 = 1]| \le \text{Adv}_{\text{KDF}, B_2}^{\text{PRF}}(\lambda).$$

In game $Game_6$, the tested session key $K_{\text{out}}$ is an independent and uniformly random value. Following a similar argument for the case (1-1), $K_{\text{out}}$ looks random to the adversary regardless of the challenge bit $b$. Therefore, we conclude that $\Pr[Game_6 = 1] = 1/2$. Combining all arguments together, we obtain

$$\left| \Pr[Game_1 = 1] - \frac{1}{2} \right| \le NM \cdot (\text{Adv}_{\text{RKEM}, B_2}^{\text{SPR-CCA}}(\lambda) + 2\text{Adv}_{\text{KDF}, B_2'}^{\text{PRF}}(\lambda)). \quad \square$$

**Proof of Cases (1-3): initiator's session state is not leaked.**

**Lemma 7.** For any efficient adversary $\mathcal{A}$, there exists a reduction $B_3$ that breaks the IND-RCCA security of RKEM and $B_3'$ that breaks the PRF security of KDF such that

$$\left| \Pr[Game_1 = 1] - \frac{1}{2} \right| \le NM^2 \cdot (\text{Adv}_{\text{RKEM}, B_3}^{\text{IND-RCCA}}(\lambda) + 2\text{Adv}_{\text{KDF}, B_3'}^{\text{PRF}}(\lambda)).$$

*Proof.* We present the rest of the sequence of games from game $Game_2$.

**Game 2:** This game guesses the tested instance and its partner instance. At the beginning of the game, it chooses $\hat{i}$ at random from $[N]$ and $ilD_i$ and $ilD_r$ at random from $[M]$. Let $E_{\text{Tested}}$ be the event that $ilD_i$ and $ilD_r$ are partner, $\text{Init}[ilD^*] = \hat{i}$ and either $ilD_i = ilD^*$ or $ilD_r = ilD^*$. (W.l.o.g., we assume $ilD_i$ is initiator and $ilD_r$ is a responder) Since $E_{\text{Tested}}$ is an efficiently checkable event, the game outputs a random bit as soon as it detects that event $E_{\text{Tested}}$ does not occur. The probability the choice made by $\mathcal{A}$ is correctly guessed with probability $1/NM^2$, so we have

$$\left| \Pr[Game_2 = 1] - \frac{1}{2} \right| = \frac{1}{NM^2} \left| \Pr[Game_1 = 1] - \frac{1}{2} \right|.$$

**Game 3:** In this game, we modify how $ilD_i$ and $ilD_r$ computes the session key. Let $(ct_C, ss_C) \stackrel{\$}{\leftarrow} \text{REnc}(pk_i, rpk_i)$ be the RKEM key-ciphertext pair generated by the instance $ilD_r$ with the user $\hat{i}$'s long-term key $pk_i$ and the reinforcing public key rpk_i generated by $ilD_i$. Then, when $ilD_i$ is invoked with $ct_C$, it uses the key $ss_C$ that was generated by $ilD_r$ instead of decrypting $ct_C$. If decryption errors do not occur in RKEM, the two games are identical. Hence,

$$|\Pr[Game_2 = 1] - \Pr[Game_3 = 1]| = \text{negl}(\lambda).$$

**Game 4:** In this game, we modify the way the responder instance $ilD_r$ computes the RKEM session key and ciphertext.
ilD<sub>r</sub> samples a random RKEM secret ss<sub>C</sub> instead of ss<sub>C</sub> computed as (ct<sub>C</sub>, ss<sub>C</sub>) $\stackrel{\$}{\leftarrow}$ REnc(pk<sub>i</sub>, rpk<sub>i</sub>), where rpk<sub>i</sub> is the reinforcing public key generated by ilD<sub>i</sub>. Note that due to the modification we made in the previous game, when ilD<sub>i</sub> receives ct<sub>C</sub>, it also uses the random key ss<sub>C</sub> generated by ilD<sub>r</sub>. Since we consider the case (1-3), the reinforced secret key of rpk<sub>i</sub>, which is stored on the session state of ilD<sub>i</sub> is not leaked if E<sub>Tested</sub> occurs. Thus, due to the IND-RCCA security of RKEM, Game<sub>3</sub> and Game<sub>4</sub> are indistinguishable. More precisely, we can construct an algorithm B<sub>3</sub> breaking the IND-RCCA security of RKEM as follows.

B<sub>3</sub> receives (pk<sup>*</sup>, sk<sup>*</sup>, rpk<sup>*</sup>, ct<sup>*</sup>, ss<sup>*</sup>) from its challenger. B<sub>3</sub> then samples a random (î, ilD<sub>i</sub>, ilD<sub>r</sub>) $\stackrel{\$}{\leftarrow}$ [N] × [M]<sup>2</sup> and generates the long-term key pairs as follows. For the user î, B<sub>3</sub> uses (pk<sup>*</sup>, sk<sup>*</sup>) as its long-term public key, and for all the other parties, B<sub>3</sub> computes the long-term key pairs correctly. Finally, B<sub>3</sub> invokes A and answers the queries made by A as follows:

* O<sub>Init</sub>(i, r): Let ilD be the assigned ilD. B<sub>3</sub> responds as in the previous game except that, if ilD = ilD<sub>i</sub>, it uses rpk<sup>*</sup> as the reinforcing public key.

* O<sub>Res</sub>(r, m<sub>1</sub>): Let ilD be the assigned ilD and rpk be the received reinforcing public key in m<sub>1</sub>.

- If Init[ilD] = î and ilD = ilD<sub>r</sub>, then B<sub>3</sub> responds as in the previous game except that it sets (ct<sub>C</sub>, ss<sub>C</sub>) := (ct<sup>*</sup>, ss<sup>*</sup>) instead of generating them on its own.

- Otherwise, B<sub>3</sub> responds as in the previous game.

* O<sub>InitDer</sub>(ilD, m<sub>2</sub>): Depending on the value of i = Init[ilD], it performs the following:

- If ilD = ilD<sub>i</sub>, then B<sub>3</sub> checks if ct = ct<sup>*</sup>. If so, it responds as in the previous game (i.e., it uses ss := ss<sup>*</sup>). Otherwise, if ct ≠ ct<sup>*</sup>, then it sends ct to O<sub>HonDec</sub> oracle and receives back ss'. B<sub>3</sub> then responds with ss'.

- Otherwise, then B<sub>3</sub> responds as in the previous game since it knows both long-term and reinforcing public secret key.

* O<sub>CreatePSK</sub>(u), O<sub>RevLSK</sub>(u), O<sub>RevPSK</sub>(u), O<sub>RegisterPK</sub>(u), RevState-ilD), RevSessKey-ilD), Test-ilD): B<sub>3</sub> responds as in the previous game. Here, note that since we consider case (1-3), B<sub>3</sub> can answer all the O<sub>RevState</sub>-query since A never queries RevState-ilD<sub>i</sub> conditioning on E<sub>Tested</sub> not occurring, which is the only query that B<sub>3</sub> cannot answer.

If A outputs a guess b', B<sub>3</sub> outputs 1 if b = b' and 0 otherwise as its guess. It can be checked that B<sub>3</sub> perfectly simulates game Game<sub>3</sub> (resp. Game<sub>4</sub>) to A when the challenged RKEM session key is the real key (resp. a random key). Thus, we have

$$|\Pr[\text{Game}_3 = 1] - \Pr[\text{Game}_4 = 1]| \le \text{Adv}_{\text{RKEM}, B_3}^{\text{IND-RCCA}}(\lambda).$$

**Game<sub>5</sub>:** We change how ilD<sub>i</sub> and ilD<sub>r</sub> compute C<sub>7</sub>. In this game, we sample a random C<sub>7</sub> instead of computing it as KDF(ss<sub>C</sub>, C<sub>6</sub>). Due to the modification we made in the previous game, ss<sub>C</sub> is chosen uniformly at random. Therefore, by the PRF security of KDF, the two games

are indistinguishable. Thus, we have

$$|\Pr[\text{Game}_4 = 1] - \Pr[\text{Game}_5 = 1]| \le \text{Adv}_{\text{KDF}, B_3''}^{\text{PRF}}(\lambda).$$

**Game<sub>6</sub>:** We change how ilD<sub>i</sub> and ilD<sub>r</sub> compute the session key K<sub>out</sub>. In this game, we sample a random K<sub>out</sub> instead of computing it as KDF(Ø, C<sub>7</sub>). Due to the modification we made in the previous game, C<sub>7</sub> is chosen uniformly at random. Therefore, by the dual-PRF security of KDF, the two games are indistinguishable. Thus, we have

$$|\Pr[\text{Game}_5 = 1] - \Pr[\text{Game}_6 = 1]| \le \text{Adv}_{\text{KDF}, B_3''}^{\text{PRF}}(\lambda).$$

In game Game<sub>6</sub>, the tested session key K<sub>out</sub> is an independent and uniformly random value. Following a similar argument for the case (1-1), K<sub>out</sub> looks random to the adversary regardless of the challenge bit b. Therefore, we conclude that Pr[Game<sub>6</sub> = 1] = 1/2. Combining all arguments together, we obtain

$$\left| \Pr[\text{Game}_1 = 1] - \frac{1}{2} \right| \le NM^2 \cdot (\text{Adv}_{\text{RKEM}, B_3}^{\text{IND-RCCA}}(\lambda) + 2\text{Adv}_{\text{KDF}, B_3''}^{\text{PRF}}(\lambda)). \quad \square$$

*Proof of Case (2-1): responder's long-term key and initiator's session state are not compromised.*

**Lemma 8.** For any efficient adversary A, there exists a reduction B<sub>4</sub> that breaks the SPR-CCA security of KEM and B'<sub>4</sub> that breaks the PRF security of KDF such that

$$\left| \Pr[\text{Game}_1 = 1] - \frac{1}{2} \right| \le NM \cdot (\text{Adv}_{\text{KEM}, B_4}^{\text{SPR-CCA}}(\lambda) + 4\text{Adv}_{\text{KDF}, B_4''}^{\text{PRF}}(\lambda)).$$

*Proof.* We present the rest of the sequence of games from game Game<sub>2</sub>.

**Game<sub>2</sub>:** This game guesses the tested instance and its peer responder. At the beginning of the game, it chooses ilD<sub>i</sub> at random from [M] and r̂ at random from U. Let E<sub>Tested</sub> be the event that ilD<sub>i</sub> = ilD<sup>*</sup> and Resp[ilD<sup>*</sup>] = r̂. Since E<sub>Tested</sub> is an efficiently checkable event, the game outputs a random bit as soon as it detects that event E<sub>Tested</sub> does not occur. The probability the choice made by A is correctly guessed with probability 1/NM, so we have

$$|\Pr[\text{Game}_2 = 1] - \frac{1}{2}| = \frac{1}{NM} |\Pr[\text{Game}_1 = 1] - \frac{1}{2}|.$$

In the following, we can assume ilD<sub>i</sub> is an initiator since the tested instance is initiator in this case and its peer is r̂.

**Game<sub>3</sub>:** In this game, we modify how the user r̂ decrypts the KEM ciphertext. Let (ct<sub>S</sub>, ss<sub>S</sub>) $\stackrel{\$}{\leftarrow}$ Enc(pk<sub>r̂</sub>) be the KEM key-ciphertext pair generated by some instance ilD with the user r̂'s long-term key pk<sub>r̂</sub>. Then, when the user r̂ receives such a ciphertext ct<sub>S</sub>, it uses the corresponding key ss<sub>S</sub> that was generated by ilD instead of decrypting ct<sub>S</sub> on the fly. If decryption errors do not occur in KEM, the two games are identical. Hence,

$$|\Pr[\text{Game}_2 = 1] - \Pr[\text{Game}_3 = 1]| = \text{negl}(\lambda).$$
**Game4:** In this game, we modify the way the initiator instance $ilD_i$ computes the KEM session key and ciphertext. $ilD_i$ samples a random KEM secret $ss_S$ and simulates $ct_S$ with the simulator $S(1^\lambda)$ instead of computing $(ct_S, ss_S) \stackrel{\$}{\leftarrow} \text{Enc}(pk_{\hat{r}})$. Note that due to the modification we made in the previous game, when $\hat{r}$ receives $ct_S$ and decrypts it, it also uses the random key $ss_S$ generated by $ilD_i$. Since we consider the case (2-1), the long-term secret key of the user $j$ is not compromised if $E_{\text{Tested}}$ occurs. Thus, due to the SPR-CCA security of KEM, Game3 and Game4 are indistinguishable. More precisely, we can construct an algorithm $B_4$ breaking the SPR-CCA security of KEM as follows.

$B_4$ receives a tuple of challenge $(pk^*, ct^*, ss^*)$ from its challenger. $B_4$ then samples a random $(\hat{r}, ilD_i) \stackrel{\$}{\leftarrow} [N] \times [M]$ and generates the long-term key pairs as follows. For the user $\hat{r}$, $B_4$ uses $pk^*$ as its long-term public key, and for all the other parties, $B_4$ computes the long-term key pairs correctly. Finally, $B_4$ invokes $\mathcal{A}$ and answers the queries made by $\mathcal{A}$ as follows:

* $O_{\text{Init}}(i, r)$: Let $ilD$ be the assigned $ilD$.

- If $ilD = ilD_i$, then $B_4$ responds as in the previous game except that it sets $(ct_S, ss_S) := (ct^*, ss^*)$ instead of generating them on its own.

- Otherwise, $B_4$ responds as in the previous game.

* $O_{\text{Res}}(r, m_1)$: Let $ilD$ be the assigned $ilD$ and $ct$ be the KEM ciphertext in $m_1$.

- If $r = \hat{r}$, then $B_4$ checks if $ct = ct^*$. If so, it responds as in the previous game (i.e., it uses $ss := ss^*$). Otherwise, if $ct \neq ct^*$, then it sends $ct$ to $O_{\text{Dec}}$ oracle and receives back $ss'$. $B_4$ then responds with $ss'$.

- Otherwise, $B_4$ responds as in the previous game.

* $O_{\text{InitDer}}(ilD, m_2)$: $B_4$ responds as in the previous game.

* $O_{\text{CreatePSK}}(u)$, $O_{\text{RevLSK}}(u)$, $O_{\text{RevPSK}}(u)$, $O_{\text{RegisterPK}}(u)$, RevState($ilD$), RevSessKey($ilD$), Test($ilD$): $B_4$ responds as in the previous game. Here, note that since we consider case (2-1), $B_4$ can answer all the $O_{\text{RevLSK}}$-query and $O_{\text{RevState}}$-query since $\mathcal{A}$ never queries RevLSK($\hat{r}$) and RevState($ilD_i$) conditioning on $E_{\text{Tested}}$ not occurring, which is the only query that $B_4$ cannot answer.

If $\mathcal{A}$ outputs a guess $b'$, $B_4$ outputs 1 if $b = b'$ and 0 otherwise as its guess. It can be checked that $B_4$ perfectly simulates game $Game_3$ (resp. Game4) to $\mathcal{A}$ when the challenge is the real key and ciphertext (resp. a random key and a simulated ciphertext). Thus, we have

$$|\text{Pr}[\text{Game}_3 = 1] - \text{Pr}[\text{Game}_4 = 1]| \le \text{Adv}_{\text{KEM}, B'_4}^{\text{SPR-CCA}}(\lambda).$$

**Game5:** We change how $ilD_i$ computes $C_4$. In this game, we replace $C_4$ with a uniformly random value instead of computing it as KDF($ss_S$, $C_3$). Due to the modification we made in the previous game, $ss_S$ is chosen uniformly at random. Therefore, by the PRF security of KDF, the two games are indistinguishable. Thus, we have

$$|\text{Pr}[\text{Game}_4 = 1] - \text{Pr}[\text{Game}_5 = 1]| \le \text{Adv}_{\text{KDF}, B'_4}^{\text{PRF}}(\lambda).$$

**Game6:** We change how $ilD_i$ computes $C_5$. In this game, we replace $C_5$ with a uniformly random value instead of

computing it as KDF($pk_C$, $C_4$). Due to the modification we made in the previous game, $C_4$ is chosen uniformly at random. Therefore, by the dual-PRF security of KDF, the two games are indistinguishable. Thus, we have

$$|\text{Pr}[\text{Game}_5 = 1] - \text{Pr}[\text{Game}_6 = 1]| \le \text{Adv}_{\text{KDF}, B'_4}^{\text{PRF}}(\lambda).$$

**Game7:** We change how $ilD_i$ computes $C_6$. In this game, we replace $C_6$ with a uniformly random value instead of computing it as KDF($psk$, $C_5$), where $psk$ is the pre-shared key used in $ilD_i$. Due to the modification we made in the previous game, $C_5$ is chosen uniformly at random. Therefore, by the dual-PRF security of KDF, the two games are indistinguishable. Thus, we have

$$|\text{Pr}[\text{Game}_6 = 1] - \text{Pr}[\text{Game}_7 = 1]| \le \text{Adv}_{\text{KDF}, B'_4}^{\text{PRF}}(\lambda).$$

**Game7:** We change how $ilD_i$ computes $C_7$. In this game, we replace $C_7$ with a uniformly random value instead of computing it as KDF($ss$, $C_6$), where $ss$ is the RKEM session key decrypted by $ilD_i$. Due to the modification we made in the previous game, $C_6$ is chosen uniformly at random. Also, in case (2-1), the adversary does not know the seed $C_6$ stored in the session state of $ilD_i = ilD^*$ since it never queries $ilD^*$ to $O_{\text{RevState}}$. Therefore, by the dual-PRF security of KDF, the two games are indistinguishable. Thus, we have

$$|\text{Pr}[\text{Game}_7 = 1] - \text{Pr}[\text{Game}_8 = 1]| \le \text{Adv}_{\text{KDF}, B'_4}^{\text{PRF}}(\lambda).$$

**Game9:** We change how $ilD_r$ computes the session key $K_{\text{out}}$. In this game, $K_{\text{out}}$ is replaced with a uniformly random value. Due to the modification we made in the previous game, $C_7$ is chosen uniformly at random. Therefore, by the dual-PRF security of KDF, the two games are indistinguishable. Thus, we have

$$|\text{Pr}[\text{Game}_8 = 1] - \text{Pr}[\text{Game}_9 = 1]| \le \text{Adv}_{\text{KDF}, B'_4}^{\text{PRF}}(\lambda).$$

In game Game9, the tested session key $K_{\text{out}}$ is an independent and uniformly random value. Following a similar argument for the case (1-1), $K_{\text{out}}$ looks random to the adversary regardless of the challenge bit $b$. Therefore, we conclude that $\text{Pr}[\text{Game}_9 = 1] = 1/2$. Combining all arguments together, we obtain

$$\left| \text{Pr}[\text{Game}_1 = 1] - \frac{1}{2} \right| \le NM \cdot (\text{Adv}_{\text{KEM}, B'_4}^{\text{SPR-CCA}}(\lambda) + 4\text{Adv}_{\text{KDF}, B'_4}^{\text{PRF}}(\lambda)). \quad \square$$

*Proof of Cases (2-2): initiator's long-term key is not leaked*

**Lemma 9.** For any efficient adversary $\mathcal{A}$, there exists a reduction $B_5$ that breaks the SPR-CCA security of RKEM and $B'_5$ that breaks the PRF security of KDF such that

$$\left| \text{Pr}[\text{Game}_1 = 1] - \frac{1}{2} \right| \le NM \cdot (\text{Adv}_{\text{RKEM}, B_5}^{\text{SPR-CCA}}(\lambda) + 2\text{Adv}_{\text{KDF}, B'_5}^{\text{PRF}}(\lambda)).$$
**Proof.** We present the rest of the sequence of games from game Game$_2$.

**Game$_2$:** This game guesses a responder instance (which will be tested) and its initiator. At the beginning of the game, it chooses ilD$_r$ at random from $[M]$ and $\hat{i}$ at random from $U$. Let $E_{\text{Tested}}$ be the event that $\text{Init}[\text{ilD}^*] = \hat{i}$ and $\text{ilD}_r = \text{ilD}^*$. Since $E_{\text{Tested}}$ is an efficiently checkable event, the game outputs a random bit as soon as it detects that event $E_{\text{Tested}}$ does not occur. The probability the choice made by $\mathcal{A}$ is correctly guessed with probability $1/NM$, so we have

$$ \left| \Pr[\text{Game}_2 = 1] - \frac{1}{2} \right| = \frac{1}{NM} \left| \Pr[\text{Game}_1 = 1] - \frac{1}{2} \right| . $$

**Game$_3$:** In this game, we modify how the user $\hat{i}$ computes the session key. Let $(ct_C, ss_C) \stackrel{\$}{\leftarrow}$ REnc(pk$_{\hat{i}}$, rpk$_{\hat{i}}$) be the RKEM key-ciphertext pair generated by the instance ilD$_r$ with the user $\hat{i}$'s long-term key pk$_{\hat{i}}$ and some rpk$_{\hat{i}}$ generate by the $\hat{i}$'s initiator instance. Then, when some ilD' such that $\text{Init}[\text{ilD}'] = \hat{i}$ and its session state has a secret key of rpk$_{\hat{i}}$ is invoked with $ct_C$, it uses the key $ss_C$ that was generated by ilD$_r$ instead of decrypting $ct_C$. If decryption errors do not occur in RKEM, the two games are identical. Hence,

$$ |\Pr[\text{Game}_2 = 1] - \Pr[\text{Game}_3 = 1]| = \text{negl}(\lambda). $$

**Game$_4$:** In this game, we modify the way the responder instance ilD$_r$ computes the RKEM session key and ciphertext. Let rpk be the RKEM reinforcing public key received by ilD$_r$. ilD$_r$ samples a random RKEM secret $ss_C$ and simulates $ct_C$ with the simulator $S(1^{\lambda}, \text{rpk})$ instead of computing $(ct_C, ss_C) \stackrel{\$}{\leftarrow}$ REnc(pk$_{\hat{i}}$, rpk). Note that due to the modification we made in the previous game, when $\hat{i}$ receives $ct_C$ and decrypts it with rpk's secret key, it also uses the random key $ss_C$ generated by ilD$_r$. Since we consider the case (2-2), the long-term secret key of the user $\hat{i}$, who is the initiator of the tested instance, is never leaked if $E_{\text{Tested}}$ occurs. Thus, due to the SPR-CCA security of RKEM, Game$_3$ and Game$_4$ are indistinguishable. More precisely, we can construct an algorithm $B_5$ breaking the SPR-CCA security of RKEM as follows.

$B_5$ receives a challenge public key pk$^*$ from its challenger. $B_5$ then samples a random $(\hat{i}, \text{ilD}_r) \stackrel{\$}{\leftarrow} [N] \times [M]$ and generates the long-term key pairs as follows. For the user $\hat{i}$, $B_5$ uses pk$^*$ as its long-term public key, and for all the other parties, $B_5$ computes the long-term key pairs correctly. Finally, $B_5$ invokes $\mathcal{A}$ and answers the queries made by $\mathcal{A}$ as follows:

* $O_{\text{Init}}(i, r)$: $B_5$ responds as in the previous game except that it generates a reinforcing public key rpk through $O_{\text{RKeyGen}}$ oracle.

* $O_{\text{Res}}(r, m_1)$: Let ilD be the assigned ilD and rpk be the received reinforcing public key in $m_1$.

- If $\text{Init}[\text{ilD}] = \hat{i}$ and ilD = ilD$_r$, then $B_5$ responds as in the previous game except that it outputs rpk to its challenger, receives $(ct^*, ss^*)$, and sets $(ct_C, ss_C) := (ct^*, ss^*)$ instead of generating them on its own.

- Otherwise, $B_5$ responds as in the previous game.

* $O_{\text{InitDer}}(\text{ilD}, m_2)$: Depending on the value of $i = \text{Init}[\text{ilD}]$, it performs the following:

- If $i = \hat{i}$, then $B_5$ checks if $ct = ct^*$. If so, it responds as in the previous game (i.e., it uses $ss := ss^*$). Otherwise, if $ct \neq ct^*$, then it sends ct and its reinforcing public key rpk to $O_{\text{MalDec}}$ oracle and receives back $ss'$. $B_5$ then responds with $ss'$.

- If $i \neq \hat{i}$, then $B_5$ responds as in the previous game since it knows both the long-term secret key and reinforcing public secret key.

* $O_{\text{CreatePSK}}(u)$, $O_{\text{RevLSK}}(u)$, $O_{\text{RevPSK}}(u)$, $O_{\text{RegisterPK}}(u)$, $\text{RevState}(\text{ilD})$, $\text{RevSessKey}(\text{ilD})$, $\text{Test}(\text{ilD})$: $B_5$ responds as in the previous game. Here, note that since we consider case (2-2), $B_5$ can answer all the $O_{\text{RevLSK}}$-query since $\mathcal{A}$ never queries $\text{RevLSK}(\hat{i})$ conditioning on $E_{\text{Tested}}$ not occurring, which is the only query that $B_5$ cannot answer.

If $\mathcal{A}$ outputs a guess $b'$, $B_5$ outputs 1 if $b = b'$ and 0 otherwise as its guess. It can be checked that $B_5$ perfectly simulates game Game$_3$ (resp. Game$_4$) to $\mathcal{A}$ when the answer in the challenge phase is the real key and ciphertext (resp. a random key and a simulated ciphertext). Thus, we have

$$ |\Pr[\text{Game}_3 = 1] - \Pr[\text{Game}_4 = 1]| \le \text{Adv}_{\text{RKEM}, B_5}^{\text{SPR-CCA}}(\lambda). $$

**Game$_5$:** We change how ilD$_r$ computes $C_7$. In this game, we replace $C_7$ with a uniformly random value instead of computing it as KDF($ss_C$, $C_6$). Due to the modification we made in the previous game, $ss_C$ is chosen uniformly at random. Therefore, by the PRF security of KDF, the two games are indistinguishable. Thus, we have

$$ |\Pr[\text{Game}_4 = 1] - \Pr[\text{Game}_5 = 1]| \le \text{Adv}_{\text{KDF}, B_5}^{\text{PRF}}(\lambda). $$

**Game$_6$:** In this game, $K_{\text{out}}$ is replaced with a uniformly random value. Due to the modification we made in the previous game, $C_7$ is chosen uniformly at random. Therefore, by the dual-PRF security of KDF, the two games are indistinguishable. Thus, we have

$$ |\Pr[\text{Game}_5 = 1] - \Pr[\text{Game}_6 = 1]| \le \text{Adv}_{\text{KDF}, B_5}^{\text{PRF}}(\lambda). $$

In game Game$_6$, the tested session key $K_{\text{out}}$ is an independent and uniformly random value. Following a similar argument for the case (1-1), $K_{\text{out}}$ looks random to the adversary regardless of the challenge bit $b$. Therefore, we conclude that $\Pr[\text{Game}_6 = 1] = 1/2$. Combining all arguments together, we obtain

$$ \left| \Pr[\text{Game}_1 = 1] - \frac{1}{2} \right| \le NM \cdot (\text{Adv}_{\text{RKEM}, B_5}^{\text{SPR-CCA}}(\lambda) + 2\text{Adv}_{\text{KDF}, B_5}^{\text{PRF}}(\lambda)). $$

□
# Appendix D. Omitted Details of Generic Construction of RKEM

## D.1. Proof of T Transform

*Proof.* As the proof for C-IND and CR-IND security proceed almost identically, we only prove C-IND security below. We consider a sequence of hybrid games, where we denote $E_i$ as the event that $\mathcal{A}$ outputs $b' = 1$ in Game$_i$. The games are formally depicted in Fig. 11.

**Game$_0$:** In this game, the adversary is given an honestly generated ciphertext. This corresponds to the C-IND security game where $b = 0$ is sampled.

**Game$_1$:** This is the same as Game$_0$ except that it samples $\mu^*$ at the beginning of the game. This is only a conceptual change and we have $\text{Pr}[E_1] = \text{Pr}[E_0]$.

**Game$_2$:** This is the same as Game$_1$ except that the adversary $\mathcal{A}$ is given access to a different oracle $\mathcal{G}$. Let $\mathcal{RKPK}(\text{pk}^*)$ denote the space of reinforcing public keys, possibly including rpks that are not an output of RKeyGen(pk$^*$). Then, $\mathcal{G}$ is sampled uniformly random over all the functions mapping $\mathcal{RKPK}(\text{pk}^*) \times \mathcal{M} \times \mathcal{M}$ to $\mathcal{R}$ conditioned on that $\mathcal{F}(\text{rpk}, \mu, \mu_r) = \mathcal{G}(\text{rpk}, \mu, \mu_r)$ for all $(\text{rpk}, \mu, \mu_r) \in \mathcal{RKPK}(\text{pk}^*) \times \mathcal{M} \times \mathcal{M} \setminus S_{\mu^*}$, where $S_{\mu^*} := \{(\text{rpk}, \mu^*, \mu_r) : (\text{rpk}, \mu_r) \in \mathcal{RKPK}(\text{pk}^*) \times \mathcal{M}\}$. We later show in Lemma 10 that there exists an adversary $\mathcal{B}_2$ against OW-CPA security such that

$$|\text{Pr}[E_1] - \text{Pr}[E_2]| \le 2 \cdot Q_F \cdot \sqrt{\text{Adv}_{\text{RPKE}_2, \mathcal{B}_2}^{\text{OW-CPA}}(1^{\lambda})}.$$

**Game$_3$:** This is the same as Game$_2$ except that the randomness rand is generated uniformly at random. Notice that the random oracle $\mathcal{F}$ is no longer accessible by the adversary $\mathcal{A}$, and therefore, $\mathcal{F}(\text{rpk}^\prime, \mu^*, \mu_r)$ for all $(\text{rpk}^\prime, \mu^*, \mu_r) \in \mathcal{RKPK}(\text{pk}^*) \times S_{\mu^*}$ are information theoretically hidden from $\mathcal{A}$. Therefore, this modification cannot be noticed by $\mathcal{A}$. Hence, we have $\text{Pr}[E_3] = \text{Pr}[E_2]$.

**Game$_4$:** In this game the adversary is given a simulated ciphertext. This corresponds to the C-IND security game where $b = 1$ is sampled. It is clear that we can construct an adversary $\mathcal{B}_1$ against C-IND security such that

$$|\text{Pr}[E_3] - \text{Pr}[E_4]| \le \text{Adv}_{\text{RPKE}_2, \mathcal{B}_1}^{\text{C-IND}}(1^{\lambda}).$$

Now notice that we have

$$\begin{aligned} \text{Adv}_{\text{RPKE}_2, \mathcal{A}}^{\text{C-IND}}(1^{\lambda}) &:= |2 \cdot \text{Pr} \left[ \text{Game}_{\text{RPKE}_2, \mathcal{A}}^{\text{C-IND}}(1^{\lambda}) = 1 \right] - 1| \\ &= |(1 - \text{Pr}[E_0]) + \text{Pr}[E_4] - 1| \\ &= |\text{Pr}[E_0] - \text{Pr}[E_4]|. \end{aligned}$$

Combining all the bounds, we arrive at the bound in the theorem statement. It remains to prove Lemma 10 below.

**Lemma 10.** There exists an adversary $\mathcal{B}_2$ against OW-CPA security such that

$$|\text{Pr}[E_1] - \text{Pr}[E_2]| \le 2 \cdot Q_F \cdot \sqrt{\text{Adv}_{\text{RPKE}_2, \mathcal{B}_2}^{\text{OW-CPA}}(1^{\lambda})}.$$

*Proof.* We invoke the O2H lemma (cf. Lemma 4) with oracles $\mathcal{F}, \mathcal{G} : \mathcal{RKPK}(\text{pk}^*) \times \mathcal{M} \times \mathcal{M} \to \mathcal{R}$ as defined in Game$_2$. We define the random variable $z$ as $(\text{pk}^*, \mu^*, L)$, where $L$ is a list such that for all $(\text{rpk}, \mu_r) \in \mathcal{RKPK}(\text{pk}^*) \times \mathcal{M}$, $L[\text{rpk}, \mu_r] := \mathcal{F}(\text{rpk}, \mu^*, \mu_r)$. This is without loss of generality as $z$ can be any bit string that can depend arbitrary on $\mathcal{F}$ and $S_{\mu^*}$. We then define the oracle-calling algorithms $\mathcal{A}_{\text{O2H}}$ and $\mathcal{B}_{\text{O2H}}$ as in Fig. 11. If $\mathcal{H} := \mathcal{F}$ (resp. $\mathcal{H} := \mathcal{G}$), then $\mathcal{A}_{\text{O2H}(\cdot)}^{\text{H}}(z)$ is identical to Game$_1$ (resp. Game$_2$), assuming $\mu^* \stackrel{\mathcal{S}}{\leftarrow} \mathcal{D}_{\mathcal{M}}$ and $(\text{pk}^*, \text{sk}^*) \stackrel{\mathcal{S}}{\leftarrow} \text{KeyGen}(1^{\lambda})$. Then, using Lemma 4, we have

$$|\text{Pr}[E_1] - \text{Pr}[E_2]| \le 2 \cdot Q_F \cdot \sqrt{\text{Pr}_{\mathcal{F}, \mathcal{G}, S_{\mu^*}, z} \left[ \mathcal{T} \stackrel{\mathcal{S}}{\leftarrow} \mathcal{B}_{\text{O2H}}^{\text{G}(\cdot)}(z) : S_{\mu^*} \cap \mathcal{T} \ne \emptyset \right]}.$$

It remains to upper bound probability inside the square root, which we denote by $p$. To this end, we construct an adversary $\mathcal{B}_2$ against the OW-CPA security that simulates the behavior of $\mathcal{B}_{\text{O2H}}$. Namely, $\mathcal{B}_2$ is given pk$^*$ and access to a random oracle $\mathcal{G}$ as part of the OW-CPA security game. It first samples $i \stackrel{\mathcal{S}}{\leftarrow} [Q_F]$ and runs $\mathcal{A}$ on input pk$^*$, relaying any oracle queries $\mathcal{A}$ makes to its own oracle $\mathcal{G}$. Once $\mathcal{A}$ outputs $(\text{rpk}^\prime, \mu_r^\prime, \text{state})$, it outputs this as its own output. Once it receives ct from the game, it further invokes $\mathcal{A}$ on input $(\text{ct}, \text{state})$. In the above, when $\mathcal{A}$ makes its $i$-th query to $\mathcal{G}$, which is assumed to exist as $\mathcal{A}$ makes $Q_F$ queries, $\mathcal{B}_2$ measures it and outputs the first register $\mu^*$ as the solution to its OW-CPA security game.

It can be checked that $\mathcal{B}_2$ simulates $\mathcal{B}_{\text{O2H}}^{\text{G}(\cdot)}(z)$ perfectly, where $z = (\text{pk}^*, \mu^*, L)$ and $\mu^*$ is the challenge message sampled by the OW-CPA security game. Here, importantly, while $\mathcal{B}_2$ cannot prepare (the exponentially large unknown string) $z$, this is not an issue as $z$ is not explicitly used by $\mathcal{B}_{\text{O2H}}^{\text{G}(\cdot)}(z)$ (and hence by $\mathcal{A}_{\text{O2H}}^{\text{G}(\cdot)}(z)$). Thus, if $\mathcal{B}_{\text{O2H}}^{\text{G}(\cdot)}(z)$ outputs some $\mathcal{T} = (\text{rpk}, \mu^*, \mu_r)$ as its output, then $\mathcal{B}_2$ wins the OW-CPA security game. In particular, we have the desired bound $p \le \text{Adv}_{\text{RPKE}_2, \mathcal{B}_2}^{\text{OW-CPA}}(1^{\lambda})$. This completes the proof $\square$

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

## D.2. Proof of $U_m^\lambda$ Transform

*Proof.* It is immediate that $\delta_c$-correctness is inherited from $\text{RPKE}_2$. As the proof for IND-RCCA security is a simplified version of the proof of SPR-CCA security, we focus on SPR-CCA security below.

We consider a sequence of hybrid games, where we denote $E_i$ as the event that $\mathcal{A}$ outputs $b' = 1$ in Game$_i$. The core changes between the games are depicted in Fig. 6. While there are many subtle differences in how we manipulate the random oracles, the high level game transition follows the proof structure of [49, Theorem 4.1], which is also an extension of techniques used in [51], [66], [67]. Below, for simplicity and without loss of generality, we assume $\mathcal{A}$ only asks for a challenge ciphertext with respect to a reinforcing key rpk$^\prime$ that it has not obtained from $\mathcal{O}_{\text{RKeyGen}}$.
<figure><img src="image_8.png" /><figcaption>Figure 11. Hybrid games for Thm. 5 and tools to invoke the O2H lemma (cf. Lemma 4). The blue highlights the differences in the games.</figcaption></figure>

**Game0:** This corresponds to the SPR-CCA game where $b=0$ is sampled. We thus have

$$ \Pr[E_0] = 1 - \Pr \left[ \text{Game}_{\text{RKEM},A}^{\text{SPR-CCA}}(1^{\lambda}) = 1 \mid b = 0 \right]. $$

**Game1:** This is the same as Game0 except that $H(\text{rpk}, \mu, \mu_r)$ in the decapsulation oracle is replaced by $H_L(\text{rpk}, \mu, \mu_r)$, where $H_L: \mathcal{RPK}(\text{pk}^*) \times \mathcal{M} \times \mathcal{M}$ is another random oracle. From Lemma 3, we have

$$ |\Pr[E_0] - \Pr[E_1]| \le (Q_{\text{dec}} + Q_{\text{H}_{\text{prf}}}) \cdot 2^{-\frac{\ell}{2}+1}. $$

**Game2:** This is the same as Game1 except that the game samples the $Q_{\text{rpk}}$ reinforcing keys $(\text{rpk}_i, \text{rsk}_i)_{i \in [Q_{\text{rpk}}]}$ after it samples $(\text{pk}^*, \text{sk}^*)$. On the $i$-th query to $\mathcal{O}_{\text{RKeyGen}}$ from the adversary, it simply returns $(\text{rpk}_i, \text{rsk}_i)$, as opposed to sampling them as in the previous game. This is merely a conceptual change. In this game, the game further samples the random oracle $\mathcal{F}: \mathcal{RPK}(\text{pk}^*) \times \mathcal{M} \times \mathcal{M} \to \mathcal{R}$ from $\mathcal{F}^{\text{good}}_{\text{pk}^*, (\text{rpk}_i)_{i \in [Q_{\text{rpk}}]}}$ defined below, where $\mathcal{R}$ denotes the encryption randomness space of the underlying RPKE$_2$.

For any $N \in \mathbb{N}$, $(\text{pk}^*, \text{sk}^*) \in \text{KeyGen}(1^{\lambda})$, $(\text{rpk}_i, \text{rsk}_i) \in \text{RKeyGen}(\text{pk}^*)$, and $(\mu_i, \mu_{r,i}) \in \mathcal{M} \times \mathcal{M}$ for $i \in [Q_{\text{rpk}}]$, we define two sets of good randomness as

$$
\begin{align*}
\mathcal{R}^{\text{good}}_{\text{pk}^*, \mu} &:= \{r \in \mathcal{R} : \forall \text{rpk} \in \mathcal{RPK}(\text{pk}^*), \\
& \phantom{:=} \mu = \text{RHalfDec}_2(\text{sk}, \text{REnc}_2(\text{pk}, \text{rpk}, \mu, \mu_r; r))\}, \text{ and} \\
\mathcal{R}^{\text{good}}_{\text{pk}^*, (\text{rpk}_i, \mu_i, \mu_{r,i})_{i \in [Q_{\text{rpk}}]}} &:= \{(r_i)_{i \in [Q_{\text{rpk}}]} \in \mathcal{R}^{\text{Rpk}} : \forall i \in [Q_{\text{rpk}}], \\
& \phantom{:=} \text{RDec}_2(\text{sk}^*, \text{rsk}_i, \text{REnc}_2(\text{pk}^*, \text{rpk}_i, \mu_i, \mu_{r,i}; r_i)) = (\mu_i, \mu_{r,i})\}.
\end{align*}
$$

The first (resp. second) set is the set of good randomness such that half (resp. standard) decryption succeeds. Here, while we omit them for better readability, we note that $\mathcal{R}^{\text{good}}_{\text{pk}^*}$ and $\mathcal{R}^{\text{good}}_{\text{pk}^*, (\text{rpk}_i, \mu_i, \mu_{r,i})_{i \in [Q_{\text{rpk}}]}}$ also depend on the secret keys $\text{sk}^*$ and $(\text{rsk}_i)_{i \in [Q_{\text{rpk}}]}$. Then, let $\mathcal{F}^{\text{good}}_{\text{pk}^*, (\text{rpk}_i)_{i \in [Q_{\text{rpk}}]}}$ be the set of functions $\mathcal{F}: \mathcal{RPK}(\text{pk}^*) \times \mathcal{M} \times \mathcal{M} \to \mathcal{R}$ satisfying $\mathcal{F}(\text{rpk}, \mu, \mu_r) \in \mathcal{R}^{\text{good}}_{\text{pk}^*}$ for all $(\text{rpk}, \mu, \mu_r) \in \mathcal{R}^{\text{RPK}}(\text{pk}^*) \times \mathcal{M} \times \mathcal{M}$ and $(\mathcal{F}(\text{rpk}_i, \mu_i, \mu_{r,i}))_{i \in [Q_{\text{rpk}}]} \in \mathcal{R}^{\text{good}}_{\text{pk}^*, (\text{rpk}_i, \mu_i, \mu_{r,i})_{i \in [Q_{\text{rpk}}]}}$ for all $(\mu_i, \mu_{r,i}) \in \mathcal{M} \times \mathcal{M}$. In Game2, we sample $\mathcal{F}$ from this $\mathcal{F}^{\text{good}}_{\text{pk}^*, (\text{rpk}_i)_{i \in [Q_{\text{rpk}}]}}$. Note that
<table><caption>TABLE 4. SUMMARY OF GAMES FOR THE PROOF OF SPR-CCA IN THM. 6.</caption><thead><tr><th rowspan="2">Game</th><th rowspan="2">H</th><th rowspan="2">F</th><th rowspan="2">ct*</th><th rowspan="2">ss*</th><th colspan="2">Decapsulation</th><th rowspan="2">Justification</th></tr><tr><th>valid ct</th><th>invalid ct</th></tr></thead><tbody><tr><td>Game<sub>0</sub></td><td>H</td><td>F<sub>pk*</sub></td><td>REnc(pk*, rpk')</td><td>H(rpk', μ*, μ<sub>r</sub><sup>*</sup>)</td><td>H(rpk, μ, μ<sub>r</sub>)</td><td>H<sub>prf</sub>(s, s<sub>r</sub>, rpk, ct)</td><td></td></tr><tr><td>Game<sub>1</sub></td><td>H</td><td>F<sub>pk*</sub></td><td>REnc(pk*, rpk')</td><td>H(rpk', μ*, μ<sub>r</sub><sup>*</sup>)</td><td>H(rpk, μ, μ<sub>r</sub>)</td><td>H<sub>L</sub>(rpk, ct)</td><td>Lemma 3</td></tr><tr><td>Game<sub>2</sub></td><td>H</td><td>F<sub>pk*</sub><sup>good</sup></td><td>REnc(pk*, rpk')</td><td>H(rpk', μ*, μ<sub>r</sub><sup>*</sup>)</td><td>H(rpk, μ, μ<sub>r</sub>)</td><td>H<sub>L</sub>(rpk, ct)</td><td>Lemma 2 + δ<sub>hc</sub>,<br>δ<sub>c</sub>-correctness</td></tr><tr><td>Game<sub>3</sub></td><td>H'<sub>L</sub> ∠ g<sub>L</sub></td><td>F<sub>pk*</sub><sup>good</sup></td><td>REnc(pk*, rpk')</td><td>H(rpk', μ*, μ<sub>r</sub><sup>*</sup>)</td><td>H(rpk, μ, μ<sub>r</sub>)</td><td>H<sub>L</sub>(rpk, ct)</td><td>by ensuring perfect<br>correctness</td></tr><tr><td>Game<sub>4</sub></td><td>H<sub>L</sub> ∠ g<sub>L</sub></td><td>F<sub>pk*</sub><sup>good</sup></td><td>REnc(pk*, rpk')</td><td>H(rpk', μ*, μ<sub>r</sub><sup>*</sup>)</td><td>H(rpk, μ, μ<sub>r</sub>)</td><td>H<sub>L</sub>(rpk, ct)</td><td>by ensuring perfect<br>correctness</td></tr><tr><td>Game<sub>5</sub></td><td>H<sub>L</sub> ∠ g<sub>L</sub></td><td>F<sub>pk*</sub><sup>good</sup></td><td>REnc(pk*, rpk')</td><td>H<sub>-L</sub>(rpk', ct*, μ<sub>r</sub><sup>*</sup>)</td><td>H<sub>L</sub>(rpk, ct)</td><td>H<sub>L</sub>(rpk, ct)</td><td>conceptual</td></tr><tr><td>Game<sub>6</sub></td><td>H<sub>L</sub> ∠ g<sub>L</sub></td><td>F<sub>pk*</sub></td><td>REnc(pk*, rpk')</td><td>H<sub>-L</sub>(rpk', ct*, μ<sub>r</sub><sup>*</sup>)</td><td>H<sub>L</sub>(rpk, ct)</td><td>H<sub>L</sub>(rpk, ct)</td><td>Lemma 2 + δ<sub>hc</sub>-half and<br>δ<sub>c</sub>-correctness</td></tr><tr><td>Game<sub>7</sub></td><td>H<sub>L</sub> ∠ g<sub>L</sub></td><td>F<sub>pk*</sub></td><td>S(1<sup>λ</sup>, rpk', μ<sub>r</sub><sup>*</sup>)</td><td>H<sub>-L</sub>(rpk', ct*, μ<sub>r</sub><sup>*</sup>)</td><td>H<sub>L</sub>(rpk, ct)</td><td>H<sub>L</sub>(rpk, ct)</td><td>CR-IND security</td></tr><tr><td>Game<sub>8</sub></td><td>H<sub>L</sub> ∠ g<sub>L</sub></td><td>F<sub>pk*</sub></td><td>S(1<sup>λ</sup>, rpk', μ<sub>r</sub><sup>*</sup>)</td><td>U(K)</td><td>H<sub>L</sub>(rpk, ct)</td><td>H<sub>L</sub>(rpk, ct)</td><td>statistical disjointness</td></tr><tr><td>Game<sub>9</sub></td><td>H<sub>L</sub> ∠ g<sub>L</sub></td><td>F<sub>pk*</sub><sup>good</sup></td><td>S(1<sup>λ</sup>, rpk', μ<sub>r</sub><sup>*</sup>)</td><td>U(K)</td><td>H<sub>L</sub>(rpk, ct)</td><td>H<sub>L</sub>(rpk, ct)</td><td>Lemma 2 + δ<sub>hc</sub>-half,<br>δ<sub>c</sub>-correctness</td></tr><tr><td>Game<sub>10</sub></td><td>H<sub>L</sub> ∠ g<sub>L</sub></td><td>F<sub>pk*</sub><sup>good</sup></td><td>S(1<sup>λ</sup>, rpk', μ<sub>r</sub><sup>*</sup>)</td><td>U(K)</td><td>H(rpk, μ, μ<sub>r</sub>)</td><td>H<sub>L</sub>(rpk, ct)</td><td>conceptual</td></tr><tr><td>Game<sub>11</sub></td><td>H'<sub>L</sub> ∠ g<sub>L</sub></td><td>F<sub>pk*</sub><sup>good</sup></td><td>S(1<sup>λ</sup>, rpk', μ<sub>r</sub><sup>*</sup>)</td><td>U(K)</td><td>H(rpk, μ, μ<sub>r</sub>)</td><td>H<sub>L</sub>(rpk, ct)</td><td>by ensuring perfect<br>correctness</td></tr><tr><td>Game<sub>12</sub></td><td>H</td><td>F<sub>pk*</sub><sup>good</sup></td><td>S(1<sup>λ</sup>, rpk', μ<sub>r</sub><sup>*</sup>)</td><td>U(K)</td><td>H(rpk, μ, μ<sub>r</sub>)</td><td>H<sub>L</sub>(rpk, ct)</td><td>by ensuring perfect<br>correctness</td></tr><tr><td>Game<sub>13</sub></td><td>H</td><td>F<sub>pk*</sub></td><td>S(1<sup>λ</sup>, rpk', μ<sub>r</sub><sup>*</sup>)</td><td>U(K)</td><td>H(rpk, μ, μ<sub>r</sub>)</td><td>H<sub>L</sub>(rpk, ct)</td><td>Lemma 2 + δ<sub>hc</sub>-half,<br>δ<sub>c</sub>-correctness</td></tr><tr><td>Game<sub>14</sub></td><td>H</td><td>F<sub>pk*</sub></td><td>S(1<sup>λ</sup>, rpk', μ<sub>r</sub><sup>*</sup>)</td><td>U(K)</td><td>H(rpk, μ, μ<sub>r</sub>)</td><td>H<sub>prf</sub>(s, s<sub>r</sub>, rpk, ct)</td><td>Lemma 3</td></tr></tbody></table>

in the previous game, we sampled F from $\mathcal{F}_{pk*}$, the set of all functions mapping $\mathcal{RPK}(pk^*) \times \mathcal{M} \times \mathcal{M}$ to $\mathcal{R}$.

Let us analyze the difference in the adversary's advantage. For any $N \in \mathbb{N}$, let us define

$$ \delta_{pk^*, (rk_{i}, \mu_{i}, \mu_{r, i})_{i \in [Q_{rk}]} := \left| \mathcal{R} \setminus \left( \mathcal{R}_{pk^*}^{\text{good}} \cap \mathcal{R}_{pk^*, (rk_{i}, \mu_{i}, \mu_{r, i})_{i \in [Q_{rk}]}^{\text{good}} \right) \right| / |\mathcal{R}|, $$

the fraction of the bad randomness. That is the fraction of randomness for which half or standard decryption fails. Further define

$$ \delta_{pk^*, (rk_{i})_{i \in [Q_{rk}]} := \max_{(\mu_i, \mu_{r,i})_{i \in [Q_{rk}]} \in (\mathcal{M} \times \mathcal{M})^{Q_{rk}}} \delta_{pk^*, (rk_{i}, \mu_{i}, \mu_{r,i})_{i \in [Q_{rk}]} $$

Relying on Lemma 2 and following a similar analysis in the proof of [48, Theorem 3.2], we have

$$ \left| \Pr[E_1 | (pk^*, sk^*, (rk_i, rsk_i)_{i \in [Q_{rk}})] \\ - \Pr[E_2 | (pk^*, sk^*, (rk_i, rsk_i)_{i \in [Q_{rk}})] \right| \\ \le 8 \cdot (Q_F + Q_{dec} + 2)^2 \cdot \delta_{pk^*, (rk_i)_{i \in [Q_{rk}}}. $$

By definition of $\delta_{hc}$-half and $\delta_c$-correctness of $RPKE_2$ (cf. Def. 22 and 23), and using the union bound, we have $\mathrm{Exp}[\delta_{pk^*, (rk_i)_{i \in [Q_{rk}}}] \le \delta_{hc} + Q_{rk} \cdot \delta_c$, where the expectation is taken over the randomness of sampling $(pk^*, sk^*) \stackrel{\$}{\leftarrow} \mathrm{KeyGen}(1^\lambda)$ and $(rk_i, rsk_i) \stackrel{\$}{\leftarrow} \mathrm{RKeyGen}(pk^*)$ for $i \in [Q_{rk}]$. Taking the average, we have

$$ |\Pr[E_1] - \Pr[E_2]| \le 8 \cdot (Q_F + Q_{dec} + 2)^2 \cdot (\delta_{hc} + Q_{rk} \cdot \delta_c). $$

Below, let BAD denote the event for which either of the following conditions hold: there exists some $(rk, \mu, \mu_r) \in \mathcal{RPK}(pk^*) \times \mathcal{M} \times \mathcal{M}$ such that no $r \in \mathcal{R}$ satisfies $\mu = \mathrm{RHalfDec}_2(\mathrm{sk}, \mathrm{REnc}_2(rk, rpk, \mu, \mu_r; r))$; and there exists some $i \in [Q_{rk}]$ and $(\mu_i, \mu_{r,i})_{i \in [Q_{rk}]} \in (\mathcal{M} \times \mathcal{M})^{Q_{rk}}$ such that no $r_i \in \mathcal{R}$ satisfies $(\mu_i, \mu_{r,i}) = \mathrm{RDec}_2(\mathrm{sk}^*, \mathrm{rsk}_i, \mathrm{REnc}_2(pk^*, rpk_i, \mu_i, \mu_{r,i}; r_i))$. Put differently, BAD denotes the event that there are no randomness for which either the half or standard decryption succeeds. Following a similar argument to [67, Claim 3] and using the union bound, we have $\Pr[\mathrm{BAD}] \le Q_{rk} \delta_{hc} + Q_{rk} \cdot \delta_c$. Lastly, we denote GOOD as the event that BAD does not occur.

**Game 3:** This is the same as Game 2 except that the random oracle H is simulated as follows, where L denotes the set of