So every time the oSend oracle needs to generate a signature of knowledge ni of an element $d \leftarrow_S Z_p^*$ for group elements $g_1, g_2, D_1$, and $D_2$, such that $D_1 \leftarrow g_1^d$, and $D_2 \leftarrow g_2^d$, for the message $m$, it sets $L_0[(g_1, D_1, g_2, D_2, m, ni)] \leftarrow d$.

Following this, whenever they need to perform a verification on a valid signature of knowledge: SoKver($m, (g_1, D_1, g_2, D_2), ni$) = 1 in a query made by $\mathcal{A}$ with $L_0[(g_1, D_1, g_2, D_2, m, ni)] = \perp$, the oSend and the oRevealTD oracles run the key extractor $Ext_{\mathcal{S}}$ on $\mathcal{A}$ in order to extract the witness $d$ that was used to build the signature ni. Now we check if $D_1 \neq g_1^d$ or $D_2 \neq g_2^d$, in other words we check the validity of the witness. If one of these two inequality occurs, then the experiment aborts and returns a random bit, else it sets $L_0[(g_1, D_1, g_2, D_2, m, ni)] \leftarrow d$.

With this game hop, we point out the possibility of the extractor $Ext_{\mathcal{S}}$ failing when it is called (this happens with probability $\epsilon_{\mathcal{S}}$). Because oRevealTD requires (possibly) two calls and oSend one call to the extractor each time $\mathcal{A}$ queries them, we thus have the bound:

$$|\mathbb{P}(G_{11} \Rightarrow 1) - \mathbb{P}(G_{12} \Rightarrow 1)| \le (2q_{RTD} + q_S) \cdot \epsilon_{\mathcal{S}}(\lambda).$$

† **Game $G_{13}$:** Here we denote by $Ext_{\mathcal{NIPoK}}$ the knowledge extractor of the zero-knowledge proof of knowledge. This game is the same as the previous one, except that we begin by initializing an empty list $L'[\cdot] \leftarrow \emptyset$, and we now describe the modification in the oRegister oracle. When oRegister received a query $(\Lambda, \text{authority}, \{\perp\})$, it generates the associated keys $(\Lambda, \overline{SK}, \Lambda, \overline{PK})$ (corresponding to the type = authority, and remind that for an authority $\Lambda$, sets $\Lambda, \overline{SK}$ and $\Lambda, \overline{PK}$ contain only one element, respectively $\Lambda, \overline{SK}$ and $\Lambda, \overline{PK} = (\Lambda, \overline{pk}, \Lambda, \overline{ni})$, so to simplify notations, in what follows we write $\Lambda, \overline{SK}$ and $\Lambda, \overline{PK}$ instead of $\Lambda, \overline{SK}, \Lambda, \overline{PK}$, and then sets $L'[\Lambda, \overline{PK}] \leftarrow \Lambda, \overline{SK}$. In the case the adversary queries oRegister on $(\Lambda, \text{authority}, \overline{PK} \neq \perp)$, the oracle sets $\Lambda, \overline{PK} \leftarrow \overline{PK}$ and parses $\Lambda, \overline{PK}$ as $(\Lambda, \overline{pk}, \Lambda, \overline{ni})$. In order to complete the process, it checks if $\mathcal{NIPoK}((g, \Lambda, \overline{pk}), \Lambda, \overline{ni}) = 1$, and then it runs the extractor $Ext_{\mathcal{NIPoK}}$ on $\mathcal{A}$ to get the witness $\Lambda, \overline{SK}$ for $\Lambda, \overline{ni}$. (If not, the game aborts, but we may reasonably assume that the adversary well constructed the public key). If $g^{\Lambda, \overline{SK}} \neq \Lambda, \overline{pk}$, then the experiment aborts and returns a random bit, else it sets $L'[\Lambda, \overline{PK}] \leftarrow \Lambda, \overline{SK}$.

With this modification, we highlight the probability of the extractor $Ext_{\mathcal{NIPoK}}$ failing when it is called. Since oRegister requires possibly one call to $Ext_{\mathcal{NIPoK}}$ at each query (this happens with probability $\epsilon_{\mathcal{NIPoK}}(\lambda)$), this implies that we have:

$$|\mathbb{P}(G_{12} \Rightarrow 1) - \mathbb{P}(G_{13} \Rightarrow 1)| \le q_R \cdot \epsilon_{\mathcal{NIPoK}}(\lambda).$$

From the next games we need to split the analysis into four branches as depicted in FIGURES 24 and 25. In what follows, 0 (resp. 1, 2 and 3) is for two instances running the **Sign-sign** (resp. **Sign-static**, **Static-sign** and **Static-static**) version of the protocol in a session. We will now work with our guessed and tested instance, and its matching peer, and in general, with games $G_{14}$ and $G_{15}$ we randomize the lawful interception elements for the tested instance, in order to test their security and prevent the adversary from forging them, and we do the same in games $G_{16}$ and $G_{17}$ for the partner instance of the tested instance.

† **Game $G_{14}^0$:** In this game, we want to randomize the element $H$ for one of the two instances (running the **Sign-sign** version of the protocol) for the lawful interception process. To do so, this game is the same as $G_{13}$ except that during the session between $\pi_{\Xi}^e$ and $\pi_{\Xi'}^e$, assuming $\pi_{\Xi}^e$ is an Initiator instance, we pick at random, according to the uniform distribution on our group $G$, the element $H_{\Xi}$ (we will then do the same with $H_{\Xi'}$). Since it is random, we need to simulate the proof $ni_{\pi_{\Xi}^e}$ using the simulator $Sim_{\mathcal{S}}$ associated to the signature of knowledge. We now claim that, by reduction, we can build a distinguisher $B_1^0$ against the DDH problem for a DDH instance $(\Gamma_*, \Delta_*, \Sigma_*)$. We thus have:
<figure><img src="image_12.png" /><figcaption>FIGURE 24 – Continuation of the game schedule with separation into four branches. All these games are used to randomize the lawful interception elements.</figcaption></figure>

$$|\mathbb{P}(\mathbb{G}_{13} \implies 1) - \mathbb{P}(\mathbb{G}_{14}^0 \implies 1)| \le \mathrm{Adv}_{\mathcal{A}}^{\mathrm{DDH}}(\lambda).$$

‡ **Proof of the claim:** We proceed as in [9], easily adapting the notation and the context. Firstly we denote by $\mathbf{Sim}$ the simulators for the proofs of knowledge, and we now describe the construction of our distinguisher $\mathcal{B}_1^0$.

He begins by setting $\mathbf{pp} \leftarrow (\lambda, \mathcal{G}, p, g)$ and picking at random $b \leftarrow \{0, 1\}$. That's for the initialization. Now we describe how $\mathcal{B}_1^0$ runs $\mathcal{A}(\mathbf{pp})$.

It starts by simulating $\mathbb{G}_{13}$ to $\mathcal{A}$ as in the real game with certain exceptions regarding some oracles. We start with the $\mathbf{oRegister}$ oracle.

$\mathbf{q} \mapsto \mathbf{oRegister}(\mathcal{E}, \mathbf{type}, \overline{\mathbf{PK}})$: if the $\ell_1^{\mathrm{th}}$ (here to make it clear we state that $\Lambda_{\ell_1}^*$ is an Initiator's authority and $\Lambda_{\ell_2}^*$ is an Responder's authority) endpoint $\mathcal{E}$ registered has type $\neq$ authority or if the query is made with $\overline{\mathbf{PK}} \neq \{\perp\}$, then $\mathcal{B}_1^0$ aborts and returns a random bit. Otherwise, it sets $\Lambda_{\ell_1}^* \leftarrow \mathcal{U}$, $\Lambda_{\ell_1}^* . \mathbf{pk} \leftarrow \Gamma_*$, $\Lambda_{\ell_1}^* . \mathbf{ni} \leftarrow \mathbf{Sim}_{\mathbf{NIPoK}}(g, \Gamma_*)$; $\Lambda_{\ell_1}^* . \overline{\mathbf{PK}} \leftarrow \{(\Lambda_{\ell_1}^* . \mathbf{pk}, \Lambda_{\ell_1}^* . \mathbf{ni})\}$ and returns $\Lambda_{\ell_1}^* . \overline{\mathbf{PK}}$. Since this set, composing the public keys of an authority, contains only one element, in what follows, we simply denote by $\Lambda . \overline{\mathbf{PK}}$ this public key, which is of the form $(\Lambda . \mathbf{pk}, \Lambda . \mathbf{ni})$.

We now take care of the $\mathbf{oSend}$ oracle.

$\mathbf{q} \mapsto \mathbf{oSend}(\pi_w^k, m)$: We have to details different cases.

$\Rightarrow$ Firstly, we consider the case $w = \Xi'$ and $k = e'$. Algorithm $\mathcal{B}_1^0$ sets $y_* \leftarrow y$, and $Y_* \leftarrow g^y$ (in this case $(y, g^y)$ is generated faithfully as in the real protocol).
⇒ Secondly, we take a look at the case $w = \Xi$ and $k = e$ and we detail the modifications. Since $w$ is an Initiator, then it that case, $\mathcal{B}_1^0$ does not generate the exponent $x$ and sets $X \leftarrow \Delta_*$ and $X_* \leftarrow X$. Next it parses $\pi_{\Xi}^e.AID$ as $(\Lambda_o^I)_{o=1}^{n_I}$, sets $\text{SetAu} \leftarrow \{\Lambda_o^I\}_{o=1}^{n_I} \setminus \{\Lambda_{\ell_1}^*\}$ and sets:

