$Q_{\text{rpk}}$ reinforcing public keys ($\text{rpk}_i$)$_i \in [Q_{\text{rpk}}]$ sampled by the game at the beginning of the game:

$$H(\text{rpk}, \mu, \mu_r) := \begin{cases} H'_L \circ g_L(\text{rpk}, \mu, \mu_r) & \text{if } \text{rpk} \in L \\ H'_{\neg L} \circ g_{\neg L}(\text{rpk}, \mu, \mu_r) & \text{if } \text{rpk} \notin L, \end{cases}$$

where $H'_L : \mathcal{RK}\mathcal{K}(\text{pk}^*) \times \mathcal{CT} \to \mathcal{K}$ and $H'_{\neg L} : \mathcal{RK}\mathcal{K}(\text{pk}^*) \times \mathcal{CT} \times \mathcal{M} \to \mathcal{K}$ are randomly sampled random oracles and

$$\begin{aligned} 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), \delta_{\text{hc}}). \end{aligned}$$

Here, $\mathcal{CT}$ denotes the ciphertext space of the underlying $\text{RPKE}_2$.

Notice that conditioned on GOOD, we have perfect half and standard decryption. Therefore, $g_L$ and $g_{\neg L}$ are injective functions. Note that $g_{\neg L}$ outputs $\mu_r$ because in case $\text{rpk} \notin L$, we cannot have no guarantee that $\text{ct} = \overline{\text{REnc}_2}(\text{pk}, \text{rpk}, \mu, \mu_r)$ correctly decrypts the message $\mu_r$. Thus, if GOOD occurs, then $H'_L$ and $H'_{\neg L}$ are both random functions and this game is equivalent to the previous game. We have,

$$\Pr[E_2 \wedge \text{GOOD}] = \Pr[E_3 \wedge \text{GOOD}]$$

Moreover, using a simple statistical lemma [49, Lemma A.1], we have

$$\begin{aligned} |\Pr[E_1] - \Pr[E_2]| &\le |\Pr[E_1] - \Pr[E_2 \wedge \text{GOOD}]| + \Pr[\text{BAD}] \\ &\le |\Pr[E_1] - \Pr[E_2 \wedge \text{GOOD}]| + \delta_{\text{hc}} + Q_{\text{rpk}} \cdot \delta_{\text{c}}. \end{aligned}$$

**Game 4:** This is the same as Game 3 except that $H'_L$ is simulated using $H_L$. For consistency, we also make a conceptual modification by rewriting $H'_{\neg L}$ as $H_{\neg L}$.

A ciphertext ct (with respect to $\text{rpk}_i \in L$) is said to be valid if we have $\text{ct} = \overline{\text{REnc}_2}(\text{pk}^*, \text{rpk}_i, \text{RDec}_2(\text{sk}^*, \text{rsk}_i, \text{ct}))$, and invalid otherwise. Notice that in the previous game, $H_L$ is only used for invalid ciphertexts, and an adversary cannot access $H_L$ on a valid ciphertext. On the other hand, conditioned on GOOD, $H'_L$ is only used for valid ciphertexts owing to $g_L$, and an adversary cannot access $H'_L$ on an invalid ciphertext. Therefore, conditioned on GOOD, the adversary cannot detect if we replace $H'_L$ by $H_L$, and we have

$$\Pr[E_3 \wedge \text{GOOD}] = \Pr[E_4 \wedge \text{GOOD}]$$

**Game 5:** This game is the same as Game 4 except that the challenge session key $\text{ss}^*$ is set as $H_{\neg L}(\text{rpk}^*, \text{ct}^*, \mu_r^*)$ and the decryption oracle always returns $H_L(\text{rpk}, \text{ct})$ as long as $\text{ct} \neq \text{ct}^*$. Conditioned on GOOD and the assumption that $\text{rpk}' \notin L$, this modification is merely conceptual due to the definition of $g_L$ and $g_{\neg L}$. We thus have

$$\Pr[E_4 \wedge \text{GOOD}] = \Pr[E_5 \wedge \text{GOOD}]$$

Using the same statistical argument, we have

$$\begin{aligned} |\Pr[E_5] - \Pr[E_6]| &\le |\Pr[E_5] - \Pr[E_5 \wedge \text{GOOD}]| + \Pr[\text{BAD}] \\ &\le |\Pr[E_5] - \Pr[E_5 \wedge \text{GOOD}]| + \delta_{\text{hc}} + Q_{\text{rpk}} \cdot \delta_{\text{c}}. \end{aligned}$$

**Game 6:** This game is the same as Game 5 except that we undo the change we made in Game 2. Namely, we now sample F from $\mathcal{F}_{\text{pk}^*}$, the set of all functions mapping $\mathcal{RK}\mathcal{K}(\text{pk}^*) \times$

$\mathcal{M} \times \mathcal{M}$ to $\mathcal{R}$. Following the same argument as before, we have

$$|\Pr[E_5] - \Pr[E_6]| \le 8 \cdot (Q_F + Q_H + 2)^2 \cdot (\delta_{\text{hc}} + Q_{\text{rpk}} \cdot \delta_{\text{c}}).$$

Here note that $Q_{\text{dec}}$ is replaced by $Q_H$ as H internally calls F when invoking $g_L$ and $g_{\neg L}$.

**Game 7:** This game is the same as Game 6 except that the challenge ciphertext $\text{ct}^*$ is generated using the simulator $\overline{\mathcal{S}}(1^{\lambda}, \text{rpk}^*, \mu_r^*)$ defined by the CR-IND security game of the underlying $\text{RPKE}_2$.

Notice that in Game 7, the decapsulation oracle no longer needs any secret key as the response is $H_L(\text{rpk}, \text{ct})$ regardless of the decryption result. Moreover, the challenge session key $\text{ss}^*$ no longer needs the challenge message $\mu^*$ as it can use $\text{ct}^*$ instead. Therefore, it is easy to check that we can construct an adversary $\mathcal{B}$ against the CR-IND security of $\text{RPKE}_2$ such that

$$|\Pr[E_6] - \Pr[E_7]| \le \text{Adv}_{\overline{\text{RPKE}_2, \mathcal{B}}}^{\text{CR-IND}}(1^{\lambda}).$$

**Game 8:** This game is the same as Game 7 except that we sample $\text{ss}^* \leftarrow \mathcal{S}^* \mathcal{K}$, as opposed to $\text{ss}^* := H_{\neg L}(\text{rpk}^*, \text{ct}^*, \mu_r^*)$.

Notice that if $\text{ct}^* \leftarrow \overline{\mathcal{S}}(1^{\lambda}, \text{rpk}^*, \mu_r^*)$ is not in $\overline{\text{REnc}_2}(\text{pk}, \text{rpk}, \mathcal{M}, \mathcal{M})$, then the adversary has no information on $H_{\neg L}(\text{rpk}^*, \text{ct}^*, \mu_r^*)$. This is because the only way the adversary can access $H_{\neg L}$ is through H but it internally runs $\overline{\text{REnc}_2}$ thanks to $g_{\neg L}$. Hence, relying on the statistical disjointness of the underlying $\text{RPKE}_2$, we have

$$|\Pr[E_7] - \Pr[E_8]| \le \text{Disj}_{\overline{\text{RPKE}_2}}(1^{\lambda}).$$

**Game 9 to Game 14:** The remaining games consist of undoing all the modifications we made on the random oracles and decapsulation oracle from Game 0 to Game 5. The exact game transition is given in Tab. 4. As it is just a rewrite of Game 0 to Game 5 with the same bound, we omit the details. We note that Game 14 corresponds to the SPR-CCA game where $b=1$ is sampled. We thus have

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

