Offline phase

input: $\mathcal{M} = (P, \delta, \nu, \tau, (t_{i,j}, v_{i,j})_{i \in [P], j \in [\delta]})$

$$ (\text{pk}, \text{sk}) = \text{KGen}(1^{\kappa}) $$

$$ (\text{pk}, \text{sk}) = \text{KGen}(1^{\kappa}) $$

$$ \omega \leftarrow \mathcal{G}_P $$

for $i \in [1..P]$:

for $j \in [1..\delta]$, for $k \in [0..2^{\nu}-1]$:

$$ C_{i,j}^k = \begin{cases} \text{Enc}(\text{pk}, 1 - v_{i,j}) = \llbracket 1 - v_{i,j} \rrbracket & \text{if } k \le t_{i,j} \\ \text{Enc}(\text{pk}, v_{i,j}) = \llbracket v_{i,j} \rrbracket & \text{otherwise.} \end{cases} $$

$$ \mathbf{C} \leftarrow (C_{i,k}^k)_{i \in [P], j \in [\delta]}^{k \in [0..2^{\nu}-1]} $$

$$ \mathbf{C} = \text{EncodeModel}(\text{pk}, \mathcal{M}) $$

$$ \text{pk}, \mathbf{C} \leftarrow \text{pk}, \mathcal{M} $$

Online phase

input: $P, \delta, \nu, \mathbf{x} = (x_{i,j})_{i \in [P], j \in [\delta]}$

for $i \in [1..P]$:

for $j \in [1..\delta]$:

$$ \llbracket S_{i,j} \rrbracket = C_{i,j}^{x_{i,j}} $$

$$ \llbracket S_i \rrbracket = \bigoplus_j \llbracket S_{i,j} \rrbracket $$

$$ \mathcal{S} \leftarrow (\llbracket S_i \rrbracket)_{i \in [P]} $$

$$ \mathcal{S} = \text{EvaluatePaths}(\text{pk}, \mathbf{x}, \mathbf{C}) $$

$$ \pi \leftarrow \mathcal{G}_P $$

for $i \in [1..P]$:

$$ \alpha \leftarrow \mathbb{Z}_q $$

$$ \llbracket \tilde{S}_i \rrbracket = \text{MultScal}(\text{pk}, \alpha, \llbracket S_{\pi(i)} \rrbracket) $$

$$ \tilde{\mathcal{S}} \leftarrow (\llbracket \tilde{S}_i \rrbracket)_{i \in [P]} $$

$$ \tilde{\mathcal{S}} = \text{RandomizeScores}(\text{pk}, \mathcal{S}) $$

$$ \tilde{\mathcal{S}} \rightarrow \mathcal{S} $$

$$ S = \sum_i (\text{Dec}(\text{sk}, \llbracket \tilde{S}_i \rrbracket)) = 0 $$

$$ \text{result} = \begin{cases} \text{accept} & \text{if } S \ge \tau \\ \text{reject} & \text{otherwise.} \end{cases} $$

$$ \text{result} = \text{EvaluateModel}(\text{sk}, \tilde{\mathcal{S}}, \tau) $$