$$H_I \leftarrow \prod_{\Lambda \in \text{SetAu}} \left( X_*^{L'[\Lambda.PK]} \right) \Sigma_* X_*^{y_*}.$$

He now needs to run $n_I \leftarrow \text{Sim}_{\text{SoK}}(m, (g, X_*, h_I, H_I, ))$, where $m = \pi_{\Xi}^e.AID \|ID_{\Xi}\|ID_{\Xi'} \|TH_2\|TH_3 \|TH_4$ in order to simulate the signature of knowledge. Finally it sets $h_* \leftarrow h_I$ and $H_* \leftarrow H_I$ (with $h_I$ faithfully generated).

We now work with the oRevealTD oracle. We modify it only if the method contained in sst (more precisely in MCS) is ID = 0.

⇒ oRevealTD(sst_I, ID_I, ID_R, Prox_I, (Λ_o^I)_{o=1}^{n_I}, ℓ): when receiving such a query, $\mathcal{B}_1^0$ parses sst_I as $\omega' \|X\|Y \|TH_2\|TH_3\|TH_4\|M_1\|m_2\|m_3\|H_I\|n_I\|ID_R\|n_r\|\text{val}\|\sigma_I$ (with $X = g^x$, $Y = g^y$), and sets $m \leftarrow (\Lambda_o^I)_{o=1}^{n_I} \|ID_I\|ID_R$, and sets $h_I \leftarrow \prod_{o=1}^{n_I} \Lambda_o^I \cdot \text{pk}$.

We know have to detail many cases.

⇒ If IdentifySession(sst_I, $\pi_{\Xi}^e$.sid) = 1 and $\Lambda_\ell^I = \Lambda_{\ell_1}^*$, then $\mathcal{B}_1^0$ aborts and returns a random bit. This is done to respect the key-freshness requirement.

⇒ If IdentifySession(sst_I, $\pi_{\Xi}^e$.sid) = 1 and $\Lambda_\ell^I \neq \Lambda_{\ell_1}^*$, then in this situation $\mathcal{B}_1^0$ knows the secret key of $\Lambda_\ell^I$. So in this case, it forges a trapdoor by computing $\Lambda_\ell^I \cdot \text{td}_1 \leftarrow X^{L'[\Lambda_\ell^I.PK]}$, $\Lambda_\ell^I \cdot \text{td}_0 \leftarrow \text{Sim}_{\text{td}}(g, \Lambda_\ell^I \cdot \text{pk}, X, \Lambda_\ell^I \cdot \text{td}_1)$ and $\Lambda_\ell^I \cdot \text{td} \leftarrow (\Lambda_\ell^I \cdot \text{td}_0, \Lambda_\ell^I \cdot \text{td}_1)$.

⇒ If IdentifySession(sst_I, $\pi_{\Xi}^e$.sid) $\neq 1$ and $\Lambda_\ell^I = \Lambda_{\ell_1}^*$, we automatically get IdentifySession(sst_I, $\pi_{\Xi'}^e$.sid) $\neq 1$, which implies that $X \|Y\|ID_I\|ID_R \neq X_* \|Y_*\|ID_{\Xi'}\|ID_{\Xi'}$. In this particular situation, $\mathcal{B}_1^0$ acts as in $\mathbb{G}_{13}$ except that:

≈ If $(\Lambda_o^I)_{o=1}^{n_I} \|ID_I\|ID_R \neq \pi_{\Xi}^e.AID \|ID_{\Xi}\|ID_{\Xi'}$, then $\mathcal{B}_1^0$ computes $\Lambda_{\ell_1}^* \cdot \text{td}_1 \leftarrow (\Lambda_{\ell_1}^* \cdot \text{pk})^{L[(g, X, h_I, Y, H_I, m, n_I)]}$, runs the simulator $\Lambda_{\ell_1}^* \cdot \text{td}_0 \leftarrow \text{Sim}_{\text{td}}(g, \Lambda_{\ell_1}^* \cdot \text{pk}, X, \Lambda_{\ell_1}^* \cdot \text{td}_1)$ and finally sets $\Lambda_{\ell_1}^* \cdot \text{td} \leftarrow (\Lambda_{\ell_1}^* \cdot \text{td}_0, \Lambda_{\ell_1}^* \cdot \text{td}_1)$. In this case $L[(g, X, h_I, Y, H_I, m, n_I)]$ is always defined because $m \neq \pi_{\Xi}^e.AID \|ID_{\Xi}\|ID_{\Xi'}$.

≈ If $(\Lambda_o^I)_{o=1}^{n_I} \|ID_I\|ID_R = \pi_{\Xi}^e.AID \|ID_{\Xi}\|ID_{\Xi'}$, but $X \neq X^*$, then we must have $Y = Y^*$ and $\mathcal{B}_1^0$ computes $\Lambda_{\ell_1}^* \cdot \text{td}_1 \leftarrow (\Lambda_{\ell_1}^* \cdot \text{pk})^{L[(g, X, h_I, Y, H_I, m, n_I)]}$, runs the simulator $\Lambda_{\ell_1}^* \cdot \text{td}_0 \leftarrow \text{Sim}_{\text{td}}(g, \Lambda_{\ell_1}^* \cdot \text{pk}, X, \Lambda_{\ell_1}^* \cdot \text{td}_1)$ and finally sets $\Lambda_{\ell_1}^* \cdot \text{td} \leftarrow (\Lambda_{\ell_1}^* \cdot \text{td}_0, \Lambda_{\ell_1}^* \cdot \text{td}_1)$. This is possible since $L[(g, X, h_I, Y, H_I, m, n_I)]$ is always defined because $X \neq X^*$.

≈ If $(\Lambda_o^I)_{o=1}^{n_I} \|ID_I\|ID_R = \pi_{\Xi}^e.AID \|ID_{\Xi}\|ID_{\Xi'}$, but $X = X^*$, then automatically $Y \neq Y^*$ which implies that:

$$h_I Y = \left( \prod_{o=1}^{n_I} \Lambda_o^I \cdot \text{pk} \right) Y \neq h_I^* Y^* = \left( \prod_{o=1}^{n_I} \Lambda_o^I \cdot \text{pk} \right) Y^*$$

and thus $h_I Y \neq h_I^* Y^*$. Then $\mathcal{B}_1^0$ computes $\Lambda_{\ell_1}^* \cdot \text{td}_1 \leftarrow (\Lambda_{\ell_1}^* \cdot \text{pk})^{L[(g, X, h_I, Y, H_I, m, n_I)]}$ and runs the simulator $\Lambda_{\ell_1}^* \cdot \text{td}_0 \leftarrow \text{Sim}_{\text{td}}(g, \Lambda_{\ell_1}^* \cdot \text{pk}, X, \Lambda_{\ell_1}^* \cdot \text{td}_1)$ and finally sets $\Lambda_{\ell_1}^* \cdot \text{td} \leftarrow (\Lambda_{\ell_1}^* \cdot \text{td}_0, \Lambda_{\ell_1}^* \cdot \text{td}_1)$. Here $L[(g, X, h_I, Y, H_I, m, n_I)]$ is always defined because $h_I Y \neq h_I^* Y^*$.

After having made all his queries to $\mathcal{B}_1^0$, the adversary $\mathcal{A}$ will return a bit $b_*$ as in the original experience. The distinguisher $\mathcal{B}_1^0$ now compares this bit to the one he samples earlier, and if $b_* = b$, he returns 1,
† **Game $G_{14}^1$:** In this game, we want to randomize elements $H$ and $H^1$ for one of the two instances (running the **Sign-static** version of the protocol) for the lawful interception process. To do so, this game is the same as $G_{13}$ except that during the session between $\pi_{\Xi}^e$ and $\pi_{\Xi'}^{e'}$, assuming $\pi_{\Xi}^e$ is an **Initiator** instance, we pick at random, according to the uniform distribution on our group $\mathbb{G}$, the elements $H_{\Xi}$ and $H_{\Xi'}^1$ (we will then do the same with $H_{\Xi'}$ and $H_{\Xi'}^1$). Since it is random, we need to simulate the proof $\text{ni}_{\pi_{\Xi}^e}$ using the simulator $\text{Sim}_{\text{Sok}}$ associated to the signature of knowledge. We now claim that, by reduction, we can build a distinguisher $B_1^1$ against the DDH problem (this is similar to the proof made in game $G_{14}^0$).
We thus have:

$$ |\mathbb{P}(G_{13} \implies 1) - \mathbb{P}(G_{14}^1 \implies 1)| \le \text{Adv}_{\mathcal{A}}^{\text{DDH}}(\lambda). $$

‡ **Proof of the claim:** We built a distinguisher $B_1^1$ in the same way as the previous reduction. But here we reduce by modifying two elements: $H_{\Xi}$ and $H_{\Xi'}^1$, that why we detail here the modifications. The initialization works exactly in the same way as for $B_1^0$. We also make the same modification for the **oRegister** and **oRevealTD** oracles, except for some notations. So we now explain the modification related to the **oSend** oracle.

$\qquad \mapsto \text{oSend}(\pi_w^k, m):$ We distinguish two cases.

$\quad \Rightarrow$ We begin by considering the case $w = \Xi'$ and $k = e'$. Algorithm $B_1^1$ sets $y_* \leftarrow y$, $Y_* \leftarrow g^y$, $r_* \leftarrow r$ and $Y_{1*} \leftarrow g^r$ (where $(y, g^y)$ and $(r, g^r)$ are generated faithfully according to the real protocol).

$\quad \Rightarrow$ Secondly, if $w = \Xi$ and $k = e$, we detail a little bit more the modifications. Since in this case $w$ is an **Initiator**, $B_1^1$ does not generate $x$ and sets $X = g^x \leftarrow \Delta_*$ and $X_* \leftarrow X$. Then it parses $\pi_{\Xi}^e$.AID as $(\Lambda_o^1)_{o=1}^{n_1}$, it sets $\text{SetAu} \leftarrow \{\Lambda_o^1\}_{o=1}^{n_1} \setminus \{\Lambda_{\ell_1}^*\}$ and sets:

$$ H_l \leftarrow \prod_{\Lambda \in \text{SetAu}} (X_*^{L'[\Lambda.PK]}) \Sigma_* X_*^{y_*}, H_l \leftarrow \prod_{\Lambda \in \text{SetAu}} (X_*^{L'[\Lambda.PK]}) \Sigma_* X_*^{r_*}, $$

and $(y, g^y)$, $(r, g^r)$ are normally generated.

It now runs $\text{ni}_l \leftarrow \text{Sim}_{\text{Sok}}(m, (g, X_*, h_l, H_l, H_l^1))$, where $m = \pi_{\Xi}^e$.AID $\|\|\text{ID}_{\Xi}\|\|\text{ID}_{\Xi'}$. Finally it sets $h_* \leftarrow h_l$, $H_* \leftarrow H_l$ and $H_*^1 \leftarrow H_l^1$ (with $h_l$ faithfully generated).

At the end of the simulation, $\mathcal{A}$ will return a bit $b_*$ as in the original experience. Algorithm $B_1^1$ compares this bit to the one he samples at the beginning, and then if $b_* = b$, then he returns 1, else it returns 0. Let's now explain how the reduction works and how $B_1^1$ distinguishes. Let $(\gamma_*, \delta_*) \in (\mathbb{Z}_p^*)^2$ such that $\Gamma_* = g^{\gamma_*}$ and $\Delta_* = g^{\delta_*}$. We set $\Lambda_{\ell_1}^* \cdot \text{SK} \leftarrow \gamma_*$.

In our situation $\Xi$ plays the role of the **Initiator** in $\pi_{\Xi}^e$. In this case $B_1^1$ sets $x_* \leftarrow \delta_*$. With these notations, we have $X_* = g^{x_*}$ and $\Lambda_{\ell_1}^* \cdot \text{pk} \leftarrow g^{\Lambda_{\ell_1}^*} \cdot \text{SK}$. If $\Sigma_* = g^{\gamma_*} \delta_*$, then $\Sigma_* = (\Lambda_{\ell_1}^* \cdot \text{pk})^{x_*}$ and:

$$ \begin{aligned} H_{l*} &= \prod_{\Lambda \in \text{SetAu}} (X_*^{L'[\Lambda.PK]}) \Sigma_* X_*^{y_*} = \prod_{\Lambda \in \text{SetAu}} (g^{L'[\Lambda.PK]} x_*) (\Lambda_{\ell_1}^* \cdot \text{pk})^{x_*} g^{x_* y_*} \\ &= \left( \prod_{o=1}^{n_l} (\Lambda_o^1 \cdot \text{pk}) Y \right)^{x_*} = (h_* Y)^{x_*} \end{aligned} $$

and
$$
\begin{align*}
H_{1*}^{1} &= \prod_{\Lambda \in \text{SetAu}} (X_{*}^{L'[\Lambda.PK]}) \Sigma_{*} X_{*}^{r_{*}} = \prod_{\Lambda \in \text{SetAu}} (g^{L'[\Lambda.PK]} x_{*}) (\Lambda_{\ell_1}^{*} \cdot \text{pk})^{x_{*}} g^{x_{*}r_{*}} \\
&= \left( \prod_{o=1}^{n_l} (\Lambda_o^l \cdot \text{pk}) Y_1 \right)^{x_{*}} = (h_* Y_1)^{x_{*}}
\end{align*}
$$

By construction, it is clear that in this case, $\mathbb{G}_{13}$ is perfectly simulated for $\mathcal{A}$ by $\mathcal{B}_1^1$. On the other hand, if $\Sigma_*$ is a random value, then $\mathbb{G}_{14}$ is perfectly simulated for $\mathcal{A}$ by $\mathcal{B}_1^1$. We then deduce that:

$$
\varphi \mapsto \mathbb{P}(\mathbb{G}_{13} \implies 1) = \mathbb{P}((\gamma_*, \delta_*) \leftarrow \mathbb{S}(\mathbb{Z}_p^*)^2, b \leftarrow \mathcal{B}_1^1(g^{\gamma_*}, g^{\delta_*}, g^{\gamma_*\delta_*}) : b = 1);
$$

$$
\varphi \mapsto \mathbb{P}(\mathbb{G}_{14} \implies 1) = \mathbb{P}((\gamma_*, \delta_*, \sigma_*) \leftarrow \mathbb{S}(\mathbb{Z}_p^*)^3, b \leftarrow \mathcal{B}_1^1(g^{\gamma_*}, g^{\delta_*}, g^{\sigma_*}) : b = 1).
$$

So here again, $\mathcal{B}_1^1$ is a well constructed distinguisher and we have:

$$
| \mathbb{P}(\mathbb{G}_{13} \implies 1) - \mathbb{P}(\mathbb{G}_{14} \implies 1) | \leq \mathrm{Adv}_{\mathcal{A}}^{\mathrm{DDH}}(\lambda)
$$

which concludes the proof of the claim.

† **Game $\mathbb{G}_{15}^1$:** This game is the same as the previous one except that here we assume that $\pi_{\Xi}^e$ is a Responder instance. We here first pick at random the element $H_{\Xi}$ and reduce against the DDH problem as in game $\mathbb{G}_{14}^0$. We thus have:

$$
| \mathbb{P}(\mathbb{G}_{14}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{15}^1 \Rightarrow 1) | \leq \text{Adv}_{\mathcal{A}}^{\text{DDH}}(\lambda).
$$

† **Game $\mathbb{G}_{15'}^1$:** This game is the same as the previous one, still assuming that $\pi_{\Xi}^e$ is a Responder instance. We here pick at random the second element $H_{\Xi}^1$. As in the previous game, we have:

$$
| \mathbb{P}(\mathbb{G}_{15}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{15'}^1 \Rightarrow 1) | \leq \text{Adv}_{\mathcal{A}}^{\text{DDH}}(\lambda).
$$

† **Game $\mathbb{G}_{16}^1$:** This game works in the same vein as $\mathbb{G}_{15}^1$, but this time we consider $\pi_{\Xi'}^{e'}$ as a Responder instance and we pick at random the element $H_{\Xi'}$ and simulate this associated proof. This leads us to the same result as in game $\mathbb{G}_{15}^1$:

$$
| \mathbb{P}(\mathbb{G}_{15'}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{16}^1 \Rightarrow 1) | \leq \text{Adv}_{\mathcal{A}}^{\text{DDH}}(\lambda).
$$

† **Game $\mathbb{G}_{16'}^1$:** This game works in the same vein as $\mathbb{G}_{15'}^1$, still considering $\pi_{\Xi'}^{e'}$ as a Responder instance. We pick at random the element $H_{\Xi'}^1$, and simulate the associated proof. This leads us to the same result:

$$
| \mathbb{P}(\mathbb{G}_{16}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{16'}^1 \Rightarrow 1) | \leq \text{Adv}_{\mathcal{A}}^{\text{DDH}}(\lambda).
$$

† **Game $\mathbb{G}_{17}^1$:** This game is the same as the previous one and works in the same vein as $\mathbb{G}_{14}^0$, i.e., this time we consider $\pi_{\Xi'}^{e'}$ as an Initiator instance and we pick at random elements $H_{\Xi'}$ and $H_{\Xi'}^1$. Following what we did in game $\mathbb{G}_{14}^1$, with a p.p.t. distinguisher $\mathcal{B}_4^1$ we obtain:
$$ \left| \mathbb{P}(G_{16'}^1 \Rightarrow 1) - \mathbb{P}(G_{17}^1 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_{14}^2$:** In this game, we want to randomize the element $H$ for one of the two instances (running the Static-sign version of the protocol) for the lawful interception process. Here again, this game is the same as $G_{13}$, and we assume that $\pi_{\Xi}^e$ is an Initiator instance. We pick at random, according to the uniform distribution on our group $G$, the element $H_{\Xi}$. Since it is random, we need to simulate the proof $n_i \pi_{\Xi}^e$ using the simulator $Sim_{SoK}$ associated to the signature of knowledge. By reduction, we can build a distinguisher $B_1^2$ against the DDH problem (this is similar to the proof made in game $G_{14}^0$). We thus have:

$$ \left| \mathbb{P}(G_{13} \Rightarrow 1) - \mathbb{P}(G_{14}^2 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_{14}^2$:** This game is the same as the previous one except that here we pick at random the element $H_{\Xi}^1$ (still assuming that $\pi_{\Xi}^e$ is an Initiator instance). We obtain the same bound as in game $G_{15}^1$:

$$ \left| \mathbb{P}(G_{14}^1 \Rightarrow 1) - \mathbb{P}(G_{14'}^1 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_{15}^2$:** This game is the same as the previous one and works in the same vein as game $G_{15}^0$. Here we assume that $\pi_{\Xi}^e$ is a Responder instance. We pick at random the two elements $H_{\Xi}$ and $H_{\Xi}^1$. Using arguments of game $G_{14}^1$, we obtain the following bound:

$$ \left| \mathbb{P}(G_{14'}^2 \Rightarrow 1) - \mathbb{P}(G_{15}^2 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_{16}^2$:** This game works in the same vein as $G_{15}^2$, but this time we consider $\pi_{\Xi'}^e$ as a Responder instance and we pick at random elements $H_{\Xi'}$ and $H_{\Xi'}^1$, and we simulate the associated proof. This leads us to the same result:

$$ \left| \mathbb{P}(G_{15}^2 \Rightarrow 1) - \mathbb{P}(G_{16}^2 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_{17}^2$:** This game works in the same vein as $G_{14}^2$. Here we consider $\pi_{\Xi'}^e$ as an Initiator instance, we pick at random the element $H_{\Xi'}$ and simulate the associated proof. Again we have:

$$ \left| \mathbb{P}(G_{16}^2 \Rightarrow 1) - \mathbb{P}(G_{17}^2 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_{17'}^2$:** This game is the same as the previous one and works in the same vein as $G_{14'}^2$, i.e., this time we consider $\pi_{\Xi'}^e$ as an Initiator instance and we pick at random the element $H_{\Xi'}^1$. This leads us to:

$$ \left| \mathbb{P}(G_{17}^2 \Rightarrow 1) - \mathbb{P}(G_{17'}^2 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_{14}^3$:** In this game, we want to randomize element $H$ $H^1$ for one of the two instances (running the Static-static version of the protocol) for the lawful interception process. Here again, this game is the same as $G_{13}$, and we assume that $\pi_{\Xi}^e$ is an Initiator instance. We pick at random, according to the uniform distribution on our group $G$, elements $H_{\Xi}$ and $H_{\Xi}^1$. Since it is random, we need to simulate the proof $n_i \pi_{\Xi}^e$ using the simulator $Sim_{SoK}$ associated to the signature of knowledge. By reduction, we can build a distinguisher $B_1^3$ against the DDH problem (this is similar to the proof made in game $G_{14}^0$). We thus have:
$$|\mathbb{P}(\mathbb{G}_{13} \implies 1) - \mathbb{P}(\mathbb{G}_{14}^3 \implies 1)| \le \text{Adv}_A^{\text{DDH}}(\lambda).$$

† **Game $\mathbb{G}_{14'}^3$**: This game is the same as the previous one except that here we pick at random the element $H_\Xi^2$ (still assuming that $\pi_\Xi^e$ is an Initiator instance). We obtain the same bound as in game $\mathbb{G}_{14}^2$ thanks to a reduction against the DDH problem. However, there are two slight modifications to do in the reduction. The first is in the oRegister oracle. When the endpoint $\Xi$ is registered, $B_{1'}^3$ embeds a part of its DDH challenge into static DIFFIE-HELLMAN key "$g^i$" of $\Xi$. The second one is due to the fact that $\Xi$ cannot be corrupt on its long-term key (otherwise $\mathcal{A}$ cannot win the game). So if $\mathcal{A}$ queries the oCorrupt oracle on $\Xi$ for this static DIFFIE-HELLMAN key, $B_{1'}^3$, aborts and returns a random bit. The rest of the reduction is identical, except for the notations. We thus have:

$$|\mathbb{P}(\mathbb{G}_{14}^3 \implies 1) - \mathbb{P}(\mathbb{G}_{14'}^3 \implies 1)| \le \text{Adv}_A^{\text{DDH}}(\lambda).$$

† **Game $\mathbb{G}_{15}^3$**: This game is the same as the previous one and work in the same vein as game $\mathbb{G}_{15}^0$. Here we assume that $\pi_\Xi^e$ is a Responder instance. We pick at random the two elements $H_\Xi$ and $H_\Xi^1$. Using arguments of game $\mathbb{G}_{15}^0$, we obtain the following bound:

$$|\mathbb{P}(\mathbb{G}_{14'}^3 \implies 1) - \mathbb{P}(\mathbb{G}_{15}^3 \implies 1)| \le \text{Adv}_A^{\text{DDH}}(\lambda).$$

† **Game $\mathbb{G}_{15'}^3$**: This game is the same as the previous one (we assume that $\pi_\Xi^e$ is a Responder instance) but this time we pick at random the element $H_\Xi^2$. Again (with the explanations of the game $\mathbb{G}_{14'}^3$) we obtain the following bound:

$$|\mathbb{P}(\mathbb{G}_{15}^3 \implies 1) - \mathbb{P}(\mathbb{G}_{15'}^3 \implies 1)| \le \text{Adv}_A^{\text{DDH}}(\lambda).$$

† **Game $\mathbb{G}_{16}^3$**: This game works in the same vein as $\mathbb{G}_{15'}^3$, but this time we consider $\pi_\Xi^{e'}$ as a Responder instance and we pick at random elements $H_{\Xi'}$ and $H_{\Xi'}^1$, and we simulate the associated proof. This leads us to:

$$|\mathbb{P}(\mathbb{G}_{15'}^3 \implies 1) - \mathbb{P}(\mathbb{G}_{16}^3 \implies 1)| \le \text{Adv}_A^{\text{DDH}}(\lambda).$$

† **Game $\mathbb{G}_{16'}^3$**: This game works in the same vein as $\mathbb{G}_{15'}^3$ (we continue considering $\pi_\Xi^{e'}$ as a Responder instance) but here we pick at random the element $H_{\Xi'}^2$, (and we simulate the associated proof). This leads us to:

$$|\mathbb{P}(\mathbb{G}_{16}^3 \implies 1) - \mathbb{P}(\mathbb{G}_{16'}^3 \implies 1)| \le \text{Adv}_A^{\text{DDH}}(\lambda).$$

† **Game $\mathbb{G}_{17}^3$**: This game works in the same vein as $\mathbb{G}_{16}^3$. Here we consider $\pi_\Xi^{e'}$ as an Initiator instance, we pick at random elements $H_{\Xi'}$ and $H_{\Xi'}^1$, and simulate the associated proof. Again we have:

$$|\mathbb{P}(\mathbb{G}_{16'}^3 \implies 1) - \mathbb{P}(\mathbb{G}_{17}^3 \implies 1)| \le \text{Adv}_A^{\text{DDH}}(\lambda).$$

† **Game $\mathbb{G}_{17'}^3$**: This game is the same as the previous one and works in the same vein as $\mathbb{G}_{14'}^3$, i.e., this time we consider $\pi_\Xi^{e'}$ as an Initiator instance and we pick at random the element $H_{\Xi'}^2$. This leads us to:
$$ |\mathbb{P}(G_{17}^3 \implies 1) - \mathbb{P}(G_{17'}^3 \implies 1)| \le \mathrm{Adv}_{\mathcal{A}}^{\mathrm{DDH}}(\lambda). $$

We are now close to the conclusion and we continue on our four branches. In games $G_{18}$ and $G_{19}$, and in games $G_{20}$ and $G_{21}$, we prevent the adversary from forging signatures, either on Initiator or Responder side. Next, in games $G_{22}$, $G_{23}$, $G_{24}$ and $G_{24}$ we test the key-derivation schedule security with element $g^{xy}$ (or $g^{iy}$ or $g^{rx}$) and ensure that the adversary is not able to predict the key(s), taking into account the fact that he obtains information from proxies if the latter are malicious. Finally with game $G_{26}$ we finish testing the security of the key-derivation schedule and we conclude the proof with the fresh and sound sessions, reducing the winning advantage of $\mathcal{A}$ to $\frac{1}{2}$.

<figure><img src="image_13.png" /><figcaption>FIGURE 25 – End of the game-schedule with the four branches and the conclusion. With games $G_{18}$, $G_{19}$, $G_{20}$ and $G_{21}$ we are flagging the false signatures $\sigma_2$ or $\sigma_3$ and aborting if one is received. Then with the following games, depending on the version, we prevent the adversary from attacking the key-derivation schedule. Finally we conclude with game $G_{26}$ by ensuring soundness and freshness, and reducing the adversary's advantage to $\frac{1}{2}$.</figcaption></figure>
† **Game $G_{18}^0$**: With next games, we want to prevent the adversary from forging signatures. This game is the same as the previous one, except that for each Responder E registered, we create an empty list and we store every message for which a signature $\sigma_2$ is generated by an honest instance $\pi_E^k$, $k \in \mathbb{N}$ (i.e., not corrupted and not adversary-controlled). We then set a bad flag bad$_{sign}$ to true when an (non-malicious) Initiator instance received a valid signature $\sigma_2$ from an uncorrupted (adversary-controlled) Responder's instance for a message which was not already generated by an honest Responder's instance. This change is internal to the game, and hence remains indistinguishable by $\mathcal{A}$. We thus have:

$$ \mathbb{P}(G_{17}^0 \Rightarrow 1) = \mathbb{P}(G_{18}^0 \Rightarrow 1). $$

† **Game $G_{19}^0$**: This game is the same as game $G_{18}^0$, but we abort when the bad flag bad$_{sign}$ is set to true. By the identical-until-bad lemma we hence have:

$$ |\mathbb{P}(G_{18}^0 \Rightarrow 1) - \mathbb{P}(G_{19}^0 \Rightarrow 1)| \le \mathbb{P}(F_3^0), $$

where $F_3^0$ is the event: the flag bad$_{sign}$ is set to true in game $G_{18}^0$.

To provide an upper bound for $\mathbb{P}(F_3^0)$, we use a hybrid argument, and claim that, by reduction, we can build p.p.t. adversaries against the EUF-CMA property of our digital signature scheme DS. We thus have:

$$ \mathbb{P}(F_3^0) \le q_{R_R} \cdot \mathrm{Adv}_{\mathrm{DS},\mathcal{A}}^{\mathrm{EUF-CMA}}(\lambda), $$

(where $q_{R_R}$ denotes the number of Responder registered (and similarly $q_{R_I}$ denotes the number of Initiator registered, and we have $q_{R_R} + q_{R_I} = q_R$)) and hence:

$$ |\mathbb{P}(G_{18}^0 \Rightarrow 1) - \mathbb{P}(G_{19}^0 \Rightarrow 1)| \le q_{R_R} \cdot \mathrm{Adv}_{\mathrm{DS},\mathcal{A}}^{\mathrm{EUF-CMA}}(\lambda). $$

‡ **Proof of the claim**: As announced, we prove this claim with an hybrid argument. For that we consider the sequence of hybrids games $\mathbb{H}_0, \cdots, \mathbb{H}_{q_{R_R}}$, where $q_{R_R}$ denotes the number of Responder registered (and similarly $q_{R_I}$ denotes the number of Initiator registered, and we have $q_{R_R} + q_{R_I} = q_R$). The game $\mathbb{H}_0$ is the game $G_{18}^0$. We assume, without loss of generality, that we number each Responder in order of registration (e.g., $R_1$ is the first Responder registered, etc. Then for all $\xi \in [1, q_{R_R}]$, game $\mathbb{H}_\xi$ is the same as game $\mathbb{H}_{\xi-1}$, except that we abort when the bad flag bad$_{sign}$ is raised for an $R_\xi$'s instance. By reduction, we build a p.p.t. algorithm $\mathcal{B}_{5,\xi}^0$ against the EUF-CMA property of DS, such that:

$$ |\mathbb{P}(\mathbb{H}_{\xi-1} \Rightarrow 1) - \mathbb{P}(\mathbb{H}_{\xi} \Rightarrow 1)| \le \mathrm{Adv}_{\mathrm{DS},\mathcal{A}}^{\mathrm{EUF-CMA}}(\lambda). $$

So to build $\mathcal{B}_{5,\xi}^0$, we first make the following assumption: there exists an adversary $\mathcal{A}$ that wins the game $\mathbb{H}_{\xi-1}$ with a non negligible probability, then denoted $\epsilon_{\mathcal{A}}(\lambda)$, by forging a signature $\sigma_2$ on one Responder $R_\xi$'s instance.

We now present the construction of $\mathcal{B}_{5,\xi}^0$. To begin with, the challenger generates a pair of public/private signature keys ($\widetilde{\mathrm{ssk}}, \widetilde{\mathrm{spk}}$) with the DS.Gen algorithm, and gives $\widetilde{\mathrm{spk}}$ to $\mathcal{B}_{5,\xi}^0$. Algorithm $\mathcal{B}_{5,\xi}^0$ wins if it sends to its challenger a message/signature $(m, \sigma)$ he did not generate, and such that DS.Verif($\widetilde{\mathrm{spk}}, m, \sigma$) = 1. So $\mathcal{B}_{5,\xi}^0$ will start by initializing an empty list $L_S \leftarrow \emptyset$, and then simulate $\mathbb{H}_{\xi-1}$ to $\mathcal{A}(\mathrm{pp})$ faithfully, except for certain points. Mainly we make two following modifications:

q- Firstly, when $\mathcal{A}$ registered Responder $R_\xi$, $\mathcal{B}_{5,\xi}^0$ sets $R_\xi$. $\overline{\mathrm{PK}} \ni R_\xi$. $\mathrm{spk} \leftarrow \widetilde{\mathrm{spk}}$.

q- In a second time, when calling the oSend oracle on input $(\pi_u^q, m)$, if $u = R_\xi$, $\mathcal{B}_{5,\xi}^0$ simulates oSend faithfully, but queries its Sign oracle (instead of the DS.Sign algorithm): $\sigma \leftarrow \mathrm{Sign}(m)$ and adds $(m, \sigma)$ to $L_S$.
Remark that $\mathcal{B}_{5,\xi}^0$ can still answer all the corruption queries, excepted for the Responder $R_\xi$. Thus if $\mathcal{A}$ asks $\mathcal{B}_{5,\xi}^0$ for a corruption query on the particular Responder, $\mathcal{B}_{5,\xi}^0$ stops the simulation.

Thus if $\mathcal{A}$ wins the game simulated by $\mathcal{B}_{5,\xi}^0$, having forged a signature under the conditions of $\mathbb{H}_{\xi-1}^0$ (i.e forging the signature $\sigma_2$ on one $R_\xi$'s instance), then $\mathcal{B}_{5,\xi}^0$ wins its game by construction (because $\mathcal{A}$ will have generated a pair $(m, \sigma) \notin L_S$) and breaks the EUF-CMA security of DS. So in this case we have $\text{Adv}_{\text{DS},\mathcal{B}_{5,\xi}^0}^{\text{EUF-CMA}}(\lambda) \ge \epsilon_\mathcal{A}(\lambda)$.

We thus built well our p.p.t. adversary $\mathcal{B}_{5,\xi}^0$. Repeating this on each hybrid game hop, we have :

$$ \begin{aligned} \left| \mathbb{P}(\mathbb{H}_0 \Rightarrow 1) - \mathbb{P}(\mathbb{H}_{q_{R_R}} \Rightarrow 1) \right| & \le \left| \mathbb{P}(\mathbb{H}_0 \Rightarrow 1) - \mathbb{P}(\mathbb{H}_1 \Rightarrow 1) \right| + \dots \\ & \quad + \left| \mathbb{P}(\mathbb{H}_{q_{R_R}-1} \Rightarrow 1) - \mathbb{P}(\mathbb{H}_{q_{R_R}} \Rightarrow 1) \right| \\ & \le q_{R_R} \cdot \text{Adv}_{\text{DS},\mathcal{A}}^{\text{EUF-CMA}}(\lambda) \end{aligned} $$

Observe that after game $\mathbb{H}_{q_{R_R}}$, $\mathcal{A}$ is no more able to forge a signature $\sigma_2$, as well as in game $\mathbb{G}_{19}^0$. We deduce that $\mathbb{P}(\mathbb{H}_{q_{R_R}} \Rightarrow 1) = \mathbb{P}(\mathbb{G}_{19}^0 \Rightarrow 1)$ and since $\mathbb{H}_0 = \mathbb{G}_{18}^0$, we thus obtain that :

$$ \mathbb{P}(F_3^0) \le q_{R_R} \cdot \text{Adv}_{\text{DS},\mathcal{A}}^{\text{EUF-CMA}}(\lambda) $$

as announced, and this concludes the proof of the claim.

With this game hop, we prevent the adversary from forging signatures $\sigma_2$. With the following two, we prevent the latter from forging signatures $\sigma_3$.

† **Game $\mathbb{G}_{20}^0$**: This game is the same as the previous one, except that for each Initiator $E'$ registered, we create an empty list and we store every message for which a signature $\sigma_3$ is generated by an honest instance $\pi_{E'}^k, k' \in \mathbb{N}$ (i.e., not corrupted and not adversary-controlled). We then set a bad flag **bad$_{sign'}$** to true when an honest Responder instance received a valid signature $\sigma_3$ from an uncorrupted (adversary-controlled) Initiator's instance for a message which was not already generated by an honest Initiator's instance.

This change is internal to the game, and hence remains indistinguishable by $\mathcal{A}$. We thus have:

$$ \mathbb{P}(\mathbb{G}_{20}^0 \Rightarrow 1) = \mathbb{P}(\mathbb{G}_{19}^0 \Rightarrow 1). $$

† **Game $\mathbb{G}_{21}^0$**: In the same vein as for game $\mathbb{G}_{19}^0$, this game is the same as game $\mathbb{G}_{20}^0$, but we abort when the bad flag **bad$_{sign'}$** is set to true. By the identical-until-bad lemma we hence have:

$$ \left| \mathbb{P}(\mathbb{G}_{20}^0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{21}^0 \Rightarrow 1) \right| \le \mathbb{P}(F_{3'}^0), $$

where $F_{3'}^0$ is the event: the flag **bad$_{sign'}$** is set to true in game $\mathbb{G}_{20}^0$.

Here again, to provide an upper bound for $\mathbb{P}(F_{3'}^0)$, we use an hybrid argument, and we claim that, by reduction, we can build p.p.t. adversaries against the EUF-CMA property of our digital signature scheme DS. This is done in a similar way as for $\mathbb{G}_{19}^0$ and we obtain:

$$ \mathbb{P}(F_{3'}^0) \le q_{R_R} \cdot \text{Adv}_{\text{DS},\mathcal{A}}^{\text{EUF-CMA}}(\lambda), $$

and hence:

$$ \left| \mathbb{P}(\mathbb{G}_{20}^0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{21}^0 \Rightarrow 1) \right| \le q_{R_R} \cdot \text{Adv}_{\text{DS},\mathcal{A}}^{\text{EUF-CMA}}(\lambda). $$
† **Game $G_{20}^1$**: This game is the same as game $G_{17}^1$ and works in the same vein as game $G_{20}^0$. For each Initiator E' registered, we create an empty list and we store every message for which a signature $\sigma_3$ is generated by an honest instance $\pi_E^k$, $k' \in \mathbb{N}$ (i.e., not corrupted and not adversary-controlled). We then set a bad flag bad$_{sign}$ to true when an honest Responder instance received a valid signature $\sigma_3$ from an uncorrupted (adversary-controlled) Initiator's instance for a message which was not already generated by an honest Initiator's instance.

This change is internal to the game, and hence remains indistinguishable by $\mathcal{A}$. We thus have:

$$ \mathbb{P}(G_{20}^1 = 1) = \mathbb{P}(G_{17}^1 = 1). $$

† **Game $G_{21}^1$**: This game is the same as the previous one and works in the same vein as game $G_{20}^1$, but we abort when the bad flag bad$_{sign}$ is set to true. By the identical-until-bad lemma we hence have:

$$ |\mathbb{P}(G_{20}^0 \Rightarrow 1) - \mathbb{P}(G_{21}^0 \Rightarrow 1)| \le \mathbb{P}(F_{3'}^1), $$

where $F_{3'}^1$ is the event: the flag bad$_{sign}$ is set to true in game $G_{20}^1$. With an hybrid argument, we obtain:

$$ \mathbb{P}(F_{3'}^1) \le q_{R_1} \cdot \text{Adv}_{\text{DS},\mathcal{A}}^{\text{EUF-CMA}}(\lambda), $$

and hence:

$$ |\mathbb{P}(G_{20}^1 \Rightarrow 1) - \mathbb{P}(G_{21}^1 \Rightarrow 1)| \le q_{R_1} \cdot \text{Adv}_{\text{DS},\mathcal{A}}^{\text{EUF-CMA}}(\lambda). $$

† **Game $G_{18}^2$**: This game is the same as game $G_{17'}^2$, except that for each Responder E registered, we create an empty list and we store every message for which a signature $\sigma_2$ is generated by an honest instance $\pi_E^k$, $k \in \mathbb{N}$ (i.e., not corrupted and not adversary-controlled). We then set a bad flag bad$_{sign}$ to true when an (non-malicious) Initiator instance received a valid signature $\sigma_2$ from an uncorrupted (adversary-controlled) Responder's instance for a message which was not already generated by an honest Responder's instance. This change is internal to the game, and hence remains indistinguishable by $\mathcal{A}$. We thus have:

$$ \mathbb{P}(G_{17'}^2 \Rightarrow 1) = \mathbb{P}(G_{18}^2 \Rightarrow 1). $$

† **Game $G_{19}^2$**: This game is the same as game $G_{18}^2$ and works in the same vein as game $G_{19}^0$: but we abort when the bad flag bad$_{sign}$ is set to true. We hence obtain:

$$ |\mathbb{P}(G_{18}^2 \Rightarrow 1) - \mathbb{P}(G_{19}^2 \Rightarrow 1)| \le q_{R_R} \cdot \text{Adv}_{\text{DS},\mathcal{A}}^{\text{EUF-CMA}}(\lambda). $$

† **Game $G_{22}^0$**: With the following games, we want the adversary from obtaining the session key through the key derivation schedule. So we begin with this game, which is the same as the previous one, but we add a failure condition: if the adversary, during the tested session, queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xy}$, then we abort and return a random bit. We then denote $F_4^0$ the event: $\mathcal{A}$ queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xy}$. If the event $F_4^0$ occurs, then challenger stops the simulation by returning a random bit. By the identical-until-bad lemma, we thus have:

$$ |\mathbb{P}(G_{21}^0 \Rightarrow 1) - \mathbb{P}(G_{22}^0 \Rightarrow 1)| \le \mathbb{P}(F_4^0). $$

Let's now provide a bound for $\mathbb{P}(F_4^0)$. For that we construct, by reduction, an adversary $B_6^0$ against the GDH problem. By the identical-until-bad lemma we hence claim that:

$$ \mathbb{P}(F_4^0) \le q_{RO_T} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda), $$

and finally:
$$ \left| \mathbb{P}(\mathbb{G}_{21}^0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{22}^0 \Rightarrow 1) \right| \le q_{\text{RO}_T} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda). $$

‡ **Proof of the claim:** This reduction is very similar to the reduction against the GDH problem proposed in [14]. We construct a p.p.t adversary $B_0^0$ against the GDH problem.

On input a GDH challenge $(g, A = g^a, B = g^b)$ and having access to a DDH oracle, returning 1 if a tuple $(g, g^a, g^b, g^c)$ is a DIFFIE-HELLMAN tuple, and 0 otherwise, our algorithm $B_0^0$ must return $g^{ab}$ in a polynomial time. To achieve this, $B_0^0$ is going to simulate $\mathbb{G}_{22}^0$ for $\mathcal{A}(\text{pp})$ faithfully, except for certain points.

Firstly, in all Initiator and Responder instances, $B_0^0$ embeds its challenge into the ephemeral sent DIFFIE-HELLMAN value as follows: it samples uniformly at random (for each instance) $k, k' \in \mathbb{Z}_p$ and sets $X \leftarrow Ag^k$ and $Y \leftarrow Bg^{k'}$ (with $A = g^a$ and $B = g^b$).

If the event $F_4^0$ occurs, then the value $Z$ queried to the $\text{SO}_T$ oracle will equal $g^{(a+k)(b+k')}$. To detect that, $B_0^0$ can compute $ZX^{-k'}B^{-k}$ which, if $F_4^0$ occurs, will equal $g^{ab}$ and test this equality by calling its DDH oracle on $(X, Y, ZX^{-k'}B^{-k})$, which will return 1 if $F_4^0$ occurs. So when the event happens $B_0^0$ wins.

To finally bound $\mathbb{P}(F_4^0)$, we remark that each time the $\text{SO}_T$ oracle is queried on input $Z$, the event $F_4^0$ can happen (on a single pair $(X, Y)$). This implies that possibly $q_{\text{RO}_T}$ DDH-oracle queries might be useful to detect the event. Hence the result:

$$ \mathbb{P}(F_4^0) \le q_{\text{RO}_T} \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda) $$

which concludes the proof of the claim.

† **Game $\mathbb{G}_{23}^0$:** This game is the same as the previous one, except that in this game we simulate the key generation of PRK$_{2e}$ for some chosen instances. Namely if our tested instance $\pi_{\Xi}$ is an honest Initiator's instance receiving $(g^y, c_2)$ from an honest Responder's instance (its partner $\pi_{\Xi'}$), and conversely if our tested instance is an honest Responder's instance receiving $m_1$ from an honest Initiator's instance (its partner), we simulate the generation of the key PRK$_{2e}$ thanks to a private oracle, denoted $\text{SO}_{\text{PRK}_{2e}}$, and working the same way as $\text{SO}_T$, but inaccessible to the adversary. Here we prove the security of $x$ and $y$ in the key-derivation schedule; in normal times, PRK$_{2e}$ is generated thanks to $\text{SO}_T$ and $\text{TH}_2$ (which is always authentic since the two instances get the same $m_1$) and $g^{xy}$.

One way to detect the modification is for the adversary to ask $\text{SO}_T$ on the correct DIFFIE-HELLMAN value $g^{xy}$. Thanks to the event $F_4^0$ the simulation is already stopped in this situation. Another way to detect it is to query $\text{SO}_P^{l_2}$, or $\text{SO}_P^{l_{key}}$, or $\text{SO}_P^{l_{iv}}$, or $\text{SO}_P^{l_{mac}}$, or $\text{SO}_P^{l_{hash}}$ on the correct value PRK$_{2e}$ which unpredictable at this stage. We denote $F_5^0$ the event: $\mathcal{A}$ queries $\text{SO}_P^{l_2}$, or $\text{SO}_P^{l_{key}}$, or $\text{SO}_P^{l_{iv}}$, or $\text{SO}_P^{l_{mac}}$, or $\text{SO}_P^{l_{hash}}$ on the correct value PRK$_{2e}$ for a session in which the latter is unpredictable. If $F_5^0$ happens, we stop the simulation and return a random bit. We can provide now an upper bound for $\mathbb{P}(F_5^0)$. For that we look at the probability of $\mathcal{A}$ querying one of these four oracles on the correct PRK$_{2e}$ in our tested session. Since for the adversary, PRK$_{2e}$ is here unpredictable, we obtain the following probability: $\frac{1}{2^{l_{hash}}}$ (since PRK$_{2e}$ has size $l_{hash}$) for the guess of PRK$_{2e}$. Now $\mathcal{A}$ can make at most $q_{\text{RO}_P^{l_2}}$ (resp. $q_{\text{RO}_P^{l_{key}}}$, $q_{\text{RO}_P^{l_{iv}}}$, and $q_{\text{RO}_P^{l_{mac}}}$) calls to $\text{SO}_P^{l_2}$ (resp. $\text{SO}_P^{l_{key}}$, $\text{SO}_P^{l_{iv}}$ and $\text{SO}_P^{l_{hash}}$), we thus have:

$$ \mathbb{P}(F_5^0) \le \frac{q_{\text{RO}_P^{l_2}} + q_{\text{RO}_P^{l_{key}}} + q_{\text{RO}_P^{l_{iv}}} + q_{\text{RO}_P^{l_{mac}}} + q_{\text{RO}_P^{l_{hash}}}}{2^{l_{hash}}}. $$

By the identical-until-bad lemma, we obtain:

$$ \left| \mathbb{P}(\mathbb{G}_{22}^0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{23}^0 \Rightarrow 1) \right| \le \mathbb{P}(F_5^0) $$

and thus:
$$ \left| \mathbb{P}(\mathbb{G}_{22}^0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{23}^0 \Rightarrow 1) \right| \le \frac{q_{\text{RO}_P^{l_2}} + q_{\text{RO}_P^{l_{\text{key}}}} + q_{\text{RO}_P^{l_{\text{iv}}}} + q_{\text{RO}_P^{l_{\text{mac}}}} + q_{\text{RO}_P^{l_{\text{hash}}}}}{2^{l_{\text{hash}}}}. $$

† **Game $\mathbb{G}_{24}^0$**: This game is the same as $\mathbb{G}_{23}^0$, but once again we simulate the generation of PRK$_{2e}$ for some other instances. Namely, if our tested instance is an honest Initiator's instance receiving a forged second message $(g^y, c_2)$ from an adversary controlled Responder's instance, but not corrupted on its long term signing key with the oCorrupt oracle, we simulate the generation of PRK$_{2e}$ thanks to the private oracle $SO_{\text{PRK}_{2e}}$, still inaccessible to the adversary.

Now let's see what happens in this situation. Firstly, we assume that $g^y$ is forged. In this case $TH_2$ is different from the value obtained by an honest Responder instance (i.e., an Responder instance simulated by the challenger) thanks to the absence of collisions because we computed it using $SO_H$ (according to game $\mathbb{G}_7$). Secondly, if $g^y$ is not forged, then the symmetric key $sk_2$ is authentic. We deduce that the ciphertext $c_2$ is forged, since the XOR-ing encryption scheme used here verifies the injective property when the key is fixed. In both cases, $m_2$ and then $TH_3$ are different from the expected values obtained with an honest Responder's instance (as before, but this time in the second run of the Responder) (note $TH_2$ and $TH_3$ are common values for Initiator and Responder instances, even if the tuple is forged; and we use these values to compute PRK$_{2e}$ or in a calculation involving PRK$_{2e}$).

As for the previous game, the use of the private oracle $SO_{\text{PRK}_{2e}}$ can possibly be detected by the adversary in two ways: he queried $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xy}$. But in this situation, thanks to the event $F_4^0$, the simulation is already stopped. Or as is the previous game by picking at random a value PRK$_{2e*}$ from $\{0, 1\}^{l_{\text{hash}}}$ and querying $SO_P$ on this value. In this situation, thanks to the event $F_5^0$, we already stopped the simulation. We hence have:

$$ \mathbb{P}(\mathbb{G}_{24}^0 \Rightarrow 1) = \mathbb{P}(\mathbb{G}_{23}^0 \Rightarrow 1). $$

† **Game $\mathbb{G}_{25}^0$**: This game is the same as the previous one, and here again we simulate the generation of the key PRK$_{2e}$ thanks to the private oracle $SO_{\text{PRK}_{2e}}$ for some instances. Namely, if our tested instance in an honest Responder's instance receiving a forged message $m_1$ from an adversary controlled Initiator's instance, but not corrupted with oCorrupt on the long term signing key.

Since $m_1$ is forged, thanks to the absence of collisions in $SO_H$, elements $TH_2$ and $TH_3$ are different from the values computed by in an honest Initiator's instance (i.e., simulated by the challenger).

Again, $\mathcal{A}$ detects the use of $SO_{\text{PRK}_{2e}}$: if he queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xy}$, and here again, thanks to the event $F_4^0$, the simulation is already stopped. Or if he queried $SO_P$ on a random value from $\{0, 1\}^{l_{\text{hash}}}$, in which case the simulation is also already stopped. We deduce that:

$$ \mathbb{P}(\mathbb{G}_{25}^0 \Rightarrow 1) = \mathbb{P}(\mathbb{G}_{24}^0 \Rightarrow 1). $$

† **Game $\mathbb{G}_{26}^0$**: This game is the same as $\mathbb{G}_{25}^0$, but here we finally focus on the generation of PRK$_{out}$ if the tested instance is fresh. Indeed if the tested instance does not respect the Fresh property, then the adversary cannot win the game with a non-zero advantage. So in this situation we generate PRK$_{out}$ thanks to a private oracle $SO_{\text{PRK}_{\text{out}}}$ for these sessions. Note that the game $\mathbb{G}_8$ ensures the points related to the authorities for all the sessions in the fresh definition. The rest of the definition means that no call to the oCorrupt oracle (on the long term signing key) occurred before each party accepted. We can retranslate this by saying that the Initiator's instance is not corrupted before receiving the second message and the Responder's instance is not corrupted before receiving the third message. By chance, the three previous games have been constructed to ensure that in this case, the key PRK$_{2e}$ is generated using the private oracle $SO_{\text{PRK}_{2e}}$, and so unpredictable by the adversary.

Since PRK$_{out}$ is computed using PRK$_{2e}$, the adversary may detect the use of the private oracle $SO_{\text{PRK}_{\text{out}}}$ (in one of the two instances involved in the session) if he asked the $SO_P^{l_{\text{hash}}}$ oracle on the (public but
unpredictable) value PRK$_{2e}$. Let's denote $F_6^0$ this event. If $F_6^0$ occurs we stop the simulation by returning a random bit. By the identical-until-bad lemma we obtain:

$$|\mathbb{P}(\mathbb{G}_{25}^0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{26}^0 \Rightarrow 1)| \le \mathbb{P}(F_6^0).$$

We now need to provide a bound for $\mathbb{P}(F_6^0)$. Formally we look at the probability of the adversary querying $SO_P^{l_{hash}}$ on the correct value PRK$_{2e}$ in one session. Since PRK$_{2e}$ is unpredictable, the probability we are looking for is hence $\frac{1}{2^{l_{hash}}}$ (because the digests output by the oracle $SO_{PRK_{2e}}$ are of size $l_{hash}$). Because $\mathcal{A}$ makes at most $q_{RO_P^{l_{hash}}}$ queries to $SO_P^{l_{hash}}$, we thus have:

$$\mathbb{P}(F_6^0) \le \frac{q_{RO_P^{l_{hash}}}}{2^{l_{hash}}},$$

and hence:

$$|\mathbb{P}(\mathbb{G}_{25}^0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{26}^0 \Rightarrow 1)| \le \frac{q_{RO_P^{l_{hash}}}}{2^{l_{hash}}}. $$

† **Game $\mathbb{G}_{22}^1$**: This game is the same as the previous one (game $\mathbb{G}_{21}^1$) and works in the same vein as game $\mathbb{G}_{22}^0$ by adding a failure condition: if the adversary, during the tested session, queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xr}$, then we abort and return a random bit. We then denote $F_4^1$ the event: $\mathcal{A}$ queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xr}$ (with $g^x$ the public DIFFIE-HELLMAN element of a challenger-controlled Initiator instance and $r$ a (adversary-controlled, not corrupted) Responder instance long-term secret key). If the event $F_4^1$ occurs, then challenger stops the simulation by returning a random bit. By the identical-until-bad lemma, we thus have:

$$|\mathbb{P}(\mathbb{G}_{21}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{22}^1 \Rightarrow 1)| \le \mathbb{P}(F_4^1).$$

Let's now provide a bound for $\mathbb{P}(F_4^1)$. For that we construct, by reduction, an adversary $\mathcal{B}_6^1$ against the GDH problem. By the identical-until-bad lemma we hence claim that:

$$\mathbb{P}(F_4^1) \le q_{NS} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda),$$

and finally:

$$|\mathbb{P}(\mathbb{G}_{21}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{22}^1 \Rightarrow 1)| \le q_{NS} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda).$$

‡ **Proof of the claim**: We want to provide an upper bound for $\mathbb{P}(F_4^1)$. Nothing more simple, by reduction we built an adversary $\mathcal{B}_6^1$ against the GDH problem.

On input a GDH challenge $(g, A = g^a, B = g^b)$ and having access to a DDH oracle, returning 1 if a tuple $(g, g^a, g^b, g^c)$ is a DIFFIE-HELLMAN tuple, and 0 otherwise, our algorithm must returns $g^{ab}$ in a polynomial time. For that, $\mathcal{B}_6^1$ simulates $\mathbb{G}_{22}^1$ for $\mathcal{A}(pp)$ as follows, mainly faithfully, but with some modifications. Firstly, in every honest Initiator instances, $\mathcal{B}_6^1$ embeds its challenge into the shared DIFFIE-HELLMAN value: it picks at random $k \in \mathbb{Z}_p$ (for each instance) and sets $X \leftarrow Ag^k$. Then he samples $k' \leftarrow \mathbb{Z}_p$ for each Responder and sets $R \leftarrow Bg^{k'}$. Even if $b$ (from $g^b$) remains unknown by $\mathcal{B}_6^1$, the latter can continue the simulation by querying the $SO_T$ oracle on input $(X, R)$.

If $F_4^1$ occurs on that particular Responder instance, then the value $Z$ queried to the $SO_T$ oracle will equal $g^{(a+k)b}$. To detect that, $\mathcal{B}_6^1$ can compute $ZR^{-k}X^{-k'}$, which if $F_4^1$ occurs will equal $g^{ab}g^{kb}g^{-kb}g^{ak'}g^{-ak'} = g^{ab}$, and test this equality with its DDH oracle on input $(X, R, ZR^{-k}X^{-k'})$, which will return 1 since $F_4^1$ occurs. So when the event happens, $\mathcal{B}_6^1$ wins.
If $F_4^1$ occurs on another Responder instance, then $\mathcal{B}_6^1$ stops the simulation.

For each Responder instance involved in a session, the event $F_4^1$ can be detected. Thus we have:

$$ \mathbb{P}(F_4^1) \le q_{\text{NS}} \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda) $$

and this concludes the proof of the claim.

† **Game $\mathbb{G}_{23}^1$**: This game is the same as the previous one ($\mathbb{G}_{22}^1$) and we work in the same vein as $\mathbb{G}_{23}^0$. Once again, if our tested instance $\pi_{\Xi}^e$ is an honest Initiator's instance receiving $(g^y, c_2)$ from an adversary controlled Responder's instance (its partner $\pi_{\Xi'}^{e'}$), but which is not corrupt (note that at this point the LI elements are chosen at random, thus they cannot be forged), the challenger simulates PRK$_{3e2m}$ for the Initiator instance with a private oracle $SO_{PRK_{3e2m}}$. As before, this key is unpredictable by the adversary. Note that here we prove the security of $r$ and $g^{rx}$ in the key-derivation schedule; in normal times, PRK$_{3e2m}$ is generated with $SO_T$, salt$_{3e2m}$ and $g^{rx}$. One way to detect the modification is for the adversary to ask $SO_T$ on the correct DIFFIE-HELLMAN value $g^{rx}$. Thanks to the event $F_4^1$ the simulation is already stopped in this situation. Another way to detect it is to query $SO_P^{l_{hash}}$, or $SO_P^{l_{key}}$, or $SO_P^{l_{iv}}$, or $SO_P^{l_{mac}}$ on the correct value PRK$_{3e2m}$ which unpredictable at this stage. We denote $F_5^1$ the event: $\mathcal{A}$ queries $SO_P^{l_{hash}}$, or $SO_P^{l_{key}}$, or $SO_P^{l_{iv}}$, or $SO_P^{l_{mac}}$ on the correct value PRK$_{3e2m}$ for a session in which the latter is unpredictable. If $F_5^1$ happens, we stop the simulation and return a random bit. We can provide now an upper bound for $\mathbb{P}(F_5^1)$. For that we look at the probability of $\mathcal{A}$ querying one of these four oracles on the correct PRK$_{3e2m}$ in our tested session. Since for the adversary, PRK$_{3e2m}$ is here unpredictable, we obtain the following probability: $\frac{1}{2^{l_{hash}}}$ (since PRK$_{3e2m}$ has size $l_{hash}$) for the guess of PRK$_{3e2m}$. Now $\mathcal{A}$ can make at most $q_{RO_P^{l_{hash}}}$ (resp. $q_{RO_P^{l_{key}}}$, $q_{RO_P^{l_{iv}}}$, and $q_{RO_P^{l_{mac}}}$) calls to $SO_P^{l_{hash}}$ (resp. $SO_P^{l_{key}}$, $SO_P^{l_{iv}}$ and $SO_P^{l_{hash}}$), we thus have:

$$ \mathbb{P}(F_5^1) \le \frac{q_{RO_P^{l_{hash}}} + q_{RO_P^{l_{key}}} + q_{RO_P^{l_{iv}}} + q_{RO_P^{l_{mac}}}}{2^{l_{hash}}}. $$

By the identical-until-bad lemma, we obtain:

$$ |\mathbb{P}(\mathbb{G}_{22}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{23}^1 \Rightarrow 1)| \le \mathbb{P}(F_5^1) $$

and thus:

$$ |\mathbb{P}(\mathbb{G}_{22}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{23}^1 \Rightarrow 1)| \le \frac{q_{\text{RO}_P^{l_{\text{hash}}}} + q_{\text{RO}_P^{l_{\text{key}}}} + q_{\text{RO}_P^{l_{\text{iv}}}} + q_{\text{RO}_P^{l_{\text{mac}}}}}{2^{l_{\text{hash}}}}. $$

† **Game $\mathbb{G}_{24}^1$**: This game is the same as $\mathbb{G}_{23}^1$, except that we keep modifying the key generation for some instances. This time, if our tested instance is an honest Responder instance receiving a forged message $m_1$ from an adversary-controlled Initiator's instance, we simulate PRK$_{3e2m}$ (for the Responder's instance) thanks to a private oracle $SO_{PRK_{3e2m}}$. In normal situations, PRK$_{3e2m}$ is generated with $SO_T$, salt$_{3e2m}$ and $g^{rx}$).

We now make the following observation: because $m_1$ is forged, elements $TH_2, TH_3$ and salt$_{3e2m}$ are different from those expected by an honest Initiator instance, thanks to the absence of collisions (since game $\mathbb{G}_7$). In this situation, the adversary detect the use of the private oracle, if he queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{rx}$ - and thanks to the event $F_4^1$, the simulation is already stopped - or if $\mathcal{A}$ queries $SO_P$ on the correct value PRK$_{3e2m}$ - and thanks to the event $F_5^1$, the simulation is already stopped. So this change becomes indistinguishable by the adversary. So we have:

$$ |\mathbb{P}(\mathbb{G}_{23}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{24}^1 \Rightarrow 1)|. $$
† **Game $\mathbb{G}_{25}^1$**: This game is the same as game $\mathbb{G}_{24}^1$, except that we apply the modification of the game $\mathbb{G}_{22}^0$ to attack the security of $x$ and $y$ in the key-derivation schedule. We perform the same analysis and reduction, and thus obtain, thanks to a p.p.t. algorithm $B_7^2$:

$$ \left| \mathbb{P}(\mathbb{G}_{24}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{25}^1 \Rightarrow 1) \right| \le q_{\text{RO}_T} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda). $$

† **Game $\mathbb{G}_{25}^1$**: This game is the same as game $\mathbb{G}_{25}^1$, except that we apply the modification of the game $\mathbb{G}_{23}^0$ to again attack the security of $x$ and $y$ in the key-derivation schedule. To detect that change, $\mathcal{A}$ has two options: queries $\text{SO}_T$ on the correct DIFFIE-HELLMAN value $g^{xy}$, which is as usual excluded at this stage or pick a random PRK$_{2e*}$ from $\{0, 1\}^{l_{\text{hash}}}$, hopping for PRK$_{2e*}$ = PRK$_{2e}$. Similarly we denote $F_5^1$ the event: $\mathcal{A}$ queries $\text{SO}_P^{l_2}$ on the correct value PRK$_{2e}$ for a session in which the latter is unpredictable (here only $\text{SO}_P^{l_2}$ uses PRK$_{2e}$). If $F_5^1$ happens, we stop the simulation and return a random bit. In a similar way as in game $\mathbb{G}_{23}^0$, we provide an upper bound for $\mathbb{P}(F_5^1)$ with:

$$ \mathbb{P}(F_{5''}^1) \le \frac{q_{\text{RO}_P^{l_2}}}{2^{l_{\text{hash}}}}. $$

By the identical-until-bad lemma, we obtain:

$$ \left| \mathbb{P}(\mathbb{G}_{25}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{25'}^1 \Rightarrow 1) \right| \le \frac{q_{\text{RO}_P^{l_2}}}{2^{l_{\text{hash}}}}. $$

† **Game $\mathbb{G}_{25''}^1$**: This game is the same as the previous one, except that if $\pi_{\Xi}^e$ is an honest Initiator's instance receiving the second message $(g^y, c_2)$ (not necessarily forged) from an adversary-controlled Responder's instance which is not corrupted, we simulate the generation of the key PRK$_{3e2m}$ for the Initiator's instance thanks to a private oracle $\text{SO}_{\text{PRK}_{3e2m}}$ (instead of using $\text{SO}_T$). This is a minor modification compare to the previous games: a difference appears only if the second message is authentic, which can be compare to saying that we are in an honest session, in which case the key PRK$_{2e}$, computed by the Initiator instance, is unpredictable since generated by a private oracle, and thus different from the public one, expected by the Responder instance, with a probability of $\frac{1}{2^{l_{\text{hash}}}}$ (since PRK$_{2e}$ is of size $l_{\text{hash}}$).

Once again a previous analysis applies: there is no collision in $\text{SO}_P^{l_{\text{hash}}}$, thus $\text{salt}_{3e2m}$ obtained by the Initiator instance is different from the value obtained by an honest Responder instance.

Adversary $\mathcal{A}$ may be able to detect the use of $\text{SO}_{\text{PRK}_{3e2m}}$ if he queries $\text{SO}_T$ on the correct DIFFIE-HELLMAN element $g^{rx}$ or $\text{SO}_P$s on the correct value PRK$_{3e2m}$. Because of events $F_4^1$ and $F_5^1$, these situations cannot happen since we already stop the simulation in these cases. We thus have:

$$ \left| \mathbb{P}(\mathbb{G}_{25''}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{25'}^1 \Rightarrow 1) \right| \le \frac{1}{2^{l_{\text{hash}}}}. $$

† **Game $\mathbb{G}_{25''}^1$**: This game is the same as the previous one, and once is not customary, if $\pi_{\Xi}^e$ is an honest Responder's instance receiving $m_1$ from an adversary-controlled Initiator's instance which is not corrupted, the challenger simulates PRK$_{3e2m}$ thanks to a private oracle $\text{SO}_{\text{PRK}_{3e2m}}$. We can perform a similar analysis as in the previous game, just reverting the role: a difference appears only if the first message is not forged, which can be compare to saying that we are in an honest session, in which case PRK$_{2e}$ is generated thanks to a private oracle, and thus different from the public one expected by the Initiator instance with probability $\frac{1}{2^{l_{\text{hash}}}}$.

And again, there are no collisions in $\text{SO}_P^{l_{\text{hash}}}$, so $\text{salt}_{3e2m}$ is different from the value obtained by an honest Initiator's instance. So $\mathcal{A}$ detect the use of this private oracle if he asked the $\text{SO}_T$ oracle on the correct DIFFIE-HELLMAN value $g^{rx}$ or queried $\text{SO}_P$s on the correct value PRK$_{3e2m}$ which is impossible thanks to the events $F_4^1$ and $F_5^1$ (which already stopped the simulation in this case). We thus have:
$$ \left| \mathbb{P}(\mathbb{G}_{25''}^1 \implies 1) - \mathbb{P}(\mathbb{G}_{25'''}^1 \implies 1) \right| \le \frac{1}{2^{l_{\text{hash}}}}. $$

† **Game $\mathbb{G}_{26}^1$**: This game is the same as $\mathbb{G}_{25''}^1$, but here we finally focus on the generation of PRK$_{out}$ if the tested instance is fresh. Indeed if the tested instance does not respect the Fresh property, then the adversary cannot win the game with a non-zero advantage. So in this situation we generate PRK$_{out}$ thanks to a private oracle $SO_{PRK_{out}}$ for these sessions. Note that the game $\mathbb{G}_8$ ensures the points related to the authorities for all the sessions in the fresh definition. The rest of the definition means that no call to the oCorrupt oracle (on the long term signing key) occurred before each party accepted. We can retranslate this by saying that the Initiator's instance is not corrupted before receiving the second message and the Responder's instance is not corrupted before receiving the third message. By chance, the three previous games have been constructed to ensure that in this case, the key PRK$_{3e2m}$ is generated using the private oracle $SO_{PRK_{3e2m}}$, and so unpredictable by the adversary.

Since PRK$_{out}$ is computed using PRK$_{3e2m}$, the adversary may detect the use of the private oracle $SO_{PRK_{out}}$ (in one of the two instances involved in the session) if he asked the $SO_P^{l_{hash}}$ oracle on the (public but unpredictable) value PRK$_{2e}$. Let's denote $F_6^1$ this event. If $F_6^1$ occurs we stop the simulation by returning a random bit. By the identical-until-bad lemma we obtain:

$$ \left| \mathbb{P}(\mathbb{G}_{25''}^1 \implies 1) - \mathbb{P}(\mathbb{G}_{26}^1 \implies 1) \right| \le \mathbb{P}(F_6^1). $$

As we done it for the game $\mathbb{G}_{26}^0$, we bound $\mathbb{P}(F_6^1)$ by:

$$ \mathbb{P}(F_6^1) \le \frac{q_{\text{RO}_P^{l_{\text{hash}}}}}{2^{l_{\text{hash}}}}, $$

and hence:

$$ \left| \mathbb{P}(\mathbb{G}_{25''}^1 \implies 1) - \mathbb{P}(\mathbb{G}_{26}^1 \implies 1) \right| \le \frac{q_{\text{RO}_P^{l_{\text{hash}}}}}{2^{l_{\text{hash}}}}. $$

† **Game $\mathbb{G}_{22}^2$**: This game is the same as $\mathbb{G}_{21}^2$ and we keep going on the same vein as $\mathbb{G}_{22}^1$. If the adversary, during the tested session (the session between $\pi_{\Xi}^e$ and $\pi_{\Xi'}^e$), queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{iy}$, then we abort and return a random bit. We then denote $F_4^2$ the event: $\mathcal{A}$ queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{iy}$ (with $g^y$ the public DIFFIE-HELLMAN element of a challenger-controlled Responder instance and $i$ a (adversary-controlled, not corrupted) Initiator instance long-term secret key). If the event $F_4^2$ occurs, then challenger stops the simulation by returning a random bit. By the identical-until-bad lemma, we thus have:

$$ \left| \mathbb{P}(\mathbb{G}_{21}^2 \implies 1) - \mathbb{P}(\mathbb{G}_{22}^2 \implies 1) \right| \le \mathbb{P}(F_4^2). $$

As in game $\mathbb{G}_{22}^1$ we construct, by reduction, an adversary $\mathcal{B}_6^2$ against the GDH problem and we bound $\mathbb{P}(F_4^2)$ by:

$$ \mathbb{P}(F_4^2) \le q_{\text{NS}} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda), $$

and finally:

$$ \left| \mathbb{P}(\mathbb{G}_{21}^2 \implies 1) - \mathbb{P}(\mathbb{G}_{22}^2 \implies 1) \right| \le q_{\text{NS}} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda). $$

† **Game $\mathbb{G}_{23}^2$**: This game is the same as the previous one and works in the same vein as $\mathbb{G}_{23}^1$, but compare to the later, here we reversed the role of the Initiator and the Responder. This time, if our tested instance is an honest Responder instance receiving a forged message $m_1$ from and adversary-controlled Initiator's
instance which is non-corrupted, and which is still non-corrupted when sending $c_3$, the challenger generates the key PRK$_{4e3m}$ (for the Responder instance) thanks to a private oracle $SO_{PRK_{4e3m}}$. Here we prove the security of $i$ and $g^{iy}$ in the key-derivation schedule; in normal times, PRK$_{4e3m}$ is generated with $SO_T$, salt$_{4e3m}$ and $g^{iy}$) (note that here we don't need to restrict the use of the oCorrupt oracle, after $A$ returns its guess).

We perform now an analysis of what is happening in this case. Because $m_1$ is forged, thanks to the absence of collisions, elements $TH_2, TH_3$ and salt$_{4e3m}$ do not equal values expected from an honest Initiator instance.

The adversary $A$ may be able to detect this modification if he asks $SO_T$ on the correct DIFFIE-HELLMAN value $g^{iy}$. Thanks to the event $F_4^2$ the simulation is already stopped in this situation. Another way to detect it is to query $SO_P^{l_{hash}}$, or $SO_P^{l_{key}}$, or $SO_P^{l_{iv}}$, or $SO_P^{l_{mac}}$ on the correct value PRK$_{4e3m}$ which unpredictable at this stage. We denote $F_5^2$ the event: $A$ queries $SO_P^{l_{hash}}$, or $SO_P^{l_{key}}$, or $SO_P^{l_{iv}}$, or $SO_P^{l_{mac}}$ on the correct value PRK$_{3e2m}$ for a session in which the latter is unpredictable. If $F_5^1$ happens, we stop the simulation and return a random bit. We can provide now an upper bound for $P(F_5^2)$. For that we look at the probability of $A$ querying one of these four oracles on the correct PRK$_{4e3m}$ in our tested session. Since for the adversary, PRK$_{4e3m}$ is here unpredictable, we obtain the following probability:

$\frac{1}{2^{l_{hash}}} \text{ (since PRK}_{4e3m} \text{ has size } l_{hash} \text{) for the guess of PRK}_{4e3m} \text{. Now } A \text{ can make at most } q_{RO_P^{l_{hash}}} \text{ (resp. } q_{RO_P^{l_{key}}}, q_{RO_P^{l_{iv}}}, \text{ and } q_{RO_P^{l_{mac}}} \text{) calls to } SO_P^{l_{hash}} \text{ (resp. } SO_P^{l_{key}}, SO_P^{l_{iv}} \text{ and } SO_P^{l_{hash}} \text{), we thus have:}$

$$P(F_5^1) \leq \frac{q_{RO_P^{l_{hash}}} + q_{RO_P^{l_{key}}} + q_{RO_P^{l_{iv}}} + q_{RO_P^{l_{mac}}}}{2^{l_{hash}}}. $$

By the identical-until-bad lemma, we obtain:

$$|P(G_{22}^2 \Rightarrow 1) - P(G_{23}^2 \Rightarrow 1)| \leq P(F_5^2) $$

and thus:

$$|P(G_{22}^2 \Rightarrow 1) - P(G_{23}^2 \Rightarrow 1)| \leq \frac{q_{RO_P^{l_{hash}}} + q_{RO_P^{l_{key}}} + q_{RO_P^{l_{iv}}} + q_{RO_P^{l_{mac}}}}{2^{l_{hash}}}. $$

† **Game $G_{24}^2$:** This game is the same as game $G_{23}^2$ and works in the same vein as $G_{24}^0$. Namely if $\pi_{\Xi}^e$ is an honest Initiator's instance receiving a forged tuple $(g^y, c_2)$ from an adversary-controlled Responder's instance which is non-corrupted, the challenger simulates PRK$_{4e3m}$ for the Initiator's instance with a private oracle $SO_{PRK_{4e3m}}$.

The same analysis as in game $G_{24}^0$ (with the appropriate notations) can be performed. Again, in this situation, the adversary detect the use of the private oracle, if he queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{iy}$ - and thanks to the event $F_4^2$, the simulation is already stopped - or if $A$ queries $SO_P$s on the correct value PRK$_{4e3m}$ - and thanks to the event $F_5^2$, the simulation is already stopped. So this change becomes indistinguishable by the adversary. So we have:

$$P(G_{24}^2 \Rightarrow 1) = P(G_{23}^2 \Rightarrow 1). $$

† **Game $G_{25}^2$:** This game is the same as game $G_{24}^2$, except that we apply the modification of the game $G_{22}^0$ to attack the security of $x$ and $y$ in the key-derivation schedule. We perform the same analysis and reduction, and thus obtain, thanks to a p.p.t. algorithm $B_7^2$:

$$|P(G_{24}^2 \Rightarrow 1) - P(G_{25}^2 \Rightarrow 1)| \leq q_{RO_T} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda). $$
† **Game $G_{25}^2$**: This game is the same as the previous one, except that we apply the modification of the game $G_{23}^0$ to again attack the security of $x$ and $y$ in the key-derivation schedule. To detect that change, $\mathcal{A}$ has two options: queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xy}$, which is as usual excluded at this stage or pick a random PRK$_{2e*}$ from $\{0, 1\}^{l_{hash}}$, hopping for PRK$_{2e*}$ = PRK$_{2e}$. Similarly we denote $F_{5''}^2$, the event: $\mathcal{A}$ queries $SO_P^{l_2}$ on the correct value PRK$_{2e}$ for a session in which the latter is unpredictable (here only $SO_P^{l_2}$ uses PRK$_{2e}$). If $F_{5''}^2$ happens, we stop the simulation and return a random bit. In a similar way as in game $G_{23}^0$, we provide an upper bound for $\mathbb{P}(F_{5''}^2)$ with:

$$ \mathbb{P}(F_{5''}^2) \leq \frac{q_{\mathrm{RO}_P^{l_2}}}{2^{l_{\mathrm{hash}}}}. $$

By the identical-until-bad lemma, we obtain:

$$ |\mathbb{P}(G_{25}^2 \implies 1) - \mathbb{P}(G_{25'}^2 \implies 1)| \leq \frac{q_{\mathrm{RO}_P^{l_2}}}{2^{l_{\mathrm{hash}}}}. $$

† **Game $G_{25''}^2$**: This game is the same as $G_{25'}^2$, except that if $\pi_{\Xi}$ is an honest Responder instance receiving $c_3$ (not necessarily forged) from an adversary-controlled Initiator's instance which is not corrupted, the challenger simulates PRK$_{4e3m}$ thanks to a private oracle $SO_{PRK_{4e3m}}$. We can now perform the same deduction as in the game $G_{25''}^1$ (with the appropriate notations) which leads to:

$$ |\mathbb{P}(G_{25'}^2 \implies 1) - \mathbb{P}(G_{25''}^2 \implies 1)| \leq \frac{1}{2^{l_{\mathrm{hash}}}}. $$

† **Game $G_{25''}^2$**: This game is the same as $G_{25''}^2$, and works in the same way as $G_{25''}^1$, with the appropriate notations. We thus obtain the same results:

$$ |\mathbb{P}(G_{25''}^2 \implies 1) - \mathbb{P}(G_{25'''}^2 \implies 1)| \leq \frac{1}{2^{l_{\mathrm{hash}}}}. $$

† **Game $G_{26}^2$**: This game is the same as $G_{25''}^2$, but here we finally focus on the generation of PRK$_{out}$ if the tested instance is fresh. As in game $G_{26}^1$ we define the event $F_6^2$ and bound $\mathbb{P}(F_6^2)$ as in game $G_{26}^0$. Here again by the identical-until-bad lemma we obtain:

$$ |\mathbb{P}(G_{25''}^2 \implies 1) - \mathbb{P}(G_{26}^2 \implies 1)| \leq \frac{q_{\mathrm{RO}_P^{l_{\mathrm{hash}}}}}{2^{l_{\mathrm{hash}}}}. $$

† **Game $G_{22}^3$**: This game follows $G_{17'}^3$ and works in the same way as $G_{22}^1$, with the appropriate notations. After defining the event $F_4^3$, we obtain the same results and thus have, thanks to a p.p.t. algorithm $\mathcal{B}_6^3$:

$$ |\mathbb{P}(G_{17'}^3 \implies 1) - \mathbb{P}(G_{22}^3 \implies 1)| \leq q_{\mathrm{NS}} \cdot \mathrm{Adv}_{\mathcal{G}}^{\mathrm{GDH}}(\lambda). $$

† **Game $G_{23}^3$**: This game is the same as the previous one, and we apply the same modification as in $G_{23}^1$ (with the appropriate notations), defining the event $F_5^3$. Again we bound $\mathbb{P}(F_5^3)$ and thanks to the identical-until-bad lemma we obtain the same result:

$$ |\mathbb{P}(G_{22}^3 \implies 1) - \mathbb{P}(G_{23}^3 \implies 1)| \leq \frac{q_{\mathrm{RO}_P^{l_{\mathrm{hash}}}} + q_{\mathrm{RO}_P^{l_{\mathrm{key}}}} + q_{\mathrm{RO}_P^{l_{\mathrm{iv}}}} + q_{\mathrm{RO}_P^{l_{\mathrm{mac}}}}}{2^{l_{\mathrm{hash}}}}. $$
† **Game $G_{24}^3$**: This game is the same as the previous one and works in the same way as $G_{22}^2$, with the appropriate notations. We here define the event $F_{5'}^3$ and we bound $\mathbb{P}(F_{5'}^3)$ in the same way. We thus obtain:

$$|\mathbb{P}(G_{23}^3 \Rightarrow 1) - \mathbb{P}(G_{24}^3 \Rightarrow 1)| \le q_{NS} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda).$$

† **Game $G_{25}^3$**: This game is the same as the previous one, and we apply the same modification as in $G_{23}^2$ (with the appropriate notations), defining the event $F_{5''}^3$. Again we obtain the same result:

$$|\mathbb{P}(G_{24}^3 \Rightarrow 1) - \mathbb{P}(G_{25}^3 \Rightarrow 1)| \le \frac{q_{\text{RO}_P^{l'\text{hash}}} + q_{\text{RO}_P^{l'\text{key}}} + q_{\text{RO}_P^{l'\text{iv}}} + q_{\text{RO}_P^{l'\text{mac}}}}{2^{l'\text{hash}}}.$$

† **Game $G_{25'}^3$**: Here again, this game is the same as the previous one, and works in the same vein as $G_{22}^0$. This leads again, thanks to a p.p.t. algorithm $B_8^3$, to:

$$|\mathbb{P}(G_{25}^3 \Rightarrow 1) - \mathbb{P}(G_{25'}^3 \Rightarrow 1)| \le q_{\text{RO}_T} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda).$$

† **Game $G_{25''}^3$**: This game is the same as the previous one, and we apply the same modification as in game $G_{25'}^2$ (with the appropriate notations). We thus obtain the same result:

$$|\mathbb{P}(G_{25'}^3 \Rightarrow 1) - \mathbb{P}(G_{25''}^3 \Rightarrow 1)| \le \frac{q_{\text{RO}_P^{l_2}}}{2^{l'\text{hash}}}. $$

† **Game $G_{25'''}^3$**: This game is the same as the previous one and works in the same way as $G_{25''}^1$ (by using the private oracle $\text{SO}_{\text{PRK}_{3\text{e}2\text{m}}}$). This leads us to bound the advantage of the adversary for this game hop in the same way:

$$|\mathbb{P}(G_{25''}^3 \Rightarrow 1) - \mathbb{P}(G_{25'''}^3 \Rightarrow 1)| \le \frac{1}{2^{l'\text{hash}}}. $$

† **Game $G_{25''''}^3$**: This game is the same as $G_{25''}^3$, except that we simulate the generation of $\text{PRK}_{4\text{e}3\text{m}}$ with the private oracle $\text{SO}_{\text{PRK}_{4\text{e}3\text{m}}}$ for $\pi_{\Xi}$ if it is an honest Initiator's instance receiving a second message (not necessarily forged) from an adversary-controlled Responder's instance (which is not corrupted on its long term static DH key). But thanks to the previous game, we know that $\text{PRK}_{3\text{e}2\text{m}}$ is random from the point of view of $\mathcal{A}$, and as it is involved in the computation of $\text{salt}_{4\text{e}3\text{m}}$ and $\text{PRK}_{4\text{e}3\text{m}}$, the latter are already unpredictable (for the Initiator and Responder instances thanks to the events introduced in the previous games, that's why the adversary cannot detect it). So this modification is indistinguishable by $\mathcal{A}$ and we thus have:

$$\mathbb{P}(G_{25'''} \Rightarrow 1) = \mathbb{P}(G_{25''''} \Rightarrow 1). $$

† **Game $G_{25''''}^3$**: This game is the same as the previous one and works in the same vein as $G_{25''}^2$. We deduce the same result and so we have:

$$|\mathbb{P}(G_{25'''}^3 \Rightarrow 1) - \mathbb{P}(G_{25''''}^3 \Rightarrow 1)| \le \frac{1}{2^{l'\text{hash}}}. $$
† **Game $G_{26}^3$**: This game is the same as $G_{25}^{3,}$, but here we finally focus on the generation of PRK$_{out}$ if the tested instance is fresh. As in game $G_{26}^2$ we define the event $F_6^3$ and bound $\mathbb{P}(F_6^3)$ as in game $G_{26}^0$. Here again by the identical-until-bad lemma we obtain:

$$|\mathbb{P}(G_{25}^3 \implies 1) - \mathbb{P}(G_{26}^3 \implies 1)| \le \frac{q_{\text{ROP}^l_{\text{hash}}}}{2^l_{\text{hash}}}.$$

We can now conclude the proof and for that we analyze the final advantage of $\mathcal{A}$ when playing game $G_{26}$ (this explanation, expect for the notations, is valid for the four games $G_{26}^0$, $G_{26}^1$, $G_{26}^2$ and $G_{26}^3$). For that we take a look at the situations in which $\mathcal{A}$ has a non-zero advantage after having return his guessing bit. It is the case when:

Sound is **false** or;

Fresh($\pi_{\Xi}^e$) is **true** and $b = b'$.

Indeed:

If Sound is **false**, then the experience returns 1 and thus the advantage of $\mathcal{A}$ is greater than 0.

Let's observe that if Fresh($\pi_{\Xi}^e$) is **false**, then the experience sets $b' \leftarrow \{0, 1\}$. So the event $b = b'$ happens, in this case, with probability $\frac{1}{2}$ and so the advantage of $\mathcal{A}$ is 0. So if Fresh($\pi_{\Xi}^e$) is **true** and if $b = b'$, then $\mathcal{A}$ wins the game $G_{26}$ (if $b \neq b'$, then $\mathcal{A}$ loses the game and it means that its advantage is 0) and thus its advantage is greater than 0.

So we need to check if here $\mathcal{A}$ respects soundness. Informally, we raised a flag Sound to **false** if:

(●) Three honest instances hold the same sid, or;

(●●) Two partnered instances involved in the same session hold different session keys.

Now observe that thanks to the game $G_2$, (●) is impossible. So we take a closer look to (●●). With honest instances, or simply controlled by the adversary (but not corrupted), with the previous construction, we do not infringe on the soundness property (thanks to the private oracles). Now if we consider two partnered instances, with at least on corrupted, since they share the session identifier with the beginning of the exchange process, they derive the same session key PRK$_{out}$ thanks to the multiples oracles SO. In other words, agreeing on the sid implies deriving the same PRK$_{out}$. Subsequently in game $G_{26}$, the flag Sound is always set to true.

We can finally bound the adversary's advantage in game $G_{26}$. For that observe that for any fresh sessions, if the adversary queries the oTest$_b$ oracle, in the case $b = 0$, since we used private oracles, it finally outputs a random key. Moreover, in the case $b = 1$, the outputed session key is random too. So, ultimately, the probability that $\mathcal{A}$ correctly guesses and distinguishes between the two keys in game $G_{26}$ is $\frac{1}{2}$ (we here look at the probability that $b = b'$), i.e.:

$$\mathbb{P}(G_{26} \implies 1) = \frac{1}{2}.$$
So finally, combining the four branches and the main branch if the beginning, we have:

$$
\begin{aligned}
\mathrm{Adv}_{\mathrm{LI-EDHOC},A}^{\mathrm{KS}}(\lambda) &= \left| \mathbb{P}(\mathbb{E}_{\mathrm{LI-EDHOC},A}^{\mathrm{KS}}(\lambda) \implies 1) - \frac{1}{2} \right| = \left| \mathbb{P}(G_0 \implies 1) - \mathbb{P}(G_{26} \implies 1) \right| \\
&\le \left| \mathbb{P}(G_0 \implies 1) - \mathbb{P}(G_1 \implies 1) \right| + \dots + \left| \mathbb{P}(G_{25} \implies 1) - \mathbb{P}(G_{26} \implies 1) \right| \\
&\le \frac{3q_{\mathrm{NS}}^2}{2^{l_C+1}p} + \frac{(q_{\mathrm{RO}_T} + q_{\mathrm{RO}_P^{l_{\mathrm{hash}}}})^2 + (q_{\mathrm{RO}_T} + q_{\mathrm{RO}_H})^2 + (q_{\mathrm{RO}_P^{l_{\mathrm{hash}}} + q_{\mathrm{RO}_H})^2}{2^{l_{\mathrm{hash}}+1}} \\
&\quad + q_{\mathrm{NS}} \cdot q_R^4 \cdot \left[ (2q_{\mathrm{RTD}} + q_S) \cdot \epsilon_{\mathrm{SoK}}(\lambda) + q_R \cdot \epsilon_{\mathrm{NIPoK}}(\lambda) + 24\mathrm{Adv}_{\mathbb{G}}^{\mathrm{DDH}}(\lambda) + 4\mathrm{Adv}_{\mathrm{DS}}^{\mathrm{EUF-CMA}}(\lambda) \right. \\
&\quad \left. + (4q_{\mathrm{RO}_T} + 4q_{\mathrm{NS}}) \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda) + 4 \cdot \frac{q_{\mathrm{RO}_P^{l_2}} + q_{\mathrm{RO}_P^{l_{\mathrm{key}}}} + q_{\mathrm{RO}_P^{l_{\mathrm{iv}}}} + q_{\mathrm{RO}_P^{l_{\mathrm{mac}}}} + q_{\mathrm{RO}_P^{l_{\mathrm{hash}}}} + 6}{2^{l_{\mathrm{hash}}}} \right]
\end{aligned}
$$

and this concludes the proof.

<figure><img src="image_14.png" /></figure>
## 7.2 LI-compliance

The second security result, whose we have ensured the validity, is now stated with the following theorem. With it, we guarantee that the four versions of our protocol respect the LI-compliance security property.

**Theorem 3 (LI-compliant LI-EDHOC protocol)** Under the assumption that our signature scheme DS is EUF-CMA-secure, that proofs and signatures of knowledge are zero-knowledge and extractable, the LI-EDHOC protocol, in its four versions, is LI-compliant. More precisely, for all p.p.t. adversary A making at most $q_R$ queries to the oRegister oracle and $q_S$ queries to the oSend oracle, we have:

$$ \mathrm{Adv}_{\mathrm{LI-EDHOC}, A}^{\mathrm{LIC}}(\lambda) \le q_R \left( \mathrm{Adv}_{\mathrm{DS}}^{\mathrm{EUF-CMA}}(\lambda) + q_R \cdot \epsilon_{\mathrm{NIPoK}}(\lambda) + q_S \cdot \epsilon_{\mathrm{SoK}}(\lambda) \right). $$

Before starting the proof, we just remind the LI-compliance security game.

<figure><img src="image_15.png" /><figcaption>FIGURE 26 – LI-compliance security game for the LI-EDHOC protocol (by $\mathrm{Prox_d.\overline{SK}}[\mathrm{sst_d}]$ we mean the secret (long-term) signing key of $\mathrm{Prox_d}$ used to sign $\mathrm{sst_d}$).</figcaption></figure>

**Proof 3 (of theorem 3)** Since the four versions of the protocol have some differences, we need, at some point, to split the proof of the theorem into four branches. The scheme is as follows: we first describe the four key-extractor algorithms $\mathrm{KeyExtract}(\pi_{\mathrm{Prox}}, \mathrm{LIC.\overline{PK}})$, and then we proceed by games hop, with four (main) games. First, the game $\mathbb{G}_0$ is the reformulation of the original game. Then with game $\mathbb{G}_1$ and $\mathbb{G}_2$ we select at random a particular honest proxy against which A will fight, and we restrict the winning condition of the adversary according to this particular proxy. Then in game $\mathbb{G}_3$ we use the $\mathrm{NIPoK}$ extractor in order to prevent the adversary from forging a proof of knowledge. Finally in game $\mathbb{G}_4$ we use the $\mathrm{SoK}$ extractor in order to prevent the adversary from forging a signature of knowledge, and we conclude by reducing the winning probability of the adversary to 0. This last game will also be split into four similar games to cover all four versions. The game schedule is depicted in FIGURE 27 below.

We start by describing the four (deterministic, unbounded (otherwise it would be possible to determine the key in polynomial time, which would be problematic)) key-extractor algorithms $\mathrm{KeyExtract}(\pi_{\mathrm{Prox}}, \mathrm{LIC.\overline{PK}})$, which given as input a proxy instance $\pi_{\mathrm{Prox}}$ and a set of public keys (generated as is the definition), outputs the same session key $\mathrm{PRK}_{\mathrm{out}}$ as the Initiator and the Responder instances having matching conversation in
<figure><img src="image_16.png" /><figcaption>FIGURE 27 – Game-schedule for the LI-compliance property</figcaption></figure>

the same session as the proxy. We depicted the four algorithms in one picture (FIGURE 28), framing or highlighting the differences that appear between the different versions:

KeyExtract($\pi_{\text{Prox}}$, LIC, $\overline{\text{PK}}$)

1. Parse the instance transcript $\pi_{\text{Prox}}$.tr, parse $\pi_{\text{Prox}}$.PNID as (I, R) and $\pi_{\text{Prox}}$.AID as $(\Lambda_q)_{q=1}^n$.

2. Set $y_1 = 0$. While $g^{y_1} \neq g^y$, do $y_1 = y_1 + 1$.

3. Set $r_1 = 0$. While $g^{r_1} \neq g^r$, do $r_1 = r_1 + 1$.

4. Set $i_1 = 0$. While $g^{i_1} \neq g^i$, do $i_1 = i_1 + 1$.

5. Compute $g^{xy} \leftarrow (g^x)^{y_1} = (g^x)^y$, $\overline{g^{xr} \leftarrow (g^x)^{r_1} = (g^x)^r}$, $\overline{g^{y_i} \leftarrow (g^y)^{i_1} = (g^y)^i}$ and PRK$_{\text{out}}$ with the additional data contained in the transcript.

6. Return PRK$_{\text{out}}$.

FIGURE 28 – The key-extractor algorithm. The hatched boxes $\overline{\cdots\cdots}$ contain the additional elements for the ID = 1 version, the boxes $\cdots$ contain the additional elements for the ID = 2 version and the highlighted texts $\cdots$ indicate the additional elements for the ID = 3 version.

Depending on the version and on whose side we stand, the transcript of the instance $\pi_{\text{Prox}}$.tr is parsed differently in the previous algorithm. In order, on the side of the Initiator we have:

* $\pi_{\text{Prox}}$.tr = MCS$\|g^x\|C_1$|EAD$_1$|$g^y$|c$_2$|c$_3$|H$_1$|ni$_1$|S$_1$|c$_4$|n$_r$|val|TH$_5$|sst$_1$;

* $\pi_{\text{Prox}}$.tr = MCS$\|g^x\|C_1$|EAD$_1$|$g^y$|c$_2$|c$_3$|H$_1$|H$_1^1$|ni$_1$|S$_1$|c$_4$|n$_r$|val|TH$_5$|sst$_1$;

* $\pi_{\text{Prox}}$.tr = MCS$\|g^x\|C_1$|EAD$_1$|$g^y$|c$_2$|c$_3$|H$_1$|H$_1^1$|ni$_1$|S$_1$|c$_4$|n$_r$|val|TH$_5$|sst$_1$;
* $\pi_{\text{Prox}}.\text{tr} = \text{MCS} \|g^x\| C_1 \|\text{EAD}_1\| g^y \|c_2\| c_3 \|H_1\| H_1^1 \|H_1^2\| \text{ni}_1 \|S_1\| c_4 \|n_r\| \text{val} \|\text{TH}_5\| \text{sst}_1$.

And on the side of the Responder, always in order, we have:

* $\pi_{\text{Prox}}.\text{tr} = \text{MCS} \|g^x\| C_1 \|\text{EAD}_1\| g^y \|c_2\| c_3 \|c_4\| H_R \|\text{ni}_R\| S_R \|n_r\| \text{val} \|\text{TH}_5\| \text{sst}_R$;

* $\pi_{\text{Prox}}.\text{tr} = \text{MCS} \|g^x\| C_1 \|\text{EAD}_1\| g^y \|c_2\| c_3 \|c_4\| H_R \|H_R^1\| \text{ni}_R \|S_R\| n_r \|\text{val} \|\text{TH}_5\| \text{sst}_R$;

* $\pi_{\text{Prox}}.\text{tr} = \text{MCS} \|g^x\| C_1 \|\text{EAD}_1\| g^y \|c_2\| c_3 \|c_4\| H_R \|H_R^1\| \text{ni}_R \|S_R\| n_r \|\text{val} \|\text{TH}_5\| \text{sst}_R$;

* $\pi_{\text{Prox}}.\text{tr} = \text{MCS} \|g^x\| C_1 \|\text{EAD}_1\| g^y \|c_2\| c_3 \|c_4\| H_R \|H_R^1\| H_R^2 \|\text{ni}_R\| S_R \|n_r\| \text{val} \|\text{TH}_5\| \text{sst}_R$.

We can now focus on the games hop.

† **Game $G_0$**: This game is the original experience $\mathbb{E}_{\text{LI-EDHOC},\mathcal{A}}^{\text{LIC}}(\lambda)$. We thus have:

$$ \mathbb{P}(\mathcal{A} \text{ wins } G_0) = \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{E}_{\text{LI-EDHOC},\mathcal{A}}^{\text{LIC}}(\lambda)). $$

† **Game $G_1$**: This game is the same game as $G_0$ except that we begin by picking at random $s \leftarrow \mathbb{1}, q_R$. Let $P_j$ be the j-th oracle party output by $\text{oRegister}$. If $\mathcal{A}$ returns a tuple $(j_*, \text{sst}_*, l_*, R_*, \text{Prox}_*, (\Lambda_{*,q}, \Lambda_{*,q}.\text{td})_{q=1}^n)$ such that $P_s \neq \text{Prox}_*$, then we abort and return 0. With this game hop, the winning advantage of the adversary is increased by a factor equaling the probability of guessing correctly the proxy $P_s$. We hence have:

$$ \mathbb{P}(\mathcal{A} \text{ wins } G_0) \leq q_R \mathbb{P}(\mathcal{A} \text{ wins } G_1). $$

† **Game $G_2$**: Let $(j_*, \text{sst}_*, l_*, R_*, \text{Prox}_*, (\Lambda_{*,q}, \Lambda_{*,q}.\text{td})_{q=1}^n)$ be the guess of $\mathcal{A}$. This game is the same as the previous one except that, using $\text{sid}_* = (C_{l,*}, C_{R,*}, g_*^x, g_*^y)$ constructed from $\text{sst}_* (C_{l,*}$ is drawn from $m_{1*}$ and $C_{R,*}$ from $m_{2*}$), if for all $k \in \mathbb{N}$, $\pi_{\text{Prox}_*}^k$. $\text{sid} \neq \text{sid}_*$, or $\pi_{\text{Prox}_*}^k$. $\text{PNID} \neq (l_*, R_*)$, or $\pi_{\text{Prox}_*}^k$. $\text{AID} \neq (\Lambda_{*,q})_{q=1}^n$, then $G_2$ aborts and returns 0. In this way, games $G_1$ and $G_2$ work the same way, unless the event $F$ occurs, where $F$ is the event: $\mathcal{A}$ returns a guess $(j_*, \text{sst}_*, l_*, R_*, \text{Prox}_*, (\Lambda_{*,q}, \Lambda_{*,q}.\text{td})_{q=1}^n)$ such that for all $k \in \mathbb{N}$, $\pi_{\text{Prox}_*}^k$. $\text{sid} \neq \text{sid}_*$, or $\pi_{\text{Prox}_*}^k$. $\text{PNID} \neq (l_*, R_*)$, or $\pi_{\text{Prox}_*}^k$. $\text{AID} \neq (\Lambda_{*,q})_{q=1}^n$.

$$ |\mathbb{P}(\mathcal{A} \text{ wins } G_1) - \mathbb{P}(\mathcal{A} \text{ wins } G_2)| \leq \mathbb{P}(F). $$

We now provide an upper bound for $\mathbb{P}(F)$. We claim that:

$$ \mathbb{P}(F) \leq \text{Adv}_{\text{DS}}^{\text{EUF-CMA}}(\lambda) $$

and hence we have:

$$ |\mathbb{P}(\mathcal{A} \text{ wins } G_1) - \mathbb{P}(\mathcal{A} \text{ wins } G_2)| \leq \text{Adv}_{\text{DS}}^{\text{EUF-CMA}}(\lambda). $$
‡ **Proof of the claim:** We prove the claim by reduction, constructing a p.p.t. adversary $\mathcal{B}_1$ that breaks the EUF-CMA security property of DS.

Before constructing $\mathcal{B}_1$, assume that an adversary $\mathcal{A}$ wins game $\mathbb{G}_1$ with a non negligible probability $\epsilon_{\mathcal{A}}(\lambda)$ by returning a guess $(j_*, \text{sst}_*, l_*, R_*, \text{Prox}_*, (\Lambda_{*,q}, \Lambda_{*,q}.\text{td})_{q=1}^n)$ such that for all $k \in \mathbb{N}$, $\pi_{\text{Prox}_*}^k$.sid $\neq$ sid$_*$, or $\pi_{\text{Prox}_*}^k$.PNID $\neq$ (l$_*$, R$_*$), or $\pi_{\text{Prox}_*}^k$.AID $\neq$ $(\Lambda_{*,q})_{q=1}^n$. Note that if $\mathcal{A}$ wins $\mathbb{G}_1$, then $\text{Prox}_*$.γ = 0 and Verify(pp, sst*, l*.PK, R*.PK, Prox*.PK, (\Lambda_{*,q})_{q=1}^n) = 1$, and according to $\mathbb{G}_1$, if $\text{Prox}_* \neq P_s$, the game returns 0.

We now present the construction of our adversary $\mathcal{B}_1$.

At the beginning, the challenger generates a pair of public/private signature keys ($\widehat{\text{ssk}}, \widehat{\text{spk}}$) with the DS.Gen algorithm, and gives to $\mathcal{B}_1$ the public signing key $\widehat{\text{spk}}$. Algorithm $\mathcal{B}_1$ wins the game if it sends back to its challenger a message/signature pair $(m, \sigma)$ he did not generate and such that $\text{DS.Verif}(\widehat{\text{spk}}, m, \sigma) = 1$.

In order to achieve this, $\mathcal{B}_1$ initializes an empty list $L_S \leftarrow \emptyset$, and then simulates $\mathbb{G}_1$ to $\mathcal{A}(\text{pp})$ faithfully, but with three exceptions:

$\qquad \mapsto \text{oRegister}(P, \text{type}, \overline{\text{PK}}):$ if the s-th register query has type $\neq$ proxy ($\mathbb{G}_1$ requirement) or $\overline{\text{PK}} \neq \{\perp\}$ (experiment requirement : we want this proxy to be honest, i.e., not malicious, then $\mathcal{B}_1$ aborts. Else $\mathcal{B}_1$ sets $P_s \leftarrow P$ and $P_s \overline{\text{PK}} \ni P_s$. $\widehat{\text{spk}} \leftarrow \widehat{\text{spk}}$.

$\qquad \mapsto \text{oSend}(\pi_P^q, m):$ if $P = \text{Prox}$, $\mathcal{B}_1$ simulates $\text{oSend}$ faithfully, but queries its Sign oracle (instead of the DS.Sign algorithm) if needed: $\sigma \leftarrow \text{Sign}(\tau)$, then adds $(\tau, \sigma)$ to $L_S$ and sets $\text{sst} \leftarrow \tau \|\sigma$ (as in the original protocol).

$\qquad \mapsto \underline{\text{Corrupt}}(P, \ell):$ if $P = P_s$ and $P \overline{\text{PK}}[l] = \widehat{\text{spk}}$, then $\mathcal{B}_1$ aborts.

Finally $\mathcal{A}$ returns $(j_*, \text{sst}_*, l_*, R_*, \text{Prox}_*, (\Lambda_{*,q}, \Lambda_{*,q}.\text{td})_{q=1}^n)$, and $\mathcal{B}_1$ parses $\text{sst}_*$ as $\tau_* \| \sigma_*$, sets $\text{sid}_* = (C_{l_*,*}, C_{R_*,*}, g_*^x, g_*^y)$, and returns $(\tau_*, \sigma_*)$ to its challenger.

Note that the simulation of $\mathbb{G}_1$ by $\mathcal{B}_1$ for $\mathcal{A}$ is perfect.

We now consider the situation in which $\mathcal{A}$ wins the game $\mathbb{G}_1$ with respect to the conditions imposed for this reduction. In this case we have $\forall k \in \mathbb{N}$, $\pi_{\text{Prox}_*}^k$.sid $\neq$ sid$_*$, or $\pi_{\text{Prox}_*}^k$.PNID $\neq$ (l$_*$, R$_*$), or $\pi_{\text{Prox}_*}^k$.AID $\neq$ $(\Lambda_{*,q})_{q=1}^n$. By interpreting this, we see that $\text{sst}_*$ was returned by $\text{oSend}$ on a run of the protocol in which no instances of $\text{Prox}_*$ was involved. This thus means that $(\tau_*, \sigma_*) \notin L_S$.

Moreover, at the beginning of the proof of this claim, we remind that in this situation (i.e., $\mathcal{A}$ wins), we must have $\text{Prox}_* = P_s$ but also Verify(pp, sst*, l*.PK, R*.PK, Prox*.PK, $(\Lambda_{*,q})_{q=1}^n) = 1$. Thanks to the description of algorithm Verify, this previous equality means that we have in particular DS.Verif($\text{Prox}_*.\widehat{\text{spk}}$, $\tau_*, \sigma_*) = 1$. In other words, $\sigma_*$ is a valid signature for the message $\tau_*$ with the challenged key $\widehat{\text{spk}}$. Bringing together these analysis, we obtain that if $\mathcal{A}$ wins (with the imposed conditions), i.e., if $F$ happens, then $\mathcal{B}_1$ wins its game, and breaks the EUF-CMA security of DS. This leads to $\text{Adv}_{\text{DS}, \mathcal{B}_1}^{\text{EUF-CMA}}(\lambda) \geq \epsilon_{\mathcal{A}}(\lambda)$, and so:

$$ \mathbb{P}(F) \leq \epsilon_{\mathcal{A}}(\lambda) \leq \text{Adv}_{\text{DS}, \mathcal{B}_1}^{\text{EUF-CMA}}(\lambda) $$

which concludes the proof of the claim.

† **Game $\mathbb{G}_3$:** Let $\text{Ext}_{\text{td}}$ be the extractor of NIPoK${d} : D_1 = g_1^d \wedge D_2 = g_2^d$} in the TDGen algorithm, and $(j_*, \text{sst}_*, l_*, R_*, \text{Prox}_*, (\Lambda_{*,q}, \Lambda_{*,q}.\text{td})_{q=1}^n)$ be the guess of $\mathcal{A}$. In order to prevent the adversary from forging proofs of knowledge (to ensure the security of the trapdoors) we insert in this game the extractor. So this game is the same game as $\mathbb{G}_2$, except that $\mathbb{G}_3$ starts by initializing an empty list $L[ ] \leftarrow \emptyset$ and:
For each query to oRevealTD on input (sst, l, R, Prox, $(\Lambda_q)_{q=1}^n, \ell$) (to get $\Lambda_\ell$.td), game $\mathbb{G}_3$ sets $L[\Lambda_\ell.td] \leftarrow \Lambda_\ell.SK$;

After that $\mathcal{A}$ returns its guess, $\mathbb{G}_3$ sets $\omega_* \leftarrow (\Lambda_{*,q})_{q=1}^n \|ID_*$(either $ID_{l*}$ or $ID_{R*}$) and parses $sst_*$ as $\omega_* \|MCS_*\| X_* \|Y_*\| TH_{2*} \|TH_{3*} \|TH_{4*} \|M_{1*} \|m_{2*} \|m_{3*} \|H_* \|ni_* \|pid_* \|n_{r*} \|val_* \|\sigma_*$(with pid either $ID_{R*}$ or $ID_{l*}$), and sets $A_0 \leftarrow X_*$ and $A_1 \leftarrow Y_*$.

For each $q \in [1, n]$ such that $L[\Lambda_{*,q}.td] = \perp$, it parses $\Lambda_{*,q}.PK \in \Lambda_{*,q}.\overline{PK}$ as $(\Lambda_{*,q}.pk, \Lambda_{*,q}.ni)$ and $\Lambda_{*,q}.td$ as $(\Lambda_{*,q}.td_0, \Lambda_{*,q}.td_1)$.

If NIPoKver($\mathcal{G}_3$, $\Lambda_{*,q}.pk$, $A_b$, $\Lambda_{*,q}.td_1$), $\Lambda_{*,q}.td_0$) = 1 (with $b = 0$ or 1 depending on the point of view), then $\mathbb{G}_3$ runs $Ext_{td}(\lambda)$ on $\mathcal{A}$ in order to extract a witness $\delta$ for the proof $\Lambda_{*,q}.td_0$ and sets $L[\Lambda_{*,q}.td] \leftarrow \delta$. Else $\mathbb{G}_3$ aborts and returns 0.

Following this, if $g^{L[\Lambda_{*,q}.td]} \neq \Lambda_{*,q}.pk$ or $A_b^{L[\Lambda_{*,q}.td]} \neq \Lambda_{*,q}.td_1$, then $\mathbb{G}_3$ aborts and returns 0.

So with this game hop we capture the possibility of $Ext_{td}$ failing when extracting a valid witness, in any of the (at most) $q_R$ calls. We deduce that:

$$ |\mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_2) - \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_3)| \le q_R \cdot \epsilon_{\text{NIPoK}}(\lambda). $$

Note that this game uses the notations of the $ID = 0$ version of the protocol (some we may have write $\mathbb{G}_3^0$ instead of $\mathbb{G}_3$). But for the three other versions, the same analysis can be performed, leading to the same result, because only the notations for NIPoK, NIPoKver, $sst$ and $\Lambda_{*,q}.td$ change (but it does not impact the above analysis). Thus, in all cases, we obtain this conclusion.

† **Game $\mathbb{G}_3^0$:** Let $Ext_{SoK}$ be the extractor of the signature of knowledge. In order to prevent the adversary from providing a forged signature of knowledge, this game is the same as the previous one, except that it starts by initializing an empty list $L'[] \leftarrow \emptyset$ and:

Each time the oSend oracle generates a SoK: $ni \leftarrow SoK_m\{z : (Z = g^z \wedge H = (hA)^z)\}$, it sets $L'[\langle g, Z, hA, H, m, ni \rangle] \leftarrow z$ (where $\mathcal{A}$ is an ephemeral DH secret of the point of view considered);

After $\mathcal{A}$ returns its guess, $\mathbb{G}_4^0$ sets $\omega_* \leftarrow (\Lambda_{*,q})_{q=1}^n \|ID_*$(either $ID_{l*}$ or $ID_{R*}$) and parses $sst_*$ as $\omega_* \|MCS_*\| X_* \|Y_*\| TH_{2*} \|TH_{3*} \|TH_{4*} \|M_{1*} \|m_{2*} \|m_{3*} \|H_* \|ni_* \|pid_* \|n_{r*} \|val_* \|\sigma_*$(with pid either $ID_{R*}$ or $ID_{l*}$), sets $A_0 \leftarrow X_*$ and $A_1 \leftarrow Y_*$, parses $\Lambda_{*,q}.PK \in \Lambda_{*,q}.\overline{PK}$ as $(\Lambda_{*,q}.pk, \Lambda_{*,q}.ni)$ and $\Lambda_{*,q}.td$ as $(\Lambda_{*,q}.td_0, \Lambda_{*,q}.td_1)$, and sets $h_* \leftarrow \prod_{q=1}^n \Lambda_{*,q}.pk$.

If $L'[\langle g, A_b, h_* A_{1-b}, H_*, m_*, ni_* \rangle] = \perp$ (here $m_* = \omega_* \|pid_* \|TH_{2*} \|TH_{3*} \|TH_{4*}$), then if SoKver($m_*$, $\langle g, A_b, h_* A_{1-b}, H_*, m_*, ni_* \rangle$) = 1, $\mathbb{G}_4^0$ runs $Ext_{SoK}(\lambda)$ on $\mathcal{A}$, in order to extract a witness $\eta$ for the proof $ni_*$ and sets $L'[\langle g, A_b, h_* A_{1-b}, H_*, m_*, ni_* \rangle] \leftarrow \eta$. Else it aborts, returning 0 (which leads Verify to output 0 for $sst_*$ in this case, since the SoKver algorithm will have returns 0). Following this, if $H_* \neq (h_* A_{1-b})^{L'[\langle g, A_b, h_* A_{1-b}, H_*, m_*, ni_* \rangle]}$ or if $A_b \neq g^{L'[\langle g, A_b, h_* A_{1-b}, H_*, m_*, ni_* \rangle]}$, then $\mathbb{G}_4^0$ aborts and returns 0.

In this game we pointed out the probability of $Ext_{SoK}$ failing to extract a valid witness when it is called in any of the (at most) $q_S$ calls. We thus obtain:

$$ |\mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_3^0) - \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_4^0)| \le q_S \cdot \epsilon_{\text{SoK}}(\lambda). $$
To conclude this branch of the game schedule, we now show that $\mathcal{A}$ always loses the game $\mathbb{G}_4^0$ against the KeyExtract algorithm we build. For that we reason through the absurd and we assume that the adversary $\mathcal{A}$ wins the game $\mathbb{G}_4^0$ with a non-zero probability. Denoting $(j_*, \text{sst}_*, l_*, R_*, \text{Prox}_*, (\Lambda_{*,q}, \Lambda_{*,q}.\text{td})_{q=1}^n)$ the guess of $\mathcal{A}$, we parse $\pi_{\text{Prox}_*}^{j_*}$.tr as $\text{MCS}\|g^x\|C_l\|\text{EAD}_1\|g^y\|c_2\|c_3\|H_l\|n_i\|S_l\|c_4\|n_r\|\text{val}\|\text{TH}_5\|\text{sst}_l$ (or as $\text{MCS}\|g^x\|C_l\|\text{EAD}_1\|g^y\|c_2\|c_3\|c_4\|H_R\|n_i\|S_R\|n_r\|\text{val}\|\text{TH}_5\|\text{sst}_R$ depending on the point of view), $\pi_{\text{Prox}_*}^{j_*}$.PNID as $(l, R)$ and $\pi_{\text{Prox}_*}^{j_*}$.AID as $(\Lambda_q)_{q=1}^n$. On the other hand, we parse $\text{sst}_*$ as $(\Lambda_{*,q})_{q=1}^n\|\text{ID}_*\|\text{MCS}_*\|X_*\|Y_*\|\text{TH}_2_*\|\text{TH}_3_*\|\text{TH}_4_*\|M_1_*\|m_2_*\|m_3_*\|H_*\|n_i\|\text{pid}_*\|n_{r_*}\|\text{val}_*\|\sigma_*$. Thanks to the game $\mathbb{G}_2$, we know that $\pi_{\text{Prox}_*}^{j_*}$.sid = $(C_{l,*}, C_{R,*}, X_*, Y_*)$, $\pi_{\text{Prox}_*}^{j_*}$.PNID = $(l_*, R_*)$ and $\pi_{\text{Prox}_*}^{j_*}$.AID = $(\Lambda_{*,q})_{q=1}^n$, which implies that:

$$X_* = X \text{ and } Y_* = Y, \quad l_* = l, R_* = R, \text{ and } (\Lambda_q)_{q=1}^n = (\Lambda_{*,q})_{q=1}^n.$$

By construction, the KeyExtract algorithm returns $(\text{PRK}_{\text{out}}$ but temporarily) $k = (g^x)^y = X^y$ where $Y = g^y$. At this point, note that an ambiguous element is $n_{r*}$. Indeed, $\mathcal{A}$ may have compute a key with some random $n_r$ and return a false $n'_r$ to the proxy which stores this value in $\text{sst}_*$. This is always possible, but useless for the adversary. Indeed, since our proxy is supposed to be honest, he will perform the test $\text{TH}_5 = \mathcal{H}(\text{TH}_{4*}, \text{val}_*, n_{r*})$ to check that he received the correct $n_{r*}$ (the proxy has compute himself $\text{TH}_4$, and if he couldn't the session would not have run until the end, so we would have IdentifySession returning 0). Despite this test, $\mathcal{A}$ may still compute $\text{PRK}_{\text{out}}$ with another random. But in this situation, this computed key $\text{PRK}_{\text{out}}$ is not valid or useless since only computable by one endpoint. And, in anyway, the Open algorithm checks this problem with $\text{val}_*$, $n_{r*}$ and $k$, returning $\perp$ if $\mathcal{A}$ cheats on this value and making $\mathcal{A}$ loosing the game in this situation. So we now assume that $n_{r*}$ is not a fake value. We set $h \leftarrow \prod_{q=1}^n \Lambda_q \cdot \text{pk}$ and $m_* = (\Lambda_q)_{q=1}^n\|\text{ID}_*\|\text{pid}_*\|\text{TH}_2_*\|\text{TH}_3_*\|\text{TH}_4_*$. We also define $a_0$ and $a_1$ so that $A_b = g^{a_b}$.

Running the Open algorithm on input $(\text{pp}, \text{sst}_*, (\Lambda_{*,q}.\text{td})_{q=1}^{n_*}, (\Lambda_{*,q}.\text{PK})_{q=1}^{n_*})$ gives us:

$$ \begin{align*} k_* &= \frac{H_*}{\prod_{q=1}^{n_*} \Lambda_{*,q}.\text{td}_1} = \frac{(h_* A_{1-b})^{L'[(g, A_b, h_* A_{1-b}, H_*, m_*, n_i)]}}{\prod_{q=1}^{n_*} A_b^{L[\Lambda_{*,q}.\text{td}]}} \\ &= \frac{h_*^{L'[(g, A_b, h_* A_{1-b}, H_*, m_*, n_i)]} (g^{a_{1-b}})^{L'[(g, A_b, h_* A_{1-b}, H_*, m_*, n_i)]}}{\prod_{q=1}^{n_*} g^{a_b L[\Lambda_{*,q}.\text{td}]}} \\ &= \frac{\left(\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{L'[(g, A_b, h_* A_{1-b}, H_*, m_*, n_i)]}\right) A_b^{a_{1-b}}}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{a_b}} \\ &= \frac{\left(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q}.\text{SK})L'[(g, A_b, h_* A_{1-b}, H_*, m_*, n_i)]}\right) k}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{a_b}} \\ &= \frac{\left(\prod_{q=1}^{n_*} A_b^{(\Lambda_{*,q}.\text{SK})}\right) k}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{a_b}} = k \end{align*} $$

This implies that $k_* = k$ (and thus $\text{PRK}_{\text{out}*} = \text{PRK}_{\text{out}}$ (note that $\mathcal{A}$ cannot cheat on transcript hashes $\text{TH}_*$ by returning different ones in $\text{sst}_*$ from those used in the protocol (and stored in tr), otherwise Verify detects it and $\mathcal{A}$ looses) with probability 1, and so $\mathcal{A}$ fails the game $\mathbb{G}_4^0$. Absurd! So $\mathcal{A}$ always fails the game $\mathbb{G}_4^0$, and thus we have:

$$\mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_4^0) = 0.$$

† **Game $\mathbb{G}_4^1$**: Again we denote by $\text{Ext}_{\text{SoK}}$ be the extractor of the signature of knowledge. This game has the same purpose as $\mathbb{G}_4^0$, and works as the previous one, except that it starts by initializing an empty list $L'[]' \leftarrow \emptyset$ and:
Each time the oSend oracle generates an SoK: ni ← SoK<sub>m</sub>{z, (Z = g<sup>z</sup> ∧ H = (hY)<sup>z</sup>) ∧ H<sup>1</sup> = (hR)<sup>z</sup>}, it sets L'[[(g, Z, hY, H, hR, H<sup>1</sup>, m, ni)] ← z (or ni ← SoK<sub>m</sub>{(z, z'), (Z = g<sup>z</sup> ∧ H = (hX)<sup>z</sup>) ∧ Z' = g<sup>z'</sup> ∧ H<sup>1</sup> = (hX)<sup>z'</sup>}, it sets L'[[(g, Z, hX, H, Z', hX, H<sup>1</sup>, m, ni)] ← (z, z'), depending on the side we consider (but this does not impact the analysis));

After A returns its guess, $\mathbb{G}_4^1$ sets $\omega_* \leftarrow (\Lambda_{*,q})_{q=1}^n \|\mathrm{ID}_*$ (either $\mathrm{ID}_{I_*}$ or $\mathrm{ID}_{R_*}$) and parses $\mathrm{sst}_*$ as $\omega_* \| \mathrm{MCS}_* \| X_* \| Y_* \| R_* \| \mathrm{TH}_{2*} \| \mathrm{TH}_{3*} \| \mathrm{TH}_{4*} \| M_{1*} \| m_{2*} \| m_{3*} \| \mathrm{H}_*^1 \| \mathrm{ni}_* \| \mathrm{pid}_* \| n_{r*} \| \mathrm{val}_* \| \sigma_*$ (with $\mathrm{pid}_*$ either $\mathrm{ID}_{R_*}$ or $\mathrm{ID}_{I_*}$), sets $A_0 \leftarrow X_*$ and $A_1 \leftarrow Y_*$, parses $\Lambda_{*,q}$.PK $\in \Lambda_{*,q}$.PK as $(\Lambda_{*,q}.\mathrm{pk}, \Lambda_{*,q}.\mathrm{ni})$ and $\Lambda_{*,q}$.td as $(\Lambda_{*,q}.\mathrm{td}_0, \Lambda_{*,q}.\mathrm{td}_1, \Lambda_{*,q}.\mathrm{td}_2)$, and sets $h_* \leftarrow \prod_{q=1}^n \Lambda_{*,q}.\mathrm{pk}$. If $L'[[(g, X_*, h_*Y_*, H_*, h_*R_*, H_*^1, m_*, ni_*)] = \perp$ (or $L'[[(g, Y_*, h_*X_*, H_*, R_*, h_*X_*, H_*^1, m_*, ni_*)] = \perp$), then:

* If SoKver($m_*$, (g, $X_*$, $h_*Y_*$, $H_*$, $R_*$, $h_*R_*$, $H_*^1$), $ni_*$) = 1 (or if SoKver($m_*$, (g, $Y_*$, $h_*X_*$, $H_*$, $R_*$, $h_*X_*$, $H_*^1$), $ni_*$) = 1), $\mathbb{G}_4^1$ runs $\mathrm{Ext}_{\mathrm{SOK}}(\lambda)$ on $\mathcal{A}$, in order to extract a witness $\eta$ (or witnesses $(\eta, \eta')$ for the proof $ni_*$ and sets $L'[[(g, X_*, h_*Y_*, H_*, h_*R_*, H_*^1, m_*, ni_*)] \leftarrow \eta$ (or $L'[[(g, Y_*, h_*X_*, H_*, R_*, h_*X_*, H_*^1, m_*, ni_*)] \leftarrow (\eta, \eta')]$). Else it aborts, returning 0 (for the same reason, in this situation Verify fails on $\mathrm{sst}_*$);

* Following this, if $H_* \neq (h_*Y_*)^{L'[[(g, X_*, h_*Y_*, H_*, h_*R_*, H_*^1, m_*, ni_*)]]}$ or if $H_*^1 \neq (h_*R_*)^{L'[[(g, X_*, h_*Y_*, H_*, h_*R_*, H_*^1, m_*, ni_*)]]}$ or if $X_* \neq g^{L'[[(g, X_*, h_*Y_*, H_*, h_*R_*, H_*^1, m_*, ni_*)]]}$ (i.e., extraction fails) (or if $H_* \neq (h_*X_*)^{L'[[(g, Y_*, h_*X_*, H_*, R_*, h_*X_*, H_*^1, m_*, ni_*)]]}$) or if $H_*^1 \neq (h_*X_*)^{L'[[(g, Y_*, h_*X_*, H_*, R_*, h_*X_*, H_*^1, m_*, ni_*)]]}$ or if $Y_* \neq g^{L'[[(g, Y_*, h_*X_*, H_*, R_*, h_*X_*, H_*^1, m_*, ni_*)]]}$ or if $R_* \neq g^{L'[[(g, Y_*, h_*X_*, H_*, R_*, h_*X_*, H_*^1, m_*, ni_*)]]}$, then $\mathbb{G}_4^1$ aborts and returns 0.

Again, with this game we pointed out the probability of $\mathrm{Ext}_{\mathrm{SOK}}$ failing to extract valid witness(es) in any of (at most) $q_S$ calls. We thus deduce that:

$$ \left| \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_3^1) - \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_4^1) \right| \le q_S \cdot \epsilon_{\mathrm{SOK}}(\lambda). $$

As previously, to conclude this branch of the game schedule, we now show that $\mathcal{A}$ always loses the game $\mathbb{G}_4^1$ against the KeyExtract algorithm we build. For that we reason through the absurd and we assume that the adversary $\mathcal{A}$ wins the game $\mathbb{G}_4^1$ with a non-zero probability. Denoting $(j_*, \mathrm{sst}_*, I_*, R_*, \mathrm{Prox}_*, (\Lambda_{*,q}, \Lambda_{*,q}.\mathrm{td})_{q=1}^n)$ the guess of $\mathcal{A}$, we parse $\pi_{\mathrm{Prox}_*}^{j_*}$.tr as $\mathrm{MCS}\|g^x\|C_I\|\mathrm{EAD}_1\|g^y\|c_2\|c_3\|H_I\|H_I^1\|ni_I\|S_I\|c_4\|n_r\|\mathrm{val}\|\mathrm{TH}_5\|\mathrm{sst}_I$ (or as $\mathrm{MCS}\|g^x\|C_I\|\mathrm{EAD}_1\|g^y\|c_2\|c_3\|c_4\|H_R\|H_R^1\|ni_R\|S_R\|n_r\|\mathrm{val}\|\mathrm{TH}_5\|\mathrm{sst}_R$ depending on the point of view), $\pi_{\mathrm{Prox}_*}^{j_*}$.PNID as $(I, R)$ and $\pi_{\mathrm{Prox}_*}^{j_*}$.AID as $(\Lambda_q)_{q=1}^n$. On the other hand, we parse $\mathrm{sst}_*$ as $(\Lambda_{*,q})_{q=1}^n \|\mathrm{ID}_* \| \mathrm{MCS}_* \| X_* \| Y_* \| R_* \| \mathrm{TH}_{2*} \| \mathrm{TH}_{3*} \| \mathrm{TH}_{4*} \| M_{1*} \| m_{2*} \| m_{3*} \| \mathrm{H}_* \| \mathrm{H}_*^1 \| \mathrm{ni}_* \| \mathrm{pid}_* \| n_{r*} \| \mathrm{val}_* \| \sigma_*$.

Thanks to the game $\mathbb{G}_2$, we know that $\pi_{\mathrm{Prox}_*}^{j_*}$.sid = $(C_{I_*}, C_{R_*}, X_*, Y_*)$, $\pi_{\mathrm{Prox}_*}^{j_*}$.PNID = $(I_*, R_*)$ and $\pi_{\mathrm{Prox}_*}^{j_*}$.AID = $(\Lambda_{*,q})_{q=1}^n$, which implies that:

$$ X_* = X \text{ and } Y_* = Y, \quad I_* = I, \quad R_* = R, \text{ and } (\Lambda_q)_{q=1}^n = (\Lambda_{*,q})_{q=1}^n $$

and note that since $R_* = R$, we also have $R_* = R$.

By construction, the KeyExtract algorithm returns $(\mathrm{PRK}_{\mathrm{out}}$ but temporarily) $k = (g^x)^y = X^y$ where $Y = g^y$ and $k' = (g^x)^r = X^r$ where $R = g^r$. At this point, as in $\mathbb{G}_4^0$, we have the same ambiguity on $n_r$, and we solved it in the same way. We set $h \leftarrow \prod_{q=1}^n \Lambda_q$.pk and $m_* = (\Lambda_q)_{q=1}^n \|\mathrm{ID}_* \| \mathrm{pid}_* \| \mathrm{TH}_{2*} \| \mathrm{TH}_{3*} \| \mathrm{TH}_{4*}$. We also define $a_0$ and $a_1$ so that $A_b = g^{a_b}$ and $r_1$ so that $R_* = g^{r_1}$.
Running the Open algorithm on input $(pp, sst_*, (\Lambda_{*,q}.\text{td})_{q=1}^{n_*}, (\Lambda_{*,q}.\text{PK})_{q=1}^{n_*})$ gives us:

$$
\begin{align*}
k_* &= \frac{H_*}{\prod_{q=1}^{n_*} \Lambda_{*,q}.\text{td}_1} = \frac{(h_* Y_*)^{L'[(g,X_*,h_* Y_*,H_*,h_* R_*,H_*^1,m_*,ni_*)]}}{\prod_{q=1}^{n_*} X_*^{L[\Lambda_{*,q}.\text{td}]}} \\
&= \frac{h_*^{L'[(g,X_*,h_* Y_*,H_*,h_* R_*,H_*^1,m_*,ni_*)]}(g^{a_1})^{L'[(g,X_*,h_* Y_*,H_*,h_* R_*,H_*^1,m_*,ni_*)]}}{\prod_{q=1}^{n_*} g^{a_0 L[\Lambda_{*,q}.\text{td}]}} \\
&= \frac{(\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{L'[(g,X_*,h_* Y_*,H_*,h_* R_*,H_*^1,m_*,ni_*)]}) X_*^{a_1}}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{a_0}} \\
&= \frac{(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q}.\text{SK})L'[(g,X_*,h_* Y_*,H_*,h_* R_*,H_*^1,m_*,ni_*)]}) k}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{a_0}} \\
&= \frac{(\prod_{q=1}^{n_*} X_*^{(\Lambda_{*,q}.\text{SK})}) k}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{a_0}} = k
\end{align*}
$$

and

$$
\begin{align*}
k'_* &= \frac{H_*^1}{\prod_{q=1}^{n_*} \Lambda_{*,q}.\text{td}_1} = \frac{(h_* R_*)^{L'[(g,X_*,h_* Y_*,H_*,h_* R_*,H_*^1,m_*,ni_*)]}}{\prod_{q=1}^{n_*} X_*^{L[\Lambda_{*,q}.\text{td}]}} \\
&= \frac{h_*^{L'[(g,X_*,h_* Y_*,H_*,h_* R_*,H_*^1,m_*,ni_*)]}(g^{r_1})^{L'[(g,X_*,h_* Y_*,H_*,h_* R_*,H_*^1,m_*,ni_*)]}}{\prod_{q=1}^{n_*} g^{a_0 L[\Lambda_{*,q}.\text{td}]}} \\
&= \frac{(\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{L'[(g,X_*,h_* Y_*,H_*,h_* R_*,H_*^1,m_*,ni_*)]}) X_*^{r_1}}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{a_0}} \\
&= \frac{(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q}.\text{SK})L'[(g,X_*,h_* Y_*,H_*,h_* R_*,H_*^1,m_*,ni_*)]}) k'}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{a_0}} \\
&= \frac{(\prod_{q=1}^{n_*} X_*^{(\Lambda_{*,q}.\text{SK})}) k'}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{a_0}} = k'
\end{align*}
$$

if we are on the Initiator point of view, or, if we are the Responder point of view:

$$
\begin{align*}
k_* &= \frac{H_*}{\prod_{q=1}^{n_*} \Lambda_{*,q}.\text{td}_1} = \frac{(h_* X_*)^{L'[(g,Y_*,h_* X_*,H_*,R_*,h_* X_*,H_*^1,m_*,ni_*)]}[0]}{\prod_{q=1}^{n_*} Y_*^{L[\Lambda_{*,q}.\text{td}]}} \\
&= \frac{h_*^{L'[(g,Y_*,h_* X_*,H_*,R_*,h_* X_*,H_*^1,m_*,ni_*)]}(g^{a_0})^{L'[(g,Y_*,h_* X_*,H_*,R_*,h_* X_*,H_*^1,m_*,ni_*)]}[0]}{\prod_{q=1}^{n_*} g^{a_1 L[\Lambda_{*,q}.\text{td}]}} \\
&= \frac{(\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{L'[(g,Y_*,h_* X_*,H_*,R_*,h_* X_*,H_*^1,m_*,ni_*)]}[0]) Y_*^{a_0}}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{a_1}} \\
&= \frac{(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q}.\text{SK})L'[(g,Y_*,h_* X_*,H_*,R_*,h_* X_*,H_*^1,m_*,ni_*)]}[0]) k}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{a_1}} \\
&= \frac{(\prod_{q=1}^{n_*} Y_*^{(\Lambda_{*,q}.\text{SK})}) k}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.\text{pk})^{a_1}} = k
\end{align*}
$$
and

$$
\begin{align*}
k'_* &= \frac{H_*^1}{\prod_{q=1}^{n_*} \Lambda_{*,q} \cdot \text{td}_2} = \frac{(h_* X_*)^{L'[(g, Y_*, h_* X_*, H_*, R_*, h_* X_*, H_*^1, m_*, ni_*)]}[1]}{\prod_{q=1}^{n_*} R_*^{L[\Lambda_{*,q} \cdot \text{td}]}} \\
&= \frac{h_*^{L'[(g, Y_*, h_* X_*, H_*, R_*, h_* X_*, H_*^1, m_*, ni_*)]}[1] (g^{a_0})^{L'[(g, Y_*, h_* X_*, H_*, R_*, h_* X_*, H_*^1, m_*, ni_*)]}[1]}{\prod_{q=1}^{n_*} g^{r_1 L[\Lambda_{*,q} \cdot \text{td}]}} \\
&= \frac{\left( \prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{L'[(g, Y_*, h_* X_*, H_*, R_*, h_* X_*, H_*^1, m_*, ni_*)]}[1] \right) R_*^{a_0}}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{r_1}} \\
&= \frac{\left( \prod_{q=1}^{n_*} g^{(\Lambda_{*,q} \cdot \text{SK}) L'[(g, Y_*, h_* X_*, H_*, R_*, h_* X_*, H_*^1, m_*, ni_*)]}[1] \right) k'}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{r_1}} \\
&= \frac{\left( \prod_{q=1}^{n_*} R_*^{(\Lambda_{*,q} \cdot \text{SK})} \right) k'}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{r_1}} = k'
\end{align*}
$$

This implies that $k_* = k$ and $k'_* = k'$ (and thus $\text{PRK}_{\text{out}*} = \text{PRK}_{\text{out}}$) with probability 1, and so $\mathcal{A}$ fails the game $\mathbb{G}_4^1$. Absurd!

So $\mathcal{A}$ always fails the game $\mathbb{G}_4^1$, and thus we have:

$$ \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_4^1) = 0. $$

† **Game $\mathbb{G}_4^2$**: In a similar way as for previous games, we denote by $\text{Ext}_{\text{SOK}}$ the extractor of the signature of knowledge. Again this game is the same as the previous one, except that it starts by initializing an empty list $L'[ ] \leftarrow \emptyset$ and:

Each time the oSend oracle generates an SoK: $\text{ni} \leftarrow \text{SoK}_m\{(z, z'), (Z = g^z \wedge H = (hY)^z) \wedge Z' = g^{z'} \wedge H^1 = (hY)^{z'}\}$, it sets

$L'[(g, Z, hY, H, Z', hY, H^1, m, ni)] \leftarrow (z, z')$ (or $\text{ni} \leftarrow \text{SoK}_m\{z, (Z = g^z \wedge H = (hX)^z) \wedge H^1 = (hI)^z\}$, it sets $L'[(g, Z, hX, H, hI, H^1, m, ni)] \leftarrow z$ depending on the side we consider (but this does not impact the analysis));

After $\mathcal{A}$ returns its guess, $\mathbb{G}_4^2$ sets $\omega_* \leftarrow (\Lambda_{*,q})_{q=1}^n \|\text{ID}_*$ (either $\text{ID}_{I_*}$ or $\text{ID}_{R_*}$) and parses $\text{sst}_*$ as $\omega_* \|\text{MCS}_* \|X_* \|Y_* \|I_* \|\text{TH}_2 \|\text{TH}_3 \|\text{TH}_4 \|M_1 \|m_2 \|m_3 \|H_* \|H_*^1 \|\text{ni}_* \|\text{pid}_* \|n_{r*} \|\text{val}_* \|\sigma_*$ (with $\text{pid}_*$ either $\text{ID}_{R_*}$ or $\text{ID}_{I_*}$), sets $A_0 \leftarrow X_*$ and $A_1 \leftarrow Y_*$, parses $\Lambda_{*,q} \cdot \text{PK}$ as $(\Lambda_{*,q} \cdot \text{pk}, \Lambda_{*,q} \cdot \text{ni})$ and $\Lambda_{*,q} \cdot \text{td}$ as $(\Lambda_{*,q} \cdot \text{td}_0, \Lambda_{*,q} \cdot \text{td}_1, \Lambda_{*,q} \cdot \text{td}_2)$, and sets $h_* \leftarrow \prod_{q=1}^n \Lambda_{*,q} \cdot \text{pk}$.

If $L'[(g, X_*, h_* Y_*, H_*, I_*, h_* Y_*, H_*^1, m_*, ni_*)] = \perp$ (or $L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, ni_*)] = \perp$), then:

* If SoKver($m_*$, $(g, X_*, h_* Y_*, H_*, I_*, h_* Y_*, H_*^1$, $\text{ni}_*$) = 1$ (or if SoKver($m_*$, $(g, Y_*, h_* X_*, H_*, I_*, h_* I_*, H_*^1$, $\text{ni}_*$) = 1), $\mathbb{G}_4^2$ runs $\text{Ext}_{\text{SOK}}(\lambda)$ on $\mathcal{A}$ in order to extract witnesses $(\eta, \eta')$ (or a witness $\eta$) for the proof $\text{ni}_*$ and sets $L'[(g, X_*, h_* Y_*, H_*, I_*, h_* Y_*, H_*^1, m_*, \text{ni}_*)] \leftarrow (\eta, \eta')$ (or $L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, \text{ni}_*)] \leftarrow \eta$). Else it aborts, returning 0 (in this situation again Verify fails on $\text{sst}_*$);

* Following this, if $H_* \neq (h_* Y_*)^{L'[(g, X_*, h_* Y_*, H_*, I_*, h_* Y_*, H_*^1, m_*, \text{ni}_*)]}[0]$ or if $H_*^1 \neq (h_* Y_*)^{L'[(g, X_*, h_* Y_*, H_*, I_*, h_* Y_*, H_*^1, m_*, \text{ni}_*)]}[1]$ or if $X_* \neq g^{L'[(g, X_*, h_* Y_*, H_*, I_*, h_* Y_*, H_*^1, m_*, \text{ni}_*)]}[0]$ or if $I_* \neq g^{L'[(g, X_*, h_* Y_*, H_*, I_*, h_* Y_*, H_*^1, m_*, \text{ni}_*)]}[1]$ (i.e., extraction fails) (or if $H_* \neq (h_* X_*)^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, \text{ni}_*)]}[0]$ or if $H_*^1 \neq (h_* I_*)^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, \text{ni}_*)]}[0]$ or if $Y_* \neq g^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, \text{ni}_*)]}$), then $\mathbb{G}_4^2$ aborts and returns 0.
With this game hop, we again pointed out the probability of $Ext_{SOK}$ failing to extract valid witness(es) in any of (at most) $q_S$ calls. We thus have:

$$ \left| \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_3^2) - \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_4^2) \right| \le q_S \cdot \epsilon_{SOK}(\lambda). $$

Here again to conclude this branch of the game schedule, we show that $\mathcal{A}$ always loses the game $\mathbb{G}_4^2$ against the KeyExtract algorithm we build. For that we reason through the absurd and we assume that the adversary $\mathcal{A}$ wins the game $\mathbb{G}_4^2$ with a non-zero probability. Denoting $(j_*, sst_*, l_*, R_*, Prox_*, (\Lambda_{*,i}, \Lambda_{*,q}.td)_{q=1}^n)$ the guess of $\mathcal{A}$, we parse $\pi_{Prox_*}^{j_*}$.tr as MCS$\|g^x\|C_1\|EAD_1\|g^y\|C_2\|C_3\|H_1\|H_1^1\|ni_1\|S_1\|C_4\|n_r\| val\|TH_5\|sst_1$ (or as MCS$\|g^x\|C_1\|EAD_1\|g^y\|C_2\|C_3\|C_4\|H_R\|H_R^1\|ni_R\|S_R\|n_r\|val\|TH_5\|sst_R$ depending on the point of view), $\pi_{Prox_*}^{j_*}$.PNID as $(l, R)$ and $\pi_{Prox_*}^{j_*}$.AID as $(\Lambda_q)_{q=1}^n$. On the other hand, we parse $sst_*$ as $(\Lambda_{*,q})_{q=1}^{n_*}\|ID_*\|MCS_*\|X_*\|Y_*\|I_*\|TH_2\|TH_3\|TH_4\|M1_*\|m2_*\|m3_*\|H_*\|H_*^1\|ni_*\|pid_*\|n_{r*}\|val_*\|\sigma_*$.

Thanks to the game $\mathbb{G}_2$, we know that $\pi_{Prox_*}^{j_*}$.sid = $(C_{l_*}, C_{R_*}, X_*, Y_*)$, $\pi_{Prox_*}^{j_*}$.PNID = $(l_*, R_*)$ and $\pi_{Prox_*}^{j_*}$.AID = $(\Lambda_{*,q})_{q=1}^{n_*}$, which implies that:

$$ X_* = X \text{ and } Y_* = Y, \quad l_* = l, R_* = R, \text{ and } (\Lambda_q)_{m=1}^n = (\Lambda_{*,q})_{q=1}^{n_*} $$

and note that since $l_* = l$, we also have $I_* = I$. By construction, the KeyExtract algorithm returns $(PRK_{out}$ but temporarily) $k = (g^x)^y = X^y$ where $Y = g^y$ and $k' = (g^y)^i = Y^i$ where $I = g^i$. At this point, as in $\mathbb{G}_4^0$, we have the same ambiguity on $n_r$, and we solve it in the same way. We set $h \leftarrow \prod_{q=1}^n \Lambda_q$.pk and $m_* = (\Lambda_q)_{q=1}^n\|ID_*\|pid_*\|TH_2\|TH_3\|TH_4$. We also define $a_0$ and $a_1$ so that $A_b = g^{a_b}$ and $i_1$ so that $I_* = g^{i_1}$.

Running the Open algorithm on input $(pp, sst_*, (\Lambda_{*,q}.td)_{q=1}^{n_*}, (\Lambda_{*,q}.PK)_{q=1}^{n_*})$ gives us:

$$
\begin{align*}
k_* &= \frac{H_*}{\prod_{q=1}^{n_*} \Lambda_{*,q}.td_1} = \frac{(h_* Y_*)^{L'[(g, X_*, h_* Y_*, H_* , I_*, h_* Y_*, H_*^1, m_*, ni_*)][0]}}{\prod_{q=1}^{n_*} X_*^{L[\Lambda_{*,q}.td]}} \\
&= \frac{h_*^{L'[(g, X_*, h_* Y_*, H_* , I_*, h_* Y_*, H_*^1, m_*, ni_*)][0]} (g^{a_1})^{L'[(g, X_*, h_* Y_*, H_* , I_*, h_* Y_*, H_*^1, m_*, ni_*)][0]}}{\prod_{q=1}^{n_*} g^{a_0 L[\Lambda_{*,q}.td]}} \\
&= \frac{\left(\prod_{q=1}^{n_*} (\Lambda_{*,q}.pk)^{L'[(g, X_*, h_* Y_*, H_* , I_*, h_* Y_*, H_*^1, m_*, ni_*)][0]}\right) X_*^{a_1}}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.pk)^{a_0}} \\
&= \frac{\left(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q}.SK)^{L'[(g, X_*, h_* Y_*, H_* , I_*, h_* Y_*, H_*^1, m_*, ni_*)][0]}}\right) k}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.pk)^{a_0}} \\
&= \frac{\left(\prod_{q=1}^{n_*} X_*^{(\Lambda_{*,q}.SK)}\right) k}{\prod_{q=1}^{n_*} (\Lambda_{*,q}.pk)^{a_0}} = k
\end{align*}
$$
and

$$
\begin{align*}
k'_* &= \frac{H_*^1}{\prod_{q=1}^{n_*} \Lambda_{*,q} \cdot \text{td}_2} = \frac{(h_* Y_*)^{L'[(g, X_*, h_* Y_*, H_*, I_*, h_* Y_*, H_*^1, m_*, ni_*)]}[1]}{\prod_{q=1}^{n_*} I_*^{L[\Lambda_{*,q} \cdot \text{td}]}} \\
&= \frac{h_*^{L'[(g, X_*, h_* Y_*, H_*, I_*, h_* Y_*, H_*^1, m_*, ni_*)]}[1] (g^{a_1})^{L'[(g, X_*, h_* Y_*, H_*, I_*, h_* Y_*, H_*^1, m_*, ni_*)]}[1]}{\prod_{q=1}^{n_*} g^{i_1 L[\Lambda_{*,q} \cdot \text{td}]} \\
&= \frac{\left(\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{L'[(g, X_*, h_* Y_*, H_*, I_*, h_* Y_*, H_*^1, m_*, ni_*)]}[1]\right) I_*^{a_1}}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{i_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q} \cdot \text{SK}) L'[(g, X_*, h_* Y_*, H_*, I_*, h_* Y_*, H_*^1, m_*, ni_*)]}[1]\right) k'}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{i_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} I_*^{(\Lambda_{*,q} \cdot \text{SK})}\right) k'}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{i_1}} = k'
\end{align*}
$$

if we are on the Initiator point of view, or, if we are the Responder point of view:

$$
\begin{align*}
k_* &= \frac{H_*}{\prod_{q=1}^{n_*} \Lambda_{*,q} \cdot \text{td}_1} = \frac{(h_* X_*)^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, ni_*)]}}{\prod_{q=1}^{n_*} Y_*^{L[\Lambda_{*,q} \cdot \text{td}]}} \\
&= \frac{h_*^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, ni_*)]} (g^{a_0})^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, ni_*)]}}{\prod_{q=1}^{n_*} g^{a_1 L[\Lambda_{*,q} \cdot \text{td}]}} \\
&= \frac{\left(\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, ni_*)]}\right) Y_*^{a_0}}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{a_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q} \cdot \text{SK}) L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, ni_*)]}\right) k}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{a_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} Y_*^{(\Lambda_{*,q} \cdot \text{SK})}\right) k}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{a_1}} = k
\end{align*}
$$

and

$$
\begin{align*}
k'_* &= \frac{H_*^1}{\prod_{q=1}^{n_*} \Lambda_{*,q} \cdot \text{td}_1} = \frac{(h_* I_*)^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, ni_*)]}}{\prod_{q=1}^{n_*} Y_*^{L[\Lambda_{*,q} \cdot \text{td}]}} \\
&= \frac{h_*^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, ni_*)]} (g^{i_1})^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, ni_*)]}}{\prod_{q=1}^{n_*} g^{a_1 L[\Lambda_{*,q} \cdot \text{td}]}} \\
&= \frac{\left(\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, ni_*)]}\right) Y_*^{i_1}}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{a_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q} \cdot \text{SK}) L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, m_*, ni_*)]}\right) k'}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{a_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} Y_*^{(\Lambda_{*,q} \cdot \text{SK})}\right) k'}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{a_1}} = k'
\end{align*}
$$
This implies that $k_* = k$ and $k'_* = k'$ (and thus $\text{PRK}_{\text{out}*} = \text{PRK}_{\text{out}}$) with probability 1, and so $\mathcal{A}$ fails the game $\mathbb{G}_4^2$. Absurd!

So $\mathcal{A}$ always fails the game $\mathbb{G}_4^2$, and thus we obtain that:

$$ \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_4^2) = 0. $$

† **Game $\mathbb{G}_4^3$**: For the last time, we consider $\text{Ext}_{\text{SOK}}$ the extractor of the signature of knowledge. Always to prevent the adversary from providing a false signature of knowledge, this game is the same as the previous one, except that it starts by initializing an empty list $L'[\,] \leftarrow \emptyset$ and:

Each time the oSend oracle generates an SoK: $\text{ni} \leftarrow \text{SoK}_m\{(z, z'), (Z = g^z \wedge H = (hA)^z) \wedge H^1 = (hB)^z \wedge Z' = g^{z'} \wedge H^2 = (hA)^{z'}\}$ (with $\mathcal{A}$ the ephemeral DH shared element, and $\mathcal{B}$ the long term static DH element of the endpoint considered), it sets $L'[\langle g, Z, hA, H, hB, H^1, Z', hA, H^2, m, ni \rangle] \leftarrow (z, z')$;

After $\mathcal{A}$ returns its guess, $\mathbb{G}_4^3$ sets $\omega_* \leftarrow (\Lambda_{*,q})_{q=1}^n \|\text{ID}_* \text{ (either } \text{ID}_{I_*} \text{ or } \text{ID}_{R_*}\text{)}$ and parses $\text{sst}_*$ as $\omega_* \|\text{MCS}_* \|X_* \|Y_* \|R_* \|I_* \|\text{TH}_{2*} \|\text{TH}_{3*} \|\text{TH}_{4*} \|M_{1*} \|m_{2*} \|m_{3*} \|\text{H}_*^1 \|\text{H}_*^2 \|\text{ni}_* \|\text{pid}_* \|n_{r*} \|\text{val}_* \|\sigma_* \text{ (with } \text{pid}_* \text{ either } \text{ID}_{R_*} \text{ or } \text{ID}_{I_*}\text{), sets } A_0 \leftarrow X_* \text{ and } A_1 \leftarrow Y_{*}, \text{ and sets } B_0 \leftarrow I_* \text{ and } B_1 \leftarrow R_* \text{, parses } \Lambda_{*,q} \text{PK as } (\Lambda_{*,q} \text{pk}, \Lambda_{*,q} \text{ni}) \text{ and } \Lambda_{*,q} \text{td as } (\Lambda_{*,q} \text{td}_0, \Lambda_{*,q} \text{td}_1, \Lambda_{*,q} \text{td}_2), \text{ and sets } h_* \leftarrow \prod_{q=1}^n \Lambda_{*,q} \text{pk.}}

If $L'[\langle g, A_{b*}, h_*A_{1-b*}, H_*, h_*B_{1-b*}, H_1^*, B_{b*}, h_*A_{1-b*}, H_2^*, m_*, ni_* \rangle] = \perp$, then:

* If $\text{SoKver}(m_*, (g, A_{b*}, h_*A_{1-b*}, H_*, h_*B_{1-b*}, H_1^*, B_{b*}, h_*A_{1-b*}, H_2^*), ni_*) = 1$, $\mathbb{G}_4^3$ runs $\text{Ext}_{\text{SOK}}(\lambda)$ on $\mathcal{A}$, extracting witnesses $(\eta, \eta')$ for the proof $ni_*$ and sets $L'[\langle g, A_{b*}, h_*A_{1-b*}, H_*, h_*B_{1-b*}, H_1^*, B_{b*}, h_*A_{1-b*}, H_2^*, m_*, ni_* \rangle] \leftarrow (\eta, \eta')$. Else it aborts, returning 0 (here again we have that Verify fails on $\text{sst}_*$ for the same reason);

* If $H_* \neq (h_*A_{1-b*})^{L'[\langle g, A_{b*}, h_*A_{1-b*}, H_*, h_*B_{1-b*}, H_1^*, B_{b*}, h_*A_{1-b*}, H_2^*, m_*, ni_* \rangle][0]}$ or if $H_1^* \neq (h_*B_{1-b*})^{L'[\langle g, A_{b*}, h_*A_{1-b*}, H_*, h_*B_{1-b*}, H_1^*, B_{b*}, h_*A_{1-b*}, H_2^*, m_*, ni_* \rangle][0]}$ or if $H_2^* \neq (h_*A_{1-b*})^{L'[\langle g, A_{b*}, h_*A_{1-b*}, H_*, h_*B_{1-b*}, H_1^*, B_{b*}, h_*A_{1-b*}, H_2^*, m_*, ni_* \rangle][1]}$ or if $A_{b*} \neq g^{L'[\langle g, A_{b*}, h_*A_{1-b*}, H_*, h_*B_{1-b*}, H_1^*, B_{b*}, h_*A_{1-b*}, H_2^*, m_*, ni_* \rangle][0]}$ or if $B_{b*} \neq g^{L'[\langle g, A_{b*}, h_*A_{1-b*}, H_*, h_*B_{1-b*}, H_1^*, B_{b*}, h_*A_{1-b*}, H_2^*, m_*, ni_* \rangle][1]}$ (i.e., extraction fails), then $\mathbb{G}_4^3$ aborts and returns 0.

For the last time, with this game we pointed out the probability of $\text{Ext}_{\text{SOK}}$ failing to extract valid witnesses in any of (at most) $q_S$ calls. We thus obtain:

$$ \left| \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_3^3) - \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_4^3) \right| \le q_S \cdot \epsilon_{\text{SOK}}(\lambda). $$

To conclude this branch of the game schedule (and the proof), we again show that $\mathcal{A}$ always loses the game $\mathbb{G}_4^3$ against the KeyExtract algorithm we build. For that we reason through the absurd and we assume that the adversary $\mathcal{A}$ wins the game $\mathbb{G}_4^3$ with a non-zero probability. Denoting $(j_*, \text{sst}_*, I_*, R_*, \text{Prox}_*, (\Lambda_{*,q}, \Lambda_{*,q} \text{td})_{q=1}^n)$ the guess of $\mathcal{A}$, we parse $\pi_{\text{Prox}_*}^{j_*} \cdot \text{tr}$ as $\text{MCS} \|g^x \|C_I \|\text{EAD}_1 \|g^y \|C_2 \|c_3 \|H_I \|H_I^1 \|H_I^2 \|\text{ni}_I \|S_I \|c_4 \|n_r \|\text{val} \|\text{TH}_5 \|\text{sst}_I$ (or as $\text{MCS} \|g^x \|C_I \|\text{EAD}_1 \|g^y \|C_2 \|c_3 \|c_4 \|H_R \|H_R^1 \|H_R^2 \|\text{ni}_R \|S_R \|n_r \|\text{val} \|\text{TH}_5 \|\text{sst}_R$ depending on the point of view), $\pi_{\text{Prox}_*}^{j_*} \cdot \text{PNID}$ as $(I, R)$ and $\pi_{\text{Prox}_*}^{j_*} \cdot \text{AID}$ as $(\Lambda_q)_{q=1}^n$. On the other hand, we parse $\text{sst}_*$ as $\omega_* \|\text{MCS}_* \|X_* \|Y_* \|R_* \|I_* \|\text{TH}_{2*} \|\text{TH}_{3*} \|\text{TH}_{4*} \|M_{1*} \|m_{2*} \|m_{3*} \|H_*^1 \|H_*^2 \|\text{ni}_* \|\text{pid}_* \|n_{r*} \|\text{val}_* \|\sigma_*$. Thanks to the game $\mathbb{G}_2$, we know that $\pi_{\text{Prox}_*}^{j_*} \cdot \text{sid} = (C_{I_*}, C_{R_*}, X_*, Y_*)$, $\pi_{\text{Prox}_*}^{j_*} \cdot \text{PNID} = (I_*, R_*)$ and $\pi_{\text{Prox}_*}^{j_*} \cdot \text{AID} = (\Lambda_{*,q})_{q=1}^n$, which implies that:

$$ X_* = X, Y_* = Y, I_* = I, R_* = R, \text{ and } (\Lambda_q)_{q=1}^n = (\Lambda_{*,q})_{q=1}^n $$
and note that since $l_* = l$ and $R_* = R$, we have $I_* = I$ and $R_* = R$. By construction, the KeyExtract algorithm returns (PRK<sub>out</sub> but temporarily) $k = (g^x)^y = X^y$ where $Y = g^y$ and $k' = (g^x)^r = X^r$ where $R = g^r$ and $k'' = (g^y)^i = Y^i$ where $I = g^i$. As in the three previous games, we have the same ambiguity with element $n_r$, and we solve it in the same way. We set $h \leftarrow \prod_{q=1}^n \Lambda_q \cdot \text{pk}$ and $m_* = (\Lambda_q)_{q=1}^n \|\text{ID}_*\| \text{pid}_* \|\text{TH}_2*\| \|\text{TH}_3*\| \|\text{TH}_4*$. We also define $a_0$ and $a_1$ so that $A_b = g^{a_b}$, $r_1$ so that $R_* = g^{r_1}$ and $i_1$ so that $I_* = g^{i_1}$.

Running the Open algorithm on input $(\text{pp}, \text{sst}_*, (\Lambda_{*,q} \cdot \text{td})_{q=1}^{n_*}, (\Lambda_{*,q} \cdot \text{PK})_{q=1}^{n_*})$ gives us:

$$
\begin{align*}
k_* &= \frac{H_*}{\prod_{q=1}^{n_*} \Lambda_{*,q} \cdot \text{td}_1} = \frac{(h_* A_{1-b_*})^{\text{L}'[(g, A_{b_*}, h_* A_{1-b_*}, H_*, h_* B_{1-b_*}, H_1^*, B_{b_*}, h_* A_{1-b_*}, H_2^*, m_*, ni_*)]}[0]}{\prod_{q=1}^{n_*} A_b^{\text{L}[\Lambda_{*,q} \cdot \text{td}]}} \\
&= \frac{(h_* g^{a_{1-b}})^{\text{L}'[(g, A_{b_*}, h_* A_{1-b_*}, H_*, h_* B_{1-b_*}, H_1^*, B_{b_*}, h_* A_{1-b_*}, H_2^*, m_*, ni_*)]}[0]}{\prod_{q=1}^{n_*} g^{a_b \text{L}[\Lambda_{*,q} \cdot \text{td}]}} \\
&= \frac{\left(\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{\text{L}'[(g, A_{b_*}, h_* A_{1-b_*}, H_*, h_* B_{1-b_*}, H_1^*, B_{b_*}, h_* A_{1-b_*}, H_2^*, m_*, ni_*)]}[0]\right) A_b^{a_{1-b}}}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{a_b}} \\
&= \frac{\left(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q} \cdot \text{SK}) \text{L}'[(g, A_{b_*}, h_* A_{1-b_*}, H_*, h_* B_{1-b_*}, H_1^*, B_{b_*}, h_* A_{1-b_*}, H_2^*, m_*, ni_*)]}[0]\right) k}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{a_b}} \\
&= \frac{\left(\prod_{q=1}^{n_*} A_b^{(\Lambda_{*,q} \cdot \text{SK})} k\right)}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{a_b}} = k
\end{align*}
$$

and if we are on the Initiator point of view we will have:

$$
\begin{align*}
k'_* &= \frac{H_*^1}{\prod_{q=1}^{n_*} \Lambda_{*,q} \cdot \text{td}_1} = \frac{(h_* R_*)^{\text{L}'[(g, X_*, h_* Y_*, H_*, h_* R_*, H_1^*, I_*, h_* Y_*, H_2^*, m_*, ni_*)]}[0]}{\prod_{q=1}^{n_*} X_*^{\text{L}[\Lambda_{*,q} \cdot \text{td}]}} \\
&= \frac{(h_* g^{r_1})^{\text{L}'[(g, X_*, h_* Y_*, H_*, h_* R_*, H_1^*, I_*, h_* Y_*, H_2^*, m_*, ni_*)]}[0]}{\prod_{q=1}^{n_*} g^{a_0 \text{L}[\Lambda_{*,q} \cdot \text{td}]}} \\
&= \frac{\left(\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{\text{L}'[(g, X_*, h_* Y_*, H_*, h_* R_*, H_1^*, I_*, h_* Y_*, H_2^*, m_*, ni_*)]}[0]\right) X_*^{r_1}}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{a_0}} \\
&= \frac{\left(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q} \cdot \text{SK}) \text{L}'[(g, X_*, h_* Y_*, H_*, h_* R_*, H_1^*, I_*, h_* Y_*, H_2^*, m_*, ni_*)]}[0]\right) k'}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{a_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} X_*^{(\Lambda_{*,q} \cdot \text{SK})} k'\right)}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot \text{pk})^{a_0}} = k'
\end{align*}
$$
and

$$
\begin{align*}
k_*'' &= \frac{H_*^2}{\prod_{q=1}^{n_*} \Lambda_{*,q} \cdot \text{td}_2} = \frac{(h_* Y_*)^{L'[(g, X_*, h_* Y_*, H_*, h_* R_*, H_*^1, I_*, h_* Y_*, H_*^2, m_*, ni_*)]}[1]}{\prod_{q=1}^{n_*} I_*^{L[\Lambda_{*,q} \cdot \text{td}]} \\
&= \frac{(h_* g^{a_1})^{L'[(g, X_*, h_* Y_*, H_*, h_* R_*, H_*^1, I_*, h_* Y_*, H_*^2, m_*, ni_*)]}[1]}{\prod_{q=1}^{n_*} g^{i_1 L[\Lambda_{*,q} \cdot \text{td}]} \\
&= \frac{\left(\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot LIpk)^{L'[(g, X_*, h_* Y_*, H_*, h_* R_*, H_*^1, I_*, h_* Y_*, H_*^2, m_*, ni_*)]}[1]\right) I_*^{a_1}}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot pk)^{i_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q} \cdot SK) L'[(g, X_*, h_* Y_*, H_*, h_* R_*, H_*^1, I_*, h_* Y_*, H_*^2, m_*, ni_*)]}[1]\right) k''}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot pk)^{i_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} I_*^{(\Lambda_{*,q} \cdot SK)}\right) k''}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot pk)^{i_1}} = k''
\end{align*}
$$

or if we are the Responder point of view we will have:

$$
\begin{align*}
k'_* &= \frac{H_*^2}{\prod_{q=1}^{n_*} \Lambda_{*,q} \cdot \text{td}_2} = \frac{(h_* X_*)^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, R_*, h_* X_*, H_*^2, m_*, ni_*)]}[1]}{\prod_{q=1}^{n_*} R_*^{L[\Lambda_{*,q} \cdot \text{td}]} \\
&= \frac{(g^{a_0})^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, R_*, h_* X_*, H_*^2, m_*, ni_*)]}[1]}{\prod_{q=1}^{n_*} g^{r_1 L[\Lambda_{*,q} \cdot \text{td}]} \\
&= \frac{\left(\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot pk)^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, R_*, h_* X_*, H_*^2, m_*, ni_*)]}[1]\right) R_*^{a_0}}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot pk)^{r_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q} \cdot SK) L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, R_*, h_* X_*, H_*^2, m_*, ni_*)]}[1]\right) k'}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot pk)^{r_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} R_*^{(\Lambda_{*,q} \cdot SK)}\right) k'}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot pk)^{r_1}} = k'
\end{align*}
$$

and

$$
\begin{align*}
k_*'' &= \frac{H_*^1}{\prod_{q=1}^{n_*} \Lambda_{*,q} \cdot \text{td}_1} = \frac{(h_* I_*)^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, R_*, h_* X_*, H_*^2, m_*, ni_*)]}[0]}{\prod_{q=1}^{n_*} Y_*^{L[\Lambda_{*,q} \cdot \text{td}]} \\
&= \frac{(h_* g^{i_1})^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, R_*, h_* X_*, H_*^2, m_*, ni_*)]}[0]}{\prod_{q=1}^{n_*} g^{a_1 L[\Lambda_{*,q} \cdot \text{td}]} \\
&= \frac{\left(\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot pk)^{L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, R_*, h_* X_*, H_*^2, m_*, ni_*)]}[0]\right) Y_*^{i_1}}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot pk)^{a_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} g^{(\Lambda_{*,q} \cdot SK) L'[(g, Y_*, h_* X_*, H_*, h_* I_*, H_*^1, R_*, h_* X_*, H_*^2, m_*, ni_*)]}[0]\right) k''}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot pk)^{a_1}} \\
&= \frac{\left(\prod_{q=1}^{n_*} Y_*^{(\Lambda_{*,q} \cdot SK)}\right) k''}{\prod_{q=1}^{n_*} (\Lambda_{*,q} \cdot pk)^{a_1}} = k''
\end{align*}
$$
This implies that $k_* = k$, $k'_* = k'$ and $k''_* = k''$ (and thus $PRK_{out*} = PRK_{out}$) with probability 1, and so $\mathcal{A}$ fails the game $\mathbb{G}_4^3$. Absurd!

So $\mathcal{A}$ always fails the game $\mathbb{G}_4^3$, and thus we have:

$$ \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_4^3) = 0. $$

So finally, for each of the four versions of the protocol, we have:

$$ \begin{aligned} \text{Adv}_{\text{LI-EDHOC},\mathcal{A}}^{\text{LIC}}(\lambda) &= \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{E}_{\text{LI-EDHOC},\mathcal{A}}^{\text{LIC}}(\lambda)) = \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_0) \\ &\le q_R \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_1) \end{aligned} $$

