<figure><img src="image_26.png" /><figcaption>FIGURE 36 – First steps of the game-schedule for the Initiator identity protection property.</figcaption></figure>

† **Game $G_5$**: This game is the same as the previous one, except that this time we abort when the bad flag $bad_3$ is set to true. Using the same analysis as is game $G_7$ of the key-secure property proof (on page 56), we bound the winning advantage of the adversary with this game hop as follows:

$$ |\mathbb{P}(G_4 \Rightarrow 1) - \mathbb{P}(G_5 \Rightarrow 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} $$

† **Game $G_6$**: This game is the same as the previous one ($G_5$), but here we try to guess in advance the Responder identity $ID\_CRED\_R$ chosen by $\mathcal{A}$ at the beginning of the game. With this game hop, the winning advantage of $\mathcal{A}$ is increased by a factor equaling the probability of guessing correctly the Responder. Denoting $N = |ESet_{meth}|$, we thus have:

$$ |\mathbb{P}(G_5 \Rightarrow 1) - \mathbb{P}(E_{LI-EDHOC,\mathcal{A}}^{Id-Initiator-0}(\lambda) \Rightarrow 1)| \le N \cdot |\mathbb{P}(G_6 \Rightarrow 1) - \mathbb{P}(E_{LI-EDHOC,\mathcal{A}}^{Id-Initiator-0}(\lambda) \Rightarrow 1)| $$

From now on, we separate our analysis into three branches. The first one concerns the versions of the protocol in which the Responder uses a signature to authenticate (i.e., methods 0 and 2), and the second and the third ones concern the two other versions (respectively methods 1 and 3). The game hops steps are depicted in FIGURE 37 below.

So we start with the first branch, i.e., methods 0 and 2.

† **Game $G_7^{0/2}$**: This game is the same as the previous one, except that we raised a bad flag $bad_{sign}$ to true when $\mathcal{A}$ forges the signature $\sigma_2$ in RespRun2. This change is internal to the game, and thus indistinguishable by $\mathcal{A}$. This leads to:

$$ \mathbb{P}(G_7^{0/2} \Rightarrow 1) = \mathbb{P}(G_6 \Rightarrow 1). $$
<figure><img src="image_27.png" /><figcaption>FIGURE 37 – Continuation of the game-schedule for the Initiator identity protection property.</figcaption></figure>

† **Game $G_8^{0/2}$**: This game is the same as game $G_7^{0/2}$, except that we abort and return a random bit when the bad flag bad$_{sign}$ is raised to true. By the identical-until-bad lemma we have:

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

where $F_1^{0/2}$ is the event: bad$_{sign}$ is raised to true in game $G_7^{0/2}$.

We claim that by reduction we can build a p.p.t. adversary $\mathcal{B}_1^{0/2}$ against the EUF-CMA-security property of our digital signature scheme DS, which leads to:

$$\mathbb{P}(F_1^{0/2}) \le \mathrm{Adv}_{\mathrm{DS},\mathcal{A}}^{\mathrm{EUF-CMA}}(\lambda)$$

and thus to:

$$|\mathbb{P}(G_7^{0/2} \Rightarrow 1) - \mathbb{P}(G_8^{0/2} \Rightarrow 1)| \le \mathrm{Adv}_{\mathrm{DS},\mathcal{A}}^{\mathrm{EUF-CMA}}(\lambda).$$

‡ **Proof of the claim:** We begin by assuming that there exists an adversary $\mathcal{A}$ that wins the game $G_7^{0/2}$ with a non negligible advantage $\epsilon_{\mathcal{A}}(\lambda)$, by forging the signature $\sigma_2$. We can now present the
construction of $\mathcal{B}_1^{0/2}$. To begin with, the challenger generates a pair of public/private signature keys ($\text{ssk}, \text{spk}$) with the DS.Gen algorithm, and gives the public signing key $\widetilde{\text{spk}}$ to $\mathcal{B}_1^{0/2}$. Algorithm $\mathcal{B}_1^{0/2}$ wins if it sends to its challenger a message/signature pair $(m, \sigma)$ he did not generate, and such that $\text{DS.Verif}(\widetilde{\text{spk}}, m, \sigma) = 1$, in a polynomial time.