<table><caption>Figure 3.3: Secure decision forest evaluation for Honest-but-Curious Client setting</caption><tr><td>Execute</td></tr><tr><td>1. (pk, sk) &leftarrow; KGen(1<sup>&kappa;</sup>; &rho;)</td></tr><tr><td>2. C &leftarrow; EncodeModel(pk, M; &rho;)</td></tr><tr><td>3. S &leftarrow; EvaluatePaths(pk, x<sub>b</sub>, C)</td></tr><tr><td>4. S &leftarrow; RandomizeScores(pk, S)</td></tr><tr><td>5. result &leftarrow; EvaluateModel(sk, S&#771;, &tau;)</td></tr><tr><td>6. transcript &leftarrow; (pk, C, S&#771;)</td></tr></table>

**Game G<sub>1</sub>.** To prepare the next game, we introduce RandomizeScores' which is a variant of RandomizeScores only taking the number of successful paths *L* = *M*(*x*<sub>0</sub>) = *M*(*x*<sub>1</sub>) as input. It outputs random ciphertexts according to this sole leakage *L* by generating a permutation of *L* ciphertexts of 0 and *P* − *L* non-zero random ciphertexts:
<figure><img src="image_29.png" /><figcaption>Figure 3.4: Client-Privacy Security Game in the Honest-but-Curious Setting</figcaption></figure>

<table><thead><tr><th>RandomizeScores(pk, S)</th><th>RandomizeScores'(L)</th></tr></thead><tbody><tr><td>π &larr; $\mathfrak{S}_P$<br>for i &isin; [1 .. P]:<br>α &larr; $\mathbb{Z}_q$<br>[[S&#771;<sub>i</sub>]] = MultScal(pk, α, [[S<sub>π(i)</sub>]])<br>S&#771; &larr; ([[S&#771;<sub>i</sub>]])<sub>i &isin; [P]</sub></td><td>π' &larr; $\mathfrak{S}_P$<br>for i &isin; [1 .. L]: [[S&#771;<sub>π'(i)</sub>]] = [[0]]<br>for i &isin; [L + 1 .. P]:<br>[[S&#771;<sub>π'(i)</sub>]] = [[k<sub>i</sub> &larr; $\mathbb{Z}_q^*]]<br>S&#771; &larr; ([[S&#771;<sub>i</sub>]])<sub>i &isin; [P]</sub></td></tr></tbody></table>

Indeed, instead of sending a permutation of the genuinely randomized encrypted scores of the paths, fresh ciphertexts are generated. Thanks to random multiplications, which keep zeroes but randomize other non-zero plaintexts, and the permutation, this game is perfectly indistinguishable from the previous one. Since the transcript only contains the new $\tilde{S}$ (which is independent of $b$), and not $S$, then the advantage in this game is 0. This proves that we have perfect client privacy as $\text{Adv}^{\text{client-privacy}}(\mathcal{A}) = 0$.

**Server Privacy.** An honest-but-curious client should not learn any information about the model owned by the server, except the feature used in the case where no dummy comparison are used. We do not consider the result as a leak as the server may act differently according to this value. Hence, we consider an adversary that chooses some inputs $x$ for the client and its random tape $\rho$, but two different models $M_0 = (P, \delta, \nu, \mathbf{t}_0, \mathbf{v}_0, \tau_0)$ and $M_1 = (P, \delta, \nu, \mathbf{t}_1, \mathbf{v}_1, \tau_1)$, with the constraint that evaluating $x$ with respect to the two models $M_0$ and $M_1$ should produce the same result. The random tape $\rho$ will be used by the client for randomizing the ciphertexts. The adversary should then distinguish transcripts involving the two models.

<figure><img src="image_30.png" /><figcaption>Figure 3.5: Server-Privacy Security Game in the Honest-but-Curious Setting</figcaption></figure>

We denote the advantage of any adversary $\mathcal{A}$ by

$$ \text{Adv}^{\text{server-privacy}}(\mathcal{A}) = \left| \Pr[\text{Exp}^{\text{server-privacy}-1}(\kappa, \mathcal{A}) = 1] - \Pr[\text{Exp}^{\text{server-privacy}-0}(\kappa, \mathcal{A}) = 1] \right|. $$

For our scheme, the server's privacy is provided by the encryption of the model in $\mathcal{C}$, during the offline phase. The private server's information are the thresholds $t_{i,j}$ and the Boolean values $v_{i,j}$ for each comparison as well as the final threshold $\tau$. One can note that the client learns which
feature is used in a given comparison. This can be avoided by adding dummy comparisons so that each feature (or many features) is used in every path as discussed previously. For the formal proof, as the scheme leaks the number of accepting paths, this is used by the simulator for the final outcome, without needing the decryption key. Then, as the decryption key is not known anymore, using IND-CPA, we can replace all the ciphertexts in the offline phase by encryptions of 0, thus the client cannot learn anything anymore.

**Game** $G_0$. The first game is the actual security game, with the execution of the protocol between the client with input $(\mathbf{x}, \rho)$ and the server with input $M_b$. We thus detail the Execute procedure:

<table><thead><tr><th>Execute</th></tr></thead><tbody><tr><td>1. $(\mathbf{pk}, \mathbf{sk}) \leftarrow \text{KGen}(1^{\kappa}; \rho)$</td></tr><tr><td>2. $\mathbf{C} \leftarrow \text{EncodeModel}(\mathbf{pk}, M_b; \rho)$</td></tr><tr><td>3. $\mathbb{S} \leftarrow \text{EvaluatePaths}(\mathbf{pk}, \mathbf{x}, \mathbf{C})$</td></tr><tr><td>4. $\tilde{\mathbb{S}} \leftarrow \text{RandomizeScores}(\mathbf{pk}, \mathbb{S})$</td></tr><tr><td>5. $\text{result} \leftarrow \text{EvaluateModel}(\mathbf{sk}, \tilde{\mathbb{S}}, \tau)$</td></tr><tr><td>6. $\text{transcript} \leftarrow (\mathbf{pk}, \mathbf{C}, \tilde{\mathbb{S}})$</td></tr></tbody></table>

**Game** $G_1$. For the next game, we need to introduce a variant EncodeModel' of EncodeModel, which outputs a list of encryptions of 0:

<table><thead><tr><th>EncodeModel(pk, M<sub>b</sub>)</th><th>EncodeModel'()</th></tr></thead><tbody><tr><td><b>for</b> i &isin; [1 .. P]:<br/><b>for</b> j &isin; [1 .. &delta;]:<br/><b>for</b> k &isin; [0 .. 2<sup>&nu;</sup> &minus; 1]:<br/><b> C </b><sup>k</sup><sub>i,j</sub> = <span style="font-size: 2em; vertical-align: middle;">{</span> Enc(pk, 1 &minus; v<sub>i,j</sub>) = [[1 &minus; v<sub>i,j</sub>]] <b>if</b> k &le; t<sub>i,j</sub><br/><b> Enc(pk, v<sub>i,j</sub>) = [[v<sub>i,j</sub>]] </b> <b>otherwise</b>.<br/><b>C</b> &leftarrow; (<b>C</b><sup>k</sup><sub>i,j</sub>)<sup>k&isin;[0 .. 2<sup>&nu;</sup> &minus; 1]</sup><sub>i&isin;[P],j&isin;[&delta;]</sub></td><td><b>for</b> i &isin; [1 .. P]:<br/><b>for</b> j &isin; [1 .. &delta;]:<br/><b>for</b> k &isin; [0 .. 2<sup>&nu;</sup> &minus; 1]:<br/><b>C</b><sup>k</sup><sub>i,j</sub> = [[0]]<br/><b>C</b> &leftarrow; (<b>C</b><sup>k</sup><sub>i,j</sub>)<sup>k&isin;[0 .. 2<sup>&nu;</sup> &minus; 1]</sup><sub>i&isin;[P],j&isin;[&delta;]</sub></td></tr></tbody></table>

The difference between the two games involves the indistinguishability of the encryption scheme in $P \times \delta \times 2^{\nu}$ ciphertexts. With a classical hybrid proof, one can show this is bounded by $P \cdot \delta \cdot 2^{\nu} \times \text{Adv}_{\mathcal{E}}^{\text{IND-CPA}}(t)$, where $t$ is the running time of the adversary $\mathcal{A}$. Hence, we have

$$ \text{Adv}^{\text{server-privacy}}(\mathcal{A}) \leq (P \cdot \delta \cdot 2^{\nu}) \cdot \text{Adv}_{\mathcal{E}}^{\text{IND-CPA}}(t). $$

This proves that an adversary has negligible advantage when playing the server privacy game.

Those proofs are done in the Honest-but-Curious setting. We now detail how to upgrade our protocol to make it secure against a malicious Client and an Honest-but-Curious Server.

## 3.2 Malicious client and honest-but-curious server

Unfortunately, a malicious client could trivially bias the outcome of the protocol described in Figure 3.3 by setting all the $[[\tilde{S}_i]]$ as encryptions of zeros, independently of his input. Hence, the server will always accept the authentication.

In this section, we describe a protocol providing secure decision forests evaluation even if the client behaves maliciously in order to get accepted, while the server is still honest-but-curious. Our security goals remain unchanged from Section 3.1, however the client may now deviate from
the protocol to influence the evaluation outcome. In order to secure our protocol, we add some
randomness within the model through the notion of *path polarity*, making path expected output
unpredictable. In other words, some paths will be expected to be valid, while other paths will be
expected to be rejected, according to the polarity *p* of the path.

3.2.1 Model encoding

We consider an enriched model $\mathcal{M} = (P, T, \delta, \nu, \tau, (t_{i,j}, v_{i,j}, p_i)_{i \in [P], j \in [\delta]})$, with ternary sequences of comparisons with a polarity $p_i$. Indeed, to be able to exploit the polarity, a path should have three possible outcomes: **accept**, **reject**, **ignore**. The mapping from the score to the outcome is done according to the leaf label and the polarity of the path. The path always ignore when the score is 0. Then, when the label is 1, the path outcomes **accept** if the score equals the polarity, **reject** when they are opposite and vice versa when the label is 0. In figure 3.1, we depict the transition from the classical tree decisoin reprenstation to our reprensetation for encoding, for a malicious client. From a binary tree, such a path is now the path down to the last node of which at least one child node is a decision leaves: on an input **x**, if it does not reach the last node (some comparisons fails before), one outputs 0, otherwise one outputs -1 or +1, whether the leaf is rejecting or accepting. From now, the polarized node of a path denotes the last one.

<figure><img src="image_31.png" /><figcaption>Figure 3.6: Decision tree representation in the malicious setting. The polarized node is in red (resp. blue) when polarity is sampled to -1 (resp 1).</figcaption></figure>

A tree of depth $\delta$ has at most $2^{\delta-1}$ such disjoint paths: an input $\mathbf{x}$ must be accepted or rejected by exactly one path only, all the other paths should output **ignore**. Indeed, as in the plain case, a sample can only reach a single leaf, there is a single path such that the score of the path is 0 when the sample reach the final comparison. It is possible to extract such paths from any binary decision tree, by possibly adding some 'always true'/'always false' nodes to make path of length $\delta$. Such 'always true'/'always false' comparisons will also be added to hide the actually used features. This will lead to an impossibility for the malicious client to predict the outcome of a path from the features used in the comparisons: the client does not know if the comparison is really exploited, and the client does not know the polarity of this path and thus whether it should force +1 or -1 to increase the score.

However, even if the client can not predict the expected outcome of the paths, he may still try
to guess enough of them to get a score higher than the threshold. But as the polarity is random
and hidden (no information leaks, as proven later), the sum of the outputs of a malicious client will
follow a binomial distribution with bias 1/2. And the expected sum of the score is 0. If we set the
threshold not too low, the probability to get accepted is negligible. An alternative is also to add
some 'always accepting' paths, to artificially increase the expected sum of an honest user. With
20 such paths, we can set $\tau = 20$. Let us thus consider 120 paths with a threshold $\tau = 20$ (with either additional 'always accepting' paths, or an initially high threshold): to pass the threshold, one needs 20 correct guesses (probability bounded by $1/10^6$, on exactly 20 non-zero outputs), or at least 70 successes (as if there is at least 70 success, the score passes the threshold) among 120 (probability less than 3%, with random -1/1 outputs). This remains reasonable with respect to usual accuracy of such models. To evaluate a path on an input $\mathbf{x}$, with a ternary result, we do not use the same weights in each comparison: the values encrypted in the $C_{i,j}^k$ will still be 1 or 0 for all the active comparisons up to the polarized one, but the encryption logic is inverted; the polarized node (shown in blue and red on Figure 3.6), will contain $\delta$ or 0, where $\delta$ is the length of the paths. Hereafter, we use $\llbracket m \rrbracket_S$ (respectively $\llbracket m \rrbracket_C$) to denote an encryption of $m$ under the public key of the server (respectively, the client) in order to avoid any confusion with the future encryption made with client's public key. The EncodeModel algorithm is thus updated as follows:

for $i \in [1..P]: \pi \leftarrow \mathcal{G}_{\delta}$

for $k \in [0..2^{\nu}-1]$

for $j \in [1..\delta-1]$:

$$C_{i,\pi(j)}^k = \begin{cases} \llbracket 1 - v_{i,j} \rrbracket_S & \text{if } k \le t_{i,j} \\ \llbracket v_{i,j} \rrbracket_S & \text{otherwise.} \end{cases}$$

$$C_{i,\pi(\delta)}^k = \begin{cases} \llbracket (1+p_i)/2 - v_{i,\delta}p_i \delta \rrbracket_S & \text{if } k \le t_{i,j} \\ \llbracket (1-p_i)/2 + v_{i,\delta}p_i \delta \rrbracket_S & \text{otherwise.} \end{cases}$$

$$C = \text{EncodeModel}(\text{pk}_S, \mathcal{M})$$

### 3.2.2 Protocol overview

When evaluating, if all the comparisons pass, the sum is $2\delta - 1$, if all but the last comparison pass, the sum is $\delta - 1$. In any other case, the sum is between 0 and $\delta - 2$ or $\delta$ and $2\delta - 2$. The idea is to map the score to either $-1$, 0 or 1, according to the mapping depicted in figure 3.7: A score of $2\delta - 1$ will map to $+1$, a score of $\delta - 1$ will map to $-1$, otherwise, the score will map to 0.

<figure><img src="image_32.png" /><figcaption>Figure 3.7: Mapping of a path score</figcaption></figure>

One cannot rely on path permutations anymore to enforce client privacy once path polarity is used. Indeed, the server needs to know for which path a score has been computed in order to later involve the correct path polarity $p_i$. To overcome this issue, we rely on a secure double equality test based on Garbled Circuits along with an Oblivious Transfer, to obliviously convert the above sums between 0 and $2\delta - 1$ into another ciphertext (under the client key) of $+1, -1$ or 0.

First, the client randomizes his scores using a random value $\alpha$, and we denote by $\beta_i$ the resulting encrypted value. Thus, if the score of a branch is $\delta - 1$, we have $\beta = \alpha + \delta - 1$, if the score is $2\delta - 1$, we have $\beta = \alpha = 2\delta - 1$. The Garbled Circuits therefore test the equality between $\alpha + \delta - 1$ (client's input) and both $\beta$ and $\beta - \delta$ (server's inputs). The transition tables are computed as follows: If $\alpha + \delta - 1 = \beta$, the outcome label is an encryption of $+1$ with the client public key ($\llbracket 1 \rrbracket_C$), otherwise, the outcome label is $\llbracket -1 \rrbracket_C$. If $\alpha + \delta - 1 = \beta - \delta$, the outcome label is $-1$ ($\llbracket -1 \rrbracket_C$), otherwise, the outcome label is $\llbracket +1 \rrbracket_C$. The evaluator then homomorphically sums the two values he obtained and multiplies the result by $2^{-1}$. If $\alpha + \delta - 1 = \beta$, the first test returns $\llbracket 1 \rrbracket_C$ and the second one $\llbracket 1 \rrbracket_C$, resulting in a final encryption of $\llbracket (1+1)/2 \rrbracket_C = \llbracket 1 \rrbracket_C$. If $\alpha + \delta - 1 = \beta - \delta$, the first test returns $\llbracket -1 \rrbracket_C$ and the second one $\llbracket -1 \rrbracket_C$, resulting in a final encryption of $\llbracket (-1+(-1))/2 \rrbracket_C = \llbracket -1 \rrbracket_C$. In any other case, the first test returns $\llbracket -1 \rrbracket_C$ and the
second one $[[1]]_C$, resulting in a final encryption of $[[(-1+1)/2]]_C = [[0]]_C$. We use Zero-knowledge Proofs to ensure that one of the label encrypts $-1$ and the other one encrypts $1$.

Once the server computes all the paths scores $S_i$ (that are encrypted with the client public key), he depolarizes them with $p_i$, adds them to a random value $\theta$ resulting in an encryption of $S_{\Omega} \leftarrow \theta + \sum_i p_i \cdot S_i$. Before asking the client to decrypt, we blind the score by using another random value $\xi$, avoiding him to increase its score. Hence, the encrypted value sent to the client is $S_{\Omega} \leftarrow \xi \cdot S_{\Omega}$. The client therefore returns $S_{\Omega}$, from which the server extracts the global score by computing $S \leftarrow \xi^{-1}S_{\Omega} - \theta$. If $S \in [\tau, T]$, where $\alpha$ is the acceptation threshold and $T$ is the number of tree (and the maximal score), the server returns accept, and reject otherwise. A visual representation of the evalution is given in figure 3.8.

<figure><img src="image_33.png" /><figcaption>Figure 3.8: Secure Evaluation (without randomization steps) of one path, with polarity $p = -1$, in the malicious client setting. Red boxes are encryptions of 0, green ones are encryptions of 1 and yellow ones are encryptions of $\delta = 4$. Grey boxes denote the path score along the evaluation</figcaption></figure>

### 3.2.3 Formal description

The client starts by computing the path score $[[S_i]]_S = \bigoplus_j [[S_{i,j}]_S$ as previously and masks it with a random value $\alpha_i \leftarrow \$ Z_p$ in order to obtain $[[\beta_i]]_S = [[\alpha_i + S_i]]_S$. On the one hand, if $(S_i = \delta - 1)$, we have $(\beta_i = \alpha_i + \delta - 1)$ and on the other hand when $(S_i = 2\delta - 1)$ we have $(\beta_i = \alpha_i + 2\delta - 1)$. By consequent, the client generates a Garbled Circuits testing equality of $\beta_i$ with $\alpha_i + \delta - 1$ and with $\alpha_i + 2\delta - 1$ by calling InitializeGC:

for $i \in [1..P]$:

$\alpha_i \leftarrow \$ Z_p$

$\alpha_{input} \leftarrow (\alpha_i + \delta - 1, \alpha_i + 2\delta - 1)$

($\mathfrak{C}_i, \mathfrak{J}_{\alpha_i}^G, \mathfrak{J}_i^E, \mathfrak{T}_i) \leftarrow \text{GC Generate}(\text{pk}_C, \mathcal{C}_{EQ}, \alpha_{input})$

($\alpha, \mathfrak{C}, \mathfrak{J}_{\alpha}^G, \mathfrak{J}_i^E, \mathfrak{T}$) = InitializeGC(pk_C)

More precisely, the algorithm InitializeGC takes as input the public key $pk_C$ of the client, and then, for each path, garbles $\mathcal{C}_{EQ}$, a circuit computing equality tests with two inputs from the client, supposedly being $\alpha_i + \delta - 1$ and $\alpha + 2\delta - 1$ and with $\beta_i$ as server input. The GC Generate algorithm takes $pk_C$ as extra argument compared to its definition in section 2.8.2. Indeed, the
first equality test labels output encryptions of +1 in the positive case and -1 otherwise; while the second ones output encryptions of -1 in the positive case and +1 otherwise. Thus, for each Garbled Circuits, the transition table $\mathcal{T}_i$ is built as follows. As our circuit has two outcomes, $\mathcal{T}_i$ actually contains two transitions tables $\mathcal{T}_i^1$ and $\mathcal{T}_i^2$, each consisting of a pair of encryptions $(\sigma_0, \sigma_1) \in \{(\llbracket -1 \rrbracket_c, \llbracket +1 \rrbracket_c), (\llbracket +1 \rrbracket_c, \llbracket -1 \rrbracket_c)\}$ and a NIZK proof $\zeta$ that the pair contains one encryption of -1 and one encryption of 1:

$$ \mathcal{T} = (\mathcal{T}_i^1, \mathcal{T}_i^2)_{i \in [P]} = ((\mathcal{D}_{i,0}^1, \sigma_{i,0}^1), (\mathcal{D}_{i,1}^1, \sigma_{i,1}^1), \zeta_i^1) ; ((\mathcal{D}_{i,0}^2, \sigma_{i,0}^2), (\mathcal{D}_{i,1}^2, \sigma_{i,1}^2), \zeta_i^2)_{i \in [P]} $$

**Secure Equality Test.** We now describe the circuit used. A Garbled Circuits testing the equality between two $\kappa$-bit values $\alpha$ and $\beta$ can be computed by:

$$ \begin{aligned} (\alpha = \beta) &= (\alpha[\ell] = \beta[\ell], \forall \ell \in [\kappa]) = (\alpha[\ell] \oplus \beta[\ell] = 0, \forall \ell \in [\kappa]) \\ &= \left( \bigwedge_{\ell=1}^{\kappa} (\overline{\alpha[\ell] \oplus \beta[\ell]}) = 1 \right) = \left( \bigwedge_{\ell=1}^{\kappa} (\alpha[\ell] \oplus \overline{\beta[\ell]}) = 1 \right). \end{aligned} $$

Each equality test requires $\kappa$ XOR-gates and $\kappa - 1$ AND-gates. Using the free-XOR and half-gates optimizations, such an equality test can be computed using $2(\kappa - 1)$ ciphertexts. One may compare hashed values of $\alpha$ and $\beta$, of shorter length, at the cost of possibly false positive cases. To avoid the computation of the negation of bits of $\beta$, the evaluator will simply set the bits of $\overline{\beta}$ as inputs for the incoming Oblivious Transfers. The circuit the client garbles is two parallel equality tests, where equality is tested bitwise.

<figure><img src="image_34.png" /><figcaption>Figure 3.9: Circuit to compute a dual equality test, where $\beta$ is tested with $\alpha_1$ and $\alpha_2$, and inputs are $\ell$ bits long. XOR gates are depicted in blue while AND gates are maroon.</figcaption></figure>

The algorithm InitializeGC returns $\alpha = (\alpha_i)_{i \in [P]}$, $\mathcal{C} = (\mathcal{C}_i)_{i \in [P]}$ the set of garbling of the circuit $C_{EQ}, \mathcal{J}_{\alpha}^{\mathcal{G}}$, the set of pair of input labels corresponding to the inputs $\alpha_{input}, \mathcal{J}^{\mathcal{E}}$ the labels for the server's inputs and the set of transition tables $\mathcal{T}$.

After initializing the Garbled Circuits, the client now evaluates the paths with his data $\mathbf{x}$ by calling EvaluatePaths. To evaluate a path, the client retrieves the required ciphertexts $C_{i,j}^{x}$ in the encoded model $\mathcal{C}$ and sums them using the server public key $pk_S$. Then, he randomizes the score by adding to it the random value $\tilde{\alpha}_i$ returned by the algorithm InitializeGC. At the end of the evaluation, the client gets a set $\beta = (\llbracket \beta_i \rrbracket_S)_{i \in [P]}$ of randomized and encrypted scores.

for $i \in [1..P]$:

for $j \in [1..\delta]$: $\llbracket S_{i,j} \rrbracket_S = C_{i,j}^{x}$

$$ \llbracket \beta_i \rrbracket_S = \llbracket \alpha_i \rrbracket_S \boxplus (\boxtimes_j \llbracket S_{i,j} \rrbracket_S) $$

$$ \beta \leftarrow (\llbracket \beta_i \rrbracket_S)_{i \in [P]} $$

$$ \beta = \text{EvaluatePaths}(pk_S, \mathbf{x}, \alpha, \mathcal{C}) $$
The client sends his public encryption key pk<sub>C</sub>, the set β of encrypted scores, and the Garbled Circuits material. The server first verifies the consistency of the transition table ≀≀ by testing all the underlying NIZK (ζ<sub>i</sub><sup>J</sup>)<sub>i∈[P], j∈{1,2}</sub> and aborts if any verification fails. Otherwise, the server obtains β<sub>i</sub> by decrypting [[β<sub>i</sub>]]<sub>S</sub> and retrieves the corresponding circuit inputs using OTs. Thus, as the Garbled Circuits takes β&#773;<sub>i</sub> as input, the server encodes the bits of β&#773;<sub>i</sub> for i ∈ [P] and obtain β&#771;. As the message space of the AHE scheme is Z<sub>q</sub>, we assume the size of β<sub>i</sub> is q. The aforementioned process is denoted EncodeOT and is formally described in this way:

$$
\begin{align*}
\textbf{if} \ \mathrm{ZK.Vf}(\mathfrak{T}) \neq 1 : \mathbf{return} \perp \\
\textbf{for} \ i \in [1 \dots P] : \beta_i = \mathrm{Dec}(\mathrm{sk}_S, [[\beta_i]]_S) \\
\quad \textbf{for} \ k \in [1 \dots q] : \tilde{\beta}_i^k = \mathrm{OT Encode}(\beta_i[k]) \\
\quad \quad \tilde{\beta} = \mathrm{EncodeOT}(\mathfrak{T}, \mathrm{sk}_S, \beta = ([\beta_i]_S)_{i \in [P]})
\end{align*}
$$

In the ElGamal setting, one may use g<sup>β<sub>i</sub></sup> instead of β<sub>i</sub> for the comparisons, which avoids the server to compute a discrete logarithm during the decryption.

After receiving the set of encoded bits $\tilde{\beta}$ from the server, the client encodes the server's labels $\mathfrak{T}^E$ using them, resulting in $\tilde{\mathfrak{T}}^E$. Those encoded labels are then sent to the server.

$$
\begin{align*}
\textbf{for } i \in [1 \dots P] \\
\quad \textbf{for } k \in [1 \dots q] : \\
\quad \quad \tilde{\mathfrak{T}}_{i,k}^E \leftarrow \text{OT Compute}(\tilde{\mathfrak{T}}_i^E, \tilde{\beta}_i^k) \\
\quad \quad \phantom{\tilde{\mathfrak{T}}_{i,k}^E \leftarrow \text{OT Compute}(\tilde{\mathfrak{T}}_i^E, \tilde{\beta}_i^k)} \tilde{\mathfrak{T}}^E = \text{ComputeOT}(\mathfrak{T}^E, \tilde{\beta})
\end{align*}
$$

Once the server is in possession of its encoded labels, it proceeds to the score computation. The score is first set as an encryption of a random $\theta \in \mathbb{Z}_q$. This is required for the future shared decryption. Then for every path $i \in [P]$, the server decodes its labels, and input them to $\mathfrak{C}_i$ together with the client's input and the transition table. If any of the circuit evaluation fails, the global score $S_\Omega$ is set as a random value such that the final output is random, to avoid failure attacks. For every successful circuit, the output is a pair $(\sigma_0, \sigma_1)$ of ciphertexts where $\sigma_b \in \{[[-1]]_C, [[1]]_C\}$. Then, the server homomorphically computes the polarized score of the path, by computing $\sigma_0 \boxtimes \sigma_1$. The server multiplies it by $2^{-1}p_i$, where $p_i$ is the polarity of the branch $i$, resulting in a ciphertext in $\{[[-1]]_C, [[0]]_C, [[1]]_C\}$, and add the result to $[[S_\Omega]]_C$. Lastly, the score is randomly blinded using $\xi \leftarrow \$ \mathbb{Z}_p^*$. Hence, $S_\Omega = \xi \cdot (\theta + \sum p_i \cdot S_i)$.

$$
\begin{align*}
\theta &\leftarrow \$ \mathbb{Z}_p; \quad [[S_\Omega]]_C \leftarrow [[\theta]]_C \\
\textbf{for } i \in [1 \dots P] : & \\
& \quad \textbf{for } k \in [1 \dots q] : \mathfrak{J}_{\beta_i^k}^E \leftarrow \text{OT.Decode}(\tilde{\mathfrak{J}}_{i,k}^E) \\
& \quad \textbf{if } \text{GC.Eval}(\mathfrak{C}_i, \mathfrak{J}_{\alpha_i}^G, \mathfrak{J}_{\beta_i}^E, \mathfrak{T}_i) = \perp \\
& \quad \quad \theta' \leftarrow \$ \mathbb{Z}_p \\
& \quad \quad \phantom{\theta' \leftarrow \$} [[S_\Omega]]_C \leftarrow [[\theta')]_C \\
& \quad \textbf{else } (\sigma_0, \sigma_1) \leftarrow \text{GC.Eval}(\mathfrak{C}_i, \mathfrak{J}_{\alpha_i}^G, \mathfrak{J}_{\beta_i}^E, \mathfrak{T}_i) \\
& \quad \quad [[S_\Omega]]_C \leftarrow [[S_\Omega]]_C \boxtimes (2^{-1} p_i \boxtimes (\sigma_0 \boxtimes \sigma_1)) \\
& \quad \xi \leftarrow \$ \mathbb{Z}_q^* \\
& \quad \phantom{\xi \leftarrow \$} [[S_\Omega]]_C \leftarrow \xi \boxtimes [[S_\Omega]]_C \\
& \quad \phantom{\xi \leftarrow \$} ([[S_\Omega]]_C, \theta, \xi) = \text{ComputeScore}(\text{pk}_C, \mathcal{M}, \mathfrak{C}, \mathfrak{J}_\alpha^G, \tilde{\mathfrak{J}}^E, \mathfrak{T})
\end{align*}
$$

Now, the server will ask the client to decrypt this ciphertext. It is risk-free as $\xi$ avoid the client to increase his score, while $\theta$ considerably reduces the chances for the adversary to guess $\xi$. Hence, the slightest modification leads to a random score.

$$
\begin{align*}
\tilde{S}_{\Omega} &\leftarrow \mathrm{Dec}(\mathrm{sk}_{\mathrm{C}}, [[S_{\Omega}]_{\mathrm{C}}]) \\
S_{\Omega} &= \mathrm{DecryptScore}(\mathrm{sk}_{\mathrm{C}}, [[S_{\Omega}]_{\mathrm{C}}])
\end{align*}
$$
Once the client has decrypted the score $S_\Omega$, he sends it back to the server, who make it back to a value in $[0..P]$. First, he removes the blinding factor $\xi$ and subtracts the initial random score $\theta$. Then, the server acts according to the score, the threshold and the number of trees $T$ (as at most one path by tree returns 1).

<figure><img src="image_35.png" /><figcaption>Figure 3.10 described the resulting protocol.</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>Figure 3.10: Secure Decision Forest Evaluation Protocol with malicious client</figcaption></figure>

### 3.2.4 Protocol security

**Correctness and Soundness.** Thanks to the polarity, the server is ensured that the client can no more arbitrarily choose the outcome of a path. Indeed, in contrast to the honest-but-curious case where expected paths values were zero, the expected value sent to the server (the outcome of the Garbled Circuits) will depend on the path polarity and the initial leaf value. With $p$ denoted the path polarity, if the leaf value is 0, the expected output is $-p$, and $p$ if the initial leaf value is 1. If the score is 0, the server will ignore the path. The paths cannot all be ignored, otherwise, there is no chance to be above the threshold $\tau$, hence preventing the two extreme attacks presented before: either the client specifically guesses $\tau$ values to be correct, and set all the other to zero (with a success probability bounded by $2^{-\tau}$), or the client tries non-zero values for all the outputs and the success probability follows a binomial distribution with parameters $(P, 1/2)$, where the number of successes must be greater than $(P + \tau)/2$.

The Garbled Circuits will evaluate the initial scores before polarity, and the unknown polarity bit $p_i$ will restore the exact outcome of the path. We show in table 3.11 the correctness of the mapping from a path score to an encryption of either $-1, 0$ or $1$. A malicious client has no other choice than a random guess of the polarity to fake the output labels of the Garbled Circuits. He could cheat with a bad encoding of the circuit to bias the output, but only with $+1/-1$ or $-1/+1$ as the output table is proven to contain encryptions of $+1$ and $-1$ with a zero-knowledge proof. But since the player has no idea about the polarity bit $p_i$, the final outcome for the path is $-1$ or
<table><caption>Figure 3.11: Mapping Correctness</caption><thead><tr><th>Path Polarity p<sub>i</sub></th><th colspan="2">-1</th><th colspan="2">1</th></tr></thead><tbody><tr><td>(&alpha;<sub>i</sub> + &delta; - 1 = &beta;<sub>i</sub>)</td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><td>GC Outcome &sigma;<sub>0</sub></td><td>[[1]]<sub>c</sub></td><td>[[&minus;1]]<sub>c</sub></td><td>[[1]]<sub>c</sub></td><td>[[&minus;1]]<sub>c</sub></td></tr><tr><td>(&alpha;<sub>i</sub> + &delta; - 1 = &beta;<sub>i</sub> &minus; &delta;)</td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><td>GC Outcome &sigma;<sub>1</sub></td><td>[[&minus;1]]<sub>c</sub></td><td>[[1]]<sub>c</sub></td><td>[[&minus;1]]<sub>c</sub></td><td>[[&minus;1]]<sub>c</sub></td></tr><tr><td>(2<sup>&minus;1</sup>p<sub>i</sub>) &#8707; (&sigma;<sub>0</sub> &#8708; &sigma;<sub>1</sub>)</td><td>[[0]]<sub>c</sub></td><td>[[&minus;1]]<sub>c</sub></td><td>[[1]]<sub>c</sub></td><td>[[0]]<sub>c</sub></td></tr><tr><td>Expected Output</td><td>0</td><td>&minus;1</td><td>1</td><td>0</td></tr></tbody></table>

+1 with identical probability, if positive and negative polarities are balanced. Hence, alteration of the result of a path, without knowing the polarity, will make the sum closer to 0. If the threshold is not too close to 0, the probability for the adversary to impersonate the user is negligible. More generally, the impact of the malicious behavior of the client on false positive outcome will be small, compared to initial accuracy of the system (in clear).

Of course, another cheating strategy can be sending a false zero-knowledge proof or wrong ciphertexts for the Garbled Circuits gates. This would lead to failure attacks with a random value in $S_{\Omega}$ (enforced in the protocol). Similarly, an incorrect decryption of $[[S_{\Omega}]]_{c}$ would lead to a random value for $\xi^{-1} \cdot S_{\Omega} - \theta$, with the detection probability greater than $1 - T/p$, which is overwhelming. This concludes in a reject.

As a consequence, we just have to take care of the accuracy of the model in the clear, for an honest execution, and we will also have to consider the impact of malicious behaviours on the false positive decisions, which is the most critical in the case of continuous authentication. In some other applications, false negative decisions might be more important to limit (such as for spam detection).

**Client Privacy.** We are still considering the client privacy against an honest-but-curious server. However, in this protocol, we no longer use permutations, because of the path polarity. Nonetheless, from the client privacy of the Oblivious Transfers in the Garbled Circuits, there is no leakage about the $\alpha_i$'s. Then the outcome $S_i$ of the path is encrypted under the client key, which hides it from the server. Eventually, the server only gets the decryption of $\sum_i S_i$, which is the number of accepting trees, the expected result to obtain the classification with confidence score.

The advantage of an adversary in the Exp$^{client-privacy-b}(\kappa, \mathcal{A})$ experiment (see Figure 3.4) is defined as

$$ \mathrm{Adv}^{\mathrm{client-privacy}}(\mathcal{A}) = \left| \Pr[\mathrm{Exp}^{\mathrm{client-privacy}-1}(\kappa, \mathcal{A}) = 1] - \Pr[\mathrm{Exp}^{\mathrm{client-privacy}-0}(\kappa, \mathcal{A}) = 1] \right|. $$

**Game $G_0$.** The first game is the actual security game, with the execution of the protocol between the client with input $x_b$ and the server with input $(\mathcal{M}, \rho)$. We thus detail the Execute procedure:
Execute

1. $(pk_S, sk_S) = KGen(1^\kappa; \rho)$

2. $C \leftarrow EncodeModel(pk_S, M; \rho)$

3. $(pk_C, sk_C) = KGen(1^\kappa)$

4. $(\alpha, C, \mathfrak{J}_\alpha^G, \mathfrak{J}^E, \mathfrak{T}) \leftarrow InitializeGC(pk_C)$

5. $\beta \leftarrow EvaluatePaths(pk_S, x_b, \alpha, C)$

6. $\tilde{\beta} \leftarrow EncodeOT(\mathfrak{T}, sk_S, \beta; \rho)$

7. $\tilde{\mathfrak{J}}^E \leftarrow ComputeOT(\mathfrak{J}^E, \tilde{\beta})$

8. $([S_\Omega]^c, \theta, \xi) \leftarrow ComputeScore(pk_C, C, \mathfrak{J}_\alpha^G, \tilde{\mathfrak{J}}^E, \mathfrak{T}; \rho)$

9. $S_\Omega \leftarrow DecryptScore(sk_C, [S_\Omega]^c)$

10. $\text{result} \leftarrow ComputeResult(\theta, \xi, S_\Omega)$

11. transcript $\leftarrow (pk_S, C, pk_C, \beta, C, \mathfrak{J}_\alpha^G, \mathfrak{T}, \tilde{\beta}, \tilde{\mathfrak{J}}^E, [S_\Omega]^c, S_\Omega, \text{result})$

**Game** $G_1$. For the first game, the client simply returns the expected $S_\Omega$ to the server instead of genuinely decrypting the received value. This value is indeed known by the simulator who can retrieve $S_\Omega$ from the inputs $(x_0, x_1)$ and $M$. Therefore, the simulator can add the random value $\theta$ to $S_\Omega$ and multiply the result by $\xi$ (from the random coins) in order to retrieve $S_\Omega$. We recall that the number of successful paths is a tolerated leakage. As previously, such a change avoids the call to the decryption procedure, and thus the need of the decryption key $sk_C$.

<table><thead><tr><th>DecryptScore(sk<sub>C</sub>, [[S<sub>Ω</sub>]<sub>D</sub>])</th><th>DecryptScore'(S<sub>Ω</sub>)</th></tr></thead><tbody><tr><td>S<sub>Ω</sub> ← Dec(sk<sub>C</sub>, [[S<sub>Ω</sub>]<sub>C</sub>])</td><td>return S<sub>Ω</sub></td></tr></tbody></table>

In this game, $\mathcal{A}$ does not gain any advantage as the output is exactly the same with both functions.

**Game** $G_2$. In this game, we introduce InitializeGC' who acts as InitializeGC except that the transition table outputs contains encryptions of random values with simulated NIZKs.

<table><thead><tr><th>InitializeGC(pk<sub>C</sub>)</th><th>InitializeGC'(pk<sub>C</sub>)</th></tr></thead><tbody><tr><td><strong>for</strong> i ∈ [1 .. P]:<br>α<sub>i</sub> ← $Z_p$<br>α<sub>input</sub> ← (α + δ − 1, α + 2δ − 1)<br>(C<sub>i</sub>, J<sub>α<sub>i</sub></sub><sup>G</sup>, J<sub>i</sub><sup>E</sup>, J<sub>i</sub><sup>T</sup>) ← GC.Generate(pk<sub>C</sub>, C<sub>EQ</sub>, α<sub>i</sub>)<br><br><strong>return</strong> (α, C, J<sub>α</sub><sup>G</sup>, J<sup>E</sup>, J)</td><td><strong>for</strong> i ∈ [1 .. P]:<br>α<sub>i</sub> ← $Z_p$<br>α<sub>input</sub> ← (α + δ − 1, α + 2δ − 1)<br>(C<sub>i</sub>, J<sub>α<sub>i</sub></sub><sup>G</sup>, J<sub>i</sub><sup>E</sup>, J<sub>i</sub><sup>T</sup>) ← GC.Generate(pk<sub>C</sub>, C<sub>EQ</sub>, α<sub>i</sub>)<br><br><strong>for</strong> j ∈ {1, 2}<br>r<sub>0</sub>, r<sub>1</sub> ← $Z_q$<br>tilde{J}<sub>i</sub><sup>j</sup> ← ((D<sub>i,0</sub><sup>j</sup>, [[r<sub>0</sub><sup>j</sup>]<sub>C</sub>), (D<sub>i,1</sub><sup>j</sup>, [[r<sub>1</sub><sup>j</sup>]<sub>C</sub>), ζ<sub>i</sub><sup>j</sup>)<br><br><strong>return</strong> (α, C, J<sub>α</sub><sup>G</sup>, J<sup>E</sup>, J)</td></tr></tbody></table>

The advantage of $\mathcal{A}$ in this game relies on the IND-CPA property of the AHE scheme, so this advantage is bounded by $Adv_{\mathcal{E}}^{\text{IND-CPA}}(t)$.

**Game** $G_3$. For this game, we use ComputeOT' who takes $\beta = (\beta_i)_{i \in [P]}$ as input and replaces the labels not corresponding to the evaluator's input by a random label.
((P, T, δ, ν, **p**₀, **t**₀, **v**₀, τ₀), (P, T, δ, ν, **p**₁, **t**₁, **v**₁, τ₁)) with the same constraints as in the honest-but-curious case. We stress that the client random coins are not given anymore. We denote the advantage of any adversary A by:

$$ \mathrm{Adv}^{\mathrm{server-privacy}}(\mathcal{A}) = \left| \Pr[\mathrm{Exp}^{\mathrm{server-privacy}-1}(\kappa, \mathcal{A}) = 1] - \Pr[\mathrm{Exp}^{\mathrm{server-privacy}-0}(\kappa, \mathcal{A}) = 1] \right|. $$

<figure><img src="image_37.png" /><figcaption>Figure 3.12: Server-Privacy Security Game in the Malicious Setting</figcaption></figure>

**Game G₀.** The first game is the actual security game, with the execution of the protocol between the client with input **x** and the server with input $M_b$. We thus detail the Execute procedure:

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

**Game G₁.** In order to prepare the next game, we use a variant ComputeResult' of ComputeResult, which only takes as input the final global outcome result = ($M_0(\mathbf{x}) \ge \tau_0$) = ($M_1(\mathbf{x}) \ge \tau_1$) as well as the larger range $[0, P]$ instead of $[\tau_b, P]$ in order to output the final outcome.

<table><thead><tr><th>ComputeResult(M<sub>b</sub>, θ, ξ, S<sub>Ω</sub>)</th><th>ComputeResult'(θ, ξ, S<sub>Ω</sub>, result)</th></tr></thead><tbody><tr><td>S<sub>Ω</sub> &larr; ξ<sup>-1</sup> &middot; S<sub>Ω</sub> &minus; θ</td><td>S<sub>Ω</sub> &larr; ξ<sup>-1</sup> &middot; S<sub>Ω</sub> &minus; θ</td></tr><tr><td>if S<sub>Ω</sub> &isin; [&tau;<sub>b</sub>, P] : result = 1</td><td>if S<sub>Ω</sub> &isin; [0, P] : result = 1</td></tr><tr><td>else result = 0</td><td>else result = 0</td></tr></tbody></table>

In case the adversary cheats during the decryption, because of the random values θ, ξ, the probability this change impacts the view of the adversary is less than $\tau_b/q$, and thus less than $P/q$, which is negligible.
**Game G₂.** For this game, instead of genuinely run ComputeScore to compute $[[S_\Omega]]_C$, the latter is set to an encryption of $\theta$ by the function ComputeScore'. If $\mathcal{A}$ decrypts both values, he won't be able to distinguish between them as both values are indistinguishable from random values.

<table><thead><tr><th>ComputeScore(pk<sub>C</sub>, M<sub>b</sub>, C, J<sub>α</sub><sup>G</sup>, J̃<sub>β</sub><sup>E</sup>, J̃<sub>τ</sub>)</th><th>ComputeScore'()</th></tr></thead><tbody><tr><td>θ &larr; $\mathbb{Z}_p$; [[S<sub>Ω</sub>]]<sub>C</sub> &larr; [[θ]]<sub>C</sub><br>for i &isin; [1 .. P] :<br>for k &isin; [1 .. q] : J<sub>β<sub>i</sub></sub><sup>E</sup> &larr; OT.Decode(J̃<sub>i,k</sub><sup>E</sup>)<br>if GC.Eval(C<sub>i</sub>, J<sub>α<sub>i</sub></sub><sup>G</sup>, J<sub>β<sub>i</sub></sub><sup>E</sup>, J̃<sub>i</sub>) =⊥:<br>θ' &larr; $\mathbb{Z}_p<br>[[S<sub>Ω</sub>]]<sub>C</sub> &larr; [[θ']]<sub>C</sub><br>else (σ<sub>0</sub>, σ<sub>1</sub>) &larr; GC.Eval(C<sub>i</sub>, J<sub>α<sub>i</sub></sub><sup>G</sup>, J<sub>β<sub>i</sub></sub><sup>E</sup>, J̃<sub>i</sub>)<br>[[S<sub>Ω</sub>]]<sub>C</sub> &larr; [[S<sub>Ω</sub>]]<sub>C</sub> &oplus; (2<sup>-1</sup>p<sub>i</sub> &otimes; (σ<sub>0</sub> &oplus; σ<sub>1</sub>))<br>ξ &larr; $\mathbb{Z}_p<br>[[S<sub>Ω</sub>]]<sub>C</sub> &larr; ξ &otimes; [[S<sub>Ω</sub>]]<sub>C</sub><br>return ([[S<sub>Ω</sub>]]<sub>C</sub>, θ, ξ)</td><td>θ &larr; $\mathbb{Z}_p$; [[S<sub>Ω</sub>]]<sub>C</sub> &larr; [[θ]]<sub>C</sub><br>ξ &larr; $\mathbb{Z}_p<br>[[S<sub>Ω</sub>]]<sub>C</sub> &larr; ξ &otimes; [[S<sub>Ω</sub>]]<sub>C</sub><br>return ([[S<sub>Ω</sub>]]<sub>C</sub>, θ, ξ)</td></tr></tbody></table>

**Game G₃.** In order to prepare the next game, we use a variant EncodeOT' of EncodeOT, which outputs encodings of random values. Due to Oblivious Transfers privacy properties, this game is indistinguishable from the previous one.

<table><thead><tr><th>EncodeOT(sk<sub>S</sub>, [[S]]<sub>S</sub>)</th><th>EncodeOT'()</th></tr></thead><tbody><tr><td>if ZKVf(J̃) ≠ 1 : return ⊥<br>for i &isin; [1 .. P] : β<sub>i</sub> = Dec(sk<sub>S</sub>, [[S<sub>i</sub>]]<sub>S</sub>)<br>for k &isin; [1 .. q] :<br>β̃<sub>i</sub><sup>k</sup> = OT Encode(β<sub>i</sub>[k])<br>return β̃</td><td>if ZKVf(J̃) ≠ 1 : return ⊥<br>for i &isin; [1 .. P] :<br>for k &isin; [1 .. q] :<br>β̃<sub>i</sub><sup>k</sup> = OT Encode(b &larr; $\mathbb{Z}_2$)<br>return β̃</td></tr></tbody></table>

As OT provides receiver privacy against an honest-but-curious sender, the advantage of $\mathcal{A}$ is bounded by $Adv_{\text{OT}}^{\text{ind}_R}(\mathcal{A})$

**Game G₄.** This game is the same as the game G₁ for the server privacy in the honest-but-curious model. We can similarly show that advantage of $\mathcal{A}$ is bounded by $N \cdot \delta \cdot 2^\nu \times \text{Adv}_\mathcal{E}^{\text{IND-CPA}}(t)$, where $t$ is the running time of the adversary $\mathcal{A}$.

Finally, when using EncodeModel', EncodeOT', ComputeScore' and ComputeResult', the global advantage $Adv^{\text{server-privacy}}(\mathcal{A})$ of the adversary $\mathcal{A}$ is bounded by $(N \cdot \delta \cdot 2^\nu) \cdot \text{Adv}_\mathcal{E}^{\text{IND}}(t) + \text{Adv}_{\text{OT}}^{\text{ind}_R}(\mathcal{A}) + N/p$.

## 3.3 Performances and applications

In this section, we detail the storage and communication costs of our protocols, and compare them with related works. We then show the accuracy of those protocols on a well-known database, namely spambase [HRFS99], and an authentication database.

### 3.3.1 Storage and bandwidth costs

In this section, we describe the storage and bandwidth cost of our protocols. Let $\lambda_{\text{OT}}^R = |\tilde{b}| = |\text{OT Encode}(b)|$, $\lambda_{\text{OT}}^S = |\text{OT Compute}(\tilde{b})|$ and $\lambda_{\text{AHE}} = |[[m]]_S| = |[[m]]_C|$.
**Offline storage cost.** Encoding of the model consists in computing a ciphertext for the $2^\nu$ possible values, for the $\delta$ comparisons of the $P$ paths. Thus, the client stores $2^\nu \cdot \delta \cdot P$ ciphertexts, leading to $2^\nu \cdot \delta \cdot P$ bits to store. Table 3.1 presents the storage cost of $C$ with respect to different model parameters. We use lifted ElGamal with Elliptic Curves and $q$ over 256 bits as $\kappa = 128$, thus, $\lambda_{AHE} = 512$. With inputs over $\nu \in [2, \dots, 8]$ bit, depth $\delta \in [2, \dots, 16]$, and $P$ ranging from 10 to 100, the storage is between a few Kilobytes (KB) and a few Megabytes (MB).

<table><thead><tr><th>P</th><th colspan="3">10</th><th colspan="3">25</th></tr><tr><th>δ</th><th>ν</th><th>2</th><th>4</th><th>8</th><th>2</th><th>4</th><th>8</th></tr></thead><tbody><tr><td>2</td><td>5 KB</td><td>20 KB</td><td>320 KB</td><td>12.5 KB</td><td>50 KB</td><td>800 KB</td></tr><tr><td>4</td><td>10 KB</td><td>40 KB</td><td>640 KB</td><td>25 KB</td><td>100 KB</td><td>1.56 MB</td></tr><tr><td>8</td><td>20 KB</td><td>80 KB</td><td>1.28 MB</td><td>50 KB</td><td>200 KB</td><td>3.13 MB</td></tr><tr><td>16</td><td>40 KB</td><td>160 KB</td><td>2.56 MB</td><td>100 KB</td><td>400 KB</td><td>6.25 MB</td></tr></tbody></table>

<table><caption>Table 3.1: Communication and Storage during the Offline Phase</caption><thead><tr><th>P</th><th colspan="3">50</th><th colspan="3">100</th></tr><tr><th>δ</th><th>ν</th><th>2</th><th>4</th><th>8</th><th>2</th><th>4</th><th>8</th></tr></thead><tbody><tr><td>2</td><td>25 KB</td><td>100 KB</td><td>1.56 MB</td><td>50 KB</td><td>200 KB</td><td>3.13 MB</td></tr><tr><td>4</td><td>50 KB</td><td>200 KB</td><td>3.13 MB</td><td>100 KB</td><td>400 KB</td><td>6.25 MB</td></tr><tr><td>8</td><td>100 KB</td><td>400 KB</td><td>6.25 MB</td><td>200 KB</td><td>800 KB</td><td>12.50 MB</td></tr><tr><td>16</td><td>200 KB</td><td>800 KB</td><td>12.50 MB</td><td>400 KB</td><td>1.60 MB</td><td>25 MB</td></tr></tbody></table>

**Online Storage Cost.** When honest, the client sends $P$ ciphertexts (one for each path score) to the server. Using the lifted ElGamal AHE, the message sent by the client is of size $P \cdot 512$ bits (see Table 3.2).

When malicious, the client sends $P$ tuples, each formed with a ciphertext of size $\lambda_{AHE}$ as the path score along with the AND-gate ciphertexts. As seen in Figure 3.9, a double comparison circuit with $\ell$ bits length inputs consists in $2(\ell - 1)$ AND gates. To reduce communication costs, we use a hash function on the Garbled Circuits inputs to be compared, with output length $\lambda_{GC}$. Thus, the client will send $2(\lambda_{GC} - 1)$ pairs of $\kappa_H$-bit hash values (using HalfGates optimization), the $2\lambda_{GC}$ input labels (where each label has size $\kappa_H$) and the transition table consisting in 4 output labels, 4 AHE ciphertexts, and $2\lambda_{ZK}$-bit length zero knowledge proofs.

This results for each path in the following bit-length:

$$ \underbrace{\lambda_{AHE}}_{||\beta_i||_C} + \underbrace{2\kappa_H \cdot 2(\lambda_{GC} - 1)}_{|e_i|} + \underbrace{2 \cdot \lambda_{GC} \cdot \kappa_H}_{|\alpha_i^G|} + \underbrace{4 \cdot (\kappa_H + \lambda_{AHE})}_{|\Sigma_i|} + \underbrace{2\lambda_{ZK}}_{|\Sigma_i|} $$

which is $5\lambda_{AHE} + 6\lambda_{GC} \cdot \kappa_H + 2\lambda_{ZK}$. With $\kappa_H = 256$, $\lambda_{GC} = 64$, $\lambda_{AHE} = 512$ and $\lambda_{ZK} = 128$, the client first message can be expressed as 101120 bits, i.e. $\approx 12.3$ KB per path. During the Oblivious Transfers, the server encodes $P \times |\beta_i| = P \cdot \lambda_{GC}$ bits. As a consequence, he sends to the client a message of $P \cdot \lambda_{GC} \cdot \lambda_{OT}^R$ bits. Using classical ElGamal as PKE in the Oblivious Transfer, one has $\lambda_{OT}^R = 512$ and $\lambda_{OT}^S = 1024$ resulting in a 4 KB long message for each path. The client responds with a $P \cdot \lambda_{GC} \cdot \lambda_{OT}^S$ bit long message corresponding to 8 KB per path. Then, the server sends the encrypted randomized score to the client who returns the plaintext value he retrieves when decrypting. Table 3.2 shows the total bandwidth cost for each party in both protocols, according to the number $P$ of paths.
<table><caption>Table 3.2: Communications During the Online Phase.</caption><thead><tr><th>P</th><th>50</th><th>100</th><th>150</th><th>200</th></tr></thead><tbody><tr><td colspan="5">Honest-but-Curious</td></tr><tr><td>Client</td><td>3.13 KB</td><td>6.25 KB</td><td>9.38 KB</td><td>12.5 KB</td></tr><tr><td>Server</td><td colspan="4">0 bit</td></tr><tr><td colspan="5">Malicious</td></tr><tr><td>Client</td><td>1 MB</td><td>2 MB</td><td>3 MB</td><td>4 MB</td></tr><tr><td>Server</td><td>200 KB</td><td>400 KB</td><td>600KB</td><td>800KB</td></tr></tbody></table>

### 3.3.2 Comparison with related works

Several approaches have been proposed in order to securely evaluate decision trees [BPSW07, BFK+09, BPTG15, WFNL16, TMZC17, DDH+16, TKK19]. However, most of these constructions are either only secure in the honest-but-curious setting or tailored for decision tree evaluation rather than decision forest evaluation. As such, except [WFNL16] and [TMZC17] which we consider hereafter, the aforementioned works cannot be compared to our protocol meaningfully. Similarly to our protocol, both [WFNL16] and [TMZC17] rely on Additive Homomorphic Encryption (AHE) and Oblivious Transfers (OT). In addition, our protocol also uses Garbled Circuits (GC) in the malicious setting.

A major difference between our protocol and existing constructions is that we rely on the server sending its encrypted model to the client rather than the client sending its encrypted data to the server. This strongly impacts the design of our protocol and allows us to introduce a preprocessing phase that can be performed offline and leveraged later during the online phrase. This is advantageous for several use-cases such as the continuous authentication one as it offers a trade-off between the number of rounds required to execute the protocol and the required bandwidth.

All existing constructions leak some information with respect to the model structure (i.e., on the server side) whether it be its total number of nodes $M$, the total number of comparison nodes $m$ or the maximal depth $\delta$ of the trees. In our protocol, the client may also learn which features will be used to evaluate the trees. We consider this as a privacy leak, but as our protocols will have a complexity independent of the depth of the trees (or more precisely, the length of the paths down to the leaves), we will be able to add dummy comparisons with dummy features, which will completely hide which are the actually used features. We thus propose two variants of our protocols in Table 3.3, without (version 1) or with dummy comparisons (version 2). They only differ during the offline step as the number of features in the comparisons impacts the communication and the storage: $\delta$ is the number of real features per path, whereas $\chi$ is the number of real and dummy features. We stress that this modification does not impact the online step of our protocols: communication only depends on the number $P$ of paths, and not their length. This thus allows us to use as many dummy features as we want to hide the trees and the forest structure. This will be a crucial property for the privacy of the model. In addition, our constructions also feature some leakage on the client side. When used to evaluate decision forests, our protocol leaks the number of successful paths within the forest which constitutes a tolerated leakage in our targeted application. Indeed, it corresponds to the number of accepting trees which allows to compute a confidence level associated to the result.

One can note half rounds in our constructions, which mean one-way flows, from the sender to the recipient. Indeed, most of our schemes are actually non-interactive. Since our goal is to provide the result to the server, in the malicious setting, we get a 5-flow protocol.
<table><caption>Table 3.3: Comparison to state-of-the-art. Protocol 1 offers a weaker feature protection compared to Protocol 2 that hides features using dummy comparisons.</caption><thead><tr><th>Scheme</th><th>Rounds</th><th>Tools</th><th>Bandwidth</th></tr></thead><tbody><tr><td colspan="4" style="text-align: center; font-weight: bold;">Honest-but-Curious model</td></tr><tr><td>[WFNL16]</td><td>6</td><td>AHE+OT</td><td>O(m)</td></tr><tr><td>[TMZC17]</td><td>4</td><td>AHE+OT</td><td>O(m)</td></tr><tr><td>Section 3.1 (Offline) - 1</td><td rowspan="2">0.5</td><td rowspan="3">AHE</td><td>O(m · δ · 2<sup>ν</sup>)</td></tr><tr><td>Section 3.1 (Offline) - 2</td><td>O(m · χ · 2<sup>ν</sup>)</td></tr><tr><td>Section 3.1 (Online)</td><td>0.5</td><td>O(P)</td></tr><tr><td colspan="4" style="text-align: center; font-weight: bold;">Malicious model</td></tr><tr><td>[WFNL16]</td><td>2</td><td>AHE+OT</td><td>O(M)</td></tr><tr><td>[TMZC17]</td><td>4</td><td>AHE+OT</td><td>O(m)</td></tr><tr><td>Section 3.2 (Offline) - 1</td><td rowspan="2">0.5</td><td rowspan="3">AHE</td><td>O(m · δ · 2<sup>ν</sup>)</td></tr><tr><td>Section 3.2 (Offline) - 2</td><td>O(m · χ · 2<sup>ν</sup>)</td></tr><tr><td>Section 3.2 (Online)</td><td>2.5</td><td>AHE+GC+OT</td><td>O(P)</td></tr></tbody></table>

## 3.4 Application to continuous authentication and spam filtering

We implemented our solution and run our tests in Python with the Scikit-learn library [PVG$^{+11}$], using 75% of the dataset as the training set and the remaining 25% as the testing set. We optimized the training using the Orthogonal Matching Pursuit Algorithm [MZ93]: we generate 100 times more trees than expected, and we then apply the OMP algorithm on the global set, such that the outcome is the best linear combination with the expected number of trees.

We first deal with our initial use case, namely the continuous authentication. We use a database of 20531 samples split in 35 profiles built with 222 features. In this context, low *False Positive Rate* (FPR) is privileged to low *False Negative Rate* (FNR), since it is preferable to ask the client to use a second authentication factor rather than being impersonated. Moreover, high accuracy for each test is not required, as multiple tests will amplify the quality. Table 3.4 shows the mean results on the 35 profiles (where, for a given profile, all other profiles are considered as imposter), depending on the number of paths *P* and the depth of the model *δ*, while *ν* is set to 6, leading to 64 ciphertexts for each comparison, stored by the client. Also, we consider several values for the acceptation threshold (*τ*) (which equals 50% by default, for the simple majority).

We compute the FPR and FNR, then the accuracy is defined as the F1-score (defined by $(1 - \text{FPR})/(1 + (\text{FNR} - \text{FPR})/2)$). Random decision would lead to an accuracy of 1/2, and perfect filter should have F1-score equal to 1. We determine the best accuracy depending on those parameters in Table 3.4. For the honest-but-curious security setting, there is no constraint on the threshold, while against malicious clients, the higher the threshold is, the higher the security level is against active impersonation attempts.

Secondly, we consider on the spambase database [HRFS99] (with 4601 samples × 57 features) which determines if an email should be considered as spam or not. Results are shown in Table 3.5.
<table><thead><tr><th rowspan="2">T</th><th rowspan="2">δ</th><th colspan="3">50%</th><th colspan="3">55%</th></tr><tr><th>FPR</th><th>FNR</th><th>F1 Score</th><th>FPR</th><th>FNR</th><th>F1 Score</th></tr></thead><tbody><tr><td rowspan="2">10</td><td>6</td><td>0.02</td><td>0.15</td><td>0.92</td><td>0.02</td><td>0.16</td><td>0.91</td></tr><tr><td>8</td><td>0.01</td><td>0.19</td><td>0.91</td><td>0.01</td><td>0.19</td><td>0.91</td></tr><tr><td rowspan="2">25</td><td>6</td><td>0.04</td><td>0.13</td><td>0.92</td><td>0.03</td><td>0.15</td><td>0.92</td></tr><tr><td>8</td><td>0.02</td><td>0.14</td><td>0.92</td><td>0.02</td><td>0.17</td><td>0.91</td></tr></tbody></table>

<table><caption>Table 3.4: Accuracy on our continuous authentication Database</caption><thead><tr><th rowspan="2">T</th><th rowspan="2">δ</th><th colspan="3">60%</th><th colspan="3">65%</th></tr><tr><th>FPR</th><th>FNR</th><th>F1 Score</th><th>FPR</th><th>FNR</th><th>F1 Score</th></tr></thead><tbody><tr><td rowspan="2">10</td><td>6</td><td>0.01</td><td>0.23</td><td>0.89</td><td>0.01</td><td>0.23</td><td>0.89</td></tr><tr><td>8</td><td>0.01</td><td>0.25</td><td>0.88</td><td>0.01</td><td>0.26</td><td>0.88</td></tr><tr><td rowspan="2">25</td><td>6</td><td>0.02</td><td>0.2</td><td>0.9</td><td>0.01</td><td>0.23</td><td>0.89</td></tr><tr><td>8</td><td>0.01</td><td>0.24</td><td>0.89</td><td>0.01</td><td>0.26</td><td>0.88</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">T</th><th rowspan="2">δ</th><th colspan="3">50%</th><th colspan="3">55%</th></tr><tr><th>FPR</th><th>FNR</th><th>F1 Score</th><th>FPR</th><th>FNR</th><th>F1 Score</th></tr></thead><tbody><tr><td rowspan="2">10</td><td>2</td><td>0.02</td><td>0.24</td><td>0.88</td><td>0.01</td><td>0.28</td><td>0.87</td></tr><tr><td>4</td><td>0.03</td><td>0.20</td><td>0.89</td><td>0.04</td><td>0.18</td><td>0.90</td></tr><tr><td rowspan="2">25</td><td>2</td><td>0.03</td><td>0.24</td><td>0.88</td><td>0.02</td><td>0.25</td><td>0.88</td></tr><tr><td>4</td><td>0.04</td><td>0.19</td><td>0.89</td><td>0.04</td><td>0.21</td><td>0.88</td></tr></tbody></table>

<table><caption>Table 3.5: Accuracy on the spambase Database</caption><thead><tr><th rowspan="2">T</th><th rowspan="2">δ</th><th colspan="3">60%</th><th colspan="3">65%</th></tr><tr><th>FPR</th><th>FNR</th><th>F1 Score</th><th>FPR</th><th>FNR</th><th>F1 Score</th></tr></thead><tbody><tr><td rowspan="2">10</td><td>2</td><td>0.02</td><td>0.24</td><td>0.88</td><td>0.01</td><td>0.45</td><td>0.81</td></tr><tr><td>4</td><td>0.02</td><td>0.27</td><td>0.87</td><td>0.01</td><td>0.30</td><td>0.86</td></tr><tr><td rowspan="2">25</td><td>2</td><td>0.01</td><td>0.47</td><td>0.80</td><td>0.00</td><td>0.56</td><td>0.78</td></tr><tr><td>4</td><td>0.02</td><td>0.23</td><td>0.89</td><td>0.01</td><td>0.34</td><td>0.85</td></tr></tbody></table>
Chapter 4

Post-quantum Oblivious Transfer from
Smooth Projective Hash Functions with
gray zone

Smooth Projective Hash Functions (SPHF), or Hash Proof System as introduced by Cramer and Shoup in [CS02], are a cryptographic primitive initially designed to provide IND-CCA encryption schemes. Over the years, SPHFs have been used for many applications such as Password-Authenticated Key Exchange [GL03, ACP09, KV11, BBC+13a], Zero-Knowledge Proofs [JR12, BBC+13b] or Witness Encryption [DS15]. Since their introduction, SPHFs have been developed over classical hard problems such as discrete logarithm or factorization. However, post-quantum cryptography does not seem to be as easily compliant with SPHF. In [KV09], Katz et al. introduced *Approximate Smooth Projective Hash Functions*. The correctness property of an SPHF claims that the hash value and the projective hash value are required to be equal on words in an NP-language, when knowing a witness, while the smoothness property expects them to be independent when no witness exists. Approximate SPHF uses an approximate correctness, that allows those values to be close, relatively to a given distance. Furthermore, languages relying on code-based or lattice-based ciphertexts result in a gap between the set of valid ciphertexts of a given value $\mu$, and the values that decrypt into $\mu$. As mentioned in [BBB+21a], an adversary could maliciously generate one of those ciphertexts and open the door for practical attacks. The presence of this gap can also be problematic when expecting to work in the Universal Composability framework [Can01]. In this chapter, we define a new primitive named Smooth Projective Hash Function with Gray Zone (SPHFwGZ) which can be seen as a relaxation of the classical Smooth Projective Hash Functions, with a subset of the words for which one cannot claim correctness nor smoothness. We then rely on this new primitive to build Oblivious Transfer (OT) protocols. Interestingly, our new paradigm features a security analysis in the Universal Composability (UC) framework and may be instantiated from post-quantum primitives. We then provide two instantiations based on the Diffie-Hellman and the Learning With Errors (LWE) problems.

★ Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Baptiste Cottier, and David Pointcheval. Post-Quantum and UC-secure Oblivious Transfer from SPHF with Gray Zone. In *The 15th International Symposium on Foundations & Practice of Security*, pages 1–16, 2022.<fnref n="1" />

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

<footnote n="1">¹in this thesis, we use 'gray' rather than 'grey', as it is written is American English</footnote>
# Contents

<table><tbody><tr><td>4.1</td><td>Smooth Projective Hash Functions with gray zone</td><td>80</td></tr><tr><td>4.1.1</td><td>Word indistinguishability and trapdoor</td><td>81</td></tr><tr><td>4.1.2</td><td>Decomposition intractability and trapdoor</td><td>81</td></tr><tr><td>4.2</td><td>Oblivious Transfer from SPHFwGZ</td><td>82</td></tr><tr><td>4.2.1</td><td>Construction of Oblivious Transfer</td><td>82</td></tr><tr><td>4.2.2</td><td>Security analysis</td><td>82</td></tr><tr><td>4.2.3</td><td>Noisy homomorphic encryption setup</td><td>84</td></tr><tr><td>4.3</td><td>Concrete instantiations of SPHFwGZ</td><td>85</td></tr><tr><td>4.3.1</td><td>Instantiation from the Diffie-Hellman problem</td><td>85</td></tr><tr><td>4.3.2</td><td>Instantiation from the Learning With Errors problem</td><td>85</td></tr></tbody></table>

# Notations & Acronyms

<table><tbody><tr><td colspan="2">Smooth Projective Hash Functions</td></tr><tr><td>SPHF</td><td>Smooth Projective Hash Function(s)</td></tr><tr><td>SPHFwGZ</td><td>Smooth Projective Hash Function(s) with Gray Zone</td></tr><tr><td>X</td><td>Space of words</td></tr><tr><td>L, L'</td><td>Languages</td></tr><tr><td>x</td><td>Word</td></tr><tr><td>w</td><td>Witness of a word in a language</td></tr><tr><td>hk</td><td>Hash key</td></tr><tr><td>hp</td><td>Projection key</td></tr><tr><td>H<sub>hk</sub></td><td>Hash value</td></tr><tr><td>H<sub>hp</sub></td><td>Projection hash</td></tr><tr><td>R<sub>L</sub></td><td>Witness Relation function for the language L</td></tr></tbody></table>

<table><tbody><tr><td colspan="2">Oblivious Transfer</td></tr><tr><td>OT</td><td>Oblivious Transfer</td></tr><tr><td>Φ<sup>SPHFwGZ</sup><sub>OT</sub></td><td>our OT protocol based on SPHFwGZ</td></tr></tbody></table>

<table><tbody><tr><td colspan="2">Security Proof</td></tr><tr><td>UC</td><td>Universal Composability</td></tr><tr><td>CRS</td><td>Common Reference String</td></tr><tr><td>S<sub>0</sub>, S<sub>1</sub></td><td>Setup sets for σ</td></tr><tr><td>R<sub>0</sub>, R<sub>1</sub>, R'<sub>1</sub></td><td>Setup sets for ρ</td></tr><tr><td>td<sub>σ</sub>, td<sub>ρ</sub></td><td>Trapdoors</td></tr><tr><td>F<sub>CRS</sub></td><td>Ideal Functionality for a CRS</td></tr><tr><td>F<sub>OT</sub></td><td>Ideal Functionality for an Oblivious Transfer</td></tr></tbody></table>
**Previous Works.** In code-based cryptography, the first proposition was made by Persichetti in [Per13]. The SPHF proposed there uses a weaker smoothness definition, called universality. Strictly speaking, this is not a drawback as we can transform an SPHF with universality property to a word-dependent SPHF with smoothness property. However, the main issue with this candidate is that the proof is done on random keys, rather than the whole keys. This has for consequence that an adversary can exploit some well-chosen keys resulting in a failure of the proof. A second construction was designed in [BBB$^+$21a]. As said before, when working with lattices and codes, languages based on ciphertexts present a Gray Zone. In this work, Bettaieb et al. withdraw this gap using a zero-knowledge proof asserting if two different ciphertexts of the same message are valid, reducing the SPHF on the set of valid ciphertexts, resulting in the first gapless post-quantum SPHF. A solution based on codes is also given in [SA21], but their solution offers an Approximate SPHF with computational smoothness, while real SPHF expects statistical/perfect smoothness. In lattice-based cryptography, the first construction was given in [KV09] where Katz et al. introduced the notion of Approximate SPHF. Their language not being exactly defined as the valid LWE-ciphertexts, decoding procedure was expensive, as detailed in [BBDQ18]. This latter article, motivated by this issue, offers the first non-approximated SPHF based on lattices. While the two previous constructions are in the standard model, Zha et al. [ZY17] propose a SPHF requiring access to a random oracle. Indeed, their language relies on simulation-sound non-interactive zero-knowledge proofs, that we are not able to construct efficiently without random oracles.

## 4.1 Smooth Projective Hash Functions with gray zone

We first give a definition of our formalization of Smooth Projective Hash Functions with Gray Zone (SPHFwGZ) which is a relaxation of the classical SPHF in which one cannot claim correctness nor smoothness for a subset of the words. Later, we provide a quantum-resistant SPHFwGZ based on lattices. With this new definition, we have two disjoint languages $\mathcal{L}, \mathcal{L}' \subset \mathcal{X}$ that does not necessarily partition the superset $\mathcal{X}$: the remaining subset $\mathcal{X} \setminus (\mathcal{L} \cup \mathcal{L}')$ is defined as the Gray Zone.

**Definition 4.1 - Smooth Projective Hash Function with Gray Zone**

An SPHFwGZ is defined with a tuple of algorithms:

- Setup($1^\kappa$) generates the parameters $\text{param}$ from $\kappa$, the security parameter, or an explicit random tape ($\sigma, \rho$) in $S_0 \times \mathcal{R}_0$. $\text{param}$ includes a description of $\mathcal{L}, \mathcal{L}', \mathcal{X}$, where $(\mathcal{L} \cup \mathcal{L}') \subset \mathcal{X}$ and $\mathcal{L} \cap \mathcal{L}' = \emptyset$, and $\mathcal{L}$ is a language hard to decide in $\mathcal{X}$. Returns $\text{param}$.

- HashKG($\text{param}$) generates a random hash key $\text{hk}$. Returns $\text{hk}$.

- ProjKG($\text{hk}, x$) derives the projection key $\text{hp}$ (it may need $x$ as input). Returns $\text{hp}$.

- Hash($\text{hk}, x$) computes the hash value $H_{\text{hk}} \in \mathcal{V}$, where $\mathcal{V}$ is the set of hash values, associated to the word $x$. Returns $H_{\text{hk}}$.

- ProjHash($\text{hp}, x, w$) computes $H_{\text{hp}} \in \mathcal{V}$ using a witness $w$ linked to the word $x$. Returns $H_{\text{hp}}$.

As the classical SPHF, our SPHFwGZ verifies the following statistical properties, for any setup execution that provides $\text{param}$, defining $\mathcal{L}, \mathcal{L}', \mathcal{X}$:

* **Correctness:** For any $x \in \mathcal{L}$, $H_{\text{hk}} = H_{\text{hp}}$, where $\text{hk} \leftarrow \text{HashKG}(\text{param})$, $\text{hp} \leftarrow \text{ProjKG}(\text{hk}, x)$, $H_{\text{hk}} \leftarrow \text{Hash}(\text{hk}, x)$, and $H_{\text{hp}} \leftarrow \text{ProjHash}(\text{hp}, x, w)$ for the witness $w$ of $x \in \mathcal{L}$;

* **Smoothness:** For any $x \in \mathcal{L}'$, the distributions of $(\text{hp}, H_{\text{hk}})$ and $(\text{hp}, v)$ are indistinguishable, where $\text{hk} \leftarrow \text{HashKG}(\text{param})$, $\text{hp} \leftarrow \text{ProjKG}(\text{hk}, x)$, $H_{\text{hk}} \leftarrow \text{Hash}(\text{hk}, x)$, and $v \leftarrow \mathcal{V}$;

The algorithms and properties described above are the basic algorithms for SPHFwGZ. For a later use, we need to define several additional properties.
### 4.1.1 Word indistinguishability and trapdoor

First, we assume languages $\mathcal{L}$ and $\mathcal{L}'$ in $\mathcal{X}$ are defined according to a random tape $(\sigma, \rho)$ sampled in a set $S_0 \times \mathcal{R}_0$ (i.e. from param $\leftarrow$ Setup($\sigma, \rho$)). The samplable set $S_0$ is defined together with its twin set $S_1$ such that when $\sigma \in S_1$, and param $\leftarrow$ Setup($\sigma, \rho$), there exists a trapdoor $\text{td}_\sigma$ that allows to test if a given word $x \in \mathcal{X}$ is in $\mathcal{L}'$ or not. We then also need the following algorithms:

* WordGen($\mathcal{L}$(param)): Samples and returns $x \leftarrow \mathcal{L}$, together with its witness $w$;

* WordTest($\text{td}_\sigma$, $x$), using the trapdoor $\text{td}_\sigma$, tests if $x \in \mathcal{L}'$.

As we assumed $\mathcal{L}$ to be a hard subset of $\mathcal{X}$ when $\sigma \in S_0$, we have the **Word-Indistinguishability Property**: An adversary can not distinguish between random words in $\mathcal{L}$ and random words in $\mathcal{X}$, for any $\sigma \in S_0$, with more than a negligible advantage.

The string $\sigma$ can be seen as a CRS, that admits a trapdoor when sampled from $S_1$. The normal use is with $\sigma \leftarrow \mathcal{S}_0$, which needs to be efficiently samplable. When $\sigma \in S_1$, the trapdoor $\text{td}_\sigma$ must be easy to compute from $\sigma$.

### 4.1.2 Decomposition intractability and trapdoor

We also define the alternate sets $\mathcal{R}_1$ and $\mathcal{R}'_1$ for $\mathcal{R}_0$. During normal use, $\rho$ is sampled from $\mathcal{R}_0$, which needs to be efficiently samplable. When $\rho \in \mathcal{R}_1$, and param $\leftarrow$ Setup($\sigma, \rho$), there exists a trapdoor $\text{td}_\rho = (x, x', w, w')$, that must be easy to compute from $\rho$. When $\rho \in \mathcal{R}'_1$, and param $\leftarrow$ Setup($\sigma, \rho$), there exists a trapdoor $\text{td}_\rho = (x, x')$, that must be easy to compute from $\rho$. Let us define the complement algorithm, for any $\rho \in \mathcal{R}_0 \cup \mathcal{R}_1 \cup \mathcal{R}'_1$:

* ComplementWord(param, $\rho, x$): from any word $x \in \mathcal{X}$, it outputs $x'$;

From this complement algorithm, we expect the following statistical property, for any $\sigma \in S_0 \cup S_1$ but $\rho$ only in $\mathcal{R}_0$:

* **Complement**: for any $x \in \mathcal{X}$, if $x' \leftarrow \text{ComplementWord}(\text{param}, \rho, x)$, we have $x = \text{ComplementWord}(\text{param}, \rho, x')$;

In addition to those algorithms, we also need a computational assumption: the **Decomposition Intractability**. This assumption states that, given random $(\sigma, \rho) \leftarrow \mathcal{S}_1 \times \mathcal{R}_0$, no adversary can generate, with non-negligible probability, $x, y \notin \mathcal{L}'$ such that $y = \text{ComplementWord}(\text{param}, \rho, x)$, and so even with the knowledge of the trapdoor $\text{td}_\sigma$.

On the other hand, when $\rho \in \mathcal{R}_1$, the trapdoor $\text{td}_\rho = (x, x', w, w')$ satisfies $x$ and $x'$ are uniformly random in $\mathcal{L}$ with witnesses $w, w'$, and $x' = \text{ComplementWord}(\text{param}, \rho, x)$. And when $\rho \in \mathcal{R}'_1$, the trapdoor $\text{td}_\rho = (x, x')$ satisfies $x$ and $x'$ are uniformly random in $\mathcal{L}'$, and $x' = \text{ComplementWord}(\text{param}, \rho, x)$.

Again, the string $\rho$ can be seen as a CRS, that admits a trapdoor when sampled from $\mathcal{R}_1$ or $\mathcal{R}'_1$. The normal use is with $\rho \leftarrow \mathcal{R}_0$, which needs to be efficiently samplable. When $\rho \in \mathcal{R}_1$ or $\rho \in \mathcal{R}'_1$, the trapdoor $\text{td}_\rho$ must be easy to compute from $\rho$.

Eventually, for the security proof to go through, we make use of the **CRS Indistinguishability**: An adversary can not distinguish between $\mathcal{R}_0$, $\mathcal{R}_1$ and $\mathcal{R}'_1$, and between $S_0$ and $S_1$, with more than a negligible advantage.

Note that we independently consider the choices between $S_0$ and $S_1$ and between $\mathcal{R}_0$, $\mathcal{R}_1$ and $\mathcal{R}'_1$, but the latter choice could depend on the former choice. So the global CRS is the pair $\text{crs} = (\sigma, \rho)$.
## 4.2 Oblivious Transfer from SPHFwGZ

In this section we first present our construction of Oblivious Transfers based on Smooth Projective Hash Functions with Gray Zone, and then provide a security proof of our Oblivious Transfer in the Universal Composability framework

### 4.2.1 Construction of Oblivious Transfer

Our Oblivious Transfer uses a crs = $(\sigma, \rho) \in S_0 \times \mathcal{R}_0$ as defined above, where we assume $S_0 \times \mathcal{R}_0 \approx S_1 \times \mathcal{R}_0 \approx S_0 \times \mathcal{R}_1 \approx S_0 \times \mathcal{R}'_1$. The idea of our Oblivious Transfer is quite straightforward. The receiver generates a word $x_b$ for the sender's input she wants to retrieve, and extract a second word $x_{1-b}$ using $\rho$ and $x_b$. Then, the sender computes a One-Time Pad encryption of his messages $m_b$ and $m_{1-b}$ with the hash values of $x_b$ and $x_{1-b}$ respectively.

We depict in Figure 4.1 the OT protocol $\Phi_{\text{OT}}^{\text{SPHFwGZ}}$.

<figure><img src="image_40.png" /><figcaption>Figure 4.1: General description of the protocol $\Phi_{\text{OT}}^{\text{SPHFwGZ}}$</figcaption></figure>

The protocol $\Phi_{\text{OT}}^{\text{SPHFwGZ}}$ provides **Correctness**. Indeed, with the honest generation $(x, w) \leftarrow \text{WordGen}\mathcal{L}(\text{param})$ we have $c = (H \oplus m, \text{hp})$. Then, $m = H \oplus m \oplus \text{ProjHash}(c_1, x, w)$ if and only if $H = \text{ProjHash}(c_1, x, w)$ which is ensured due to the correctness property of the SPHFwGZ. Moreover, the **complement** property ensures the value $x_1$ computed by the sender is always the same as the value $x_1$ computed by the receiver.

We now prove the privacy of our Oblivious Transfer in the Universal Composability framework.

### 4.2.2 Security analysis

Our Oblivious Transfer protocol will be proven in the CRS-hybrid model (as in [PVW08]), with the functionality $\mathcal{F}_{\text{CRS}}$, where the two players get the same random crs from the sid. In practice, as we assumed $S_0$ and $\mathcal{R}_0$ efficiently samplable, $(\sigma, \rho)$ can be derived from $\mathcal{H}(\text{sid})$. Then, in Figure 4.2, we recall the ideal functionality $\mathcal{F}_{\text{OT}}$ for a secure Oblivious Transfer, where there are two first messages from the sender with input $(m_0, m_1)$ and from the receiver with input bit $b$, to initialize the process, and the final request message by the sender that decides when the receiver can get $m_b$.
$\mathcal{F}_{\text{OT}}$ interacts with a sender S and a receiver R:

* Upon receiving a message $(\text{sid}, \text{sender}, m_0, m_1)$ from S, store $(\text{sid}, m_0, m_1)$;

* Upon receiving a message $(\text{sid}, \text{receiver}, b)$ from R, store $(\text{sid}, b)$;

* Upon receiving a message $(\text{sid}, \text{answer})$ from the adversary, check if both records $(\text{sid}, m_0, m_1)$ and $(\text{sid}, b)$ exist for sid. If yes, send $(\text{sid}, m_b)$ to R, and sid to the adversary and halt. If not, send nothing but continue running.

<caption>Figure 4.2: Functionality $\mathcal{F}_{\text{OT}}$</caption>

**Theorem 4.1**

The protocol $\Phi_{\text{OT}}^{\text{SPHFwGZ}}$ UC-realizes $\mathcal{F}_{\text{OT}}$ in the $\mathcal{F}_{\text{CRS}}$-hybrid model in the static-corruption setting, from any SPHFwGZ providing the decomposition intractability.

We stress that we consider static corruptions only, where the corrupted players are known when each protocol execution starts.

**Game** $G_0$. This is the real game, where $\mathcal{F}_{\text{CRS}}$ samples crs in $S_0 \times \mathcal{R}_0$.

**Game** $G_1$. In this game, the simulator $S$ simulates itself the sampling of crs = $(\sigma, \rho) \leftarrow_S S_0 \times \mathcal{R}_0$, and generates correctly every flow from the honest players, as they would do themselves, knowing the inputs $(m_0, m_1)$ and $b$ sent by the environment to the sender and the receiver, respectively.

**Game** $G_2$. In this game, we deal with **corrupted receivers**. Instead of sampling crs = $(\sigma, \rho) \leftarrow_S S_0 \times \mathcal{R}_0$, the simulator $S$ samples crs = $(\sigma, \rho) \leftarrow_S S_1 \times \mathcal{R}_0$, and therefore with the trapdoor $\text{td}_{\sigma}$. This game is indistinguishable from the previous one due to the CRS Indistinguishability.

**Game** $G_3$. In this game, the simulator $S$ uses the trapdoor $\text{td}_{\sigma}$ to get $t_i = \text{WordTest}(x_i, \text{td}_{\sigma})$ for $i \in \{0, 1\}$. If $t_0 = t_1 = 0$ (none of the words are in $\mathcal{L}'$), $S$ aborts. This game is indistinguishable from the previous one, under the Decomposition Intractability, as $(\sigma, \rho) \in S_1 \times \mathcal{R}_0$.

**Game** $G_4$. If $t_0 = t_1 = 0$, we still abort. If $t_0 = t_1 = 1$ we set $b = 0$, otherwise, we set $b$ such that $t_b = 0$. Next, the simulator $S$ proceeds on $m_b$ with $x_b$ and on a random message with $x_{1-b}$. Under the smoothness of the SPHFwGZ, as $x_{1-b} \in \mathcal{L}'$, and the One-Time Pad Semantic Security, this game is statistically indistinguishable from the previous one.

**Game** $G_5$. In this game, we deal with **corrupted senders**. Instead of sampling crs = $(\sigma, \rho) \leftarrow_S S_0 \times \mathcal{R}_0$, the simulator $S$ samples crs = $(\sigma, \rho) \leftarrow_S S_0 \times \mathcal{R}_1$, and therefore with the trapdoor $\text{td}_{\rho} = (x, x', w, w')$. This game is indistinguishable from the previous one due to the CRS indistinguishability.

**Game** $G_6$. In this game, the simulator $S$ respectively sets $(x_0, w_0, x_1, w_1)$ as $(x, w, x', w')$ from $\text{td}_{\rho}$. It can then retrieve both $m_0$ and $m_1$. This game is indistinguishable from the previous one due to the Word Indistinguishability, and the uniform distribution of the trapdoor.

**Game** $G_7$. We now deal with **honest players**. Instead of sampling crs = $(\sigma, \rho) \leftarrow_S S_0 \times \mathcal{R}_0$, the simulator $S$ samples crs = $(\sigma, \rho) \leftarrow_S S_0 \times \mathcal{R}'_1$, and therefore with the trapdoor $\text{td}_{\rho} = (x, x')$, and simulates the flows with random $m_0, m_1 \leftarrow_S \mathcal{M}$ and random $b \leftarrow_S \{0, 1\}$. Under the CRS Indistinguishability and the smoothness of the SPHFwGZ, as both $x, x' \in \mathcal{L}'$, coupled with the One-Time Pad Semantic Security, this game is indistinguishable from the previous one.
**Game $G_8$.** This is the ideal game We can now make use of the functionality $\mathcal{F}_{OT}$ which leads to the following simulator:

* If no participant is corrupted, one uses crs $\leftarrow_S S_0 \times \mathcal{R}'_1$, and the simulator $S$ simply uses random inputs for the sender and the receiver;

* If the receiver is corrupted, one uses crs $\leftarrow_S S_1 \times \mathcal{R}_0$, and the simulator $S$ extracts $b$ using the trapdoor $td_\sigma$, and sends $(\text{sid}, \text{receiver}, b)$ to $\mathcal{F}_{OT}$;

* If the sender is corrupted, one uses crs $\leftarrow_S S_0 \times \mathcal{R}_1$, and the simulator $S$ extracts $m_0, m_1$ using the trapdoor $td_\rho$, and sends $(\text{sid}, \text{sender}, m_0, m_1)$ to $\mathcal{F}_{OT}$;

* The adversary sends $(\text{sid}, \text{answer})$ when it decides to deliver the result to the receiver.

### 4.2.3 Noisy homomorphic encryption setup

We now define a general setup leading to an instantiation of our Oblivious Transfer from many Homomorphic Encryption. This setup includes encryption schemes with potential decryption failure, as shown with our lattice-based instantiation, thanks to some amplification. We denote the group law $*$ on plaintexts and $\oplus$ on the ciphertexts.

We consider an encryption scheme $\Pi = (\text{Setup}, \text{KGen}, \text{Enc}, \text{Dec})$ with possible decryption failures. Thus, we set $\mathcal{X}$ as the ciphertext space of $\Pi$, whereas

$$ \mathcal{L} = \{\text{Enc}(\text{pk}, 0; r)\} \subset \mathcal{X} \text{ and } \mathcal{L}' = \{c \in \mathcal{X}, \text{Dec}(\text{sk}, c) \neq 0\} \subset \mathcal{X}. $$

Sets $S_0$ and $S_1$ can both be seen as public keys pk generated from $\text{KGen}(1^\kappa)$ except that when $\sigma \in S_1$, the secret key sk is known and defines the trapdoor $td_\sigma$. Hence, $\sigma$ (which defines the public key pk) defines the sets $\mathcal{L}$ and $\mathcal{L}'$ in $\mathcal{X}$. On the other hand, we can define $\mathcal{R}_0, \mathcal{R}_1$ and $\mathcal{R}'_1$ as follows:

* $\mathcal{R}_0 = \mathcal{X}$, the set of all the ciphertexts, or a superset, with uniform distribution;

* $\mathcal{R}_1 = \{c_0 \oplus c_1\}$, for two ciphertexts $c_0, c_1$ in $\mathcal{L}$, following the distribution of the encryption algorithm, on plaintext 0, and according the distribution of the randomness $r_0, r_1$, which allows to define the trapdoor $td_\rho$ as $(c_0, c_1, r_0, r_1)$;

* $\mathcal{R}'_1 = \{c_0 \oplus c_1\}$, for two ciphertexts $c_0, c_1$ in $\mathcal{L}'$, following the distribution of the encryption algorithm, on non-zero plaintexts, which allows to define the trapdoor $td_\rho$ as $(c_0, c_1)$.

The setup defined above verifies both basic assumptions required to make the Oblivious Transfer Universally Composable:

* CRS Indistinguishability: Under the semantic security of the encryption scheme $\Pi, \mathcal{L}, \mathcal{L}'$, and $\mathcal{X}$ are indistinguishable. The homomorphic property implies that $\{x \oplus x'|(x, x') \in \mathcal{X}^2\} = \mathcal{X}$. As a consequence, we have indistinguishability between $\mathcal{R}_0 = \mathcal{X} = \{x \oplus x'|(x, x') \in \mathcal{X}^2\}$, $\mathcal{R}_1 = \{x \oplus x'|(x, x') \in \mathcal{L}^2\}$, and $\mathcal{R}'_1 = \{x \oplus x'|(x, x') \in \mathcal{L}'^2\}$. Furthermore, as $S_0 = S_1$, they are perfectly indistinguishable;

* Word Indistinguishability: Under the semantic security of the encryption scheme $\Pi$, one can not distinguish between $c_0 \in \mathcal{L}$, an encryption of 0 and $c_1 \in \mathcal{X}$, an encryption of a random value.

* Complement: for any $x \in \mathcal{X}$, if $x' \leftarrow \text{ComplementWord}(\text{param}, \rho, x) = \rho \oplus x^{-1}$, hence we have $\text{ComplementWord}(\text{param}, \rho, x') = \rho \oplus (\rho \oplus x^{-1})^{-1} = x$;

Additional properties will depend on concrete instantiations.
## 4.3 Concrete instantiations of SPHFwGZ

We now provide two concrete instantiations of SPHFwGZ based on the Diffie-Hellman and Learning With Errors problems. As both constructions rely on a homomorphic encryption scheme, we can already consider the basic properties shown in Section 4.2.3.

### 4.3.1 Instantiation from the Diffie-Hellman problem

In this section, we focus on elliptic curve based cryptography, using the Decisional Diffie-Hellman assumption in a prime-order group.

#### 4.3.1.1 SPHFwGZ from ElGamal encryption.

From the IND-CPA ElGamal encryption scheme in a group $G$, using multiplicative notation, of prime order $p$, with generator $g$.

We set $S_0 = S_1 = \{\sigma = h = g^{td_\sigma}; td_\sigma \leftarrow_S \mathbb{Z}_p\}$. Then, $R_0$ is defined as $\mathbb{G}^2 = \{\rho = (\hat{g}, \hat{h}) \leftarrow_S \mathbb{G}^2\}$, $R_1$ as $\{\rho = (\hat{g} \leftarrow g^{r_0} \cdot g^{r_1}, \hat{h} \leftarrow h^{r_0} \cdot h^{r_1}); (r_0, r_1) \leftarrow_S \mathbb{Z}_p\}$ and $R'_1$ as $\{c_0 \oplus c_1; (c_0, c_1) \in \mathbb{G}^{2 \times 2}\}$. The crs is set as $(\sigma, \rho)$. One can note that witnesses only exist when $\rho \in R_1$, then $td_\rho = (c_0 = (g^{r_0}, h^{r_0}), c_1 = (g^{r_1}, h^{r_1}), r_0, r_1)$. Hence, $c_0$ and $c_1$ are encryptions of $M = g^0$, with respective randomness $r_0$ and $r_1$. Moreover, while $td_\sigma$ always exists, it is not necessarily known.

From the above generic construction, we have $\mathcal{X} = \{(g^r, h^r \cdot M); M \in \mathbb{G}\} = \mathbb{G}^2$ and $\mathcal{L} = \{(g^r, h^r)\}$, which are indistinguishable under the Decisional Diffie-Hellman assumption. With $\text{param} = (g, \sigma = h)$, which determines all the sets (specified by the Setup algorithm), we can define:

* $\text{hk} = \text{HashKG}(\text{param}) = (\alpha, \beta) \leftarrow_S \mathbb{Z}_p^2$;

* $\text{hp} = \text{ProjKG}(\text{hk}) = g^\alpha h^\beta$;

* $H = \text{Hash}(\text{hk}, x = (u, v)) = u^\alpha v^\beta \in \mathbb{G}$;

* $H' = \text{ProjHash}(\text{hp}, x, w = r) = \text{hp}^r$, if $x = (g^r, h^r) \in \mathcal{L}$.

* $x' = (u', v') = \text{ComplementWord}(\rho = (\hat{g}, \hat{h}), x = (u, v)) = (\hat{g} \cdot u^{-1}, \hat{h} \cdot v^{-1})$

This is a word-independent SPHFwGZ. And we can show the expected properties:

* **Correctness:** When $x = (u, v) = (g^r, h^r) \in \mathcal{L}$, with witness $r$, $H = u^\alpha v^\beta = (g^\alpha h^\beta)^r = \text{hp}^r = H'$;

* **Smoothness:** When $x = (u, v) = (g^r, h^{r'}) \notin \mathcal{L}$, then $r' = r + r''$ with $r'' \neq 0$: $H = u^\alpha v^\beta = (g^\alpha h^\beta)^r \times g^{r''\beta} = \text{hp}^{r'} \times g^{r''\beta} = H' \times g^{r''\beta}$. But $\beta$ is perfectly hidden in $\text{hp}$, and $g^{r''\beta}$ is perfectly unpredictable;

* **Decomposition Intractability:** In ElGamal encryption there is no decryption failure: all the ciphertexts can be covered by the encryption algorithm, and the decryption perfectly inverts the encryption process. So we have $\mathcal{L}' = \mathcal{X} \setminus \mathcal{L}$. A random ciphertext $\rho$ encrypts an $M \neq 1$ with overwhelming probability. Then, when it encrypts $M \neq 1$, from the homomorphic property, this is impossible to have two encryptions of 1 whose product is $\rho$. Hence, the decomposition intractability is statistical: the probability of existence of the decomposition is bounded by $1/\rho$, on $\rho$, even knowing the decryption key, and thus the trapdoor $td_\sigma$.

Note that this construction exactly corresponds to the one from [CS98].

### 4.3.2 Instantiation from the Learning With Errors problem

In this section, we focus on lattice-based cryptography. We are going to show how to instantiate the various required components from the Learning With Errors problem.
**Regev Encryption.** Regev [Reg05] showed that for $\chi = D_{\mathbb{Z},\sigma}$, a Gaussian centered distribution in $\mathbb{Z}$ for any standard deviation $\sigma \ge 2\sqrt{n}$, and $q$ such that $q/\sigma = \text{poly}(n)$, $\text{LWE}_{\chi,q}$ is at least as hard as solving worst-case SIVP for polynomial approximation factors, which is assumed to be hard to solve, even for quantum computers.

**Trapdoor for LWE.** Throughout this section, we will use the trapdoors introduced in [MP12] to build our public matrix **A**. Define $g_A(\mathbf{s}, \mathbf{e}) = \mathbf{A}\mathbf{s} + \mathbf{e}$, the gadget matrix **G** as $\mathbf{G}^t = \mathbf{I}_n \otimes \mathbf{g}^t$, where $\mathbf{g}^t = [1, 2, \dots, 2^k]$ and $k = \lceil \log q \rceil - 1$, and let $\mathbf{H} \in \mathbb{Z}_q^{n \times n}$ be invertible. The notation $[\mathbf{A} | \mathbf{B}]$ is for horizontal concatenation, while $[\mathbf{A}; \mathbf{B}]$ is for vertical concatenation.

**Lemma 1 ([MP12, Theorems 5.1 and 5.4])** There exist two PPT algorithms TrapGen and $g_{\cdot}^{-1}$ with the following properties assuming $q \ge 2$ and $m \ge \Theta(n \log q)$:

* TrapGen($1^n, 1^m, q$) outputs $(\mathbf{T}, \mathbf{A}_0)$, where the distribution of the matrix $\mathbf{A}_0$ is at negligible statistical distance from uniform in $\mathbb{Z}_q^{m \times n}$, and such that $\mathbf{T}\mathbf{A}_0 = \mathbf{0}$, where $s_1(\mathbf{T}) \le O(\sqrt{m})$ and where $s_1(\mathbf{T})$ is the operator norm of $\mathbf{T}$, which is defined as $\max_{x \ne 0} \|\mathbf{T}x\|/\|x\|$.2

* Let $(\mathbf{T}, \mathbf{A}_0) \leftarrow \text{TrapGen}(1^n, 1^m, q)$. Let $\mathbf{A}_H = \mathbf{A}_0 + [\mathbf{0}; \mathbf{GH}]$ for some invertible matrix $\mathbf{H}$ called a tag. Then, we have $\mathbf{T}\mathbf{A}_H = \mathbf{GH}$. Furthermore, if $\mathbf{x} \in \mathbb{Z}_q^m$ can be written as $\mathbf{A}_H\mathbf{s} + \mathbf{e}$, with $\mathbf{s} \in \mathbb{Z}_q^n$ and $\mathbf{e} \in \mathbb{Z}_q^m$ where $\|\mathbf{e}\| \le B' := q/\Theta(\sqrt{m})$, then $g_{\mathbf{A}_H}^{-1}(\mathbf{T}, \mathbf{x}, \mathbf{H})$ outputs $(\mathbf{s}, \mathbf{e})$.

More precisely, to sample $(\mathbf{T}, \mathbf{A}_0)$ with TrapGen, we sample a uniform $\bar{\mathbf{A}} \in \mathbb{Z}_q^{\bar{m} \times n}$ where $\bar{m} = m - nk = \Theta(n \log q)$, and some $\mathbf{R} \leftarrow \mathcal{D}^{nk \times \bar{m}}$, where the distribution $\mathcal{D}^{nk \times \bar{m}}$ assigns probability $1/2$ to $0$, and $1/4$ to $\pm 1$. We output $\mathbf{T} = [-\mathbf{R} | \mathbf{I}_{nk}]$ along with $\mathbf{A}_0 = [\bar{\mathbf{A}}; \mathbf{R}\bar{\mathbf{A}}]$. Then, given a tag $\mathbf{H}$, with $\mathbf{A}_H = \mathbf{A}_0 + [\mathbf{0}; \mathbf{GH}]$, we have: $\mathbf{T}\mathbf{A}_H = \mathbf{GH}$.

We will only consider a fixed tag $\mathbf{H} = \mathbf{I}$, for the Micciancio-Peikert encryption [MP12]. Our construction only requires CPA encryption so we don't need several tags, but we need to be able to reject improperly computed ciphertexts, and the gadget matrix is here, to allow this extra control during the decryption.

**LWE Encryption à la Micciancio-Peikert.** For this scheme, we assume $q$ to be an odd prime. We set an encoding function for messages $\text{Encode}(\mu \in \{0, 1\}) = \mu \cdot (0, \dots, 0, \lceil q/2 \rceil)^t$. Note that $2 \cdot \text{Encode}(\mu) = (0, \dots, 0, \mu)^t \bmod q$, as $\lceil q/2 \rceil$ is the inverse of $2 \bmod q$, for such an odd $q$.

Let $(\mathbf{T}, \mathbf{A}_0) \leftarrow \text{TrapGen}(1^n, 1^m, q)$. The public encryption key is $\mathbf{pk} = \mathbf{A}_0$, and the secret decryption key is $\mathbf{sk} = \mathbf{T}$.

* $\text{Enc}(\mathbf{pk} = \mathbf{A}_0, \mu \in \{0, 1\})$ encrypts the message $\mu$ under the public key $\mathbf{pk}$ as follows: Let $\mathbf{A} = \mathbf{A}_0 + [\mathbf{0}; \mathbf{G}]$. Pick $\mathbf{s} \in \mathbb{Z}_q^n$, $\mathbf{e} \leftarrow D_{\mathbb{Z}_q, t}^m$ where $t = \sigma\sqrt{m} \cdot \omega(\sqrt{\log n})$. Restart if $\|\mathbf{e}\| > B$, where $B := 2t\sqrt{m}$.3 Output the ciphertext:

$$ \mathbf{c} = \mathbf{A}\mathbf{s} + \mathbf{e} + \text{Encode}(\mu) \bmod q. $$

* $\text{Dec}(\mathbf{sk} = \mathbf{T}, \mathbf{c} \in \mathbb{Z}_q^m)$ decrypts the ciphertext $\mathbf{c}$ using the decryption key $\mathbf{sk}$ as follows: With $B'' := q/2\Theta(\sqrt{m})$, output

$$ \begin{cases} \mu & \text{if } g_{\mathbf{A}}^{-1}(\mathbf{T}, 2\mathbf{c}, \mathbf{I}) = (2\mathbf{s}, 2\mathbf{e} + (0, \dots, 0, \mu)) \text{ where } \mathbf{s} \in \mathbb{Z}_q^n, \mathbf{e} \in \mathbb{Z}^m \text{ and } \|\mathbf{e}\| \le B'', \\ \perp & \text{otherwise.}^4 \end{cases} $$

<footnote n="2">²The bound on $s_1(\mathbf{T})$ holds except with probability at most $2^{-n}$ in the original construction, but we assume the algorithm restarts if it does not hold.</footnote>

<footnote n="3">³This happens only with exponentially small probability $2^{-\Theta(n)}$.</footnote>
With $\Lambda(A) = \{As|s \in \mathbb{Z}_q^n\}$, honestly generated ciphertext $c$ are such that $d(c-Encode(\mu), \Lambda(A)) \le B$, while the decryption procedure is guaranteed not to return $\mu$ as soon as $d(c-Encode(\mu), \Lambda(A)) > B$". From the decryption procedure, we have:

$$ \mu' := \mathrm{Dec}(\mathbf{T}, \mathbf{c}) \neq \perp \iff d(\mathbf{c} - \mathrm{Encode}(\mu'), \Lambda(\mathbf{A})) < B'' $$

Suppose that $m \ge \Theta(n \log q)$. The scheme is correct as long as $B \le B''$, or equivalently $2\sigma m^{3/2}$. $\omega(\sqrt{\log n}) \le q$.

**Theorem 4.2**

Assume $m \ge \Theta(n \log q)$. The above scheme is IND-CPA assuming the hardness of the LWE$_{\chi,q}$ problem for $\chi = D_{\mathbb{Z},\sigma}$.

Furthermore, this encryption scheme is homomorphic for plaintexts in $(\mathbb{Z}_2, +)$, and ciphertexts in $\mathbb{Z}_q^m$ with component-wise addition.

**Bit-SPHFwGZ from LWE Encryption Scheme.** We consider, an LWE encryption scheme defined with a superpolynomial modulus. More precisely, we set $m = n \log(q)$, $t = \sqrt{mn} \cdot \omega(\sqrt{\log(n)})$, $k = \Theta(n)$, $s \ge \Theta(\sqrt{n}) \wedge s/q = \mathrm{negl}(n)$, $s = \Omega(mk^2q^{2/3})$. We also set $R$ to be a probabilistic rounding function from $[0, 1]$ to $\{0, 1\}$, such that $R(x) = 1$ with probability $0.5 \cdot \cos(\frac{2\pi x}{q})$ and 0 otherwise.

We set $S_0 = S_1 = \{\sigma = \mathbf{A} = \mathbf{A}_0 + [0; \mathbf{G}]|(\mathbf{T}, \mathbf{A}_0) \leftarrow \mathrm{TrapGen}(1^n, 1^m, q)\}$, $\mathrm{td}_\sigma$ being $\mathbf{T}$. Then, $\mathcal{R}_0$ is defined as $\{\rho = \mathbf{v} \in \mathbb{Z}_q^m\}$ and $\mathcal{R}_1$ is the set composed of all the sums of two honest encryptions of 0, in other words as $\{\rho = \mathbf{A}(\mathbf{s} + \mathbf{s}') + \mathbf{e} + \mathbf{e}' \mod q | \mathbf{s}, \mathbf{s}' \leftarrow \mathbb{Z}_q^n, \mathbf{e}, \mathbf{e}' \leftarrow D_{\mathbb{Z},t}^m\}$ with $\|\mathbf{e}\| \le B$ and $\|\mathbf{e}'\| \le B$}, more simply $\mathcal{R}_1$ can be written as $\{\rho = \mathbf{A}(\mathbf{s}+\mathbf{s}') + \mathbf{e}+\mathbf{e}' \mod q | \mathbf{s}, \mathbf{s}' \in \mathbb{Z}_q^n, \mathbf{e}, \mathbf{e}' \leftarrow D_{\mathbb{Z},t}^m \wedge \|\mathbf{e}\| \le B \wedge \|\mathbf{e}'\| \le B\}$ with $\mathrm{td}_\rho = (\mathbf{A}\mathbf{s} + \mathbf{e}, \mathbf{A}\mathbf{s}' + \mathbf{e}', (\mathbf{s}, \mathbf{e}), (\mathbf{s}', \mathbf{e}'))$.

With $\mathcal{X} = \{\mathbf{c} \leftarrow \mathbb{Z}_q^m\}$, $\mathcal{L} = \{\mathbf{c} \exists \mathbf{s}, \mathbf{e}, \mathbf{c} = \mathrm{Enc}(\mathbf{A}_0, 0; \mathbf{s}, \mathbf{e})\}$ defined following the description above, and $\mathcal{L}' = \{\mathbf{c} \in \mathcal{X} | \mathrm{Dec}(\mathbf{T}, \mathbf{c}) \neq 0\}$, note that $\mathbf{s}$ could be enough as a witness for $\mathbf{c} = \mathbf{A}\mathbf{s} + \mathbf{e} \in \mathcal{L}$, as one can check $\mathbf{e} = \mathbf{c} - \mathbf{A}\mathbf{s}$ is small enough. This defines the Setup algorithm, and we have:

**Definition 4.2 - Bit-SPHFwGZ over Micciancio-Peikert like Ciphertexts [ ]**

For $k = \Theta(n)$, and picking $s \ge \Theta(\sqrt{n})$, and $s = \Omega(mk^2q^{2/3})$, we can define:

$$ - \mathrm{HashKG}(\mathrm{param}) = \mathbf{hk} = \mathbf{h} \leftarrow \mathcal{D}_{\mathbb{Z},s}^{m} $$

$$ - \mathrm{ProjKG}(\mathbf{hk}) = \mathbf{hp} = \mathbf{A}^t\mathbf{h} $$

$$ - \mathrm{Hash}(\mathbf{hk}, \mathbf{c}) = R(\langle\mathbf{hk}, \mathbf{c}\rangle) = R(\langle\mathbf{h}, \mathbf{c}\rangle) \in \{0, 1\} $$

$$ - \mathrm{ProjHash}(\mathbf{hp}, \mathbf{c}, w = \mathbf{s}) = R(\langle\mathbf{hp}, \mathbf{s}\rangle) = R(\langle\mathbf{A}^t\mathbf{h}, \mathbf{s}\rangle) $$

For a word $\mathbf{c} = \mathbf{A}\mathbf{s} + \mathbf{e}$ in the language $\mathcal{L}$, $\langle\mathbf{h}, \mathbf{c}\rangle = \mathbf{h}^t\mathbf{A}\mathbf{s} + \mathbf{h}^t\mathbf{e} = \langle\mathbf{A}^t\mathbf{h}, \mathbf{s}\rangle + \mathbf{h}^t\mathbf{e}$. And by construction $\mathbf{h}^t\mathbf{e}$ is small. The choice of the rounding function $R(x)$, characterized by a coin flip where the outcome 1 is weighted by $0.5 \cdot \cos(\frac{2\pi x}{q})$, is such that it allows to cancel out this small noise most of the time, while providing smoothness for words outside the language (ensuring that $R(\langle\mathbf{hk}, \mathbf{c}\rangle)$ is random when given only $\mathbf{hp}$)

It was shown in [BBDQ18], that for this choice of random function, such bit-SPHFwGZ achieves negligible-universality, thanks to the rounding function, but $(3/4 + o(1))$-correctness for the chosen set of parameters.

<footnote n="4">⁴Note that the inversion algorithm $g_{(\cdot)}^{-1}$ can succeed even if $\|\mathbf{e}\| > B''/2$, depending on the randomness of the trapdoor. It is crucial to reject decryption nevertheless when $\|\mathbf{e}\| > B''$ to ensure security.</footnote>
**Full-Fledged SPHFwGZ from LWE.** The previous construction has limitations as it is neither perfectly correct, nor smooth, we need to apply a transformation to reach those goals. This transformation is explained below, first informally, then in more details:

* It is a bit-function meaning the final hash value lives in $\{0, 1\}$, while one needs a larger mask. To solve this issue, one has to run it in parallel a linear number of times, to have an output string long enough.

* The correctness is imperfect. The output bit only matches with probability $3/4 + o(1)$. As such, applications running Enc(pk, m; r) should encryption a redundant version of m, with an error-correcting code, ECC(m). Such transformation makes the SPHF word-dependent (i.e. the projection key is dependent on the user/receiver input), however in our scenario, such a word-dependent function is enough.

* $\forall i \in [\ell]$, the verifier generates $\mathbf{h}_i \leftarrow D_{\mathbb{Z}_s}^m$, $\mathbf{h}_{\mathbf{p}_i} = \mathbf{A}^t \mathbf{h}_i$, $H_i = R(\langle \mathbf{h}_k, \mathbf{c} \rangle)$

* It then picks a random value $K \leftarrow \{0, 1\}^\kappa$, and compute $T = \text{ECC}(K) \oplus S$ where $S = \|\|_i H_i$, and sends $(\mathbf{h}_{\mathbf{p}_i})_{i \in [\ell]}$, $S$ to the prover.

* The prover can then compute, $\forall i \in [\ell]$, $H'_i = R(\langle \mathbf{h}_p, \mathbf{s} \rangle)$, then $S' = \|\|_i H'_i$, and finally recover $K' = \text{ECC}^{-1}(T \oplus S')$. As the SPHFwGZ has a correctness of $3/4 + o(1)$, the error correcting code can correct the small differences between $S$ and $S'$, and so $K' = K$.

To describe this in terms of SPHF, we use capital letters for our new construction:

* **SETUP(1**<sup>*κ*</sup>*):* Outputs the result from *Setup(1<sup>*κ*</sup>)*

* **HASHKG(param):** Picks a random $K \leftarrow \{0, 1\}^\kappa$, and $\forall i \in [\ell]$, gets $\mathbf{h}_{\mathbf{k}_i} = \text{HashKG(param)}$, and set $\text{HK} = (\{\mathbf{h}_{\mathbf{k}_i}\}, K)$;

* **ProjKG(HK, c):** $\forall i \in [\ell]$, gets $\mathbf{h}_{\mathbf{p}_i} = \text{ProjKG}(\mathbf{h}_{\mathbf{k}_i})$, $H_i = \text{Hash}(\mathbf{h}_{\mathbf{k}_i}, c)$. It then computes $T = \text{ECC}(K) \oplus S$ where $S = (H_i)_{i \in [\ell]}$, and outputs $\text{HP} = ((\mathbf{h}_{\mathbf{p}_i})_{i \in [\ell]}, T)$;

* **HASH(HK, c):** Returns $K$, from HK;

* **PROJHASH(HP, c, w = s):** $\forall i \in [\ell]$, computes $H'_i = \text{ProjHash}(\mathbf{h}_{\mathbf{p}_i}, c, s)$. Then computes $S' = (H'_i)_{i \in [\ell]}$, and finally $K' = \text{ECC}^{-1}(T \oplus S')$.

Such transformation allows to achieve smoothness which can be proven with an hybrid argument, handling intermediate distributions where the first $H_i$ values are random. The correctness is simply inherited from the correcting-code capacity, while the number of errors to be corrected can be estimated thanks to the Hoeffding's bound [Hoe63]. We can guarantee the expected properties:

* **Correctness:** When $x = c \in \mathcal{L}$, with the above conversion, we have $K = K'$ with overwhelming probability, thanks to the error-correcting code;

* **Smoothness:** When $x = c \notin \mathcal{L}$, then the value $K$ is random from an adversary point of view, as the parallelization technique allows to transform the negligible-universality to a classical smoothness (at the cost of a word-dependent SPHF);

* **Half Decomposition Intractability:** A random vector $\rho$ should not be split into two ciphertexts that could be decrypted to 0, or at least not too often. We first deal with *half* decomposition intractability, when at most half of the random vectors can be split.

To get a lower-bound on the number of vectors like such $\rho$, we can remark that a vector verifies this property as soon as $d(\rho, \Lambda(\mathbf{A}))$ is greater than 2 times the decryption bound.

This is the reason why we took a conservative value $B'' = B'/2$ in the encryption compared to classical Micciancio-Peikert encryption. By halving the decryption radius, we ensured that adding two elements that still decrypt within this bound will fall on classically decryptable ciphertexts. As such, at least half the elements cannot be reached (those that classically decrypted to 1). Hence, $\Pr_{\rho \in \mathbb{Z}_q^m} [\exists \mathbf{c}, \mathbf{d} | \rho = \mathbf{c} + \mathbf{d} \wedge \text{Dec}(\mathbf{sk}, \mathbf{c}) = \text{Dec}(\mathbf{sk}, \mathbf{d}) = 0] \le 1/2$. This is a statistical bound, that holds even when knowing the decryption key.
Another amplification is required to make full-fledged decomposition intractability, by working on ciphertexts $(\mathbf{c}_j)_{j \in [k]}$, with $k$ parallel executions of the SPHFwGZ, with a final XOR of all the outputs, so that the smoothness for one word is enough to get the smoothness for the vector of words, but the correctness on all the words leads to the global correctness. The acceptable language, for correctness is then:

$$ \tilde{\mathcal{L}} = \mathcal{L}^k = \{(\mathbf{c}_j)_{j \in [k]} | (\forall j \in [k]), \exists (\mathbf{s}_j, \mathbf{e}_j), \mathbf{c} = \text{Enc}(\mathbf{A}_0, 0; \mathbf{s}_j, \mathbf{e}_j)\} \subset \mathcal{X}^k $$

whereas the language for the smoothness becomes:

$$ \tilde{\mathcal{L}}' = \mathcal{L}'^k = \{(\mathbf{c}_j)_{j \in [k]} | (\exists j \in [k]), \text{Dec}(\mathbf{T}, \mathbf{c}_j) \neq 0\} \subset \mathcal{X}^k $$

Then, for random $(\rho_j)_{j \in [k]} \leftarrow \mathcal{X}^k$, a decomposition would be a list of pairs $(\mathbf{c}_j, \mathbf{d}_j)_{j \in [k]} \in (\mathcal{X} \times \mathcal{X})^k$ such that for all $j$, $\rho_j = \mathbf{c}_j + \mathbf{d}_j$ and $\text{Dec}(\mathbf{T}, \mathbf{c}_j) = \text{Dec}(\mathbf{T}, \mathbf{d}_j) = 0$, which only exists with probability less than $1/2^k$. We thus have achieved all the security properties required for our applications.
Chapter 5

Computational security analysis of the
EDHOC protocol

A key agreement is under analysis by IETF [SMP21], under the name Ephemeral Diffie-Hellman Over COSE (EDHOC). EDHOC aims at being a very compact and lightweight authenticated Diffie-Hellman key exchange with ephemeral keys. This protocol is deeply inspired from SIGMA [Kra03] and OPTLS [KW16] and targets constrained devices over low-power IoT radio communication technologies. For this reason, very aggressive parameters are proposed to minimize the communications. Nonetheless, it is still expected to provide mutual authentication, forward secrecy, and identity protection, with a 128-bit security level even with those aggressive parameters. A formal analysis has already been proposed at SECRYPT'21 [NSB21], on a former version, leading to some improvements, in the ongoing evaluation process by IETF. Unfortunately, while formal analysis can detect some misconceptions in the protocol, it cannot evaluate the actual security level. In this chapter, we analyze the computational security of the last version of EDHOC.

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

<footnote>★ Baptiste Cottier and David Pointcheval. Security Analysis of Improved EDHOC Protocol. In *The 15th International Symposium on Foundations & Practice of Security*, pages 1–16, 2022</footnote>
# Contents

<table><tr><td>5.1 Protocol description</td><td>92</td></tr><tr><td>5.2 Key privacy</td><td>94</td></tr><tr><td>5.3 Explicit authentication</td><td>103</td></tr><tr><td>5.4 Identity protection</td><td>104</td></tr><tr><td>5.5 Improvements</td><td>106</td></tr><tr><td>5.5.1 Improved mutual authentication with more flows</td><td>106</td></tr><tr><td>5.5.2 Improved EDHOC protocol</td><td>107</td></tr></table>

# Notations & Acronyms

<table><thead><tr><th colspan="2">Protocol Description</th></tr></thead><tbody><tr><td>CBOR</td><td>Concise Binary Object Representation</td></tr><tr><td>COSE</td><td>CBOR object signing and encryption</td></tr><tr><td>EDHOC</td><td>Ephemeral Diffie-Hellman over COSE</td></tr><tr><td>Η</td><td>Hash function SHA-256 (256 bits digest)</td></tr><tr><td>X<sub>e</sub>, x<sub>e</sub></td><td>Initiator Ephemeral DH Public and Secret Key</td></tr><tr><td>X<sub>s</sub>, x<sub>s</sub></td><td>Initiator Static DH Public and Secret Key</td></tr><tr><td>Y<sub>e</sub>, y<sub>e</sub></td><td>Responder Ephemeral DH Public and Secret Key</td></tr><tr><td>Y<sub>s</sub>, y<sub>s</sub></td><td>Responder Static DH Public and Secret Key</td></tr><tr><td>HKDF</td><td>HMAC-based Key Derivation Function</td></tr><tr><td>PRK</td><td>Pseudorandom Key</td></tr><tr><td>ε, D</td><td>One-time Encryption and Decryption</td></tr><tr><td>ε', D'</td><td>Authenticated Encryption and Decryption with Associated Data</td></tr><tr><td>IV</td><td>Initialization Vector</td></tr><tr><td>EAD</td><td>External Authorized Data</td></tr><tr><td>⊥</td><td>Protocol abortion</td></tr><tr><td>TH</td><td>Transcript Hash</td></tr><tr><td>t<sub>2</sub>, t<sub>3</sub></td><td>MAC tags</td></tr><tr><td>C<sub>R</sub>, C<sub>I</sub></td><td>Connection Identifiers</td></tr></tbody></table>

<table><caption>Figure 5.1: Notations</caption><thead><tr><th colspan="2">Security Analysis</th></tr></thead><tbody><tr><td>l<sub>MAC</sub></td><td>MAC output length</td></tr><tr><td>l<sub>plaintext</sub></td><td>Plaintext length of the first message send by the responder</td></tr><tr><td>l<sub>hash</sub></td><td>Hash length</td></tr><tr><td>l<sub>key</sub>, l<sub>IV</sub></td><td>Key and IV length</td></tr></tbody></table>
We first give a description of the EDHOC protocol, then prove key privacy, explicit authentication and identity protection. We close the chapter by giving some improvements to the actual protocol.

## 5.1 Protocol description

Ephemeral Diffie-Hellman over COSE [Sch16] (EDHOC) aims to provide a public-key exchange of two parties, denoted Initiator (that initiates the key exchange) and Responder, potentially running on constrained devices over low-power IoT radio communication technologies. EDHOC protocol can be instantiated with several settings:

*   **Authentication Method**: Each party (Initiator and Responder) can use an authentication method: either by Signature or by using a Static DH Key.

<table><thead><tr><td>Value</td><td>Initiator</td><td>Responder</td><td>Denotation</td></tr></thead><tbody><tr><td>0</td><td>Signature</td><td>Signature</td><td>SIG-SIG</td></tr><tr><td>1</td><td>Signature</td><td>Static DH</td><td>SIG-STAT</td></tr><tr><td>2</td><td>Static DH</td><td>Signature</td><td>STAT-SIG</td></tr><tr><td>3</td><td>Static DH</td><td>Static DH</td><td>STAT-STAT</td></tr></tbody></table>

*   **Cipher Suites**: Ordered set of protocol security settings. Initial paper offers many possible suites, including ones with either 8 or 16 bytes MAC, but we focus on the cipher suites with agressive MAC length set to 8 bytes, i.e. Cipher Suites 0 and 2 which share the following parameters:

<table><thead><tr><td>(Application) AEAD</td><td>Hash</td><td>MAC len</td></tr></thead><tbody><tr><td>AES-CCM-16-64-128</td><td>SHA-256</td><td>8</td></tr></tbody></table>

The difference between Cipher Suites 0 and 2 is the Elliptic Curve used: X25519 in suite 0 and P-256 in suite 2.

*   **Connection Identifiers**. Data that may be used to correlate between messages and facilitate retrieval of protocol state in EDHOC and application.

*   **Credentials and Identifiers**. They are used to identify and optionally transport the authentication keys of the Initiator and the Responder.

As this is the setup in which we are doing the security analysis, we can assume both the Initiator and the Responder agreed to use the authentication method 3, where both use Static Diffie-Hellman keys. Also, as the difference between Cipher Suite 0 and Cipher Suite 2 is the choice of the Elliptic Curve, both providing the same security, we do not include the Cipher Suite ID Suites_I (as it appears in [SMP21]) in the first message of the protocol.

**Extract and Expand.** In the EDHOC Key-Schedule defined below, the pseudorandom keys (PRK) are derived using an extraction function. In our context, as we study cipher suites 0 and 2, our hash algorithm is set as SHA-256. Therefore Extract(salt, IKM) =HKDF-Extract (salt, IKM) is defined with SHA-256, where IKM holds for Input Keying Material (in our context, this will be some Diffie-Hellman keys) and Expand(PRK, info, len) =HKDF-Expand (PRK, info, len) where info contains the transcript hash ($TH_2$, $TH_3$ or $TH_4$), the name of the derived key and some context, while len denotes the output length.
**Key Schedule.** During the key exchange, several cryptographic computations occur. The keying material, including MAC Keys (as we study STAT-STAT method), Encryption Keys and Initialization Vectors result from a key schedule, adapted from Norrman et al. [NSB21]. In Figure 5.2, purple boxes denote Diffie-Hellman shared secrets ($g^{x_e y_e}$, $g^{y_s x_e}$, $g^{x_s y_e}$), where $x_e$ and $y_e$ denote the ephemeral keys, while $x_s$ and $y_s$ are the long-term static DH keys. From those Diffie-Hellman shared secrets, we extract the pseudo random keys PRK$_{2e}$, PRK$_{3e2m}$ and PRK$_{4e3m}$, in light blue. Those keys are then expanded to compute the encryption material (keys and IV), in red, and the authentication tags $t_2$ and $t_3$, in yellow. Keys PRK$_{2e}$ and PRK$_{3e2m}$ are also used to compute the salts $salt_{3e2m}$ and $salt_{4e3m}$ respectively, in gray, used in the HKDF -Extract function. The final session key PRK$_{out}$, backgrounded in green, is computed calling HKDF -Expand on PRK$_{4e3m}$. Transcript hashes, denoted TH$_i$, are used as input to the HKDF -Expand function. More precisely, with SHA-256 as $\mathcal{H}$, we have:

$$TH_2 = \mathcal{H}(Y_e, C_R, \mathcal{H}(m_1)) \qquad TH_3 = \mathcal{H}(TH_2, m_2) \qquad TH_4 = \mathcal{H}(TH_3, m_3)$$

where $m_1$ is the first message sent by the Initiator, $m_2$ and $m_3$ respectively are the plaintexts respectively encrypted in the message 2 and message 3.

<figure><img src="image_42.png" /><figcaption>Figure 5.2: Key Derivation (for the STAT-STAT Method).</figcaption></figure>

**Authenticated Encryption with Associated Data (AEAD).** As said above, the cipher suites we work on both use AES-CCM-16-64-128. We detail this Authenticated Encryption scheme:

* AES-CCM: CCM, for Counter with CBC-MAC is an AES mode providing both encryption and authentication. CCM mode combines the CBC-MAC and the CTR (counter) mode of encryption. The first step consists in calculating a tag $T$, then, encrypt the message and the tag using the counter mode. Hence, the authenticated encryption is done in the Mac-then-Encrypt approach.

* 16: messages length is limited to $2^{16}$ bytes long (64KiB). Therefore, the nonce is 13 bytes long allowing $2^{13 \times 8}$ possible values of the nonce without repeating
* 64: Tag is 64 bits long.

* 128: Key is 128 bits long.

**Connection Identifiers (from [SMP21])**. Connection identifiers ($C_I$ and $C_R$) may be used to correlate EDHOC messages and facilitate the retrieval of protocol state during EDHOC protocol execution or in a subsequent application protocol. The connection identifiers do not have any cryptographic purpose in EDHOC.

**EDHOC-Exporter and EDHOC-KeyUpdate.** At the end of the protocol, the Initiator and the Responder compute $TH_4$. This value can be used in case an application need to export the EDHOC session key. Also, in case the key needs to be updated, the Initiator and the Responder rerun HKDF-Extract, with $PRK_{4e3m}$ as input, together with a random nonce agreed upon by the Initiator and the Responder.

**Protocol.** The detailed description of the protocol is given in Fig 5.3. The final session key is $SK = PRK_{out}$

**Security Goals.** The security goals of an authenticated key exchange protocol are:

* *Key Privacy:* Equivalent to Implicit Authentication. At most both participants know the final session key. With additional *Perfect Forward Secrecy*, by compromising the long-term credential of either peer, an attacker shall not be able to compute past session keys. In our context, this will rely on a Diffie-Hellman assumption.

* *Mutual Authentication:* Equivalent to explicit authentication. Exactly both participants have the material to compute the final session key.

* *Identity Protection:* At most both participants know the identity of the Initiator and the Responder.

## 5.2 Key privacy

An authenticated key exchange protocol AKE can be defined using three algorithms:

* $KGen(ID)$ takes an identity ID as input and samples a long term pair of keys ($pk, sk$). Key pairs are associated to that user with identity ID, and the public key is added to the list *peerpk*.

* *Activate(ID, role)* takes as input a user identity ID and its *role* ∈ {initiator, responder}. Activate returns a state *st* and a message *m*′.

* *Run(ID, sk, peerpk, m)* delivers *m* to the session of user ID with secret key *sk* and state *st*. Run updates the state *st* and returns the response message *m*′

Algorithm *Run* takes as implicit argument a state *st*, that contains some information, denoted in *typewriter font*, about the actual session. A value *peerid* ∈ $\mathbb{N}$ used to identify the intended partner identity of the session, a *role*, either initiator or responder, defining the role played by the session. The state also contains the *status* of the actual session. Either the session *status* is **running**, meaning the session has been activated, **accepted**, meaning that a party has all the material to compute the session key or **terminated** when the session key is computed and the protocol is ended. We also consider a **rejected** flag in case the session meets a mistake in the verification phase. The final session key is stored in *SK* and set as $⊥$ until defined by the key schedule. Finally, *sid* stores the session identifier used to define partnered session in the security model.
<table><caption>Figure 5.3: EDHOC Protocol in the Static-Static Method</caption><thead><tr><th>Initiator</th><th>static keys</th><th>Responder</th></tr></thead><tbody><tr><td>X<sub>s</sub> = g<sup>x<sub>s</sub></sup></td><td></td><td>Y<sub>s</sub> = g<sup>y<sub>s</sub></sup></td></tr><tr><td colspan="3"><strong>InitRun1(ID<sub>1</sub>)</strong></td></tr><tr><td>x<sub>e</sub> &larr; $\mathbb{Z}_p$, X<sub>e</sub> &larr; g<sup>x<sub>e</sub></sup></td><td></td><td></td></tr><tr><td>C<sub>1</sub> &larr; {0, 1}<sup>n<sub>1</sub></sup></td><td></td><td></td></tr><tr><td>m<sub>1</sub> &larr; (X<sub>e</sub>||C<sub>1</sub>||EAD<sub>1</sub>)</td><td>m<sub>1</sub> &rarr;</td><td></td></tr><tr><td colspan="3"><strong>RespRun1(ID<sub>R</sub>, y<sub>s</sub>, m<sub>1</sub>)</strong></td></tr><tr><td>Parse m<sub>1</sub> as (X<sub>e</sub>||c||EAD<sub>1</sub>)</td><td></td><td></td></tr><tr><td>y<sub>e</sub> &larr; $\mathbb{Z}_p$, Y<sub>e</sub> &larr; g<sup>y<sub>e</sub></sup></td><td></td><td></td></tr><tr><td>C<sub>R</sub> &larr; {0, 1}<sup>n<sub>R</sub></sup></td><td></td><td></td></tr><tr><td>sid &larr; (C<sub>1</sub>, C<sub>R</sub>, X<sub>e</sub>, Y<sub>e</sub>)</td><td></td><td></td></tr><tr><td>PRK<sub>2e</sub> &larr; HKDF-Extract("", X<sub>e</sub><sup>y<sub>e</sub></sup>)</td><td></td><td></td></tr><tr><td>TH<sub>2</sub> &larr; H(Y<sub>e</sub>, C<sub>R</sub>, H(m<sub>1</sub>))</td><td></td><td></td></tr><tr><td>sk<sub>2</sub> &larr; HKDF-Expand(PRK<sub>2e</sub>, 0, TH<sub>2</sub>, l<sub>plaintext</sub>)</td><td></td><td></td></tr><tr><td>salt<sub>3e2m</sub> &larr; HKDF-Expand(PRK<sub>2e</sub>, 1, TH<sub>2</sub>, l<sub>hash</sub>)</td><td></td><td></td></tr><tr><td>PRK<sub>3e2m</sub> &larr; HKDF-Extract(salt<sub>3e2m</sub>, Y<sub>s</sub><sup>x<sub>s</sub></sup>)</td><td></td><td></td></tr><tr><td>t'<sub>2</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 2, CTX<sub>2</sub>, l<sub>MAC</sub>)</td><td></td><td></td></tr><tr><td>if t'<sub>2</sub> &ne; t<sub>2</sub> : return &perp;</td><td></td><td></td></tr><tr><td>TH<sub>3</sub> &larr; H(TH<sub>2</sub>, m<sub>2</sub>)</td><td></td><td></td></tr><tr><td>sk<sub>3</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 3, TH<sub>3</sub>, l<sub>key</sub>)</td><td></td><td></td></tr><tr><td>IV<sub>3</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 4, TH<sub>3</sub>, l<sub>IV</sub>)</td><td></td><td></td></tr><tr><td>salt<sub>4e3m</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 5, TH<sub>3</sub>, l<sub>hash</sub>)</td><td></td><td></td></tr><tr><td>PRK<sub>4e3m</sub> &larr; HKDF-Extract(salt<sub>4e3m</sub>, Y<sub>s</sub><sup>x<sub>s</sub></sup>)</td><td></td><td></td></tr><tr><td>accepted &larr; 1</td><td></td><td></td></tr><tr><td>CTX<sub>3</sub> &larr; (ID<sub>1</sub>||TH<sub>3</sub>||X<sub>s</sub>||EAD<sub>3</sub>)</td><td></td><td></td></tr><tr><td>t<sub>3</sub> &larr; HKDF-Expand(PRK<sub>4e3m</sub>, 6, CTX<sub>3</sub>, l<sub>MAC</sub>)</td><td></td><td></td></tr><tr><td>m<sub>3</sub> &larr; (ID<sub>1</sub>||t<sub>3</sub>||EAD<sub>3</sub>)</td><td></td><td></td></tr><tr><td>c<sub>3</sub> &larr; E'(sk<sub>3</sub>, IV<sub>3</sub>, m<sub>3</sub>)</td><td>c<sub>3</sub> &larr;</td><td></td></tr><tr><td colspan="3"><strong>RespRun2(ID, st, peerpk, c<sub>3</sub>)</strong></td></tr><tr><td>TH<sub>3</sub> &larr; H(TH<sub>2</sub>, m<sub>2</sub>)</td><td></td><td></td></tr><tr><td>sk<sub>3</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 3, TH<sub>3</sub>, l<sub>key</sub>)</td><td></td><td></td></tr><tr><td>IV<sub>3</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 4, TH<sub>3</sub>, l<sub>IV</sub>)</td><td></td><td></td></tr><tr><td>set m<sub>3</sub> &larr; D'(sk<sub>3</sub>, IV<sub>2</sub>, c<sub>3</sub>)</td><td></td><td></td></tr><tr><td>if m<sub>3</sub> = &perp; : return &perp;</td><td></td><td></td></tr><tr><td>parse m<sub>3</sub> as (ID<sub>1</sub>||t<sub>3</sub>||EAD<sub>3</sub>)</td><td></td><td></td></tr><tr><td>X<sub>s</sub> &larr; peerpk(ID<sub>1</sub>)</td><td></td><td></td></tr><tr><td>salt<sub>4e3m</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 5, TH<sub>3</sub>, l<sub>hash</sub>)</td><td></td><td></td></tr><tr><td>PRK<sub>4e3m</sub> &larr; HKDF-Extract(salt<sub>4e3m</sub>, X<sub>s</sub><sup>y<sub>s</sub></sup>)</td><td></td><td></td></tr><tr><td>accepted &larr; 1</td><td></td><td></td></tr><tr><td>CTX<sub>3</sub> &larr; (ID<sub>1</sub>||TH<sub>3</sub>||X<sub>s</sub>||EAD<sub>3</sub>)</td><td></td><td></td></tr><tr><td>t'<sub>3</sub> &larr; HKDF-Expand(PRK<sub>4e3m</sub>, 6, CTX<sub>3</sub>, l<sub>MAC</sub>)</td><td></td><td></td></tr><tr><td>if t'<sub>3</sub> &ne; t<sub>3</sub> : return &perp;</td><td></td><td></td></tr><tr><td>TH<sub>4</sub> &larr; H(TH<sub>3</sub>, m<sub>3</sub>)</td><td></td><td></td></tr><tr><td>PRK<sub>out</sub> &larr; HKDF-Expand(PRK<sub>4e3m</sub>, 7, TH<sub>4</sub>, l<sub>hash</sub>)</td><td></td><td></td></tr><tr><td>terminated &larr; 1</td><td></td><td></td></tr><tr><td>SK &larr; PRK<sub>out</sub></td><td></td><td></td></tr></tbody></table>
We describe in Figure 5.4 the security game introduced in [DG20] following the framework by Bellare et al. [BR06]. After initializing the game, the adversary A is given multiple access to the following queries:

* NewUser: Generates a new user by generating a new pair of keys.

* Send: Controls activation and message processing of sessions

* SessionKeyReveal: Reveals the session key of a terminated session.

* LongTermKeyReveal: Corrupts a user and reveals its long term secret key.

* Test: Provides a real-or-random challenge on the session key of the queried session.

Then, the adversary makes a single call to the Finalize algorithm, which returns the result of the predicate $[b' = b]$, where $b'$ is the guess of A and $b$ is the challenge bit, after succeeding through the following predicates:

**Sound:** ensures at most two sessions share the same sid. Once a couple of sessions is detected, the predicate checks if both of them have their status accepted, one session user ID is the peerid of the other session, with different role and the same final session key SK. If one of these property is not verified, the adversary breaks the soundness.

**Fresh:** detects trivially attacked sessions. First, it ensures that neither the session key is revealed nor any of the peers of the session is corrupted before the acceptance time $t_{acc}$. In a second time, the Fresh predicate ensures that the partnered session is neither tested nor revealed. If such a session is detected, we set the answer bit $b'$ as 0.

The advantage of an adversary A against the key privacy is its bias in guessing $b$, from the random choice: $Adv_{kp-ake}^{kp-ake}(A) = \Pr[b' = b] - 1/2$. Therefore, in Figure 5.5 we give a formalized description of the EDHOC protocol compliant with the security game made in Figure 5.4. The protocol is analyzed in the random oracle model, therefore, HKDF can be substituted by respective random oracles.

## Theorem 5.1

The above EDHOC protocol satisfies the key privacy property under the Gap Diffie-Hellman problem in the Random Oracle model, and the injectivity of $(\mathcal{E}, \mathcal{D})$. More precisely, with $q_{RO}$ representing the global number of queries to the random oracles, $n_{\sigma}$ the number of running sessions, $N$ the number of users, and $\ell_{hash}$ the hash digest length, we have $Adv_{EDHOC}^{kp-ake}(t; q_{RO}, n_{\sigma}, N)$ upper-bounded by

$$Adv_{\mathcal{G}}^{GDH}(t, n_{\sigma} \cdot q_{RO}) + 2N \cdot Adv_{\mathcal{G}}^{GDH}(t, q_{RO}) + \frac{q_{RO}^2 + 4}{2\ell_{hash} + 1}$$

**Game** $G_0$. This game is the key privacy security game $G_{AKE,A}^{kp-ake}$ (defined in Figure 5.4) played by A using the KGen, Activate and Run algorithms (defined in Figure 5.5). The KGen algorithm generates a long term pair of key, calling Activate with a user with identity $u$, A creates its $i$-th session with $u$, denoted $\pi_u^i$.

$$Pr[Succ_0] = Pr[G_{AKE,A}^{kp-ake}]$$

where the event Succ means $b' = b$.

We stress that in this security model, with Perfect Forward Secrecy, we use the weak definition of corruption, meaning that a query to LongTermKeyReveal only reveals the long-term key, while the ephemeral key remains unrevealed. We say a party/session is non-corrupted if no query to LongTermKeyReveal has been made before the time of acceptance $t_{acc}$, where we consider each block (InitRun1, InitRun2, RespRun1, RespRun2) as atomic. Then corruptions can only happen between two calls to simulated players.
Initialize ()

1. time ← 0

2. users ← 0

3. b ← $ \{0, 1\}

NewUser ()

1. users ← users + 1

2. (pk<sub>users</sub>, sk<sub>users</sub>) ← $ KGen

3. revatk<sub>users</sub> ← ∞

4. peerpk[users] ← pk<sub>users</sub>

5. return pk<sub>users</sub>

LongTermKeyReveal(u)

1. time ← time + 1

2. revatk<sub>u</sub> ← time

3. return sk<sub>u</sub>

SessionKeyReveal(u, i)

1. if $\pi_u^i = \perp$ or

$\pi_u^i.status \neq \text{accepted}$:

2. return $\perp$

3. $\pi_u^i$.revealed ← true

4. return $\pi_u^i$.SK

Finalize(b')

1. if $\neg$Sound:

2. return 1

3. if $\neg$Fresh:

4. $b' \leftarrow 0$

5. return $[b = b']$

Send(u, i, m)

1. if $\pi_u^i = \perp$:

2. (peerid, role) ← m

3. ($\pi_u^i, m'$) ← $\$ \text{Activate}(u, sk_u, \text{peerid}, \text{peerpk}, \text{role})$

4. $\pi_u^i \cdot t_{acc} \leftarrow 0$

5. else :

6. ($\pi_u^i, m'$) ← $\$ \text{Run}(u, sk_u, \pi_u^i, \text{peerpk}, \text{role})$

7. if $\pi_u^i$.status = accepted :

8. time ← time + 1

9. $\pi_u^i \cdot t_{acc} \leftarrow$ time

10. return $m'$

Sound

1. if $\exists$ distinct $\pi_u^i, \pi_v^i, \pi_w^k$ with $\pi_u^i$.sid = $\pi_v^j$.sid = $\pi_w^k$.sid:

2. return false

3. if $\exists \pi_u^i, \pi_v^i$ with

4. $\pi_u^i$.status = $\pi_v^i$.status = accepted

5. and $\pi_u^i$.sid = $\pi_v^j$.sid

6. and $\pi_u^i$.peerid = u and $\pi_v^j$.peerid = v

7. and $\pi_u^i$.role $\neq$ $\pi_v^j$.role, but $\pi_u^i$.SK $\neq$ $\pi_v^j$.SK

8. return false

9. return true

Test(u, i)

1. if $\pi_u^i = \perp$ or

$\pi_u^i.status \neq \text{accepted}$ or $\pi_u^i.tested$

2. return $\perp$

3. $\pi_u^i$.tested ← true

4. $T \leftarrow T \cup \{\pi_u^i\}$

5. $k_0 \leftarrow \pi_u^i$.SK

6. $k_1 \leftarrow \$ KE.KS$

7. return $k_b$

Fresh

1. $\forall \pi_u^i \in T$

2. if $\pi_u^i$.revealed

or revatk<sub>$\pi_u^i$.peerid</sub> < $\pi_u^i \cdot t_{acc}$:

3. return false

4. if $\exists \pi_v^j \neq \pi_u^i$.s.t.

$\pi_u^i$.sid = $\pi_u^i$.sid and

($\pi_v^j$.tested or $\pi_v^j$.revealed):

5. return false

6. return true

<caption>Figure 5.4: Authenticated Key Exchange Key Privacy Security Game $G_{AKE,A}^{kp-ake}$</caption>
<table><caption>Figure 5.5: Formalized description of the EDHOC protocol</caption>
  <thead>
    <tr>
      <th>KeyGen()</th>
      <th>Run(ID, sk, peerpk, m)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>1. sk &larr; $Z_p<br>2. pk &larr; g<sup>Z_p</sup><br>3. <strong>return</strong> (pk, sk)<br>Activate(ID, role)</td>
      <td>1. <strong>if</strong> status &ne; <strong>running</strong>:<br>2. <strong>return</strong> &perp;<br>3. <strong>if</strong> role = initiator:<br>4. m' &larr; InitRun2(ID, sk, m)<br>5. <strong>else</strong> sid = &perp;:<br>6. m' &larr; RespRun1(ID, sk, m)<br>7. <strong>else</strong>:<br>8. m' &larr; RespRun2(ID, peerpk, m)<br>9. <strong>return</strong> m<br>RespRun1(ID<sub>R</sub>, y<sub>s</sub>, m<sub>1</sub> = (X<sub>e</sub>, C<sub>I</sub>, EAD<sub>1</sub>))</td>
    </tr>
    <tr>
      <td>1. role &larr; role<br>2. status &larr; <strong>running</strong><br>3. <strong>if</strong> role = initiator:<br>4. m' &larr; InitRun1(ID)<br>5. <strong>else</strong> m' &larr; &perp;<br>6. <strong>return</strong> m<br>InitRun1(ID<sub>I</sub>)</td>
      <td>1. y<sub>e</sub> &larr; $Z_p<br>2. Y<sub>e</sub> &larr; g<sup>y<sub>e</sub></sup><br>3. C<sub>R</sub> &larr; {0, 1}<sup>nI</sup><br>4. sid &larr; (C<sub>I</sub>, C<sub>R</sub>, X<sub>e</sub>, Y<sub>e</sub>)<br>5. PRK<sub>2e</sub> &larr; RO<sub>T</sub>("", X<sub>e</sub><sup>y<sub>e</sub></sup>)<br>6. sk<sub>2</sub> &larr; RO<sub>P</sub>(PRK<sub>2e</sub>, 0, TH<sub>2</sub>, l<sub>plaintext</sub>)<br>7. salt<sub>3e2m</sub> &larr; RO<sub>P</sub>(PRK<sub>2e</sub>, 1, TH<sub>2</sub>, l<sub>hash</sub>)<br>8. PRK<sub>3e2m</sub> &larr; RO<sub>T</sub>(salt<sub>3e2m</sub>, X<sub>e</sub><sup>y<sub>s</sub></sup>)<br>9. TH<sub>2</sub> &larr; H(Y<sub>e</sub>, C<sub>R</sub>, H(m<sub>1</sub>))</td>
    </tr>
    <tr>
      <td>1. x<sub>e</sub> &larr; $Z_p<br>2. X<sub>e</sub> &larr; g<sup>x<sub>e</sub></sup><br>3. C<sub>I</sub> &larr; {0, 1}<sup>nI</sup><br>4. st &larr; (C<sub>I</sub>, X<sub>e</sub>, x<sub>e</sub>)<br>5. m<sub>1</sub> &larr; (C<sub>I</sub>||X<sub>e</sub>||EAD<sub>1</sub>)<br>6. <strong>return</strong> m<sub>1</sub><br>InitRun2(ID<sub>I</sub>, x<sub>s</sub>, (Y<sub>e</sub>, c<sub>2</sub>, C<sub>R</sub>))</td>
      <td>10. CTX<sub>2</sub> &larr; (ID<sub>R</sub>||TH<sub>2</sub>||Y<sub>s</sub>||EAD<sub>2</sub>)<br>11. t<sub>2</sub> &larr; RO<sub>P</sub>(PRK<sub>3e2m</sub>, 2, CTX<sub>2</sub>, l<sub>MAC</sub>)<br>12. m<sub>2</sub> &larr; (ID<sub>R</sub>||t<sub>2</sub>||EAD<sub>2</sub>)<br>13. c<sub>2</sub> &larr; E(sk<sub>2</sub>, m<sub>2</sub>)<br>14. <strong>return</strong> (Y<sub>e</sub>, c<sub>2</sub>, C<sub>R</sub>)<br>RespRun2(ID<sub>R</sub>, peerpk, c<sub>3</sub>)</td>
    </tr>
    <tr>
      <td>1. PRK<sub>2e</sub> &larr; RO<sub>T</sub>("", Y<sub>e</sub><sup>x<sub>e</sub></sup>)<br>2. TH<sub>2</sub> &larr; H(Y<sub>e</sub>, C<sub>R</sub>, H(m<sub>1</sub>))<br>3. sk<sub>2</sub> &larr; RO<sub>P</sub>(PRK<sub>2e</sub>, 0, TH<sub>2</sub>, l<sub>plaintext</sub>)<br>4. m<sub>2</sub> &larr; D(sk<sub>2</sub>, c<sub>2</sub>)<br>5. (ID<sub>R</sub>||t<sub>2</sub>||EAD<sub>2</sub>) &larr; m<sub>2</sub><br>6. CTX<sub>2</sub> &larr; (ID<sub>R</sub>||TH<sub>2</sub>||Y<sub>s</sub>||EAD<sub>2</sub>)<br>7. salt<sub>3e2m</sub> &larr; RO<sub>P</sub>(PRK<sub>2e</sub>, 1, TH<sub>2</sub>, l<sub>hash</sub>)<br>8. PRK<sub>3e2m</sub> &larr; RO<sub>T</sub>(salt<sub>3e2m</sub>, Y<sub>s</sub><sup>x<sub>e</sub></sup>)<br>9. t<sub>2</sub> &larr; RO<sub>P</sub>(PRK<sub>3e2m</sub>, 2, CTX<sub>2</sub>, l<sub>MAC</sub>)</td>
      <td>1. TH<sub>3</sub> &larr; H(TH<sub>2</sub>, m<sub>2</sub>)<br>2. sk<sub>3</sub> &larr; RO<sub>P</sub>(PRK<sub>3e2m</sub>, 3, TH<sub>3</sub>, l<sub>key</sub>)<br>3. IV<sub>3</sub> &larr; RO<sub>P</sub>(PRK<sub>3e2m</sub>, 4, TH<sub>3</sub>, l<sub>IV</sub>)<br>4. m<sub>3</sub> &larr; D'(sk<sub>3</sub>, IV<sub>3</sub>, c<sub>3</sub>)<br>5. <strong>if</strong> m<sub>3</sub> = &perp;:<br>6. status &larr; <strong>rejected</strong><br>7. <strong>return</strong> &perp;<br>(ID<sub>I</sub>||t<sub>3</sub>||EAD<sub>3</sub>) &larr; m<sub>3</sub><br>9. X<sub>s</sub> &larr; peerpk(ID<sub>I</sub>)</td>
    </tr>
    <tr>
      <td>10. <strong>if</strong> t'<sub>2</sub> &ne; t<sub>2</sub>:<br>11. status &larr; <strong>rejected</strong><br>12. <strong>return</strong> &perp;<br>13. TH<sub>3</sub> &larr; H(TH<sub>2</sub>, m<sub>2</sub>)<br>14. sk<sub>3</sub> &larr; RO<sub>P</sub>(PRK<sub>3e2m</sub>, 3, TH<sub>3</sub>, l<sub>key</sub>)<br>15. IV<sub>3</sub> &larr; RO<sub>P</sub>(PRK<sub>3e2m</sub>, 4, TH<sub>3</sub>, l<sub>IV</sub>)<br>16. salt<sub>4e3m</sub> &larr; RO<sub>P</sub>(PRK<sub>3e2m</sub>, 5, TH<sub>3</sub>, l<sub>hash</sub>)<br>17. PRK<sub>4e3m</sub> &larr; RO<sub>T</sub>(salt<sub>4e3m</sub>, Y<sub>s</sub><sup>x<sub>s</sub></sup>)<br>18. status &larr; <strong>accepted</strong><br>19. CTX<sub>3</sub> &larr; (ID<sub>I</sub>||TH<sub>3</sub>||X<sub>s</sub>||EAD<sub>3</sub>)<br>20. t<sub>3</sub> &larr; RO<sub>P</sub>(PRK<sub>4e3m</sub>, 6, CTX<sub>3</sub>, l<sub>MAC</sub>)<br>21. m<sub>3</sub> &larr; (ID<sub>I</sub>||t<sub>3</sub>||EAD<sub>3</sub>)<br>22. c<sub>3</sub> &larr; E(sk<sub>3</sub>, IV<sub>3</sub>, m<sub>3</sub>)<br>23. TH<sub>4</sub> &larr; H(TH<sub>3</sub>, m<sub>3</sub>)<br>24. PRK<sub>out</sub> &larr; RO<sub>P</sub>(PRK<sub>4e3m</sub>, 7, TH<sub>4</sub>, l<sub>hash</sub>)<br>25. status &larr; <strong>terminated</strong><br>26. SK &larr; PRK<sub>out</sub><br>27. <strong>return</strong> c<sub>3</sub></td>
      <td>10. salt<sub>4e3m</sub> &larr; RO<sub>P</sub>(PRK<sub>3e2m</sub>, 5, TH<sub>3</sub>, l<sub>hash</sub>)<br>11. PRK<sub>4e3m</sub> &larr; RO<sub>T</sub>(salt<sub>4e3m</sub>, X<sub>s</sub><sup>y<sub>e</sub></sup>)<br>12. status &larr; <strong>accepted</strong><br>13. CTX<sub>3</sub> &larr; (ID<sub>I</sub>||TH<sub>3</sub>||X<sub>s</sub>||EAD<sub>3</sub>)<br>14. t'<sub>3</sub> &larr; RO<sub>P</sub>(PRK<sub>4e3m</sub>, 6, CTX<sub>3</sub>, l<sub>MAC</sub>)<br>15. <strong>if</strong> t'<sub>3</sub> &ne; t<sub>3</sub>:<br>16. status &larr; <strong>rejected</strong><br>17. <strong>return</strong> &perp;<br>TH<sub>4</sub> &larr; H(TH<sub>3</sub>, m<sub>3</sub>)<br>19. PRK<sub>out</sub> &larr; RO<sub>P</sub>(PRK<sub>4e3m</sub>, 7, TH<sub>4</sub>, l<sub>hash</sub>)<br>20. status &larr; <strong>terminated</strong><br>21. SK &larr; PRK<sub>out</sub><br>22. <strong>return</strong> &perp;</td>
    </tr>
  </tbody>
</table>
**Game** $G_1$. In this game, we simulate the random oracles by lists that are empty at the beginning of the game. As $RO_T$ and $\mathcal{H}$ always return a digest of size $\ell_{hash}$, we simply use the simulation oracle $SO_T$ and $SO_{\mathcal{H}}$ respectively. However, $RO_P$ may return values of several lengths: $\ell_{ plaintext }$ for the one-time key encrypting the responder first message, $\ell_{hash}$ for the salt values and the session key, $\ell_{key}$ and $\ell_{IV}$ for the AEAD key length and Initialisation Vector respectively, and $\ell_{MAC}$ for the tags. We thus define a simulation oracle by digest size: $SO_P^{size}$, for size in $\{\ell_{plaintext}, \ell_{hash}, \ell_{key}, \ell_{IV}, \ell_{MAC}\}$

The simulation oracles $SO_P$ and $SO_{\mathcal{H}}$ work as the usual way of simulating the answer with a new random answer for any new query, and the same answer if the same query is asked again. For the simulation oracles $SO_T$, the oracle consists in a list that contains elements of the form $(\text{str}, Z, (X, Y); \lambda)$, where when first set, either $Z$ or $(X, Y)$ is non-empty. Indeed, when making a call to a random oracle, the official query is of the form $(\text{str}, Z)$, where $\text{str}$ is any bit string, that can be empty or a pseudo-random key, and $Z$ is a Diffie-Hellman value. Then, the simulator checks in the list for an entry matching with $(\text{str}, Z, *; \lambda)$. If such an element is found, one outputs $\lambda$, otherwise one randomly set $\lambda \leftarrow \{0, 1\}^{\kappa}$ and append $(\text{str}, Z, \perp; \lambda)$ to the list. But later, the simulator will also ask queries of the form $(\text{str}, (X, Y))$, where $(X, Y)$ is a pair of group elements. Then one checks in the list for an entry matching with either $(\text{str}, *, (X, Y); \lambda)$ or $(\text{str}, Z, *; \lambda)$ such that $\text{DDH}(g, X, Y, Z) = 1$. If such an element is found, one outputs $\lambda$, otherwise one randomly set $\lambda \leftarrow \{0, 1\}^{\kappa}$ and append $(\text{str}, \perp, (X, Y); \lambda)$ to the list. When such new kinds of elements exist in the list, for the first kind of queries $(\text{str}, Z)$, one checks in the list for an entry matching with either $(\text{str}, Z, *; \lambda)$ as before, or $(\text{str}, *, (X, Y); \lambda)$ such that $\text{DDH}(g, X, Y, Z) = 1$. We detail in Figure 5.6 the functioning of those oracles, and the modifications made to the simulation.

Thanks to the DDH oracle, this simulation is perfect, and is thus indistinguishable to the adversary:

$$ \Pr[\text{Succ}_1] = \Pr[\text{Succ}_0] $$

**Game** $G_2$. In order to prevent collisions in the future PRK generation, we modify the simulation oracles $SO_T$, $SO_P^{\ell_{hash}}$ and $SO_{\mathcal{H}}$, such that if a collision occurs, the simulator stops. We therefore need to determine the probability of a collision, to bound the probability for an adversary to distinguish this game from the previous one. To do so, we rely on the birthday paradox. By denoting $q_{SO_T}$, $q_{SO_P^{\ell_{hash}}}$, $q_{SO_{\mathcal{H}}}$ the amount of queries made to oracles $SO_T$, $SO_P^{\ell_{hash}}$, $SO_{\mathcal{H}}$ respectively, the birthday paradox bound gives:

$$ \Pr[\text{Succ}_2] - \Pr[\text{Succ}_1] \le \frac{q_{SO_T}^2 + q_{SO_P^{\ell_{hash}}}^2 + q_{SO_{\mathcal{H}}}^2}{2^{\ell_{hash}+1}} $$

**Game** $G_3$. One can note that thanks to the above simulation of the random oracles, the simulator does not need anymore to compute Diffie-Hellman values. Then, for every simulated player, the simulator generates $X_e$ or $Y_e$ at random in the group, and the simulation is still performed as in the previous game. As corruption queries only reveal long-term secret, still known to the simulator, the view of the adversary is perfectly indistinguishable of the previous game and we have:

$$ \Pr[\text{Succ}_3] = \Pr[\text{Succ}_2] $$

**Game** $G_4$. In this game, when simulating any **initiator** receiving a forged tuple $(Y_e, c_2, C_R)$ from the adversary in the name of a **non-corrupted user**, one simulates $PRK_{3e2m}$ thanks to a private oracle $SO_{PRK_{3e2m}}$, which makes it perfectly unpredictable to the adversary. If the pair $(Y_e, C_R)$ is forged, $TH_2$ and salt$_{3e2m}$ are different from the values obtained by a possibly simulated responder, thanks to the absence of collisions as they are respectively computed using $SO_{\mathcal{H}}$ and $SO_P^{\ell_{hash}}$. Otherwise, $sk_2$ is not modified. So if the ciphertext $c_2$ is forged,
<figure><img src="image_43.png" /><figcaption>Figure 5.6: Description of SO<sub>T</sub> list queries and modifications to the simulation</figcaption></figure>
thanks to the injective property of the encryption scheme $(\mathcal{E}, \mathcal{D})$ when the key is fixed, $m_2$, and by consequent $\text{TH}_3$ and $\text{salt}_{4e3m}$ are different from the values obtained by a possibly simulated responder. In order to detect the inconsistency of $\text{PRK}_{3e2m}$ with respect to the public oracle answer, the adversary must have asked $\text{SO}_T$ on the correct Diffie-Hellman value $X_e^{Y_s}$. We denote the event $F_1$, that query $X_e^{Y_s}$ is asked whereas $Y_s$ is the long-term secret key of a non-corrupted user and $X_e$ has been generated by the simulator. If this event happens (which can easily be checked as the simulator knows $Y_s$), one stops the simulation:

$$|\text{Pr}[\text{Succ}_4] - \text{Pr}[\text{Succ}_3]| \le \text{Pr}[F_1].$$

**Game $G_{4'}$.** We now provide an upper-bound on $\text{Pr}[F_1]$ : given a GDH challenge $(X = g^x, Y = g^y)$, one simulates all the $X_e$ as $X_e = X \cdot g^r$, for random $r \leftarrow \mathbb{Z}_p$, but chooses one user to set $Y_s = Y$. Even if $Y_s$ is therefore not known, simulation is still feasible as the simulator can make query to the $\text{SO}_T$ oracle with input $(X_e, Y_s)$. Then, one can still answer all the corruption queries, excepted for that user. But anyway, if $F_1$ happens on that user, this user must be non-corrupted at that time: one has solved the GDH problem, and one can stop the simulation. If the guess on the user is incorrect, one can also stop the simulation: $\text{Pr}[F_1] \le N \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(t, q_{\text{RO}})$, where $N$ is the number of users in the system.

**Game $G_5$.** In this game, when simulating any **responder** receiving a forged message $m_1$ from the adversary in the name of a **non-corrupted user**, still non-corrupted when sending $c_3$ to $\text{RespRun2}$, one simulates $\text{PRK}_{4e3m}$ thanks to a private oracle $\text{SO}_{\text{PRK}_{4e3m}}$, which makes it perfectly unpredictable to the adversary. Since $m_1$ is forged, thanks to the absence of collisions, $\text{TH}_2, \text{TH}_3$, and $\text{salt}_{4e3m}$ are different from the values obtained by a possibly simulated responder. In order to detect the inconsistency of $\text{PRK}_{4e3m}$ with respect to the public oracle answer, the adversary must have asked $\text{SO}_T$ on the correct Diffie-Hellman value $Y_e^{X_s}$. We denote the event $F_2$, that query $Y_e^{X_s}$ is asked whereas $X_s$ is the long-term secret key of a non-corrupted user and $Y_e$ has been generated by the simulator. If this event happens (which can easily be checked as the simulator knows $X_s$), one stops the simulation:

$$|\text{Pr}[\text{Succ}_5] - \text{Pr}[\text{Succ}_4]| \le \text{Pr}[F_2].$$

**Game $G_{5'}$.** We now provide an upper-bound on $\text{Pr}[F_2]$ : given a GDH challenge $(X = g^x, Y = g^y)$, one simulates all the $Y_e$ as $Y_e = Y \cdot g^{r'}$, for random $r' \leftarrow \mathbb{Z}_p$, but chooses one user to set $X_s = X$. Then, one can still answer all the corruption queries, excepted for that user. But anyway, if $F_2$ happens on that user, this user must be non-corrupted at that time: one has solved the GDH problem, and one can stop the simulation. If the guess on the user is incorrect, one can also stop the simulation: $\text{Pr}[F_2] \le N \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(t, q_{\text{RO}})$.

**Game $G_6$.** In this game, we simulate the key generation of $\text{PRK}_{2e}$, for all the passive sessions ($m_1$ received by a simulated responder comes from a simulated initiator, or $(Y_e, c_2, C_R)$ received by a simulated initiator comes from a simulated responder, and both used the same $m_1$ as first message), thanks to a private oracle $\text{SO}_{\text{PRK}_{2e}}$, acting in the same vein as $\text{SO}_T$, but not available to the adversary. This makes a difference with the previous game if the key $\text{PRK}_{2e}$ has also been generated by asking $\text{SO}_T$ on the correct Diffie-Hellman value $Z = g^{x_e y_e}$. We denote by $F_3$ the latter event, and stop the simulation in such a case:

$$|\text{Pr}[\text{Succ}_6] - \text{Pr}[\text{Succ}_5]| \le \text{Pr}[F_3]$$

**Game $G_{6'}$.** We now provide an upper-bound on $\text{Pr}[F_3]$. Given a GDH challenge $(X = g^x, Y = g^y)$, one simulates all the $X_e$ as $X_e = X \cdot g^r$, for random $r \leftarrow \mathbb{Z}_p$, and all the $Y_e$ as $Y_e = Y \cdot g^{r'}$, for random $r' \leftarrow \mathbb{Z}_p$. As the key $\text{PRK}_{2e}$ does not depend on the session
context, any query Z to the SO<sub>T</sub> oracle can make F<sub>3</sub> occurs on any of the passive session pairs (X<sub>e</sub> = X · g<sup>r</sup>, Y<sub>e</sub> = Y · g<sup>r'</sup>), we upper-bound the number by n<sub>σ</sub>. Hence, q<sub>RO</sub> DDH-oracle queries might be useful to detect F<sub>3</sub> on an input Z = CDH(X<sub>e</sub>, Y<sub>e</sub>) = g<sup>XY</sup> · X<sup>r'</sup> · Y<sup>r</sup> · g<sup>rr'</sup>, solving the GDH challenge (X, Y):

$$ \Pr[F_3] \leq \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(t, n_{\sigma} \cdot q_{\mathrm{RO}}). $$

**Game G<sub>7</sub>.** In this game, when simulating any **initiator** receiving the second message (Y<sub>e</sub>, c<sub>2</sub>, C<sub>R</sub>), from the adversary in the name of a **non-corrupted user**, one simulates PRK<sub>3e2m</sub> thanks to a private oracle SO<sub>PRK<sub>3e2m</sub></sub>. This makes a difference with the previous game only if this is a passive session, in which case PRK<sub>2e</sub> is unpredictable, and thus different from the public one excepted with probability 2<sup>-l<sub>hash</sub></sup>. As there are no collision, salt<sub>3e2m</sub> is different from the value obtained by a possibly simulated responder. In order to detect the inconsistency of PRK<sub>3e2m</sub> with respect to the public oracle answer, the adversary must have asked SO<sub>T</sub> on the correct Diffie-Hellman value X<sub>e</sub><sup>Y<sub>e</sub></sup>, which is not possible as event F<sub>1</sub> stops the simulation:

$$ |\Pr[\mathrm{Succ}_7] - \Pr[\mathrm{Succ}_6]| \leq \frac{1}{2^{l_{\mathrm{hash}}}}. $$

**Game G<sub>8</sub>.** In this game, when simulating any **initiator** receiving the second message (Y<sub>e</sub>, c<sub>2</sub>, C<sub>R</sub>), from the adversary in the name of a **non-corrupted user**, one simulates PRK<sub>4e3m</sub> thanks to a private oracle SO<sub>PRK<sub>4e3m</sub></sub>. In this case, PRK<sub>3e2m</sub> is unpredictable, as well as salt<sub>4e3m</sub> and PRK<sub>4e3m</sub>:

$$ \Pr[\mathrm{Succ}_8] = \Pr[\mathrm{Succ}_7]. $$

**Game G<sub>9</sub>.** In this game, when simulating any **responder** receiving c<sub>3</sub>, from the adversary in the name of a **non-corrupted user**, one simulates PRK<sub>4e3m</sub> thanks to the private oracle SO<sub>PRK<sub>4e3m</sub></sub>. This makes a difference with the previous game only if this is not a passive session, in which case PRK<sub>2e</sub> is unpredictable, and thus different from the public one excepted with probability 2<sup>-l<sub>hash</sub></sup>. As there are no collision, salt<sub>3e2m</sub>, PRK<sub>3e2m</sub>, and salt<sub>4e3m</sub> are different from the values obtained by a possibly simulated responder. In order to detect the inconsistency of PRK<sub>4e3m</sub> with respect to the public oracle answer, the adversary must have asked SO<sub>T</sub> on the correct Diffie-Hellman value Y<sub>e</sub><sup>X<sub>e</sub></sup>, which is not possible as event F<sub>2</sub> stops the simulation:

$$ |\Pr[\mathrm{Succ}_9] - \Pr[\mathrm{Succ}_8]| \leq \frac{1}{2^{l_{\mathrm{hash}}}}. $$

**Game G<sub>10</sub>.** In this game, for any fresh session, one simulates PRK<sub>out</sub> thanks to the private oracle SO<sub>PRK<sub>out</sub></sub>. A session being fresh means that no corruption of the party or of the partner occurred before the time of acceptance: the initiator is not corrupted before receiving (Y<sub>e</sub>, c<sub>2</sub>, C<sub>R</sub>) and the responder is not corrupted before receiving c<sub>3</sub>. By consequent, they are not corrupted before PRK<sub>4e3m</sub> was computed. We have seen above that in those cases, the key PRK<sub>4e3m</sub> is generated using the private oracle SO<sub>PRK<sub>4e3m</sub></sub>: it is unpredictable. The use of the private oracle SO<sub>PRK<sub>out</sub></sub> can only be detected if the query PRK<sub>4e3m</sub> is asked to SO<sub>P</sub>:

$$ |\Pr[\mathrm{Succ}_{10}] - \Pr[\mathrm{Succ}_9]| \leq \frac{q_{\mathrm{SO}_P^{l_{\mathrm{hash}}}}}{2^{l_{\mathrm{hash}}}}. $$

Globally, one can note that the gap between the initial and the last games is upper-bounded by

$$ \begin{aligned} & \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(t, n_{\sigma} \cdot q_{\mathrm{RO}}) + 2N \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(t, q_{\mathrm{RO}}) \\ & + \frac{q_{\mathrm{SO}_T}^2 + q_{\mathrm{SO}_P^{l_{\mathrm{hash}}}}^2 + q_{\mathrm{SO}_H}^2}{2^{l_{\mathrm{hash}}+1}} + \frac{2 + q_{\mathrm{SO}_P^{l_{\mathrm{hash}}}}}{2^{l_{\mathrm{hash}}}} \\ & \leq \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(t, n_{\sigma} \cdot q_{\mathrm{RO}}) + 2N \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(t, q_{\mathrm{RO}}) + \frac{q_{\mathrm{RO}}^2 + 4}{2^{l_{\mathrm{hash}}+1}} \end{aligned} $$
Eventually, for all the fresh sessions, in the real case ($b = 0$), the private oracle is used, and outputs a random key, while in the random case ($b = 1$), the session key is random too:

$$ \mathrm{Pr}[\mathrm{Succ}_{10}] = \frac{1}{2}. $$

This concludes the proof.

## 5.3 Explicit authentication

Explicit authentication (or mutual authentication) aims to ensure each participant has the material to compute the final session key (accepts) when the partner terminates. In the EDHOC protocol, this means the responder (resp. the initiator) owns the private long-term key $y_s$ (resp $x_s$) associated to the long-term public key $Y_s$ (resp. $X_s$), and the private ephemeral keys, when the partner terminates.

Finalize

1. **return** :

$$ \forall \pi_u^i \text{ s.t. } \begin{cases} \pi_u^i \cdot \text{status} = \textbf{terminated} \\ \pi_u^i \cdot t_{acc} < \text{revltk}_{\pi_u^i \cdot \text{peerid}} \end{cases}, \exists \pi_v^j \text{ s.t. } \begin{cases} \pi_v^j \cdot \text{peerid} = v \\ \pi_v^j \cdot \text{peerid} = u \\ \pi_v^j \cdot \text{sid} = \pi_v^j \cdot \text{sid} \\ \pi_v^j \cdot \text{role} \neq \pi_v^j \cdot \text{role} \\ \pi_v^j \cdot \text{status} = \textbf{accepted} \end{cases} $$

<caption>Figure 5.7: Finalize Function for the Explicit Authentication Security Game</caption>

To do so, the responder uses $y_s$ in RespRun1 to compute PRK$_{3e2m}$ used for the tag $t_2$ and the key sk$_3$. In the same way, the initiator uses $x_s$ to compute PRK$_{4e3m}$, used for the tag $t_3$. Furthermore, they both have to use their ephemeral keys to compute PRK$_{2e}$, used for sk$_2$.

**Responder Authentication.** Consider a simulated initiator receiving a forged message ($Y_e, c_2, C_R$) from the adversary in the name of a **non-corrupted user**. In such a case, consider the modifications made in the key privacy proof up to the game $G_7$. Hence, we have replaced the generation of PRK$_{3e2m}$ with a private oracle. Then the advantage of the adversary in breaking the explicit authentication of the responder in this game is bounded by $\frac{1}{2^{\ell_{MAC}}}$, added to the gap induced by the modifications made up to the game $G_7$. This leads to the following theorem:

**Theorem 5.2**

The above EDHOC protocol satisfies the responder authentication under the Gap Diffie-Hellman problem in the Random Oracle model, and the injectivity of $(\mathcal{E}, \mathcal{D})$. More precisely, with $q_{RO}$ representing the global number of queries to the random oracles, $n_\sigma$ the number of running sessions, $N$ the number of users, and $\ell_{hash}$ the hash digest length, we have $\mathrm{Adv}_{\mathrm{EDHOC}}^{\mathrm{auth-resp}}(t; q_{RO}, n_\sigma, N)$ upper-bounded by

$$ \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(t, n_{\sigma} \cdot q_{\mathrm{RO}}) + 2N \cdot \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(t, q_{\mathrm{RO}}) + \frac{q_{\mathrm{RO}}^2 + 2}{2^{\ell_{\mathrm{hash}}+1}} + \frac{1}{2^{\ell_{\mathrm{MAC}}} $$

**Optimal Reduction.** One cannot expect more after these three flows, as the adversary can play the role of the responder with known $y_e$. Without knowing $y_s$, it just gets stuck to compute PRK$_{3e2m}$ and thus $t_2$. But it can guess it (with probability $2^{-\ell_{MAC}}$), breaking authentication. But it will not know SK.
**Initiator Authentication.** We now consider any **responder** receiving a forged message $c_3$ from the adversary in the name of a **non-corrupted user**. As above, considering the modifications made in the key privacy proof up to the game $G_8$, we have replaced the generation of PRK$_{4e3m}$ with a private oracle. Then the advantage of the adversary in breaking the explicit authentication of the initiator in this game is bounded by $\frac{1}{2^{\ell_{MAC}}}$, added to the gap induced by the modifications made up to the game $G_7$. This leads to the following theorem:

**Theorem 5.3**

The above EDHOC protocol satisfies the initiator authentication under the Gap Diffie-Hellman problem in the Random Oracle model, and the injectivity of $(\mathcal{E}, \mathcal{D})$. More precisely, with $q_{RO}$ representing the global number of queries to the random oracles, $n_\sigma$ the number of running sessions, $N$ the number of users, and $\ell_{hash}$ the hash digest length, we have $\text{Adv}_{\text{EDHOC}}^{\text{auth-init}}(t; q_{RO}, n_\sigma, N)$ upper-bounded by

$$ \text{Adv}_{\text{EDHOC}}^{\text{GDH}}(t, n_{\sigma} \cdot q_{\text{RO}}) + 2N \cdot \text{Adv}_{\text{EDHOC}}^{\text{GDH}}(t, q_{\text{RO}}) + \frac{q_{\text{RO}}^2 + 4}{2^{\ell_{\text{hash}}+1}} + \frac{1}{2^{\ell_{\text{MAC}}}+1} $$

**Optimal Reduction.** One cannot expect more after these three flows, as the adversary can play the role of the initiator with known $x_e$. Without knowing $x_s$, it just gets stuck to compute PRK$_{4e3m}$ and thus $t_3$. But it can guess it (with probability $2^{-\ell_{MAC}}$) and encrypt it, as it knows $sk_3$, breaking authentication. But it will not know SK.

## 5.4 Identity protection

Let us now consider anonymity, with identity protection. More precisely, we want to show that the initiator's identity ($ID_I$) is protected against active adversaries, while responder's identity ($ID_R$) is protected only against passive adversaries.

The values $ID_I$ and $ID_R$ are the authentication credentials containing the public authentication keys of I and R, respectively.

**Responder's Identity Protection.** The value $ID_R$ is used in the computation of $CTX_2$ itself used to compute $t_2$, which together with $ID_R$ constitute the first part of $m_2 = (ID_R \| t_2 \| EAD_2)$ whose encryption is $c_2$ under $sk_2$. For the sake of clarity, we set $EAD_2 = \text{''}$ as $EAD_2$ is independent from the identity of the responder and has no cryptographic purpose. As a responder, the passive adversary can only learn information about $ID_R$ using the ciphertext $c_2$. We thus define the responder identity protection experiment as follows:

$$ \text{Exp}_{\text{EDHOC}}^{\text{ID-resp}-b}(\mathcal{A}) $$

1. $ID_{R_0}, ID_{R_1} \leftarrow \mathcal{A}(\text{peerid})$

2. $m_1 \leftarrow \mathcal{A}(\text{InitRun1}(\cdot))$

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

4. $ID_R \leftarrow ID_{R_0}$

5. $y_s \leftarrow sk_{ID_R}$

6. $(Y_e, c_2, C_R) \leftarrow \text{RespRun1}(ID_R, y_s, m_1)$

7. $b' \leftarrow \mathcal{A}(c_2)$

8. **return** $b = b'$

We define the advantage $\text{Adv}_{\text{EDHOC}}^{\text{ID-resp}-b}$ of the adversary in breaking the responder mutual authentication of EDHOC by:

$$ \text{Adv}_{\text{EDHOC}}^{\text{ID-resp}-b}(t) = \max_{\mathcal{A}} \left( | \Pr[\text{Exp}_{\text{EDHOC}}^{\text{ID-resp}-0}(\mathcal{A}) = 1] - \Pr[\text{Exp}_{\text{EDHOC}}^{\text{ID-resp}-1}(\mathcal{A}) = 1] | \right) $$
## Theorem 5.4

The above EDHOC protocol protects Responder's Identity under the Gap Diffie-Hellman problem in the Random Oracle model, the injectivity and the semantic security of $\Pi = (\mathcal{E}, \mathcal{D})$. More precisely, with $q_{RO}$ representing the global number of queries to the random oracles, $n_{\sigma}$ the number of running sessions, $N$ the number of users, and $\ell_{hash}$ the hash digest length, we have $\text{Adv}_{\text{EDHOC}}^{\text{ID-resp-b}}(t; q_{RO}, n_{\sigma}, N)$ upper-bounded by

$$ \text{Adv}_{\mathbb{G}}^{\text{GDH}}(t, n_{\sigma} \cdot q_{\text{RO}}) + 2N \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(t, q_{\text{RO}}) + \text{Adv}_{\Pi}^{\text{IND}}(t) + \frac{q_{\text{RO}}^2 + 2}{2\ell_{\text{hash}}+1} $$

**Game** $G_0$. This game is $\text{Exp}_{\text{EDHOC}}^{\text{ID-resp-0}}$. The simulated initiator follows the protocol, computes $c_2 = \mathcal{E}(\text{sk}_2, (\text{ID}_R \| t_2))$ and sends $Y_e, c_2, C_R$ to the adversary:

$$ \Pr[\text{Succ}_0] = \Pr[\text{Exp}_{\text{EDHOC}}^{\text{ID-resp-0}} = 1] $$

**Game** $G_1$. In this game, we applied the modification made from $G_0$ up to $G_6$ in the key privacy proof.

$$ |\Pr[\text{Succ}_1] - \Pr[\text{Succ}_0]| \le \text{Adv}_{\mathbb{G}}^{\text{GDH}}(t, n_{\sigma} \cdot q_{\text{RO}}) + 2N \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(t, q_{\text{RO}}) + \frac{q_{\text{RO}}^2}{2\ell_{\text{hash}}+1} $$

**Game** $G_2$. In this game, one simulates $\text{sk}_2$ thanks to a private oracle, which makes a difference only if the random $\text{PRK}_{2e}$ is asked to the public oracle:

$$ |\Pr[\text{Succ}_2] - \Pr[\text{Succ}_1]| \le \frac{1}{2\ell_{\text{hash}}} $$

**Game** $G_3$. In this game, we replace the line 4 of the experiment by $\text{ID}_R \leftarrow \text{ID}_{R_{1-b}}$, leading to the instanciation of $\text{Exp}_{\text{EDHOC}}^{\text{ID-resp-1}}$. As $\text{sk}_2$ is chosen at random, using the semantic security of the encryption scheme $(\mathcal{E}, \mathcal{D})$, we thus have

$$ |\Pr[\text{Succ}_3] - \Pr[\text{Succ}_2]| \le \text{Adv}_{\Pi}^{\text{IND}}(t) $$

**Initiator's Identity Protection.** In this case, we expect an active security: we consider the simulation of an initiator interacting with an adversary playing in the name of a non-corrupted user with public long-term key $Y_s$. We have simulated $\text{PRK}_{3e2m}$ with a private oracle, which leads to a private random key $\text{sk}_3$, unless the query has been asked, with the same argument as above.

The value $\text{ID}_I$ is used in the computation of $\text{CTX}_3$ itself used to compute $t_3$, which together with $\text{ID}_I$ constitute the first part of the message $m_3 = (\text{ID}_R \| t_2 \| \text{EAD}_2)$ whose encryption is $c_3$ under $\text{sk}_3$. As above, for the sake of generality, we set $\text{EAD}_3 = $"". One can note that the first message $m_1$ sent by the initiator is independent of $\text{ID}_R$. We therefore start the experiment after the adversary sent his first message $(Y_e, c_2, C_R)$:

$$ \text{Exp}_{\text{EDHOC}}^{\text{ID-init-b}}(\mathcal{A}) $$

1. $\text{ID}_{l_0}, \text{ID}_{l_1} \leftarrow \mathcal{A}(\text{peerid})$

2. $(Y_e, c_2, C_R) \leftarrow \mathcal{A}(\text{RespRun1}(\cdot))$

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

4. $\text{ID}_I \leftarrow \text{ID}_{I_b}$

5. $x_s \leftarrow \text{sk}_{\text{ID}_I}$

6. $Y_s \leftarrow \text{peerpk}[\text{ID}_I]$

7. $c_3 \leftarrow \text{InitRun2}(\text{ID}_I, x_s, Y_s, (Y_e, c_2, C_R))$

8. $b' \leftarrow \text{Adv}(c_3)$

9. **return** $b = b'$
We define the advantage $Adv_{EDHOC}^{ID-init-b}$ of the adversary in breaking the responder mutual authentication of EDHOC by:

$$Adv_{EDHOC}^{ID-init-b}(t) = \max_{\mathcal{A}} \left( |\Pr[\mathbf{Exp}_{EDHOC}^{ID-init-0}(\mathcal{A}) = 1] - \Pr[\mathbf{Exp}_{EDHOC}^{ID-init-1}(\mathcal{A}) = 1]| \right)$$

### Theorem 5.5

The above EDHOC protocol protects Initiator's Identity under the Gap Diffie-Hellman problem in the Random Oracle model, the injectivity of $(\mathcal{E}, \mathcal{D})$ and the semantic security of $\Pi' = (\mathcal{E}', \mathcal{D}')$. More precisely, with $q_{RO}$ representing the global number of queries to the random oracles, $n_{\sigma}$ the number of running sessions, $N$ the number of users, and $\ell_{hash}$ the hash digest length, we have $Adv_{EDHOC}^{ID-init-b}(t; q_{RO}, n_{\sigma}, N)$ upper-bounded by

$$Adv_{\mathcal{G}}^{GDH}(t, n_{\sigma} \cdot q_{RO}) + 2N \cdot Adv_{\mathcal{G}}^{GDH}(t, q_{RO}) + Adv_{\Pi'}^{IND}(t) + \frac{q_{RO}^2 + 2}{2\ell_{hash} + 1}$$

## 5.5 Improvements

In this section, we present improvements to increase both key privacy and mutual authentication. First, we explain how one can improve mutual authentication with just a few more flows, but without modifying the protocol. Then, we propose a modification of the key schedule that improves both the key privacy security and the mutual authentication security.

### 5.5.1 Improved mutual authentication with more flows

As seen in Section 5.3, EDHOC protocol offers an explicit authentication security of $\ell_{MAC}$ bits. The lower setting for $\ell_{MAC}$ is 64 bits, giving a 64-bit security only. We describe in this section that by considering the fourth optional message sent from the responder to the initiator and a fifth message sent from the initiator to the responder, we can reach a 128-bit security.

With this updated protocol EDHOC, we first reconsider the responder authentication.

**Updated Authentication.** Consider a simulated initiator (resp. responder) receiving a forged message $c_4$ (resp. $c_5$) from the adversary in the name of a non-corrupted user. In such a case, we consider the modifications made in the key privacy proof up to the game $G_9$. Hence, in both cases, we have replaced the generation of PRK$_{4e3m}$ with a private oracle. We can additionally replace the generation of $sk_4$ (resp. $sk_5$) by a private oracle, which makes a difference with probability bounded by $\frac{1}{2^{\ell_{hash}}}$. Then the advantage of the adversary in passing the new verification step is bounded by $Adv_{\Pi'}^{uf-cma}(\mathcal{A})$, in conjunction with the previous probability $\frac{1}{2^{\ell_{MAC}}}$ for the tag:

### Theorem 5.6

The above EDHOC protocol satisfies the responder/initiator authentication under the Gap Diffie-Hellman problem in the Random Oracle model, the injective property of $(\mathcal{E}, \mathcal{D})$, and the un- forgeability of $\Pi' = (\mathcal{E}', \mathcal{D}')$. More precisely, with $q_{RO}$ representing the global number of queries to the random oracles, $n_{\sigma}$ the number of running sessions, $N$ the number of users, and $\ell_{hash}$ the hash digest length, we have both $Adv_{EDHOC}^{auth-init}(t; q_{RO}, n_{\sigma}, N)$ and $Adv_{EDHOC}^{auth-resp}(t; q_{RO}, n_{\sigma}, N)$ upper-bounded by

$$Adv_{\mathcal{G}}^{GDH}(t, n_{\sigma} \cdot q_{RO}) + 2N \cdot Adv_{\mathcal{G}}^{GDH}(t, q_{RO}) + \frac{1}{2^{\ell_{MAC}}} \cdot Adv_{\Pi'}^{uf-cma}(t) + \frac{q_{RO}^2 + 6}{2^{\ell_{hash} + 1}}$$

Note that one can expect a 128-bit security with $\frac{1}{2^{\ell_{MAC}}} \cdot Adv_{\Pi'}^{uf-cma}$.
### 5.5.2 Improved EDHOC protocol

We present two modifications, and their motivations.

**Non-Empty Nonce for PRK$_{2e}$**. Looking at the games $G_6$ and $G_6'$ of the key-privacy proof, in which we simulate the generation of the key PRK$_{2e}$, we have the following advantage for the adversary to distinguish between the games $G_5$ and $G_6$:

$$| \Pr[\text{Succ}_6] - \Pr[\text{Succ}_5] | \le \text{Adv}_{\mathbb{G}}^{\text{GDH}}(t, n_{\sigma} \cdot q_{\text{RO}}).$$

One can note that this advantage depends on the number of sessions $n_{\sigma}$. This is induced by the fact that, as the key PRK$_{2e}$ does not depend on the session context, any query Z to the SO$_T$ oracle can solve any of the $n_{\sigma}$ GDH instances. Therefore, a first modification we suggest in the key schedule in Figure 5.8 would be to compute the key PRK$_{2e}$ according to TH$_2$ (or any value depending on the actual session). This implies for the adversary to make a query to the SO$_T$ oracle with a specific TH$_2$ linked to a single session, leading to the following advantage for the adversary A:

$$| \Pr[\text{Succ}_6] - \Pr[\text{Succ}_5] | \le \text{Adv}_{\mathbb{G}}^{\text{GDH}}(t, q_{\text{RO}}).$$

and the updated Theorem 5.1:

**Theorem 5.1**

he above EDHOC protocol satisfies the key privacy property under the Gap Diffie-Hellman problem in the Random Oracle model, and the injective property of $(\mathcal{E}, \mathcal{D})$. More precisely, with $q_{\text{RO}}$ representing the global number of queries to the random oracles, N the number of users, and $\ell_{\text{hash}}$ the hash digest length, we have $\text{Adv}_{\text{EDHOC}}^{\text{kp-ake}}(t; q_{\text{RO}}, n_{\sigma}, N)$ upper-bounded by

$$(2N + 1) \cdot \text{Adv}_{\mathbb{G}}^{\text{GDH}}(t, q_{\text{RO}}) + \frac{q_{\text{RO}}^2 + 4}{2\ell_{\text{hash}} + 1}$$

Therefore, this also impacts Theorems 5.2 and 5.3 (Explicit Authentication) and Theorems 5.4 and 5.5 (Identity Protection) as the game $G_6$ of the key privacy is used in those proofs.

**Second message from the Initiator.** The encryption key $sk_3$, used by the initiator to encrypt its second message $m_3$, is computed by calling HKDF -Expand on PRK$_{3e2m}$. However, even an adversary that plays in the name of a non-corrupted user, is able to compute PRK$_{3e2m}$, when knowing the Initiator ephemeral key $x_e$, as PRK$_{3e2m}$ does not depend on $x_s$, the long term secret key of the Initiator. In order to break the Initiator authentication, with respect to a Responder, an adversary can play on behalf of any user as an Initiator. It will be able to compute $sk_3$, but not $t_3$, for which value it will need some luck, but this is only 64-bit long! Which is not enough for a 128-bit security.

To get around this issue, we suggest modifying the construction of Initiator's second message as follows: Initial message $m_3 = (\text{ID}_1||t_3||\text{EAD}_3)$ is split as $m_3 \leftarrow (\text{ID}_1)$ and $m'_3 \leftarrow (t_3||\text{EAD}_3)$. Thus, $m_3$ is encrypted using $sk_3$ (with a one-time pad encryption scheme $\Pi = (\mathcal{E}, \mathcal{D})$, under $sk_3$ still depending on PRK$_{3e2m}$) into $c_3$. Then $m'_3$ does not need to be encrypted. We introduce the value $\ell_{\text{sec}}$, always set as the expected bit-security parameter, independently of the $\ell_{\text{MAC}}$ value. Then, we set the length of $t_3$ to be $\ell_{\text{sec}}$, as it already authenticates CTX$_3 = (\text{ID}_1||\text{TH}_3||X_s||\text{EAD}_3)$. Concretely, the second message sent by the initiator to the responder is: $c_3||m'_3$, where $c_3 = \mathcal{E}(sk_3, m_3)$, $m'_3 = t_3||\text{EAD}_3$. Once the Responder receives $(c_3, m'_3)$, he first decrypts $c_3$, retrieves $X_s$ using $m_3$, computes PRK$_{4e3m}$ and is then able to verify the tag $t_3$, allowing to check the authenticity of $\text{ID}_1$, as well as all the other values is CTX$_3 = \text{ID}_1||\text{TH}_3||X_s||\text{EAD}_3$. The extra required length for the tag $t_3$ is perfectly compensated by the absence of the tag jointly sent when
using Authenticated Encryption, and the plaintext length of $m_3$ is the same as the encryption of $m_3$. Therefore, this does not impact the communication cost of the protocol, until $l_{sec} \le 2 \times l_{MAC}$, but improves to $l_{sec}$-bit security for Initiator-Authentication.

About the Responder-Authentication, $t_2$ also provides a 64-bit security level only: by guessing it, any active adversary can make the initiator terminate, and thus breaking the responder-authentication, if one does not wait for the fourth flow $c_4$, $m'_4$. However, with this fourth flow, we can show the $2 \times l_{MAC}$-bit security level is achieved.

In Figure 5.8, we show the updated Key Schedule, while in Figure 5.9, we describe the differences between the previous and the new version.

<figure><img src="image_44.png" /><figcaption>Figure 5.8: Updated Key Derivation after our improvements.</figcaption></figure>
<table><caption>Figure 5.9: Optimized EDHOC with four messages in the STAT/STAT Authentication Method. Our modifications compared to [SMP21] (draft-ietf-lake-edhoc-15) are represented by previous | new and additions by gray highlights</caption><thead><tr><th>Initiator</th><th>Responder</th></tr></thead><tbody><tr><td>x<sub>s</sub>, x<sub>s</sub> = g<sup>x<sub>s</sub></sup></td><td>y<sub>s</sub>, y<sub>s</sub> = g<sup>y<sub>s</sub></sup></td></tr></tbody></table><p>InitRun1(ID<sub>1</sub>)</p><p>x<sub>e</sub> &larr; $\mathbb{Z}_p$, X<sub>e</sub> &larr; g<sup>x<sub>e</sub></sup>; C<sub>1</sub> &larr; $\{0, 1\}^{nl}$</p><p>m<sub>1</sub> &larr; (X<sub>e</sub>||C<sub>1</sub>||EAD<sub>1</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;m<sub>1</sub> &rarr; RespRun1(ID<sub>R</sub>, y<sub>s</sub>, m<sub>1</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;Parse m<sub>1</sub> as (X<sub>e</sub>||c||EAD<sub>1</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;y<sub>e</sub> &larr; $\mathbb{Z}_p$, Y<sub>e</sub> &larr; g<sup>y<sub>e</sub></sup>; C<sub>R</sub> &larr; $\{0, 1\}^{nl}$</p><p>&nbsp;&nbsp;&nbsp;&nbsp;sid &larr; (C<sub>1</sub>, C<sub>R</sub>, X<sub>e</sub>, Y<sub>e</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;PRK<sub>2e</sub> &larr; HKDF-Extract("" | TH<sub>2</sub>, X<sub>e</sub><sup>y<sub>e</sub></sup>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;TH<sub>2</sub> &larr; H(Y<sub>e</sub>, C<sub>R</sub>, H(m<sub>1</sub>))</p><p>&nbsp;&nbsp;&nbsp;&nbsp;sk<sub>2</sub> &larr; HKDF-Expand(PRK<sub>2e</sub>, 0, TH<sub>2</sub>, l<sub>plaintext</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;salt<sub>3e2m</sub> &larr; HKDF-Expand(PRK<sub>2e</sub>, 1, TH<sub>2</sub>, l<sub>hash</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;PRK<sub>3e2m</sub> &larr; HKDF-Extract(salt<sub>3e2m</sub>, Y<sub>s</sub><sup>x<sub>e</sub></sup>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;t'<sub>2</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 2, CTX<sub>2</sub>, l<sub>MAC</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;if t'<sub>2</sub> &ne; t<sub>2</sub> : return &perp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;TH<sub>3</sub> &larr; H(TH<sub>2</sub>, m &asymp; 2)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;sk<sub>3</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 3, TH<sub>3</sub>, l<sub>key</sub> | l<sub>id</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;IV<sub>3</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 4, TH<sub>3</sub>, l<sub>IV</sub>) | &empty;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;salt<sub>4e3m</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 5, TH<sub>3</sub>, l<sub>hash</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;PRK<sub>4e3m</sub> &larr; HKDF-Extract(salt<sub>4e3m</sub>, Y<sub>e</sub><sup>x<sub>s</sub></sup>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;accepted &larr; 1</p><p>&nbsp;&nbsp;&nbsp;&nbsp;CTX<sub>3</sub> &larr; (ID<sub>1</sub>||TH<sub>3</sub>||X<sub>s</sub>||EAD<sub>3</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;t<sub>3</sub> &larr; HKDF-Expand(PRK<sub>4e3m</sub>, 6, CTX<sub>3</sub>, l<sub>MAC</sub> | l<sub>sec</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;m<sub>3</sub> &larr; (ID<sub>1</sub>||t<sub>3</sub>||EAD<sub>3</sub> | ID<sub>1</sub>, m'<sub>3</sub> &larr; (t<sub>3</sub>||EAD<sub>3</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;c<sub>3</sub> &larr; E'(sk<sub>3</sub>, IV<sub>3</sub>; m'<sub>3</sub>; "") | E(sk<sub>3</sub>, m<sub>3</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c<sub>3</sub>, m'<sub>3</sub> &rarr; RespRun2(ID, st, peerpk, c<sub>3</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;TH<sub>3</sub> &larr; H(TH<sub>2</sub>, m<sub>2</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sk<sub>3</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 3, TH<sub>3</sub>, l<sub>key</sub> | l<sub>id</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;IV<sub>3</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 4, TH<sub>3</sub>, l<sub>IV</sub>) | &empty;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m<sub>3</sub> &larr; D'(sk<sub>3</sub>, IV<sub>3</sub>; c<sub>3</sub>; "") | D(sk<sub>3</sub>, c<sub>3</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;parse m<sub>3</sub> as (ID<sub>1</sub>||t<sub>3</sub>||EAD<sub>3</sub>) | ID<sub>1</sub> and m'<sub>3</sub> as (t<sub>3</sub>||EAD<sub>3</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;X<sub>s</sub> &larr; peerpk(ID<sub>1</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;salt<sub>4e3m</sub> &larr; HKDF-Expand(PRK<sub>3e2m</sub>, 5, TH<sub>3</sub>, l<sub>hash</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;PRK<sub>4e3m</sub> &larr; HKDF-Extract(salt<sub>4e3m</sub>, X<sub>s</sub><sup>y<sub>e</sub></sup>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;accepted &larr; 1</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CTX<sub>3</sub> &larr; (ID<sub>1</sub>||TH<sub>3</sub>||X<sub>s</sub>||EAD<sub>3</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t'<sub>3</sub> &larr; HKDF-Expand(PRK<sub>4e3m</sub>, 6, CTX<sub>3</sub>, l<sub>MAC</sub> | l<sub>sec</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if t'<sub>3</sub> &ne; t<sub>3</sub> : return &perp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;TH<sub>4</sub> &larr; H(TH<sub>3</sub>, m<sub>3</sub>, m'<sub>3</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sk<sub>4</sub> &larr; HKDF-Expand(PRK<sub>4e3m</sub>, 8, TH<sub>4</sub>, l<sub>key</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;IV<sub>4</sub> &larr; HKDF-Expand(PRK<sub>4e3m</sub>, 9, TH<sub>4</sub>, l<sub>IV</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m<sub>4</sub> &larr; "", m'<sub>4</sub> &larr; EAD<sub>4</sub></p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c<sub>4</sub> &larr; E'(sk<sub>4</sub>, IV<sub>4</sub>; m<sub>4</sub>; m'<sub>4</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c<sub>4</sub>, m'<sub>4</sub> &larr; TH<sub>4</sub> &larr; H(TH<sub>3</sub>, m<sub>3</sub>, m'<sub>3</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sk<sub>4</sub> &larr; HKDF-Expand(PRK<sub>4e3m</sub>, 8, TH<sub>4</sub>, l<sub>key</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;IV<sub>4</sub> &larr; HKDF-Expand(PRK<sub>4e3m</sub>, 9, TH<sub>4</sub>, l<sub>IV</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m<sub>4</sub> &larr; "", m'<sub>4</sub> &larr; EAD<sub>4</sub></p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c<sub>4</sub> &larr; E'(sk<sub>4</sub>, IV<sub>4</sub>; m<sub>4</sub>; m'<sub>4</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;PRK<sub>out</sub> &larr; HKDF-Expand(PRK<sub>4e3m</sub>, 7, TH<sub>4</sub>, l<sub>hash</sub>)</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;terminated &larr; 1</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SK &larr; PRK<sub>out</sub></p></table>
# Chapter 6

## Conclusion

While initially explicitly used to secure human-to-human communications, cryptography is now implicitly used for device-to-device communications. With the growing concern about privacy jointly to the increasing amount of exchanged messages in our digital life, the spectrum of cryptography get wider. In this thesis, we have provided several contributions through various fields.

First, in chapter 3, we used cryptography as a tool at the service of Machine Learning, a field in continuous expansion. Indeed, whereas previous work consider evaluation on the server side, we showed that one can also securely evaluate a Decision Tree on the client device, opening the doors to use cases such as Continuous Authentication. Our protocol proven to be secure against Honest-but-Curious client only need a single flow to be completed. However, our protocol secure against malicious client requires Garbled Circuits, which use Oblivious Transfers and therefore increases communication cost, both in terms of bandwidth and flows. Even if secure evaluation of Machine Learning models is widely studied, a big remaining challenge is to find solutions to securely train on datasets and securely update encoded models.

Then, in chapter 4, we have explored the field of secure multiparty computation and post-quantum cryptography. We introduced Smooth Projective Hash Function with Gray Zone that are a relaxation of Smooth Projective Hash Functions to cases where correctness nor smoothness can not be claimed for every word. This relaxation is made by considering a new property, named Decomposition Intractability. We showed that if the Decomposition Intractability property was provided, it was enough to build an Oblivious Transfer proven to be secure in the Universal Composability Framework and instantiated such Oblivious Transfer with post-quantum cryptography using the LWE Encryption Scheme.

We may wonder if an instantiation can be done based on other post-quantum family, in particular error correcting codes. More generally, one may wonder if other properties on Smooth Projective Hash Functions with Gray Zone leading could lead to other constructions.

Finally, in chapter 5 we analyzed an authenticated key exchange protocol, EDHOC, specifically developed for lightweight cryptography. This led to improvements in order to reach sufficient security even in aggressive settings. Such protocols will take up more and more space as the Internet of Things grows considerably.
Bibliography

[AAB<sup>+22</sup>] Carlos Aguilar Melchor, Nicolas Aragon, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Edoardo Persichetti, Gilles Zémor, Jurjen Bos, Arnaud Dion, Jerome Lacan, Jean-Marc Robert, and Pascal Veron. HQC. Technical report, National Institute of Standards and Technology, 2022. available at https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions. [Cited on page 38]

[ABB<sup>+22</sup>] Nicolas Aragon, Paulo Barreto, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Phillipe Gaborit, Shay Gueron, Tim Guneysu, Carlos Aguilar Melchor, Rafael Misoczki, Edoardo Persichetti, Nicolas Sendrier, Jean-Pierre Tillich, Gilles Zémor, Valentin Vasseur, Santosh Ghosh, and Jan Richter-Brokmann. BIKE. Technical report, National Institute of Standards and Technology, 2022. available at https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions. [Cited on page 38]

[ABC<sup>+22</sup>] Martin R. Albrecht, Daniel J. Bernstein, Tung Chou, Carlos Cid, Jan Gilcher, Tanja Lange, Varun Maram, Ingo von Maurich, Rafael Misoczki, Ruben Niederhagen, Kenneth G. Paterson, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, Cen Jung Tjhai, Martin Tomlinson, and Wen Wang. Classic McEliece. Technical report, National Institute of Standards and Technology, 2022. available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions. [Cited on page 38]

[ACP09] Michel Abdalla, Céline Chevalier, and David Pointcheval. Smooth projective hashing for conditionally extractable commitments. In Shai Halevi, editor, *CRYPTO 2009*, volume 5677 of LNCS, pages 671–689. Springer, Heidelberg, August 2009. [Cited on page 78]

[AGH10] Carlos Aguilar Melchor, Philippe Gaborit, and Javier Herranz. Additively homomorphic encryption with d-operand multiplications. In Tal Rabin, editor, *CRYPTO 2010*, volume 6223 of LNCS, pages 138–154. Springer, Heidelberg, August 2010. [Cited on page 38]

[AL07] Yonatan Aumann and Yehuda Lindell. Security against covert adversaries: Efficient protocols for realistic adversaries. In Salil P. Vadhan, editor, *TCC 2007*, volume 4392 of LNCS, pages 137–156. Springer, Heidelberg, February 2007. [Cited on page 42]

[AMPR14] Arash Afshar, Payman Mohassel, Benny Pinkas, and Ben Riva. Non-interactive secure computation based on cut-and-choose. In Phong Q. Nguyen and Elisabeth Oswald, editors, *EUROCRYPT 2014*, volume 8441 of LNCS, pages 387–404. Springer, Heidelberg, May 2014. [Cited on pages 5 and 22]

[BBB<sup>+21a</sup>] Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Yann Connan, and Philippe Gaborit. A gapless code-based hash proof system based on RQC and its applications. Cryptology ePrint Archive, Report 2021/026, 2021. https://eprint.iacr.org/2021/026. [Cited on pages 78 and 80]

[BBB<sup>+21b</sup>] Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Baptiste Cottier, and David Pointcheval. Secure decision forest evaluation. In *The 16th International Conference on Availability, Reliability and Security*, pages 1–12, 2021. [Not cited.]

[BBB<sup>+22a</sup>] Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Yann Connan, and Philippe Gaborit. A gapless code-based hash proof system based on rqc and its applications. *Designs, Codes and Cryptography*, pages 1–34, 2022. [Cited on pages 4, 5, and 21]
[BBB<sup>+</sup>22b] Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Baptiste Cottier, and David Pointcheval. Post-Quantum Oblivious Transfer from Smooth Projective Hash Functions with grey<sup>1</sup> Zone. hal-03772089, 2022. https://hal.archives-ouvertes.fr/hal-03772089. [Not cited.]

[BBB<sup>+</sup>22c] Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Baptiste Cottier, and David Pointcheval. Secure Decision Forest Evaluation. hal-03321368, 2022. https://hal.archives-ouvertes.fr/hal-03321368. [Not cited.]

[BBB<sup>+</sup>22d] Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Baptiste Cottier, and David Pointcheval. Post-Quantum and UC-secure Oblivious Transfer from SPHF with Grey Zone. In *The 15th International Symposium on Foundations & Practice of Security*, pages 1–16, 2022. [Not cited.]

[BBC<sup>+</sup>13a] Fabrice Ben Hamouda, Olivier Blazy, Céline Chevalier, David Pointcheval, and Damien Vergnaud. Efficient UC-secure authenticated key-exchange for algebraic languages. In Kaoru Kurosawa and Goichiro Hanaoka, editors, *PKC 2013*, volume 7778 of LNCS, pages 272–291. Springer, Heidelberg, February / March 2013. [Cited on page 78]

[BBC<sup>+</sup>13b] Fabrice Benhamouda, Olivier Blazy, Céline Chevalier, David Pointcheval, and Damien Vergnaud. New techniques for SPHFs and efficient one-round PAKE protocols. In Ran Canetti and Juan A. Garay, editors, *CRYPTO 2013, Part I*, volume 8042 of LNCS, pages 449–475. Springer, Heidelberg, August 2013. [Cited on page 78]

[BBDQ18] Fabrice Benhamouda, Olivier Blazy, Léo Ducas, and Willy Quach. Hash proof systems over lattices revisited. In Michel Abdalla and Ricardo Dahab, editors, *PKC 2018, Part II*, volume 10770 of LNCS, pages 644–674. Springer, Heidelberg, March 2018. [Cited on pages 80 and 87]

[Ben16] Fabrice Benhamouda. *Diverse modules and zero-knowledge*. PhD thesis, Paris Sciences et Lettres (ComUE), 2016. [Cited on page 41]

[BFK<sup>+</sup>09] Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Ahmad-Reza Sadeghi, and Thomas Schneider. Secure evaluation of private linear branching programs with medical applications. In Michael Backes and Peng Ning, editors, *ESORICS 2009*, volume 5789 of LNCS, pages 424–439. Springer, Heidelberg, September 2009. [Cited on page 74]

[BGN05] Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. Evaluating 2-DNF formulas on ciphertexts. In Joe Kilian, editor, *TCC 2005*, volume 3378 of LNCS, pages 325–341. Springer, Heidelberg, February 2005. [Cited on page 38]

[BHR12] Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of garbled circuits. In Ting Yu, George Danezis, and Virgil D. Gligor, editors, *ACM CCS 2012*, pages 784–796. ACM Press, October 2012. [Cited on page 45]

[BM90] Mihir Bellare and Silvio Micali. Non-interactive oblivious transfer and applications. In Gilles Brassard, editor, *CRYPTO'89*, volume 435 of LNCS, pages 547–557. Springer, Heidelberg, August 1990. [Cited on page 43]

[BMR90] Donald Beaver, Silvio Micali, and Phillip Rogaway. The round complexity of secure protocols (extended abstract). In *22nd ACM STOC*, pages 503–513. ACM Press, May 1990. [Cited on pages 45 and 47]

[BPSW07] Justin Brickell, Donald E. Porter, Vitaly Shmatikov, and Emmett Witchel. Privacy-preserving remote diagnostics. In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson, editors, *ACM CCS 2007*, pages 498–507. ACM Press, October 2007. [Cited on page 74]

[BPTG15] Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser. Machine learning classification over encrypted data. In *NDSS 2015. The Internet Society, February 2015*. [Cited on page 74]
[BR93] Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Dorothy E. Denning, Raymond Pyle, Ravi Ganesan, Ravi S. Sandhu, and Victoria Ashby, editors, *ACM CCS 93*, pages 62–73. ACM Press, November 1993. [Cited on page 31]

[BR06] Mihir Bellare and Phillip Rogaway. The security of triple encryption and a framework for code-based game-playing proofs. In Serge Vaudenay, editor, *EUROCRYPT 2006*, volume 4004 of LNCS, pages 409–426. Springer, Heidelberg, May / June 2006. [Cited on page 96]

[Can01] Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In *42nd FOCS*, pages 136–145. IEEE Computer Society Press, October 2001. [Cited on page 78]

[CD22] Wouter Castryck and Thomas Decru. An efficient key recovery attack on SIDH (preliminary version). Cryptology ePrint Archive, Report 2022/975, 2022. https://eprint.iacr.org/2022/975. [Cited on page 38]

[CP22a] Baptiste Cottier and David Pointcheval. Security Analysis of Improved EDHOC Protocol. In *The 15th International Symposium on Foundations & Practice of Security*, pages 1–16, 2022. [Not cited.]

[CP22b] Baptiste Cottier and David Pointcheval. Security analysis of the EDHOC protocol. hal-03772082v2, 2022. https://hal.archives-ouvertes.fr/hal-03772082. [Not cited.]

[CS98] Ronald Cramer and Victor Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In Hugo Krawczyk, editor, *CRYPTO'98*, volume 1462 of LNCS, pages 13–25. Springer, Heidelberg, August 1998. [Cited on page 85]

[CS02] Ronald Cramer and Victor Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In Lars R. Knudsen, editor, *EUROCRYPT 2002*, volume 2332 of LNCS, pages 45–64. Springer, Heidelberg, April / May 2002. [Cited on pages 40, 41, and 78]

[DDH$^{+16}$] Martine De Cock, Rafael Dowsley, Caleb Horst, Raj Katti, Anderson C. A. Nascimento, Stacey C. Newman, and Wing-Sea Poon. Efficient and private scoring of decision trees, support vector machines and logistic regression models based on pre-computation. Cryptology ePrint Archive, Report 2016/736, 2016. https://eprint.iacr.org/2016/736. [Cited on page 74]

[DG20] Hannah Davis and Felix Günther. Tighter proofs for the SIGMA and TLS 1.3 key exchange protocols. Cryptology ePrint Archive, Report 2020/1029, 2020. https://eprint.iacr.org/2020/1029. [Cited on page 96]

[DH76] Whitfield Diffie and Martin E. Hellman. New directions in cryptography. *IEEE Transactions on Information Theory*, 22(6):644–654, 1976. [Cited on page 32]

[DPB18] Aurélien Dupin, David Pointcheval, and Christophe Bidan. On the leakage of corrupted garbled circuits. In Joonsang Baek, Willy Susilo, and Jongkil Kim, editors, *ProvSec 2018*, volume 11192 of LNCS, pages 3–21. Springer, Heidelberg, October 2018. [Cited on pages 5 and 22]

[DS15] David Derler and Daniel Slamanig. Practical witness encryption for algebraic languages and how to reply an unknown whistleblower. Cryptology ePrint Archive, Report 2015/1073, 2015. https://eprint.iacr.org/2015/1073. [Cited on page 78]

[EGL82] Shimon Even, Oded Goldreich, and Abraham Lempel. A randomized protocol for signing contracts. In David Chaum, Ronald L. Rivest, and Alan T. Sherman, editors, *CRYPTO'82*, pages 205–210. Plenum Press, New York, USA, 1982. [Cited on page 42]

[EIG85] Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. *IEEE Transactions on Information Theory*, 31:469–472, 1985. [Cited on page 38]
[Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, *41st ACM STOC*, pages 169–178. ACM Press, May / June 2009. [Cited on pages 37 and 38]

[GL03] Rosario Gennaro and Yehuda Lindell. A framework for password-based authenticated key exchange. In Eli Biham, editor, *EUROCRYPT 2003*, volume 2656 of LNCS, pages 524–543. Springer, Heidelberg, May 2003. https://eprint.iacr.org/2003/032.ps.gz. [Cited on pages 41 and 78]

[GM82] Shafi Goldwasser and Silvio Micali. Probabilistic encryption and how to play mental poker keeping secret all partial information. In *14th ACM STOC*, pages 365–377. ACM Press, May 1982. [Cited on page 38]

[GMP+08] Sebastian Gajek, Mark Manulis, Olivier Pereira, Ahmad-Reza Sadeghi, and Jörg Schwenk. Universally composable security analysis of TLS—Secure sessions with handshake and record layer protocols. Cryptology ePrint Archive, Report 2008/251, 2008. https://eprint.iacr.org/2008/251. [Cited on page 52]

[GMW87] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, *19th ACM STOC*, pages 218–229. ACM Press, May 1987. [Cited on pages 42 and 45]

[HBD+20] Andreas Hulsing, Daniel J. Bernstein, Christoph Dobraunig, Maria Eichlseder, Scott Fluhrer, Stefan-Lukas Gazdag, Panos Kampanakis, Stefan Kolbl, Tanja Lange, Martin M Lauridsen, Florian Mendel, Ruben Niederhagen, Christian Rechberger, Joost Rijneveld, Peter Schwabe, Jean-Philippe Aumasson, Bas Westerbaan, and Ward Beullens. SPHINCS+. Technical report, National Institute of Standards and Technology, 2020. available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. [Cited on page 38]

[Hoe63] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. *Journal of the American Statistical Association*, 58(301):13–30, 1963. [Cited on page 88]

[HRFS99] Mark Hopkins, Erik Reeber, George Forman, and Jaap Suermondt. *Spambase Data Set*, 1999. http://archive.ics.uci.edu/ml/datasets/Spambase/. [Cited on pages 72 and 75]

[IKNP03] Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending oblivious transfers efficiently. In Dan Boneh, editor, *CRYPTO 2003*, volume 2729 of LNCS, pages 145–161. Springer, Heidelberg, August 2003. [Cited on page 44]

[JAC+22] David Jao, Reza Azarderakhsh, Matthew Campagna, Craig Costello, Luca De Feo, Basil Hess, Amir Jalali, Brian Koziel, Brian LaMacchia, Patrick Longa, Michael Naehrig, Joost Renes, Vladimir Soukharev, David Urbanik, Geovandro Pereira, Koray Karabina, and Aaron Hutchinson. SIKE. Technical report, National Institute of Standards and Technology, 2022. available at https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions. [Cited on page 38]

[JR12] Charanjit S. Jutla and Arnab Roy. Relatively-sound NIZKs and password-based key-exchange. In Marc Fischlin, Johannes Buchmann, and Mark Manulis, editors, *PKC 2012*, volume 7293 of LNCS, pages 485–503. Springer, Heidelberg, May 2012. [Cited on page 78]

[Kra03] Hugo Krawczyk. SIGMA: The "SIGn-and-MAc" approach to authenticated Diffie-Hellman and its use in the IKE protocols. In Dan Boneh, editor, *CRYPTO 2003*, volume 2729 of LNCS, pages 400–425. Springer, Heidelberg, August 2003. [Cited on page 90]

[KS08] Vladimir Kolesnikov and Thomas Schneider. Improved garbled circuit: Free XOR gates and applications. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, *ICALP 2008, Part II*, volume 5126 of LNCS, pages 486–498. Springer, Heidelberg, July 2008. [Cited on page 47]
[KV09] Jonathan Katz and Vinod Vaikuntanathan. Smooth projective hashing and password-based authenticated key exchange from lattices. In Mitsuru Matsui, editor, *ASIACRYPT 2009*, volume 5912 of LNCS, pages 636–652. Springer, Heidelberg, December 2009. [Cited on pages 41, 78, and 80]

[KV11] Jonathan Katz and Vinod Vaikuntanathan. Round-optimal password-based authenticated key exchange. In Yuval Ishai, editor, *TCC 2011*, volume 6597 of LNCS, pages 293–310. Springer, Heidelberg, March 2011. [Cited on page 78]

[KW16] Hugo Krawczyk and Hoeteck Wee. The optls protocol and tls 1.3. In *2016 IEEE European Symposium on Security and Privacy (EuroS&P '16)*, pages 81–96. IEEE Computer Society, 2016. https://eprint.iacr.org/2015/978. [Cited on page 90]

[LDK+20] Vadim Lyubashevsky, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Peter Schwabe, Gregor Seiler, Damien Stehlé, and Shi Bai. CRYSTALS-DILITHIUM. Technical report, National Institute of Standards and Technology, 2020. available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. [Cited on page 38]

[Lin13] Yehuda Lindell. Fast cut-and-choose based protocols for malicious and covert adversaries. In Ran Canetti and Juan A. Garay, editors, *CRYPTO 2013, Part II*, volume 8043 of LNCS, pages 1–17. Springer, Heidelberg, August 2013. [Cited on pages 5 and 22]

[LP07] Yehuda Lindell and Benny Pinkas. An efficient protocol for secure two-party computation in the presence of malicious adversaries. In Moni Naor, editor, *EUROCRYPT 2007*, volume 4515 of LNCS, pages 52–78. Springer, Heidelberg, May 2007. [Cited on pages 5, 22, and 51]

[LR14] Yehuda Lindell and Ben Riva. Cut-and-choose Yao-based secure computation in the online/offline and batch settings. In Juan A. Garay and Rosario Gennaro, editors, *CRYPTO 2014, Part II*, volume 8617 of LNCS, pages 476–494. Springer, Heidelberg, August 2014. [Cited on pages 5 and 22]

[MF06] Payman Mohassel and Matthew Franklin. Efficiency tradeoffs for malicious two-party computation. In Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin, editors, *PKC 2006*, volume 3958 of LNCS, pages 458–473. Springer, Heidelberg, April 2006. [Cited on pages 5 and 22]

[MP12] Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In David Pointcheval and Thomas Johansson, editors, *EUROCRYPT 2012*, volume 7237 of LNCS, pages 700–718. Springer, Heidelberg, April 2012. [Cited on page 86]

[MZ93] S.G. Mallat and Zhifeng Zhang. Matching pursuits with time-frequency dictionaries. *IEEE Transactions on Signal Processing*, 41(12):3397–3415, 1993. [Cited on page 75]

[NP01] Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In *Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms*, pages 448–457, 2001. [Cited on page 43]

[NPS99] Moni Naor, Benny Pinkas, and Reuban Sumner. Privacy preserving auctions and mechanism design. In *Proceedings of the 1st ACM Conference on Electronic Commerce*, pages 129–139, 1999. [Cited on page 48]

[NSB21] Karl Norrman, Vaishnavi Sundararajan, and Alessandro Bruni. Formal analysis of edhoc key establishment for constrained iot devices. In *Proceedings of the 18th International Conference on Security and Cryptography (SECRYPT '21)*, pages 210–221. INSTICC, SciTePress, 2021. https://arxiv.org/abs/2007.11427. [Cited on pages 90 and 93]

[Pai99] Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Jacques Stern, editor, *EUROCRYPT'99*, volume 1592 of LNCS, pages 223–238. Springer, Heidelberg, May 1999. [Cited on page 38]
[Per13] Edoardo Persichetti. Secure and anonymous hybrid encryption from coding theory. In Philippe Gaborit, editor, *Post-Quantum Cryptography - 5th International Workshop, PQCrypto 2013*, pages 174–187. Springer, Heidelberg, June 2013. [Cited on page 80]

[PFH+20] Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. FALCON. Technical report, National Institute of Standards and Technology, 2020. available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. [Cited on page 38]

[PSSW09] Benny Pinkas, Thomas Schneider, Nigel P. Smart, and Stephen C. Williams. Secure two-party computation is practical. In Mitsuru Matsui, editor, *ASIACRYPT 2009*, volume 5912 of LNCS, pages 250–267. Springer, Heidelberg, December 2009. [Cited on page 48]

[PVG+11] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. *Journal of machine learning research*, 12(Oct):2825–2830, 2011. [Cited on page 75]

[PVW08] Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. A framework for efficient and composable oblivious transfer. In David Wagner, editor, *CRYPTO 2008*, volume 5157 of LNCS, pages 554–571. Springer, Heidelberg, August 2008. [Cited on page 82]

[Reg05] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, *37th ACM STOC*, pages 84–93. ACM Press, May 2005. [Cited on pages 39 and 86]

[RSA78] Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. *Communications of the Association for Computing Machinery*, 21(2):120–126, 1978. [Cited on pages 32 and 38]

[SA21] Masoumeh Koochak Shooshtari and Mohammad Reza Aref. Smooth projective hash function from codes and its applications. *IEEE Transactions on Services Computing*, pages 1–1, 2021. [Cited on page 80]

[SAB+20] Peter Schwabe, Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, and Damien Stehlé. CRYSTALS-KYBER. Technical report, National Institute of Standards and Technology, 2020. available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. [Cited on page 38]

[Sch16] Jim Schaad. Cbor object signing and encryption (cose), 2016. [Cited on page 92]

[Sho94] Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In *35th FOCS*, pages 124–134. IEEE Computer Society Press, November 1994. [Cited on page 38]

[SMP21] Göran Selander, John Preuß Mattsson, and Francesca Palombini. Ephemeral Diffie-Hellman Over COSE (EDHOC). Internet-Draft draft-ietf-lake-edhoc-15, Internet Engineering Task Force, October 2021. Work in Progress. [Cited on pages 90, 92, 94, and 109]

[SRA81] Adi Shamir, Ronald L Rivest, and Leonard M Adleman. Mental poker. In *The mathematical gardner*, pages 37–43. Springer, 1981. [Cited on page 42]

[TKK19] Anselme Tueno, Florian Kerschbaum, and Stefan Katzenbeisser. Private evaluation of decision trees using sublinear cost. *PoPETs*, 2019(1):266–286, January 2019. [Cited on page 74]

[TMZC17] Raymond K. H. Tai, Jack P. K. Ma, Yongjun Zhao, and Sherman S. M. Chow. Privacy-preserving decision trees evaluation via linear functions. In Simon N. Foley, Dieter Gollmann, and Einar Snekkenes, editors, *ESORICS 2017, Part II*, volume 10493 of LNCS, pages 494–512. Springer, Heidelberg, September 2017. [Cited on pages 74 and 75]
[WFNL16] David J. Wu, Tony Feng, Michael Naehrig, and Kristin E. Lauter. Privately evaluating decision trees and random forests. PoPETs, 2016(4):335-355, October 2016. [Cited on pages 74 and 75]

[WMK17] Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. Faster secure two-party computation in the single-execution setting. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part III, volume 10212 of LNCS, pages 399-424. Springer, Heidelberg, April / May 2017. [Cited on pages 5 and 22]

[Yao86] Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In 27th FOCS, pages 162-167. IEEE Computer Society Press, October 1986. [Cited on pages 42 and 45]

[ZRE15] Samee Zahur, Mike Rosulek, and David Evans. Two halves make a whole - reducing data transfer in garbled circuits using half gates. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part II, volume 9057 of LNCS, pages 220-250. Springer, Heidelberg, April 2015. [Cited on page 49]

[ZY17] Jiang Zhang and Yu Yu. Two-round PAKE from approximate SPH and instantiations from lattices. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part III, volume 10626 of LNCS, pages 37-67. Springer, Heidelberg, December 2017. [Cited on page 80]
<figure><img src="image_45.png" /></figure>
## RÉSUMÉ

De nos jours, la cryptographie fait partie intégrante de notre quotidien. Initialement destinée à être utilisée pour les interactions entre humains, elle est aujourd'hui employée pour les interactions avec et entre des machines. A travers cette thèse, nous présenterons nos diverses contributions couvrant une partie du spectre de la cryptographie interactive.

Dans un premier temps, nous la verrons comme un outil au service de l'apprentissage automatique. Nous montrerons qu'elle peut permettre à un client et à un serveur d'interagir afin de faire évaluer les données du client par le modèle du serveur, sans qu'aucun d'eux n'apprenne d'informartion confidentielle au sujet de l'autre.

Ensuite, nous étendrons la notion déjà existante de Smooth Projective Hash Functions pour la rendre plus compatible avec la cryptographie post-quantique, et notamment les réseaux euclidiens. Cette extension servira de base à la construction de Transferts Inconscients, largement déployés aujourd'hui dans le cadre de Calculs Multipartites Securisés.

Finalement, nous nous intéresserons à la cryptographie à bas-coût, permettant à des appareils techniquement limités d'interagir entre eux tout en jouissant d'une sécurité suffisante. Plus précisément, nous étudierons la sécurité d'un protocole authentifié d'échange de clés optimisé pour de tels appareils, permettant d'établir une communication sécurisée entre eux.

## MOTS CLÉS

Apprentissage automatique – Authentification – Calcul Multipartite Sécurisé – Cryptographie Post-quantique – Cryptographie à bas-coût

## ABSTRACT

Nowadays, cryptography is an integral part of our daily lives. Originally intended to be used for human-to-human interactions, cryptography is now also used for with and between machines. In this thesis, we will present our contributions covering part of the spectrum of interactive cryptography.

First, we will use cryptography as a tool for Machine Learning. We will show that a client and a server can securely interact such that the client gets his data evaluated by a model owned by the server, without learning any confidential information about the other party's data.

Next, we will extend the already existing primitive of Smooth Projective Hash Functions to make it more compliant with post-quantum cryptography, and in particular with lattices. This extension will be used as a basis for the construction of Oblivious Transfers, widely used in the Secure Multiparty Context.

Finally, we will focus on lightweight cryptography, allowing technically limited devices to interact with each other while enjoying sufficient security. More precisely, we will perform a security analysis of an authenticated key exchange protocol optimized for such devices, allowing them to securely interact.

## KEYWORDS

Machine Learning – Authentication – Secure Multiparty Computation – Post-Quantum Cryptography – Lightweight Cryptography