$$ \begin{aligned} &\le q_R \left( \begin{aligned} &|\mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_1) - \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_2)| \\ &+ |\mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_2) - \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_3)| \\ &+ |\mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_3) - \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_4)| + \mathbb{P}(\mathcal{A} \text{ wins } \mathbb{G}_4) \end{aligned} \right) \\ &\le q_R \left( \text{Adv}_{\text{DS}}^{\text{EUF-CMA}}(\lambda) + q_R \cdot \epsilon_{\text{NIPoK}}(\lambda) + q_S \cdot \epsilon_{\text{SoK}}(\lambda) \right) \end{aligned} $$

and this concludes the proof. ■

<figure><img src="image_17.png" /></figure>
## 7.3 Non-frameability.

With this third theorem, we also verify that our four protocols respect the non-frameability security property.

**Theorem 4 (Non-Frameable LI-EDHOC protocol)** Under the assumption that our signature scheme DS is EUF-CMA-secure, the Sign-sign version of the LI-EDHOC protocol is non-frameable. Moreover, assuming that our proofs and signatures of knowledge are zero-knowledge and extractable, and that the Oracle-DLog problem is hard in $\mathcal{G}$, then the three other versions of the LI-EDHOC protocol are non-frameable. More precisely, for all p.p.t. adversary $\mathcal{A}$ making at most $q_R$ queries to the $\mathbf{oRegister}$ oracle, we have (for the Sign-sign method):