Combining all the bounds together, we arrive at the bound in the theorem statement.

Lastly, we point out that the proof of IND-RCCA is a simplification of the above proof for SPR-CCA. This is because in the SPR-CCA security game, the challenge ciphertext was created using a malicious reinforcing public key $\text{rpk}'$ and the decapsulation oracle could be queried on any honest $\text{rpk}_i \in L$ generated by the challenger. In contrast, in the IND-RCCA security game, the challenge ciphertext and decapsulation oracle are defined by a unique honestly generated $\text{rpk}^*$. The proof for IND-RCCA consists of almost the same game hybrids for SPR-CCA, but removes the discussion on $\delta_{\text{hc}}$-half correctness and sets $Q_{\text{rpk}} = 1$. As the proof is almost identical, we omit the details. $\square$
# Appendix E. Omitted Details of Lattice-based RPKE₂

## E.1. C-IND Security of RPKE₂

*Proof.* 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 simulator $S$ takes as input $(1^{\lambda}, \text{rk}_i, \mu_r)$, samples random $(\mathbf{u}, v_0, v_1) \leftarrow \mathcal{R}_q^k \times \mathcal{R}_q \times \mathcal{R}_q$, and outputs a ciphertext ct as $(\bar{\mathbf{u}}, \bar{v}_0, \bar{v}_1) := (\text{Compress}_q(\mathbf{u}, d_u), \text{Compress}_q(v_0, d_{v_0}), \text{Compress}_q(v_1, d_{v_1}))$. Some of the critical game transitions are depicted in Fig. 12.

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

$$ \Pr[E_0] = 1 - \Pr \left[ \text{Game}_{\text{RPKE}_2, \mathcal{A}}^{\text{C-IND}}(1^{\lambda}) = 1 \mid b=0 \right]. $$

**Game1:** This is the same as Game0 except that the game modifies how the random oracle $G$ is simulated. It first samples $(\text{seed}_A, A) \leftarrow \{0, 1\}^{256} \times \mathcal{R}_q^{n \times k}$ and a $2Q_G$-wise independent function $G: \{0, 1\}^{256} \times \mathcal{R}_q^{n \times k}$ conditioned on $G(\text{seed}_A) = A$, where $Q_G$ is the number of oracle queries to $G$. One way to sample such function would be to first sample a random $G'$ (which is possible since $q$ is a prime, cf. [81, Theorem 6.1]). Let $M = G'(\text{seed}_A)$. Then simply define $G$ as computing $G'$ and adding $A-M$. Using [81, Theorem 6.1], a $2Q_G$-wise independent function is perfectly indistinguishable from a random oracle to an adversary making at most $Q_G$ oracle queries. Moreover, for oracle $G_{\text{Decomp}}$, we can simply use a $2Q_{\text{Decomp}}$-wise independent function to sample the randomness to run $G_{\text{Decomp}}$, where $Q_{\text{Decomp}}$ is the number of oracle queries to $G_{\text{Decomp}}$. We thus have $\Pr[E_0] = \Pr[E_1]$.

**Game2:** This is the same game as Game1 except that the public key $b$ is sampled uniformly over $\mathcal{R}_q^n$ as opposed to $b := A \cdot s + x$ as in the previous game. As we modified $A$ to be directly sampled by the game, it is easy to check that this game is indistinguishable from the previous game relying on MLWE. Formally, there exists an adversary $\mathcal{B}_1$ against the MLWE$_{q,n,k,\chi,\chi}$ problem such that

$$ |\Pr[E_1] - \Pr[E_2]| \le \text{Adv}_{\mathcal{B}_1}^{\text{MLWE}}(1^{\lambda}). $$

**Game3:** This is the same as Game2 except that it samples the challenge message $\mu^*$ and computes $\Delta := G_r(\mu^*)$ at the outset of the game. See Fig. 12 for the exact description. Clearly this produces the same view to the adversary as in the previous game. We thus have $\Pr[E_2] = \Pr[E_3]$.

**Game4:** This is the same as Game3 except that the adversary $\mathcal{A}$ is given access to a different oracle $F$ as opposed to $G_r$. In particular, the game samples a random $F: \mathcal{M} \to \mathcal{R}_q$ such that $F(\mu) = G_r(\mu)$ for all $\mu \in \mathcal{M} \setminus \{\mu^*\}$. See Fig. 12 for the formal description of the game. We later show in Lemma 11 that there exists an adversary $\mathcal{B}_2$ against the MLWE$_{q,k+1,n,\chi_r, (\chi_i)_{i \in [k+1]}}$ problem such that

$$ |\Pr[E_3] - \Pr[E_4]| \le 2 \cdot Q_{G_r} \cdot \sqrt{\text{Adv}_{\mathcal{B}_2}^{\text{MLWE}}(1^{\lambda}) + \frac{1}{|\mathcal{M}|}}. $$

**Game5:** This is the same as Game4 except that it samples $\Delta \leftarrow \mathbb{Z}_{2^{d_{v_1}}}^d$ as opposed to setting it as $\Delta := G_r(\mu^*)$. See Fig. 12 for the formal description of the game. Notice that the random oracle $G_r$ is no longer accessible by the adversary $\mathcal{A}$, and therefore, $\Delta$ is information theoretically hidden from $\mathcal{A}$. Therefore, this modification cannot be noticed by $\mathcal{A}$. Hence, we have $\Pr[E_4] = \Pr[E_5]$.

**Game6:** This is the same game as Game5 except that the challenger ciphertext ct* = $(\bar{\mathbf{u}}^*, \bar{v}_0^*, \bar{v}_1^*)$ is sampled slightly differently. It generates $\bar{\mathbf{u}}^*$ and $\bar{v}_0^*$ as in the previous game but samples $\bar{v}_1^* \leftarrow \mathbb{Z}_{2^{d_{v_1}}}^d$. Due to the modification we made in the previous game, $\Delta$ is information theoretically hidden to the adversary. Therefore, $\bar{v}_1^*$ is distributed uniformly random over $\mathbb{Z}_{2^{d_{v_1}}}^d$. We therefore have $\Pr[E_5] = \Pr[E_6]$.

**Game7:** This is the same game as Game6 except that the remaining part of the challenger ciphertext ct* is sampled uniformly at random. It samples $(\mathbf{u}^*, v_0^*) \leftarrow \mathcal{R}_q^k \times \mathcal{R}_q$ and sets $(\bar{\mathbf{u}}^*, \bar{v}_0^*) := (\text{Compress}_q(\mathbf{u}^*, d_u), \text{Compress}_q(v_0^*, d_{v_0}))$. See Fig. 12 for the formal description of the game. It is easy to check that this game is indistinguishable from the previous game relying on MLWE. Formally, there exists an adversary $\mathcal{B}_3$ against the MLWE$_{q,k+1,n,\chi_r, (\chi_i)_{i \in [k+1]}}$ problem such that

$$ |\Pr[E_6] - \Pr[E_7]| \le \text{Adv}_{\mathcal{B}_3}^{\text{MLWE}}(1^{\lambda}). $$

