# Fine-grained, privacy-augmenting LI-compliance in the LAKE standard - Extended version

Pascal Lafourcade, Elsa Lopez Perez, Charles Olivier-Anclin, Cristina Onete, Clément Papon, Mališa Vučinić

► To cite this version:

Pascal Lafourcade, Elsa Lopez Perez, Charles Olivier-Anclin, Cristina Onete, Clément Papon, et al. Fine-grained, privacy-augmenting LI-compliance in the LAKE standard - Extended version. ESORICS 2025 - 30th European Symposium on Research in Computer Security, Sep 2025, Toulouse, France. hal-05126079

HAL Id: hal-05126079

https://hal.science/hal-05126079v1

Submitted on 29 Sep 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Fine-grained, privacy-augmenting
LI-compliance in the LAKE standard

Pascal Lafourcade*, Elsa López Pérez*, Charles Olivier-Anclin*,
Cristina Onete†, Clément Papon†, and Mališa Vučinić*

* LIMOS, Université Clermont Auvergne, France

* Inria, France

† XLIM, Université de Limoges, France

Abstract

The Internet Engineering Task Force and its LAKE working group standardized the Ephemeral Diffie-Hellman over COSE (EDHOC) authenticated key-exchange protocol for use in constrained Internet of Things deployments. The use cases include cellular networks, such as NB-IoT, but also non-cellular networks such as 6TiSCH, and LoRaWAN. As a result of its use in cellular networks, EDHOC will be subject to Lawful Interception (LI), which allows a group of authorities to break, if equipped with a warrant, the end-to-end (E2E) security of the channel established through EDHOC. Current implementations of EDHOC would only allow lawful interception by using the cellular network operator as a legitimate endpoint, essentially running a Person-in-the-Middle attack against the protocol. In this work, we focus on a privacy-preserving, fine-grained LI-compliant modification of EDHOC for all four authentication methods that this protocol currently supports. We achieve this via a careful white-box composition of EDHOC with the Lawful Interception Key-Exchange approach of Arfaoui et al. (ESORICS 2021) and Bultel and Onete (SAC 2022). Our resulting construction not only achieves strong key-security, but also non-frameability, and LI-compliance, without breaking the identity-protection property of EDHOC. Our implementation results show that, while LIKE adds an overhead to a standard EDHOC implementation in Rust, the resulting protocol remains practical while achieving much better privacy and LI-compliance.

<footnote>This is an extended version of the article published as:</footnote>

<footnote>P. Lafourcade, E. López Pérez, C. Olivier-Anclin, C. Onete, C. Papon, M. Vučinić, “Fine-grained, privacy-augmenting LI-compliance in the LAKE standard”, in Proceedings of the 30th European Symposium on Research in Computer Security (ESORICS) 2025, Springer Nature, 2026.</footnote>

<footnote>https://doi.org/10.1007/978-3-032-07901-5_13</footnote>

<footnote>This extended version includes additional results, detailed proofs, and new discussions not present in the
original publication.</footnote>
# Table of contents

<table><tr><td>1</td><td>Introduction</td><td>5</td></tr><tr><td>1.1</td><td>LAKE</td><td>5</td></tr><tr><td>1.2</td><td>Our contribution</td><td>6</td></tr><tr><td>1.3</td><td>Related work</td><td>6</td></tr><tr><td>2</td><td>The EDHOC protocol</td><td>7</td></tr><tr><td>2.1</td><td>Protocol outline</td><td>7</td></tr><tr><td>3</td><td>Background</td><td>10</td></tr><tr><td>3.1</td><td>Notations</td><td>10</td></tr><tr><td>3.2</td><td>Cryptographic background</td><td>10</td></tr><tr><td>3.2.1</td><td>Classical group assumptions</td><td>10</td></tr><tr><td>3.2.2</td><td>The Oracle-DLog problem</td><td>11</td></tr><tr><td>3.2.3</td><td>Signature scheme</td><td>12</td></tr><tr><td>3.2.4</td><td>Zero-knowledge tools</td><td>13</td></tr><tr><td>3.2.5</td><td>Encryption scheme</td><td>14</td></tr><tr><td>3.2.6</td><td>Hash function</td><td>17</td></tr><tr><td>3.3</td><td>The identical-until-bad lemma</td><td>17</td></tr><tr><td>3.4</td><td>The LIKE framework</td><td>18</td></tr><tr><td>4</td><td>LI-compliant EDHOC</td><td>19</td></tr><tr><td>4.1</td><td>Setup and Key generation</td><td>20</td></tr><tr><td>4.2</td><td>Precomputation stage</td><td>21</td></tr><tr><td>4.3</td><td>Handshake - First case</td><td>22</td></tr><tr><td>4.4</td><td>Handshake - Second case</td><td>28</td></tr><tr><td>4.5</td><td>Handshake - Third case</td><td>32</td></tr><tr><td>4.6</td><td>Handshake - Fourth case</td><td>35</td></tr><tr><td>5</td><td>Implementation and evaluation</td><td>39</td></tr><tr><td>5.1</td><td>Implementation setup</td><td>39</td></tr><tr><td>5.2</td><td>Implementation results</td><td>40</td></tr><tr><td>6</td><td>Security Model</td><td>42</td></tr><tr><td>6.1</td><td>Execution environment</td><td>42</td></tr><tr><td>6.2</td><td>Oracles</td><td>44</td></tr><tr><td>6.3</td><td>Security properties</td><td>46</td></tr><tr><td>6.3.1</td><td>Key-security</td><td>46</td></tr><tr><td>6.3.2</td><td>LI-compliance</td><td>46</td></tr><tr><td>6.3.3</td><td>Non-frameability</td><td>49</td></tr><tr><td>6.3.4</td><td>Identity protection</td><td>49</td></tr><tr><td>7</td><td>Security results</td><td>52</td></tr><tr><td>7.1</td><td>Key security</td><td>52</td></tr><tr><td>7.2</td><td>LI-compliance</td><td>81</td></tr><tr><td>7.3</td><td>Non-frameability</td><td>96</td></tr><tr><td>7.4</td><td>Identity protection</td><td>101</td></tr><tr><td>7.4.1</td><td>Responder identity protection</td><td>101</td></tr><tr><td>7.4.2</td><td>Initiator identity protection</td><td>112</td></tr><tr><td>8</td><td>Conclusion</td><td>121</td></tr></table>
9 Acknowledgments 121

References 122
# 1 Introduction

Privacy is a human right. The Universal Declaration for Human Rights [34], states: "No one shall be subjected to arbitrary interference with his privacy [...] or correspondence [...]. Everyone has the right to the protection of the law against such [...] attacks." The United Nations describes privacy as a cornerstone of other basic human rights, like "the free development and expression of an individual's personality, identity, and beliefs, and their ability to participate in political, economic, social and cultural life" [35].

Edward Snowden's 2013 revelations of widespread mass surveillance engendered public outcry. Advocates for sacrificing privacy for the sake of (inter-)national security clashed with privacy supporters warning of censorship and autocracy. Examples of illegal mass-surveillance abound today. The NSA once collected call data from all Verizon customers, and data pertaining to calls in the Bahamas and Afghanistan [17]. During the COVID-19 pandemic, contact-tracing data was used in order to facilitate criminal investigations [16]. A recently-proposed EU regulation on moderating child sexual abuse material (CSAM) in encrypted communications enables mass client-side scanning, in spite of outspread criticism from both scientists [30] and socio-economical entities [12].

Mass-surveillance is a threat to basic human rights. Yet, even strong privacy advocates agree that investigations limited in scope and motivation (by lawfully-obtained warrants) can be legitimate [4]. This is the type of limited Lawful Interception (LI) that the EU resolution on security through encryption and security despite encryption supports [15].

Lawful Interception (LI) has been a legal and technical requirement for over 30 years in mobile communications, featuring prominently in 3GPP specifications [2, 1, 3]. Every operator that provides end-to-end encrypted user communication is subject to such requirements.

## 1.1 LAKE

The Lightweight Authenticated Key Exchange (LAKE) working group of the Internet Engineering Task Force (IETF) standardized a lightweight secure-channel establishment for use in NB-IoT, 6TiSCH, and LoRaWAN. Since it will be used in mobile environments, LAKE must comply with LI.

The solution proposed by LAKE is EDHOC [31]: a mutually-authenticated lightweight secure-channel establishment scheme, guaranteeing identity-protection as a form of privacy. The initiator and responder may choose to authenticate either through signatures or by using static DH-keys. As described in section 2, the protocol completes in 1.5, optionally 2, round trips. Starting from the 2nd message, communications may be authenticated and/or encrypted using intermediate secrets.

EDHOC is not LI-compliant by design. Naïvely, this can be achieved by turning mobile infrastructure nodes into endpoints – as is the case for other protocols, like AKA; this comes, however, at the cost of an unnecessary loss of privacy, making mobile network operators complicit to mass surveillance.

In this paper, we aim to render the EDHOC protocol LI-compliant without this massive loss of privacy. Ideally, our LI-EDHOC scheme must guarantee the security of exchanged messages except with respect to their sender, the receiver, and the collaborative efforts of all the Lawful Interception authorities<fnref n="1" /> permitted to intercept. Moreover, interception should be fine-grained, limited only to one session at a time.

We use the pairing-free Lawful-Interception Key-Exchange (LIKE) approach [9] described in section 3. Applying LIKE to a real-world protocol such as EDHOC, which features four methods of authentication and complex key schedules, while also preserving EDHOC's lightweight character and identity-protection, is far from trivial. An important challenge, for instance, stems from the fact that EDHOC features two types of authentication, which can be combined arbitrarily. While signature-based authentication is compatible with

<footnote n="1">¹LI is performed differently from one country to another. For instance in France, Lawful Interception requires the technical cooperation of the operator, the legislative branch, and law-enforcement. We model each participant that requires a cryptographic key as an authority – which allows us to construct our protocol in an elegant manner. In other countries, potentially more authorities might be required. Our system is flexible and can address all such scenarios. Our protocol is designed to allow parties to be aware of potential LI (as we believe transparency should be reinforced) – but this could be technically adjusted to allow proxies to indicate, in a prior message, the authorities that must be used for each exchange.</footnote>
past LIKE approaches, it is not clear that MAC-based authentication will provide provable non-framewability.
Another important challenge is combining LIKE with the complex key-schedule of the EDHOC protocol.

## 1.2 Our contribution

We describe LI-compliant extensions for EDHOC's four authentication methods, and guarantee:

- **KEY-SECRECY:** session traffic keys are indistinguishable from random except for that session's initiator, responder, and the collusion of all the authorities allowed to perform LI for that session.

- **NON-FRAMEABILITY:** it is impossible to falsely accuse a user of taking part in a session that it did not run.

- **LI COMPLIANCE:** the mobile infrastructure nodes (proxies) forwarding the communication can prove keys computed in accepting sessions are lawfully-interceptable by the correct set of LI authorities.

- **IDENTITY-PROTECTION:** an attacker (active for Initiator and passive for Responder) cannot learn the identities of the two endpoints.

Each property provably holds in the LIKE models of [5, 9], and a (modified) identity-protection model of [14]. Moreover, we provide an open-source implementation of our scheme in Rust optimized for constrained devices. We demonstrate the feasibility of our scheme by evaluating it on two hardware platforms that are typical examples of hardware used in the LAKE use cases.

## 1.3 Related work

Lawful Interception initially relied on Key-Escrow: the idea of entrusting communication to a managing trusted third party (TTP), which could learn the session key. Unfortunately, Key-Escrow often requires the online presence of authorities and can easily be pushed to mass surveillance. In spite of new LI techniques [6], current LI still relies on Key Escrow [36, 22].

Our work comes closest to a different approach [5] called LIKE, which aimed to achieve fine-grained LI-compliant Authenticated Key-Exchange (AKE) with better privacy. A first pairing-based instantiation [5] was rendered more efficient, pairing-free, and usable in roaming scenarios by Bultel and Onete [9]. One property provided by LIKE is non-frameability, which is also underlined by recent related work [8] in the context of 5G (and beyond) network architectures.

Some techniques for connection-monitoring and data-encryption [19, 21] could be extended to the LI scenario, though this is not their original goal. As they rely on pairings, they are incompatible with lightweight AKE, however. Finally, a worthwhile privacy-preserving alternative for LI is provided by CRUMPLE [37], which provides LI through a proof of work. This interesting approach is, unfortunately, not sufficiently efficient to comply with current LI requirements (which demand that interception yield “timely” results).

Finally note that throughout the standardization process of EDHOC [31], the protocol was analysed in various versions. A formal analysis using SAPIC+ identified weaknesses and proposed modifications in EDHOC version 12 [23]; later, the authors verified draft 14, showing that many previously identified issues had been addressed.

Cottier and Pointcheval then provided an analysis of EDHOC draft 15 [14, 13] and suggested further improvements. In 2023, Günther and Mukendi [18] analyzed draft 17 and proposed changes to the key schedule and to the construction of transcript hashes.
## 2 The EDHOC protocol

In response to a need for lightweight secure-channel establishment in the context of the Internet of Things (IoT), the Internet Engineering Task Force (IETF) is currently standardizing Lightweight Authenticated Key Exchange (LAKE), centered around the Ephemeral Diffie-Hellman Over COSE (EDHOC) protocol. EDHOC is a two-party mutually-authenticated DIFFIE-HELLMAN-based AKE scheme relying on Krawczyk's SIGMA-I protocol [25]. It features three mandatory messages and an optional fourth. The handshake is run in sessions between an Initiator I and a Responder R, which can choose how they want to authenticate: either by using signature schemes, or by using a certified static DIFFIE-HELLMAN (DH) key. The four combinations of authentication mechanisms are called methods 0, 1, 2, and 3, as described in TABLE 1. We denote by $(ssk_P, spk_P)$ the private/public signature keys of party P, and by $(p, g^p)$ party P's long-term static DH private/public keys. The parties indicate their preferred means of authentication method in message_1.

<table><caption>TABLE 1 – Current authentication methods registered by IANA (0-1-2-3).</caption><thead><tr><th>ID</th><th>Initiator</th><th>Credential I</th><th>Responder</th><th>Credential R</th></tr></thead><tbody><tr><td>0</td><td>Signature</td><td>(ssk<sub>I</sub>, spk<sub>I</sub>)</td><td>Signature</td><td>(ssk<sub>R</sub>, spk<sub>R</sub>)</td></tr><tr><td>1</td><td>Signature</td><td>(ssk<sub>I</sub>, spk<sub>I</sub>)</td><td>Static DIFFIE-HELLMAN</td><td>(r, g<sup>r</sup>)</td></tr><tr><td>2</td><td>Static DIFFIE-HELLMAN</td><td>(i, g<sup>i</sup>)</td><td>Signature</td><td>(ssk<sub>R</sub>, spk<sub>R</sub>)</td></tr><tr><td>3</td><td>Static DIFFIE-HELLMAN</td><td>(i, g<sup>i</sup>)</td><td>Static DIFFIE-HELLMAN</td><td>(r, g<sup>r</sup>)</td></tr></tbody></table>

In addition to these two authentication methods, the Working Group is currently working on the standardization of Pre-Shared Key (PSK) authentication for EDHOC, where the PSK can be either distributed using an out-of-band channel (fresh sessions), or it can be derived from previous handshakes using any of the already supported methods (0-1-2-3) (resumption session).

### 2.1 Protocol outline

FIGURE 1 depicts the EDHOC message flow. The first message, always sent unencrypted, consists of parameters METHOD and SUITES_I, indicating the authentication method and desired cipher suite, a connection identifier $C_I$ which acts as a session identifier for peers running multiple sessions, some additional information called external authorization data $EAD_1$, and a fresh ephemeral public key $g^x$ (we denote the corresponding private key as $x$).

If the Responder supports the method and cipher suite, it computes message_2, which consists of an ephemeral DH element $g^y$ sent in clear (the private key is denoted as $y$) and a ciphertext, encrypted with a key denoted as $sk_2$, derived from $g^x$ and $g^y$. The plaintext consists of: a connection identifier $C_R$, an identifier indicating the Responder's long-term authentication credential, some additional data $EAD_2$, and an authentication by the Responder, consisting of either a signature (methods 1 and 3) or a MAC (methods 0 and 2). The signature is computed with the Responder's private key $ssk_R$ over the credential identifier ID_CRED_R, a transcript hash $TH_2$ detailed in FIGURE 2, the public key $spk_R$, and $EAD_2$. If the Responder uses static-DH authentication, then the MAC key is derived from both the ephemeral DH product of $g^x$ and $g^y$ and from the semi-static DH product of $g^x$ and the static element $g^r$. The Initiator decrypts the ciphertext in message_2 with the key $sk_2$, derived from $g^x$ and $g^y$ (the latter is sent in clear). Then, it recovers and verifies the Responder's authentication, according to the authentication method. message_3 is somewhat similar to message_2, except that it is AEAD-encrypted using a key derived either solely from the ephemeral DH values $g^x$ and $g^y$ (methods 0 and 2) or from both the ephemeral DH product of $g^x$ and $g^y$, and the semi-static DH product of $g^x$ and $g^r$ (methods 1 and 3).

The optional message_4 provides explicit key-confirmation and is an AEAD-encryption on additional data $EAD_4$. The encryption key is derived from the previously computed ephemeral (and potentially semi-static)
<figure><img src="image_2.png" /><figcaption>FIGURE 1 – The EDHOC message flow [28].</figcaption></figure>

DH products, and additionally, for methods 2 or 3, a new semi-static DH product between the ephemeral value $g^y$ and the Initiator's static DH element $g^i$.

The full key-schedule of the protocol is depicted in FIGURE 2. EDHOC uses two functions, **EDHOC_Expand** and **EDHOC_Extract**, with the EDHOC hash algorithm in the selected cipher suite to derive keys used in message processing. **EDHOC_Extract** is used to derive fixed-length uniformly pseudorandom keys (PRKs) from Elliptic Curve DIFFIE-HELLMAN (ECDH) shared secrets.

**EDHOC_Expand** is used to define a key derivation function, **EDHOC_KDF**, for generating MACs and for deriving output keying material (OKM) from PRKs.

There are three main secret values that are computed, labelled, respectively PRK$_{2e}$, PRK$_{3e2m}$ and PRK$_{4e3m}$. The notations indicate the purposes of these secrets: the 2e subscript indicates the key is used to encrypt **message_2** content. The 3e2m subscript indicates the value is used to encrypt **message_3** and (depending on the authentication method) compute the MAC in **message_2**. Note that in case of signature-only authentication (method 0), the entire key-schedule is derived from the ephemeral DH values $g^x$ and $g^y$. If both parties use static DH authentication, the key schedule resembles X3DH [27], using the ephemeral DH product and two semi-static ones.
<figure><img src="image_3.png" /><figcaption>FIGURE 2 – EDHOC’s key scheduling. The figure shows how keys are derived for all four authentication methods [29].</figcaption></figure>
# 3 Background

We present here all the notations and the necessary cryptographic background to build our protocol in a solid and elegant manner, as well as to provide detailed and rigorous proofs.

## 3.1 Notations

With this short paragraph, we summarize the general notations we will use. These are mostly standard notations.

Throughout this paper, $\lambda \in \mathbb{N}^*$ is a security parameter, and we write $x \leftarrow y$ to denote that variable $x$ is assigned value $y$. By $x \leftarrow \mathbb{X}$ we express the fact that $x$ is sampled uniformly at random from the set $\mathbb{X}$. The notation $y \leftarrow \text{Alg}(x)$ signifies that algorithm $\text{Alg}$ outputs $y$ on input $x$.

When we talk about the EDHOC protocol, we will use the notations of the standardization [32], and during our modification, for the writing of the LI-EDHOC protocol, those that we will add will try to be in the continuity of the style. We also use some of [14] in order to lighten certain algorithmic notations.

Since we mix the EDHOC protocol with the LIKE protocol, we also use notations from [5, 9]. To refer to a general party, we use the letter $P$, but when we need to be more specific we use: $E$ to denote an endpoint, $\text{Prox}$ to denote a proxy and $\Lambda$ to denote an authority. Some parties have attributes and to refer to them we use $P.\{\text{the attribute}\}$. Finally if $F$ is an event, we denote by $\mathbb{P}(F)$ the probability that the event $F$ occurs.

## 3.2 Cryptographic background

### 3.2.1 Classical group assumptions

While EDHOC is a generic protocol which can be instantiated with different primitives, currently its main use relies on elliptic-curve cryptography (ECC) [29]. Moreover, as it will be illustrated several times in this paper, we use DIFFIE-HELLMAN elements, from a well chosen group $\mathbb{G}$. We thus exploit the cryptographic power of groups. For that we formalize the cryptographic assumptions needed for our security analysis. To begin with we want that in our group the DDH problem is hard to solve, the CDH assumption holds and the GDH problem is hard to solve. In what follows, $\mathbb{G}$ denotes a cyclic group of prime order $p$ and $g$ denotes a generator of $\mathbb{G}$.

**Definition 1 (Discret Logarithm problem)** The DL-advantage of a p.p.t adversary $\mathcal{A}$ in a group $\mathbb{G}$ is defined with the experiment depicted in FIGURE 3 by:

$$ \text{Adv}_{\mathbb{G},\mathcal{A}}^{\text{DL}}(\lambda) = \mathbb{P}[\mathbb{E}_{\mathbb{G},\mathcal{A}}^{\text{DL}}(\lambda) \implies 1] $$

By $\text{Adv}_{\mathbb{G}}^{\text{DL}}(\lambda)$ we thus denote the maximum advantage over all the p.p.t. adversary $\mathcal{A}$. The DL problem for the group $\mathbb{G}$ is said to be hard if $\text{Adv}_{\mathbb{G}}^{\text{DL}}(\lambda)$ is negligible in $\lambda$.

**Definition 2 (Decisional DIFFIE-HELLMAN problem)** The DDH-advantage of p.p.t. adversary $\mathcal{A}$ in a group $\mathbb{G}$ is defined thanks to the experiment depicted in FIGURE 3 by:

$$ \text{Adv}_{\mathbb{G},\mathcal{A}}^{\text{DDH}}(\lambda) = \left| \mathbb{P}[\mathbb{E}_{\mathbb{G},\mathcal{A}}^{\text{DDH},1}(\lambda) \implies 1] - \mathbb{P}[\mathbb{E}_{\mathbb{G},\mathcal{A}}^{\text{DDH},0}(\lambda) \implies 1] \right|. $$

We then denote the maximum advantage over all the p.p.t. adversary $\mathcal{A}$ by $\text{Adv}_{\mathbb{G}}^{\text{DDH}}(\lambda)$. The DDH problem for the group $\mathbb{G}$ is said to be hard if $\text{Adv}_{\mathbb{G}}^{\text{DDH}}(\lambda)$ is negligible in $\lambda$.
**Definition 3 (Computational DIFFIE-HELLMAN assumption)** *The CDH-advantage of p.p.t. adversary *A* in a group *G* is defined thanks to the experiment depicted in FIGURE 3 by:*

$$ \mathrm{Adv}_{G, \mathcal{A}}^{\mathrm{CDH}}(\lambda) = \mathbb{P}[\mathbb{E}_{G, \mathcal{A}}^{\mathrm{CDH}}(\lambda) \implies 1]. $$

We then denote the maximum advantage over all the p.p.t. adversary *A* by $\mathrm{Adv}_{\mathbb{G}}^{\mathrm{CDH}}(\lambda)$. The CDH assumption for the group *G* states that $\mathrm{Adv}_{\mathbb{G}}^{\mathrm{CDH}}(\lambda)$ is negligible in $\lambda$.

**Definition 4 (Gap DIFFIE-HELLMAN problem)** *The Gap DIFFIE-HELLMAN problem for the group *G* is defined thanks to the experiment depicted in FIGURE 3 played against a p.p.t. adversary *A*, having access to a DDH oracle $\mathcal{O}_{\mathrm{DDH}}$.*

The GDH problem is said to be hard for *G* if:

$$ \mathrm{Adv}_{\mathbb{G}, \mathcal{A}}^{\mathrm{GDH}}(\lambda) = \mathbb{P}[\mathbb{E}_{\mathbb{G}, \mathcal{A}}^{\mathrm{GDH}}(\lambda) \implies 1] $$

is negligible in $\lambda$ for all p.p.t. adversary *A*. We then denote the maximum advantage over all the p.p.t. adversary *A* by $\mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\lambda)$.

$$ \begin{array}{l} \mathbb{E}_{\mathbb{G}, \mathcal{A}}^{\mathrm{DL}}(\lambda) \\ 1: u \leftarrow \mathbb{Z}_{p-1}, U \leftarrow g^u \\ 2: u' \leftarrow \mathcal{A}(U) \\ 3: \text{if } g^{u'} = h \text{ then} \\ 4: \text{ return } 1 \\ 5: \text{else} \\ 6: \text{ return } 0 \end{array} $$

$$ \begin{array}{l} \mathbb{E}_{\mathbb{G}, \mathcal{A}}^{\mathrm{CDH}}(\lambda) \\ 1: u, v \leftarrow \mathbb{Z}_{p-1} \\ 2: (U, V) \leftarrow (g^u, g^v) \\ 3: W \leftarrow \mathcal{A}(U, V) \\ 4: \text{if } W = g^{uv} \text{ then} \end{array} $$

$$ \begin{array}{l} \mathbb{E}_{\mathbb{G}, \mathcal{A}}^{\mathrm{GDH}}(\lambda) \\ 1: u, v \leftarrow \mathbb{Z}_{p-1} \\ 2: (U, V) \leftarrow (g^u, g^v) \\ 3: W \leftarrow \mathcal{A}^{\mathcal{O}_{\mathrm{DDH}}(\cdot, \cdot)}(U, V) \\ 4: \text{if } W = g^{uv} \text{ then} \end{array} $$

$$ \begin{array}{l} \mathbb{E}_{\mathbb{G}, \mathcal{A}}^{\mathrm{DDH}, 0}(\lambda) \\ 1: u, v, w \leftarrow \mathbb{Z}_{p-1} \\ 2: (U, V, W) \leftarrow (g^u, g^v, g^w) \\ 3: b' \leftarrow \mathcal{A}(U, V, W) \\ 4: \text{ return } b' \end{array} $$

$$ \begin{array}{l} \mathbb{E}_{\mathbb{G}, \mathcal{A}}^{\mathrm{DDH}, 1}(\lambda) \\ 1: u, v \leftarrow \mathbb{Z}_{p-1} \\ 2: (U, V, W) \leftarrow (g^u, g^v, g^{uv}) \\ 3: b' \leftarrow \mathcal{A}(U, V, W) \\ 4: \text{ return } b' \end{array} $$

$$ \begin{array}{l} \mathcal{O}_{\mathrm{DDH}}(g^u, g^v, g^w) \\ 1: \text{if } g^w = g^{uv} \text{ then} \\ 2: \text{ return } 1 \\ 3: \text{else} \\ 4: \text{ return } 0 \end{array} $$

<caption>FIGURE 3 – The DL, DDH, CDH and GDH experiments</caption>

### 3.2.2 The Oracle-DLog problem

Interestingly, allowing both static-DH-based and signature-based authentication yields both a positive and a negative outcome. On the plus side, if one credential is lost or corrupted, the endpoint need not immediately re-initialize its public keys. Moreover, note that EDHOC’s static-DH authentication mode is still forward-secure, since it is combined with an ephemeral secret. On the downside, however, the use of static-DH authentication renders non-frameability difficult to prove, requiring either heavier computations, or a slight modification of the standard Discrete Logarithm problem (we will require access to a CDH oracle, akin to how GDH requires DDH oracle access). We dub this new problem *Oracle-DLog*, which is similar to the *Q-One-More Diffie-Hellman* problem defined in [24].
**Definition 5 (Oracle-DLog problem)** The Oracle-DLog problem is defined as follows. Let $x \leftarrow \mathbb{Z}_p^*$ and $X \leftarrow g^x$. The Oracle-DLog problem challenges an adversary in possession of $X$, with oracle access to $O_{\text{CDH}}^X(\cdot)$ – returning, on input $Y = g^y \in \mathbb{G}$, the value $g^{xy} \in \mathbb{G}$ – to retrieve $x$, as depicted with the experiment of FIGURE 4 below.

As for the previous group problems, we define the Oracle-DLog advantage of a p.p.t. adversary.

**Definition 6** The Oracle-DLog-advantage of p.p.t. adversary $\mathcal{A}$ in a group $\mathbb{G}$ is defined thanks to the experiment depicted in FIGURE 4 by:

$$ \text{Adv}_{\mathbb{G}, \mathcal{A}}^{\text{Oracle-DLog}}(\lambda) = \mathbb{P}[\mathbb{E}_{\mathbb{G}, \mathcal{A}}^{\text{Oracle-DLog}}(\lambda) \implies 1]. $$

By $\text{Adv}_{\mathbb{G}}^{\text{Oracle-DLog}}(\lambda)$ we denote the maximum advantage over all the p.p.t. adversary $\mathcal{A}$. The Oracle-DLog problem is said to be hard in $\mathbb{G}$ if $\text{Adv}_{\mathbb{G}}^{\text{Oracle-DLog}}(\lambda)$ is negligible in $\lambda$.

<figure><img src="image_4.png" /><figcaption>FIGURE 4 – The Oracle-DLog experiment</figcaption></figure>

### 3.2.3 Signature scheme

Signature-based authentication methods (i.e., methods 0, 1, 2) in EDHOC require the use of an EUF-CMA-secure signature scheme (usually instantiated by EdDSA or ES256), while static-DH-based authentication is combined with a MAC scheme, which in EDHOC in fact implements as HKDF_Expand (thus, we idealize this call as a random oracle). We extend the use of digital signature scheme to proxies. In order to do that properly, we define what is a digital signature scheme and also what is the EUF-CMA property expected from it.