$$ \mathrm{Adv}_{\mathrm{LI}-\mathrm{EDHOC}, \mathcal{A}}^{\mathrm{NF}-0}(\lambda) \le q_R \cdot \mathrm{Adv}_{\mathrm{DS}}^{\mathrm{EUF-CMA}}(\lambda) $$

and (for the three others methods):

$$ \mathrm{Adv}_{\mathrm{LI}-\mathrm{EDHOC}, \mathcal{A}}^{\mathrm{NF}-1,2,3}(\lambda) \le q_R \cdot \left( \mathrm{Adv}_{\mathrm{DS}}^{\mathrm{EUF-CMA}}(\lambda) + q_R \cdot \epsilon_{\mathrm{NIPoK}}(\lambda) + \epsilon_{\mathrm{SoK}}(\lambda) + \mathrm{Adv}_{\mathcal{G}}^{\mathrm{Oracle-DLog}}(\lambda) \right). $$

Before starting the proof, we just remind the non-frameability security game.

<figure><img src="image_18.png" /><figcaption>FIGURE 29 – Non-frameability security game for the LI-EDHOC protocol (by $P.\overline{\mathcal{SK}}[sst]$ we mean the long-term key of $P$ associated to the method stored in $sst$).</figcaption></figure>

**Proof 4 (of theorem 4)** In the non-frameability game, the adversary aims to convince the verifier that a given endpoint participated in a session, despite this being false. We proceed by games hop and we separate this proof in two parts. First we treat the case for a signing party, and we subsequently treat the case for a static party. However the first two games are common to both. The game $\mathcal{G}_0$ is simply the original experiment, and then in game $\mathcal{G}_1$ we chose at random an honest endpoint, against which $\mathcal{A}$ will try to forge a session state. After choosing this particular endpoint, we divide the proof into two branches, depending on the authentication method used by the endpoint. If it is a signature authentication, with game $\mathcal{G}_2^{\mathrm{Sign}}$, we raised a bad flag whenever $\mathcal{A}$ forges a signature, and finally with game $\mathcal{G}_3^{\mathrm{Sign}}$, we abort if the bad flag is raised and we reduce against the EUF-CMA security property of DS. Otherwise, we selected an endpoint using static DH authentication, and with game $\mathcal{G}_2^{\mathrm{Static}}$, we prevent the adversary from forging proof of knowledge on the authorities' long-term public keys with the extractor. In game $\mathcal{G}_3^{\mathrm{Static}}$ we simulate the signature of knowledge for the chosen endpoint (with the simulator) and extracting them (with the extractor) in game $\mathcal{G}_4^{\mathrm{Static}}$, to finally reduce against the Oracle-DLog problem. The game schedule is depicted in FIGURE 30 below.
<figure><img src="image_19.png" /><figcaption>FIGURE 30 – Game-schedule for the non-frameability property.</figcaption></figure>