At this point, observe that the challenge ciphertext ct* is the same as an output of the simulator $S(1^{\lambda}, \text{rk}_r, \mu_r')$.

**Game8:** This is the same as Game7 except that it no longer samples $\Delta$ and the adversary $\mathcal{A}$ is given access to the oracle $G_r$ as opposed to $F$ in the prior game. See Fig. 12 for the formal description of the game. As $\Delta$ is no longer used by the game, this is a conceptual change. Moreover, as $G_r$ and $F$ have the same functionality, this is also only conceptual. Therefore, we have $\Pr[E_7] = \Pr[E_8]$.

**Game9:** The remaining game is to undo the changes from Game0 to Game2. Namely, the public key is sampled as a valid MLWE sample and the oracle $G$ is sampled randomly. Following the exact same argument to move from Game0 to Game2, we can show that there exists an adversary $\mathcal{B}_4$ against the MLWE$_{q,n,k,\chi,\chi}$ problem such that

$$ |\Pr[E_8] - \Pr[E_9]| \le \text{Adv}_{\mathcal{B}_4}^{\text{MLWE}}(1^{\lambda}). $$

This corresponds to the C-IND game where $b=1$ is sampled. We thus have

$$ \Pr[E_9] = \Pr \left[ \text{Game}_{\text{RPKE}_2, \mathcal{A}}^{\text{C-IND}}(1^{\lambda}) = 1 \mid b=1 \right]. $$

Combining all the bounds together, we arrive at the bound in the theorem statement. It remains to prove the following lemma to complete the proof.

**Lemma 11.** There exists an adversary $\mathcal{B}_2$ against the MLWE$_{q,k+1,n,\chi_r, (\chi_i)_{i \in [k+1]}}$ problem such that

$$ |\Pr[E_3] - \Pr[E_4]| \le 2 \cdot Q_{G_r} \cdot \sqrt{\text{Adv}_{\mathcal{B}_2}^{\text{MLWE}}(1^{\lambda}) + \frac{1}{|\mathcal{M}|}}. $$

*Proof.* We invoke the O2H lemma (cf. Lemma 4) with oracles $G_r, F: \mathcal{M} \to \mathcal{R}_q$ as defined in Game4, where
<figure><img src="image_9.png" /><figcaption>Figure 12. Game<sub>3</sub> to Game<sub>5</sub>, and Game<sub>7</sub> and Game<sub>8</sub> for the proof of C-IND security, and tools to invoke O<sub>2H</sub> lemma.</figcaption></figure>

S := { µ* } ⊂ M for a randomly chosen µ*. We define the random variable w as (pk*, G, Δ), where Δ := G<sub>r</sub>(µ*). This is without loss of generality as z can be any bit string that can depend arbitrary on G<sub>r</sub> and S. We then define the oracle-calling algorithms A<sub>O<sub>2H</sub></sub> and B<sub>O<sub>2H</sub></sub> as in Fig. 12. If H := G<sub>r</sub> (resp. H := F), then A<sub>O<sub>2H</sub>(·)</sub>(w) is identical to Game<sub>3</sub> (resp. Game<sub>4</sub>). Then, using Lemma 4, we have

$$
|\Pr[E_3] - \Pr[E_4]| \\
\le 2 \cdot Q_{G_r} \cdot \sqrt{\Pr_{G_r, F, S, w} \left[ \mathcal{T} \stackrel{\$}{\leftarrow} \mathcal{B}_{O_{2H}}^{F(\cdot)}(w) : S \cap \mathcal{T} \ne \emptyset \right]}.
$$

It remains to upper bound probability inside the square
root, which we denote by *p*. We only provide a proof
sketch as this follows from an almost identical argument

to the remaining game transitions from Game₄ to Game₇
in the main proof. Namely, first observe that *p* remains the
same even if we modify $\mathcal{A}_{\text{O2H}}^{\text{F}(\cdot)}(w)$ to set $v_1^* := \Delta$ instead.
This is because from $\mathcal{A}$'s point of view, $\Delta := G_r(\mu^*)$
is information theoretically hidden, and $\Delta$ is distributed
uniformly over $R_q$. We further modify $\mathcal{A}_{\text{O2H}}^{\text{F}(\cdot)}(w)$ to set
$(\mathbf{u}^*, v_0^*) \stackrel{\$}{\leftarrow} R_q^k \times R_q$ instead. We can show that $p$ only
changes negligibly due to the MLWE$_{q,k+1,n,\chi_r}(\chi_i)_{i \in [k+1]}$
assumption. That is, if $\mathcal{B}_{\text{O2H}}^{\text{F}(\cdot)}(w)$ outputs a set $\mathcal{T}$ that includes
$\mu^*$ with different probabilities, then it can be used to solve
the MLWE$_{q,k+1,n,\chi_r}(\chi_i)_{i \in [k+1]}$ problem. Lastly, at this point,
since $\mu^*$ is information theoretically hidden from $\mathcal{A}$, the
probability that $\mathcal{B}_{\text{O2H}}^{\text{F}(\cdot)}(w)$ outputs $\mu^*$ is at most $\frac{1}{|\mathcal{M}|}$. This
concludes the proof.

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

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

## E.2. CR-IND Security of RPKE$_2$

*Proof.* We consider a sequence of hybrid games, where we denote $E_i$ as the event that $A$ outputs $b' = 1$ in Game$_i$. The simulator $S_r$ and some of the critical game transitions are depicted in Fig. 13.

**Game$_0$:** This corresponds to the CR-IND game where $b = 0$ is sampled. We thus have

$$ \mathrm{Pr}[E_0] = 1 - \mathrm{Pr} \left[ \mathrm{Game}_{\mathrm{RPKE}_{2,A}}^{\mathrm{CR-IND}} (1^{\lambda}) = 1 \mid b = 0 \right]. $$

**Game$_1$:** This is the same as Game$_0$ except that the game modifies how the random oracle $G$ is simulated. See Fig. 12 for the exact description. This argument is identical to the one we used to move to Game$_0$ to Game$_1$ in the proof of Thm. 9. Thus we have

$$ \mathrm{Pr}[E_0] = \mathrm{Pr}[E_1]. $$

**Game$_2$:** This is the same game as Game$_1$ except that the game replaces $\mathbf{b}_r$ by a uniform sample in $R_q^n$. Since the reinforcing secret key $s_r$ is not used elsewhere than to compute $\mathbf{b}_r$, this reduces to the MLWE problem. There exists an adversary $\mathcal{B}_1$ against the MLWE$_{q,k,n,\chi,\chi}$ problem such that

$$ |\mathrm{Pr}[E_1] - \mathrm{Pr}[E_2]| \le \mathrm{Adv}_{\mathcal{B}_1}^{\mathrm{MLWE}}(1^{\lambda}). $$

**Game$_3$:** This is the same as Game$_2$ except that the game modifies how the random oracle $G_r$ is simulated, and how the reinforcing public key $\bar{\mathbf{b}}_r$ is sampled. It first samples $\mathbf{b}_r^* \stackrel{\$}{\leftarrow} R_q^n$ and replaces the oracle $G_{\mathrm{Decomp}}$ by an efficient simulator $\mathrm{Sim}$ that simulates $G_{\mathrm{Decomp}}$ conditioned on $G_{\mathrm{Decomp}}(\bar{\mathbf{b}}_r) = \mathbf{b}_r^*$ where $\bar{\mathbf{b}}_r = \mathrm{Compress}_q(\mathbf{b}_r^*, d_r)$. Due to the complex output distribution of $G_{\mathrm{Decomp}}$ that furthermore depends on the input, defining such simulator is more challenging than in previous proofs where we could directly use 2Q-wise independent functions. We prove in Lemma 12 that we can define an efficient simulator for this conditioned oracle that succeeds with all but negligible probability $\mathrm{negl}(\lambda)$. We thus have

$$ |\mathrm{Pr}[E_2] - \mathrm{Pr}[E_3]| = \mathrm{negl}(\lambda). $$

**Game$_4$:** This is the same as Game$_3$ except that the game modifies how $v_0^*$ in the challenge ciphertext is computed. See Fig. 12 for the exact description. Notice that

$$ \begin{aligned} v_0^* - \mu' \cdot |q/2| &= \mathbf{r}^\top \cdot \mathbf{b} + z \\ &= \mathbf{r}^\top \cdot (\mathbf{A} \cdot \mathbf{s} + \mathbf{x}) + z \\ &= \mathbf{u}^* \cdot \mathbf{s} - \mathbf{z}^\top \cdot \mathbf{s} + \mathbf{r}^\top \cdot \mathbf{x} + z, \end{aligned} $$

where the first (resp. last) line is how $v_0^*$ is computed in Game$_3$ (resp. Game$_4$). Thus, we have

$$ \mathrm{Pr}[E_3] = \mathrm{Pr}[E_4]. $$

**Game$_5$:** This is the same as Game$_4$ except that the challenge ciphertext $\mathrm{ct}^*$ is sampled by the simulator $S_r$. See Fig. 12

for the exact description of the game and the simulator. We later show in Lemma 13 that there exists an adversary $\mathcal{B}$ against the hint-MLWE$_{q,k,n+1,\chi,\chi,\mathcal{F}}$ problem such that

$$ |\mathrm{Pr}[E_4] - \mathrm{Pr}[E_5]| \le \mathrm{Adv}_{\mathcal{B}}^{\mathrm{hint-MLWE}}(1^{\lambda}). $$

The remaining games is to undo our modification.

**Game$_6$:** This is the same as Game$_5$ except that the game computes the random oracle $G_{\mathrm{Decomp}}$ as in the real game. Using an identical argument to move from Game$_0$ to Game$_1$ and Game$_2$ to Game$_3$, we have

$$ |\mathrm{Pr}[E_6] - \mathrm{Pr}[E_7]| = \mathrm{negl}(\lambda). $$

**Game$_7$:** This is the same as Game$_6$ except that the game samples $\mathrm{rpk}^*$ as in the real game. See Fig. 12 for the exact description. Using an identical argument to move from Game$_1$ to Game$_2$, there exists an adversary $\mathcal{B}_3$ against the MLWE$_{q,k,n,\chi,\chi}$ problem such that

$$ |\mathrm{Pr}[E_6] - \mathrm{Pr}[E_7]| \le \mathrm{Adv}_{\mathcal{B}_3}^{\mathrm{MLWE}}(1^{\lambda}). $$

**Game$_8$:** This is the same as game Game$_7$ except that the game computes the random oracle $G$ as in the real game. Using an identical argument to move from Game$_0$ to Game$_1$, we have $\mathrm{Pr}[E_7] = \mathrm{Pr}[E_8]$. This corresponds to the C-IND game where $b = 1$ is sampled. We thus have

$$ \mathrm{Pr}[E_8] = \mathrm{Pr} \left[ \mathrm{Game}_{\mathrm{RPKE}_{2,A}}^{\mathrm{CR-IND}} (1^{\lambda}) = 1 \mid b = 1 \right]. $$

Combining all the bounds together, we arrive at the bound in the theorem statement. It remains to prove the following lemmas to complete the proof.

**Lemma 12.** Let $q = \mathrm{poly}(\lambda)$. For any (possibly unbounded) adversary $\mathcal{A}$ making at most $Q_{\mathrm{Decomp}}$ (quantum) oracle queries, there is an efficient simulator $\mathrm{Sim}$ that samples a function $G_{\mathrm{Decomp}}^*$ with polynomial-sized description such that:

$$ \left| \mathrm{Pr} \left[ \begin{array}{l} \mathbf{b}_r \stackrel{\$}{\leftarrow} R_q^n, \\ \mathbf{b}_r^* \stackrel{\$}{\leftarrow} R_q^n, \\ \mathbf{b}_r^* \stackrel{\$}{\leftarrow} R_q^n, \\ \mathbf{b}_r := \mathrm{Compress}_q(\mathbf{b}_r^*, d_{b_r}), \quad : \mathcal{A}^{\mathrm{Decomp}}(\bar{\mathbf{b}}_r, \mathbf{b}_r^*) \to 1 \end{array} \right] \right| = \mathrm{negl}(\lambda), $$

where the probability is also taken over the randomness of sampling the random oracle $G_{\mathrm{Decomp}}$.

*Proof.* Let us define the left (resp. right) hand probability in the lemma statement as $p_{\mathrm{real}}$ and $p_{\mathrm{sim}}$. Recall that given an input $\bar{\mathbf{b}}_r$, the random oracle $G_{\mathrm{Decomp}}$ samples a random element $\mathbf{b}_r^*$ in $R_q$ such that $\mathrm{Compress}_q(\mathbf{b}_r^*) = \bar{\mathbf{b}}_r$, i.e., $\mathbf{b}_r^* \stackrel{\$}{\leftarrow} \mathcal{U}(\{\mathbf{b}' \in R_q^n \mid \mathrm{Compress}_q(\mathbf{b}', d_{b_r}) = \bar{\mathbf{b}}_r\})$. When $\mathbf{b}_r \stackrel{\$}{\leftarrow} R_q^n$, we can see that $\mathbf{b}_r^*$ is also uniformly distributed over $R_q^n$ conditioned on $\bar{\mathbf{b}}_r = \mathrm{Compress}_q(\mathbf{b}_r^*, d_{b_r})$. Put differently, there is an inefficient simulator $\mathrm{Sim}'$ that first samples $\mathbf{b}_r^*$, computes $\bar{\mathbf{b}}_r = \mathrm{Compress}_q(\mathbf{b}_r^*, d_{b_r})$, and samples a random oracle $G'_{\mathrm{Decomp}}$ conditioned on $G'_{\mathrm{Decomp}}(\bar{\mathbf{b}}_r) = \mathbf{b}_r^*$ such that