**Definition 7 (Digital signature scheme)** A digital signature scheme DS consists of three algorithms: DS.Gen and DS.Sign which are probabilistic and DS.Verif which is deterministic. The first one, DS.Gen, takes as input the security parameter $1^{\lambda}$ and outputs a pair of public/private signing keys (PK, SK). The second one, DS.Sign, takes as input the secret key SK and a message $m$ to sign, and outputs a signature $\sigma$ for $m$. Finally, DS.Verif takes as input the public key PK, the message $m$, and the signature $\sigma$, and outputs 1 if $\sigma$ is a valid signature for $m$, or 0 otherwise.

Moreover, we require that DS has perfect correctness, i.e., that for all (PK, SK) output by DS.Gen, for all message $m$, $DS.Verif(PK, m, DS.Sign(SK, m)) = 1$.

**Definition 8 (EUF-CMA property)** The Existential Unforgeability against Chosen Messages Attacks property against a p.p.t. adversary $\mathcal{A}$ for a digital signature scheme DS = (DS.Gen, DS.Sign, DS.Verif),
having access to a signing oracle Sig, is defined thanks to the experiment depicted in FIGURE 5.

The digital signature scheme DS is said existentially unforgeable against chosen messages attacks if:

$$ \mathbf{Adv}_{\text{DS},\mathcal{A}}^{\text{EUF-CMA}}(\lambda) = \mathbb{P}[\mathbb{E}_{\text{DS},\mathcal{A}}^{\text{EUF-CMA}}(\lambda) \implies 1] $$

is negligible in $\lambda$ for all p.p.t. adversary $\mathcal{A}$. We then denote the maximum advantage over all the p.p.t. adversary $\mathcal{A}$ by $\mathbf{Adv}_{\text{DS}}^{\text{EUF-CMA}}(\lambda)$.

<figure><img src="image_5.png" /><figcaption>FIGURE 5 – The EUF-CMA experiment</figcaption></figure>

### 3.2.4 Zero-knowledge tools

Following the work established in [5, 9], we embed in the EDHOC protocol LI elements, which are proved well constructed by the endpoint thanks to a signature of knowledge, a well-known primitive. We also use non-interactive proof of knowledge to add security on long-term key and trapdoors. We now define properly signature of knowledge and proof of knowledge, with the required properties for the security of the protocol. For that, let $\mathcal{R}$ be a binary relation and let $\mathcal{L}$ be a language such that $s \in \mathcal{L} \iff (\exists w, (s, w) \in \mathcal{R})$.

The objective of a prover with a Non-Interactive Proof of Knowledge (NIPoK) is to convince a verifier, possessing a statement $s$, that he knows a witness $w$ such that $(s, w) \in \mathcal{R}$. The nature of the Zero-Knowledge (ZK) property of NIPoK additionally certifies that no information about $w$ is revealed with the proof. Signature of knowledge (SoK) are similar to NIPoK. Here a prover will use its witness $w$ as a signature private key to sign the message $m$, and then the verifier uses the statement as a public signature key to check the validity of the signature. If the verification is positive, the verifier is convinced by the prover that the latter know a witness for the statement. We can again here ask for a ZK property. In what follows, for a statement $s$, a witness $w$ and a message $m$, we denote by $\text{NIPoK}\{w : (w, s) \in \mathcal{R}\}$ and $\text{SoK}_m\{w : (w, s) \in \mathcal{R}\}$ respectively NIPoK and SoK. We require that the one we use are ZK. We will give in that paper an example of such a signature of knowledge, using practical objects for implementation (but any kind of proof/signature of knowledge satisfying the security properties can be used).

**Definition 9 (Non-interactive proof of knowledge)** A Non-Interactive Proof of Knowledge (NIPoK) for the language $\mathcal{L}$ is a pair of algorithms (NIPoK, NIPoKver) verifying: (1) NIPoK$\{w : (s, w) \in \mathcal{R}\} \to \nu$; and (2) NIPoKver$(s, \nu) \to b$, where $b$ is either 1 or 0 if the proof is valid or not.

For memory, $s$ denotes the statement for which a prover knows a witness $w$ and $\nu$ denotes the proof outputs by NIPoK and verified by a verifier.

We require that our NIPoK has the following properties:
† Completeness: for all pair $(s, w) \in \mathcal{R}$, we have the equation:

$$ \mathrm{NIPoKver}(s, \mathrm{NIPoK}\{w : (s, w) \in \mathcal{R}\}) = 1. $$

† Perfect Zero Knowledge: there exists a polynomial-time algorithm called the simulator and denoted $\mathrm{Sim}_{\mathrm{NIPoK}}$ taking as input a statement, such that for all pair $(s, w) \in \mathcal{R}$, $\mathrm{Sim}_{\mathrm{NIPoK}}$ and $\mathrm{NIPoK}\{w : (s, w) \in \mathcal{R}\}$ follow the same probability distribution. This is a formal reformulation of the zero-knowledge idea presented above. We require the simulator to generate a proof, without knowing $w$, that is indistinguishable from the one generated by the prover. If this is the case, it means that the real proof reveals no information about the secret.

† Knowledge extractor: there exists a probabilistic polynomial time (p.p.t.) algorithm called the extractor and denoted $\mathrm{Ext}_{\mathrm{NIPoK}}$ as well as a negligible function $\epsilon_{\mathrm{NIPoK}}$ of $\lambda$, such that for any algorithm $\mathcal{A}(\lambda)$ having access to the previous simulator $\mathrm{Sim}$ that forges signatures for chosen statement and that outputs a fresh tuple $(s, \nu)$ verifying $\mathrm{NIPoKver}(s, \nu) = 1$, then the extractor $\mathrm{Ext}_{\mathrm{NIPoK}}(\lambda)$, having access to $\mathcal{A}(\lambda)$, outputs a witness $w$ such that $(s, w) \in \mathcal{R}$ with probability at least $1 - \epsilon_{\mathrm{NIPoK}}(\lambda)$.

The definition on signature of knowledge follows the same construction as NIPoK.

**Definition 10 (Signature of knowledge)** A Signature of Knowledge (SoK) for the language $\mathcal{L}$ is then a pair of algorithms (SoK, SoKver) verifying: (1) SoK$\{m|w : (s, w) \in \mathcal{R}\} \to \sigma$, where $\sigma$ is a signature of the message $m$; and (2) SoKver$(m, s, \sigma) \to b$, where $b$ is either 1 or 0 if the signature is valid or not. For memory, $m$ denotes the message to sign, $s$ denotes the statement for which we know a witness $w$ and $\sigma$ denotes the signature outputs by SoK.

We require that our SoK verifies the following properties:

† Completeness: for all pair $(s, w) \in \mathcal{R}$, for all message $m$, we have the equation: $\mathrm{SoKver}(m, s, \mathrm{SoK}\{m|w : (s, w) \in \mathcal{R}\}) = 1$.

† Perfect Zero Knowledge: there exists a polynomial-time algorithm called the simulator and denoted $\mathrm{Sim}_{\mathrm{SoK}}$ taking as input a message and a statement, such that for all message $m$, for all pair $(s, w) \in \mathcal{R}$, $\mathrm{Sim}_{\mathrm{SoK}}(m, s)$ and $\mathrm{SoK}\{m|w : (s, w) \in \mathcal{R}\}$ follow the same probability distribution.

† Knowledge extractor: there exists a probabilistic polynomial time (p.p.t.) algorithm called the extractor and denoted $\mathrm{Ext}_{\mathrm{SoK}}$ as well as a negligible function $\epsilon_{\mathrm{SoK}}$ of $\lambda$, such that for any algorithm $\mathcal{A}(\lambda)$ having access to the previous simulator $\mathrm{Sim}_{\mathrm{SoK}}$ that forges signatures for chosen message/statement pairs and that outputs a fresh tuple $(m, s, \sigma)$ verifying $\mathrm{SoKver}(m, s, \sigma) = 1$, then the extractor $\mathrm{Ext}_{\mathrm{SoK}}(\lambda)$, having access to $\mathcal{A}(\lambda)$, outputs a witness $w$ such that $(s, w) \in \mathcal{R}$ with probability at least $1 - \epsilon_{\mathrm{SoK}}(\lambda)$.

In this work, we rely on proofs of knowledge of discrete logarithms, which are known to be efficiently constructible [11]. Subsequently, signatures of knowledge can be derived from non-interactive zero-knowledge proofs using the Fiat-Shamir heuristic [10].

### 3.2.5 Encryption scheme

Key-derivation for EDHOC employs HKDF [26], which comes with an Extract-and-Expand mechanism. We idealize both steps as a random oracle. Once expanded, keys are used in two fundamental ways: for stream-cipher encryption (XOR-ing key-bits with plaintext-bits), and for AEAD-encryption (which we require to be AEAD-secure). Following [14], we describe in more detail the properties of the two encryption schemes
we use in the protocol. The first encryption is made with a symmetric encryption scheme (KGen, Enc, Dec) verifying the two following properties.

We require that our XOR-ing encryption scheme (KGen, Enc, Dec) satisfies the common and implicit following property: *injectivity*.

**Definition 11 (Injective property)** *The symmetric encryption scheme (KGen, Enc, Dec) satisfies the Injective property if :*

$$ \forall sk \in \mathcal{K}, \forall m_0, m_1 \in \mathcal{M}, \text{Enc}(sk, m_0) = \text{Enc}(sk, m_1) \implies m_0 = m_1 $$

where $\mathcal{K}$ denotes the key space and $\mathcal{M}$ the message space.

In other words, for each fixed key and each pair of messages, if the encryption with the key the two messages gives the same ciphertext, then this implies that the two messages are the same, or said another way, for a fixed key, it is impossible to find two different messages which give the same ciphertext when encrypted with this key.

The identity protection property of the LI-EDHOC protocol on the Responder point of view, defined in [14], consist generally speaking in distinguishing the identity of two given Responder. This property requires that our XOR-ing encryption scheme satisfies a very common property, close to the IND-CPA property, but only allowing the adversary to choose one pair of plaintext messages, the IND property.

**Definition 12 (Indistinguishability property)** *The Indistinguishability property of the encryption scheme (KGen, Enc, Dec) against a p.p.t. adversary $\mathcal{A}$ is defined thanks to the experiment IND depicted in FIGURE 7. The encryption scheme (KGen, Enc, Dec) satisfies the indistinguishability property if:*

$$ \text{Adv}_{(\text{KGen}, \text{Enc}, \text{Dec}), \mathcal{A}}^{\text{IND}}(\kappa) = \mathbb{P}[\mathbb{E}_{(\text{KGen}, \text{Enc}, \text{Dec})}^{\text{IND}}(\kappa) \implies 1] $$

is a function negligible in $\kappa$ ($\kappa$ a security parameter) for all p.p.t. adversary $\mathcal{A}$. We then denote the maximum advantage over all the p.p.t. adversary $\mathcal{A}$ by $\text{Adv}_{(\text{KGen}, \text{Enc}, \text{Dec})}^{\text{IND}}(\kappa)$.

For example, the OTP encryption scheme verifies these two properties. For the second encryption, we use an Authenticated Encryption with Associated Data (AEAD) encryption scheme, generally defined as follows.

**Definition 13 (Authenticated Encryption with Associated Data)** *An Authenticated Encryption with Associated Data encryption scheme is an encryption scheme $(\text{KGen}^{\prime}, \text{Enc}^{\prime}, \text{Dec}^{\prime})$ working as follows. The key-generation algorithm takes as input a security parameter $\kappa$ and picks a random a secret key sk (from a key space $\mathcal{K}$) and an initialization vector IV (from an $\mathcal{IY}$ space) and returns (sk, IV). The encryption algorithm Enc$^{\prime}$, on input (sk, IV), a message m (of a message space $\mathcal{M}$) and some associated data a (from a data space $\mathcal{AD}$), outputs the ciphertext c = Enc$^{\prime}$(sk, IV, m, a). Finally the decryption algorithm Dec$^{\prime}$ takes as input (sk, IV), a ciphertext c (from a ciphertext space $\mathcal{C}$) and some associated data a, returns m = Dec$^{\prime}$(sk, IV, c, a) if c is a valid ciphertext for sk, IV and a, or $\perp$ otherwise.*

We need our AEAD encryption scheme to be secure in the following way.

**Definition 14** *We say that our AEAD encryption scheme is secure if, for all p.p.t. adversary $\mathcal{A}$, the advantage $\text{Adv}_{\text{AEAD}, \mathcal{A}}^{\text{Secure}}(\kappa)$, defined thanks to the experiment depicted in FIGURE 6 by :*

$$ \text{Adv}_{\text{AEAD}, \mathcal{A}}^{\text{Secure}}(\kappa) = \left| \mathbb{P}[\mathbb{E}_{\text{AEAD}}^{\text{Secure-1}}(\kappa) \implies 1] - \mathbb{P}[\mathbb{E}_{\text{AEAD}}^{\text{Secure-0}}(\kappa) \implies 1] \right| $$
is negligible compared to $κ$.

In other words, an adversary $\mathcal{A}$ has access, for a fixed key generated by the challenger, to an encryption and a decryption oracle. The adversary may query both. Depending on the game, the encryption oracle return a faithfully encrypt message or a random ciphertext of the expected length. On the other side, the decryption oracle return either the faithful decryption of a ciphertext (not previously generated by $\mathcal{A}$) or $⊥$. The advantage of $\mathcal{A}$ is then its probability of distinguishing which experiment he played.