† **Game $G_0$**: This game is the original experience $E_{LI-EDHOC,A}^{NF}(\lambda)$. We thus have:

$$P(G_0 \Rightarrow 1) = P(E_{LI-EDHOC,A}^{NF}(\lambda) \Rightarrow 1).$$

† **Game $G_1$**: This game is the same as the previous one, except that it starts by picking $\ell \leftarrow \mathbb{S}[1, q_R]$. We denote by $P_j$ the $j$-th party registered.

If $A$ returns $(sst, P)$ with $P \neq P_\ell$, then $G_1$ aborts and returns 0. With this game hop, the winning advantage of the adversary is increased by a factor equaling the probability of guessing correctly the party $P_\ell$. We thus have:

$$P(G_0 \Rightarrow 1) \leq q_R \cdot P(G_1 \Rightarrow 1).$$

We now split the proof into two branches.

**Proof for a signing party.** From now on, for this first branch we assume that party $P_\ell$ uses the signing method. Thus it provides a signature which is recorded in the session state and subsequently verified. The associated signature must be valid for the adversary to win the experiment in such a case. We show below that the adversary can only frame party $P_\ell$ by producing a forgery for $P_j$'s signing key. This is prevented based on the EUF-CMA security property of the signature scheme as we elaborate below.

† **Game $G_2^{\text{Sign}}$**: This game is the same as the previous one, except that the challenger records all the messages signed by party $P_\ell$ which has been picked in game $G_1$. If $A$ returns $(sst, P)$ with $P = P_\ell$, we parsed $sst$ as $sst = \omega \parallel \text{MCS} \parallel g^x \parallel g^y \parallel \text{TH}_2 \parallel \text{TH}_3 \parallel \text{TH}_4 \parallel M_1 \parallel m_2 \parallel m_3 \parallel H_d \parallel \text{ni} \parallel \text{pid}_d \parallel n_r \parallel \text{val} \parallel \sigma$. In the one hand, assuming that party $P_\ell$ is an Initiator in this session, we parse $m_3$ as $(\text{ID}_1 \parallel \sigma_3 \parallel \text{EAD}_3)$ we check that $\sigma_3$ is a valid signature on a signed message of the recorded list. Otherwise the experiment raised a bad flag badInitt to true. On the other hand, assuming that party $P_\ell$ is a Responder, we parse $m_2$ as $(C_R \parallel \text{ID}_R \parallel \sigma_2 \parallel \text{EAD}_2)$ and do the same checks on $\sigma_2$. The experiment raised a bad flag badResp to true
if the message was not honestly signed by the honest party. This modification is internal to the game, and we obtain:

$$ \mathbb{P}(\mathbb{G}_2^{\text{Sign}} \Rightarrow 1) = \mathbb{P}(\mathbb{G}_1 \Rightarrow 1). $$

† **Game $\mathbb{G}_3^{\text{Sign}}$**: This game is the same as the previous one, except that we abort when bad flags $\text{bad}_{\text{Init}}$ or $\text{bad}_{\text{Init}}$ is set to true. Let's denote $F$ this event. We claim that, by reduction, we can build a p.p.t. adversary $\mathcal{B}_{\text{Sign}}$ against the EUF-CMA property of DS in order to bound $\mathbb{P}(F)$, and by the identical-until-bad lemma we thus have:

$$ |\mathbb{P}(\mathbb{G}_2^{\text{Sign}} \Rightarrow 1) - \mathbb{P}(\mathbb{G}_3^{\text{Sign}} \Rightarrow 1)| \le \text{Adv}_{\text{DS},\mathcal{A}}^{\text{EUF-CMA}}(\lambda). $$

‡ **Proof of the claim**: The reduction is direct and similar to the previous ones on the EUF-CMA assumption. We first assume for contradiction that we have a p.p.t. adversary $\mathcal{A}$ that wins against game $\mathbb{G}_2^{\text{Sign}}$ but not game $\mathbb{G}_3^{\text{Sign}}$ with a non-zero probability $\epsilon_{\mathcal{A}}(\lambda)$. Hence, $\mathcal{A}$ triggered the failure condition added in game $\mathbb{G}_2^{\text{Sign}}$ by returning a valid signature that has not been produced by party $P_{\ell}$. Based on the challenger of the $\mathbb{E}_{\text{DS},\mathcal{A}}^{\text{EUF-CMA}}(\lambda)$ experiment, we build a p.p.t. algorithm $\mathcal{B}_{\text{Sign}}$ returning a forgery as follows.

The challenger generates a pair of private/public signature keys ($\widetilde{\text{ssk}}, \widetilde{\text{spk}}$) thanks to DS.Gen, and sends $\widetilde{\text{spk}}$ to $\mathcal{B}_{\text{Sign}}$. Then algorithm $\mathcal{B}_{\text{Sign}}$ initializes an empty list $L \leftarrow \emptyset$, and then simulates $\mathbb{G}_2^{\text{Sign}}$ to $\mathcal{A}$ faithfully, with two exceptions. Firstly, when $\mathcal{A}$ registered (honestly) party $P_{\ell}$, $\mathcal{B}_{\text{Sign}}$ sets $P_{\ell}.\widetilde{\text{PK}} \ni P_{\ell}.\widetilde{\text{spk}} \leftarrow \widetilde{\text{spk}}$. Secondly, whenever $\mathcal{A}$ queries $\text{oSend}$, all required signatures are generated through the signature oracle Sign provided by the EUF-CMA experiment.

Finally, $\mathcal{A}$ returns a $\text{sst}$ from which $\mathcal{B}_{\text{Sign}}$ extract a signature $\sigma_2$ or $\sigma_3$ depending on the role of the party $P_{\ell}$, and the associated MAC $t$ used as a message to sign. If $\mathcal{A}$ wins the game by returning a valid signature that has not been produced by party $P_{\ell}$, i.e., if $F$ occurs, we have by construction of the game and the algorithm Verify, that $\text{DS.Verif}(P_{\ell}.\widetilde{\text{spk}}, t, \sigma) = 1$ and $(t, \sigma) \notin L$. Thus $\mathcal{B}_{\text{Sign}}$ breaks the EUF-CMA security of DS and we have:

$$ \text{Adv}_{\text{DS},\mathcal{B}_{\text{Sign}}}^{\text{EUF-CMA}}(\lambda) \ge \epsilon_{\mathcal{A}}(\lambda) \ge \mathbb{P}(F) $$

which concludes the proof of the claim.

To conclude this branch of the proof, we now show that has a zero probability of winning game $\mathbb{G}_3^{\text{Sign}}$. For that observe that in game $\mathbb{G}_3^{\text{Sign}}$ the adversary is left with the objective to return ($\text{sst}, P$), where $P = P_{\ell}$ and $\text{sst}$ must contains a signature $\sigma_2$ or $\sigma_3$ (depending on the role of $P_{\ell}$ in the associated statement) which is on a message that has been produced by party $P_{\ell}$. By construction, this signature is verified by the Verify algorithm. Since $\mathcal{A}$ is not able anymore to forged this signature, in order to respect the winning condition of Verify returning 1, this signature must have been generated by $P_{\ell}$. But this implies that there exists an integer $q \in \mathbb{N}$ such that $\pi_{P_{\ell}}^q \ne \perp$ and $\text{IdentifySession}(\text{sst}, \pi_{P_{\ell}}^q) = 1$, which contradict the last winning condition of the game. Thus $\mathcal{A}$ is unable to win game $\mathbb{G}_3^{\text{Sign}}$. We thus have:

$$ \mathbb{P}(\mathbb{G}_3^{\text{Sign}} \Rightarrow 1) = 0 $$

**Proof for a static party.** From now on, for this second branch, we assume that party $P_{\ell}$ uses the static authentication method. Thus, no signature is registered in the session state by the endpoint $P_{\ell}$, only a SoK produced by the latter, involving its long term static DH secret. This signature of knowledge is verified in the final verification step of the non-frameability experiment. We now elaborate why this SoK cannot have been generated by the adversary for party $P_{\ell}$.
† **Game $G_2^{Static}$**: Let's denote $Ext_{NIPoK}$ the knowledge extractor of the zero-knowledge proof of knowledge. In order to prevent the adversary from forging proofs of knowledge on authorities' long-term public keys, this game operate similarly to game $G_1$, except that we begin by initializing an empty list $L'[ ] \leftarrow \emptyset$, and we slightly modify the oRegister oracle. When $\mathcal{A}$ queries oRegister on input $(\Lambda, \text{authority}, \{\perp\})$, it generates the associated keys $(\Lambda.\mathcal{SK}, \Lambda.\mathcal{PK})$ (to simplify notations, in what follows we write $\Lambda.\mathcal{SK}$ and $\Lambda.\mathcal{PK}$ instead of $\Lambda.\mathcal{SK}, \Lambda.\mathcal{PK}$, since these sets contain only one element each) and then sets $L'[\Lambda.\mathcal{PK}] \leftarrow \Lambda.\mathcal{SK}$. Now in case the adversary queries oRegister on $(\Lambda, \text{authority}, \mathcal{PK} \neq \perp)$, which in this experiment is the most likely, the oracle sets $\Lambda.\mathcal{PK} \leftarrow \mathcal{PK}$ and parses $\Lambda.\mathcal{PK}$ as $(\Lambda.\mathcal{pk}, \Lambda.\mathcal{ni})$.

To complete the process correctly, it checks if $NIPoKver((g, \Lambda.\mathcal{pk}), \Lambda.\mathcal{ni}) = 1$ (if not, the game aborts), and then it runs the extractor $Ext_{NIPoK}$ on $\mathcal{A}$ to get the witness $\Lambda.\mathcal{SK}$ for $\Lambda.\mathcal{ni}$. Following this, if $g^{\Lambda.\mathcal{SK}} \neq \Lambda.\mathcal{pk}$, then the experiment aborts and returns a random bit, else it sets $L'[\Lambda.\mathcal{PK}] \leftarrow \Lambda.\mathcal{SK}$.

With this modification, we point out the probability of the extractor $Ext_{NIPoK}$ failing when called to extract a valid witness. Since oRegister requires possibly one call to $Ext_{NIPoK}$ at each query, this implies that:

$$ \left| \mathbb{P}(G_1 \Rightarrow 1) - \mathbb{P}(G_2^{Static} \Rightarrow 1) \right| \le q_R \cdot \epsilon_{NIPoK}(\lambda). $$

† **Game $G_3^{Static}$**: Let's denote by $Sim_{SoK}$ the simulator of the signature of knowledge. This game is the same as $G_8$, except that each time the oSend oracle is queried to produce signature of knowledge for party $P_\ell$, the signature of knowledge $n_i$ is simulate using $Sim_{SoK}$. Since by assumption the simulator $Sim_{SoK}$ and the SoK algorithm follow the same probability distribution, this modification is indistinguishable by $\mathcal{A}$, and thus we have:

$$ \mathbb{P}(G_3^{Static} \Rightarrow 1) = \mathbb{P}(G_2^{Static} \Rightarrow 1). $$