$$ p_{\mathrm{real}} = \mathrm{Pr} \left[ \begin{array}{l} \mathbf{b}_r^* \stackrel{\$}{\leftarrow} R_q^n, \\ \mathbf{b}_r := \mathrm{Compress}_q(\mathbf{b}_r^*, d_{b_r}), \quad : \mathcal{A}^{\mathrm{Decomp}}(\bar{\mathbf{b}}_r, \mathbf{b}_r^*) \to 1 \end{array} \right], $$
### Game₁, Game₂

1: (seed<sub>A</sub>, A) $\stackrel{\$}{\leftarrow}$ {0, 1}<sup>256</sup> × R<sub>q</sub><sup>n×k</sup>

2: Sample 2Q<sub>G</sub>-wise independent function G s.t. G(seed<sub>A</sub>) = A

3: (pk<sup>*</sup>, sk<sup>*</sup>) $\stackrel{\$}{\leftarrow}$ KeyGen<sub>2</sub>(1<sup>λ</sup>)

4: parse(seed<sub>A</sub>, b) $\leftarrow$ pk<sup>*</sup>

5: A := G(seed<sub>A</sub>)

6: (s<sub>r</sub>, x<sub>r</sub>) $\stackrel{\$}{\leftarrow}$ χ<sup>k</sup> × χ<sup>n</sup> / If Game<sub>1</sub>

7: b<sub>r</sub> $\leftarrow$ A · s<sub>r</sub> + x<sub>r</sub> / If Game<sub>1</sub>

8: b<sub>r</sub> $\stackrel{\$}{\leftarrow}$ R<sub>q</sub><sup>n</sup> / If Game<sub>2</sub>

9: $\overline{b_r} := \text{Compress}_q(\mathbf{b_r}, d_{b_r})$

10: (rpk<sup>*</sup>, rsk<sup>*</sup>) $\leftarrow$ (b̄<sub>r</sub>, s<sub>r</sub>) / If Game<sub>1</sub>