<figure><img src="image_6.png" /><figcaption>FIGURE 6 – AEAD secure games (here $C^{|c'|}$ denotes the set of ciphertexts of length $|c'|$).</figcaption></figure>

Then for the identity protection property on the point of view of the Initiator, we require that our AEAD encryption scheme satisfies the following two properties, ensuring that the adversary may not be able to distinguish between two Initiator's identities.

**Definition 15 (IND-CPA property)** The Indistinguishability under Chosen Plaintext Attack property against a p.p.t. adversary $\mathcal{A}$ of an AEAD encryption scheme (KGen', Enc', Dec') is defined thanks to the experiment IND depicted in FIGURE 7. The AEAD encryption scheme satisfies the IND-CPA security property if:

$$ \text{Adv}_{\text{AEAD}, \mathcal{A}}^{\text{IND-CPA}}(\kappa) = \mathbb{P}[\mathbb{E}_{\text{AEAD}}^{\text{IND-CPA}}(\kappa) \implies 1] $$

is negligible in $κ$ ($κ$ a security parameter) for all p.p.t. adversary $\mathcal{A}$. We then denote the maximum advantage over all the p.p.t. adversary $\mathcal{A}$ by $\text{Adv}_{\text{AEAD}}^{\text{IND-CPA}}(\kappa)$.

**Definition 16 (UF-CMA property)** The UnForgeability under Chosen-Message Attack security property of an AEAD encryption scheme (KGen', Enc', Dec') against a p.p.t. adversary $\mathcal{A}$, having access to an AEAD encryption oracle $\mathcal{O}_{\text{Enc}'}$, is defined thanks to the experiment UF-CMA depicted in FIGURE 7. The AEAD encryption scheme satisfies the UF-CMA property if:

$$ \text{Adv}_{\text{AEAD}, \mathcal{A}}^{\text{UF-CMA}}(\kappa) = \mathbb{P}[\mathbb{E}_{\text{AEAD}}^{\text{UF-CMA}}(\kappa) \implies 1] $$
is a function negligible in $κ$ for all p.p.t. adversary $\mathcal{A}$. We then denote the maximum advantage over all the p.p.t. adversary $\mathcal{A}$ by $\text{Adv}_{\text{AEAD}}^{\text{UF-CMA}}(κ)$.

<figure><img src="image_7.png" /><figcaption>FIGURE 7 – The IND, IND-CPA and UF-CMA experiments</figcaption></figure>

### 3.2.6 Hash function

We also need a hash function $\mathcal{H}$ at different stages. In particular, the key-derivation steps rely on the computation and input of updated session hashes.

We idealize this hash function $\mathcal{H}$ as a random oracle (in practice, instantiated as SHA256).

The choice of precise primitives as described in [29] makes it possible to respect, in particular, the physical implementation constraints. In our case, we consider more general and theoretical primitives possessing some specific cryptographic properties, while ensuring that those used in [29] verify these properties.

## 3.3 The identical-until-bad lemma

Another important tool that will be used in our security proofs is the famous identical-until-bad lemma (also known as the fundamental lemma of game-playing in [7], or as (an adaptation of) the difference lemma in [33]).

**Theorem 1 (The identical-until-bad lemma)** Let $\mathbb{G}_q$ and $\mathbb{G}_j$ be two games and let $F$ be an event. We consider $Z$ the set of all possible outputs common to both games $\mathbb{G}_q$ and $\mathbb{G}_j$. We assume that for all $\zeta \in Z$, the events $"\mathbb{G}_q \Rightarrow \zeta"$, $"\mathbb{G}_j \Rightarrow \zeta"$ and $F$ are defined on the same probability space. We also assume that $\mathbb{G}_q$ and $\mathbb{G}_j$ behave identically unless the event $F$ occurs in one of them, i.e., for all $\zeta \in Z$, $[(\mathbb{G}_q \Rightarrow \zeta) \wedge \neg F] \iff [(\mathbb{G}_j \Rightarrow \zeta) \wedge \neg F]$.

Under the previous assumptions, we have, for all $\zeta \in Z$:

$$|\mathbb{P}(\mathbb{G}_q \Rightarrow \zeta) - \mathbb{P}(\mathbb{G}_j \Rightarrow \zeta)| \le \mathbb{P}(F).$$
**Proof 1** The proof is quite direct. Let $\zeta \in Z$. First, by the law of total probability, we have:

$$|\mathbb{P}(\mathbb{G}_q \Rightarrow \zeta) - \mathbb{P}(\mathbb{G}_j \Rightarrow \zeta)| = |\mathbb{P}[(\mathbb{G}_q \Rightarrow \zeta) \wedge F] + \mathbb{P}[(\mathbb{G}_q \Rightarrow \zeta) \wedge \neg F] - \mathbb{P}[(\mathbb{G}_j \Rightarrow \zeta) \wedge F] - \mathbb{P}[(\mathbb{G}_j \Rightarrow \zeta) \wedge \neg F]|.$$

Since by assumption $[(\mathbb{G}_q \Rightarrow \zeta) \wedge \neg F] \iff [(\mathbb{G}_j \Rightarrow \zeta) \wedge \neg F]$, it comes that $\mathbb{P}[(\mathbb{G}_q \Rightarrow \zeta) \wedge \neg F] = \mathbb{P}[(\mathbb{G}_j \Rightarrow \zeta) \wedge \neg F]$, and we now obtain:

$$|\mathbb{P}(\mathbb{G}_q \Rightarrow \zeta) - \mathbb{P}(\mathbb{G}_j \Rightarrow \zeta)| = |\mathbb{P}[(\mathbb{G}_q \Rightarrow \zeta) \wedge F] - \mathbb{P}[(\mathbb{G}_j \Rightarrow \zeta) \wedge F]|.$$

But it is clear that $\mathbb{P}[(\mathbb{G}_q \Rightarrow \zeta) \wedge \neg F] \in [0; \mathbb{P}(F)]$ and $\mathbb{P}[(\mathbb{G}_j \Rightarrow \zeta) \wedge \neg F] \in [0; \mathbb{P}(F)]$. So the absolute value of the difference cannot exceed $\mathbb{P}(F)$, which can be rewritten as:

$$|\mathbb{P}(\mathbb{G}_q \Rightarrow \zeta) - \mathbb{P}(\mathbb{G}_j \Rightarrow \zeta)| = |\mathbb{P}[(\mathbb{G}_q \Rightarrow \zeta) \wedge F] - \mathbb{P}[(\mathbb{G}_j \Rightarrow \zeta) \wedge F]| \leq \mathbb{P}(F).$$

This is what was announced, and this concludes the proof. ■

## 3.4 The LIKE framework

Originally introduced in the context of mobile authenticated key-exchange protocols, Lawful Interception Key Exchange (LIKE) is a two-party AKE scheme featuring two proxies, representing the serving networks of the two endpoints [5]. The system also features a number of authorities, which need not be online for the duration of each protocol session. Each handshake is lawfully-interceptable by the collaboration of all the members of an authority set, whose size and composition depend on current legislations.

Formally, LIKE is defined as $\text{LIKE} = (\text{Setup}, \text{UKeyGen}, \text{OpKeyGen}, \text{AKeyGen}, \text{AKE}, \text{Verify}, \text{TDGen}, \text{Open})$. Setup provides a global setup for the choice of universal parameters. The next three algorithms allow mobile users, operators, and authorities to generate long-term public keys. The LIKE protocol is run in sessions via the AKE algorithm. The verification algorithm allows for the verification of the soundness of the handshake and for the validation of the participants, whereas the last two algorithms provide mechanisms for LI.

LIKE assumes a scenario in which the two endpoints can only communicate through the proxies, and the protocol guarantees: key-security, non-frameability, and LI compliance (also called “honest-operator” in [5, 9]). In this paper, we start from [9], a follow-up work of [5] which achieved pairing-free LIKE in the roaming scenario, by using an Elgamal-like encryption of the session secret.

Our approach carefully combines this second LIKE approach, and makes use of both (non-interactive) proofs and signatures of knowledge.
## 4 LI-compliant EDHOC

In order to empower mobile network operators (MNOs) with the ability to provide privacy-preserving LI-compliant secure-channel establishment, we encrypt session secrets in the session state, such that only the collaboration of the entire authority-set will be able to decrypt these values. For that purpose, we essentially combine the LIKE approach and the EDHOC protocol (section 2).

The composition is not black-box, for several important reasons. The first is our wish to preserve as many of the EDHOC properties as possible, including identity-protection. The latter requires that network adversaries (passive, for Responders, active, for Initiators) be unable to distinguish the endpoint's identity. As a result, some of the LIKE messages will need to be incorporated in EDHOC's encrypted messages, modifying them in a non-trivial fashion. As a result, we prefer to use different notations for the two protocols, referring to EDHOC's first and second messages as message_1 and message_2 (as in section 2), as opposed to $M_1$ and $M_2$ for our protocol LI-EDHOC. Another problem is verifying the consistency of the elements input in the key-computation, which we discuss below. Finally, we choose white-box composition for the sake of efficiency – since some LIKE elements are already present in EDHOC.

An important modification we make to the original LIKE [5, 9] is that the session keys take in input an additional nonce $n_r$ (and we use the exporter keys featured in EDHOC). This artifice of our construction is necessary in order to enforce LI-compliance on the initiator's side. Thus, we include the nonce $n_r$ in the context of the exporter PRK expansion (bottom right of FIGURE 2). Encrypting part of the handshake also raises a serious concern with respect to LI-compliance, in which proxies must be able to prove that the elements required to compute the key are consistent with the encrypted secrets and the ciphertexts. A naïve solution would be to send the entire messages unencrypted (thus nullifying the identity-protection afforded by EDHOC). Our solution tries to reconcile both LI requirements and identity-protection. We make endpoints send their encryption keys (not secrets) for handshake messages, encrypted with a key shared between the endpoint and the proxy<fnref n="2" />, which allows the latter to verify the consistency of the transcript<fnref n="3" />.

In order to provide LI-recovery of session keys, we essentially encrypt some component session secrets, as specified in TABLE 2. In the rest of this section, we will explain how, using elements $H$ (and optionally $H^1$ and $H^2$), authorities may recover $g^{xy}$ (and $g^{rx}$ and $g^{iy}$). This could be done naïvely by running the protocol of [9] for each secret in parallel; that, however, would be suboptimal and could potentially break the LI-compliance guarantee, since EDHOC features an inter-dependence between the ephemeral and semi-static secrets. Each secret will be recovered by the authorities from an ElGamal-like encryption of it under the product of the authorities' keys. During the protocol, each authority derives a trapdoor (essentially a local decryption with just its own private key) – and by using the homomorphic properties of ElGamal, the combination of all trapdoors yields the session's secret. Crucially, if even one authority withholds its trapdoor, the secret remains hidden – even from a collusion of all other authorities.

Our white-box approach to combining the LIKE approach and EDHOC enables us to minimise the overhead introduced to EDHOC, while reusing its elements (such as the ephemeral DH values $g^x, g^y$) as components in both protocols. To further reduce computational overhead, we use Schnorr-based proofs and signatures of knowledge, applying the Fiat-Shamir heuristic to make them non-interactive.

We proceed to describe our protocol, whose handshake is also depicted in FIGURE 8. This is a high level description. Much more details, for each version of the protocol, are depicted in FIGURES 9 and 10 (ID = 0), in FIGURES 11 and 12 (ID = 1), in FIGURES 13 and 14 (ID = 2) and in FIGURES 15 and 16 (ID = 3).

<footnote n="2">²This is not a strong assumption, as the mobile protocol stack feature a hierarchy of keys usable to that effect.</footnote>

<footnote n="3">³We considered two alternative approaches. The key under which the keys are encrypted could be negotiated during the handshake, at the expense of additional complexity. We discarded this alternative since a shared key is already present in the 5G stack. A second, cleaner alternative would be to encrypt handshake messages with a different key, which is computable by the proxies and endpoints alike. Unfortunately this would require modifying the key schedule of EDHOC (already standardized) and potentially introducing cumbersome key-computation tools including pairings.</footnote>
has a different shape (either a DIFFIE-HELLMAN element, or signature keys). The EKeyGen algorithm, for an endpoint E, generates these two pairs of keys, an latter when running a protocol session, E selects the appropriate pair.

**EKeyGen(pp):** This algorithm generates a signing keys pair (ssk<sub>E</sub>, spk<sub>E</sub>) using the DS.Gen algorithm from DS, and also sample $e \leftarrow \mathbb{Z}_p^*$ and generates $(e, g^e) := (\text{E.SK}, \text{E.PK})$, a static DIFFIE-HELLMAN keys pair. It then returns ((ssk<sub>E</sub>, spk<sub>E</sub>), (e, g<sup>e</sup>)). Then depending on the method used for the key-exchange, the user selects one of the two pairs of (long term) keys that will be used for the specific protocol run.

## 4.2 Precomputation stage

Handshakes are preceded by a precomputation phase, during which users verify all authorities' public keys and proofs. Note that due to roaming, LI can take place for an independent set of authorities at each end (Initiator and Responder). In addition, at this point we assume that, if the proxy does not already have a shared key pcsk<sub>E,ProxE</sub> with its endpoint (E), then we assume both the proxy and endpoint generate this common key<fnref n="4" />.

On their side, the Initiator and its proxy Prox<sub>I</sub> run the PreComp<sub>I</sub> algorithm, which parses APK<sub>I</sub> = (Λ<sup>I</sup><sub>j</sub>.PK)<sup>n<sub>I</sub></sup><sub>j=1</sub> (vector of the public keys of the Initiator's authorities involved in the interception process) as ((Λ<sup>I</sup><sub>j</sub>.pk, Λ<sup>I</sup><sub>j</sub>.ni))<sup>n<sub>I</sub></sup><sub>j=1</sub> and checks Λ<sup>I</sup><sub>j</sub>.ni for all j ∈ [1, n<sub>I</sub>].

It sets $\omega_I \leftarrow (\Lambda_j^I)^{n_I} \| \text{ID\_CRED\_I}^5$ and $h_I \leftarrow \prod_{j=1}^{n_I} \Lambda_j^I \cdot \text{pk} = \prod_{j=1}^{n_I} g^{\Lambda_j^I \cdot \text{SK}}$.

If the Initiator and its proxy does not already share a long-term encryption key pcsk<sub>I,ProxI</sub>, PreComp<sub>I</sub> generates such a key (in our modeling we assume that this long term key is used for a secure encryption scheme (KGen'', Enc'', Dec'')).

Similarly, the Responder and its proxy Prox<sub>R</sub> do the same check routine, and they set $\omega_R \leftarrow (\Lambda_j^R)^{n_R} \| \text{ID\_CRED\_R}$ and $h_R \leftarrow \prod_{j=1}^{n_R} \Lambda_j^R \cdot \text{pk} = \prod_{j=1}^{n_R} g^{\Lambda_j^R \cdot \text{SK}}$ thanks to the PreComp<sub>R</sub> algorithm. If necessary, they also negotiate a long-term encryption key pcsk<sub>R,ProxR</sub>.

The values ($h_I, \omega_I$) and pcsk<sub>I,ProxI</sub> (for the Initiator), and ($h_R, \omega_R$) and pcsk<sub>R,ProxR</sub> (for the Responder), are shared between the proxies and the endpoints. We assume moreover that the proxies know the identity of the endpoints (as is already the case following an initial AKA/Handshake). This stage can be done once and then reused for multiple sessions (for the same set of authorities of an endpoint).

Elements $h_I$ and $h_R$ are publicly known, but their insertion in the protocol will allow us to do secure lawful interception. Indeed, their role is to help authorities to retrieve e.g., $g^{xy}$, a necessary element to compute the session key.

Formally expressed as an algorithm, this results in the following process, which must be executed as a precomputation by both the Initiator and the Responder.

**PreComp<sub>I</sub>($M_I$):** Parse $M_I$ as $(\Lambda_j^I)^{n_I} \| \text{ID}_I$, and verify each authority's proof via NIPoKver(Λ<sup>I</sup><sub>j</sub>.pk, Λ<sup>I</sup><sub>j</sub>.ni). Upon failure, the procedure aborts with $\perp$. Upon success, compute $h_I \leftarrow \prod_{j=1}^{n_I} \Lambda_j^I \cdot \text{pk}$, and $\omega_I \leftarrow (\Lambda_j^I)^{n_I} \| \text{ID}_I$, and return $(h_I, \omega_I)$.

Algorithm PreComp<sub>R</sub> for the Responder is naïvely obtained from PreComp<sub>I</sub> by adapting the notations.

We will now describe the four versions of the LI compliant EDHOC protocol, assuming all precomputations are done. In what follows, we present the modifications we made on the original protocol, and we provide in four figures an algorithmic description of the protocols, respecting the specification of [32].

<footnote n="4">⁴This would be done at the beginning of each handshake anyway, within the 5G protocol stack.</footnote>

<footnote n="5">⁵This notation, ID\_CRED\_E, comes from [32] and denotes the identity credentials of an user E. In the rest of the paper we will abbreviate it as ID<sub>E</sub>, to make it mode readable.</footnote>
## 4.3 Handshake - First case

**Message flow.** With elements of the pre-computation stage, we can now integrate lawful interception in the EDHOC protocol. For this we will insert into the message flow a tool which will subsequently allow us to generate trapdoors and make fine-grained lawful interception by recovering the session key PRK<sub>out</sub>. We first consider the case where both the Initiator and the Responder use signature as current authentication method (ID = 0 in TABLE 1). We will later explain the changes to be made in case this method changes (ID = 1, 2, 3 in TABLE 1). The protocol is depicted in FIGURES 8 and 9 below.

Messages between the endpoints, the Initiator and the Responder, pass through proxies we added to the scheme. The first task of the Initiator remains unchanged. He sample its session nonce (connexion identifier) and its DIFFIE-HELLMAN pair. He then sends message $M_1$, to the Responder, via proxies Prox<sub>I</sub> and Prox<sub>R</sub> (InitRun1). To sum up $M_1$ contains, $g^x$, its connection identifier $C_I$, the authentication method (here it is 0), the cipher suite which will be used, and the external authorization data EAD<sub>1</sub>. The proxy Prox<sub>I</sub> (with Prox<sub>I</sub>Run1) initializes $\tau_I$ as $\omega_I \| \text{MCS} \| g^x$ ($g^x$, and latter $g^y$, are necessary elements for trapdoors generation) and Prox<sub>R</sub> initializes $\tau_R$ as $\omega_R \| \text{MCS} \| g^x$ (Prox<sub>R</sub>Run1)(here MCS denotes the method and cipher suite that the Initiator wants to use for the handshake).

The first actions of the Responder remains also unchanged, except that he returns to its proxy the usual EDHOC second message, concatenated with the transcript hash, i.e., he sends its ephemeral DIFFIE-HELLMAN element $g^y$ and the ciphertext $c_2$ (which is $m_2$ encrypted with the key $sk_2$ (RespRun1)).

The proxy Prox<sub>R</sub> updates $\tau_R$ with $g^y$, and sends $g^y$ and $c_2$ to Prox<sub>I</sub>, which also update $\tau_I$ with $g^y$, before returning the message he received to the Initiator (Prox<sub>R</sub>Run2 and Prox<sub>I</sub>Run2).

The first important addition is made on the Initiator side (in InitRun1). Besides its usual calculations, we ask him to compute $H_I$ with his private DIFFIE-HELLMAN element $x$, the shared ephemeral DIFFIE-HELLMAN element $g^y$ and the public value $h_I$: $H_I = (h_I g^y)^x$, and to sign it with a signature of knowledge of discrete logarithm. This signature is important because $H_I$ is necessary for retrieving the session key PRK<sub>out</sub> (so we must ensure that $H_I$ as been constructed well). The signed message contains the identities of the involved parties (authorities and endpoints) as well as the three transcript hashes. These elements are important for the lawful interception process. Indeed, if the signature of knowledge is valid, this ensure that the two endpoints well take part to the handshakes and that the elements used for the computation of PRK<sub>out</sub>, which will be transmitted to the authorities, are correct. This signature is a central object in the implementations presented in section 5. In addition to this, the Initiator encrypt the two secret key $sk_2$ and ($sk_3, \text{IV}_3$), and the HMAC $t_2$ with the key $\text{psck}_{I, \text{Prox}_I}$ as $S_I^6$.

Then the Initiator sends (in clear in $M_3$) to its proxy Prox<sub>I</sub>, in addition to the usual ciphertext $c_3$ (which is $m_3$ encrypted using $sk_3$), the element $H_I$ and the signature of knowledge $n_I$, along with $S_I$. When receiving this message, the proxy decipher $S_I$. Since he now gets $M_1, c_2$ and $c_3$, along with $sk_2$ and ($sk_3, \text{IV}_3$), he can on his own compute $\text{TH}_2, \text{TH}_3$, and $\text{TH}_4$ and verify the signature $\sigma_2$ with $t_2$ and $m_2$; he also obtains $\text{ID}_R$ from $c_2$. With these elements, he recreates the signed message of the SoK $n_I$ and verified it. If it is valid, this means that all elements are correct so far. He updates $\tau_I$ by storing $\text{TH}_2, \text{TH}_3, \text{TH}_4, M_1, m_2$ and $m_3, t_2, H_I, n_I$, and $\text{ID}_R$ (so far we have $\tau_I = \omega_I \| \text{MCS} \| g^x \| g^y \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4 \| M_1 \| m_2 \| m_3 \| H_I \| n_I \| \text{ID}_R \| t_2$) (Prox<sub>I</sub>Run2). Finally it forwards $c_3$ to Prox<sub>R</sub> which simply forwards it to the Responder.

The Responder, on his side (RespRun2), performs its usual calculations and the same additional operations as the Initiator with the element $H_R$ and the signature of knowledge $n_R$. He also ciphers the keys $sk_2$ and ($sk_3, \text{IV}_3$) along with the two HMAC $t_2$ and $t_3$, as $S_R$. There is also another important modification here. In the normal EDHOC protocol, this fourth message is optional. In our situation we must make it mandatory because we must add randomness in the computation of the session key PRK<sub>out</sub> in the following way. The Responder picks at random a nonce $n_r$ and inserts it in the computation of PRK<sub>out</sub>. He also computes a verification value (whose usefulness will be explained below) $\text{val} = \mathcal{H}(g^{xy}, \dots, n_r)$ and the value

<footnote n="6">⁶This addition is not trivial and useless; it results from extensive reflexion and optimization efforts aimed at resolving an issue that emerged during the proof of the non-frameability security property. In particular, it concerns the ability of verify a signature during the verification phase. Moreover, both HMACs must be sent separately on the Initiator's side in order to prevent an impersonation attack.</footnote>
TH₅ = H(TH₄, val, nᵣ). In this way, the Initiator, when receiving M₄ obtains nᵣ and is able to compute the same PRK<sub>out</sub>. The natural question is then: why is this necessary?

To make is simple, if we do not insert this fourth message, including randomness, the Initiator computes the key PRK<sub>out</sub> before the Responder and the latter can also compute PRK<sub>out</sub> before proving to its proxy he formed well its lawful interception element H<sub>R</sub>. So in this situation, the two endpoints may engaged a communication which is not completely interceptable<sup>7</sup>. The addition of the randomness and the fourth obligatory message prevent this situation<sup>8</sup>.

As the Initiator did, the Responder now needs to transmit these values to its proxy. So he sends M<sub>4</sub> composed of the ciphertext c<sub>4</sub> (which is m<sub>4</sub> encrypted with sk<sub>4</sub>), transcript hashes TH<sub>2</sub>, TH<sub>3</sub> and TH<sub>4</sub>, the element H<sub>R</sub> along with the signature of knowledge ni<sub>R</sub>, and also n<sub>r</sub>, TH<sub>5</sub> and val.

At this point, we must explain how which party finishes its run of the exchange. Firstly Prox<sub>R</sub>, as Prox<sub>I</sub> did, deciphers S<sub>R</sub> and computes m<sub>2</sub>, m<sub>3</sub> and the transcript hashes TH<sub>2</sub>, TH<sub>3</sub> and TH<sub>4</sub> on its own (he also obtains ID<sub>I</sub> from c<sub>3</sub>). He verifies the two signatures σ<sub>2</sub> and σ<sub>3</sub> with t<sub>2</sub> and t<sub>3</sub>. He also verifies the signature of knowledge he received, as well as the validity of n<sub>r</sub> with val, TH<sub>5</sub> and the value he computed TH<sub>4</sub>. If it is valid, he then updates in τ<sub>R</sub> (we have τ<sub>R</sub> = ω<sub>R</sub>||MCS||g<sup>x</sup>||g<sup>y</sup>||TH<sub>2</sub>||TH<sub>3</sub>||TH<sub>4</sub>||M<sub>1</sub>||m<sub>2</sub>||m<sub>3</sub>||H<sub>R</sub>||ni<sub>R</sub>||ID<sub>I</sub>||t<sub>2</sub>||t<sub>3</sub>||n<sub>r</sub>||val), and then signed τ<sub>R</sub> with its private signature key ssk<sub>Prox<sub>R</sub></sub>. The session state sst<sub>R</sub> he stores and provides eventually to authorities is τ<sub>R</sub> concatenated with this signature (Prox<sub>R</sub>Run<sub>3</sub>). He finally forwards c<sub>4</sub>, n<sub>r</sub>, val, TH<sub>5</sub> and t<sub>3</sub> to Prox<sub>I</sub>, which checks the validity of this message and the signature σ<sub>3</sub> (as Prox<sub>R</sub> did) and performs the same computations as Prox<sub>R</sub> to generate sst<sub>I</sub> (Prox<sub>I</sub>Run<sub>4</sub>) after updating τ<sub>I</sub>. This last element sst is useful and important for trapdoors generation and in the procedure to recover the key (that is why we added a signature from the proxy, in order to ensure that the element τ is well formed). Finally Prox<sub>I</sub> forwards c<sub>4</sub>, n<sub>r</sub>, val and TH<sub>5</sub> to the Initiator which performs the same verification as the proxies, checks the ciphertext c<sub>4</sub> and computes PRK<sub>out</sub> with the valid n<sub>r</sub>.

**Session state.** At the end of the protocol, Prox<sub>d</sub> returns :

$$sst_d = \omega_d \| \text{MCS} \| g^x \| g^y \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4 \| M_1 \| m_2 \| m_3 \| H_d \| ni_d \| pid_d \| t_2 \| t_3 \| n_r \| val \| \sigma_d$$

where pid<sub>d</sub> denotes the partner identity of ID<sub>d</sub>. We parse sst<sub>d</sub> as

$$[\omega_d] \| [\text{MCS}] \| [g^x] \| [g^y] \| [\text{TH}_2] \| [\text{TH}_3] \| [\text{TH}_4] \| [\bar{M}_1] \| [\bar{m}_2] \| [\bar{m}_3] \| [\bar{H}_d] \| [\bar{ni}_d] \| [pid_d] \| [t_2] \| [t_3] \| n_r \| [val] \| [\sigma_d]$$

To keep it simple, the dashed boxes are used to check the validity of the session, i.e., verify the identity of the participants and verify that the tools for lawful interception have been well implemented. Next, the black boxes are used to compute g<sup>xy</sup>, and then with the highlighted boxes we compute PRK<sub>out</sub> (this will be explained below).

**Verification of sst.** Before extracting trapdoors or opening the session, the session state sst must be verified. It consists of: ω||MCS||g<sup>x</sup>||g<sup>y</sup>||g<sup>i</sup>||TH<sub>2</sub>||TH<sub>3</sub>||TH<sub>4</sub>||M<sub>1</sub>||m<sub>2</sub>||m<sub>3</sub>||H||ni||pid||t<sub>2</sub>||t<sub>3</sub>||n<sub>r</sub>||val||σ. The plaintext messages M<sub>1</sub>, m<sub>2</sub> and m<sub>3</sub> allow for the verification of the transcript hashes and the authentication of both parties (through signatures of knowledge). The verification algorithm also extracts, from ω the public keys of the authorities, for which the proofs of knowledge of the discrete logarithm must be verified. Subsequently the signature of knowledge is verified with respect to both the signed message and to the equality of the discrete logarithm used to compute H. In this version of the protocol, since both endpoints use signature authentication, the verification algorithm obtains, from m<sub>2</sub>, m<sub>3</sub>, t<sub>2</sub> and t<sub>3</sub> all the necessary information to verify the signatures σ<sub>2</sub> and σ<sub>3</sub>. Finally, parsing sst as τ||σ, the signature σ generated by the proxy is verified with respect to the message τ.

<footnote n="7">⁷Note that this problem appears in [9], but does not impact the security properties proved or the proposed conditions of use presented in the paper.</footnote>

<footnote n="8">⁸This fourth additional message could be seen as a reduction of the lightweight nature of the protocol. But it remains reasonable, and we except that with this addition, we will be able to prove soon another security property: explicit authentication.</footnote>
PreComp_I(M_I)

1: Parse $M_I$ as $((\Lambda_j^I)^{n_I}_{j=1} || \text{ID}_I)$

2: $\forall j \in [1, n_I]$ if NIPoKver($\Lambda_j^I$.pk, $\Lambda_j^I$.ni) $\neq$ 1

3: **then return** $\perp$

4: $h_I \leftarrow \prod_{j=1}^{n_I} \Lambda_j^I$.pk, $\omega_I \leftarrow (\Lambda_j^I)^{n_I}_{j=1} || \text{ID}_I$

5: Agreement on secret key $\text{pcsk}_{I, \text{Prox}_I}$

6: **return** $(h_I, \omega_I)$

Prox_IRun1(ID_I, M_1)

1: Parse $M_1$ as $(\text{MCS} \| g^x \| C_I \| \text{EAD}_1)$

2: $\tau_I \leftarrow \omega_I \| \text{MCS} \| g^x$ // Initialize $\tau_I$

3: **return** $M_1$

Prox_IRun2(ID_I, M_2)

1: Parse $M_2$ as $(g^y \| c_2)$

2: $\tau_I \leftarrow \tau_I \| g^y$ // Update $\tau_I$

3: **return** $M_2$

Prox_IRun3(ID_I, M_3)

1: Parse $M_3$ as $(c_3 || H_I || \text{ni}_I || S_I)$

// Decipher $S_I$ and verify transcript hashes

2: $K_I \leftarrow \text{Dec}''(\text{pcsk}_{I, \text{Prox}_I}, S_I)$, parse $K_I$ as $(\text{sk}_2 || \text{sk}_3 || \text{IV}_3 || t_2)$

3: $m_2 \leftarrow \text{Dec}(\text{sk}_2, c_2)$, get $\text{ID}_R$, $\sigma_2$ from $m_2$

4: $\text{TH}_2 \leftarrow \mathcal{H}(g^y, \mathcal{H}(M_1))$, $\text{TH}_3 \leftarrow \mathcal{H}(\text{TH}_2, m_2, \text{ID}_R)$

5: $\text{ad}_3 \leftarrow (l_{\text{ead}} || $\text{"} || \text{TH}_3)$, $m_3 \leftarrow \text{Dec}'(\text{sk}_3, \text{IV}_3, \text{ad}_3, c_3)$

6: $\text{TH}_4 \leftarrow \mathcal{H}(\text{TH}_3, m_3, \text{ID}_I)$

// Verify SoK and HMAC, and update $\tau_I$

7: **if** DS.Verif(spk_R, $(l_{\text{sig}} || \text{CTX}_2 || t_2)$, $\sigma_2$) $\neq$ 1

8: **then return** $\perp$

9: **if** SoKver($\omega_I || \text{ID}_R || \text{TH}_2 || \text{TH}_3 || \text{TH}_4$, $\text{stm}_I$, $\text{ni}_I$) $\neq$ 1

10: **then return** $\perp$

11: **accepted** $\leftarrow$ 1

12: $\tau_I \leftarrow \tau_I || \text{TH}_2 || \text{TH}_3 || \text{TH}_4 || M_1 || m_2 || m_3 || H_I || \text{ni}_I || \text{ID}_R || t_2$

13: **return** $M_3' \leftarrow c_3$

Prox_IRun4(ID_I, M_4')

1: Parse $M_4'$ as $(c_4 || n_r || \text{val} || \text{TH}_5 || t_3)$

2: **if** $M_4' = \perp$ **then return** $\perp$

3: **if** $\text{TH}_5 = \mathcal{H}(\text{TH}_4, \text{val}, n_r)$ **then return** $\perp$
**if** DS.Verif(spk_I, $(l_{\text{sig}} || \text{CTX}_3 || t_3)$, $\sigma_3$) $\neq$ 1

4: **then return** $\perp$

// Update and sign $\tau_I$

5: $\tau_I \leftarrow \tau_I || t_3 || n_r || \text{val}$, $\sigma_I \leftarrow \text{DS.Sign}(\text{ssk}_{\text{Prox}_I}, \tau_I)$

6: **terminated** $\leftarrow$ 1, $\text{sst}_I \leftarrow \tau_I || \sigma_I$

7: **return** $M_4'' \leftarrow (c_4 || n_r || \text{val} || \text{TH}_5)$

PreComp_R(M_R)

1: Parse $M_R$ as $((\Lambda_j^R)^{n_R}_{j=1} || \text{ID}_R)$

2: $\forall j \in [1, n_R]$ if NIPoKver($\Lambda_j^R$.pk, $\Lambda_j^R$.ni) $\neq$ 1

3: **then return** $\perp$

4: $h_R \leftarrow \prod_{j=1}^{n_R} \Lambda_j^R$.pk, $\omega_R \leftarrow (\Lambda_j^R)^{n_R}_{j=1} || \text{ID}_R$

5: Agreement on secret key $\text{pcsk}_{R, \text{Prox}_R}$

6: **return** $(h_R, \omega_R)$

Prox_RRun1(ID_R, M_1)

1: Parse $M_1$ as $(\text{MCS} \| g^x \| C_I \| \text{EAD}_1)$

2: $\tau_R \leftarrow \omega_R \| \text{MCS} \| g^x$ // Initialize $\tau_R$

3: **return** $M_1$

Prox_RRun2(ID_R, M_2)

1: Parse $M_2$ as $(g^y \| c_2)$

2: $\tau_R \leftarrow \tau_R \| g^y$ // Update $\tau_R$

3: **return** $M_2$

Prox_RRun3(ID_R, M_4)

1: Parse $M_4$ as $(c_4 || n_r || \text{val} || \text{TH}_5 || H_R || \text{ni}_R || S_R)$

2: **if** $M_4 = \perp$ **then return** $\perp$
// Decipher $S_R$ and verify transcript hashes

3: $K_R \leftarrow \text{Dec}''(\text{pcsk}_{R, \text{Prox}_R}, S_R)$

4: Parse $K_R$ as $(\text{sk}_2 || \text{sk}_3 || \text{IV}_3 || t_2 || t_3)$

5: $m_2 \leftarrow \text{Dec}(\text{sk}_2, c_2)$, $\text{TH}_2 \leftarrow \mathcal{H}(g^y, \mathcal{H}(M_1))$

6: $\text{TH}_3 \leftarrow \mathcal{H}(\text{TH}_2, m_2, \text{ID}_R)$, $\text{ad}_3 \leftarrow (l_{\text{ead}} || $\text{"} || \text{TH}_3)$

7: $m_3 \leftarrow \text{Dec}'(\text{sk}_3, \text{IV}_3, \text{ad}_3, c_3)$, get $\text{ID}_I$, $\sigma_3$ from $m_3$

8: $\text{TH}_4 \leftarrow \mathcal{H}(\text{TH}_3, m_3, \text{ID}_I)$
// Verify SoK and HMACs, update and sign $\tau_R$

9: **if** DS.Verif(spk_R, $(l_{\text{sig}} || \text{CTX}_2 || t_2)$, $\sigma_2$) $\neq$ 1

10: **then return** $\perp$

11: **if** DS.Verif(spk_I, $(l_{\text{sig}} || \text{CTX}_3 || t_3)$, $\sigma_3$) $\neq$ 1

12: **then return** $\perp$

13: **if** SoKver($\omega_R || \text{ID}_I || \text{TH}_2 || \text{TH}_3 || \text{TH}_4$, $\text{stm}_R$, $\text{ni}_R$) $\neq$ 1

14: **then return** $\perp$

15: **if** $\text{TH}_5 \neq \mathcal{H}(\text{TH}_4, \text{val}, n_r)$ **then return** $\perp$

16: **accepted** $\leftarrow$ 1

17: $\tau_R \leftarrow \tau_R || \text{TH}_2 || \text{TH}_3 || \text{TH}_4 || M_1 || m_2 || m_3 || H_R || \text{ni}_R || \text{ID}_I || t_2 || t_3 || n_r || \text{val}$

18: $\sigma_R \leftarrow \text{DS.Sign}(\text{ssk}_{\text{Prox}_R}, \tau_R)$

19: **terminated** $\leftarrow$ 1, $\text{sst}_R \leftarrow \tau_R || \sigma_R$

20: **return** $M_4' \leftarrow (c_4 || n_r || \text{val} || \text{TH}_5 || t_3)$

<caption>FIGURE 9 – Lawful Interception in the EDHOC protocol with ID = 0. The notation MCS denotes the method (here 0 = **Sign-sign**) and the cipher suite that the Initiator wants to use.</caption>
InitRun1(ID₁)
1: (x ← $\mathbb{Z}_p^*$, $g^x$), C₁ ← $\{0, 1\}^{l_C}$
2: return M₁ ← (MCS $\|g^x\|C_1$ EAD₁)
InitRun2(ID₁, M₂)
1: Parse M₂ as $(g^y \|c_2)$, $g^{xy} \leftarrow (g^y)^x$
   // Compute sk₂ and decrypt c₂
2: TH₂ ← $\mathcal{H}(g^y, \mathcal{H}(M_1))$
3: PRK₂e ← HKDF_Extract(TH₂, $g^{xy}$)
4: sk₂ ← HKDF_Expand(PRK₂e, $\mathbf{0} \|TH_2\|l_2$, $l_2$)
5: m₂ ← Dec(sk₂, $c_2$), parse m₂ as (C_R $\|ID_R\|\sigma_2$ EAD₂)
6: CTX₂ ← (C_R $\|ID_R\|TH_2$ EAD₂), sid ← (C₁, C_R, $g^x$, $g^y$)
7: t'₂ ← HKDF_Expand(PRK₂e, $\mathbf{2} \|CTX_2\|l_{mac}$, $l_{mac}$)
   // Verify Responder authentication
8: if DS.Verif(spkR, $(l_{sig} \|CTX_2\|t'₂)$, $\sigma_2$) ≠ 1 then
   return ⊥
9: accepted ← 1
   // Compute key-schedule for 3rd message
10: TH₃ ← $\mathcal{H}(TH_2, m_2, ID_R)$, CTX₃ ← $(ID_1 \|TH₃\|EAD₃)$
11: sk₃ ← HKDF_Expand(PRK₂e, $\mathbf{3} \|TH₃\|l_{key}$, $l_{key}$)
12: IV₃ ← HKDF_Expand(PRK₂e, $\mathbf{4} \|TH₃\|l_{iv}$, $l_{iv}$)
13: ad₃ ← $(l_{ead} \|" \|TH₃)$
14: t₃ ← HKDF_Expand(PRK₂e, $\mathbf{6} \|CTX₃\|l_{mac}$, $l_{mac}$)
   // Authenticate (signature in method 0)
15: $\sigma_3 \leftarrow DS.Sign(sskR, (l_{sig} \|CTX₃\|t₃))$
   // Ensure LI-compliance and assemble M₃
16: m₃ ← $(ID_1 \|\sigma_3\|EAD₃)$, $c_3 \leftarrow Enc'(sk₃, IV₃, ad₃, m₃)$
17: TH₄ ← $\mathcal{H}(TH₃, m₃, ID_1)$
18: $\Gamma_1 \leftarrow (h_1 g^y)^x$
19: $\text{stm}_1 \leftarrow [X = g^x \wedge H_1 = (h_1 g^y)^x]$ 
20: $\Gamma_2 \leftarrow \text{SoK}_{\omega_R \|ID_R\|TH_2 \|TH_3\|TH_4} \{y : \text{stm}_1\}$
21: $K_1 \leftarrow (sk_2 \|sk_3\|IV_3 \|t_2)$, $S_1 \leftarrow \text{Enc}''(\text{pcsk}_{I, \text{Prox}_1}, K_1)$
22: return M₃ ← $(c_3 \|H_1 \|\Gamma_1 \|S_1)$
InitRun3(ID₁, $M''_4$)
1: Parse $M''_4$ as $(c_4 \|n_r \|\text{val} \|TH_5)$
2: if $c_4 = \bot$ then return $\bot$
3: if TH₅ ≠ $\mathcal{H}(TH₄, \text{val}, n_r)$ then return $\bot$
4: sk₄ ← HKDF_Expand(PRK₂e, $\mathbf{8} \|TH₄\|l_{key}$, $l_{key}$)
5: IV₄ ← HKDF_Expand(PRK₂e, $\mathbf{9} \|TH₄\|l_{key}$, $l_{key}$)
6: ad₄ ← $(l_{ead}, \|" \|TH₄)$, $m_4 \leftarrow \text{Dec}'(sk₄, IV₄, ad₄, c₄)$
7: Parse $m_4$ as EAD₄, if $m_4 = \bot$ then return $\bot$
8: PRK_out ← HKDF_Expand(PRK₂e, $\mathbf{7} \|TH₄\|\bar{\lfloor n_r \rfloor} \|l_{hash}\|l_{hash}$)
9: terminated ← 1

RespRun1(IDR, M₁)
1: (y ← $\mathbb{Z}_p^*$, $g^y$), C_R ← $\{0, 1\}^{l_C}$
2: Parse M₁ as (MCS $\|g^x\|C_1$ EAD₁)
   // Compute key-schedule for 2nd message
3: $g^{xy} \leftarrow (g^x)^y$, sid ← (C₁, C_R, $g^x$, $g^y$)
4: TH₂ ← $\mathcal{H}(g^y, \mathcal{H}(M_1))$
5: PRK₂e ← HKDF_Extract(TH₂, $g^{xy}$)
6: sk₂ ← HKDF_Expand(PRK₂e, $\mathbf{0} \|TH_2\|l_2$, $l_2$)
7: CTX₂ ← (C_R $\|ID_R\|TH_2$ EAD₂)
8: $t_2 \leftarrow$ HKDF_Expand(PRK₂e, $\mathbf{2} \|CTX_2\|l_{mac}$, $l_{mac}$)
   // Authenticate (signature in method 0)
9: $\sigma_2 \leftarrow$ DS.Sign(sskR, $(l_{sig} \|CTX_2\|t_2))$
   // Assemble M₂
10: $m_2 \leftarrow$ (C_R $\|ID_R\|\sigma_2$ EAD₂), $c_2 \leftarrow$ Enc(sk₂, $m_2$)
11: return M₂ ← $(g^y \|c_2)$
RespRun2(IDR, $M'_3$)
1: Parse $M'_3$ as $c_3$, TH₃ ← $\mathcal{H}(TH_2, m_2, ID_R)$
   // Compute sk₃ and decrypt c₃
2: sk₃ ← HKDF_Expand(PRK₂e, $\mathbf{3} \|TH₃\|l_{key}$, $l_{key}$)
3: IV₃ ← HKDF_Expand(PRK₂e, $\mathbf{4} \|TH₃\|l_{iv}$, $l_{iv}$)
4: ad₃ ← $(l_{ead} \|" \|TH₃)$, $m_3 \leftarrow \text{Dec}'(sk₃, IV₃, ad₃, $c_3$)
5: Parse $m_3$ as $(ID_1 \|\sigma_3\|EAD₃)$, CTX₃ ← $(ID_1 \|TH₃\|EAD₃)$
6: $t'_3 \leftarrow$ HKDF_Expand(PRK₂e, $\mathbf{6} \|CTX₃\|l_{mac}$, $l_{mac}$)
   // Verify Initiator authentication
7: if DS.Verif(spkI, $(l_{sig} \|CTX₃\|t'_3)$, $\sigma_3$) ≠ 1 then
   return $\bot$
8: accepted ← 1
   // Compute key-schedule for 4th message
9: TH₄ ← $\mathcal{H}(TH₃, m₃, ID_1)$
10: sk₄ ← HKDF_Expand(PRK₂e, $\mathbf{8} \|TH₄\|l_{key}$, $l_{key}$)
11: IV₄ ← HKDF_Expand(PRK₂e, $\mathbf{9} \|TH₄\|l_{key}$, $l_{key}$)
12: ad₄ ← $(l_{ead}, \|" \|TH₄)$
   // Ensure LI-compliance and assemble M₄
13: $\Gamma_R \leftarrow$ $(h_R g^x)^y$
14: $\text{stm}_R \leftarrow [Y = g^y \wedge H_R = (h_R g^x)^y]$ 
15: $\Gamma_1 \leftarrow \text{SoK}_{\omega_R \|ID_1\|TH_2 \|TH_3\|TH_4} \{y : \text{stm}_R\}$
16: $K_R \leftarrow$ (sk₂ $\|sk_3\|IV_3 \|t_2\|t_3)$, $S_R \leftarrow \text{Enc}''(\text{pcsk}_{R, \text{Prox}_R}, K_R)$
17: $m_4 \leftarrow$ EAD₄ $\|n_r)$, $c_4 \leftarrow$ Enc'(sk₄, IV₄, ad₄, $m_4$)
18: $n_r \leftarrow \{0, 1\}^{l_{rand}}$, val $\leftarrow \mathcal{H}(g^{xy}, " \|TH_4)$
19: PRK_out ← HKDF_Expand(PRK₂e, $\mathbf{7} \|TH₄\|\bar{\lfloor n_r \rfloor} \|l_{hash}\|l_{hash}$)
20: terminated ← 1, TH₅ ← $\mathcal{H}(TH₄, \text{val}, n_r)$
21: return M₄ ← $(c_4 \|n_r \|\text{val} \|TH_5 \|H_R \|ni_R \|S_R)$

<caption>FIGURE 10 – Lawful Interception in the EDHOC protocol with ID = 0 (continued).</caption>
detect it with this verification, and prevent it from communicating in the future. Note that in our situation, such a scenario is unlikely. In our use case within 5G networks, proxies are operators, and it is not in their interest to cheat. Also note that if a proxy cheats in this way, it does not compromise the security properties we are going to establish.

**Correctness of the opening.** Let's quickly detail the previous calculation. For example we have with $d = l$:

$$H_l = (h_l g^y)^x = \left( \prod_{j=1}^{n_l} \Lambda_j^l \cdot pk \right)^x g^{xy} = \left( \prod_{j=1}^{n_l} g^{\Lambda_j^l \cdot SK} \right)^x g^{xy} = \prod_{j=1}^{n_l} g^{\Lambda_j^l \cdot SK} x g^{xy} = \prod_{j=1}^{n_l} g^{x \Lambda_j^l \cdot SK} g^{xy}.$$

And remind that $\Lambda_j^l \cdot td_1 = (g^x)^{\Lambda_j^l \cdot SK} = g^{x \Lambda_j^l \cdot SK}$, so

$$\prod_{j=1}^{n_l} \Lambda_j^l \cdot td_1 = \prod_{j=1}^{n_l} g^{x \Lambda_j^l \cdot SK}.$$

Finally we have as desired:

$$\frac{H_l}{\prod_{j=1}^{n_l} \Lambda_j^l \cdot td_1} = \frac{\prod_{j=1}^{n_l} g^{x \Lambda_j^l \cdot SK} g^{xy}}{\prod_{j=1}^{n_l} g^{x \Lambda_j^l \cdot SK}} = g^{xy}.$$

**Signature of knowledge.** In the protocol, the Initiator and the Responder have to do a signature of knowledge. Formally, it is a proof of knowledge of a discrete logarithm to two different bases, in order to certify that the element $H_d$ is well formed (and note that we previously emphasize the importance and the role of the signed message) [11]. We can proceed as follows, for example with $d = l$.

We consider a hash function $\mathcal{H}_{\text{SoK}} : \mathbb{G} \times \{0, 1\}^* \to \mathbb{Z}_p^*$ (idealize as a random oracle as previously explained), the statement $\text{stm}_l = [X = g^x \wedge H_l = (h_l g^y)^x]$, a (secret) witness $x$ for that statement and a (public) message $m_l = \omega_l \|\text{ID}_R\| \text{TH}_2 \|\text{TH}_3\| \text{TH}_4$. The Initiator then runs the SoK algorithm as follows.

**SoK($m_l, x, \text{stm}_l$):** Pick at random $r_l \leftarrow \mathbb{S}$. Compute $I_1 \leftarrow g^{r_1}$, $I_2 \leftarrow (h_l g^y)^{r_1}$, $\alpha_l \leftarrow \mathcal{H}_{\text{SoK}}(I_1 I_2, m_l)$ and $\beta_l \leftarrow r_l - \alpha_l x \pmod{p}$. Return $n_l = (\alpha_l, \beta_l)$.

Next, when he checks $n_l$, the proxy $\text{Prox}_l$ runs the SoKver algorithm as follows.

**SoKver($m_l, \text{stm}_l, n_l$):** Compute $I'_1 \leftarrow g^{\beta_l} (g^x)^{\alpha_l}$ and $I'_2 \leftarrow (h_l g^y)^{\beta_l} (h_l^x g^{xy})^{\alpha_l} = (h_l g^y)^{\beta_l} (H_l)^{\alpha_l}$. Return 1 if $\alpha_l = \mathcal{H}_{\text{SoK}}(I'_1 I'_2, m_l)$, else return 0.

This signature of knowledge works. Indeed, if $n_l$ is a valid signature we will have:

$$I'_1 = g^{\beta_l} g^{x \alpha_l} = g^{r_1 - \alpha_1 x} g^{\alpha_1 x} = g^{r_1} g^{-\alpha_1 x} g^{\alpha_1 x} = g^{r_1} = I_1$$

and

$$\begin{aligned} I'_2 = (h_l g^y)^{\beta_l} h_l^{x \alpha_l} g^{xy \alpha_l} &= h_l^{\beta_l} g^{y \beta_l} h_l^{x \alpha_l} g^{xy \alpha_l} = h_l^{r_1 - \alpha_1 x} g^{r_1 y - \alpha_1 x y} h_l^{x \alpha_l} g^{xy \alpha_l} \\ &= h_l^{r_1} h_l^{-\alpha_1 x} g^{r_1 y} g^{-\alpha_1 x y} h_l^{x \alpha_l} g^{xy \alpha_l} = h_l^{r_1} g^{r_1 y} = I_2 \end{aligned}$$

On their side, the Responder and his proxy $\text{Prox}_R$ do the same with the statement $\text{stm}_R = [Y = g^y \wedge H_R = (h_R g^x)^y]$, the (private) witness $y$ and the (public) message $m_R = \omega_R \|\text{ID}_R\| \text{TH}_2 \|\text{TH}_3\| \text{TH}_4$.

**Proof of knowledge.** As [9], we use two kinds of proofs of knowledge. The first one is used for authorities' long-term public keys and proves the knowledge of a discrete logarithm. This is done to secure the opening
procedure, ensuring that it happens only when all the authorities imbedded in the session state cooperate to retrieve the session key. The second one is used to prove the knowledge of a discrete logarithm to two different bases. This is done to ensure that when cooperate to open session, no authority cheats and gives a false trapdoor, potentially leading to recovering the wrong session key. The proofs are non-interactive and zero-knowledge, and can be build in a very similar way as the signature of knowledge we presented above.

## 4.4 Handshake - Second case

**Message flow.** We are now interested in the case where the Responder uses Static DIFFIE-HELLMAN as current authentication method (ID = 1). Compared to the previous version changes are minimal. The Initiator (resp. the Responder) only needs to compute the element $H_1^1$ (resp. $H_R^1$) and to add it to his signature of knowledge $ni_I$ (resp. $ni_R$). This element, e.g., on the Initiator's side is composed of the public value $h_I$, the secret ephemeral DIFFIE-HELLMAN element $x$ and the longterm secret key of the Responder $g^r$: $H_1^1 = (h_I g^r)^x$. Similarly $H_R^1 = (h_R g^x)^r$.

On their side, proxies need to store the static DIFFIE-HELLMAN element $g^r$ (this element is useful for the authorities to build an additional trapdoor, as we will see in the TDGen algorithm). Prox$_I$ gets it from the Initiator in message $M_3$ and Prox$_R$ knows it from its database since he knows the Responder. The rest of the protocol does not undergo further modifications. In this case, since $t_2$ is not signed, we do not need to make it verified by proxies and stored in sst, thus we don't need to encrypt it in $S_I$ and $S_R$. This is depicted in FIGURES 11 and 12 below. Moreover, some changes are necessary for the TDGen and the Open algorithms.

**Session state.** In this case, the way we constructed the session state sst is slightly different from the first case. At the end of the protocol, we have

$$ \text{sst}_d = \omega_d \| \text{MCS} \| g^x \| g^y \| g^r \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4 \| M_1 \| m_2 \| m_3 \| \text{H}_d \| H_d^1 \| ni_d \| pid_d \| t_3 \| n_r \| \text{val} \| \sigma_d $$

where pid$_d$ denotes the partner identity of ID$_d$. We parse sst$_d$ as

$$ \text{[\bar{\omega}_d]} \| \text{[MCS]} \| \text{[g}^x \| \text{[g}^y \| \text{[g}^r \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4 \| \text{[M}_1 \| \text{[m}_2 \| \text{[m}_3 \| \text{H}_d \| \text{H}_d^1 \| \text{ni}_d \| \text{pid}_d \| \text{t}_3 \| n_r \| \text{val} \| \text{[\sigma}_d]} $$

As before, the dashed boxes are used to check the validity of the session. Next, the black boxes are used to compute $g^{xy}$ and $g^{rx}$, and then with the highlighted boxes we compute $\text{PRK}_{\text{out}}$.

**Verification of sst.** The verification of sst works in a very similar way as for the previous case. The algorithm Verify just did not check the signature $\sigma_2$.

**Generation of trapdoors and opening the session.** In this situation, we have to make some changes to the TDGen and Open algorithms. For the TDGen algorithm, the inputs remain the same, but it now works as follows.

**TDGen(pp, sst_d, $\Lambda^d$.SK):** Parse sst$_d$ as $\omega_d \| \text{MCS} \| g^x \| g^y \| g^r \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4 \| M_1 \| m_2 \| m_3 \| \text{H}_d \| H_d^1 \| ni_d \| pid_d \| t_3 \| n_r \| \text{val} \| \sigma_d$ (with $d \in \{I, R\}$) and set $A_I \leftarrow g^x$ and $A_R \leftarrow g^y$. Set $\Lambda^d$.td$_1 \leftarrow A_d^{\Lambda^d.SK}$, $\Lambda^d$.td$_2 \leftarrow g^{r\Lambda^d.SK}$ and $\Lambda^d$.td$_0 \leftarrow \text{NIPoK}\{\Lambda^d.SK : \Lambda^d.pk = g^{\Lambda^d.SK} \wedge \Lambda^d.td_1 = A_d^{\Lambda^d.SK} \wedge \Lambda^d.td_2 = g^{r\Lambda^d.SK}\}$. Set $\Lambda^d.td \leftarrow (\Lambda^d.td_0, \Lambda^d.td_1, \Lambda^d.td_2)$. Return $\Lambda^d.td$.

For the Open algorithm, the inputs remain the same, as well as a large part of the algorithm. We simply add some computations.

**Open(pp, sst_d, APK_d, $\mathcal{T}_d$):** Parse sst$_d$ as $\omega_d \| \text{MCS} \| g^x \| g^y \| g^r \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4 \| M_1 \| m_2 \| m_3 \| \text{H}_d \| H_d^1 \| ni_d \| pid_d \| t_3 \| n_r \| \text{val} \| \sigma_d$
PreComp_I(M_I)

1: Parse $M_I$ as $((\Lambda_j^I)^{n_I}_{j=1} || \text{ID}_I)$

2: $\forall j \in [1, n_I]$ if NIPoKver($\Lambda_j^I$.pk, $\Lambda_j^I$.ni) $\neq 1$

3: **then return** $\perp$

4: $h_I \leftarrow \prod_{j=1}^{n_I} \Lambda_j^I \cdot \text{pk}, \omega_I \leftarrow (\Lambda_j^I)^{n_I}_{j=1} || \text{ID}_I$

5: Agreement on secret key $\text{psck}_{I, \text{Prox}_I}$

6: **return** $(h_I, \omega_I)$

Prox_IRun1(ID_I, M_1)

1: Parse $M_1$ as $(\text{MCS} || g^x || C_I || \text{EAD}_1)$

2: $\tau_1 \leftarrow \omega_I || \text{MCS} || g^x$ // Initialize $\tau_1$

3: **return** $M_1$

Prox_IRun2(ID_I, $M_2'$)

1: Parse $M_2$ as $(g^y || c_2)$

2: $\tau_1 \leftarrow \tau_1 || g^y$ // Update $\tau_1$

3: **return** $M_2$

Prox_IRun3(ID_I, $M_3$)

1: Parse $M_3$ as $(c_3 || H_I || H_I^1 || \text{ni}_I || S_I)$

// Decipher $S_I$ and verify transcript hashes

2: $K \leftarrow \text{Dec}''(\text{psck}_{I, \text{Prox}_I}, S_I)$, parse $K$ as $(\text{sk}_2 || \text{sk}_3 || \text{IV}_3)$

3: $m_2 \leftarrow \text{Dec}(\text{sk}_2, c_2)$, get ID_R from $m_2$

4: $\text{TH}_2 \leftarrow \mathcal{H}(g^y, \mathcal{H}(M_1))$, $\text{TH}_3 \leftarrow \mathcal{H}(\text{TH}_2, m_2, \text{ID}_R)$

5: $\text{ad}_3 \leftarrow (l_{\text{ead}} || || \text{TH}_3)$, $m_3 \leftarrow \text{Dec}'(\text{sk}_3, \text{IV}_3, \text{ad}_3, c_3)$

6: $\text{TH}_4 \leftarrow \mathcal{H}(\text{TH}_3, m_3, \text{ID}_I)$, get $g^r$ from ID_R

// Verify SoK and update $\tau_1$

7: **if** $\text{SoKver}(\omega_I || \text{ID}_R || \text{TH}_2 || \text{TH}_3 || \text{TH}_4, \text{stm}_I, \text{ni}_I) \neq 1$

8: **then return** $\perp$

9: **accepted** $\leftarrow 1$

10: $\tau_1 \leftarrow \tau_1 || g^r || \text{TH}_2 || \text{TH}_3 || \text{TH}_4 || M_1 || m_2 || m_3 || H_I || H_I^1 || \text{ni}_I || \text{ID}_R$

11: **return** $M_3' \leftarrow c_3$

Prox_IRun4(ID_I, $M_4'$)

1: Parse $M_4'$ as $(c_4 || n_r || \text{val} || \text{TH}_5 || t_3)$

2: **if** $M_4' = \perp$ **then return** $\perp$

3: **if** $\text{TH}_5 = \mathcal{H}(\text{TH}_4, \text{val}, n_r)$ **then return** $\perp$

4: **if** $\text{DS.Verif}(\text{spk}_I, (l_{\text{sig}} || \text{CTX}_3 || t_3), \sigma_3) \neq 1$

5: **then return** $\perp$

// Update and sign $\tau_1$

6: $\tau_1 \leftarrow \tau_1 || t_3 || n_r || \text{val}, \sigma_I \leftarrow \text{DS.Sign}(\text{ssk}_{\text{Prox}_I}, \tau_I)$

7: **terminated** $\leftarrow 1, \text{sst}_I \leftarrow \tau_I || \sigma_I$

8: **return** $M_4'' \leftarrow (c_4 || n_r || \text{val} || \text{TH}_5)$

PreComp_R(M_R)

1: Parse $M_R$ as $((\Lambda_j^R)^{n_R}_{j=1} || \text{ID}_R)$

2: $\forall j \in [1, n_R]$ if NIPoKver($\Lambda_j^R$.pk, $\Lambda_j^R$.ni) $\neq 1$

3: **then return** $\perp$

4: $h_R \leftarrow \prod_{j=1}^{n_R} \Lambda_j^R \cdot \text{pk}, \omega_R \leftarrow (\Lambda_j^R)^{n_R}_{j=1} || \text{ID}_R$

5: Agreement on secret key $\text{psck}_{R, \text{Prox}_R}$

6: **return** $(h_R, \omega_R)$

Prox_RRun1(ID_R, $M_1$)

1: Parse $M_1$ as $(\text{MCS} || g^x || C_I || \text{EAD}_1)$

2: $\tau_R \leftarrow \omega_R || \text{MCS} || g^x$ // Initialize $\tau_R$

3: **return** $M_1$

Prox_RRun2(ID_R, $M_2$)

1: Parse $M_2$ as $(g^y || c_2)$

2: $\tau_R \leftarrow \tau_R || g^y || g^r$ // Update $\tau_R$

3: **return** $M_2$

Prox_RRun3(ID_R, $M_4$)

1: Parse $M_4$ as $(c_4 || n_r || \text{val} || \text{TH}_5 || H_R || H_R^1 || \text{ni}_R || S_R)$

2: **if** $M_4 = \perp$ **then return** $\perp$

// Decipher $S_R$ and verify transcript hashes

3: $K_R \leftarrow \text{Dec}''(\text{psck}_{R, \text{Prox}_R}, S_R)$, parse $K_R$ as $(\text{sk}_2 || \text{sk}_3 || \text{IV}_3 || t_3)$

4: $m_2 \leftarrow \text{Dec}(\text{sk}_2, c_2)$, $\text{TH}_2 \leftarrow \mathcal{H}(g^y, \mathcal{H}(M_1))$

5: $\text{TH}_3 \leftarrow \mathcal{H}(\text{TH}_2, m_2, \text{ID}_R)$, $\text{ad}_3 \leftarrow (l_{\text{ead}} || || \text{TH}_3)$

6: $m_3 \leftarrow \text{Dec}'(\text{sk}_3, \text{IV}_3, \text{ad}_3, c_3)$, get ID_I, $\sigma_3$ from $m_3$

7: $\text{TH}_4 \leftarrow \mathcal{H}(\text{TH}_3, m_3, \text{ID}_I)$

// Verify SoK and HMACs, update and sign $\tau_R$

8: **if** $\text{DS.Verif}(\text{spk}_I, (l_{\text{sig}} || \text{CTX}_3 || t_3), \sigma_3) \neq 1$

9: **then return** $\perp$

10: **if** $\text{SoKver}(\omega_R || \text{ID}_R || \text{TH}_2 || \text{TH}_3 || \text{TH}_4, \text{stm}_R, \text{ni}_R) \neq 1$

11: **then return** $\perp$

12: **if** $\text{TH}_5 \neq \mathcal{H}(\text{TH}_4, \text{val}, n_r)$ **then return** $\perp$

13: **accepted** $\leftarrow 1$

14: $\tau_R \leftarrow \tau_R || \text{TH}_2 || \text{TH}_3 || \text{TH}_4 || M_1 || m_2 || m_3 || H_R || H_R^1 || \text{ni}_R || \text{ID}_I || t_3 || n_r || \text{val}$

15: $\sigma_R \leftarrow \text{DS.Sign}(\text{ssk}_{\text{Prox}_R}, \tau_R)$

16: **terminated** $\leftarrow 1, \text{sst}_R \leftarrow \tau_R || \sigma_R$

17: **return** $M_4' \leftarrow (c_4 || n_r || \text{val} || \text{TH}_5 || t_3)$

<caption>FIGURE 11 – Lawful Interception in the EDHOC protocol with ID = 1. The notation MCS denotes the method (here 1 = **Sign-static**) and the cipher suite that the Initiator wants to use.</caption>
InitRun1(ID<sub>I</sub>)

1: ($x \leftarrow \mathbb{Z}_p^*$, $g^x$), $C_I \leftarrow \{0, 1\}^{l_C}$

2: **return** $M_1 \leftarrow (\text{MCS} \| g^x \| C_I \| \text{EAD}_1)$

InitRun2(ID<sub>I</sub>, $M_2$)

1: Parse $M_2$ as $(g^y \| c_2)$, $g^{xy} \leftarrow (g^y)^x$

// Compute $sk_2$ and decrypt $c_2$

2: $\text{TH}_2 \leftarrow \mathcal{H}(g^y, \mathcal{H}(M_1))$

3: $\text{PRK}_{2e} \leftarrow \text{HKDF\_Extract}(\text{TH}_2, g^{xy})$

4: $sk_2 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{2e}, 0 \| \text{TH}_2 \| l_2, l_2)$

5: $m_2 \leftarrow \text{Dec}(sk_2, c_2)$, parse $m_2$ as $(C_R \| \text{ID}_R \| t_2 \| \text{EAD}_2)$

6: Get $g^r$ from $\text{ID}_R$, $g^{rx} \leftarrow (g^r)^x$, $\text{sid} \leftarrow (C_I, C_R, g^x, g^y)$

7: $\text{CTX}_2 \leftarrow (C_R \| \text{ID}_R \| \text{TH}_2 \| g^r \| \text{EAD}_2)$

// Verify Responder authentication

8: $\text{salt}_{3e2m} \leftarrow \text{HKDF\_Expand}(\text{PRK}_{2e}, 1 \| \text{TH}_2 \| l_{\text{hash}}, l_{\text{hash}})$

9: $\text{PRK}_{3e2m} \leftarrow \text{HKDF\_Extract}(\text{salt}_{3e2m}, g^{xr})$

10: $t'_2 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 2 \| \text{CTX}_2 \| l_{\text{mac}}, l_{\text{mac}})$

11: **if** $t'_2 \neq t_2$ **then** **return** $\perp$

12: **accepted** $\leftarrow 1$

// Compute key-schedule for 3rd message

13: $\text{TH}_3 \leftarrow \mathcal{H}(\text{TH}_2, m_2, \text{ID}_R)$, $\text{CTX}_3 \leftarrow (\text{ID}_I \| \text{TH}_3 \| \text{EAD}_3)$

14: $sk_3 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 3 \| \text{TH}_3 \| l_{\text{key}}, l_{\text{key}})$

15: $\text{IV}_3 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 4 \| \text{TH}_3 \| l_{\text{iv}}, l_{\text{iv}})$

16: $t_3 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 6 \| \text{CTX}_3 \| l_{\text{mac}}, l_{\text{mac}})$

// Authenticate (signature in method 1)

17: $\sigma_3 \leftarrow \text{DS.Sign}(\text{ssk}_I, (l_{\text{sig}} \| \text{CTX}_3 \| t_3))$

// Ensure LI-compliance and assemble $M_3$

18: $m_3 \leftarrow (\text{ID}_I \| \sigma_3 \| \text{EAD}_3)$, $ad_3 \leftarrow (l_{\text{ead}} \| \| \text{TH}_3)$

19: $c_3 \leftarrow \text{Enc}'(sk_3, \text{IV}_3, ad_3, m_3)$, $\text{TH}_4 \leftarrow \mathcal{H}(\text{TH}_3, m_3, \text{ID}_I)$

20: $\text{H}_I \leftarrow (\text{h}_I g^y)^x, \text{H}_I^1 \leftarrow (\text{h}_I g^r)^x$

21: $\text{stm}_I \leftarrow [X = g^x \wedge \text{H}_I = (\text{h}_I g^y)^x \wedge \text{H}_I^1 = (\text{h}_I g^r)^x]$

22: $\text{ni}_I \leftarrow \text{SoK}_{\omega_I \| \text{ID}_I \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4} \{x : \text{stm}_I\}$

23: $\text{K}_I \leftarrow (\text{sk}_2 \| \text{sk}_3 \| \text{IV}_3)$, $S_I \leftarrow \text{Enc}''(\text{pcsk}_{I, \text{Prox}_I}, \text{K}_I)$

24: **return** $M_3 \leftarrow (c_3 \| \text{H}_I \| \text{H}_I^1 \| \text{ni}_I \| S_I)$

InitRun3(ID<sub>I</sub>, $M_4''$)

1: Parse $M_4''$ as $(c_4 \| n_r \| \text{val} \| \text{TH}_5)$

2: **if** $c_4 = \perp$ **then** **return** $\perp$

3: **if** $\text{TH}_5 \neq \mathcal{H}(\text{TH}_4, \text{val}, n_r)$ **then** **return** $\perp$

4: $sk_4 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 8 \| \text{TH}_4 \| l_{\text{key}}, l_{\text{key}})$

5: $\text{IV}_4 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 9 \| \text{TH}_4 \| l_{\text{key}}, l_{\text{key}})$

6: $ad_4 \leftarrow (l_{\text{ead}}, \| \| \text{TH}_4)$, $m_4 \leftarrow \text{Dec}'(sk_4, \text{IV}_4, ad_4, c_4)$

7: Parse $m_4$ as EAD<sub>4</sub>, **if** $m_4 = \perp$ **then** **return** $\perp$

8: $\text{PRK}_{\text{out}} \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 7 \| \text{TH}_4 \| \lceil \bar{n}_r \rceil \| l_{\text{hash}}, l_{\text{hash}})$

9: **terminated** $\leftarrow 1$

RespRun1(ID<sub>R</sub>, $M_1$)

1: ($y \leftarrow \mathbb{Z}_p^*$, $g^y$), $C_R \leftarrow \{0, 1\}^{l_C}$

2: Parse $M_1$ as $(\text{MCS} \| g^x \| C_I \| \text{EAD}_1)$

// Compute key-schedule for 2nd message

3: $g^{xy} \leftarrow (g^x)^y, g^{xr} \leftarrow (g^x)^r$, $\text{sid} \leftarrow (C_I, C_R, g^x, g^y)$

4: $\text{TH}_2 \leftarrow \mathcal{H}(g^y, \mathcal{H}(m_1))$

5: $\text{PRK}_{2e} \leftarrow \text{HKDF\_Extract}(\text{TH}_2, g^{xy})$

6: $sk_2 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{2e}, 0 \| \text{TH}_2 \| l_2, l_2)$

7: $\text{salt}_{3e2m} \leftarrow \text{HKDF\_Expand}(\text{PRK}_{2e}, 1 \| \text{TH}_2 \| l_{\text{hash}}, l_{\text{hash}})$

8: $\text{PRK}_{3e2m} \leftarrow \text{HKDF\_Extract}(\text{salt}_{3e2m}, g^{xr})$

9: $\text{CTX}_2 \leftarrow (C_R \| \text{ID}_R \| \text{TH}_2 \| g^r \| \text{EAD}_2)$

// Authenticate (static DH in method 1)

10: $t_2 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 2 \| \text{CTX}_2 \| l_{\text{mac}}, l_{\text{mac}})$

// Assemble $M_2$

11: $m_2 \leftarrow (C_R \| \text{ID}_R \| t_2 \| \text{EAD}_2)$, $c_2 \leftarrow \text{Enc}(sk_2, m_2)$

12: **return** $M_2 \leftarrow (g^y \| c_2)$

RespRun2(ID<sub>R</sub>, $M_3'$)

1: Parse $M_3'$ as $c_3$, $\text{TH}_3 \leftarrow \mathcal{H}(\text{TH}_2, m_2, \text{ID}_R)$

// Compute $sk_3$ and decrypt $c_3$

2: $sk_3 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 3 \| \text{TH}_3 \| l_{\text{key}}, l_{\text{key}})$

3: $\text{IV}_3 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 4 \| \text{TH}_3 \| l_{\text{iv}}, l_{\text{iv}})$

4: $ad_3 \leftarrow (l_{\text{ead}} \| \| \text{TH}_3)$, $m_3 \leftarrow \text{Dec}'(sk_3, \text{IV}_3, ad_3, c_3)$

5: Parse $m_3$ as $(\text{ID}_I \| \sigma_3 \| \text{EAD}_3)$, $\text{CTX}_3 \leftarrow (\text{ID}_I \| \text{TH}_3 \| \text{EAD}_3)$

6: $t'_3 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 6 \| \text{CTX}_3 \| l_{\text{mac}}, l_{\text{mac}})$

// Verify Initiator authentication

7: **if** $\text{DS.Verif}(\text{spk}_I, (l_{\text{sig}} \| \text{CTX}_3 \| t'_3), \sigma_3) \neq 1$ **then** **return** $\perp$

8: **accepted** $\leftarrow 1$

// Compute key-schedule for 4th message

9: $\text{TH}_4 \leftarrow \mathcal{H}(\text{TH}_3, m_3, \text{ID}_I)$

10: $sk_4 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 8 \| \text{TH}_4 \| l_{\text{key}}, l_{\text{key}})$

11: $\text{IV}_4 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 9 \| \text{TH}_4 \| l_{\text{key}}, l_{\text{key}})$

12: $ad_4 \leftarrow (l_{\text{ead}}, \| \| \text{TH}_4)$

// Ensure LI-compliance and assemble $M_4$

13: $\text{H}_R \leftarrow (\text{h}_R g^x)^y, \text{H}_R^1 \leftarrow (\text{h}_R g^x)^r$

14: $\text{stm}_R \leftarrow [Y = g^y \wedge \text{H}_R = (\text{h}_R g^x)^y \wedge Y_1 = g^r \wedge \text{H}_R^1 = (\text{h}_R g^x)^r]$

15: $\text{ni}_R \leftarrow \text{SoK}_{\omega_R \| \text{ID}_I \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4} \{(y, r) : \text{stm}_R\}$

16: $\text{K}_R \leftarrow (\text{sk}_2 \| \text{sk}_3 \| \text{IV}_3 \| t_3)$, $S_R \leftarrow \text{Enc}''(\text{pcsk}_{R, \text{Prox}_R}, \text{K}_R)$

17: $m_4 \leftarrow (\text{EAD}_4 \| n_r)$, $c_4 \leftarrow \text{Enc}'(sk_4, \text{IV}_4, ad_4, m_4)$

18: $n_r \leftarrow \{0, 1\}^{l_{\text{rand}}}$, $\text{val} \leftarrow \mathcal{H}(g^{xy}, \dots, n_r)$

19: $\text{PRK}_{\text{out}} \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 7 \| \text{TH}_4 \| \lceil \bar{n}_r \rceil \| l_{\text{hash}}, l_{\text{hash}})$

20: **terminated** $\leftarrow 1$, $\text{TH}_5 \leftarrow \mathcal{H}(\text{TH}_4, \text{val}, n_r)$

21: **return** $M_4 \leftarrow (c_4 \| n_r \| \text{val} \| \text{TH}_5 \| \text{H}_R \| \text{H}_R^1 \| \text{ni}_R \| S_R)$

<caption>FIGURE 12 – Lawful Interception in the EDHOC protocol with ID = 1 (continued).</caption>
**Proof of knowledge.** The proofs of knowledge for authorities' long-term public keys remains the same in this case. Only the ones for trapdoors are slightly modified, as we need to prove the discrete logarithm equality in another base. But this can be done in a similar way as the previous ones.

## 4.5 Handshake - Third case

**Message flow.** We are now interested in the case where the Initiator uses Static DIFFIE-HELLMAN as current authentication method and the Responder a signature (ID = 2). For this version, as well as the last one, the changes compare to the first case, are minimal. In this version, both the Initiator and the Responder need to compute the additional element $H_1^1$ or $H_R^1$. On the Initiator's side for example, $H_1^1$ is formed of $h_1$, the longterm secret $i$ and the shared ephemeral DIFFIE-HELLMAN element $g^i$: $H_1^1 = (h_1 g^i)^i$. Similarly, $H_R^1 = (h_R g^i)^i$. The rest of the message flow remains the same.

Again on their side, proxies store the element $g^i$ (for the same reason as in the previous case), Prox_R obtaining it with the fourth message of the Responder and Prox_I from its database since he knows the Initiator. In this case, since $t_3$ is not signed, we do not need to make it verified by proxies and stored in sst, thus we don't need to encrypt it in $S_R$ and send it to Prox_I. This is depicted in FIGURES 13 and 14 below. Moreover, few changes are necessary for the TDGen and the Open algorithms as it is detailed after.

**Session state.** The way we constructed the session state sst in this case is similar to the second case. At the end of the protocol, we have

$$sst_d = \omega_d \| \text{MCS} \| g^x \| g^y \| g^i \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4 \| M_1 \| m_2 \| m_3 \| H_d \| H_d^1 \| ni_d \| pid_d \| t_2 \| n_r \| val \| \sigma_d$$

where pid_d denotes the partner identity of ID_d. So we parse sst_d as

$$[\bar{\omega}_d] \| [\text{MCS}] \| [g^x] \| [g^y] \| [g^i] \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4 \| [\bar{M}_1] \| [\bar{m}_2] \| [\bar{m}_3] \| \text{H}_d \| [\bar{H}_d^1] \| [\bar{ni}_d] \| [\bar{pid}_d] \| [\bar{t}_2] \| n_r \| [\bar{val}] \| [\bar{\sigma}_d]$$

As usual, the dashed boxes are used to check the validity of the session. Next, the black boxes are used to compute $g^{xy}$ and $g^{iy}$, and then with the highlighted boxes we compute PRK\_out.

**Verification of sst.** The verification of sst works in a very similar way as for the first case. The algorithm Verify just did not check the signature $\sigma_3$ in this situation.

**Generation of trapdoors and opening the session.** We discuss here the changes that must be done to the TDGen and Open algorithms.

For the TDGen algorithm, the inputs remain the same, as well as the entire protocol. We just replace the element $g^r$ by $g^i$ in the computation of $\Lambda$.td_2 (and so in the statement for the NIPoK ($\Lambda$.td_0)).

For the Open algorithm, the inputs remain the same, as well as a large part of the algorithm. The only modification appears in the computation of $g^{iy}$. In this case, to retrieve $g^{iy}$, it is the Initiator authorities which use the trapdoors $\Lambda_j^1$.td_2$, and the Responder authorities use only the trapdoors $\Lambda_j^R$.td_1$.

**Signature of knowledge.** In this case, in terms of signature, compared to the second case, the role of the Initiator and the Responder are reversed, i.e., the Responder signs with the SoK algorithm that was used by the Initiator, and the latter signs with the SoK algorithm that was used by the Responder.

**Proof of knowledge.** The same remark as the previous case applies here. As we explained before, in the case ID = 1, for the case ID = 2, only one set of authorities needs of the two trapdoors to retrieve the key. For a practical implementation, in this situation, the set which only needs one trapdoor can compute a simpler proof of knowledge, by not including the second trapdoor. Again for readability, we let it as it is.
PreComp_I(M_I)

1: Parse $M_I$ as $((\Lambda_j^I)^{n_I}_{j=1} || \text{ID}_I)$

2: $\forall j \in [1, n_I]$ if NIPoKver($\Lambda_j^I$.pk, $\Lambda_j^I$.ni) $\neq$ 1

3: **then return** $\perp$

4: $h_I \leftarrow \prod_{j=1}^{n_I} \Lambda_j^I$.pk, $\omega_I \leftarrow (\Lambda_j^I)^{n_I}_{j=1} || \text{ID}_I$

5: Agreement on secret key pcsk_{I,Prox_I}

6: **return** $(h_I, \omega_I)$

Prox_IRun1(ID_I, M_1)

1: Parse $M_1$ as $(\text{MCS} || g^x || C_I || \text{EAD}_1)$

2: $\tau_I \leftarrow \omega_I || \text{MCS} || g^x$ // Initialize $\tau_I$

3: **return** $M_1$

Prox_IRun2(ID_I, M_2)

1: Parse $M_2$ as $(g^y || c_2)$

2: $\tau_I \leftarrow \tau_I || g^y$ // Update $\tau_I$

3: **return** $M_2$

Prox_IRun3(ID_I, M_3)

1: Parse $M_3$ as $(c_3 || H_I || H_I^1 || \text{ni}_I || S_I)$

// Decipher $S_I$ and verify transcript hashes

2: $K_I \leftarrow \text{Dec}''(\text{pcsk}_{I,\text{Prox}_I}, S_I)$, parse $K_I$ as $(\text{sk}_2 || \text{sk}_3 || \text{IV}_3 || t_2)$

3: $m_2 \leftarrow \text{Dec}(\text{sk}_2, c_2)$, get $\text{ID}_R$, $\sigma_2$ from $m_2$

4: $\text{TH}_2 \leftarrow \mathcal{H}(g^y, \mathcal{H}(M_1))$, $\text{TH}_3 \leftarrow \mathcal{H}(\text{TH}_2, m_2, \text{ID}_R)$

5: $\text{ad}_3 \leftarrow (l_{\text{ead}} || $\text{"} || \text{TH}_3)$, $m_3 \leftarrow \text{Dec}'(\text{sk}_3, \text{IV}_3, \text{ad}_3, c_3)$

6: $\text{TH}_4 \leftarrow \mathcal{H}(\text{TH}_3, m_3, \text{ID}_I)$

// Verify SoK and HMAC, and update $\tau_I$

7: **if** DS.Verif(spk_R, $(l_{\text{sig}} || \text{CTX}_2 || t_2)$, $\sigma_2$) $\neq$ 1

8: **then return** $\perp$

9: **if** SoKver($\omega_I || \text{ID}_R || \text{TH}_2 || \text{TH}_3 || \text{TH}_4$, $\text{stm}_I$, $\text{ni}_I$) $\neq$ 1

10: **then return** $\perp$

11: **accepted** $\leftarrow$ 1

12: $\tau_I \leftarrow \tau_I || g^i || \text{TH}_2 || \text{TH}_3 || \text{TH}_4 || M_1 || m_2 || m_3 || H_I || H_I^1 || \text{ni}_I || \text{ID}_R || t_2$

13: **return** $M_3' \leftarrow c_3$

Prox_IRun4(ID_I, $M_4'$)

1: Parse $M_4'$ as $(c_4 || n_r || \text{val} || \text{TH}_5)$

2: **if** $M_4' = \perp$ **then return** $\perp$

3: **if** $\text{TH}_5 = \mathcal{H}(\text{TH}_4, \text{val}, n_r)$ **then return** $\perp$

// Update and sign $\tau_I$

4: $\tau_I \leftarrow \tau_I || n_r || \text{val}, \sigma_I \leftarrow \text{DS SIGN}(\text{ssk}_{\text{Prox}_I}, \tau_I)$

5: **terminated** $\leftarrow$ 1, $\text{sst}_I \leftarrow \tau_R || \sigma_I$

6: **return** $M_4' \leftarrow M_4'$

PreComp_R(M_R)

1: Parse $M_R$ as $((\Lambda_j^R)^{n_R}_{j=1} || \text{ID}_R)$

2: $\forall j \in [1, n_R]$ if NIPoKver($\Lambda_j^R$.pk, $\Lambda_j^R$.ni) $\neq$ 1

3: **then return** $\perp$

4: $h_R \leftarrow \prod_{j=1}^{n_R} \Lambda_j^R$.pk, $\omega_R \leftarrow (\Lambda_j^R)^{n_R}_{j=1} || \text{ID}_R$

5: Agreement on secret key pcsk_{R,Prox_R}

6: **return** $(h_R, \omega_R)$

Prox_RRun1(ID_R, $M_1$)

1: Parse $M_1$ as $(\text{MCS} || g^x || C_I || \text{EAD}_1)$

2: $\tau_R \leftarrow \omega_R || \text{MCS} || g^x$ // Initialize $\tau_R$

3: **return** $M_1$

Prox_RRun2(ID_R, $M_2$)

1: Parse $M_2$ as $(g^y || c_2)$

2: $\tau_R \leftarrow \tau_R || g^y$ // Update $\tau_R$

3: **return** $M_2$

Prox_RRun3(ID_R, $M_4$)

1: Parse $M_4$ as $(c_4 || n_r || \text{val} || \text{TH}_5 || H_R || H_R^1 || \text{ni}_R || S_R)$

2: **if** $M_4 = \perp$ **then return** $\perp$

// Decipher $S_R$ and verify transcript hashes

3: $K_R \leftarrow \text{Dec}''(\text{pcsk}_{R,\text{Prox}_R}, S_R)$, parse $K_R$ as $(\text{sk}_2 || \text{sk}_3 || \text{IV}_3 || t_2)$

4: $m_2 \leftarrow \text{Dec}(\text{sk}_2, c_2)$, $\text{TH}_2 \leftarrow \mathcal{H}(g^y, \mathcal{H}(M_1))$

5: $\text{TH}_3 \leftarrow \mathcal{H}(\text{TH}_2, m_2, \text{ID}_R)$, $\text{ad}_3 \leftarrow (l_{\text{ead}} || $\text{"} || \text{TH}_3)$

6: $m_3 \leftarrow \text{Dec}'(\text{sk}_3, \text{IV}_3, \text{ad}_3, c_3)$, get $\text{ID}_I$ from $m_3$

7: $\text{TH}_4 \leftarrow \mathcal{H}(\text{TH}_3, m_3, \text{ID}_I)$, get $g^i$ from $\text{ID}_I$

// Verify SoK and HMAC, update and sign $\tau_R$

8: **if** DS.Verif(spk_R, $(l_{\text{sig}} || \text{CTX}_2 || t_2)$, $\sigma_2$) $\neq$ 1

9: **then return** $\perp$

10: **if** SoKver($\omega_R || \text{ID}_R || \text{TH}_2 || \text{TH}_3 || \text{TH}_4$, $\text{stm}_R$, $\text{ni}_R$) $\neq$ 1

11: **then return** $\perp$

12: **if** $\text{TH}_5 \neq \mathcal{H}(\text{TH}_4, \text{val}, n_r)$ **then return** $\perp$

13: **accepted** $\leftarrow$ 1

14: $\tau_R \leftarrow \tau_R || g^i || \text{TH}_2 || \text{TH}_3 || \text{TH}_4 || M_1 || m_2 || m_3 || H_R || H_R^1 || \text{ni}_R || \text{ID}_I || t_2 || n_r || \text{val}$

15: $\sigma_R \leftarrow \text{DS SIGN}(\text{ssk}_{\text{Prox}_R}, \tau_R)$

16: **terminated** $\leftarrow$ 1, $\text{sst}_R \leftarrow \tau_R || \sigma_R$

17: **return** $M_4' \leftarrow (c_4 || n_r || \text{val} || \text{TH}_5)$

<caption>FIGURE 13 – Lawful Interception in the EDHOC protocol with ID = 2. The notation MCS denotes the method (here 2 = **Static-sign**) and the cipher suite that the Initiator wants to use.</caption>
InitRun1(ID<sub>I</sub>)
1: (x &$\leftarrow$ Z<sub>p</sub><sup>*</sup>, g<sup>x</sup>), C<sub>I</sub> &$\leftarrow$ {0, 1}<sup>l<sub>C</sub></sup>
2: return M<sub>1</sub> &larr; (MCS||g<sup>x</sup>||C<sub>I</sub>||EAD<sub>1</sub>)
InitRun2(ID<sub>I</sub>, M<sub>2</sub>)
1: Parse M<sub>2</sub> as (g<sup>y</sup>||c<sub>2</sub>), g<sup>xy</sup> &$\leftarrow$ (g<sup>y</sup>)<sup>x</sup>, g<sup>yi</sup> &$\leftarrow$ (g<sup>y</sup>)<sup>i</sup>
// Compute sk<sub>2</sub> and decrypt c<sub>2</sub>
2: TH<sub>2</sub> &$\leftarrow$ H(g<sup>y</sup>, H(M<sub>1</sub>))
3: PRK<sub>2e</sub> &$\leftarrow$ HKDF_Extract(TH<sub>2</sub>, g<sup>xy</sup>)
4: sk<sub>2</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>2e</sub>, 0||TH<sub>2</sub>||l<sub>2</sub>, l<sub>2</sub>)
5: m<sub>2</sub> &$\leftarrow$ Dec(sk<sub>2</sub>, c<sub>2</sub>), parse m<sub>2</sub> as (C<sub>R</sub>||ID<sub>R</sub>||σ<sub>2</sub>||EAD<sub>2</sub>)
6: CTX<sub>2</sub> &$\leftarrow$ (C<sub>R</sub>||ID<sub>R</sub>||TH<sub>2</sub>||EAD<sub>2</sub>), sid &$\leftarrow$ (C<sub>I</sub>, C<sub>R</sub>, g<sup>x</sup>, g<sup>y</sup>)
7: t'<sub>2</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>2e</sub>, 2||CTX<sub>2</sub>||l<sub>mac</sub>, l<sub>mac</sub>)
// Verify Responder authentication
8: if DS.Verif(spk<sub>R</sub>, (l<sub>sig</sub>||CTX<sub>2</sub>||t'<sub>2</sub>), σ<sub>2</sub>) &ne; 1 then
    return &perp;
9: accepted &$\leftarrow$ 1
// Compute key-schedule ofr 3rd message
10: TH<sub>3</sub> &$\leftarrow$ H(TH<sub>2</sub>, m<sub>2</sub>, ID<sub>R</sub>), CTX<sub>3</sub> &$\leftarrow$ (ID<sub>I</sub>||TH<sub>3</sub>||g<sup>i</sup>||EAD<sub>3</sub>)
11: sk<sub>3</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>2e</sub>, 3||TH<sub>3</sub>||l<sub>key</sub>, l<sub>key</sub>)
12: IV<sub>3</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>2e</sub>, 4||TH<sub>3</sub>||l<sub>iv</sub>, l<sub>iv</sub>)
13: salt<sub>4e3m</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>2e</sub>, 5||TH<sub>3</sub>||l<sub>hash</sub>, l<sub>hash</sub>)
14: PRK<sub>4e3m</sub> &$\leftarrow$ HKDF_Extract(salt<sub>4e3m</sub>, g<sup>yi</sup>)
// Authenticate (static DH in method 2)
15: t<sub>3</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>4e3m</sub>, 6||CTX<sub>3</sub>||l<sub>mac</sub>, l<sub>mac</sub>)
// Ensure LI-compliance and assemble M<sub>3</sub>
16: m<sub>3</sub> &$\leftarrow$ (ID<sub>I</sub>||t<sub>3</sub>||EAD<sub>3</sub>), ad<sub>3</sub> &$\leftarrow$ (l<sub>ead</sub>||"||TH<sub>3</sub>)
17: c<sub>3</sub> &$\leftarrow$ Enc'(sk<sub>3</sub>, IV<sub>3</sub>, ad<sub>3</sub>, m<sub>3</sub>), TH<sub>4</sub> &$\leftarrow$ H(TH<sub>3</sub>, m<sub>3</sub>, ID<sub>I</sub>)
18: H<sub>I</sub> &$\leftarrow$ (h<sub>I</sub>g<sup>y</sup>)<sup>x</sup>, H<sub>I</sub><sup>1</sup> &$\leftarrow$ (h<sub>I</sub>g<sup>y</sup>)<sup>i</sup>
19: stml &$\leftarrow$ [X = g<sup>x</sup> &amp; H<sub>I</sub> = (h<sub>I</sub>g<sup>y</sup>)<sup>x</sup> &amp; X<sub>1</sub> = g<sup>i</sup> &amp; H<sub>I</sub><sup>1</sup> = (h<sub>I</sub>g<sup>y</sup>)<sup>i</sup>]
20: ni<sub>I</sub> &$\leftarrow$ SoK<sub>ω<sub>I</sub></sub>||ID<sub>R</sub>||TH<sub>2</sub>||TH<sub>3</sub>||TH<sub>4</sub> { (x, i) : stml }]
21: K<sub>I</sub> &$\leftarrow$ (sk<sub>2</sub>||sk<sub>3</sub>||IV<sub>3</sub>||t<sub>2</sub>), S<sub>I</sub> &$\leftarrow$ Enc''(pcsk<sub>I,Prox<sub>I</sub></sub>, K<sub>I</sub>)
22: return M<sub>3</sub> &$\leftarrow$ (c<sub>3</sub>||H<sub>I</sub>||H<sub>I</sub><sup>1</sup>||ni<sub>I</sub>||S<sub>I</sub>)
InitRun3(ID<sub>I</sub>, M''<sub>4</sub>)

1: Parse M''<sub>4</sub> as (c<sub>4</sub>||n<sub>r</sub>||val||TH<sub>5</sub>)
2: if c<sub>4</sub> = &perp; then return &perp;
3: if TH<sub>5</sub> &ne; H(TH<sub>4</sub>, val, n<sub>r</sub>) then return &perp;
4: sk<sub>4</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>4e3m</sub>, 8||TH<sub>4</sub>||l<sub>key</sub>, l<sub>key</sub>)
5: IV<sub>4</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>4e3m</sub>, 9||TH<sub>4</sub>||l<sub>key</sub>, l<sub>key</sub>)
6: ad<sub>4</sub> &$\leftarrow$ (l<sub>ead</sub>||"||TH<sub>4</sub>), m<sub>4</sub> &$\leftarrow$ Dec'(sk<sub>4</sub>, IV<sub>4</sub>, ad<sub>4</sub>, c<sub>4</sub>)
7: Parse m<sub>4</sub> as EAD<sub>4</sub>, if m<sub>4</sub> = &perp; then return &perp;
8: PRK<sub>out</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>4e3m</sub>, 7||TH<sub>4</sub>||[n&#x0304;<sub>r</sub>]</sub>||l<sub>hash</sub>, l<sub>hash</sub>)
9: terminated &$\leftarrow$ 1

RespRun1(ID<sub>R</sub>, M<sub>1</sub>)
1: (y &$\leftarrow$ Z<sub>p</sub><sup>*</sup>, g<sup>y</sup>), C<sub>R</sub> &$\leftarrow$ {0, 1}<sup>l<sub>C</sub></sup>
2: Parse M<sub>1</sub> as (MCS||g<sup>x</sup>||C<sub>I</sub>||EAD<sub>1</sub>)
// Compute key-schedule for 2nd message
3: g<sup>xy</sup> &$\leftarrow$ (g<sup>x</sup>)<sup>y</sup>, sid &$\leftarrow$ (C<sub>I</sub>, C<sub>R</sub>, g<sup>x</sup>, g<sup>y</sup>)
4: TH<sub>2</sub> &$\leftarrow$ H(g<sup>y</sup>, H(M<sub>1</sub>))
5: PRK<sub>2e</sub> &$\leftarrow$ HKDF_Extract(TH<sub>2</sub>, g<sup>xy</sup>)
6: sk<sub>2</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>2e</sub>, 0||TH<sub>2</sub>||l<sub>2</sub>, l<sub>2</sub>)
7: CTX<sub>2</sub> &$\leftarrow$ (C<sub>R</sub>||ID<sub>R</sub>||TH<sub>2</sub>||EAD<sub>2</sub>)
8: t<sub>2</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>2e</sub>, 2||CTX<sub>2</sub>||l<sub>mac</sub>, l<sub>mac</sub>)
// Authenticate (signature in method 2)
9: σ<sub>2</sub> &$\leftarrow$ DS.See(ssk<sub>R</sub>, (l<sub>sig</sub>||CTX<sub>2</sub>||t<sub>2</sub>))
// Assemble M<sub>2</sub>
10: m<sub>2</sub> &$\leftarrow$ (C<sub>R</sub>||ID<sub>R</sub>||σ<sub>2</sub>||EAD<sub>2</sub>), c<sub>2</sub> &$\leftarrow$ Enc(sk<sub>2</sub>, m<sub>2</sub>)
11: return M<sub>2</sub> &$\leftarrow$ (g<sup>y</sup>||c<sub>2</sub>)
RespRun2(ID<sub>R</sub>, M'<sub>3</sub>)
1: Parse M'<sub>3</sub> as c<sub>3</sub>, TH<sub>3</sub> &$\leftarrow$ H(TH<sub>2</sub>, m<sub>2</sub>, ID<sub>R</sub>)
// Compute sk<sub>3</sub> and decrypt c<sub>3</sub>
2: sk<sub>3</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>2e</sub>, 3||TH<sub>3</sub>||l<sub>key</sub>, l<sub>key</sub>)
3: IV<sub>3</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>2e</sub>, 4||TH<sub>3</sub>||l<sub>iv</sub>, l<sub>iv</sub>)
4: ad<sub>3</sub> &$\leftarrow$ (l<sub>ead</sub>||"||TH<sub>3</sub>), m<sub>3</sub> &$\leftarrow$ Dec'(sk<sub>3</sub>, IV<sub>3</sub>, ad<sub>3</sub>, c<sub>3</sub>)
5: Parse m<sub>3</sub> as (ID<sub>I</sub>||t<sub>3</sub>||EAD<sub>3</sub>), get g<sup>i</sup> from ID<sub>I</sub>
6: g<sup>yi</sup> &$\leftarrow$ (g<sup>i</sup>)<sup>y</sup>, CTX<sub>3</sub> &$\leftarrow$ (ID<sub>I</sub>||TH<sub>3</sub>||g<sup>i</sup>||EAD<sub>3</sub>)
7: salt<sub>4e3m</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>2e</sub>, 5||TH<sub>3</sub>||l<sub>hash</sub>, l<sub>hash</sub>)
8: PRK<sub>4e3m</sub> &$\leftarrow$ HKDF_Extract(salt<sub>4e3m</sub>, g<sup>yi</sup>)
9: t'<sub>3</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>4e3m</sub>, 6||CTX<sub>3</sub>||l<sub>mac</sub>, l<sub>mac</sub>)
// Verify Initiator authentication
10: if t<sub>3</sub> &ne; t'<sub>3</sub> then return &perp;
11: accepted &$\leftarrow$ 1
// Compute key-schedule for 4th message
12: TH<sub>4</sub> &$\leftarrow$ H(TH<sub>3</sub>, m<sub>3</sub>, ID<sub>I</sub>), ad<sub>4</sub> &$\leftarrow$ (l<sub>ead</sub>||"||TH<sub>4</sub>)
13: sk<sub>4</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>4e3m</sub>, 8||TH<sub>4</sub>||l<sub>key</sub>, l<sub>key</sub>)
14: IV<sub>4</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>4e3m</sub>, 9||TH<sub>4</sub>||l<sub>key</sub>, l<sub>key</sub>)
// Ensure LI-compliance and assemble M<sub>4</sub>
15: H<sub>R</sub> &$\leftarrow$ (h<sub>R</sub>g<sup>x</sup>)<sup>y</sup>, H<sub>R</sub><sup>1</sup> &$\leftarrow$ (h<sub>R</sub>g<sup>y</sup>)<sup>i</sup>
16: stm<sub>R</sub> &$\leftarrow$ [Y = g<sup>y</sup> &amp; H<sub>R</sub> = (h<sub>R</sub>g<sup>x</sup>)<sup>y</sup> &amp; H<sub>R</sub><sup>1</sup> = (h<sub>R</sub>g<sup>y</sup>)<sup>i</sup>]
17: ni<sub>R</sub> &$\leftarrow$ SoK<sub>ω<sub>R</sub></sub>||ID<sub>I</sub>||TH<sub>2</sub>||TH<sub>3</sub>||TH<sub>4</sub> {y : stm<sub>R</sub>}]
18: K<sub>R</sub> &$\leftarrow$ (sk<sub>2</sub>||sk<sub>3</sub>||IV<sub>3</sub>||t<sub>2</sub>), S<sub>R</sub> &$\leftarrow$ Enc''(pcsk<sub>R,Prox<sub>R</sub></sub>, K<sub>R</sub>)
19: m<sub>4</sub> &$\leftarrow$ EAD<sub>4</sub>, c<sub>4</sub> &$\leftarrow$ Enc'(sk<sub>4</sub>, IV<sub>4</sub>, ad<sub>4</sub>, m<sub>4</sub>)
20: n<sub>r</sub> &$\leftarrow$ {0, 1}<sup>l<sub>rand</sub></sup>, val &$\leftarrow$ H(g<sup>xy</sup>, "", n<sub>r</sub>)
21: PRK<sub>out</sub> &$\leftarrow$ HKDF_Expand(PRK<sub>4e3m</sub>, 7||TH<sub>4</sub>||[n&#x0304;<sub>r</sub>]</sub>||l<sub>hash</sub>, l<sub>hash</sub>)
22: terminated &$\leftarrow$ 1, TH<sub>5</sub> &$\leftarrow$ H(TH<sub>4</sub>, val, n<sub>r</sub>)
23: return M<sub>4</sub> &$\leftarrow$ (c<sub>4</sub>||n<sub>r</sub>||val||TH<sub>5</sub>||H<sub>R</sub>||H<sub>R</sub><sup>1</sup>||ni<sub>R</sub>||S<sub>R</sub>)

<caption>FIGURE 14 – Lawful Interception in the EDHOC protocol with ID = 2 (continued).</caption>
## 4.6 Handshake - Fourth case

**Message flow.** We study here the last case, where the Initiator and the Responder use Static DIFFIE-HELLMAN as current authentication method (ID = 3). Changes are minimal compare to the previous case. Indeed the Initiator, when receiving the second message $M_2$ gets $g^r$ and then compute elements $H_I^1$ and $H_I^2$: $H_I^1 = (h_I g^r)^x$ and $H_I^2 = (h_I g^y)^i$. He adds those elements to its signature of knowledge and transmits them to its proxy ProxI. On his side, the Responder obtains $g^i$ after deciphering $c_3$ and then compute elements $H_R^1$ and $H_R^2$: $H_R^1 = (h_R g^i)^y$ and $H_R^2 = (h_R g^x)^r$. Similarly he adds those elements to its signature of knowledge and also transmits them to its proxy ProxR along with its usual last message. This modification are depicted in FIGURES 15 and 16 below. Note that it is mainly a merge of the two previous methods (from the static point of view). Concerning the proxies, they both store the static DIFFIE-HELLMAN elements $g^i$ and $g^r$ (obtain in the same way we describe for the two previous cases), which will be useful in the Open algorithm (see details below). In this case, since $t_2$ and $t_3$ are not signed, we do not need to make them verified by proxies and thus encrypt it in $S_I$ or $S_R$, which simplifies a little the protocol. Moreover, some changes are again necessary for the TDGen and the Open algorithms. We will explain latter in more details the importance of these elements $H^1$ and $H^2$ in addition to $H$. But here to make it simple, for methods involving a static DIFFIE-HELLMAN element, we need to derive another PRK compute with a DIFFIE-HELLMAN key involving this static DIFFIE-HELLMAN. As we need to retrieve $g^{xy}$ to compute the key PRKout in the first case, we will need here to retrieve this DIFFIE-HELLMAN key, and that is why we introduce these elements.

**Session state.** At the end of the protocol, we have

$$ \text{sst}_d = \omega_d \| \text{MCS} \| g^x \| g^y \| g^r \| g^i \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4 \| M_1 \| m_2 \| m_3 \| H_d \| H_d^1 \| H_d^2 \| ni_d \| pid_d \| n_r \| \text{val} \| \sigma_d $$

where pid_d denotes the partner identity of ID_d. So we parse sst_d as

$$ [\bar{\omega}_d] \llbracket \text{MCS} \rrbracket \llbracket g^x \rrbracket \llbracket g^y \rrbracket \llbracket g^r \rrbracket \llbracket g^i \rrbracket \text{ TH}_2 \text{ TH}_3 \text{ TH}_4 \llbracket \bar{M}_1 \rrbracket \llbracket \bar{m}_2 \rrbracket \llbracket \bar{m}_3 \rrbracket \llbracket H_d \rrbracket \llbracket H_d^1 \rrbracket \llbracket H_d^2 \rrbracket \llbracket ni_d \rrbracket \llbracket pid_d \rrbracket \llbracket n_r \rrbracket \llbracket \text{val} \rrbracket \llbracket \sigma_d \rrbracket $$

Again, the dashed boxes are used to check the validity of the session. Next, the black boxes are used to compute $g^{xy}$, $g^{iy}$ and $g^{rx}$; then with the highlighted boxes we compute PRKout.

**Verification of sst.** The verification of sst works in a very similar way as for the first case. The algorithm Verify just did not check signatures $\sigma_2$ and $\sigma_3$ in this situation.

So we may think to generalized Verify algorithm, which based on the MCS it gets from sst (parsed in the good way after analyzing MCS) adapts to each case, performing the appropriate verifications for the method selected in MCS. This is the modify Verify algorithm we will consider in our security analysis.

**Generation of trapdoors and opening the session.** As for the previous cases, we make some changes to the TDGen and Open algorithms.

For the TDGen algorithm, the inputs remain the same, and as in the previous case, the trapdoor vector of an authority $\Lambda$ is $(\Lambda.td_0, \Lambda.td_1, \Lambda.td_2)$. Elements $\Lambda.td_0$ and $\Lambda.td_1$ are constructed in the same way as in the previous case, unlike $\Lambda.td_2$. Indeed, here we set $B_I \leftarrow g^i$ and $B_R \leftarrow g^r$ and $\Lambda.td_2 \leftarrow B_d^{\Lambda.SK}$

For the Open algorithm, the inputs remain the same, but the usual disjunction we made in the two previous cases is more complex here.

**Open(pp, sst_d, APK_d, T_d):** Parse sst_d as $\omega_d \| \text{MCS} \| g^x \| g^y \| g^r \| g^i \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4 \| M_1 \| m_2 \| m_3 \| H_d \| H_d^1 \| H_d^2 \| ni_d \| pid_d \| n_r \| \text{val} \| \sigma_d$ (with $d \in \{I, R\}$) and set $A_I \leftarrow g^x$, $A_R \leftarrow g^y$, $B_I \leftarrow g^i$ and $B_R \leftarrow g^r$. Parse APK_d as $((\Lambda_j^d.pk, \Lambda_j^d.ni))_{j=1}^{n_d}$ and $T_d$ as $((\Lambda_j^d.td_0, \Lambda_j^d.td_1, \Lambda_j^d.td_2))_{j=1}^{n_d}$.

Verify that NIPoKver$((g, \Lambda_j^d.pk, A_d, B_d, \Lambda_j^d.td_1, \Lambda_j^d.td_2), \Lambda_j^d.td_0) = 1$ for all $j \in [1, n_d]$. If any verification fails, return special symbol $\perp$. Else:
PreComp<sub>I</sub>(M<sub>I</sub>)

1 : Parse M<sub>I</sub> as ((Λ<sub>j</sub><sup>1</sup>)<sub>j=1</sub><sup>n<sub>I</sub></sup>||ID<sub>I</sub>)

2 : ∀j ∈ ⌊1, n<sub>I</sub>⌋ if NIPoKver(Λ<sub>j</sub><sup>1</sup>.pk, Λ<sub>j</sub><sup>1</sup>.ni) ≠ 1

3 : then return ⊥

4 : h<sub>I</sub> ← ∏<sub>j=1</sub><sup>n<sub>I</sub></sup> Λ<sub>j</sub><sup>1</sup>.pk, ω<sub>I</sub> ← (Λ<sub>j</sub><sup>1</sup>)<sub>j=1</sub><sup>n<sub>I</sub></sup> ||ID<sub>I</sub>

5 : Agreement on secret key pcsk<sub>I,Prox<sub>I</sub></sub>

6 : return (h<sub>I</sub>, ω<sub>I</sub>)

Prox<sub>I</sub>Run1(ID<sub>I</sub>, M<sub>1</sub>)

1 : Parse M<sub>1</sub> as (MCS||g<sup>x</sup>||C<sub>I</sub>||EAD<sub>1</sub>)

2 : τ<sub>I</sub> ← ω<sub>I</sub>||MCS||g<sup>x</sup> // Initialize τ<sub>I</sub>

3 : return M<sub>1</sub>

Prox<sub>I</sub>Run2(ID<sub>I</sub>, M<sub>2</sub>)

1 : Parse M<sub>2</sub> as (g<sup>y</sup>||c<sub>2</sub>)

2 : τ<sub>I</sub> ← τ<sub>I</sub>||g<sup>y</sup> // Update τ<sub>I</sub>

3 : return M<sub>2</sub>

Prox<sub>I</sub>Run3(ID<sub>I</sub>, M<sub>3</sub>)

1 : Parse M<sub>3</sub> as (c<sub>3</sub>||H<sub>I</sub>||H<sub>I</sub><sup>1</sup>||H<sub>I</sub><sup>2</sup>||ni<sub>I</sub>||S<sub>I</sub>)

2 : K<sub>I</sub> ← Dec''(pcsck<sub>I,Prox<sub>I</sub></sub>, S<sub>I</sub>), parse K<sub>I</sub> as (sk<sub>2</sub>||sk<sub>3</sub>||IV<sub>3</sub>)

3 : m<sub>2</sub> ← Dec(sk<sub>2</sub>, c<sub>2</sub>), get ID<sub>R</sub> from m<sub>2</sub>

4 : TH<sub>2</sub> ← H(g<sup>y</sup>, H(M<sub>1</sub>)), TH<sub>3</sub> ← H(TH<sub>2</sub>, m<sub>2</sub>, ID<sub>R</sub>)

5 : ad<sub>3</sub> ← (l<sub>aead</sub>||“ ”||TH<sub>3</sub>), m<sub>3</sub> ← Dec'(sk<sub>3</sub>, IV<sub>3</sub>, ad<sub>3</sub>, c<sub>3</sub>)

6 : TH<sub>4</sub> ← H(TH<sub>3</sub>, m<sub>3</sub>, ID<sub>I</sub>), get g<sup>r</sup> from ID<sub>R</sub>
// Verify SoK and update τ<sub>I</sub>

7 : if SoKver(ω<sub>I</sub>||ID<sub>R</sub>||TH<sub>2</sub>||TH<sub>3</sub>||TH<sub>4</sub>, stm<sub>I</sub>, ni<sub>I</sub>) ≠ 1

8 : then return ⊥

9 : accepted ← 1

10 : τ<sub>I</sub> ← τ<sub>I</sub>||g<sup>r</sup>||g<sup>i</sup>||TH<sub>2</sub>||TH<sub>3</sub>||TH<sub>4</sub>||M<sub>1</sub>||m<sub>2</sub>||m<sub>3</sub>||
H<sub>I</sub>||H<sub>I</sub><sup>1</sup>||H<sub>I</sub><sup>2</sup>||ni<sub>I</sub>||ID<sub>R</sub>

11 : return M'<sub>3</sub> ← c<sub>3</sub>

Prox<sub>I</sub>Run4(ID<sub>I</sub>, M'<sub>4</sub>)

1 : Parse M'<sub>4</sub> as (c<sub>4</sub>||n<sub>r</sub>||val||TH<sub>5</sub>)

2 : if M'<sub>4</sub> = ⊥ then return ⊥

3 : if TH<sub>5</sub> = H(TH<sub>4</sub>, val, n<sub>r</sub>) then return ⊥
// Update and sign τ<sub>I</sub>

4 : τ<sub>I</sub> ← τ<sub>I</sub>||n<sub>r</sub>||val, σ<sub>I</sub> ← DS.Sig(ssk<sub>Prox<sub>I</sub></sub>, τ<sub>I</sub>)

5 : terminated ← 1, sst<sub>I</sub> ← τ<sub>I</sub>||σ<sub>I</sub>

6 : return M'<sub>4</sub> ← M'<sub>4</sub>

PreComp<sub>R</sub>(M<sub>R</sub>)

1 : Parse M<sub>R</sub> as ((Λ<sub>j</sub><sup>R</sup>)<sub>j=1</sub><sup>n<sub>R</sub></sup>||ID<sub>R</sub>)

2 : ∀j ∈ ⌊1, n<sub>R</sub>⌋ if NIPoKver(Λ<sub>j</sub><sup>R</sup>.pk, Λ<sub>j</sub><sup>R</sup>.ni) ≠ 1

3 : then return ⊥

4 : h<sub>R</sub> ← ∏<sub>j=1</sub><sup>n<sub>R</sub></sup> Λ<sub>j</sub><sup>R</sup>.pk, ω<sub>R</sub> ← (Λ<sub>j</sub><sup>R</sup>)<sub>j=1</sub><sup>n<sub>R</sub></sup> ||ID<sub>R</sub>

5 : Agreement on secret key pcsk<sub>R,Prox<sub>R</sub></sub>

6 : return (h<sub>R</sub>, ω<sub>R</sub>)

Prox<sub>R</sub>Run1(ID<sub>R</sub>, M<sub>1</sub>)

1 : Parse M<sub>1</sub> as (MCS||g<sup>x</sup>||C<sub>I</sub>||EAD<sub>1</sub>)

2 : τ<sub>R</sub> ← ω<sub>R</sub>||MCS||g<sup>x</sup> // Initialize τ<sub>R</sub>

3 : return M<sub>1</sub>

Prox<sub>R</sub>Run2(ID<sub>R</sub>, M<sub>2</sub>)

1 : Parse M<sub>2</sub> as (g<sup>y</sup>||c<sub>2</sub>)

2 : τ<sub>R</sub> ← τ<sub>R</sub>||g<sup>y</sup>||g<sup>r</sup> // Update τ<sub>R</sub>

3 : return M<sub>2</sub> ← (g<sup>y</sup>||c<sub>2</sub>)

Prox<sub>R</sub>Run3(ID<sub>R</sub>, M<sub>4</sub>)

1 : Parse M<sub>4</sub> as (c<sub>4</sub>||n<sub>r</sub>||val||TH<sub>5</sub>||H<sub>R</sub>||H<sub>R</sub><sup>1</sup>||H<sub>R</sub><sup>2</sup>||ni<sub>R</sub>||S<sub>R</sub>)

2 : if M<sub>4</sub> = ⊥ then return ⊥
// Decipher S<sub>R</sub> and verify transcript hashes

3 : K<sub>R</sub> ← Dec''(pcsck<sub>R,Prox<sub>R</sub></sub>, S<sub>R</sub>), parse K<sub>R</sub> as (sk<sub>2</sub>||sk<sub>3</sub>||IV<sub>3</sub>)

4 : m<sub>2</sub> ← Dec(sk<sub>2</sub>, c<sub>2</sub>), TH<sub>2</sub> ← H(g<sup>y</sup>, H(M<sub>1</sub>))

5 : TH<sub>3</sub> ← H(TH<sub>2</sub>, m<sub>2</sub>, ID<sub>R</sub>), ad<sub>3</sub> ← (l<sub>aead</sub>||“ ”||TH<sub>3</sub>)

6 : m<sub>3</sub> ← Dec'(sk<sub>3</sub>, IV<sub>3</sub>, ad<sub>3</sub>, c<sub>3</sub>), get ID<sub>I</sub> from m<sub>3</sub>

7 : TH<sub>4</sub> ← H(TH<sub>3</sub>, m<sub>3</sub>, ID<sub>I</sub>), get g<sup>i</sup> from ID<sub>I</sub>
// Verify SoK, update and sign τ<sub>R</sub>

8 : if SoKver(ω<sub>R</sub>||ID<sub>I</sub>||TH<sub>2</sub>||TH<sub>3</sub>||TH<sub>4</sub>, stm<sub>R</sub>, ni<sub>R</sub>) ≠ 1

9 : then return ⊥

10 : if TH<sub>5</sub> ≠ H(TH<sub>4</sub>, val, n<sub>r</sub>) then return ⊥

11 : accepted ← 1

12 : τ<sub>R</sub> ← τ<sub>R</sub>||g<sup>r</sup>||g<sup>i</sup>||TH<sub>2</sub>||TH<sub>3</sub>||TH<sub>4</sub>||M<sub>1</sub>||m<sub>2</sub>||m<sub>3</sub>||
H<sub>R</sub>||H<sub>R</sub><sup>1</sup>||H<sub>R</sub><sup>2</sup>||ni<sub>R</sub>||ID<sub>I</sub>||n<sub>r</sub>||val

13 : σ<sub>R</sub> ← DS.Sig(ssk<sub>Prox<sub>R</sub></sub>, τ<sub>R</sub>)

14 : terminated ← 1, sst<sub>R</sub> ← τ<sub>R</sub>||σ<sub>R</sub>

15 : return M'<sub>4</sub> ← (c<sub>4</sub>||n<sub>r</sub>||val||TH<sub>5</sub>)

<caption>FIGURE 15 – Lawful Interception in the EDHOC protocol with ID = 3. The notation MCS denotes the method (here 3 = Static-static) and the cipher suite that the Initiator wants to use.</caption>
InitRun1(ID₁)

1: ($x \leftarrow \mathbb{Z}_p^*, g^x$), $C_1 \leftarrow \{0, 1\}^{lc}$

2: return $M_1 \leftarrow (\text{MCS} \| g^x \| C_1 \| \text{EAD}_1)$

InitRun2(ID₁, $M_2$)

1: Parse $M_2$ as ($g^y \| c_2$), $g^{xy} \leftarrow (g^y)^x, g^{yi} \leftarrow (g^y)^i$

// Compute $sk_2$ and decrypt $c_2$

2: $\text{TH}_2 \leftarrow \mathcal{H}(g^y, \mathcal{H}(M_1))$, $\text{PRK}_{2e} \leftarrow \text{HKDF\_Expand}(\text{TH}_2, g^{xy})$

3: $sk_2 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{2e}, 0 \| \text{TH}_2 \| l_2)$

4: $m_2 \leftarrow \text{Dec}(sk_2, c_2)$, parse $m_2$ as ($C_R \| \text{ID}_R \| t_2 \| \text{EAD}_2$)

5: Get $g^r$ from ID<sub>R</sub>, $g^{xr} \leftarrow (g^r)^x$

6: $\text{salt}_{3e2m} \leftarrow \text{HKDF\_Expand}(\text{PRK}_{2e}, 1 \| \text{TH}_2 \| l_{\text{hash}}, l_{\text{hash}})$

7: $\text{PRK}_{3e2m} \leftarrow \text{HKDF\_Extract}(\text{salt}_{3e2m}, g^{xr})$

8: $\text{CTX}_2 \leftarrow (C_R \| \text{ID}_R \| \text{TH}_2 \| g^r \| \text{EAD}_2)$

9: $t'_2 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 2 \| \text{CTX}_2 \| l_{\text{mac}}, l_{\text{mac}})$

// Verify Responder authentication

10: **if** $t_2 \neq t'_2$ **then return** $\perp$

11: accepted $\leftarrow 1$

// Compute key-schedule for 3rd message

12: $\text{TH}_3 \leftarrow \mathcal{H}(\text{TH}_2, m_2, \text{ID}_R)$, $\text{CTX}_3 \leftarrow (\text{ID}_R \| \text{TH}_3 \| g^i \| \text{EAD}_3)$

13: $sk_3 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 3 \| \text{TH}_3 \| l_{\text{key}}, l_{\text{key}})$

14: $\text{IV}_3 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 4 \| \text{TH}_3 \| l_{\text{iv}}, l_{\text{iv}})$

15: $\text{salt}_{4e3m} \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 5 \| \text{TH}_3 \| l_{\text{hash}}, l_{\text{hash}})$

16: $\text{PRK}_{4e3m} \leftarrow \text{HKDF\_Extract}(\text{salt}_{4e3m}, g^{yi})$

// Authenticate (static DH in method 3)

17: **t**$_3 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{4e3m}, 6 \| \text{CTX}_3 \| l_{\text{mac}}, l_{\text{mac}})$

// Ensure LI-compliance and assemble $M_3$

18: $m_3 \leftarrow (\text{ID}_I \| t_3 \| \text{EAD}_3)$, $\text{TH}_4 \leftarrow \mathcal{H}(\text{TH}_3, m_3, \text{ID}_I)$

19: $\text{ad}_3 \leftarrow (l_{\text{ead}} \| \| \text{TH}_3)$, $c_3 \leftarrow \mathcal{E}''(\text{sk}_3, \text{IV}_3, \text{ad}_3, m_3)$

20: **H**$_1 \leftarrow (\text{h}_1 g^y)^x, \text{H}^1_1 \leftarrow (\text{h}_1 g^r)^x, \text{H}^2_1 \leftarrow (\text{h}_1 g^y)^i$

21: **st**<sub>1</sub> $\leftarrow [X = g^x \wedge \text{H}_1 = (\text{h}_1 g^y)^x \wedge \text{H}^1_1 = (\text{h}_1 g^r)^x$ 
$\wedge X_1 = g^i \wedge \text{H}^2_1 = (\text{h}_1 g^y)^i]$

22: **n**<sub>1</sub> $\leftarrow \text{SoK}_{\omega_1} \| \text{ID}_R \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4$ {$(x, i) : \text{st} \text{m}_1$}

23: **K**<sub>1</sub> $\leftarrow (\text{sk}_2 \| \text{sk}_3 \| \text{IV}_3)$, $S_1 \leftarrow \mathcal{E}''(\text{pcsk}_{\text{R,ProxR}}, K_1)$

24: return $M_3 \leftarrow (c_3 \| \text{H}_1 \| \text{H}^1_1 \| \text{H}^2_1 \| \text{ni} \| S_1)$

InitRun3(ID₁, $M_4''$)

1: Parse $M_4''$ as ($c_4 \| n_r \| \text{val} \| \text{TH}_5$)

2: if $c_4 = \perp$ then return $\perp$

3: if $\text{TH}_5 \neq \mathcal{H}(\text{TH}_4, \text{val}, n_r)$ then return $\perp$

4: $sk_4 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{4e3m}, 8 \| \text{TH}_4 \| l_{\text{key}}, l_{\text{key}})$

5: $\text{IV}_4 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{4e3m}, 9 \| \text{TH}_4 \| l_{\text{key}}, l_{\text{key}})$

6: $\text{ad}_4 \leftarrow (l_{\text{ead}}, \| \| \text{TH}_4)$, $m_4 \leftarrow \text{Dec}'(sk_4, \text{IV}_4, \text{ad}_4, c_4)$

7: Parse $m_4$ as EAD<sub>4</sub>, if $m_4 = \perp$ then return $\perp$

8: $\text{PRK}_{\text{out}} \leftarrow \text{HKDF\_Expand}(\text{PRK}_{4e3m}, 7 \| \text{TH}_4 \| \lceil \bar{n}_r \rceil \| l_{\text{hash}}, l_{\text{hash}})$

9: terminated $\leftarrow 1$

RespRun1(ID<sub>R</sub>, $M_1$)

1: ($y \leftarrow \mathbb{Z}_p^*, g^y$), $C_R \leftarrow \{0, 1\}^{lc}$

2: parse $M_1$ as ($\text{MCS} \| g^x \| C_1 \| \text{EAD}_1$)

// Compute key-schedule for 2nd message

3: $g^{xy} \leftarrow (g^x)^y, g^{xr} \leftarrow (g^x)^r$, sid $\leftarrow (C_1, C_R, g^x, g^y)$

4: $\text{TH}_2 \leftarrow \mathcal{H}(g^y, \mathcal{H}(M_1))$, $\text{PRK}_{2e} \leftarrow \text{HKDF\_Extract}(\text{TH}_2, g^{xy})$

5: $sk_2 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{2e}, 0 \| \text{TH}_2 \| l_2)$

6: $\text{salt}_{3e2m} \leftarrow \text{HKDF\_Expand}(\text{PRK}_{2e}, 1 \| \text{TH}_2 \| l_{\text{hash}}, l_{\text{hash}})$

7: $\text{PRK}_{3e2m} \leftarrow \text{HKDF\_Extract}(\text{salt}_{3e2m}, g^{xr})$

8: $\text{CTX}_2 \leftarrow (C_R \| \text{ID}_R \| \text{TH}_2 \| g^r \| \text{EAD}_2)$

// Authenticate (static DH in method 3)

9: **t**$_2 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 2 \| \text{CTX}_2 \| l_{\text{mac}}, l_{\text{mac}})$

// Assemble $M_2$

10: $m_2 \leftarrow (C_R \| \text{ID}_R \| t_2 \| \text{EAD}_2)$, $c_2 \leftarrow \mathcal{E}(sk_2, m_2)$

11: return $M_2 \leftarrow (g^y \| c_2)$

RespRun2(ID<sub>R</sub>, $M_3'$)

1: Parse $M_3'$ as $c_3$, $\text{TH}_3 \leftarrow \mathcal{H}(\text{TH}_2, m_2, \text{ID}_R)$

// Compute $sk_3$ and decrypt $c_3$

2: $sk_3 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 3 \| \text{TH}_3 \| l_{\text{key}}, l_{\text{key}})$

3: $\text{IV}_3 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 4 \| \text{TH}_3 \| l_{\text{iv}}, l_{\text{iv}})$

4: $\text{ad}_3 \leftarrow (l_{\text{ead}} \| \| \text{TH}_3)$, $m_3 \leftarrow \text{Dec}'(sk_3, \text{IV}_3, \text{ad}_3, c_3)$

5: Parse $m_3$ as $(\text{ID}_I \| t_3 \| \text{EAD}_3)$, get $g^i$ from ID<sub>I</sub>

6: $g^{yi} \leftarrow (g^i)^y$, $\text{CTX}_3 \leftarrow (\text{ID}_I \| \text{TH}_3 \| g^i \| \text{EAD}_3)$

7: $\text{salt}_{4e3m} \leftarrow \text{HKDF\_Expand}(\text{PRK}_{3e2m}, 5 \| \text{TH}_3 \| l_{\text{hash}}, l_{\text{hash}})$

8: $\text{PRK}_{4e3m} \leftarrow \text{HKDF\_Extract}(\text{salt}_{4e3m}, g^{yi})$

9: $t'_3 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{4e3m}, 6 \| \text{CTX}_3 \| l_{\text{mac}}, l_{\text{mac}})$

// Verify Initiator authentication

10: **if** $t_3 \neq t'_3$ **then return** $\perp$

11: accepted $\leftarrow 1$

// Compute key-schedule for 4th message

12: $\text{TH}_4 \leftarrow \mathcal{H}(\text{TH}_3, m_3, \text{ID}_I)$, $\text{ad}_4 \leftarrow (l_{\text{ead}} \| \| \text{TH}_4)$

13: $sk_4 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{4e3m}, 8 \| \text{TH}_4 \| l_{\text{key}}, l_{\text{key}})$

14: $\text{IV}_4 \leftarrow \text{HKDF\_Expand}(\text{PRK}_{4e3m}, 9 \| \text{TH}_4 \| l_{\text{key}}, l_{\text{key}})$

// Ensure LI-compliance and assemble $M_4$

15: $\text{H}_R \leftarrow (\text{h}_R g^x)^y, \text{H}^1_R \leftarrow (\text{h}_R g^i)^y, \text{H}^2_R \leftarrow (\text{h}_R g^x)^r$

16: **st**<sub>R</sub> $\leftarrow [Y = g^y \wedge \text{H}_R = (\text{h}_R g^x)^y \wedge \text{H}^1_R = (\text{h}_R g^i)^y$ 
$\wedge Y_1 = g^r \wedge \text{H}^2_R = (\text{h}_R g^x)^r]$

17: **n**<sub>R</sub> $\leftarrow \text{SoK}_{\omega_R} \| \text{ID}_I \| \text{TH}_2 \| \text{TH}_3 \| \text{TH}_4$ {$(y, r) : \text{st} \text{m}_R$}

18: $\text{K}_R \leftarrow (\text{sk}_2 \| \text{sk}_3 \| \text{IV}_3)$, $S_R \leftarrow \mathcal{E}''(\text{pcsk}_{\text{R,ProxR}}, K_R)$

19: $n_r \leftarrow \{0, 1\}^{l_{\text{rand}}}$, val $\leftarrow \mathcal{H}(g^{xy}, \text{``}, n_r)$

20: $m_4 \leftarrow \text{EAD}_4$, $c_4 \leftarrow \text{Enc}'(sk_4, \text{IV}_4, \text{ad}_4, m_4)$

21: $\text{PRK}_{\text{out}} \leftarrow \text{HKDF\_Expand}(\text{PRK}_{4e3m}, 7 \| \text{TH}_4 \| \lceil \bar{n}_r \rceil \| l_{\text{hash}}, l_{\text{hash}})$

22: terminated $\leftarrow 1$, $\text{TH}_5 \leftarrow \mathcal{H}(\text{TH}_4, \text{``}, n_r)$

23: return $M_4 \leftarrow (c_4 \| n_r \| \text{val} \| \text{TH}_5 \| \text{H}_R \| \text{H}^1_R \| \text{H}^2_R \| \text{ni} \| S_R)$

<caption>FIGURE 16 – Lawful Interception in the EDHOC protocol with ID = 3 (continued).</caption>
$$ \dagger \text{ for } d = I, \text{ compute: } g^{xy} \leftarrow \frac{H_I}{\prod_{j=1}^{n_I} \Lambda_j^I \cdot \text{td}_1}, g^{rx} \leftarrow \frac{H_I^1}{\prod_{j=1}^{n_I} \Lambda_j^I \cdot \text{td}_1} \text{ and } g^{iy} \leftarrow \frac{H_I^2}{\prod_{j=1}^{n_I} \Lambda_j^I \cdot \text{td}_2}, $$

$$ \dagger \text{ for } d = R, \text{ compute } g^{xy} \leftarrow \frac{H_R}{\prod_{j=1}^{n_R} \Lambda_j^R \cdot \text{td}_1}, g^{rx} \leftarrow \frac{H_R^2}{\prod_{j=1}^{n_R} \Lambda_j^R \cdot \text{td}_2} \text{ and } g^{iy} \leftarrow \frac{H_R^1}{\prod_{j=1}^{n_R} \Lambda_j^R \cdot \text{td}_1}, $$

and if $\mathcal{H}(g^{xy}, \dots, n_r) \neq \text{val}$, return $\perp$. Otherwise, with $g^{xy}, g^{rx}, g^{iy}, \text{TH}_2, \text{TH}_3, \text{TH}_4$ and $n_r$, compute $\text{PRK}_{2e}, \text{PRK}_{3e2m}, \text{PRK}_{4e3m}$ and $\text{PRK}_{\text{out}}$.

Let's quickly explain importance of the changes we made. This is similar to what we have done before. We want to retrieve $g^{xy}$, $g^{iy}$ and $g^{rx}$. However the elements $H_I, H_I^1, H_I^2$ and $H_R, H_R^1, H_R^2$ have been constructed in different ways. So to retrieve $g^{xy}$ with $H_I$ (resp. $H_R$), we need to "divide" $H_I$ by $h_I^x$ (resp. $H_R$ by $h_R^y$), to retrieve $g^{iy}$ with $H_I^1$ (resp. $H_R^1$), we "divide" $H_I^1$ by $h_I^i$ (resp. $H_R^1$ by $h_R^y$), and to retrieve $g^{rx}$ with $H_I^2$ (resp. $H_R^2$, we "divide" $H_I^2$ by $h_I^x$ (resp. $H_R^2$ by $h_R^r$).

**Signature of knowledge.** In this case we mix the two signature protocols of the second case. The signature of knowledge made by the Initiator and the Responder is a proof of knowledge of a discrete logarithm to three different bases and of a discrete logarithm to two different bases in order to certify that the elements $H_d, H_d^1$ and $H_d^2$ are well formed. We continue to consider a hash function $\mathcal{H}_{\text{SoK}} : \mathbb{G} \times \{0,1\}^* \to \mathbb{Z}_p^*$. We can proceed as follows, for example on the Initiator side.

We work with the statement $\text{stm}_I = [X = g^x \wedge H_I = (h_I g^y)^x \wedge H_I^1 = (h_I g^r)^x \wedge X_1 = g^i \wedge H_I^2 = (h_I g^y)^i]$, witnesses $x$ and $i$ for that statement and the message $m_I = \omega_I \|\| \text{ID}_R \|\|\| \text{TH}_2 \|\|\| \text{TH}_3 \|\|\| \text{TH}_4$. The Initiator runs the SoK algorithm as follows.

**SoK($m_I, (x, i), \text{stm}_I$):** Pick at random $r_I, s_I \leftarrow \mathbb{Z}_p^*$. Compute $I_1 \leftarrow g^{r_I}, I_2 \leftarrow (h_I g^y)^{r_I}, I_3 \leftarrow (h_I g^r)^{r_I}, I_4 \leftarrow g^{s_I}, I_5 \leftarrow (h_I g^y)^{s_I}, \alpha_I \leftarrow \mathcal{H}_{\text{SoK}}(I_1 I_2 I_3 I_4 I_5, m_I), \beta_I \leftarrow r_I - \alpha_I x \pmod p \text{ and } \gamma_I \leftarrow s_I - \alpha_I i \pmod p$. Return $n_I = (\alpha_I, \beta_I, \gamma_I)$.

Next, when he checks $n_I$, the proxy $\text{Prox}_I$ runs the SoKver algorithm as follows.

**SoKver($m_I, \text{stm}_I, n_I$):** Compute $I'_1 \leftarrow g^{\beta_I}(g^x)^{\alpha_I}, I'_2 \leftarrow (h_I g^y)^{\beta_I}(h_I^x g^{xy})^{\alpha_I} = (h_I g^y)^{\beta_I}(H_I)^{\alpha_I}, I'_3 \leftarrow (h_I g^r)^{\beta_I}(h_I^x g^{xr})^{\alpha_I} = (h_I g^r)^{\beta_I}(H_I^1)^{\alpha_I}, I'_4 \leftarrow g^{\gamma_I}(g^i)^{\alpha_I} \text{ and } I'_5 \leftarrow (h_I g^y)^{\gamma_I}(h_I^i g^{iy})^{\alpha_I} = (h_I g^y)^{\gamma_I}(H_I^2)^{\alpha_I}$. Return 1 if $\alpha_I = \mathcal{H}_{\text{SoK}}(I'_1 I'_2 I'_3 I'_4 I'_5, \omega_I)$, else return 0.

On their side, the Responder and his proxy $\text{Prox}_R$ work with the statement $\text{stm}_R = [Y = g^y \wedge H_R = (h_R g^x)^y \wedge H_R^1 = (h_R g^i)^y \wedge Y_1 = g^r \wedge H_R^2 = (h_R g^x)^r]$, the witnesses $y$ and $r$, and the message $m_R = \omega_R \|\| \text{ID}_I \|\|\| \text{TH}_2 \|\|\| \text{TH}_3 \|\|\| \text{TH}_4$. The SoK and SoKver algorithms work in the same way.

**Proof of knowledge.** In this version of the protocol, each set of authorities needs to compute the two trapdoors. Thus the proofs of knowledge for them are a little bit more substantial to calculate, but works in the same way as the previous two cases.
# 5 Implementation and evaluation

As method 3 (Static-static) of authentication is likely to be the most expensive, we implement LI-EDHOC in this particular setting. We complement the lakers implementation of EDHOC in Rust, with bindings for C and Python. As an online addition to this article, we release the LIKE implementation as open source<fnref n="9" />.

## 5.1 Implementation setup

Our implementation transports LIKE elements within the External Authorization Data (EAD) fields of EDHOC. This allows for selective activation of lawful interception maintaining EDHOC's base structure. There are two main additions to the lakers implementation of EDHOC: (1) the cryptographic primitives supporting the generation and verification of the Signature of Knowledge. We instantiate the SoK as described in section 4.6. (2) dedicated EAD handlers that generate and process LIKE elements during the EDHOC handshake. These handlers populate the EAD field of the message with the necessary additional elements of LIKE. The implementation includes the pre-computation phase performed once for a given set of peers and authorities, during which the values ($h_1, \omega_1$) are computed.

We evaluate the implementation on two typical constrained platforms, based on the ARM Cortex-M core¹⁰: (1) nRF52840 development board featuring an ARM Cortex-M4F processor running at 64 MHz with 256 kB RAM and 1 MB flash memory, and (2) STM32WBA55CG development board featuring an ARM Cortex-M33 processor running at 32 MHz with 128 kB RAM and 512 kB flash memory. To precisely measure execution time we used the Saleae Logic 8 logic analyzer connected to specific GPIO pins on both development boards, that are toggled at the beginning and end of given code sections (see FIGURE 17). The sampling frequency is set to 40 MS/s (Mega Samples per second).

<figure><img src="image_8.png" /><figcaption>FIGURE 17 – Our evaluation setup. We benchmark the execution on the embedded evaluation board STM32WBA55CG (on the right) by toggling General Purpose Input/Output pins and recording the execution times using a logic analyzer (on the left). The logic analyzer software used to process the data runs on a PC.</figcaption></figure>

<footnote n="9">⁹https://github.com/ElsaLopez133/lakers.git
¹⁰Note that we are not making a comparison here, but simply presenting implementation results on commonly used platforms.</footnote>
For the evaluation, the Initiator and the Responder are located on the same physical device, which removes the network communication overhead and allows us to focus on computational performance. Note that the evaluation does not include the proxies which run on non-constrained devices.

## 5.2 Implementation results

We present the results in TABLES 3 and 4. “Software LIKE” corresponds to a software-based implementation, with all cryptographic operations performed in software, without any hardware acceleration. “Hardware LIKE” corresponds to a hardware-accelerated implementation where elliptic curve operations (point addition and point multiplication), field operations (modular multiplication and modular addition) and hash operations are performed using hardware acceleration.

<table><caption>TABLE 3 – Message overhead for the Initiator running EDHOC authenticated with DH Static Keys with and without implementing LIKE.</caption><thead><tr><td>Message</td><td>EDHOC with LIKE (bytes)</td><td>EDHOC base (bytes)</td></tr></thead><tbody><tr><td>Message_1</td><td>37</td><td>37</td></tr><tr><td>Message_3</td><td>115</td><td>19</td></tr><tr><td>Total</td><td>152</td><td>56</td></tr></tbody></table>

TABLE 3 shows the bytes carried in each message for the Initiator (messages 1 and 3). The extra bytes compared to the standard EDHOC implementation in the third message come from the additional signature of knowledge.

TABLE 4 shows that the implementation of LIKE comes with a significant overhead, mainly due to the expensive ECC point multiplications and additions which figure in the SoK. We note an (expected) effect of the clock frequency and processor architecture on performance: the software-based implementation on Cortex M4F is comparable with the hardware-based implementation on Cortex M33. Finally, we observe that hardware acceleration substantially reduces the execution time differences observed between base EDHOC and LI-EDHOC for the Cortex M33 device, making lawful-interception more practical for deployment in constrained devices. Future iterations of this implementation could implement hardware acceleration as well in the nRF52840 (Cortex M4F) to further improve performance and reduce computation times.

Moreover, it would be interesting to run future experiments on hardware dedicated for ECC computations, such as [20]. Finally note that, whereas static authentication requires a lengthy signature of knowledge, complexity drops for authentication methods relying only on ephemeral secrets (i.e., where peers use signatures to authenticate).
<table><caption>TABLE 4 – LI-EDHOC handshake (LIKE) vs. EDHOC (base) runtime evaluation (in seconds), for implementations fully run in software (SW) or featuring ECC, field operations, and hashes that are hardware accelerated (HW).</caption><thead><tr><th rowspan="2">Operation</th><th colspan="2">Cortex M4F @ 64 MHz</th><th colspan="4">Cortex M33 @ 32 MHz</th></tr><tr><th>SW LIKE</th><th>SW base</th><th>SW LIKE</th><th>SW base</th><th>HW LIKE</th><th>HW base</th></tr></thead><tbody><tr><td colspan="7"><strong>Precomputation Phase</strong></td></tr><tr><td>Precomputation (vok_log_auth)</td><td>1.8095</td><td>-</td><td>7.1282</td><td>-</td><td>0.5798</td><td>-</td></tr><tr><td>Precomputation (h)</td><td>0.0015</td><td>-</td><td>0.0057</td><td>-</td><td>0.00005</td><td>-</td></tr><tr><td>Precomputation (w)</td><td>0.0015</td><td>-</td><td>0.0055</td><td>-</td><td>0.0009</td><td>-</td></tr><tr><td><strong>Subtotal</strong></td><td><strong>1.8125</strong></td><td><strong>-</strong></td><td><strong>7.1394</strong></td><td><strong>-</strong></td><td><strong>0.5808</strong></td><td><strong>-</strong></td></tr><tr><td colspan="7"><strong>Initiator</strong></td></tr><tr><td>Message_1</td><td>0.0016</td><td>0.0016</td><td>0.0062</td><td>0.0062</td><td>0.0016</td><td>0.0016</td></tr><tr><td>Message_3 (SoK)</td><td>9.1231 (6.2477)</td><td>2.8495</td><td>35.9294 (24.6097)</td><td>11.2157</td><td>4.1256 (2.8484)</td><td>1.2649</td></tr><tr><td><strong>Subtotal</strong></td><td><strong>9.1247</strong></td><td><strong>2.8511</strong></td><td><strong>35.9356</strong></td><td><strong>11.2219</strong></td><td><strong>4.1272</strong></td><td><strong>1.2665</strong></td></tr></tbody></table>
# 6 Security Model

Our LI-EDHOC protocol guarantees the key-security, non-frameability, and LI-compliance security properties from LIKE [5, 9], but also a stronger property of EDHOC: identity protection. We provide here a description of the security model.

## 6.1 Execution environment

LIKE includes three types of participants: endpoints belonging to a set ESet, proxies from a set PROXSet, and authorities in a set AUTHSet. Each party P has private and public parameters ($P, \overline{SK}, P, \overline{PK}$) – which for EDHOC are in fact private/public keysets instead of just one key$^{11}$. We also make endpoints and proxies store a set of symmetric keys shared between them in an attribute $P.PCSK = \{(Q, \overline{pcsk}_{P,Q})\}, Q \in \text{ShareSet}$ (if $P \in \text{ESet}$, then $\text{ShareSet} = \text{PROXSet}$ and vice-versa). Any party may be corrupted, yielding to the adversary one element of the private keyset. The party P stores a corruption bit $P.SK.\gamma$ for each key $SK \in P.\overline{SK}$, initially set to 0 and raised to 1 either if the adversary reveals the long term key SK during the handshake, or if he registers a malicious party.

Protocol sessions are always run by instances of four parties: two endpoints, playing the parts of Initiator and Responder; and two proxies. We denote by $\pi_P^q$ the $q^{th}$ instance of P. Each endpoint/proxy instance keeps track of attributes, including: the session identifier $\pi_P^q.sid$; the computed session key $\pi_P^q.PRK_{out}$; a session state $\pi_P^q.sst$; partner identifiers (PNID for the partnering endpoint (or endpoints if this is a proxy instance), AID for the authorities chosen by that party as legitimate for Lawful Interception, and ProxID for the partnering proxies); a flag indicating authentication acceptance (denoted $\pi_P^q.\alpha$); and $\pi_P^qrole$ (the role role $\in \{\text{Initiator, Responder, ProxyI, ProxyR}\}$ of P in the handshake).

To better capture EDHOC, endpoint party instances require several additional values: $\pi_P^q.meth$ (the method that will be used for a session involving this instance); $\pi_P^q.SK$ (the private key used by P to authenticate); a flag $\pi_P^q.SK.\gamma$ (indicating the corruption of the long term key SK used by $\pi_P^q$); a flag indicating the revelation of the session key (denoted $\pi_P^q.\rho$); and $\pi_P^q.pid.PK$ (the public key that P expects its partner to use for authentication). Both proxy and endpoint instances also store the current symmetric encryption key $\pi_P^q.pcsk \in P.PCSK$ used during the handshake. Finally proxy instances store three specific values : $\pi_P^q.sst$ (the session state built during the protocol session run); $\pi_P^q.tr$ (the transcript of the protocol session run) and $\pi_P^q.ctn$ (an indicative value (in $[1, 4]$ ou in $[1, 3]$)) used to indicate which proxy algorithm should be executed next in the protocol run).