**Game $G_4^{Static}$**: This game is the same as the previous one, except that we added an additional failure condition: during the verification of the values $(sst, P)$ returned by the adversary, the state $sst$ contains either a SoK $n_i$ or $n_i_R$ depending whether $sst$ corresponds to a Initiator's or Responder's proxy state. After a successful verification of the SoK, the challenger uses the extractor algorithm of the SoK, denoted $Ext_{SoK}$, to recover the secret $(x^*, i^*)$ (for a SoK $n_i$) or $(y^*, r^*)$ (for a SoK $n_i_R$). He then checks the validity of this secret (as in game $G_9$ of the proof of theorem 2), if it fails, stops the simulation.

With this game hop, we highlight the possibility of the extractor $Ext_{SoK}$ failing when extracting a valid witness. Since the extractor is called once in the game, we thus have the bound:

$$ \left| \mathbb{P}(G_3^{Static} \Rightarrow 1) - \mathbb{P}(G_4^{Static} \Rightarrow 1) \right| \le \epsilon_{SoK}(\lambda). $$

To conclude this branch of the proof, we now need to bound $\mathbb{P}(G_4^{Static} \Rightarrow 1)$. To do so, we build a reduction on the Oracle-DLog problem.

So we consider game $G_4^{Static}$ and will construct an intermediary p.p.t. algorithm $B_{Static}$ which simulates it based on the challenger of the Oracle-DLog experiment. We also consider an adversary $\mathcal{A}$ and demonstrate that if $\mathcal{A}$ wins with non negligible probability $\epsilon_{\mathcal{A}}(\lambda)$ against game $G_4^{Static}$, then we can build an adversary against the Oracle-DLog problem that we assumed hard.

The challenger of the Oracle-DLog experiment starts by sending a value $U$ to $B_{Static}$. With only one exception, algorithm $B_{Static}$ generate the parameter and keys as prescribed in experiment $G_4^{Static}$ and as it was done by the challenger of $G_4^{Static}$. The exception is when $B_{Static}$ sets the keys of the static endpoint $P_\ell$. There $B_{Static}$ only sets the long-term public key as $U$ (usually denoted by $g^\ell$ or $g^r$), and the long-term secret key is set to $\perp$. Algorithm $B_{Static}$ subsequently reproduce the action of the challenger of game $G_4^{Static}$ for any query which does not involve endpoint $P_\ell$. For any query involving
$P_\ell$ following differences are observed: on receiving $g^x$ or $g^y$ (depending on the Initiator or Responder role of $P_\ell$) from another endpoint starting an handshake process, $\mathcal{B}_{\text{Static}}$ send $V$ (either $g^x$ or $g^y$) as a query to the oracle $\mathcal{O}_{\text{CDH}}^U$ of the Oracle-DLog challenger. This call returns an element $W$ that can be used as $g^{iy}$ or $g^{rx}$, once again with a notation depending the role of endpoint $P_\ell$ in this session. Subsequently, based on this element, and also based on the extracted authorities' secret keys, $\mathcal{B}_{\text{Static}}$ computes either:

- $H_R^1 = (h_R g^x)^r = U \sum_{j=1}^{n_R} \Lambda_j^R \cdot SK \cdot g^{rx}$, where $U = g^r$, for $P_\ell$ as a Responder in a **Sign-static** method;

- $H_1^1 = (h_1 g^y)^i = U \sum_{j=1}^{n_1} g^{iy}$, where $U = g^i$, for $P_\ell$ as an Initiator in a **Static-sign** method;

- $H_1^2 = (h_1 g^y)^i = U \sum_{j=1}^{n_1} g^{iy}$, where $U = g^i$, for $P_\ell$ as an Initiator in a **Static-static** method;

- $H_R^2 = (h_R g^x)^r = U \sum_{j=1}^{n_R} \Lambda_j^R \cdot SK \cdot g^{rx}$, where $U = g^r$, for $P_\ell$ as a Responder in a **Static-static** method.

As the SoK is simulated, $\mathcal{B}_{\text{Static}}$ can still generate it. This allows to fully simulate $P_\ell$. Based on the final witness extraction a value $i^*$ or $r^*$ extracted from a winning adversary $\mathcal{A}$ against the simulation of $\mathcal{B}_{\text{Static}}$ of game $\mathbb{G}_4^{\text{Static}}$, the extracted witness can be sent to the challenger of the Oracle-DLog as an answer to the Oracle-DLog problem. Thus the chances of $\mathcal{B}_{\text{Static}}$ winning against the Oracle-DLog problem are the same as the chances of $\mathcal{A}$ winning against $\mathbb{G}_4^{\text{Static}}$ as it was perfectly simulated, i.e.:

$$ \mathrm{Adv}_{\mathbb{G}, \mathcal{B}_{\text{Static}}}^{\mathrm{Oracle-DLog}}(\lambda) = \epsilon_{\mathcal{A}}(\lambda). $$

So we finally obtain that:

$$ \mathbb{P}(\mathbb{G}_4^{\text{Static}} \Rightarrow 1) = \mathrm{Adv}_{\mathbb{G}, \mathcal{A}}^{\mathrm{Oracle-DLog}}(\lambda). $$

So to conclude the proof in its entirety, we have for the **Sign-sign** version of the LI-EDHOC protocol:

$$ \begin{aligned} \mathrm{Adv}_{\text{LI-EDHOC}, \mathcal{A}}^{\text{NF-0}}(\lambda) &= \mathbb{P}(\mathbb{E}_{\text{LI-EDHOC}, \mathcal{A}}^{\text{NF}}(\lambda) \implies 1) = \mathbb{P}(\mathbb{G}_0 \implies 1) \\ &\le q_R \cdot \mathbb{P}(\mathbb{G}_1 \implies 1) \\ &= q_R \cdot \mathbb{P}(\mathbb{G}_2^{\text{Sign}} \implies 1) \\ &\le q_R \cdot \left( |\mathbb{P}(\mathbb{G}_2^{\text{Sign}} \implies 1) - \mathbb{P}(\mathbb{G}_3^{\text{Sign}} \implies 1)| + \mathbb{P}(\mathbb{G}_3^{\text{Sign}} \implies 1) \right) \\ &\le q_R \cdot \mathrm{Adv}_{\mathrm{DS}}^{\text{EUF-CMA}}(\lambda). \end{aligned} $$

And for the **Static-static** version:

$$ \begin{aligned} \mathrm{Adv}_{\text{LI-EDHOC}, \mathcal{A}}^{\text{NF-3}}(\lambda) &= \mathbb{P}(\mathbb{E}_{\text{LI-EDHOC}, \mathcal{A}}^{\text{NF}}(\lambda) \implies 1) = \mathbb{P}(\mathbb{G}_0 \implies 1) \\ &\le q_R \cdot \mathbb{P}(\mathbb{G}_1 \implies 1) \\ &\le q_R \cdot \left( |\mathbb{P}(\mathbb{G}_1 \implies 1) - \mathbb{P}(\mathbb{G}_2^{\text{Static}} \implies 1)| + \dots + \mathbb{P}(\mathbb{G}_4^{\text{Static}} \implies 1) \right) \\ &\le q_R \cdot \left( q_R \cdot \epsilon_{\text{NIPOK}}(\lambda) + \epsilon_{\text{SoK}}(\lambda) + \mathrm{Adv}_{\mathbb{G}, \mathcal{A}}^{\text{Oracle-DLog}}(\lambda) \right). \end{aligned} $$

Finally combining both for the **Sign-static** and **Static-sign** versions:

$$ \mathrm{Adv}_{\text{LI-EDHOC}, \mathcal{A}}^{\text{NF-1,2}}(\lambda) \le q_R \cdot \left( \mathrm{Adv}_{\mathrm{DS}}^{\text{EUF-CMA}}(\lambda) + q_R \cdot \epsilon_{\text{NIPOK}}(\lambda) + \epsilon_{\text{SoK}}(\lambda) + \mathrm{Adv}_{\mathbb{G}, \mathcal{A}}^{\text{Oracle-DLog}}(\lambda) \right). $$

And this concludes the proof.

<figure><img src="image_20.png" /></figure>
## 7.4 Identity protection.

We now present the two following statements, which state that our protocols satisfy the Initiator and Responder identities protection between proxies, respectively against active and passive adversaries. In this situation the considered adversary only has access to the $RO_H$, $RO_T$ and $RO_p$ oracles (indispensable to simulate the protocol run), but not to those described in FIGURE 18.

### 7.4.1 Responder identity protection

We begin with the Responder side.