11: rpk<sup>*</sup> $\leftarrow \overline{b_r}$ / If Game<sub>2</sub>

12: (μ', state) $\stackrel{\$}{\leftarrow}$ A<sup>G(·),G<sub>Decomp</sub>,G<sub>r(·)</sub></sup>(pk<sup>*</sup>, sk<sup>*</sup>, rpk<sup>*</sup>)

13: $\mu_r^* \stackrel{\$}{\leftarrow} U(M)$

14: $b_r^* \stackrel{\$}{\leftarrow} G_{\text{Decomp}}(\overline{b_r}, d_{b_r})$

15: (r, z, z<sub>r</sub>) $\stackrel{\$}{\leftarrow}$ χ<sub>r</sub><sup>n</sup> × χ<sub>r</sub><sup>k</sup> × χ<sub>z</sub> × χ<sub>r</sub>

16: $\Delta := G_r(\mu')$

17: $\mathbf{u}^* := \mathbf{r}^\top \cdot \mathbf{A} + \mathbf{z}^\top$

18: $v_0^* := \mathbf{r}^\top \cdot \mathbf{b} + z + \mu' \cdot [q/2]$

19: $v_1^* := \mathbf{r}^\top \cdot \mathbf{b}_r^* + z_r + \mu_r^* \cdot [q/2] + \Delta$

20: $\bar{u}^* := \text{Compress}_q(u, d_u)$

21: $\bar{v}_0^* := \text{Compress}_q(v_0, d_{v_0})$

22: $\bar{v}_1^* := \text{Compress}_q(v_1, d_{v_1})$

23: ct<sup>*</sup> := (u&#773;<sup>*</sup>, v&#773;<sub>0</sub><sup>*</sup>, v&#773;<sub>1</sub><sup>*</sup>)

24: $b' \stackrel{\$}{\leftarrow} A^{G(·),G_{\text{Decomp}},G_{r(·)}}(ct^*, \text{state})$

25: return b'

### Simulator S<sub>r</sub>(1<sup>λ</sup>, pk<sup>*</sup>, sk<sup>*</sup>, rpk<sup>*</sup>, μ')

1: parse(seed<sub>A</sub>, b) $\leftarrow$ pk<sup>*</sup>

2: parse(seed<sub>A</sub>, s) $\leftarrow$ sk<sup>*</sup>

3: A := G(seed<sub>A</sub>)

4: x := b - A · s

5: (r, z, z) $\stackrel{\$}{\leftarrow}$ χ<sub>r</sub><sup>n</sup> × χ<sub>r</sub><sup>k</sup> × χ<sub>z</sub>

6: $\mathbf{u}^* \stackrel{\$}{\leftarrow} R_q^k$

7: $v_0^* := \mathbf{u}^* \cdot \mathbf{s} - \mathbf{z}^\top \cdot \mathbf{s} + \mathbf{r}^\top \cdot \mathbf{x} + z + \mu' \cdot [q/2]$

8: $v_1^* \stackrel{\$}{\leftarrow} R_q$

9: $\bar{u}^* := \text{Compress}_q(u, d_u)$

10: $\bar{v}_0^* := \text{Compress}_q(v_0, d_{v_0})$

11: $\bar{v}_1^* := \text{Compress}_q(v_1, d_{v_1})$

12: ct<sup>*</sup> := (u&#773;<sup>*</sup>, v&#773;<sub>0</sub><sup>*</sup>, v&#773;<sub>1</sub><sup>*</sup>)

13: return ct<sup>*</sup>

### Game<sub>3</sub>, Game<sub>4</sub>

/ Identical up to Game<sub>2</sub>, Line 4

5: $\mathbf{b}_r^* \stackrel{\$}{\leftarrow} R_q^n$

6: $\overline{b_r} := \text{Compress}_q(\mathbf{b}_r^*, d_{b_r})$

7: $G_{\text{Decomp}} \stackrel{\$}{\leftarrow} \text{Sim}(\overline{b_r}, \mathbf{b}_r^*)$

8: A := G(seed<sub>A</sub>)

9: rpk<sup>*</sup> := $\overline{b_r}$

10: (μ', state) $\stackrel{\$}{\leftarrow}$ A<sup>G(·),G<sub>Decomp</sub>,G<sub>r(·)</sub></sup>(pk<sup>*</sup>, sk<sup>*</sup>, rpk<sup>*</sup>)

11: $\mu_r^* \stackrel{\$}{\leftarrow} U(M)$

12: (r, z, z<sub>r</sub>) $\stackrel{\$}{\leftarrow}$ χ<sub>r</sub><sup>n</sup> × χ<sub>r</sub><sup>k</sup> × χ<sub>z</sub> × χ<sub>r</sub>

13: $\Delta := G_r(\mu')$

14: $\mathbf{u}^* := \mathbf{r}^\top \cdot \mathbf{A} + \mathbf{z}^\top$

15: $v_0^* := \mathbf{r}^\top \cdot \mathbf{b} + z + \mu' \cdot [q/2]$ / If Game<sub>3</sub>

16: $v_0^* := \mathbf{u}^* \cdot \mathbf{s} - \mathbf{z}^\top \cdot \mathbf{s} + \mathbf{r}^\top \cdot \mathbf{x} + z + \mu' \cdot [q/2]$ / If Game<sub>4</sub>

17: $v_1^* := \mathbf{r}^\top \cdot \mathbf{b}_r^* + z_r + \mu_r^* \cdot [q/2] + \Delta$

/ Identical to Game<sub>2</sub>, Line 20 onward

### Game<sub>5</sub>

/ Identical up to Game<sub>4</sub>, Line 7

8: $\mathbf{b}_r^* \stackrel{\$}{\leftarrow} R_q^n$

9: $\overline{b_r} := \text{Compress}_q(\mathbf{b}_r^*, d_{b_r})$

10: $G_{\text{Decomp}} \stackrel{\$}{\leftarrow} \text{Sim}(\overline{b_r}, \mathbf{b}_r^*)$

11: A := G(seed<sub>A</sub>)

12: rpk<sup>*</sup> := $\overline{b_r}$

13: (μ', state) $\stackrel{\$}{\leftarrow}$ A<sup>G(·),G<sub>Decomp</sub>,G<sub>r(·)</sub></sup>(pk<sup>*</sup>, sk<sup>*</sup>, rpk<sup>*</sup>)

14: $ct^* \stackrel{\$}{\leftarrow} S_r(1^\lambda, pk^*, sk^*, rpk^*, \mu')$

15: $b' \stackrel{\$}{\leftarrow} A^{G(·),G_{\text{Decomp}},G_{r(·)}}(ct^*, \text{state})$

16: return b'

<caption>Figure 13. Game<sub>1</sub> to Game<sub>5</sub> for the proof of CR-IND security, and the description of simulator S<sub>r</sub>.</caption>
where denote the right hand probability as $p'$.

It remains to prove that we can replace $Sim'$ with an efficient algorithm sampling an efficiently computable $G'_{Decomp}$. The core idea relies on the observation that we can sample $G'_{Decomp}$ only with access to a uniform sampler over $\mathbb{Z}_q$, using rejection sampling. Indeed, we can equivalently (independently) sample the $i$-th coordinate of $\mathbf{b}_r^*$, denoted as $(\overline{\mathbf{b}_r})_i$, by sampling an element $c$ in $\mathbb{Z}_q$ and restarting as long as $\text{Compress}_q(c) \neq (\overline{\mathbf{b}_r})_i$.

As a first step, we consider a simulator $Sim''$ that samples a random oracle $G^{(\kappa)}_{Decomp}$ which samples its outputs with the above method, however limiting the number of attempts per coordinate to $\kappa$ - setting $\perp$ in case of failure. Furthermore, we consider that $G^{(\kappa)}_{Decomp}$ calls a random oracle on its input for each pair of coordinate and attempt number instead of a sampler (with an efficient description) over $\mathbb{Z}_q$. We implement the condition $G^{(\kappa)}_{Decomp}(\overline{\mathbf{b}_r}) = \mathbf{b}_r^*$ by conditioning the first random oracle for each coordinate $i$ to take as value $(\mathbf{b}_r^*)_i$ on $(\overline{\mathbf{b}_r})_i$. Then, since the depth of the circuit necessary to implement the rejection sampling with $\kappa$ attempts is poly($\lambda, \kappa$), we can aggregate the results of the individual quantum oracles into a final result with an efficient quantum circuit.

Let's now evaluate the probability that the sampling of $G^{(\kappa)}_{Decomp}$ succeeds on all possible inputs, as it then has the same distribution as $G_{Decomp}$. One coordinate sampling attempt succeeds with probability at least $1/q$. After $\kappa$ attempts, the probability of still failing for one coordinate is thus $(1 - 1/q)^\kappa \le e^{-\kappa/q}$. By union-bound the probability of failing on any of $d$ coordinates is bounded by $d \cdot e^{-\kappa/q}$.

Going further, since there are at most $2^{d \cdot d_{v_1}}$ possible inputs for this function, the probability of successful sampling of $G^{(\kappa)}_{Decomp}$ is at least $1 - 2^{d \cdot d_{v_1}} \cdot d \cdot e^{-\kappa/q}$ by union bound. We set $\kappa = \omega(q \cdot d \log d \cdot d_{v_1})$ so that this probability is overwhelming. In that case, we deduce

$$ \left| p' - \Pr \left[ \begin{array}{l} \mathbf{b}_r^* \stackrel{\$}{\leftarrow} R_q^n, \\ \overline{\mathbf{b}_r} := \text{Compress}_q(\mathbf{b}_r^*, d_{b_r}), : A^{G_{\text{Decomp}}}(\overline{\mathbf{b}_r}, \mathbf{b}_r^*) \to 1 \end{array} \right] \right| = \text{negl}(\lambda), $$

where denote the right hand probability as $p''$.

Lastly, we define $Sim(\overline{\mathbf{b}_r}, \mathbf{b}_r^*)$ which works as $Sim''$ but replaces each random oracle $H$ over $\mathbb{Z}_q$ (with a conditioning $H(c) = c'$ on one input) using a $2Q_{Decomp}$-wise independent function. This oracle is $G^*_{Decomp}$, which clearly has a polynomial-sized description. As in previous proofs, one way to sample such function would be to first sample a random $2Q_{Decomp}$-wise independent function $H'$ (which is possible since $q$ is a prime, cf. [81, Theorem 6.1]). Then simply define $H$ as computing $H'$ and adding $c' - H(c)$.

Using [81, Theorem 6.1], a $2Q_{Decomp}$-wise independent function is perfectly indistinguishable from a random oracle to an adversary making at most $2Q_{Decomp}$ oracle queries. Hence, we have

$$ p'' = p_{\text{sim}}. \quad \square $$

**Lemma 13.** There exists an adversary $\mathcal{B}$ against the hint-MLWE$_{q,k+1,n,\chi_r,\chi_z,\mathcal{F}}$ problem such that

$$ |\Pr[E_4] - \Pr[E_5]| \le \mathrm{Adv}_{\mathcal{B}}^{\mathrm{hint-MLWE}}(1^{\lambda}). $$

*Proof.* The proof follows immediately from the hint-MLWE problem. Assume $\mathcal{B}$ is given as challenge $(\mathbf{B}, \mathbf{d}, [\mathbf{x}^\top | -\mathbf{s}^\top | 0], h)$, where $\mathbf{B} \in R_q^{(k+1) \times n}$, $\mathbf{d} \in R_q^{k+1}$, and $(\mathbf{s}, \mathbf{x}) \stackrel{\$}{\leftarrow} \chi^k \times \chi^n$. $\mathcal{B}$ then sets the last row of $\mathbf{B}$ as $\mathbf{b}_r^{*\top}$ and the remaining matrix as $\mathbf{A}^\top$. Similarly, it sets the last entry of $\mathbf{d}$ as $v_1$ and the remaining column vector as $\mathbf{u}^*$. It then simulates the Game$_4$ challenger with the provided $\mathbf{A}$. When the adversary $\mathcal{A}$ outputs $(\mu', \text{state})$, $\mathcal{B}$ uses the provided $\mathbf{u}^*$, and computes $v_0^* := \mathbf{u}^* \cdot \mathbf{s} + h + \mu' \cdot [q/2]$ and $v_1^* := v_1 + \mu_r^* \cdot [q/2] + \Delta$. It then sets the challenge ciphertext $ct^*$ as in Game$_4$ and completes the simulation. $\mathcal{B}$ then outputs whatever output by $\mathcal{A}$ as its guess.

It can be checked that $\mathcal{B}$ perfectly simulates Game$_4$ (resp. Game$_5$) if $\mathbf{d}$ is a valid (resp. invalid). Thus, we arrive at the bound in the lemma statement. Concretely, if $\mathbf{d} = \begin{bmatrix} \mathbf{A}^\top \\ \mathbf{b}_r^{*\top} \end{bmatrix} \cdot \mathbf{r} + \begin{bmatrix} \mathbf{z} \\ z_r \end{bmatrix}$, then it can be checked that $h = -\mathbf{z}^\top \cdot \mathbf{s} + \mathbf{r}^\top \cdot \mathbf{x} + z$ as desired, where $z \stackrel{\$}{\leftarrow} \chi_z$. Note that the random oracle $G_r$ can be perfectly simulated by a $2Q_{G_r}$-wise independent function as we did for $G$. $\square$

### E.3. Statistical Disjointness of $\overline{\text{RPKE}}_2$

This is a simple consequence of the counting argument.

**Lemma 14.** Let $B > 0$ such that $\Pr[x \stackrel{\$}{\leftarrow} \chi_r : |x| > B] \le \text{negl}(\lambda)$, $c := \max\{n, k\}$, and $T := \max\{(2 \cdot B + 1)^2, (2 \cdot \lfloor \frac{q}{2^{d_{v_0}+1}} \rfloor + 1)^2\}$. Then, our $\overline{\text{RPKE}}_2$ is statistical disjoint assuming $(\frac{T^c}{q^k})^d = \text{negl}(\lambda)$.

*Proof.* Recall from Thm. 9 that the simulator $\mathcal{S}$ takes as input $(1^\lambda, \text{rpk}, \mu_r)$, samples random $(\mathbf{u}, v_0, v_1) \stackrel{\$}{\leftarrow} R_q^k \times R_q \times R_q$, and outputs a simulated ciphertext $ct$ as $(\overline{\mathbf{u}}, \overline{v_0}, \overline{v_1}) := (\text{Compress}_q(\mathbf{u}, d_{v_1}), \text{Compress}_q(v_0, d_{v_0}), \text{Compress}_q(v_1, d_{v_1}))$. In contrast, $\mathbf{u}$ in a valid ciphertext generated using $\overline{\text{RPKE}}_2$ is set as $\mathbf{u} = \mathbf{r}^\top \cdot \mathbf{A} + \mathbf{z}^\top$ for $(\mathbf{r}, \mathbf{z}) \stackrel{\$}{\leftarrow} \chi_r^n \times \chi_r^k$. If simulated and valid ciphertexts agree, then we must have

$$ \mathbf{u} + \delta_{\text{sim}} = \mathbf{A}^{\top} \cdot \mathbf{r} + \mathbf{z} + \delta_{\text{val}}, \quad (1) $$

where $\delta_{\text{sim}}$ and $\delta_{\text{val}}$ are offsets due to the decompres- sion, whose infinity norm is smaller than $\lfloor \frac{q}{2^{d_{v_0}+1}} \rfloor$ due to Lemma 1. Using a simple counting argument, $\mathbf{A}^\top \cdot \mathbf{r} + \mathbf{z} + \delta_{\text{val}} - \delta_{\text{sim}}$ can take at most $(2 \cdot B + 1)^{nd} \cdot (2 \cdot B + 1)^{kd} \cdot (2 \cdot \lfloor \frac{q}{2^{d_{v_0}+1}} \rfloor + 1)^{2kd} \le T^{cd}$. Assuming $(T/q)^{cd} = \text{negl}(\lambda)$, the probability that Eq. (1) holds for $\mathbf{u} \stackrel{\$}{\leftarrow} R_q^k$ is negligible as desired. $\square$
### E.4. (Half-)Correctness of $\overline{RPKE_2}$

Correctness can be shown as for ML-KEM [19], although we additionally need to take into account rounding terms for the reinforcing public key.

**Lemma 15.** *Our $\overline{RPKE_2}$ is half-correct assuming*

$$ \Pr [\|\mathbf{r}^\top \cdot \mathbf{x} - (\mathbf{z} + \boldsymbol{\delta})^\top \cdot \mathbf{s} + z + \delta_0\|_{\infty} \le q/4] = 1 - \mathrm{negl}(\lambda), $$

where the probability is taken over the randomness to sample $(\mathbf{s}, \mathbf{x}) \stackrel{\$}{\leftarrow} \chi^k \times \chi^n$, $(\mathbf{r}, \mathbf{z}) \stackrel{\$}{\leftarrow} \chi_r^n \times \chi_r^k$, $z \stackrel{\$}{\leftarrow} \chi_z$, and $(\boldsymbol{\delta}, \delta_0) \stackrel{\$}{\leftarrow} \chi_{\text{round}}^k(d_u) \times \chi_{\text{round}}(d_{v_0})$. Here, $\chi_{\text{round}}(c)$ is the distribution $\{\boldsymbol{\delta} = \text{Decompress}_q(\text{Compress}_q(\mathbf{b}, c), c) - \mathbf{b} \mid \mathbf{b} \leftarrow \mathcal{U}(R_q)\}$.

Moreover, it is correct further assuming the above holds where we replace $d_{v_0}$ by $d_{v_1} \stackrel{\$}{\leftarrow} \chi_{\text{round}}(d_{v_1})$, sample $\mathbf{z}$ from $\chi_r$, and add a term $\mathbf{r}^\top \cdot \delta_{\text{rpk}}$ where $\delta_{\text{rpk}}$ is sampled from $\{\mathbf{b}' - \mathbf{b} \mid \mathbf{b}, \mathbf{b}' \leftarrow \mathcal{U}(R_q) \wedge \text{Compress}_q(\mathbf{b}, d_{v_1}) = \text{Compress}_q(\mathbf{b}', d_{v_1})\}$.

*Proof.* We first provide the proof for half-correctness. Observe that we have

$$ \begin{aligned} v_0 - \mathbf{u}^{\top} \cdot \mathbf{s} &= \mathbf{r}^{\top} \cdot (\mathbf{A} \cdot \mathbf{s} + \mathbf{x}) + z + \mu \cdot [q/2] - (\mathbf{r} \cdot \mathbf{A}^{\top} + \mathbf{z}^{\top})^{\top} \cdot \mathbf{s} \\ &= \mathbf{r}^{\top} \cdot \mathbf{x} - \mathbf{z}^{\top} \cdot \mathbf{s} + z + \mu \cdot [q/2]. \end{aligned} $$

Due to rounding and Lemma 1, we further have $\hat{\mathbf{u}} := \text{Decompress}_q(\bar{\mathbf{u}}, d_u) = \mathbf{u} + \boldsymbol{\delta}$ and $\hat{v}_0 := \text{Decompress}_q(\bar{v}_0, d_{v_0}) = v_0 + \delta_0$, where $\boldsymbol{\delta}$ and $\delta_0$ are from the lemma statement. Plugging this into the above equation, it can be checked that $\text{RHalfDec}_2$ correctly decodes $\mu$ under the assumption made in the lemma.

The case for correctness follows straightforwardly considering also the reinforcing ciphertext, and the compression plus decompression of the reinforcing public key which add a term $\delta_{\text{rpk}}$ to $\mathbf{A} \cdot \mathbf{s} + \mathbf{x}$ in $v_1$ uniformly sampled from $\{\mathbf{b}' - \mathbf{b} \mid \text{Compress}_q(\mathbf{b}, d_{v_1}) = \text{Compress}_q(\mathbf{b}', d_{v_1})\}$. $\square$

## Appendix F. (Reinforced) KEM-based Noise Protocols

The Noise Protocol Framework [4] gives key exchange protocols based on Diffie-Hellman. WireGuard is based on the Noise “IKpsk2” pattern. There exists a preliminary specification [24] and prior academic work [13] which show how to convert DH-based Noise to KEM-based protocols. However, they did not show how to handle PSK in PQ Noise exchanges. Use of pre-shared keys triggers special handling of DH keys in classic Noise, which leaves the question on how to handle this for KEM-based approaches. Additionally, since [13] was published, Cremers et al. [2] have introduced the concept of binding properties for KEMs. By including public keys in the $C_i$ key derivation chain, the derived $K_i$ will bind them(achieving MAL-BIND-K-PK, [2, Sec. 4.8]). Otherwise, an adversary is able to set up two sessions that have the same shared key but disagree on identities (c.f. Sec. B). We also show how to extend Noise protocols with reinforced KEM.

**KEM Noise patterns.** In classic Noise, the e and s messages indicate the transmission of ephemeral and static public keys. To complete ephemeral key agreement, both parties include e tokens in their messages, after which they trigger the key agreement computation by the ee token. For KEM-based key exchange, we will instead need to compute and transmit a ciphertext message. As done in [13], [24], we replace the responder's e and ee tokens by a single ekem token, which will indicate the encapsulation, transmission, and decapsulation of the ciphertext and the inclusion of the shared secret into the key schedule. For static key exchange, there is a similar skem token. Fig. 14 shows an example.

<figure><img src="image_12.png" /><figcaption>Figure 14. Translation to PQ tokens in the IN pattern.</figcaption></figure>

**Key schedule computations.** Noise attempts to ensure that different sessions compute unique keys. In the description of the PSK extension to classic Noise, [4, Sec. 9.2] states that in PSK handshakes, all ephemeral public keys are included in the key schedule to ensure that PSK-derived session keys are randomized. This reasoning can be extended to the use of KEMs. In addition, without relying on binding properties of the KEM [2], we can not assume that any computed shared secrets are unique to a particular public key, which could lead to similar results as with shared PSK keys. So to ensure randomized keys and guard against misbinding, we require that e and s tokens are followed by MixKey operations which update the $C_i$ chaining key with the transmitted public key. Because sharing ciphertexts will immediately result in a (sufficiently random) shared secret being included in the chaining key, we do not include ciphertexts into the chaining key; ciphertexts are still included in computations of $H_i$ and thus authenticated. The key schedule computations are shown in Fig. 15. Note that both [13], [24] only update $H_i$ for the public keys and ciphertexts. There are other possible solutions to bind the $K_i$, such as deriving $K_i$ from both $C_i$ and $H_i$, but we leave exploring this to future work.

### F.1. Noise Patterns for KEM Key Exchange

Below, we give the updated descriptions of the operations to process the e, ekem, s, and skem tokens in Noise

<figure><img src="image_13.png" /><figcaption>Figure 15. PQ Noise key computations with KEM (left) and RKEM (right)</figcaption></figure>
handshake patterns. The precise details of the referenced functions are given in [4, §5]; these new rules update the definition of `WriteMessage` specifically. We encrypt ciphertexts encapsulated to static keys following [13]; we differ mainly in the calls to `MixKey()` for all public keys. **Symbol e:** Generate (epk, esk) $\stackrel{\$}{\leftarrow}$ KEM.KeyGen, transmit epk, and call `MixHash` (epk) and `MixKey` (epk) to update $H_i$ and $C_i$, respectively.

**Symbol ekem:** Generate (ct, ss) $\stackrel{\$}{\leftarrow}$ KEM.Encaps(epk) and transmit ct, or receive and decapsulate ct to get the shared secret ss $\leftarrow$ KEM.Decaps(esk, ct). Next, call `MixHash` (ct) to update $H_i$. Update the key schedule by calling `MixKey` (ss).

**Symbol s:** Encrypt and transmit static public key spk by calling `EncryptAndHash` (spk), which also updates $H_i$, and call `MixKey` (spk) to update $C_i$.

**Symbol skem:** Generate (ct, ss) $\stackrel{\$}{\leftarrow}$ KEM.Encaps(spk) and encrypt and transmit ct by calling `EncryptAndHash` (ct), or decrypt and decapsulate ct to get the shared secret ss $\leftarrow$ KEM.Decaps(ssk, ct). Note that this implicitly updates the hash transcript. Update the key schedule by calling `MixKey` (ss).

## F.2. Extending Post-Quantum Noise With Reinforced KEM

We define the following symbols for reinforced KEM: **Symbol r:** Generate (rpk, rsk) $\stackrel{\$}{\leftarrow}$ RKeyGen(spk), transmit rpk, and call `MixHash` (rpk) and `MixKey` (rpk) to update $H_i$ and $C_i$, respectively.

**Symbol rkem:** Call (ct, ss) $\stackrel{\$}{\leftarrow}$ KEM.Encaps(spk, rpk) and encrypt and transmit ct by calling `EncryptAndHash` (ct), or decrypt and decapsulate ct to get the shared secret ss $\leftarrow$ RDec(ssk, rsk, ct). Note that this implicitly updates the hash $H_i$. Update the key schedule by calling `MixKey` (ss).

We can define the `rkem` extension that transforms Noise patterns by the following rules. An example is shown in Fig. 16, and the key schedule computations in Fig. 15.

1) Any pair of `ekem`, `skem` or `skem`, `ekem` tokens can be replaced by a single `rkem` token.

2) If the previous replacement was made, the `e` token which should be present in the prior message can be replaced by a `r` token.

<table><caption>Figure 16. Translation to RKEM tokens in the pqIN pattern.</caption><tr><td>-> e, s</td><td>-> r, s</td></tr><tr><td><- ekem, skem</td><td><- rkem</td></tr></table>

# Contents

<table><tr><td>1</td><td>Introduction</td><td>1</td></tr><tr><td>1.1</td><td>Our Contribution</td><td>2</td></tr><tr><td>1.2</td><td>Related Work</td><td>3</td></tr><tr><td>1.3</td><td>Concurrent and Independent Work</td><td>3</td></tr></table>

<table><tr><td>2</td><td>Preliminaries</td><td>4</td></tr><tr><td>2.1</td><td>Notation</td><td>4</td></tr><tr><td>2.2</td><td>Lattices</td><td>4</td></tr><tr><td>2.3</td><td>Rounding</td><td>4</td></tr><tr><td>2.4</td><td>Quantum Tools</td><td>5</td></tr><tr><td>2.5</td><td>General Cryptographic Primitives</td><td>5</td></tr></table>

<table><tr><td>3</td><td>Reviewing PQ WireGuard by Hülsing et al.</td><td>6</td></tr><tr><td>3.1</td><td>Construction Overview</td><td>6</td></tr><tr><td>3.2</td><td>Security Properties</td><td>7</td></tr></table>

<table><tr><td>4</td><td>Computational Model for PQ WireGuard</td><td>8</td></tr><tr><td>4.1</td><td>Syntax and Execution Environment</td><td>8</td></tr><tr><td>4.2</td><td>Security Guarantees</td><td>8</td></tr></table>

<table><tr><td>5</td><td>PQ WireGuard from Reinforced KEM</td><td>10</td></tr><tr><td>5.1</td><td>Introducing Reinforced KEM</td><td>10</td></tr><tr><td>5.2</td><td>Building PQ WireGuard from RKEM</td><td>11</td></tr><tr><td>5.3</td><td>Security of Our RKEM-based PQ WireGuard</td><td>12</td></tr></table>

<table><tr><td>6</td><td>Generic Construction of Reinforced KEM</td><td>14</td></tr><tr><td>6.1</td><td>Reinforced Double-Message PKE</td><td>14</td></tr><tr><td>6.2</td><td>OW-Secure RPKE<sub>2</sub> to CCA Secure RKEM</td><td>15</td></tr></table>

<table><tr><td>7</td><td>Our Lattice-based Reinforced KEM: Rebar</td><td>17</td></tr><tr><td>7.1</td><td>OW-(R)CPA Security</td><td>17</td></tr><tr><td>7.2</td><td>Ciphertext (R-)Indistinguishability</td><td>18</td></tr><tr><td>7.3</td><td>Remaining Properties</td><td>18</td></tr></table>

<table><tr><td>8</td><td>Implementation and Experiments</td><td>18</td></tr><tr><td>8.1</td><td>Parameters and Instantiation of Our RKEM</td><td>18</td></tr><tr><td>8.2</td><td>Integration in WireGuard and Experiments</td><td>19</td></tr></table>

<table><tr><td>Appendix A:</td><td>Omitted Details of Security Model</td><td>23</td></tr><tr><td>A.1</td><td>Subtle Issue in Prior Computational Model</td><td>23</td></tr><tr><td>A.2</td><td>Key Indistinguishability</td><td>23</td></tr></table>

<table><tr><td>Appendix B:</td><td>UKS Attack Without Proper Key Schedule</td><td>24</td></tr><tr><td>Appendix C:</td><td>Key-Indistinguishability of Our PQ WireGuard</td><td>24</td></tr></table>

<table><tr><td>Appendix D:</td><td>Omitted Details of Generic Construction of RKEM</td><td>30</td></tr><tr><td>D.1</td><td>Proof of T Transform</td><td>30</td></tr><tr><td>D.2</td><td>Proof of U<sub>m</sub><sup>L</sup> Transform</td><td>30</td></tr></table>

<table><tr><td>Appendix E:</td><td>Omitted Details of Lattice-based RPKE<sub>2</sub></td><td>34</td></tr><tr><td>E.1</td><td>C-IND Security of RPKE<sub>2</sub></td><td>34</td></tr><tr><td>E.2</td><td>CR-IND Security of RPKE<sub>2</sub></td><td>36</td></tr><tr><td>E.3</td><td>Statistical Disjointness of RPKE<sub>2</sub></td><td>38</td></tr><tr><td>E.4</td><td>(Half-)Correctness of RPKE<sub>2</sub></td><td>39</td></tr></table>
Appendix F: (Reinforced) KEM-based Noise Protocols 39

F.1 Noise Patterns for KEM Key Exchange 39

F.2 Extending Post-Quantum Noise With
Reinforced KEM . . . . . . . . . . . 40