So to sum up, we list the data associated to each instance $\pi_P^q$ as follows:

† **sid**: a vector ($C_I, C_R, g^x, g^y$) that contains the ephemeral public keys $g^x$ and $g^y$, as well as the connection identifiers $C_I$ and $C_R$, initially set to $\perp$, and update during the session run (for example if the two endpoint instances do not agree on the method to use during the handshake, sid is maintained to $\perp$).

† **PRK<sub>out</sub>**: the session key, initially set to $\perp$, and update when the protocol terminate correctly. This information is specific to the endpoint instances.

† **PNID**: this set contains the identity of all other endpoints taking part to the same session as $\pi_P^q$. There is two cases for this: either it contains only the name of the partner $\pi_P^q$ is trying to exchange with if $P \in \text{ESet}$; or it contains the names of the two users trying to exchange if $P \in \text{PROXSet}$ (in this case the list is ordered : PNID = [ID\_Initiator, ID\_Responder]).

† **ProxID**: this set stores the identity of all other proxies taking part to the same session as $\pi_P^q$. There is also two cases here: either this contains the identity of the two proxies taking part to the exchange if $P \in \text{ESet}$ (in this case the list is ordered : ProxID = [ID\_Proxy_I, ID\_Proxy_R]); or it contains the identity of the other proxy involved in the exchange if $P \in \text{PROXSet}$.