**Theorem 5 (Responder identity protecting LI-EDHOC protocol)** Under the assumption that the DDH and the GDH problems are hard to solve in $\mathbb{G}$, that our two encryption schemes (KGen, Enc, Dec) and (KGen'', Enc'', Dec'') are IND-secure and that our encryption scheme (KGen', Enc', Dec') is an AEAD-encryption scheme IND-CPA-secure, then the LI-EDHOC protocol, in its four versions, protect the Responder's identity against passive adversaries. More precisely, for all p.p.t. adversary $\mathcal{A}$ making at most $q_{RO_T}$ (resp. $q_{RO_p}$ and $q_{RO_H}$) queries to the $RO_T$ (resp. $RO_p$ and $RO_H$) oracle, we have:

$$ \begin{aligned} \mathrm{Adv}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{Id-Pro-Resp}}(\lambda) \le & \frac{(q_{SO_T} + q_{SO_P^{l'hash}})^2 + (q_{SO_T} + q_{SO_H})^2 + (q_{SO_P^{l'hash}} + q_{SO_H})^2}{2^{l_{hash}+1}} + 12 \mathrm{Adv}_{\mathbb{G}}^{\mathrm{DDH}}(\lambda) \\ & + 8 q_{RO_T} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda) + 5 \cdot \frac{q_{RO_P^{l'key}} + q_{RO_P^{l'iv}} + q_{RO_P^{l'mac}}}{2^{l_{hash}}} + 4 \cdot \frac{q_{RO_P^{l'2}} + q_{RO_P^{l'hash}} + 2}{2^{l_{hash}}} \\ & + 4 \cdot \left( 8 \mathrm{Adv}_{(KGen'', Enc'', Dec'')}^{\mathrm{IND}}(l_{key}) + \mathrm{Adv}_{(KGen, Enc, Dec)}^{\mathrm{IND}}(l_2) + \mathrm{Adv}_{\mathrm{AEAD}}^{\mathrm{IND-CPA}}(l_{key}) \right) \end{aligned} $$

**Proof 5 (of theorem 5)** To begin with we remind here, in FIGURE 31 the Responder identity protection security games.

$$ \begin{array}{l} \displaystyle \mathbb{E}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{IdPro-Responder-b}}(\lambda) \\ \qquad 1 : \mathrm{pp} \leftarrow \mathrm{Setup}(1^{\lambda}) \\ \qquad 2 : \mathrm{ID\_CRED\_R}_0, \mathrm{ID\_CRED\_R}_1 \leftarrow \mathcal{A}(\mathrm{ESet}_{\mathrm{meth}}) \\ \qquad 3 : \mathrm{ID\_CRED\_R} \leftarrow \mathrm{ID\_CRED\_R}_b \\ \qquad 4 : \mathrm{ID\_CRED\_I} \leftarrow \mathrm{ESet}_{\mathrm{meth}} \\ \qquad 5 : M_1 \leftarrow \mathrm{InitRun1}(\mathrm{ID\_CRED\_I}) \\ \qquad 6 : M_2 \leftarrow \mathrm{RespRun1}(\mathrm{ID\_CRED\_R}, M_1) \\ \qquad 7 : M_3 \leftarrow \mathrm{InitRun2}(\mathrm{ID\_CRED\_I}, M_2) \\ \qquad 8 : M'_3 \leftarrow \mathrm{ProxIRun3}(\mathrm{ID\_CRED\_I}, M_3) \\ \qquad 9 : M_4 \leftarrow \mathrm{RespRun2}(\mathrm{ID\_CRED\_R}, M'_3) \\ \qquad 10 : M \leftarrow (\mathrm{ID\_CRED\_I}, M_1, M_2, M_3, M'_3, M_4) \\ \qquad 11 : b' \leftarrow \mathcal{A}(M) \\ \qquad 12 : \text{if } b = b' \text{ then return } 1 \\ \qquad 13 : \text{else return } 0 \end{array} $$

FIGURE 31 – The LI-EDHOC Responder identity protection security games. By $\mathrm{ESet}_{\mathrm{meth}}$ we mean the set of all endpoints running the protocol with the same method (0,1,2, or 3).

We proceed by game hops which are depicted in FIGURES 32 to 34 below. Firstly, game $\mathbb{G}_0$ is a reformulation of the original experiment $\mathbb{E}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{IdPro-Responder-1}}(\lambda)$. Then with games $\mathbb{G}_1$, $\mathbb{G}_2$, and $\mathbb{G}_3$ we simulate random oracles $RO$ as list, in order to manipulate them later. We next prevent collisions on some oracles with games $\mathbb{G}_4$ and $\mathbb{G}_5$. We now need to divide our analysis into four branches, in order to distinguish between the four
versions of the protocol (denoting games with exponent 0, 1, 2 or 3 to indicate the method used in the current game). With games $G_6$, $G_{6'}$, $G_7$ and $G_7'$, we randomize the H elements in order to prevent the adversary from obtaining informations about $g^{xy}$ (or $g^{iy}$ or $g^{xr}$), so he cannot compute on his side some keys as $sk_2$ or $sk_3$. With the pack of games $G_8$ and $G_9$ we randomize the key-schedule elements to limit the capacity of $\mathcal{A}$ in predicting the encryption keys (and thus potentially learning the identity of the Responder). With game $G_{10}$ we randomize the encryption keys $sk_2$ and $sk_3$ to make them unpredictable to $\mathcal{A}$. Finally with game $G_{11}$ we turn the game into the original experiment $\mathbb{E}_{\text{LI-EDHOC},\mathcal{A}}^{\text{IdPro-Responder-0}}(\lambda)$, so we can conclude on the advantage of $\mathcal{A}$.

<figure><img src="image_21.png" /><figcaption>FIGURE 32 – First steps of the game-schedule for the Responder identity protection security property.</figcaption></figure>

† **Game $G_0$**: This game is the original experience $\mathbb{E}_{\text{LI-EDHOC},\mathcal{A}}^{\text{IdPro-Responder-1}}(\lambda)$. As usually we thus have:

$$ \mathbb{P}(G_0 \implies 1) = \mathbb{P}(\mathbb{E}_{\text{LI-EDHOC},\mathcal{A}}^{\text{IdPro-Responder-1}}(\lambda) \implies 1). $$

† **Game $G_1$**: This game is the same as the previous one except that we make the same modification as in the game $G_3$ of the key-secure property demonstration (on page 55); namely we simulate $RO_H$ thanks to a list (with memory) denoted $SO_H$. We thus obtain the same conclusion:

$$ \mathbb{P}(G_1 \implies 1) = \mathbb{P}(G_0 \implies 1). $$

† **Game $G_2$**: Similarly, this game works as the previous one, except that we make the same modification as in the game $G_4$ of the key-secure property demonstration (on page 55); namely we simulate $RO_P$ thanks to a list (again with memory) denoted $SO_P$ (still depending on the digest size, but again it does not impact the analysis). We thus obtain the same result:

$$ \mathbb{P}(G_2 \implies 1) = \mathbb{P}(G_1 \implies 1). $$

† **Game $G_3$**: Similarly, this game is the same as the previous one, except that this time we make the same modification as in the game $G_5$ of the key-secure property demonstration (on page 55); namely we simulate $RO_T$ thanks to a special list (with memory) denoted $SO_T$ (following the same construction as in $G_5$). We thus obtain:
$$ \mathbb{P}(\mathbb{G}_3 \implies 1) = \mathbb{P}(\mathbb{G}_2 \implies 1). $$

† **Game $\mathbb{G}_4$**: In a future game, we will work on the key-derivation schedule. With this game, and the next one, we want to avoid collision between some simulated random oracles. So this game is the same as the previous one, except that this time we make the same modification as in the game $\mathbb{G}_6$ of the key-secure property demonstration (on page 56), raising a bad flag **bad$_3$** to true when a collision between $SO_H$ and $SO_T$, or $SO_T$ and $SO_P^{l_{hash}}$, or $SO_H$ and $SO_P^{l_{hash}}$ occurs. This change is indistinguishable by the adversary and we obtain:

$$ \mathbb{P}(\mathbb{G}_4 \implies 1) = \mathbb{P}(\mathbb{G}_3 \implies 1). $$

† **Game $\mathbb{G}_5$**: This game is the same as the previous one, except that this time we make the same modification as in the game $\mathbb{G}_7$ of the key-secure property demonstration (on page 56), aborting when the bad flag **bad$_3$** is set to true. Using the same analysis as in game $\mathbb{G}_7$, we bound the winning advantage of the adversary with this game hop as follows:

$$ |\mathbb{P}(\mathbb{G}_4 \implies 1) - \mathbb{P}(\mathbb{G}_5 \implies 1)| \le \frac{(q_{SO_T} + q_{SO_P^{l_{hash}}})^2 + (q_{SO_T} + q_{SO_H})^2 + (q_{SO_P^{l_{hash}}} + q_{SO_H})^2}{2^{l_{hash}+1}}. $$

<figure><img src="image_22.png" /><figcaption>FIGURE 33 – Continuation of the game-schedule for the Responder identity protection security property. With these games we randomize the H elements.</figcaption></figure>

† **Game $\mathbb{G}_6^0$**: With the next game pack, we prevent the adversary from obtaining information from the H elements. This game is the same as the previous one except that we pick at random, according to the uniform distribution on the group $\mathbb{G}$, the element $H_1$ of the Initiator (and of course simulate the proof $n_1$ with the simulator $Sim_{\mathbb{G}_K}$ associated to the $\mathbb{S}_K$). We claim that, by reduction, we can build a p.p.t. algorithm $\mathcal{B}_1^0$ against the DDH problem, and thus we have:

$$ |\mathbb{P}(\mathbb{G}_5 \implies 1) - \mathbb{P}(\mathbb{G}_6^0 \implies 1)| \le \mathrm{Adv}_{\mathcal{A}}^{\mathrm{DDH}}(\lambda). $$

‡ **Proof of the claim**: The challenger gives a DDH challenge ($\Gamma = g^{\gamma}, \Delta = g^{\delta}, \Sigma$) to $\mathcal{B}_1^0$, with either $\Sigma = g^{\gamma\delta}$ or $\Sigma = g^{\sigma}$ with $\sigma \neq \gamma\delta$, and $\mathcal{B}_1^0$ tries to distinguish. To do so $\mathcal{B}_1^0$ simulates game $\mathbb{G}_5$ to $\mathcal{A}$ faithfully, except on certain points:
≈ When registering all authorities (to generate the element $h_I$), $\mathcal{B}_1^0$ chooses $\Lambda_* \in (\Lambda_j^I)_{j=1}^{n_I}$ and sets $\Lambda_* \cdot pk \leftarrow \Delta = g^\delta$ (and he simulates the associated proof thanks to the simulator $\text{Sim}_{\text{NIPoK}}$);

≈ When simulating the protocol run, $\mathcal{B}_1^0$ sets $(g^x =:) X \leftarrow \Gamma = g^\gamma$, and:

$$H_I \leftarrow \prod_{\Lambda \in (\Lambda_j^I)_{j=1}^{n_I} \setminus \Lambda_*} (X^{\Lambda \cdot SK}) \Sigma X^y.$$

Now observe that if $\Sigma = g^{\gamma\delta}$, $H_I$ is well formed as described by the protocol, and in this case (since $\mathcal{B}_1^0$ did not have to answer $\mathcal{A}$'s queries) $\mathcal{B}_1^0$ perfectly simulates game $\mathbb{G}_5$ to $\mathcal{A}$. On the other hand, if $\Sigma = g^\sigma$, with $\sigma \leftarrow \mathbb{Z}_p^*$, $H_I$ is random, and in that case $\mathcal{B}_1^0$ perfectly simulates game $\mathbb{G}_6^0$ to $\mathcal{A}$. So we deduce that:

$$\varphi \leftarrow \mathbb{P}(\mathbb{G}_5 \implies 1) = \mathbb{P}((\gamma, \delta) \leftarrow \mathbb{Z}_p^*, b \leftarrow \mathcal{B}_1^0(g^\gamma, g^\delta, g^{\gamma\delta}) : b = 1);$$

$$\varphi \leftarrow \mathbb{P}(\mathbb{G}_6^0 \implies 1) = \mathbb{P}((\gamma, \delta, \sigma) \leftarrow \mathbb{Z}_p^*, b \leftarrow \mathcal{B}_1^0(g^\gamma, g^\delta, g^\sigma) : b = 1).$$

So $\mathcal{B}_1^0$ is a well constructed distinguisher and we have:

$$|\mathbb{P}(\mathbb{G}_5 \implies 1) - \mathbb{P}(\mathbb{G}_6^0 \implies 1)| \le \text{Adv}_{\mathcal{A}}^{\text{DDH}}(\lambda)$$

which concludes the proof of the claim.

† **Game $\mathbb{G}_6^0$**: This game is the same as the previous one except that this time we pick at random, according to the uniform distribution on the group $\mathbb{G}$, the element $H_R$ of the Responder (and of course simulate the proof $n_I R$ with the simulator $\text{Sim}_{\text{SoK}}$ associated to the SoK). As in the previous game, by reduction, we can build a p.p.t. algorithm $\mathcal{B}_2^0$ against the DDH problem, and thus we have:

$$|\mathbb{P}(\mathbb{G}_6^0 \implies 1) - \mathbb{P}(\mathbb{G}_7^0 \implies 1)| \le \text{Adv}_{\mathcal{A}}^{\text{DDH}}(\lambda).$$

† **Game $\mathbb{G}_6^1$**: This game is the same as the previous one (game $\mathbb{G}_5$) except that this time we pick at random, according to the uniform distribution on the group $\mathbb{G}$, elements $H_I$ and $H_I^1$ of the Initiator (and of course simulate the proof $n_I I$ with the simulator $\text{Sim}_{\text{SoK}}$ associated to the SoK). As in game $\mathbb{G}_6^0$, by reduction (slightly adapted), we can build a p.p.t. algorithm $\mathcal{B}_1^1$ against the DDH problem, and thus we have:

$$|\mathbb{P}(\mathbb{G}_5 \implies 1) - \mathbb{P}(\mathbb{G}_6^1 \implies 1)| \le \text{Adv}_{\mathcal{A}}^{\text{DDH}}(\lambda).$$

† **Game $\mathbb{G}_7^1$**: This game is the same as the previous one, and works in the same vein as game $\mathbb{G}_7^0$. Thanks to a p.p.t. algorithm $\mathcal{B}_2^1$, we have:

$$|\mathbb{P}(\mathbb{G}_6^1 \implies 1) - \mathbb{P}(\mathbb{G}_7^1 \implies 1)| \le \text{Adv}_{\mathcal{A}}^{\text{DDH}}(\lambda).$$

† **Game $\mathbb{G}_7^1$**: This game is the same as the previous one, and works in the same vein as game $\mathbb{G}_7^0$, but here we pick at random the element $H_R^1$ (and simulate the associated proof). Thanks to a p.p.t. algorithm $\mathcal{B}_2^1$ (instead of imbedding the challenge $\Gamma = g^\gamma$ in $X = g^x$, we set $R := g^r \leftarrow g^\gamma$ (since $\mathcal{A}$ cannot corrupt the Responder this does not lead to any problem)), we have:
$$ \left| \mathbb{P}(G_7^1 \Rightarrow 1) - \mathbb{P}(G_7^1 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_6^2$**: This game is the same as the previous one (game $G_5$), and works in the same vein as game $G_6^0$. Thanks to a p.p.t. algorithm $B_1^1$, we have:

$$ \left| \mathbb{P}(G_5 \Rightarrow 1) - \mathbb{P}(G_6^2 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_{7'}^2$**: This game is the same as the previous one, and works in the same vein as games $G_6^0$ and $G_{7'}^1$. Thanks to a p.p.t. algorithm $B_1^1$, we have:

$$ \left| \mathbb{P}(G_6^2 \Rightarrow 1) - \mathbb{P}(G_{7'}^2 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_7^2$**: This game is the same as the previous one, except that this time we pick at random, according to the uniform distribution on the group $G$, elements $H_R$ and $H_R^1$ of the Responder (and of course simulate the proof $ni_R$ with the simulator $Sim_{sOK}$ associated to the $sOK$). As in game $G_6^1$, by reduction (slightly adapted), we can build a p.p.t. algorithm $B_2^2$ against the DDH problem, and thus we have:

$$ \left| \mathbb{P}(G_{6'}^2 \Rightarrow 1) - \mathbb{P}(G_7^2 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_6^3$**: This game is the same as the previous one (game $G_5$), and works in the same vein as game $G_6^1$. Thanks to a p.p.t. algorithm $B_1^3$, we have:

$$ \left| \mathbb{P}(G_5 \Rightarrow 1) - \mathbb{P}(G_6^3 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_{6'}^3$**: This game is the same as the previous one, and works in the same vein as game $G_{6'}^2$. Thanks to a p.p.t. algorithm $B_1^3$, we have:

$$ \left| \mathbb{P}(G_6^3 \Rightarrow 1) - \mathbb{P}(G_{6'}^3 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_7^3$**: This game is the same as the previous one, and works in the same vein as game $G_7^2$. Thanks to a p.p.t. algorithm $B_2^3$, we have:

$$ \left| \mathbb{P}(G_{6'}^3 \Rightarrow 1) - \mathbb{P}(G_7^3 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$

† **Game $G_{7'}^3$**: This game is the same as the previous one, and works in the same vein as game $G_{7'}^1$. Thanks to a p.p.t. algorithm $B_2^3$, we have:

$$ \left| \mathbb{P}(G_{7'}^3 \Rightarrow 1) - \mathbb{P}(G_{7'}^3 \Rightarrow 1) \right| \le \text{Adv}_A^{\text{DDH}}(\lambda). $$
<figure><img src="image_23.png" /><figcaption>FIGURE 34 – Continuation of the game-schedule for the Responder identity protection security property. With these games we randomize the key-derivation schedule elements in order to prevent the adversary to obtain the encryptions keys $sk_2$ and $sk_3$, and we conclude the security game by modifying the game $G_{10}$ in the original experiment with bit $b = 0$.</figcaption></figure>

† **Game $G_8^0$**: This game is the same as game $G_7^0$, except that we added a failure condition: if the adversary, during the protocol session, queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xy}$, we then abort and return a random bit. We then denote $F_1^0$ the event: $\mathcal{A}$ queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xy}$. If the event $F_1^0$ occurs, then challenger stops the simulation by returning a random bit. By the identical-until-bad lemma, we thus have:

$$|\mathbb{P}(G_7^0 \Rightarrow 1) - \mathbb{P}(G_8^0 \Rightarrow 1)| \le \mathbb{P}(F_1^0).$$

Let's now provide a bound for $\mathbb{P}(F_1^0)$. For that we construct, by reduction, an adversary $B_3^0$ against the GDH problem. We hence claim that:

$$\mathbb{P}(F_1^0) \le q_{RO_T} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda),$$

and finally:

$$|\mathbb{P}(G_7^0 \Rightarrow 1) - \mathbb{P}(G_8^0 \Rightarrow 1)| \le q_{RO_T} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda).$$

‡ **Proof of the claim:** This reduction is very similar to the reduction against the GDH problem proposed in [14] and also the one we made in the key-security property proof. So we briefly explain the construction of a p.p.t adversary $B_3^0$ against the GDH problem.

On input a GDH challenge $(g, A = g^a, B = g^b)$ and having access to a DDH oracle, returning 1 if a tuple $(g, g^a, g^b, g^c)$ is a DIFFIE-HELLMAN tuple, and 0 otherwise, our algorithm $B_3^0$ must return $g^{ab}$ in
a polynomial time. To achieve this, $\mathcal{B}_3^0$ is going to simulate $\mathbb{G}_8^0$ for $\mathcal{A}(\mathbb{p}\mathbb{p})$ faithfully, except for certain points.

Firstly, $\mathcal{B}_3^0$ embeds its challenge into the ephemeral sent DIFFIE-HELLMAN value of each endpoint as follows: it samples uniformly at random $k, k' \in \mathbb{Z}_p$ and sets $X \leftarrow Ag^k$ and $Y \leftarrow Bg^{k'}$ (with $A = g^a$ and $B = g^b$).

If the event $F_1^0$ occurs, then the value $Z$ queried to the $SO_T$ oracle will equal $g^{(a+k)(b+k')}$. To detect that, $\mathcal{B}_3^0$ can compute $ZX^{-k'}B^{-k}$ which, if $F_1^0$ occurs, will equal $g^{ab}$ and test this equality by calling its DDH oracle on $(X, Y, ZX^{-k'}B^{-k})$, which will return 1 if $F_1^0$ occurs. So when the event happens $\mathcal{B}_3^0$ wins.

To finally bound $\mathbb{P}(F_1^0)$, we remark that each time the $SO_T$ oracle is queried on input $Z$, the event $F_1^0$ can happen (on a single pair $(X, Y)$). This implies that possibly $q_{RO_T}$ DDH-oracle queries might be useful to detect the event. Hence the result:

$$ \mathbb{P}(F_1^0) \leq q_{RO_T} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda) $$

which concludes the proof of the claim.

† **Game $\mathbb{G}_8^0$**: This game is the same as the previous one, except that in this game we simulate the key generation of PRK$_{2e}$ for our running session. Namely we simulate the generation of the key PRK$_{2e}$ thanks to a private oracle, denoted $SO_{PRK_{2e}}$, and working the same way as $SO_T$, but inaccessible to $\mathcal{A}$ (in normal times, PRK$_{2e}$ is generated thanks to $SO_T$, $TH_2$ and $g^{xy}$).

One way to detect the modification is for the adversary to ask $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xy}$. Thanks to the event $F_1^0$ the simulation is already stopped in this situation. Another way to detect it is to query $SO_P^{l_2}$, or $SO_P^{l_{key}}$, or $SO_P^{l_{iv}}$, or $SO_P^{l_{mac}}$ on the correct value PRK$_{2e}$ which unpredictable at this stage. We denote $F_2^0$ the event: $\mathcal{A}$ queries $SO_P^{l_2}$, or $SO_P^{l_{key}}$, or $SO_P^{l_{iv}}$, or $SO_P^{l_{mac}}$ on the correct value PRK$_{2e}$ for a session in which the latter is unpredictable. If $F_2^0$ happens, we stop the simulation and return a random bit. We can provide now an upper bound for $\mathbb{P}(F_2^0)$. For that we look at the probability of $\mathcal{A}$ querying one of these four oracles on the correct PRK$_{2e}$ in our protocol session.

Since for the adversary, PRK$_{2e}$ is here unpredictable, we obtain the following probability: $\frac{1}{2^{l_{hash}}}$ (since PRK$_{2e}$ has size $l_{hash}$) for the guess of PRK$_{2e}$. Now $\mathcal{A}$ can make at most $q_{RO_P^{l_2}}$ (resp. $q_{RO_P^{l_{key}}}$, $q_{RO_P^{l_{iv}}}$, and $q_{RO_P^{l_{mac}}}$) calls to $SO_P^{l_2}$ (resp. $SO_P^{l_{key}}$, $SO_P^{l_{iv}}$ and $SO_P^{l_{hash}}$), we thus have:

$$ \mathbb{P}(F_2^0) \leq \frac{q_{RO_P^{l_2}} + q_{RO_P^{l_{key}}} + q_{RO_P^{l_{iv}}} + q_{RO_P^{l_{mac}}}}{2^{l_{hash}}}. $$

Another way to detect the modification is on elements $S_1$ and $S_R$. But since he cannot corrupt proxies, this will not help him in its distinguishing task, except if he wins the experiment $E_{(KGen'',Enc'',Dec'')}^{\mathrm{IND}}(l_{key})$ (since elements contained in these ciphertexts are unpredictable), which is supposed difficult.

Note that this game is very similar to the game $\mathbb{G}_2^0$ of the key-security property proof, and so by the identical-until-bad lemma, we obtain:

$$ |\mathbb{P}(\mathbb{G}_8^0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_9^0 \Rightarrow 1)| \leq \mathbb{P}(F_2^0) + 2\mathrm{Adv}_{(KGen'',Enc'',Dec'')}^{\mathrm{IND}}(l_{key}) $$

and thus:

$$ |\mathbb{P}(\mathbb{G}_8^0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_9^0 \Rightarrow 1)| \leq \frac{q_{RO_P^{l_2}} + q_{RO_P^{l_{key}}} + q_{RO_P^{l_{iv}}} + q_{RO_P^{l_{mac}}}}{2^{l_{hash}}} + 2\mathrm{Adv}_{(KGen'',Enc'',Dec'')}^{\mathrm{IND}}(l_{key}). $$

† **Game $\mathbb{G}_8^1$**: This game is the same as the previous one (game $\mathbb{G}_7^1$) and works in the same vein as game $\mathbb{G}_8^0$ by adding a failure condition: if the adversary, during the protocol session, queries $SO_T$ on the
correct DIFFIE-HELLMAN value $g^{xr}$, then we abort and return a random bit. We then denote $F_1^1$ the event: $\mathcal{A}$ queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xr}$ (with $g^x$ the public DIFFIE-HELLMAN element of a challenger-controlled Initiator instance and $r$ a challenger-controlled Responder instance long-term secret key). If the event $F_1^1$ occurs, then challenger stops the simulation by returning a random bit. By the identical-until-bad lemma, we thus have:

$$|\mathbb{P}(\mathbb{G}_{7'}^1 \implies 1) - \mathbb{P}(\mathbb{G}_8^1 \implies 1)| \le \mathbb{P}(F_1^1).$$

Let's now provide a bound for $\mathbb{P}(F_1^1)$. For that we construct, by reduction, an adversary $\mathcal{B}_3^1$ against the GDH problem and we claim that:

$$\mathbb{P}(F_1^1) \le q_{\text{RO}_T} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda),$$

and finally:

$$|\mathbb{P}(\mathbb{G}_{7'}^1 \implies 1) - \mathbb{P}(\mathbb{G}_8^1 \implies 1)| \le q_{\text{RO}_T} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda).$$

‡ **Proof of the claim:** We want to provide an upper bound for $\mathbb{P}(F_1^1)$. As we did in the previous branch, by reduction we built an adversary $\mathcal{B}_3^1$ against the GDH problem.

On input a GDH challenge $(g, A = g^a, B = g^b)$ and having access to a DDH oracle, returning 1 if a tuple $(g, g^a, g^b, g^c)$ is a DIFFIE-HELLMAN tuple, and 0 otherwise, our algorithm must returns $g^{ab}$ in a polynomial time. For that, $\mathcal{B}_3^1$ simulates $\mathbb{G}_8^1$ for $\mathcal{A}(\text{pp})$ as follows, mainly faithfully, but with some modifications. Firstly, $\mathcal{B}_3^1$ embeds its challenge into the shared DIFFIE-HELLMAN value: it picks at random $k \in \mathbb{Z}_p$ and sets $X \leftarrow Ag^k$. Then for the chosen Responder, he sets $R \leftarrow B$.

Even if $b$ (from $g^b$) remains unknown by $\mathcal{B}_3^1$, the latter can continue the simulation by querying the $SO_T$ oracle on input $(X, R)$.

If $F_1^1$ occurs on that particular Responder instance, then the value $Z$ queried to the $SO_T$ oracle will equal $g^{(a+k)b}$. To detect that, $\mathcal{B}_3^1$ can compute $ZR^{-k}$, which if $F_1^1$ occurs will equal $g^{ab}g^{kb}g^{-kb} = g^{ab}$, and test this equality with its DDH oracle on input $(X, R, ZR^{-k})$, which will return 1 since $F_1^1$ occurs. So when the event happens, $\mathcal{B}_3^1$ wins.

To finally bound $\mathbb{P}(F_1^1)$, we remark that each time the $SO_T$ oracle is queried on input $Z$, the event $F_1^1$ can happen. Again, this implies that possibly $q_{\text{RO}_T}$ DDH-oracle queries might be useful to detect the event. Thus we have:

$$\mathbb{P}(F_4^1) \le q_{\text{RO}_T} \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(\lambda)$$

and this concludes the proof of the claim.

† **Game $\mathbb{G}_8^1$:** This game is the same as the previous one and we work in the same vein as $\mathbb{G}_9^0$. The challenger simulates $\text{PRK}_{3e2m}$ for both endpoints with a private oracle $SO_{\text{PRK}_{3e2m}}$. As before, this key is unpredictable by the adversary (in normal times, $\text{PRK}_{3e2m}$ is generated with $SO_T$, $\text{salt}_{3e2m}$ and $g^{xr}$).

One way to detect the modification is for the adversary to ask $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xr}$. Thanks to the event $F_1^1$ the simulation is already stopped in this situation. Another way to detect it is to query $SO_P^{l_{\text{hash}}}$, or $SO_P^{l_{\text{key}}}$, or $SO_P^{l_{\text{iv}}}$, or $SO_P^{l_{\text{mac}}}$ on the correct value $\text{PRK}_{3e2m}$ which unpredictable at this stage. We denote $F_1^1$, the event: $\mathcal{A}$ queries $SO_P^{l_{\text{hash}}}$, or $SO_P^{l_{\text{key}}}$, or $SO_P^{l_{\text{iv}}}$, or $SO_P^{l_{\text{mac}}}$ on the correct value $\text{PRK}_{3e2m}$ for a session in which the latter is unpredictable. If $F_1^1$ happens, we stop the simulation and return a random bit. We can provide now an upper bound for $\mathbb{P}(F_1^1)$. For that we look at the probability of $\mathcal{A}$ querying one of these four oracles on the correct $\text{PRK}_{3e2m}$ in our protocol session. Since for the adversary, $\text{PRK}_{3e2m}$ is here unpredictable, we obtain the following probability:

$$\frac{1}{2^{l_{\text{hash}}}} \text{ (since } \text{PRK}_{3e2m} \text{ has size } l_{\text{hash}} \text{) for the guess of } \text{PRK}_{3e2m}. \text{ Now } \mathcal{A} \text{ can make at most } q_{\text{RO}_P, l_{\text{hash}}} \text{ (resp.}$$
$q_{RO_P^{l_{key}}}$, $q_{RO_P^{l_{iv}}}$, and $q_{RO_P^{l_{mac}}}$ calls to $SO_P^{l_{hash}}$ (resp. $SO_P^{l_{key}}$, $SO_P^{l_{iv}}$ and $SO_P^{l_{hash}}$), we thus have:

$$ \mathbb{P}(F_{1'}^1) \leq \frac{q_{RO_P^{l_{hash}}} + q_{RO_P^{l_{key}}} + q_{RO_P^{l_{iv}}} + q_{RO_P^{l_{mac}}}}{2^{l_{hash}}}. $$

Again, another way to detect the modification is on elements $S_I$ and $S_R$, thus by the identical-until-bad lemma, we obtain:

$$ |\mathbb{P}(\mathbb{G}_8^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{8'}^1 \Rightarrow 1)| \leq \mathbb{P}(F_{1'}^1) + 2\mathrm{Adv}^{\mathrm{IND}}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''})}(l_{\mathrm{key}}) $$

and thus:

$$ |\mathbb{P}(\mathbb{G}_8^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{8'}^1 \Rightarrow 1)| \leq \frac{q_{RO_P^{l_{hash}}} + q_{RO_P^{l_{key}}} + q_{RO_P^{l_{iv}}} + q_{RO_P^{l_{mac}}}}{2^{l_{hash}}} + 2\mathrm{Adv}^{\mathrm{IND}}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''})}(l_{\mathrm{key}}). $$

† **Game $\mathbb{G}_8^1$**: This game is the same as game $\mathbb{G}_{8'}^1$, except that we apply the modification of the game $\mathbb{G}_8^0$. We perform the same analysis and reduction, and thus obtain, thanks to a p.p.t. algorithm $\mathcal{B}_4^1$:

$$ |\mathbb{P}(\mathbb{G}_{8'}^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_9^1 \Rightarrow 1)| \leq q_{RO_T} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda). $$

† **Game $\mathbb{G}_{9'}^1$**: This game is the same as the previous one, except that we apply the modification of the game $\mathbb{G}_9^0$. To detect that change, $\mathcal{A}$ has two options: queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xy}$, which is as usual excluded at this stage or pick a random PRK$_{2e*}$ from $\{0, 1\}^{l_{hash}}$, hopping for PRK$_{2e*}$ = PRK$_{2e}$. Similarly we denote $F_{2'}^1$ the event: $\mathcal{A}$ queries $SO_P^{l_2}$ on the correct value PRK$_{2e}$ for a session in which the latter is unpredictable (here only $SO_P^{l_2}$ uses PRK$_{2e}$). If $F_{2'}^1$ happens, we stop the simulation and return a random bit. In a similar way as in game $\mathbb{G}_9^0$, we provide an upper bound for $\mathbb{P}(F_{2'}^1)$ with:

$$ \mathbb{P}(F_{2'}^1) \leq \frac{q_{RO_P^{l_2}}}{2^{l_{hash}}}. $$

Here again $\mathcal{A}$ can detect the modification on $S_I$ and $S_R$. By the identical-until-bad lemma, we obtain:

$$ |\mathbb{P}(\mathbb{G}_9^1 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{9'}^1 \Rightarrow 1)| \leq \frac{q_{RO_P^{l_2}}}{2^{l_{hash}}} + 2\mathrm{Adv}^{\mathrm{IND}}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''})}(l_{\mathrm{key}}). $$

† **Game $\mathbb{G}_8^2$**: This game is the same as $\mathbb{G}_7^2$ and we keep going on the same vein as $\mathbb{G}_8^1$. If the adversary, during the session queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{iy}$, then we abort and return a random bit. We then denote $F_1^2$ the event: $\mathcal{A}$ queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{iy}$. If the event $F_1^2$ occurs, then challenger stops the simulation by returning a random bit. By the identical-until-bad lemma, we thus have:

$$ |\mathbb{P}(\mathbb{G}_7^2 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_8^2 \Rightarrow 1)| \leq \mathbb{P}(F_1^2). $$

As in game $\mathbb{G}_8^1$ we construct, by reduction, an adversary $\mathcal{B}_3^2$ against the GDH problem and we bound $\mathbb{P}(F_1^2)$ by:

$$ \mathbb{P}(F_1^2) \leq q_{RO_T} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda), $$

and finally:

$$ |\mathbb{P}(\mathbb{G}_7^2 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_8^2 \Rightarrow 1)| \leq q_{RO_T} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda). $$
† **Game $G_8^2$**: This game is the same as the previous one and works in the same vein as $G_8^1$. Here the challenger generates the key PRK$_{4e3m}$ for both endpoints thanks to a private oracle $SO_{PRK_{4e3m}}$ (in normal times, PRK$_{4e3m}$ is generated with $SO_T$, salt$_{4e3m}$ and $g^{iy}$). We perform now an analysis of what is happening in this case, and we obtain, similarly to game $G_8^1$:

$$|\mathbb{P}(G_8^2 \Rightarrow 1) - \mathbb{P}(G_8^2 \Rightarrow 1)| \le \frac{q_{\mathrm{RO}_P^{l'\mathrm{hash}}} + q_{\mathrm{RO}_P^{l'\mathrm{key}}} + q_{\mathrm{RO}_P^{l'\mathrm{iv}}} + q_{\mathrm{RO}_P^{l'\mathrm{mac}}} + 2\mathrm{Adv}^{\mathrm{IND}}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''})}(l_{\mathrm{key}})}{2^{l'\mathrm{hash}}}.$$

† **Game $G_9^2$**: This game is the same as the previous one, except that we apply the modification of the game $G_9^1$. We perform the same analysis and reduction, and thus obtain, thanks to a p.p.t. algorithm $B_4^2$:

$$|\mathbb{P}(G_9^2 \Rightarrow 1) - \mathbb{P}(G_9^2 \Rightarrow 1)| \le q_{\mathrm{RO}_T} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda).$$

† **Game $G_{9'}^2$**: This game is the same as the previous one, except that we apply the modification of the game $G_{9'}^1$. We can perform the same analysis and hence obtain thanks to the identical-until-bad lemma:

$$|\mathbb{P}(G_9^2 \Rightarrow 1) - \mathbb{P}(G_{9'}^2 \Rightarrow 1)| \le \frac{q_{\mathrm{RO}_P^{l'2}}}{2^{l'\mathrm{hash}}} + 2\mathrm{Adv}^{\mathrm{IND}}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''})}(l_{\mathrm{key}}).$$

† **Game $G_8^3$**: This game follows $G_8^3$, and works in the same way as $G_8^1$, with the appropriate notations. After defining the event $F_1^3$, we obtain the same results and thus have, thanks to a p.p.t. algorithm $B_3^3$:

$$|\mathbb{P}(G_7^3 \Rightarrow 1) - \mathbb{P}(G_8^3 \Rightarrow 1)| \le q_{\mathrm{RO}_T} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda).$$

† **Game $G_8^3$**: This game is the same as the previous one, and we apply the same modification as in $G_8^1$ (with the appropriate notations), defining the event $F_1^3$. Again we bound $\mathbb{P}(F_1^3)$ and thanks to the identical-until-bad lemma we obtain the same result:

$$|\mathbb{P}(G_8^3 \Rightarrow 1) - \mathbb{P}(G_{8'}^3 \Rightarrow 1)| \le \frac{q_{\mathrm{RO}_P^{l'\mathrm{hash}}} + q_{\mathrm{RO}_P^{l'\mathrm{key}}} + q_{\mathrm{RO}_P^{l'\mathrm{iv}}} + q_{\mathrm{RO}_P^{l'\mathrm{mac}}} + 2\mathrm{Adv}^{\mathrm{IND}}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''})}(l_{\mathrm{key}})}{2^{l'\mathrm{hash}}}.$$

† **Game $G_8^3$**: This game is the same as the previous one and works in the same way as $G_8^2$, with the appropriate notations. We thus obtain:

$$|\mathbb{P}(G_8^3 \Rightarrow 1) - \mathbb{P}(G_9^3 \Rightarrow 1)| \le q_{\mathrm{RO}_T} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda).$$

† **Game $G_{9'}^3$**: This game is the same as the previous one, and we apply the same modification as in $G_{9'}^2$ (with the appropriate notations). Again we obtain the same result:

$$|\mathbb{P}(G_{9'}^3 \Rightarrow 1) - \mathbb{P}(G_9^3 \Rightarrow 1)| \le \frac{q_{\mathrm{RO}_P^{l'\mathrm{hash}}} + q_{\mathrm{RO}_P^{l'\mathrm{key}}} + q_{\mathrm{RO}_P^{l'\mathrm{iv}}} + q_{\mathrm{RO}_P^{l'\mathrm{mac}}} + 2\mathrm{Adv}^{\mathrm{IND}}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''})}(l_{\mathrm{key}})}{2^{l'\mathrm{hash}}}.$$

† **Game $G_{9'}^3$**: Here again, this game is the same as the previous one, and works in the same vein as $G_9^1$. This leads again, thanks to a p.p.t. algorithm $B_5^3$, to:
$$|\mathbb{P}(G_{9'}^3 \Rightarrow 1) - \mathbb{P}(G_{9''}^3 \Rightarrow 1)| \le q_{RO_T} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda).$$

† **Game $G_{9''}^3$**: This game is the same as the previous one, and we apply the same modification as in game $G_{9'}^1$ (with the appropriate notations). We thus obtain the same result:

$$|\mathbb{P}(G_{9''}^3 \Rightarrow 1) - \mathbb{P}(G_{9'''}^3 \Rightarrow 1)| \le \frac{q_{RO_P} l^2}{2^{l_{\text{hash}}}} + 2\mathrm{Adv}_{(K\text{Gen}'', \text{Enc}'', \text{Dec}'')}(l_{\text{key}}).$$

We can now conclude the four branches. We explicit games $G_{10}$ and $G_{11}$ instead of games $G_{10}^{0,1,2,3}$ and $G_{11}^{0,1,2,3}$ because, in the two cases, the four games are very similar and to make it lighter, we just explain, in parentheses, what can change.

† **Game $G_{10}$**: This game is the same as the previous one, except that, we generate the keys $sk_2$ and $sk_3$ thanks to private oracles $SO_{sk_2}$ and $SO_{sk_3}$, which work in the same vein as $SO_P^{l^2}$ and $SO_P^{l_{\text{key}}}$, but which are not accessible to $\mathcal{A}$ (usually $sk_2$ and $sk_3$ are obtained using PRK$_{2e}$ (or PRK$_{3e2m}$ or PRK$_{4e3m}$)). Once again the adversary may detect this modification only if he queries $SO_P^{l^2}$ or $SO_P^{l_{\text{key}}}$ on the public (randomly generated) key PRK$_{2e}$ (or PRK$_{3e2m}$ or PRK$_{4e3m}$). Since there is $2^{l_{\text{hash}}}$ possibility for PRK$_{2e}$ (or PRK$_{3e2m}$ or PRK$_{4e3m}$), the probability the adversary made these particular queries is then $\frac{2}{2^{l_{\text{hash}}}}$. Note that here again $\mathcal{A}$ may detect a change in the ciphertexts $S_I$ and $S_R$, but we can make the same analysis we did before. So finally we have:

$$|\mathbb{P}(G_9 \Rightarrow 1) - \mathbb{P}(G_{10} \Rightarrow 1)| \le \frac{2}{2^{l_{\text{hash}}}} + 2\mathrm{Adv}_{(K\text{Gen}'', \text{Enc}'', \text{Dec}'') , \mathcal{A}}^{\mathrm{IND}}(l_{\text{key}}).$$

† **Game $G_{11}$**: This game works in the same vein as the previous one, except that we replace the choice of $ID\_CRED\_R \leftarrow ID\_CRED\_R_b$ by $ID\_CRED\_R \leftarrow ID\_CRED\_R_{1-b}$. So here we simulate the experiment $\mathbb{E}_{\overline{LI-EDHOC}, \mathcal{A}}^{\mathrm{Id-Responder-0}}(\lambda)$ for $\mathcal{A}$ (despite everything, we remain in the context where PRK$_{2e}$ (or PRK$_{3e2m}$ or PRK$_{4e3m}$), $sk_2$ and $sk_3$ are simulated thanks to private oracles). In this situation, the adversary will receive different ciphertexts $c_2$ and $c_3$, and also $S_I$ and $S_R$ (and also $c_4$, but there is nothing to learn from $c_4$ (or its decryption)). So he detects the changes we made, but this will not help him in its distinguishing task. Indeed, here he knows that the four messages did not come from the same Responder and he wants to succeed in distinguishing them. But since the keys $sk_2$ and $sk_3$ are random at this point, the adversary is forced to win the experiments $\mathbb{E}_{(K\text{Gen},\text{Enc},\text{Dec}), \mathcal{A}}^{\mathrm{IND}}(l_2)$, $\mathbb{E}_{(K\text{Gen}'',\text{Enc}'',\text{Dec}''), \mathcal{A}}^{\mathrm{IND}}(l_{\text{key}})$ and $\mathbb{E}_{\text{AEAD}, \mathcal{A}}^{\mathrm{IND-CPA}}(l_{\text{key}})$ (that is why we did not randomize the initialization vector $IV_3$), which were previously assumed to be very difficult to win. So finally we bound the winning advantage of the adversary with this game hop as follows:

$$|\mathbb{P}(G_{10} \Rightarrow 1) - \mathbb{P}(G_{11} \Rightarrow 1)| \le \mathrm{Adv}_{(K\text{Gen},\text{Enc},\text{Dec}), \mathcal{A}}^{\mathrm{IND}}(l_2) + \mathrm{Adv}_{\text{AEAD}, \mathcal{A}}^{\mathrm{IND-CPA}}(l_{\text{key}}) + 2\mathrm{Adv}_{(K\text{Gen}'',\text{Enc}'',\text{Dec}'')}(l_{\text{key}}).$$

So finally, to summarize, we have:
$$
\begin{align*}
\mathrm{Adv}_{\mathrm{LI}-\mathrm{EDHOC}, \mathcal{A}}^{\mathrm{Id-Pro-Resp}}(\lambda) &= \left| \mathbb{P}(\mathbb{E}_{\mathrm{LI}-\mathrm{EDHOC}, \mathcal{A}}^{\mathrm{Id-Responder}-1}(\lambda) \Rightarrow 1) - \mathbb{P}(\mathbb{E}_{\mathrm{LI}-\mathrm{EDHOC}, \mathcal{A}}^{\mathrm{Id-Responder}-0}(\lambda) \Rightarrow 1) \right| \\
&= \left| \mathbb{P}(\mathbb{G}_0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{11} \Rightarrow 1) \right| \\
&\le \left| \mathbb{P}(\mathbb{G}_0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_1 \Rightarrow 1) \right| + \dots + \left| \mathbb{P}(\mathbb{G}_{10} \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{11} \Rightarrow 1) \right| \\
&\le \frac{(q_{\mathrm{SO}_T} + q_{\mathrm{SO}_P}^{\mathrm{l}^{\mathrm{hash}}})^2 + (q_{\mathrm{SO}_T} + q_{\mathrm{SO}_H})^2 + (q_{\mathrm{SO}_P}^{\mathrm{l}^{\mathrm{hash}}} + q_{\mathrm{SO}_H})^2}{2^{l_{\mathrm{hash}}+1}} + 12 \mathrm{Adv}_{\mathbb{G}}^{\mathrm{DDH}}(\lambda) \\
&\quad + 8 q_{\mathrm{RO}_T} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda) + 5 \cdot \frac{q_{\mathrm{RO}_P}^{\mathrm{l}^{\mathrm{key}}} + q_{\mathrm{RO}_P}^{\mathrm{l}_{\mathrm{iv}}} + q_{\mathrm{RO}_P}^{\mathrm{l}_{\mathrm{mac}}}}{2^{l_{\mathrm{hash}}}} + 4 \cdot \frac{q_{\mathrm{RO}_P}^{\mathrm{l}^{\mathrm{l}_2}} + q_{\mathrm{RO}_P}^{\mathrm{l}^{\mathrm{hash}}} + 2}{2^{l_{\mathrm{hash}}}} \\
&\quad + 4 \cdot \left( 8 \mathrm{Adv}_{(\mathrm{KGen}''_{\mathrm{Enc}''}, \mathrm{Dec}''_{\mathrm{Enc}''})}^{\mathrm{IND}}(l_{\mathrm{key}}) + \mathrm{Adv}_{(\mathrm{KGen}, \mathrm{Enc}, \mathrm{Dec})}^{\mathrm{IND}}(l_2) + \mathrm{Adv}_{\mathrm{AEAD}}^{\mathrm{IND-CPA}}(l_{\mathrm{key}}) \right)
\end{align*}
$$

and this concludes the proof.

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

### 7.4.2 Initiator identity protection

We continue with that property on the Initiator side.

**Theorem 6 (Initiator identity protecting LI-EDHOC protocol)** *Under the assumption that the DDH and the GDH problems are hard to solve in $\mathbb{G}$, that our encryption scheme $(\mathrm{KGen}''_{\mathrm{Enc}''}, \mathrm{Dec}''_{\mathrm{Enc}''})$ is IND-secure, that our encryption scheme $(\mathrm{KGen}', \mathrm{Enc}', \mathrm{Dec}')$ in an AEAD-encryption scheme IND-CPA-secure, and that our digital signature scheme DS is EUF-CMA-secure, then the LI-EDHOC protocol, in its four versions, protect the Initiator's identity against (partial) active adversaries. More precisely, for all p.p.t. adversary $\mathcal{A}$ making at most $q_{\mathrm{RO}_T}$ (resp. $q_{\mathrm{RO}_P}$ and $q_{\mathrm{RO}_H}$) queries to the $\mathrm{RO}_T$ (resp. $\mathrm{RO}_P$ and $\mathrm{RO}_H$) oracle, denoting $N$ the number of endpoints, we have:*

$$
\begin{align*}
\mathrm{Adv}_{\mathrm{LI}-\mathrm{EDHOC}, \mathcal{A}}^{\mathrm{Id-Pro-Init}}(\lambda) &\le \frac{(q_{\mathrm{RO}_T} + q_{\mathrm{RO}_P^{\mathrm{l}^{\mathrm{hash}}}})^2 + (q_{\mathrm{RO}_T} + q_{\mathrm{RO}_H})^2 + (q_{\mathrm{RO}_P^{\mathrm{l}^{\mathrm{hash}}}} + q_{\mathrm{RO}_H})^2}{2^{l_{\mathrm{hash}}+1}} + N \cdot \left[ 3 \mathrm{Adv}_{\mathbb{G}}^{\mathrm{DDH}}(\lambda) \right. \\
&\quad + 5 q_{\mathrm{RO}_T} \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda) + 3 \cdot \frac{q_{\mathrm{RO}_P^{\mathrm{l}^{\mathrm{hash}}}} + q_{\mathrm{RO}_P^{\mathrm{l}^{\mathrm{key}}}} + q_{\mathrm{RO}_P^{\mathrm{l}_{\mathrm{iv}}}} + q_{\mathrm{RO}_P^{\mathrm{l}_{\mathrm{mac}}}}}{2^{l_{\mathrm{hash}}}} + \frac{q_{\mathrm{RO}_P^{\mathrm{l}^{\mathrm{l}_2}}} + 1}{2^{l_{\mathrm{hash}}-1}} \\
&\quad \left. + 2 \mathrm{Adv}_{\mathrm{AEAD}}^{\mathrm{IND-CPA}}(l_{\mathrm{key}}) + 9 \mathrm{Adv}_{(\mathrm{KGen}''_{\mathrm{Enc}''}, \mathrm{Dec}''_{\mathrm{Enc}''})}^{\mathrm{IND}}(l_{\mathrm{key}}) + 2 \mathrm{Adv}_{\mathrm{DS}}^{\mathrm{EUF-CMA}}(\lambda) \right]
\end{align*}
$$

**Proof 6 (of theorem 6)** To begin with, here again, in FIGURE 35, we remind the Initiator identity protection security games.

We proceed by game hops which are depicted in FIGURES 36 and 37 below. Firstly, game $\mathbb{G}_0$ is a reformulation of the original experiment $\mathbb{E}_{\mathrm{LI}-\mathrm{EDHOC}, \mathcal{A}}^{\mathrm{IdPro-Initiator}-1}(\lambda)$. Then with games $\mathbb{G}_1$, $\mathbb{G}_2$, and $\mathbb{G}_3$ we simulate random oracles $\mathrm{RO}$ as list, in order to manipulate them later, as in the previous proof. We next prevent collisions on some oracles with games $\mathbb{G}_4$ and $\mathbb{G}_5$, and with game $\mathbb{G}_6$ we try to guess in advance the adversary chosen Responder. We now need to divide our analysis into three branches, in order to distinguish between methods 0 and 2, 1, and 3 of the protocol (denoting games with exponent $0/2$, 1, and 3 to indicate the method used in the current game). On the first branch corresponding to methods 0 and 2, with games $\mathbb{G}_7^{0/2}$ and $\mathbb{G}_8^{0/2}$ we prevent $\mathcal{A}$ from forging the Responder signature $\sigma_2$, and we conclude this branch with the game $\mathbb{G}_9^{0/2}$ corresponding the original experiment $\mathbb{E}_{\mathrm{LI}-\mathrm{EDHOC}, \mathcal{A}}^{\mathrm{IdPro-Initiator}-0}(\lambda)$. The two other branches correspond to methods 1 and 3, but are very similar. With games $\mathbb{G}_7^{1/3}$ we randomize the H elements in order to prevent the adversary from obtaining informations about $g^{xy}$ (or $g^{iy}$ or $g^{xr}$). With the pack of games $\mathbb{G}_8^{1/3}$, $\mathbb{G}_9^{1/3}$, $\mathbb{G}_{10}^{1/3}$ and $\mathbb{G}_{11}^{1/3}$ we randomize the key-schedule elements to limit the capacity of $\mathcal{A}$ in predicting the encryption keys (and thus potentially learning the identity of the Initiator). Next with game $\mathbb{G}_{12}^{1/3}$ we randomize the encryption key $\mathrm{sk}_3$ to make it unpredictable to $\mathcal{A}$. Finally with game $\mathbb{G}_{13}^{1/3}$ we turn the game into the original experiment $\mathbb{E}_{\mathrm{LI}-\mathrm{EDHOC}, \mathcal{A}}^{\mathrm{IdPro-Initiator}-0}(\lambda)$, so we can conclude on the advantage of $\mathcal{A}$.
<figure><img src="image_25.png" /><figcaption>FIGURE 35 – The LI-EDHOC Initiator identity protection security games. By ESet<sub>meth</sub> we mean the set of all endpoints running the protocol with the same method (0,1,2, or 3).</figcaption></figure>

† **Game $G_0$**: This first game is the original experiment $E_{\text{LI-EDHOC},\mathcal{A}}^{\text{Id-Initiator}-1}(\lambda)$. As usually we have:

$$ \mathbb{P}(G_0 = 1) = \mathbb{P}(E_{\text{LI-EDHOC},\mathcal{A}}^{\text{Id-Initiator}-1}(\lambda) = 1). $$

† **Game $G_1$**: As in the Responder identity protection proof, this game is the same as the previous one except that we simulate $RO_{\mathcal{H}}$ thanks to a list denoted $SO_{\mathcal{H}}$. As usually we obtain:

$$ \mathbb{P}(G_1 = 1) = \mathbb{P}(G_0 = 1). $$

† **Game $G_2$**: Again, this game works as the previous one, except that we simulate $RO_{\mathcal{P}}$ thanks to a list denoted $SO_{\mathcal{P}}$ (still depending on the digest size, but again it does not impact the analysis). We thus obtain:

$$ \mathbb{P}(G_2 = 1) = \mathbb{P}(G_1 = 1). $$

† **Game $G_3$**: To finish with the simulation of random oracles, this game is the same as the previous one, except that this time we simulate $RO_{\mathcal{T}}$ thanks to a special list denoted $SO_{\mathcal{T}}$ (following the same construction as in $G_5$ in the key-security property proof (on page 55)). We obtain as before:

$$ \mathbb{P}(G_3 = 1) = \mathbb{P}(G_2 = 1). $$

† **Game $G_4$**: With this game and the next one, we want to avoid collision between some simulated random oracles. So this game is the same as the previous one, except that this time we raise a bad flag bad<sub>3</sub> to true when a collision between $SO_{\mathcal{H}}$ and $SO_{\mathcal{T}}$, or $SO_{\mathcal{T}}$ and $SO_{\mathcal{P}}^{l_{\text{hash}}}$, or $SO_{\mathcal{H}}$ and $SO_{\mathcal{P}}^{l_{\text{hash}}}$ occurs. This change is indistinguishable by the adversary and we obtain, as before:

$$ \mathbb{P}(G_4 = 1) = \mathbb{P}(G_3 = 1). $$