So $\mathcal{B}_1^{0/2}$ will start by simulating $\mathbb{G}_7^{0/2}$ to $\mathcal{A}$ faithfully, except for one point: if we denote by $\mathbb{R}$ the guessed Responder, then $\mathcal{B}_1^{0/2}$ sets $\mathbb{R}.\text{spk} \leftarrow \widetilde{\text{spk}}$.

Now when $\mathcal{B}_1^{0/2}$ simulates the continuation of the protocol run to $\mathcal{A}$, if the signature verification is successful, since $\mathbb{R}$ is not corrupted on its long-term signing keys, $\mathcal{B}_1^{0/2}$ knows that $\mathcal{A}$ forges the signature $\sigma_2$ on message $m = (l_{\text{sig}} \| \text{CTX}_2 \| t_2)$, and so $\mathcal{B}_1^{0/2}$ wins and breaks the EUF-CMA security of DS. So in this case we have $\text{Adv}_{\text{DS}, \mathcal{B}_1^{0/2}}^{\text{EUF-CMA}}(\lambda) \ge \epsilon_{\mathcal{A}}(\lambda)$.

We thus built well our p.p.t. adversary $\mathcal{B}_1^{0/2}$ which leads us to:

$$ \mathbb{P}(F_1^{0/2}) \le \text{Adv}_{\text{DS}, \mathcal{A}}^{\text{EUF-CMA}}(\lambda) $$

and this concludes the proof of the claim.

† **Game $\mathbb{G}_9^{0/2}$**: This game is the same as the previous one, except that we replace the choice of $\text{ID\_CRED\_I} \leftarrow \text{ID\_CRED\_I}_b$ by $\text{ID\_CRED\_I} \leftarrow \text{ID\_CRED\_I}_{1-b}$. As in the previous proof, we here simulate the experiment $\mathbb{E}_{\text{LI-EDHOC}, \mathcal{A}}^{\text{Id-Initiator-0}}(\lambda)$ for $\mathcal{A}$. Since in this situation $\mathcal{A}$ can anymore forge the signature $\sigma_2$, then he cannot obtain the continuation of the protocol run, i.e., messages $M_3$ and $M'_3$, and so he cannot detect this change. Moreover, $M_1$ is not link to $\text{ID\_CRED\_I}$, and so $\mathcal{A}$ cannot detect this change here again. So finally we have:

$$ \mathbb{P}(\mathbb{E}_{\text{LI-EDHOC}, \mathcal{A}}^{\text{Id-Initiator-0}}(\lambda) \implies 1) = \mathbb{P}(\mathbb{G}_9^{0/2} \implies 1) = \mathbb{P}(\mathbb{G}_8^{0/2} \implies 1). $$

So finally, to summarize and finalize this branch, we have:

$$ \begin{aligned} \text{Adv}_{\text{LI-EDHOC}, 0/2, \mathcal{A}}^{\text{Id-Pro-Init}}(\lambda) &= \left| \mathbb{P}(\mathbb{E}_{\text{LI-EDHOC}, \mathcal{A}}^{\text{Id-Initiator-1}}(\lambda) \implies 1) - \mathbb{P}(\mathbb{E}_{\text{LI-EDHOC}, \mathcal{A}}^{\text{Id-Initiator-0}}(\lambda) \implies 1) \right| \\ &= \left| \mathbb{P}(\mathbb{G}_0 \implies 1) - \mathbb{P}(\mathbb{G}_9^{0/2} \implies 1) \right| \\ &\le \left| \mathbb{P}(\mathbb{G}_0 \implies 1) - \mathbb{P}(\mathbb{G}_1 \implies 1) \right| + \cdots + \left| \mathbb{P}(\mathbb{G}_8^{0/2} \implies 1) - \mathbb{P}(\mathbb{G}_9^{0/2} \implies 1) \right| \\ &\le \frac{(q_{\text{SO}_T} + q_{\text{SO}_{p'\text{hash}}})^2 + (q_{\text{SO}_T} + q_{\text{SO}_H})^2 + (q_{\text{SO}_{p'\text{hash}}} + q_{\text{SO}_H})^2}{2l_{\text{hash}}+1} + 2N \cdot \text{Adv}_{\text{DS}}^{\text{EUF-CMA}}(\lambda) \end{aligned} $$

We now focus on the two remaining branches, i.e., methods 1 and 3.