<footnote n="11">11 For an authority, these sets contains solely one element, respectively $a$ and $g^a$. For a proxy, there are naturally the private and public signing key, but also symmetric encryption keys, shared with endpoints. Finally, concerning an endpoint, there are the two types of long-term keys, and also the symmetric encryption key shared with the associated proxy.</footnote>
† **AID**: this set is unilateral, it only contains the identities of the authorities, (potentially) involved in the
lawful interception, associated to the instance $\pi_P^q$.

† **role**: the role $\in \{\text{Initiator}, \text{Responder}, \text{Proxy}_1, \text{Proxy}_R\}$ of P in the handshake.

† **α**: a flag initially set to one of the five values {$\perp$, running, accepted, rejected, terminated} depending on
the state of the protocol run.

† **ρ**: a reveal bit, initially set to 0 and raised to 1 if the adversary reveals the instance's session key. This
information is specific to endpoint instances.

† **meth**: the method $meth \in \{0, 1, 2, 3\}$ that will be used for a session involving this instance (initially set
to $\perp$).

† **SK**: the long term secret key used by P during the handshake to authenticate. This information is
specific to endpoint instances.

† **SK.γ**: a reveal bit set to 0 and raised to 1 if the adversary reveals the long-term secret key $\pi_P^q$.SK during
the handshake, or if P is a malicious party registered by $\mathcal{A}$. This information is specific to endpoint
instances.

† **pid.PK**: the public key P expects its partner to use during the handshake to authenticate (according to
the method selected). This information is specific to endpoint instances.

† **pcsk**: the symmetric encryption key ($pcsk \in P.PCSK$) used during the handshake to cipher data between
an endpoint and its associated proxy instances.

† **sst**: the session state sst, used by proxies to store and verify data, and useful for the key-recovery process.
This information is specific to proxy instances.

† **tr**: the transcript of the protocol session run, storing, in order, all messages sent and received. This
information is specific to proxy instances.

† **cnt**: this is an integer $f \in [1, 4]$ (for Initiator proxies) or $f \in [1, 3]$ (for Responder proxies) used to
indicate which proxy algorithm (*ProxₐRun*) should be executed next in the protocol run. It has no
impact on the security analysis.

Moreover each authority registered is equipped with a trapdoor reveal bit **tdrev**, initially set to 0 and
raised to 1 if, in any session, the adversary reveals the trapdoor of an authority on one instance.

Following [5, 9] we define here the notion of instances *have matching conversation*.

**Definition 17** Let (P, Q) be two endpoints with P ≠ Q and let $q, j$ be two natural integers. We says that $\pi_P^q$ have matching conversation with $\pi_Q^j$ (or that $\pi_P^q$ matches $\pi_Q^j$) if $\pi_P^q sid \neq \perp$, $\pi_P^q sid = \pi_Q^j sid$, $Q = \pi_P^q PNID$ and $P = \pi_Q^j PNID$.