† **Game $\mathbb{G}_7^1$**: With the next game pack, we prevent the adversary from obtaining information from the $\mathbb{H}$ elements. This game is the same as the previous one (gamme $\mathbb{G}_6$) except that this time we pick at random, according to the uniform distribution on the group $\mathbb{G}$, elements $H_1$ and $H_1^1$ of the Initiator (and of course simulate the proof $n_1$ with the simulator $\text{Sim}_{\text{SoK}}$ associated to the SoK). As in game $\mathbb{G}_6^0$ of the Responder identity protection property proof, by reduction (slightly adapted), we can build a p.p.t. algorithm $\mathcal{B}_1^1$ against the DDH problem, and thus we have:

$$ \left| \mathbb{P}(\mathbb{G}_6 \implies 1) - \mathbb{P}(\mathbb{G}_7^1 \implies 1) \right| \le \text{Adv}_{\mathcal{A}}^{\text{DDH}}(\lambda). $$
† **Game $G_7^3$**: This game is the same as the previous one (game $G_6$), and works in the same vein as game $G_7^1$. Thanks to a p.p.t. algorithm $B_1^3$, we have:

$$ |\mathbb{P}(G_6 \implies 1) - \mathbb{P}(G_7^3 \implies 1)| \leq \textcolor{red}{\text{Adv}}_{\mathcal{A}}^{\text{DDH}}(\lambda). $$

† **Game $G_7^3$**: 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$, the element $H_1^2$ of the Initiator (and of course simulate the proof $n_i$ with the simulator $Sim_{SoK}$ associated to the SoK). As in game $G_6^0$ of the Responder identity protection property proof, by reduction (slightly adapted), we can build a p.p.t. algorithm $B_1^3$, against the DDH problem, and thus we have:

$$ |\mathbb{P}(G_7^3 \implies 1) - \mathbb{P}(G_7^3 \implies 1)| \leq \textcolor{red}{\text{Adv}}_{\mathcal{A}}^{\text{DDH}}(\lambda). $$

† **Game $G_8^1$**: This game is the same as the previous one (game $G_7^1$) and works in the same vein as game $G_8^1$ of the Responder identity protection property proof, i.e., 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$ an adversary-controlled, not corrupted, 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}(G_7^1 \implies 1) - \mathbb{P}(G_8^1 \implies 1)| \leq \mathbb{P}(F_1^1). $$

As we did in game $G_8^1$ of the Responder identity protection property proof, we construct, by reduction, an adversary $B_2^1$ against the GDH problem to bound $\mathbb{P}(F_1^1)$ and we claim that:

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

and finally:

$$ |\mathbb{P}(G_7^1 \implies 1) - \mathbb{P}(G_8^1 \implies 1)| \leq q_{RO_T} \cdot \textcolor{red}{\text{Adv}}_{\mathbb{G}}^{\text{GDH}}(\lambda). $$

† **Game $G_9^1$**: This game is the same as the previous one and we work in the same vein as $G_9^0$ of the Responder identity protection property proof. The challenger simulates $PRK_{3e2m}$ for the Initiator with a private oracle $SO_{PRK_{3e2m}}$. As before, this key is unpredictable by the adversary (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^{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_{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_2^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_2^1$ happens, we stop the simulation and return a random bit. We can provide now an upper bound for $\mathbb{P}(F_2^1)$. For that we look at the probability of $\mathcal{A}$ querying one of these four oracles on the correct $PRK_{3e2m}$ in our protocol 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_2^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 the element $S_I$, thus by the identical-until-bad lemma, we obtain:

$$ \left| \mathbb{P}(G_8^1 \Rightarrow 1) - \mathbb{P}(G_9^1 \Rightarrow 1) \right| \le \mathbb{P}(F_2^1) + \mathrm{Adv}^{\mathrm{IND}}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''})}(l_{\mathrm{key}}) $$

and thus:

$$ \left| \mathbb{P}(G_8^1 \Rightarrow 1) - \mathbb{P}(G_9^1 \Rightarrow 1) \right| \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^{l_{\mathrm{hash}}}} + \mathrm{Adv}^{\mathrm{IND}}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''})}(l_{\mathrm{key}}). $$

† **Game $G_{10}^1$**: This game is the same as the previous one and works in the same vein as game $G_8^0$ of the Responder identity protection property proof, i.e., 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_3^1$ the event: $\mathcal{A}$ queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{xy}$. If the event $F_3^1$ occurs, then challenger stops the simulation by returning a random bit. By the identical-until-bad lemma, we thus have:

$$ \left| \mathbb{P}(G_9^1 \Rightarrow 1) - \mathbb{P}(G_{10}^1 \Rightarrow 1) \right| \le \mathbb{P}(F_3^1). $$

To provide a bound for $\mathbb{P}(F_3^1)$ we construct, by reduction, an adversary $B_3^1$ against the GDH problem, as we did for game $G_8^0$ in the Responder identity protection property proof. We hence claim that:

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

and finally:

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

† **Game $G_{11}^1$**: This game is the same as the previous one, except that in this game we simulate the key generation of PRK$_{2e}$ for our Initiator in the running session. Namely we simulate the generation of the key PRK$_{2e}$ thanks to a private oracle, denoted $SO_{\mathrm{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}$).

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_{\mathrm{hash}}}$, hopping for PRK$_{2e*}$ = PRK$_{2e}$. Similarly we denote $F_4^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_4^1$ happens, we stop the simulation and return a random bit. In a similar way as in game $G_9^0$ of the Responder identity protection property proof, we provide an upper bound for $\mathbb{P}(F_4^1)$ with:

$$ \mathbb{P}(F_4^1) \le \frac{q_{\mathrm{RO}_P^{l_2}}}{2^{l_{\mathrm{hash}}}}. $$

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

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

† **Game $G_8^3$**: This game follows $G_7^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_2^3$:

$$ \left| \mathbb{P}(G_{7'}^3 \Rightarrow 1) - \mathbb{P}(G_8^3 \Rightarrow 1) \right| \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^1$ (with the appropriate notations), defining the event $F_2^3$. Again we bound $\mathbb{P}(F_2^3)$ and thanks to the identical-until-bad lemma we obtain the same result:

$$ \left| \mathbb{P}(G_9^3 \Rightarrow 1) - \mathbb{P}(G_9^3 \Rightarrow 1) \right| \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}}} + \text{Adv}^{\text{IND}}_{(\text{KGen''}, \text{Enc''}, \text{Dec''})}(l_{\text{key}})}{2^{l'\text{hash}}} $$

† **Game $G_{10}^3$**: This game is the same as the previous one and works in the same way as game $G_8^2$ of the Responder identity protection property proof: 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_3^3$ the event: $\mathcal{A}$ queries $SO_T$ on the correct DIFFIE-HELLMAN value $g^{iy}$. If the event $F_3^3$ occurs, then challenger stops the simulation by returning a random bit. By the identical-until-bad lemma, we thus have:

$$ \left| \mathbb{P}(G_9^3 \Rightarrow 1) - \mathbb{P}(G_{10}^3 \Rightarrow 1) \right| \le \mathbb{P}(F_3^3). $$

As in game $G_8^2$ (of the Responder identity protection property proof) we construct, by reduction, an adversary $B_3^3$ against the GDH problem and we bound $\mathbb{P}(F_3^3)$ by:

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

and finally:

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

† **Game $G_{11}^3$**: This game is the same as the previous one, except that here the challenger generates the key PRK$_{4e3m}$ for the Initiator 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^2$ of the Responder identity protection property proof:

$$ \left| \mathbb{P}(G_{10}^3 \Rightarrow 1) - \mathbb{P}(G_{11}^3 \Rightarrow 1) \right| \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}}} + \text{Adv}^{\text{IND}}_{(\text{KGen''}, \text{Enc''}, \text{Dec''})}(l_{\text{key}})}{2^{l'\text{hash}}} $$

† **Game $G_{11}^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_4^3$, to:

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

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

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

We can now conclude the two remaining branches. We explicit games $G_{12}$ and $G_{13}$ instead of games $G_{12}^{1,3}$ and $G_{13}^{1,3}$ because, in the two cases, the two games are very similar.

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

$$ \left| \mathbb{P}(\mathbb{G}_{11} \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{12} \Rightarrow 1) \right| \le \frac{1}{2^{l_{hash}}} + \mathrm{Adv}^{\mathrm{IND}}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''}), \mathcal{A}}(l_{\mathrm{key}}). $$

† **Game $\mathbb{G}_{13}$:** This game is the same as the previous one, except that we replace the choice of $\mathrm{ID\_CRED\_I}$ with $\mathrm{ID\_CRED\_I}_b$ by $\mathrm{ID\_CRED\_I}$ with $\mathrm{ID\_CRED\_I}_1 - b$. As in the previous proof, we here simulate the experiment $\mathbb{E}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{Id-Initiator-0}}(\lambda)$ for $\mathcal{A}$ (and as before we remain in the context where PRK$_{3e2m}$, PRK$_{4e3m}$ and $sk_3$ are simulated thanks to private oracles).