For *correctness*, accepting endpoint instances that have matching conversation compute the same session
key; accepting endpoint instance keys are lawfully-interceptable by the collaboration of all the authorities in
the instance's AID.
## 6.2 Oracles

Similarly to [5, 9], we use game-based security notions and give the adversary access to the following oracles:

† **oRegister**(*P*, *type*, *P*.PK): this oracle allows *A* to register either honest parties (with P.PK = ⊥) or malicious parties (with malicious P.PK(≠⊥)). The value *type* belongs to {endpoint, proxy, authority}.

† **oSend**($\pi_P^q$, *m*): with this oracle, *A* can send a message *m* to an endpoint instance $\pi_P^j$, following the logical order of messages send during the protocol session run.

† **oReveal**($\pi_P^q$): with this oracle *A* learns the session key of endpoint instance $\pi_P^q$. It also sets the corruption flag $\rho$ to 1.

† **oTest**<sub>*b*</sub>($\pi_P^q$): This oracle can only be queried once during a security game, and returns either the real session key computed by endpoint instance $\pi_P^q$ or a random key, depending on the value of a bit *b* (selected at the beginning of the game by the challenger).

† **oRevealTD**(*sst*, *I*, *R*, *Prox*, *AID*, *l*): thanks to this oracle, *A* learns the trapdoor of authority $\Lambda_\ell$ registered in authority set *AID* for a session with state *sst*, if, and only if, the *Verify* algorithm called on *sst* and the associated data outputs 1. It also sets the trapdoor reveal flag $\Lambda_\ell$.tdrev to 1.

The previous oracles come from [9], and we need to modify two oracles in our work, extending them to capture multiple authentication modes and credentials:

† **oNewSession**(*P*, *role*, *PNID*, *PK*<sub>*I*</sub>, *PK*<sub>*R*</sub>, *ProxID*, *AID*): with this oracle *A* creates endpoint/proxy instances of an endpoint/proxy *P* with role *role* ∈ {Initiator, Responder, Proxy*<sub>*I*</sub>*}, Proxy*<sub>*R*</sub>*}, with initiator authentication using the initiator's public credential *PK*<sub>*I*</sub> and responder authentication using responder credential *PK*<sub>*R*</sub>. This allows to create an instance using a specific method (either 0, 1, 2 or 3) (given (*PK*<sub>*I*</sub>, *PK*<sub>*R*</sub>), we identify the method and we implicitly associate an integer corresponding to the method (either 0, 1, 2 or 3).

† **oCorrupt**(*P*, *l*): this oracle allows the adversary to corrupt the *l*<sup>th</sup> long-term key of party *P*, and sets the corruption bit $\gamma$ of each instance $\pi_P^q$ using this long-term key to 1.

The oracles accessible to the adversary, along with their functionalities, are all depicted in FIGURE 18. Moreover as in [5, 9], we need an auxiliary function which takes as input a *sst* and an instance $\pi$, and returns 1 if the *sst* is the resulting of a $\pi$ run. This allows us to establish a link between a session state and an instance (instead of just a party). We denote this function *IdentifySession*.
oRegister(u, type, $\overline{PK}$)

1: if type = endpoint then

2: ESet ← ESet ∪ {u}

3: else if role = proxy then

4: PROXSet ← PROXSet ∪ {u}

5: else

6: AUTHSet ← AUTHSet ∪ {u}

7: ($\overline{PK}$, $\overline{SK}$) ← (type)KeyGen(u, pp)

8: if $\overline{PK}$ = {⊥} then

9: u.$\overline{PK}$ ← $\overline{PK}$, u.$\overline{SK}$ ← $\overline{SK}$

10: for all SK ∈ $\overline{SK}$, SK.γ = 0

11: else $\overline{PK}$ ≠ {⊥} then

12: u.$\overline{PK}$ ← $\overline{PK}$

for all SK ∈ $\overline{SK}$, SK.γ = 1

13: return u.$\overline{PK}$

oNewSession(u, q, role, PK<sub>I</sub>, PK<sub>R</sub>, PNID, ProxID, AID)

1: if $\pi_u^q$ = ⊥ then

2: $\pi_u^q$.sid ← ⊥, $\pi_u^q$.α ← ⊥

3: $\pi_u^q$.role ← role, $\pi_u^q$.PNID ← PNID

4: $\pi_u^q$.ProxID ← ProxID, $\pi_u^q$.AID ← AID

5: $\pi_u^q$.meth ← (PK<sub>I</sub>, PK<sub>R</sub>), $\pi_u^q$.PRK<sub>out</sub> ← ⊥

6: if role ∈ {Initiator, Responder} then

7: $\pi_u^q$.ρ ← 0

8: if role = Initiator then

9: $\pi_u^q$.SK ← u.$\overline{SK}$[PK<sub>I</sub>]

10: $\pi_u^q$.pid.PK ← PK<sub>R</sub>

11: $\pi_u^q$.pcsk ← pcsk<sub>u,ProxID[l]</sub>

12: else

13: $\pi_u^q$.SK ← u.$\overline{SK}$[PK<sub>R</sub>]

14: $\pi_u^q$.pid.PK ← PK<sub>I</sub>

15: $\pi_u^q$.pcsk ← pcsk<sub>u,ProxID[R]</sub>

16: if role ∈ {Proxy<sub>I</sub>, Proxy<sub>R</sub>} then

17: $\pi_u^q$.sst ← ⊥

18: $\pi_u^q$.ctn ← 1

19: $\pi_u^q$.tr ← ⊥

20: if role = Proxy<sub>I</sub> then

21: $\pi_u^q$.pcsk ← pcsk<sub>PNID[l],u</sub>

22: else

23: $\pi_u^q$.pcsk ← pcsk<sub>PNID[R],u</sub>

24: return $\pi_u^q$

oCorrupt(u, ℓ)

1: u.$\overline{SK}$[ℓ].γ ← 1

2: ∀q ∈ $\mathbb{N}^*$, $\pi_u^q$.SK = u.$\overline{SK}$[ℓ] then $\pi_u^q$.SK.γ = 1

3: return u.$\overline{SK}$[ℓ]

oTest<sub>b</sub>($\pi_u^q$)

1: if $\pi_u^q$ = ⊥ or $\pi_u^q$.α ≠ terminated or $\pi_u^q$.role ∉ {Initiator, Responder} then

2: return ⊥

3: else

4: T ← T ∪ { $\pi_u^q$ }

5: k<sub>0</sub> ← $\pi_u^q$.PRK<sub>out</sub>

6: k<sub>1</sub> ← s K

7: return k<sub>b</sub>

oSend($\pi_u^q$, m)

1: if $\pi_u^q$.role = Initiator then

2: if $\pi_u^q$.α = ⊥ then

3: m' ← InitRun1(m)

4: else

5: m' ← InitRun2(m)

6: return m'

7: else if $\pi_u^q$.role = Responder then

8: if $\pi_u^q$.sid = ⊥ then

9: m' ← RespRun1(m)

10: else

11: m' ← RespRun2(m)

12: return m'

13: else

14: if $\pi_u^q$.cnt = f ∈ [[1, 4]] and $\pi_u^q$.role = Proxy<sub>I</sub> then

15: m' ← Prox<sub>I</sub>Runf(m)

16: $\pi_u^q$.cnt = $\pi_u^q$.cnt + 1

17: return m'

18: else if $\pi_u^q$.cnt = f ∈ [[1, 3]] and $\pi_u^q$.role = Proxy<sub>R</sub> then

19: m' ← Prox<sub>R</sub>Runf(m)

20: $\pi_u^q$.cnt = $\pi_u^q$.cnt + 1

21: return m'

22: else

23: return ⊥

oReveal($\pi_u^q$)

1: if $\pi_u^q$.role ∉ {Proxy<sub>I</sub>, Proxy<sub>R</sub>} then

2: if $\pi_u^q$ = ⊥ or $\pi_u^q$.status ≠ terminated then

3: return ⊥

4: else

5: $\pi_u^q$.ρ ← 1

6: return $\pi_u^q$.PRK<sub>out</sub>

oRevealTD(sst, u, v, Prox, ($\Lambda_o$)<sub>o=1</sub>, ℓ)

1: if Verify(pp, sst, u.$\overline{PK}$, v.$\overline{PK}$, Prox.$\overline{PK}$, ($\Lambda_o$.$\overline{PK}$)<sub>o=1</sub>) = 1

2: then $\Lambda_o$.tdrev ← 1

3: return $\Lambda_o$.td

4: else

5: return ⊥

<caption>FIGURE 18 – Security model oracles (by $u \overline{SK}[PK_I]$ we denote the long-term secret key of $u$ associated to the long-term public key $PK_I$).</caption>
## 6.3 Security properties

### 6.3.1 Key-security

In the key-security game, the adversary uses all the oracles presented above in order to learn the value of the bit $b$ (selected by the challenger) used for the single $oTest_b$ query. The adversary wins if, and only if, it guesses $b$ correctly, if its $oTest$ query target Fresh instances as defined below (following [9]), and if he respects the Sound property. This property ensures that only two endpoint instances have matching conversation with the same session identifier $sid$ (no collision among the $sid$ of different sessions occurs) and that two endpoint instances having matching conversation have opposite roles and derive the same session key. The Sound and Fresh properties are depicted in FIGURE 22, as well as the key-security game. (i.e., for which)

**Definition 18** An instance $\pi_u^q$ is said to be Fresh if the long-term authentication credential used by both endpoints in that instance is uncorrupted at the time of the test query, the session key has not been revealed, and at least one authority in AID is honest and its trapdoor has not been revealed. More formally the endpoint instance $\pi_u^q$ is Fresh if:

$$ \dagger \pi_u^q.\alpha = \text{terminated}, \pi_u^q.SK.\gamma = 0 \text{ for the long-term key u.SK used by the instance and } \pi_u^q.\rho = 0; $$

$$ \dagger \text{ If there exists } j \in \mathbb{N} \text{ such that } \pi_u^q \text{ and } \pi_v^j \text{ have matching conversation (where } v = \pi_u^q.PNID), \text{ then } \pi_v^j.\alpha = \text{terminated}, \pi_v^j.SK.\gamma = 0 \text{ for the long-term key v.SK used in the session, and } \pi_v^j.\rho = 0; $$

$$ \dagger \text{ If there exists no instance } \pi_v^j \text{ such that } \pi_u^q \text{ has matching conversation with } \pi_v^j, \text{ then } \pi_v^j.SK.\gamma = 0 \text{ for the key v.SK supposed to be used in a potential exchange with } \pi_u^q \text{ (regarding } \pi_u^q.meth); $$

$$ \dagger \text{ It exists } \Lambda \in \text{AUTHSet such that } \mathcal{A} \text{ made no } o\text{RevealTD}(sst, I, R, \text{Prox}, (\Lambda_i)_{i=1}^n, \ell) \text{ query such that:} $$

$$ \ddagger \Lambda \in \pi_u^q.AID, \Lambda.SK.\gamma = 0 \text{ for all } SK \in \Lambda.\overline{SK} \text{ and } \Lambda = \Lambda_l; $$

$$ \ddagger \text{ IdentifySession}(sst, \pi_u^q) = 1. $$

$$ \dagger \text{ It exists } \Lambda' \in \text{AUTHSet such that for all } j \in \mathbb{N} \text{ such that } \pi_u^q \text{ has matching conversation with } \pi_v^j, \mathcal{A} \text{ made no } o\text{RevealTD}(sst, I, R, \text{Prox}, (\Lambda_i)_{i=1}^n, \ell) \text{ query such that:} $$

$$ \ddagger \Lambda' \in \pi_v^j.AID, \Lambda'.SK.\gamma = 0 \text{ for all } SK \in \Lambda'.\overline{SK} \text{ and } \Lambda' = \Lambda_l; $$

$$ \ddagger \text{ IdentifySession}(sst, \pi_v^j) = 1. $$

**Definition 19 (Key-security)** We define the key-security advantage of a p.p.t. adversary $\mathcal{A}$ as:

$$ \text{Adv}_{\text{LI-EDHOC},\mathcal{A}}^{\text{KS}}(\lambda) = \left| \mathbb{P} \left[ \mathbb{E}_{\text{LI-EDHOC},\mathcal{A}}^{\text{KS}}(\lambda) \implies 1 \right] - \frac{1}{2} \right|. $$

The experiment is depicted in FIGURE 22 along with the Sound and Fresh properties (FIGURE 19). We then said that the LI-EDHOC protocol is key-secure if for any p.p.t. adversary $\mathcal{A}$, the advantage $\text{Adv}_{\text{LI-EDHOC},\mathcal{A}}^{\text{KS}}(\lambda)$ is negligible compared to $\lambda$.

### 6.3.2 LI-compliance

In the LI-compliance security game, $\mathbb{E}_{\text{LI-EDHOC},\mathcal{A}}^{\text{LIC}}(\lambda)$, the goal of the adversary is to generate a protocol session that completes successfully, but for which the lawful interception process fails—either by recovering no session key or by retrieving a key that differs from the one actually established during the session.
To model this property, we use a key-extractor algorithm, as originally proposed in [9]. This algorithm derives from a complete protocol session between an Initiator and a Responder (who may be malicious) an outputs which is the session key established during the execution. To ensure that key security is preserved, the extractor must be unbounded. Based on [9], we adapt the general structure of the key-extractor algorithm as follows.

**Definition 20 (Key-extractor)** A key-extractor algorithm KeyExtract is a deterministic and unbounded algorithm which takes as input a proxy instance and a vector of public keys, and outputs a session key PRK<sub>out</sub>. Moreover, we require that for any m, n ∈ $\mathbb{N}^*$, for any Initiator I and Responder R, for any proxies Prox<sub>I</sub> and Prox<sub>R</sub>, for any sets of authorities ($\Lambda_j^I$)<sub>j=1</sub><sup>m</sup> and ($\Lambda_j^R$)<sub>j=1</sub><sup>n</sup>, and for any set {pp, I.PK, I.SK, R.PK, R.SK, Prox<sub>I</sub>.PK, Prox<sub>I</sub>.SK, Prox<sub>R</sub>.PK, Prox<sub>R</sub>.SK, PRK<sub>out</sub>, sst<sub>I</sub>, sst<sub>R</sub>, APK<sub>I</sub> = ($\Lambda_j^I$.PK)<sub>j=1</sub><sup>m</sup>, ASK<sub>I</sub> = ($\Lambda_j^I$.SK)<sub>j=1</sub><sup>m</sup>, APK<sub>R</sub> = ($\Lambda_j^R$.PK)<sub>j=1</sub><sup>n</sup>, ASK<sub>R</sub> = ($\Lambda_j^R$.SK)<sub>j=1</sub><sup>n</sup>, tr<sub>I</sub>, tr<sub>R</sub>, LIC.PK} generated as follows:

- pp ← Setup($\lambda$);

- (I.PK, I.SK), (R.PK, R.SK) ← EKeyGen(pp);

- (Prox<sub>I</sub>.PK, Prox<sub>I</sub>.SK), (Prox<sub>R</sub>.PK, Prox<sub>R</sub>.SK) ← ProxKeyGen(pp);

- $\forall j \in [1, m], \forall k \in [1, n] \ (\Lambda_j^I.PK, \Lambda_j^I.SK), (\Lambda_k^R.PK, \Lambda_k^R.SK) \leftarrow AKeyGen(pp);$

- (PRK<sub>out</sub>, sst<sub>I</sub>, sst<sub>R</sub>, PRK<sub>out</sub>) resulting on a run of the LI-EDHOC protocol on input pp and the previous public key sets PK;

- tr<sub>I</sub> is the transcript of the protocol session execution producing sst<sub>I</sub> from the point of view of Prox<sub>I</sub>;

- tr<sub>R</sub> is the transcript of the protocol session execution producing sst<sub>R</sub> from the point of view of Prox<sub>R</sub>;

- LIC.PK ← {I.PK, R.PK, Prox<sub>I</sub>.PK, Prox<sub>R</sub>.PK} ∪ {$\Lambda_j^I.PK$}<sub>j=1</sub><sup>m</sup> ∪ {$\Lambda_j^R.PK$}<sub>j=1</sub><sup>n</sup>;

we have that for any $U \in \{I, R\}$ and for any proxy instance $\pi_{\text{Prox}_U}$ such that $\pi_{\text{Prox}_U} \cdot \text{tr} = \text{tr}_U$ and $\pi_{\text{Prox}_U} \cdot \text{sst} = \text{sst}_U$:

$$ \mathbb{P}(\text{KeyExtract}(\pi_{\text{Prox}_U}, \text{LIC.PK}) = \text{PRK}_{\text{out}}) = 1. $$

The set of keys LIC.PK is there to ensure that the KeyExtract algorithm extracts the correct key, i.e., it may need certain keys to compute PRK<sub>out</sub> (and possibly also use some of these keys in the proof to do some verifications).

The adversary has access to all but the oTest oracles and he wants to outputs a tuple $(j, sst_d, I, R, Prox_d, (\Lambda_q^d, \Lambda_q^d.td))_{q=1}^{nd})$ in such a way that the session keys retrieving by the Open algorithm and the KeyExtract algorithm based on this tuple are different.

**Definition 21 (LI-compliance)** We define the LI-compliance advantage of a p.p.t. adversary $\mathcal{A}$ as:

$$ \text{Adv}_{\text{LI-EDHOC},\mathcal{A}}^{\text{LIC}}(\lambda) = \mathbb{P} \left[ \begin{array}{l} (\text{PRK}_{\text{out}*}, \pi_{\text{Prox}_d}^j, \text{LIC.PK}) \leftarrow \mathbb{E}_{\text{LI-EDHOC},\mathcal{A}}^{\text{LIC}}(\lambda) \\ \wedge \text{PRK}_{\text{out}} \leftarrow \text{KeyExtract}(\pi_{\text{Prox}_d}^j, \text{LIC.PK}) \\ \text{s.t. } \text{PRK}_{\text{out}} \neq \perp \wedge \text{PRK}_{\text{out}*} \neq \perp \wedge \text{PRK}_{\text{out}} \neq \text{PRK}_{\text{out}*} \end{array} \right]. $$

The experiment is depicted in FIGURE 20. We then said that the LI-EDHOC protocol is LI-compliant secure if for any p.p.t. adversary $\mathcal{A}$, the advantage $\text{Adv}_{\text{LI-EDHOC},\mathcal{A}}^{\text{LIC}}(\lambda)$ is negligible compared to $\lambda$.
### 6.3.3 Non-frameability

In the non-frameability security game, $\mathbb{E}_{\text{LI-EDHOC},A}^{\text{NF}}(\lambda)$, the adversary is given access to all oracles except oTest. The objective is to associate an honest party P—either an Initiator or a Responder—with a session state sst resulting from a communication in which P did not reach an accepting state.

More precisely, the adversary wins if they can construct such a party P and a session sst involving valid roles (an Initiator or a Responder, a proxy, and a group of authorities), such that sst appears to result from a legitimate communication involving P, despite P not having accepted the session. Otherwise, the adversary loses the non-frameability game.

**Definition 22 (Non-frameability)** We define the non-frameability advantage of a p.p.t. adversary A as:

$$ \mathrm{Adv}_{\text{LI-EDHOC},A}^{\text{NF}}(\lambda) = \mathbb{P}[\mathbb{E}_{\text{LI-EDHOC},A}^{\text{NF}}(\lambda) \implies 1]. $$

The experiment is depicted in FIGURE 20. We then said that the LI-EDHOC protocol is non-frameable if for any p.p.t. adversary A, the advantage $\mathrm{Adv}_{\text{LI-EDHOC},A}^{\text{NF}}(\lambda)$ is negligible compared to $\lambda$.

$$ \mathbb{E}_{\text{LI-EDHOC},A}^{\text{LIC}}(\lambda) $$

1: $\mathrm{pp} \leftarrow \mathrm{Setup}(1^{\lambda})$

2: $\mathrm{ESet} \leftarrow \emptyset, \mathrm{PROXSet} \leftarrow \emptyset, \mathrm{AUTHSet} \leftarrow \emptyset$

3: $\mathcal{O}_{\text{LIC}} \leftarrow \left\{ \begin{array}{l} \text{oRegister}(\cdot, \cdot, \cdot), \text{oSend}(\cdot, \cdot), \\ \text{oNewSession}(\cdot, \cdot, \cdot, \cdot), \\ \text{oCorrupt}(\cdot, \cdot), \\ \text{SessionKeyReveal}(\cdot, \cdot), \\ \text{oRevealTD}(\cdot, \cdot, \cdot, \cdot, \cdot) \end{array} \right\}$

4: $(j, \text{sst}_d, l, R, \text{Prox}_d, (\Lambda_q^d, \Lambda_{q.\text{td}}^d)_{q=1}^{n_d}) \leftarrow \mathcal{A}^{\mathcal{O}_{\text{LIC}}}(\lambda, \text{pp})$

5: **if** $\text{Prox}_d \overline{\mathbb{SK}}[\text{sst}_d].\gamma = 1$ **then**

6: **return** $\perp$

7: **if** $\text{Verify}(\text{pp}, \text{sst}_d, l, \overline{\text{PK}}, R, \overline{\text{PK}}, \text{Prox}_d, \overline{\text{PK}}, (\Lambda_q^d, \overline{\text{PK}})_{q=1}^{n_d}) = 0$

8: **then return** $\perp$

9: **if** $\text{IdentifySession}(\text{sst}_d, \pi_{\text{Prox}_d}^j) = 0$ **then**

10: **return** $\perp$

11: $\mathrm{PRK}_{\mathrm{out}*} \leftarrow \mathrm{Open}(\mathrm{pp}, \mathrm{sst}_d, (\Lambda_q^d, \overline{\mathrm{PK}})_{q=1}^{n_d}, (\Lambda_{q.\mathrm{td}}^d)_{q=1}^{n_d})$

12: **if** $\mathrm{PRK}_{\mathrm{out}*} = \perp$ **then**

13: **return** $\perp$

14: $\mathrm{LIC.\overline{\mathrm{PK}}} \leftarrow l.\overline{\mathrm{PK}} \cup R.\overline{\mathrm{PK}} \cup \mathrm{Prox}_d.\overline{\mathrm{PK}} \cup \{\cup(\Lambda_q^d, \overline{\mathrm{PK}})_{q=1}^{n_d}\}$

15: **return** $(\mathrm{PRK}_{\mathrm{out}*}, \pi_{\mathrm{Prox}_d}^j, \mathrm{LIC.\overline{\mathrm{PK}}})$

$$ \mathbb{E}_{\text{LI-EDHOC},A}^{\text{NF}}(\lambda) $$

1: $\mathrm{pp} \leftarrow \mathrm{Setup}(1^{\lambda})$

2: $\mathrm{ESet} \leftarrow \emptyset, \mathrm{PROXSet} \leftarrow \emptyset, \mathrm{AUTHSet} \leftarrow \emptyset$

3: $b \leftarrow \{0, 1\}$

4: $\mathcal{O}_{\text{NF}} \leftarrow \left\{ \begin{array}{l} \text{oRegister}(\cdot, \cdot, \cdot), \text{oSend}(\cdot, \cdot), \\ \text{oNewSession}(\cdot, \cdot, \cdot, \cdot), \\ \text{oCorrupt}(\cdot, \cdot), \\ \text{SessionKeyReveal}(\cdot, \cdot), \\ \text{oRevealTD}(\cdot, \cdot, \cdot, \cdot, \cdot) \end{array} \right\}$

5: $(\text{sst}, \text{P}) \leftarrow \mathcal{A}^{\mathcal{O}_{\text{NF}}}(\lambda, \text{pp})$

6: **if** $\exists(l, R) \in \mathrm{ESet}^2, \exists n \in \mathbb{N}^*, \exists \mathrm{Prox} \in \mathrm{PROXSet}, \exists (\Lambda_j)_{j=1}^n \in \mathrm{AUTHSet}^n \text{ s.t. :}$

7: $- \mathrm{Verify}(\text{pp}, \text{sst}, l, \overline{\mathrm{PK}}, R, \overline{\mathrm{PK}}, \mathrm{Prox.\overline{\mathrm{PK}}}, (\Lambda_j, \overline{\mathrm{PK}})_{j=1}^n) = 1;$

8: $- P \in \{l, R\}$ and $P.\overline{\mathbb{SK}}[\text{sst}].\gamma = 0;$

9: $- \forall q \in \mathbb{N}, \text{ if } \pi_p^q \neq \perp: \text{IdentifySession}(\text{sst}, \pi_p^q) = 0$ or $\pi_p^q.\alpha = 0;$

10: **then return** 1

11: **else return** 0.

<caption>FIGURE 20 – The LI-EDHOC non-frameability and LI-compliance security games (by $P.\overline{\mathbb{SK}}[\text{sst}]$ we mean the long-term secret key of P associated to the method stored in sst, and by $\mathrm{Prox}_d.\overline{\mathbb{SK}}[\text{sst}_d]$ we mean the secret (long-term) signing key of $\mathrm{Prox}_d$ used to sign sst$_d$).</caption>

### 6.3.4 Identity protection

To enable lawful interception, each proxy must be aware of the identities of both participants. By assumption each proxy is aware of the identity of its associated endpoint. During the protocol run, thanks to the
additional encryption between the endpoint and its proxy, the later learns the identity of the endpoint's partner. The identity protection property has been defined in [14] in the special case of EDHOC but can be easily generalizable to other protocols. We slightly adapt this definition to take into account the modification we made in LI-EDHOC.

**On the Responder side.** As is the case in [14], we will show that our protocol, LI-EDHOC, is identity protective against passive adversaries for the Responder, i.e., an adversary that only intercepts forwarded messages cannot learn the identity of the Responder, at least, given two Responder identities, distinguish one of the two. Why this restriction to passive adversaries? It's actually quite simple. If $\mathcal{A}$ is active and impersonates the Initiator, then he immediately learns the identity of the Responder to the second message. If $\mathcal{A}$ is active but can simply control the Initiator (without corrupting its long-term keys), then he also learns the identity of the Responder to the second message since $sk_2$ only depends on $g^{xy}$. This is why we limit ourselves to a passive adversary.

It goes without saying that if the adversary has access to sst, he learns both identities. This is an assumption we make here (and also for the identity protection of the Initiator): $\mathcal{A}$ never accesses sst (which seems reasonable, given that this information is kept secret by the proxy until an authority requests interception). It also goes without saying that the corruption of an authority leads nowhere. Indeed, the only for $\mathcal{A}$ to obtain information by corrupting an authority is to have access to sst (so far supposed impossible). Finally a trivial attack consists of corruption a proxy, which we will assume is impossible in our security game (and which seems reasonable since in our application case, it is then an operator).

We know define this identity protection notion with more rigor for the Responder.

**Definition 23 (Responder identity protection)** In a similar way, we define the Responder identity protection advantage of a p.p.t. adversary $\mathcal{A}$ as:

$$ \mathrm{Adv}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{Id-Pro-Resp}}(\lambda) = \left| \mathbb{P}\left[ \mathbb{E}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{Id-Responder-1}}(\lambda) \implies 1 \right] - \mathbb{P}\left[ \mathbb{E}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{Id-Responder-0}}(\lambda) \implies 1 \right] \right| $$

with the experiences depicted in FIGURE 21. We then said that the LI-EDHOC protocol is Responder identity protecting if for any p.p.t. adversary $\mathcal{A}$, the advantage $\mathrm{Adv}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{Id-Pro-Resp}}(\lambda)$ is negligible compared to $\lambda$.

**On the Initiator side.** The LI-EDHOC protocol is also identity protective for the Initiator against passive adversaries but also against active adversaries who can control the Responder without corruption its long-term keys. On the other hand, against a fully active adversary $\mathcal{A}$ who impersonates a Responder (with corruption of the long-term keys) the property is not preserved.

We here define this identity protection notion for the Initiator, as we did for the Responder.

**Definition 24 (Initiator identity protection)** We define the Initiator identity protection advantage of a p.p.t. adversary $\mathcal{A}$ as:

$$ \mathrm{Adv}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{Id-Pro-Init}}(\lambda) = \left| \mathbb{P}\left[ \mathbb{E}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{Id-Initiator-1}}(\lambda) \implies 1 \right] - \mathbb{P}\left[ \mathbb{E}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{Id-Initiator-0}}(\lambda) \implies 1 \right] \right| $$

with the experiences depicted in FIGURE 21. We then said that the LI-EDHOC protocol is Initiator identity protecting if for any p.p.t. adversary $\mathcal{A}$, the advantage $\mathrm{Adv}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{Id-Pro-Init}}(\lambda)$ is negligible compared to $\lambda$.
<figure><img src="image_9.png" /><figcaption>FIGURE 21 – The LI-EDHOC 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>
# 7 Security results

Following the approach of [14], we conduct this security analysis in the random oracle model, where the hash function and the key-derivation functions used across the four protocols are represented as random oracles. Specifically, we denote by $RO_H$ the oracle corresponding to the hash function, and by $RO_T$ and $RO_P$ the oracles modeling $HKDF_Extract$ and $HKDF_Expand^{12}$, respectively, as ideal random functions.

We begin this section by establishing the key-security property of our protocol on page 52. Then, on page 81, we demonstrate that the LI-EDHOC protocol satisfies the LI-compliance property. We continue on page 96, with the proof of the non-frameability property. Finally, on page 101, we prove the identity protection properties (for the Responder and the Initiator) of the protocol.

## 7.1 Key security

The first security result we obtained is now presented in the following statement. It states that our protocols satisfy the key-security property.

**Theorem 2 (Key-Secure LI-EDHOC protocol)** Under the assumption that the signature scheme DS is EUF-CMA-secure, that the proofs and signatures of knowledge are zero-knowledge and extractable, that the DDH and the GDH problems are hard to solve in $\mathbb{G}$, the encryption schemes are secure and injective, then the LI-EDHOC protocol, in its four versions, is key-secure. More precisely, for all p.p.t. adversary $\mathcal{A}$ making at most $q_R$ (resp. $q_{RO_T}$, $q_{RO_P}$, $q_{RO_H}$, $q_{RTD}$, $q_{NS}$ and $q_S$) queries to the $oRegister$ (resp. $RO_T$, $RO_P$, $RO_H$, $oRevealTD$, $oNewSession$ and $oSend$) oracle, we have:

$$ \begin{aligned} \mathrm{Adv}_{\mathrm{LI-EDHOC}, \mathcal{A}}^{\mathrm{KS}}(\lambda) \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}} \\ & + 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. \\ & \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} $$

**Proof 2 (of theorem 2)** To prove this theorem, we proceed by games hop. As a reminder, here is the key-security security game.

<figure><img src="image_10.png" /><figcaption>FIGURE 22 – LI-EDHOC key-security security game.</figcaption></figure>

<footnote n="12">¹²More precisely, we have several random oracles $RO_P : RO_P^{l_2}, RO_P^{l_{mac}}, RO_P^{l_{hash}}, RO_P^{l_{key}}, RO_P^{l_{iv}}$, depending on the digest size, but for clarity here we simply denote them as $RO_P$ (latter we will make the distinction).</footnote>
Our security model capture the four versions of the protocol into one security experiment. Nevertheless some difference appear at certain stages between the four versions, which leads us to split our analysis into four branches, depending on which authentication method is used for a session. For the first thirteen games, the method used does not intervene in the analysis (except for the twelfth, for notations). Then we will separate our analysis into four branches. The FIGURE 23 depicts the thirteen first steps with some explanation. Then in FIGURE 24 we present the beginning of the four branches and with FIGURE 25 we represent the end of the four branches along with the conclusion.

To begin with, the game $G_0$ is the reformulation of the original experience. Then with games $G_1$ and $G_2$ we ensure uniqueness of the partnering instances (one Initiator instance for one Responder instance). This is useful for the Sound property. Then in games $G_3$, $G_4$ and $G_5$, we simulate the random oracles RO as lists SO (in order to manipulate them later). With games $G_6$ and $G_7$ we avoid collisions between three simulated oracles (necessary later to ensure the key-schedule security). Then with game $G_8$ we try to guess the instance tested by the adversary, as well as its potential partner, and in game $G_9$ we ensure that this partner exists, and guessed it in game $G_{10}$. Then with $G_{11}$ we chose particular authorities in order to ensure that some sessions are partly fresh. Next with games $G_{12}$ and $G_{13}$ we use extractors of knowledge to prevent the adversary from providing false signatures or proofs of knowledge.

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

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

† **Game $G_1$:** This game is the same game as the previous one, except that this time, we set bad flags `bad_1` and `bad_2` to `true` when:

- two honest (either Initiator or Responder) instances pick the same nonce ($C_1$ or $C_R$) or the same group element `[bad_1]`;

- an honest Responder instance picks a nonce or a group element already received from an Initiator instance `[bad_2]`.

By "honest" we mean not adversary-controlled. This changes are internal to the game, thus are indistinguishable by the adversary $\mathcal{A}$. We hence have:

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

† **Game $G_2$:** This game is the same as $G_1$, except that we abort when flags `bad_1` or `bad_2` are set to `true`. By the identical-until-bad lemma, we have:

$$ |\mathbb{P}(G_1 \Rightarrow 1) - \mathbb{P}(G_2 \Rightarrow 1)| \le \mathbb{P}(F_1) $$

where $F_1$ is the event: `bad_1` or `bad_2` is set to `true` in $G_1$.

We provide an upper bound for $\mathbb{P}(F_1)$ using the birthday paradox. First, observe that we pick at random $q_{NS}$ pairs of group element and nonce over a space of size $p \times 2^{l_c}$. We may reasonably assume that $q_{NS} \le p \times 2^{l_c}$. Thus, the birthday paradox theorem gives us that the probability a collision occurs between two such pairs is:

$$ \frac{q_{NS}(q_{NS} - 1)}{2(2^{l_c}p)} \le \frac{q_{NS}^2}{2^{l_c+1}p}. $$
<figure><img src="image_11.png" /><figcaption>FIGURE 23 – Thirteen first games of the game-schedule.</figcaption></figure>
This was for bad<sub>1</sub>. Now for bad<sub>2</sub> observe that a Responder instance may receive at most $q_{NS} - 1$ pairs of group element and nonce. Since this is true for possibly $q_{NS} - 1$ Responder instance, we thus deduce that the probability it picks at random one of these pairs is:

$$ \frac{(q_{NS} - 1)(q_{NS} - 1)}{2^{l_c} p} \le \frac{q_{NS}^2}{2^{l_c} p} = \frac{2q_{NS}^2}{2^{l_c+1} p}. $$

So, combining these two results, we thus obtain:

$$ |\mathbb{P}(\mathbb{G}_1 \implies 1) - \mathbb{P}(\mathbb{G}_2 \implies 1)| \le \frac{3q_{NS}^2}{2^{l_c+1} p} $$

where $p = |\mathbb{G}|$ and $l_c$ is the length of the nonces.

At the end of this game, we have proved that no more than two endpoint instances can share the same sid = ($C_1, C_R, g^x, g^y$). Indeed, by absurd, let's assume that there exists three endpoint instances $\pi_u^q, \pi_v^j$, and $\pi_w^k$ that have matching conversation by pairs. In this situation, we have then three pairs of partnered instances, but they only commonly share (at most) two DIFFIE-HELLMAN pairs of exchanged elements. But thanks to bad flags bad<sub>1</sub> or bad<sub>2</sub>, after, $\mathbb{G}_2$ we abort if this situation occurs. Contradiction $\not\subset$.

Moreover, this game also implies that endpoint instances having matching conversation have opposite roles. Indeed, by absurd, since at most two instances can share the same sid, we have the following implication: if the two endpoint instances having matching conversation, have the same role, they thus have the same DIFFIE-HELLMAN element (since its position is fixed in the sid). But thanks to the bad flag bad<sub>1</sub>, this is a collision and after game $\mathbb{G}_2$, we abort in this situation. We thus have a contradiction $\not\subset$. This analysis ensure a part of the soundness property.

† **Game $\mathbb{G}_3$**: This game is the same as $\mathbb{G}_2$, except that we simulate $RO_H$ with a list that is empty when the game begins. Then for any new query it picks, stores and returns a random value from $\{0, 1\}^{l_{hash}}$, and returns the same answer if a query is repeated. We then denote $SO_H$ instead of $RO_H$. This modification is internal to the game and indistinguishable by the adversary. Thus we have:

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

† **Game $\mathbb{G}_4$**: This game is the same as $\mathbb{G}_3$ except that here we simulate $RO_P$ (which is used to simulate the different expansions in the key-derivation schedule instead of HKDF_Expand) with a list that is empty when the game begins. Then for any new query it picks, stores and returns a random value, and returns the same answer if a query is repeated. We then denote $SO_P$ instead of $RO_P$. However, remark that $SO_P$ picks at random values of different lengths depending on which query is made. In fact we define simulated random oracles by size: $SO_P^{size}$ for $size \in \{l_2, l_{id}, l_{hash}, l_{key}, l_{iv}, l_{mac}\}$. But this distinction does not impact this or future analysis, we will however specify which one we use if necessary. This modification is internal to the game and indistinguishable by the adversary. Thus we have:

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

† **Game $\mathbb{G}_5$**: This game is the same as game $\mathbb{G}_4$ except that here we simulate $RO_T$ (which is used to simulate the different extractions in the key-derivation schedule instead of HKDF_Extract) with a list that is empty when the game begins and which we denote $SO_T$ instead of $RO_T$. But this one is slightly different from the two previous ones. Indeed we need, for future reductions against the GDH
problem, that it accepts two types of queries. To do so, the list elements differ from the previous two simulated oracles adn are of the form (string, Z, (X, Y); λ), with at least Z or (X, Y) different from ⊥. We distinguish two situations. Firstly, when making a normal call to this oracle, A make a query of the form (string, Z), where string is any bit string, which may represent one of the pseudo-random key or simply be empty, and Z is a group element, possibly a DIFFIE-HELLMAN value, according to the protocol run. In that case the challenger checks in the list he kept in memory to find an entry matching with (string, Z, *; ν) (here * is either ⊥ or (X, Y) (if already defined with a DIFFIE-HELLMAN couple (X, Y) matching Z)). If the search is successful, the challenger then outputs ν. Otherwise he randomly sets ν ←$ {0, 1}^{l_{hash}}$ and appends the new element (string, Z, ⊥; ν) to the list.

Secondly, e.g., during reductions, the adversary will also ask queries of the form (string, (X, Y)), where (X, Y) is a pair of group elements. Once again then the challenger checks the list he has in memory for an entry matching with either (string, *, (X, Y); ν) or (str, Z, *; ν) such that (X, Y, Z) is a DIFFIE-HELLMAN tuple. Again, if its search is successful, he outputs ν. Otherwise he randomly sets ν ←$ {0, 1}^{l_{hash}}$ and appends (string, ⊥, (X, Y); ν) to the list. We must precise that the simulation is perfect and indistinguishable by the adversary, since the challenger can use the DDH oracle provided with the GDH problem to check if a tuple (X, Y, Z) is a DIFFIE-HELLMAN tuple (in the second case). We hence have:

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

† **Game $\mathbb{G}_6$:** Since $SO_H$, $SO_P^{l_{hash}}$ and $SO_T$ return a digest of size $l_{hash}$, we want to avoid collision between this three “simulated” oracles. For this the game $\mathbb{G}_6$ is the same as $\mathbb{G}_5$ except that we set a bad flag bad$_3$ to true when a collision on two of this three simulated oracles occurs. This modification is indistinguishable by the adversary A and so we have:

$$ \mathbb{P}(\mathbb{G}_6 \implies 1) = \mathbb{P}(\mathbb{G}_5 \implies 1). $$

† **Game $\mathbb{G}_7$:** This game is the same as $\mathbb{G}_6$, except that this time we abort when flag bad$_3$ is set to true. By the identical-until-bad lemma we have:

$$ |\mathbb{P}(\mathbb{G}_6 \implies 1) - \mathbb{P}(\mathbb{G}_7 \implies 1)| \le \mathbb{P}(F_2) $$

where $F_2$ is the event: a collision occurs between $SO_H$ and $SO_P^{l_{hash}}$, or $SO_H$ and $SO_T$, or $SO_T$ and $SO_P^{l_{hash}}$.

We provide an upper bound for $\mathbb{P}(F_2)$ using the birthday paradox and the same analysis we made in game $\mathbb{G}_2$ to obtain that:

$$ |\mathbb{P}(\mathbb{G}_6 \implies 1) - \mathbb{P}(\mathbb{G}_7 \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}}. $$

† **Game $\mathbb{G}_8$:** We denote by $(e, \Xi, b')$ the guess of the adversary. With this game, we try to guess in advance the tested instance choosing by A, as well as its potential partner for having matching conversation. This game is the same as the previous one except that we pick at random $e^* ←$ $\llbracket 1, q_{NS} \rrbracket$ and $(p_1, p_2) ←$ $\llbracket 1, q_R \rrbracket^2$. Denoting $P_j$ the j-th party registered by A, if $e \neq e^*$, $\Xi \neq P_{p_1}$ and $\Xi' \neq P_{p_2}$, where $\Xi' = \pi_{\Xi}^e$. PNID, then we abort the simulation and return a random bit.

Thus with this game hop, we increase the winning advantage of A by a factor equaling the correct guessing $(e^*, p_1, p_2)$ of the challenger. This leads us to:

$$ |\mathbb{P}(\mathbb{G}_7 \implies 1) - \frac{1}{2}| \le q_{NS} \cdot q_R^2 \cdot |\mathbb{P}(\mathbb{G}_8 \implies 1) - \frac{1}{2}|. $$
† **Game $G_9$**: This game is the same as the previous one, except that we add an additional failure condition. In this game, we abort if, for the guessed instance $\pi_{\Xi}^e$ there exists no integer $e' \in \mathbb{N}$ such that $\pi_{\Xi}^{e'}$ and $\pi_{\Xi'}^{e'}$ have matching conversation. Then observe that $\mathcal{A}$ has the same chances of winning $G_8$ and $G_9$. Indeed if there exists no matching conversation instance for $\pi_{\Xi}^e$, then $\mathcal{A}$ has a zero winning advantage in game $G_8$ since in this situation he did not respect the Fresh property and the oTest condition. So it is clear that we have:

$$ \mathbb{P}(G_9 \Rightarrow 1) = \mathbb{P}(G_8 \Rightarrow 1). $$

As a result of this game, thanks to game $G_2$, we now have selected an endpoint instance $\pi_{\Xi}^e$ for which there exist a unique instance $\pi_{\Xi'}^{e'}$ having matching conversation with.

† **Game $G_{10}$**: With this game we try to guess in advance the matching instance of $\pi_{\Xi}^e$. For that, this game is the same as game $G_9$, except that we begin by picking at random $e' \leftarrow \mathbb{S} \llbracket 1, q_{NS} \rrbracket$ and if $\pi_{\Xi}^e$ and $\pi_{\Xi'}^{e'}$ do not have matching conversation, then we abort and return a random bit (with $\Xi' = \pi_{\Xi}^e \cdot \text{PNID}$). As above, we increase the winning probability of $\mathcal{A}$ with this game hop, by a factor equaling the correct guessing probability of the matching instance, which leads us to:

$$ |\mathbb{P}(G_9 \Rightarrow 1) - \frac{1}{2}| \le q_{NS} \cdot |\mathbb{P}(G_{10} \Rightarrow 1) - \frac{1}{2}|. $$

† **Game $G_{11}$**: This game is the same as the previous one, except that we begin by picking two indexes $(\ell_1, \ell_2) \leftarrow \mathbb{S} \llbracket 1, q_R \rrbracket^2$. Next:

$\qquad \mapsto$ if the $\ell_1^{th}$ or the $\ell_2^{th}$ party registered by the adversary thanks to the oRegister oracle:

$\qquad \mapsto$ is not an authority or;

$\qquad \mapsto$ is an authority (then denoted by $\Lambda_{\ell_1}^{d^*}$ or $\Lambda_{\ell_2}^{d'^*}$) but which is corrupted (the adversary called the oCorrupt oracle on them or maliciously registered them);

$\qquad \mapsto$ or if $\Lambda_{\ell_1}^{d^*}$ and $\Lambda_{\ell_2}^{d'^*}$ are in the same set of authorities (i.e., both either Initiator's authorities, or Responder's authorities);

$\qquad \mapsto$ or if the adversary queries the oRevealTD oracle with request $(\text{sst}, \pi_{\Xi}^e, \pi_{\Xi'}^{e'}, \pi_w^k, (\Lambda_o)_{o=1}^n, \ell)$ such that:

$\qquad \mapsto$ $\Lambda_\ell = \Lambda_{\ell_1}^{d^*}$ and IdentifySession(sst_d, $\pi_{\Xi}^e$.sid) = 1 or;

$\qquad \mapsto$ $\Lambda_\ell = \Lambda_{\ell_2}^{d'^*}$ and IdentifySession(sst_d', $\pi_{\Xi'}^{e'}$.sid) = 1;

then we abort and return a random bit.

The natural question now is whether such indexes exist. In fact this is not necessarily the case. But in the end, if $\mathcal{A}$ wants to win the game with a non-zero probability, he must respect the Fresh property, which requires the existence of two such indexes. So if such a situation occurs, we stop the game and return a random bit. With this game hop, the winning advantage of the adversary is increased by a factor equaling the probability of selecting correctly these two authorities. We thus obtain:

$$ |\mathbb{P}(G_{10} \Rightarrow 1) - \frac{1}{2}| \le q_R^2 \cdot |\mathbb{P}(G_{11} \Rightarrow 1) - \frac{1}{2}|. $$

† **Game $G_{12}$**: We denote by Ext$_{SoK}$ the knowledge extractor of the signature of knowledge. In order to prevent the adversary from providing false signatures of knowledge, this game is the same as the previous one, except that we begin by initializing four empty lists $L_0$[ ], $L_1$[ ], $L_2$[ ], $L_3$[ ]. We describe what happens with $L_0$, which is easily adaptable for the three others with the appropriate notations.