In this situation, the adversary will receive a different ciphertext $c_3$ (and different $M_1$, but as we explain earlier this does not help him to distinguish since $M_1$ is not linked to the initiator identity). Then $\mathcal{A}$ detects this modification, but this will not help him to distinguish. Indeed here he knows that the two messages didn't come from the same initiator and he wants to succeed in distinguishing them. But since the key $sk_3$ is random at this point, $\mathcal{A}$ is forced to win the experiment $\mathbb{E}_{\mathrm{AEAD}, \mathcal{A}}^{\mathrm{IND-CPA}}(l_{\mathrm{key}})$, which we previously assumed to be very difficult, if he wants to win the game (that is why we didn't simulate (randomly) the initiator vector $IV_3$). He will also receive a different ciphertext $S_I$, but again since the key $sk_3$ is random he is forced to win the experiment $\mathbb{E}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''}), \mathcal{A}}^{\mathrm{IND}}(l_{\mathrm{key}})$ which again was assumed to be very difficult to win. So finally we bound the winning advantage of the adversary with this game hop as follows:

$$ \left| \mathbb{P}(\mathbb{G}_{12} \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{13} \Rightarrow 1) \right| \le \mathrm{Adv}^{\mathrm{IND-CPA}}_{\mathrm{AEAD}, \mathcal{A}}(l_{\mathrm{key}}) + \mathrm{Adv}^{\mathrm{IND}}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''})}(l_{\mathrm{key}}). $$

So finally, to summarize, we have:

$$
\begin{aligned}
\mathrm{Adv}^{\mathrm{Id-Pro-Init}}_{\mathrm{LI-EDHOC}, \mathcal{A}}(\lambda) &= \left| \mathbb{P}\left(\mathbb{E}^{\mathrm{Id-Initiator-1}}_{\mathrm{LI-EDHOC}, \mathcal{A}}(\lambda) \Rightarrow 1\right) - \mathbb{P}\left(\mathbb{E}^{\mathrm{Id-Initiator-0}}_{\mathrm{LI-EDHOC}, \mathcal{A}}(\lambda) \Rightarrow 1\right) \right| \\
&= \left| \mathbb{P}(\mathbb{G}_0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{13} \Rightarrow 1) \right| \\
&\le \left| \mathbb{P}(\mathbb{G}_0 \Rightarrow 1) - \mathbb{P}(\mathbb{G}_1 \Rightarrow 1) \right| + \cdots + \left| \mathbb{P}(\mathbb{G}_{12} \Rightarrow 1) - \mathbb{P}(\mathbb{G}_{13} \Rightarrow 1) \right| \\
&\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}} + N \cdot \left[ 3\mathrm{Adv}^{\mathrm{DDH}}_{\mathbb{G}}(\lambda) \right. \\
&\qquad \left. + 5q_{RO_T} \cdot \mathrm{Adv}^{\mathrm{GDH}}_{\mathbb{G}}(\lambda) + 3 \cdot \frac{q_{RO_P^{l_{hash}} + q_{RO_P^{l_{key}} + q_{RO_P^{l_{iv}} + q_{RO_P^{l_{mac}}}}}{2^{l_{hash}}} + \frac{q_{RO_P^{l_2}} + 1}{2^{l_{hash}-1}} \right. \\
&\qquad \left. + 2\mathrm{Adv}^{\mathrm{IND-CPA}}_{\mathrm{AEAD}, \mathcal{A}}(l_{\mathrm{key}}) + 9\mathrm{Adv}^{\mathrm{IND}}_{(\mathrm{KGen''}, \mathrm{Enc''}, \mathrm{Dec''}), \mathcal{A}}(l_{\mathrm{key}}) \right]
\end{aligned}
$$

and this concludes the proof. ■
# 8 Conclusion

Mobile environments come with a compulsory Lawful Interception (LI) clause for mobile network operators (MNOs). Naïve LI, however, is intrusive, essentially forcing the operator to eavesdrop on all communications.

Our work provides *fine-grained, session-specific* LI for the complex EDHOC protocol, which is being standardized for mobile use in the LAKE IETF working group. Our LI-EDHOC scheme provably guarantees AKE security, non-frameability, and a proof of LI key-recovery for EDHOC’s 4 authentication methods, while preserving identity-protection and explicit authentication. Evaluations on two different ARM Cortex-M platforms, show that our protocol remains efficient in constrained environments, especially when the signatures of knowledge benefit from hardware acceleration. Even better performances are likely to be obtained for signature-based authentication methods, or if the processor were optimized for ECC computations.

# 9 Acknowledgments

This work has been partially supported by the French National Research Agency under the France 2030 label (NF-HiSec ANR-22-PEFT-0009) and through the PRIvacy-preserving tools for VAlidation and Security of Queries (PRIVASIQ) project (ANR-23-CE39-0008). The views reflected herein do not necessarily reflect the opinion of the French government.
References

[1] 3GPP. Lawful interception architecture and functions. https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=3182, 2018.

[2] 3GPP. Lawful interception requirements. https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=3181, 2018.

[3] 3GPP. Protocols and procedures for lawful interception. https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=3183, 2019.

[4] Harold Abelson, Ross Anderson, Steven M. Bellovin, Josh Benaloh, Matt Blaze, Whitfield Diffie, John Gilmore, Matthew Green, Susan Landau, Peter G. Neumann, Ronald L. Rivest, Jeffrey I. Schiller, Bruce Schneier, Michael A. Specter, and Daniel J. Weitzner. Keys under doormats. *Comms. of the ACM*, 58(10):24–26, 2015.

[5] Ghada Arfaoui, Olivier Blazy, Xavier Bultel, Pierre-Alain Fouque, Thibaut Jacques, Adina Nedelcu, and Cristina Onete. How to (legally) keep secrets from mobile operators. In *Proceedings of ESORICS*, pages 23–43, 2021.

[6] Mihir Bellare and Ronald L. Rivest. Translucent cryptography—an alternative to key escrow, and its implementation via fractional oblivious transfer. *Journal of Cryptology*, 12(2):117–139, 1999.

[7] Mihir Bellare and Phillip Rogaway. Code-based game-playing proofs and the security of triple encryption. Cryptology ePrint Archive, Paper 2004/331, 2004.

[8] Felipe Boeira, Mikael Asplund, and Marinho Barcellos. Provable non-frameability for 5g lawful interception. In *Proceedings of the 16th ACM Conference on Security and Privacy in Wireless and Mobile Networks*, WiSec '23, page 109–120. Association for Computing Machinery, 2023.

[9] Xavier Bultel and Cristina Onete. Pairing-free secure-channel establishment in mobile networks with fine-grained lawful interception. In *Proceedings of ACM SAC*, page 968–970, 2022.

[10] Jan Camenisch and Markus Stadler. Efficient group signature schemes for large groups. In *Advances in Cryptology — CRYPTO '97*, 1997.

[11] Jan Camenisch and Markus Stadler. Proof systems for general statements about discrete logarithms. Technical Report/ETH Zurich, Department of Computer Science, 260, 1997.

[12] Global Encryption Coalition. Joint statement on the dangers of the may 2024 council of the EU compromise proposal on EU CSAM. https://www.globalencryption.org/2024/05/joint-statement-on-the-dangers-of-the-may-2024-council-of-the-eu-compromise-proposal-on-eu-csam/, 2024.

[13] Baptiste Cottier and David Pointcheval. Security analysis of the edhoc protocol, 2022.

[14] Baptiste Cottier and David Pointcheval. Security analysis of improved edhoc protocol. In Guy-Vincent Jourdan, Laurent Mounier, Carlisle Adams, Florence Sèdes, and Joaquin Garcia-Alfaro, editors, *Foundations and Practice of Security*, pages 3–18, Cham, 2023. Springer Nature Switzerland.

[15] EU Council. Resolution on security through encryption and security despite encryption. https://data.consilium.europa.eu/doc/document/ST-13084-2020-REV-1/en/pdf, 2020.

[16] FairTrials. Short update: Police in Germany defend the use of contact tracing for criminal investigations. https://www.fairtrials.org/news/short-update-police-germany-defend-use-contact-tracing-criminal-investigations, 2020.
[17] Lorenzo Franceschi-Bicchierai. The 10 biggest revelations from edward snowden's leaks. https://mashable.com/2014/06/05/edward-snowden-revelations/?europe=true, 2014.

[18] Felix Günther and Marc Ilunga Tshibumbu Mukendi. Careful with mac-then-sign: A computational analysis of the edhoc lightweight authenticated key exchange protocol. In *2023 IEEE 8th European Symposium on Security and Privacy (EuroS&P)*, pages 773–796, 2023.

[19] Xu He, Lixiang Li, and Haipeng Peng. A key escrow-free kp-abe scheme and its application in standalone authentication in iot. *IEEE Internet of Things Journal*, 11(7):11381–11394, 2024.

[20] Xianghong Hu, Xueming Li, Xin Zheng, Yuan Liu, and Xiaoming Xiong. A high speed processor for elliptic curve cryptography over nist prime field. *IET Circuits, Devices & Systems*, 16:350–359, 02 2022.

[21] Meijuan Huang, Yutian Liu, Bo Yang, Yanqi Zhao, and Mingrui Zhang. Efficient revocable attribute-based encryption with data integrity and key escrow-free. *Information*, 15:32, 01 2024.

[22] Ingrid Huso, Marco Olivieri, Leonardo Galgano, Adnan Rashid, Giuseppe Piro, and Gennaro Boggia. Design and implementation of a looking-forward lawful interception architecture for future mobile communication systems. *Comput. Networks*, 249:110518, 2024.

[23] Charlie Jacomme, Elise Klein, Steve Kremer, and Maïwenn Racouchot. A comprehensive, formal and automated analysis of the EDHOC protocol. In *32nd USENIX Security Symposium (USENIX Security 23)*, pages 5881–5898, Anaheim, CA, August 2023. USENIX Association.

[24] Jake Januzelli and Jiayu Xu. A complete characterization of one-more assumptions in the algebraic group model. Cryptology ePrint Archive, Paper 2024/1954, 2024.

[25] Hugo Krawczyk. SIGMA: The 'SIGn-and-MAc' Approach to Authenticated Diffie-Hellman and Its Use in the IKE Protocols. In *Advances in Cryptology - CRYPTO 2003*, volume 2729 of LNCS, pages 400–425, 2003.

[26] Hugo Krawczyk and Pasi Eronen. HMAC-based Extract-and-Expand Key Derivation Function (HKDF). RFC 5869, May 2010.

[27] Moxie Marlinspike and Trevor Perrin. The X3DH key agreement protocol. https://signal.org/docs/specifications/x3dh/, 2016.

[28] Elsa Lopez Perez, Thomas Watteyne, Rafael Marin-Lopez, Cristina Onete, and Mališa Vučinić. Pre-shared key authentication with edhoc: The security-performance tradeoff, 2025. awaiting for publication.

[29] Elsa López Pérez, Inria Göran Selander, John Preuß Mattsson, Thomas Watteyne, and Mališa Vučinić. Edhoc is a new security handshake standard: An overview of security analysis, 2024.

[30] 379 scientists and researchers from 36 countries. Open letter on the position of scientists and researchers on the updated version of the EU's proposed Child Sexual Abuse Regulation. https://homes.esat.kuleuven.be/~preneel/Open_letter_CSAR_aug24_still_unacceptable.pdf, 2024.

[31] G. Selander, J. Preuss Mattsson, and F. Palombini. Ephemeral Diffie-Hellman over COSE (EDHOC). RFC 9528, 2024.

[32] Göran Selander, John Preuß Mattsson, and Francesca Palombini. Ephemeral Diffie-Hellman Over COSE (EDHOC). RFC 9528, March 2024.

[33] Victor Shoup. Sequences of games: a tool for taming complexity in security proofs. Cryptology ePrint Archive, Paper 2004/332, 2004.
[34] UN. Universal Declaration of Human Rights. https://www.un.org/en/universal-declaration-human-rights/, 1948.

[35] UN. Special rapporteur on privacy. https://www.ohchr.org/en/special-procedures/, 2021.

[36] Giuseppe Ungaro, Francesco Ricchitelli, Ingrid Huso, Giuseppe Piro, and Gennaro Boggia. Design and implementation of a lawful interception architecture for b5g systems based on key escrow. In *2022 IEEE Conference on Standards for Communications and Networking (CSCN)*, pages 207-207, 2022.

[37] Charles Wright and Mayank Varia. Crypto crumple zones: Enabling limited access without mass surveillance. In *2018 IEEE European Symposium on Security and Privacy (EuroS&P)*, pages 288-306, 2018.