# Contribution à la cryptographie interactive

Baptiste Cottier

► To cite this version:

Baptiste Cottier. Contribution à la cryptographie interactive. Cryptographie et sécurité [cs.CR]. Ecole Normale Supérieure de Paris - ENS Paris, 2023. Français. NNT: tel-04253249

HAL Id: tel-04253249

https://hal.science/tel-04253249

Submitted on 22 Oct 2023

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

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

Public Domain
Contribution to interactive cryptography

Soutenue par

Baptiste COTTIER

Le 06 janvier 2023

École doctorale n°386

Sciences Mathématiques
de Paris Centre

Spécialité

Informatique

Composition du jury :

Cristina Onete
Université de Limoges
Rapporteur

Sébastien Canard
Orange Labs
Rapporteur

Damien Vergnaud
Sorbonne Université, CNRS, LIP6
PRÉSIDENT DU JURY
Examinateur

Maryline Laurent
Télécom SudParis
Examinateur

David Pointcheval
CNRS, Ecole Normale Supérieure
Directeur de thèse

Olivier Blazy
Ecole Polytechnique
Codirecteur de thèse

Slim Bettaieb
Worldline
Invité

Loïc Bidoux
Worldline
Technology Innovation Institute
Invité
<figure><img src="image_1.png" /></figure>
# Remerciements

Dans un premier temps, je tiens naturellement à remercier David Pointcheval, mon directeur de thèse, pour sa confiance, son soutien ainsi que sa patience, que j'ai probablement parfois dû mettre à rude épreuve. Merci également à Olivier Blazy, co-directeur de cette thèse, pour sa disponibilité et sa pédagogie.

Mes remerciements vont aussi à Slim Bettaieb et Loïc Bidoux, mes superviseurs, pour m'avoir initié à l'univers de la recherche. J'espère que votre départ à l'autre bout du monde pendant ma thèse n'est qu'une coïncidence. Merci à Jean-Claude Barbezange sans qui cette thèse n'aurait pas eu lieu. Merci à Benjamin, Céline, Olivier et de manière plus générale à mes collègues de chez Worldline de m'avoir accepté avec mes pieds nus et leurs chaussons, mon humour et mes bavardages répétitifs.

Merci aux autres doctorants du laboratoire pour nos échanges, que ce soit autour d'un café ou d'une table de ping-pong. Merci également à Lise-Marie, Linda et Tiffany pour leur bonne humeur permanente et nos longues discussions.

Finalement, de manière plus pudique, merci à ma famille et mes amis, qui me supportent (dans tous les sens du terme) depuis de nombreuses années et n'ont cessé de croire en moi. Un merci tout particulier à celle dont notre aventure a commencé en même temps que cette thèse, mais qui elle ne se terminera pas.

N'étant pas de nature à exposer mes sentiments, je sais que cette section peut paraître succinte à prime abord. Cependant, je suis conscient que sans l'entourage que j'ai pu avoir pendant cette thèse, de tout point de vue, je n'en serai pas venu à bout, et je suis reconnaissant envers chacun d'entre vous.
# Contents

<table><tr><td>Remerciements</td><td>i</td></tr><tr><td>List of Figures</td><td>iv</td></tr><tr><td>List of Tables</td><td>vi</td></tr><tr><td>Notations & Acronyms</td><td>vii</td></tr><tr><td>1a Introduction – Version française</td><td>1</td></tr><tr><td>1.1 Motivations</td><td>1</td></tr><tr><td>1.2 Objectifs</td><td>3</td></tr><tr><td>1.3 Contributions</td><td>4</td></tr><tr><td>1.4 Organisation</td><td>6</td></tr><tr><td>1.5 Résumé long</td><td>8</td></tr><tr><td>1.5.1 Préliminaires</td><td>8</td></tr><tr><td>1.5.2 Évaluation sécurisée de forêts de décision</td><td>11</td></tr><tr><td>1.5.3 Transfert Inconscient basé sur les SPHF avec zone grise</td><td>14</td></tr><tr><td>1.5.4 Analyse de sécurité du protocole EDHOC</td><td>16</td></tr><tr><td>1b Introduction – English version</td><td>19</td></tr><tr><td>2.1 Motivations</td><td>19</td></tr><tr><td>2.2 Objectives</td><td>20</td></tr><tr><td>2.3 Contributions</td><td>21</td></tr><tr><td>2.4 Organization</td><td>23</td></tr><tr><td>2 Preliminaries</td><td>25</td></tr><tr><td>2.1 Complexity definitions</td><td>26</td></tr><tr><td>2.2 Symmetric cryptography</td><td>26</td></tr><tr><td>2.2.1 Symmetric encryption</td><td>26</td></tr><tr><td>2.2.2 Message authentication code</td><td>29</td></tr><tr><td>2.2.3 Authenticated Encryption</td><td>30</td></tr><tr><td>2.2.4 Hash functions</td><td>31</td></tr><tr><td>2.2.5 Random oracle model</td><td>31</td></tr><tr><td>2.2.6 Pseudorandom functions</td><td>32</td></tr><tr><td>2.3 Asymmetric cryptography</td><td>32</td></tr><tr><td>2.3.1 Discrete Logarithm problem and Diffie-Hellman assumptions</td><td>32</td></tr><tr><td>2.3.2 Factorization problems</td><td>34</td></tr><tr><td>2.3.3 Public-key encryption</td><td>34</td></tr><tr><td>2.3.4 Digital signatures</td><td>36</td></tr><tr><td>2.4 Homomorphic encryption</td><td>37</td></tr><tr><td>2.5 Post-Quantum cryptography</td><td>38</td></tr><tr><td>2.6 Zero-knowledge proofs</td><td>39</td></tr><tr><td>2.7 Smooth Projective Hash Functions</td><td>40</td></tr><tr><td>2.8 Secure multi-party computation</td><td>41</td></tr><tr><td>2.8.1 Oblivious Transfers</td><td>42</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>2.8.2</td>
      <td>Garbled Circuits</td>
      <td>45</td>
    </tr>
    <tr>
      <td>2.9</td>
      <td>Universal Composability</td>
      <td>51</td>
    </tr>
    <tr>
      <td>2.10</td>
      <td>Decision forest</td>
      <td>52</td>
    </tr>
    <tr>
      <td><b>3</b></td>
      <td><b>Secure decision forest evaluation</b></td>
      <td><b>54</b></td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>Honest-but-curious client and server</td>
      <td>56</td>
    </tr>
    <tr>
      <td>3.1.1</td>
      <td>Model encoding</td>
      <td>56</td>
    </tr>
    <tr>
      <td>3.1.2</td>
      <td>Evaluation description</td>
      <td>57</td>
    </tr>
    <tr>
      <td>3.1.3</td>
      <td>Protocol security</td>
      <td>57</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>Malicious client and honest-but-curious server</td>
      <td>61</td>
    </tr>
    <tr>
      <td>3.2.1</td>
      <td>Model encoding</td>
      <td>62</td>
    </tr>
    <tr>
      <td>3.2.2</td>
      <td>Protocol overview</td>
      <td>63</td>
    </tr>
    <tr>
      <td>3.2.3</td>
      <td>Formal description</td>
      <td>64</td>
    </tr>
    <tr>
      <td>3.2.4</td>
      <td>Protocol security</td>
      <td>67</td>
    </tr>
    <tr>
      <td>3.3</td>
      <td>Performances and applications</td>
      <td>72</td>
    </tr>
    <tr>
      <td>3.3.1</td>
      <td>Storage and bandwidth costs</td>
      <td>72</td>
    </tr>
    <tr>
      <td>3.3.2</td>
      <td>Comparison with related works</td>
      <td>74</td>
    </tr>
    <tr>
      <td>3.4</td>
      <td>Application to continuous authentication and spam filtering</td>
      <td>75</td>
    </tr>
    <tr>
      <td><b>4</b></td>
      <td><b>Post-quantum Oblivious Transfer from SPHF with gray zone</b></td>
      <td><b>78</b></td>
    </tr>
    <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>
    <tr>
      <td><b>5</b></td>
      <td><b>Computational security analysis of the EDHOC protocol</b></td>
      <td><b>90</b></td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Protocol description</td>
      <td>92</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Key privacy</td>
      <td>94</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>Explicit authentication</td>
      <td>103</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Identity protection</td>
      <td>104</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Improvements</td>
      <td>106</td>
    </tr>
    <tr>
      <td>5.5.1</td>
      <td>Improved mutual authentication with more flows</td>
      <td>106</td>
    </tr>
    <tr>
      <td>5.5.2</td>
      <td>Improved EDHOC protocol</td>
      <td>107</td>
    </tr>
    <tr>
      <td><b>6</b></td>
      <td><b>Conclusion</b></td>
      <td><b>112</b></td>
    </tr>
    <tr>
      <td colspan="2"><b>Bibliography</b></td>
      <td><b>114</b></td>
    </tr>
  </tbody>
</table>
List of Figures

<table><tbody><tr><td>1a.1 Protocole de Transfert Inconscient</td><td>9</td></tr><tr><td>1a.2 État des boîtes pendant le protocole</td><td>10</td></tr><tr><td>1a.3 Arbre de décision pour désigner une viennoiserie contenant des barres de chocolat.</td><td>11</td></tr><tr><td>1a.4 Représentation d'un arbre de décision dans le cas honnête-mais-curieux</td><td>12</td></tr><tr><td>1a.5 Représentation d'un arbre dans le cas d'une cliente malveillante</td><td>13</td></tr><tr><td>1a.6 Correspondance entre résultat et score</td><td>13</td></tr><tr><td>1a.7 Description du protocole de Transfert Inconscient</td><td>16</td></tr><tr><td>2.1 ElGamal Encryption Scheme</td><td>38</td></tr><tr><td>2.2 Smooth Projective Hash Functions Summary</td><td>41</td></tr><tr><td>2.3 Secure two-party computation protocol</td><td>42</td></tr><tr><td>2.4 Oblivious Transfer protocol</td><td>43</td></tr><tr><td>2.5 Bellare-Micali's Oblivious Transfer</td><td>43</td></tr><tr><td>2.6 Naor-Pinkas' Oblivious Transfer construction</td><td>44</td></tr><tr><td>2.7 Initial Sender and Receiver inputs</td><td>44</td></tr><tr><td>2.8 New Sender and Receiver inputs</td><td>44</td></tr><tr><td>2.9 FreeXOR optimization</td><td>47</td></tr><tr><td>2.10 Graphical representation of GRR2</td><td>49</td></tr><tr><td>2.11 Correctness table for the HalfGates optimization</td><td>50</td></tr><tr><td>2.12 The Real/Ideal World paradigm</td><td>52</td></tr><tr><td>2.13 Decision Classification Tree Exemple</td><td>53</td></tr><tr><td>2.14 Representation of a good fitting and overfitting</td><td>53</td></tr><tr><td>2.15 Database Sampling</td><td>53</td></tr><tr><td>3.1 Decision tree representation in the Honest-but-Curious setting</td><td>56</td></tr><tr><td>3.2 Client-side evaluation phase</td><td>58</td></tr><tr><td>3.3 Secure decision forest evaluation for Honest-but-Curious Client setting</td><td>59</td></tr><tr><td>3.4 Client-Privacy Security Game in the Honest-but-Curious Setting</td><td>60</td></tr><tr><td>3.5 Server-Privacy Security Game in the Honest-but-Curious Setting</td><td>60</td></tr><tr><td>3.6 Decision tree representation in the malicious setting</td><td>62</td></tr><tr><td>3.7 Mapping of a path score</td><td>63</td></tr><tr><td>3.8 Secure Evaluation in the Malicious setting</td><td>64</td></tr><tr><td>3.9 Circuit to compute a dual equality test</td><td>65</td></tr><tr><td>3.10 Secure Decision Forest Evaluation Protocol with malicious client</td><td>67</td></tr><tr><td>3.11 Mapping Correctness</td><td>68</td></tr><tr><td>3.12 Server-Privacy Security Game in the Malicious Setting</td><td>71</td></tr><tr><td>4.1 General description of our Oblivious Transfer protocol</td><td>82</td></tr><tr><td>4.2 Functionality F<sub>OT</sub></td><td>83</td></tr><tr><td>5.1 Notations</td><td>91</td></tr><tr><td>5.2 Key Derivation (for the STAT -STAT Method).</td><td>93</td></tr><tr><td>5.3 EDHOC Protocol in the Static-Static Method</td><td>95</td></tr><tr><td>5.4 Authenticated Key Exchange Key Privacy Security Game</td><td>97</td></tr><tr><td>5.5 Formalized description of the EDHOC protocol</td><td>98</td></tr></tbody></table>
<table><tr><td>5.6</td><td>Description of SO<sub>T</sub> list queries and modifications to the simulation</td><td>100</td></tr><tr><td>5.7</td><td>Finalize Function for the Explicit Authentication Security Game</td><td>103</td></tr><tr><td>5.8</td><td>Updated Key Derivation after our improvements.</td><td>108</td></tr><tr><td>5.9</td><td>Optimized EDHOC</td><td>109</td></tr></table>
# List of Tables

<table><tr><td>1a.1 Répartition des clés entre l'Initiatrice et le Répondant</td><td>17</td></tr><tr><td>2.1 Summary of the Homomorphic Encryption families</td><td>38</td></tr><tr><td>2.2 Truth table for the AND logical gate and the XOR logical gate</td><td>45</td></tr><tr><td>2.3 Unpermuted Garbled Table for an AND gate</td><td>46</td></tr><tr><td>2.4 Unpermuted Garbled Table for an XOR gate</td><td>46</td></tr><tr><td>2.5 Garbled tables - Without optimizations</td><td>47</td></tr><tr><td>2.6 Garbled tables - With FreeXOR</td><td>48</td></tr><tr><td>2.7 Garbled tables - With Garbled Row Reduction 3</td><td>48</td></tr><tr><td>2.8 Garbled tables - With Garbled Row Reduction 2 optimization</td><td>49</td></tr><tr><td>2.9 Garbled tables - With HalfGates optimization</td><td>51</td></tr><tr><td>3.1 Communication and Storage during the Offline Phase</td><td>73</td></tr><tr><td>3.2 Communications During the Online Phase</td><td>74</td></tr><tr><td>3.3 Comparison to state-of-the-art</td><td>75</td></tr><tr><td>3.4 Accuracy on our continuous authentication Database</td><td>76</td></tr><tr><td>3.5 Accuracy on the spambase Database</td><td>76</td></tr></table>
# Notations & acronyms

We define here some global notations. A more precise list of notations is given at the beginning of each chapter.

<table><thead><tr><th colspan="2">Symbols</th></tr></thead><tbody><tr><td>a∥b</td><td>a concatenated with b</td></tr><tr><td>a ←$A$</td><td>a is uniformly sampled from A</td></tr><tr><td>[A]</td><td>[1 .. A]</td></tr></tbody></table><table><thead><tr><th colspan="2">Encryption</th></tr></thead><tbody><tr><td>sk</td><td>Secret key</td></tr><tr><td>pk</td><td>Public Key</td></tr><tr><td>M</td><td>Space of Messages</td></tr><tr><td>K</td><td>Space of Keys</td></tr><tr><td>IV</td><td>Initialization Vector</td></tr><tr><td>AHE</td><td>Additive Homomorphic Encryption</td></tr><tr><td>AEAD</td><td>Authenticated Encryption with Additional Data</td></tr><tr><td>OTP</td><td>One-Time Pad</td></tr></tbody></table><table><thead><tr><th colspan="2">Security</th></tr></thead><tbody><tr><td>1<sup>κ</sup></td><td>Security Parameter</td></tr><tr><td>A</td><td>Adversary</td></tr><tr><td>A<sup>F</sup></td><td>Adversary with access to an oracle computing F(·)</td></tr><tr><td>Q</td><td>List of queries made by A to an oracle</td></tr><tr><td>Exp</td><td>Experiment</td></tr><tr><td>Adv</td><td>Advantage of the adversary</td></tr><tr><td>F</td><td>Functionality</td></tr><tr><td>CDH</td><td>Computational Diffie-Hellman</td></tr><tr><td>DDH</td><td>Decisional Diffie-Hellman</td></tr><tr><td>GDH</td><td>Gap Diffie-Hellman</td></tr><tr><td>IND-CPA</td><td>INDistinguishability under Chosen Plaintext Attack</td></tr><tr><td>IND-CCA</td><td>INDistinguishability under Chosen Ciphertext Attack</td></tr><tr><td>EUF-CMA</td><td>Existential UnForgeability under Chosen Messages Attack</td></tr><tr><td>RO</td><td>Random Oracle</td></tr><tr><td>SO</td><td>Simulation Oracle</td></tr></tbody></table><table><thead><tr><th colspan="2">Primitives</th></tr></thead><tbody><tr><td>MPC</td><td>Multiparty Secure Computation</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>OT</td><td>Oblivious Transfer</td></tr><tr><td>NIZK</td><td>Non-Interactive Zero Knowledge Proofs</td></tr><tr><td>MAC</td><td>Message Authentication Code</td></tr></tbody></table>
# Chapter 1a

# Introduction – Version française

Dans cette section, nous présentons les motivations qui ont conduit aux divers projets de cette thèse. Dans un second temps, nous présenterons les divers objectifs, ainsi que les contributions en ayant découlées dans une dernière section.

## 1.1 Motivations

Au quotidien, nos données personnelles sont de plus en plus exploitées. Avec l'arrivée du Règlement général sur la protection des données (RGPD) en 2016, la confidentialité a gagné en intérêt auprès des utilisateurs tout autant qu'auprès des entreprises. Afin de protéger ses données, une solution consiste à faire appel à la cryptographie. Depuis les petits messages codés échangés à l'école jusqu'aux communications inter-présidentielles, la cryptographie trouve facilement sa place dans la communication entre humains. Il va de soi qu'aujourd'hui, le spectre de la cryptographie ne se limite plus aux interactions humaines, mais atteint aussi nos téléphones, nos ordinateurs et de façon générale, le moindre objet connecté qui nous entoure, entre autres les serveurs. Bien qu'au premier abord, la confidentialité semble ne présenter que des avantages, elle peut constituer un frein dans certains cas. Prenons l'exemple d'une messagerie. Il est important quand nous utilisons une messagerie que seuls les deux contacts aient accès aux messages et médias échangés. D'un autre point de vue, garantir une telle confidentialité peut attirer des utilisateurs aux intentions malhonnêtes. Il serait donc tout aussi appréciable que, si des messages à contenu illégal sont échangés, cette même messagerie puisse les détecter et agir en conséquence. Se pose alors la question suivante : Comment trouver le parfait, ou à défaut le meilleur, équilibre entre la confidentialité et l'exploitation des données ? La branche de la cryptographie qui étudie ce genre de problématiques est appelée *Calcul Multipartite Sécurisé*. Le Calcul Multipartite Sécurisé peut se définir comme une famille de protocoles permettant à plusieurs acteurs, appelés parties, de collaborer afin d'évaluer une fonction de leurs données. Ces valeurs données en entrée du protocole, et de manière générale toute valeur donnée en entrée d'un protocole, seront désignées *input*, tandis que les valeurs retournées par le protocole seront appelées *output*. À la fin de l'exécution d'un protocole, chaque partie ne doit rien connaître de plus que ce qu'elles ne peuvent déduire à partir de leurs *input* et *output* respectifs. Pour reprendre l'exemple de la messagerie, cela reviendrait à pouvoir détecter un message à contenu illégal sans pour autant connaître le contenu du message.

Il n'est pas rare que lorsque toutes ces données sont collectées, elles soient utilisées comme *input* d'un modèle d'apprentissage automatique (*Machine Learning* en anglais). L'apprentissage automatique est un outil qui permet de classer, prédire ou estimer une valeur, à partir d'échantillons préalablement utilisés afin d'établir un modèle du comportement de ces échantillons. C'est un outil massivement utilisé de nos jours, que ce soit pour la détection de pourriel, la prédiction de la météo, ou bien, et c'est ce dernier cas d'usage qui va nous intéresser, pour pouvoir authentifier de manière continue un utilisateur. Authentifier de manière continue un utilisateur consiste à
l'authentifier sans que cela n'impacte son utilisation, de manière transparente. Dans le cadre de l'authentification continue sur mobile, cela peut se faire en analysant la vitesse à laquelle il utilise son clavier, la pression et la trajectoire de son doigt quand il utilise son navigateur, etc. C'est son comportement qui va lui permettre de s'authentifier. Du fait que ces données servent à l'authentification d'un utilisateur, ce sont des données sensibles, qui demandent un minimum de confidentialité. Il en va de même pour le modèle enregistré sur un serveur, qui, s'il était dévoilé, pourrait permettre à un utilisateur de fausser ses données pour pouvoir usurper l'identité d'un autre utilisateur. C'est pourquoi il faut donc aussi que le modèle utilisé soit confidentiel. Cela nous amène à une problématique proche de celle décrite précédemment :

*Comment évaluer un modèle d'apprentissage automatique pour de l'authentification continue de manière confidentielle ?*

Nous répondons à cette question dans le troisième chapitre de ce manuscrit. Notre réponse contient deux protocoles ; l'un est prouvé sûr contre un adversaire honnête-mais-curieux et le second, contre un adversaire malveillant. L'adversaire honnête-mais-curieux représente une partie qui suit le protocole, mais qui va essayer d'extraire autant d'informations que possible sur les autres parties à partir de ce qu'elle voit. L'adversaire malveillant, lui, est libre de ne pas suivre le protocole. Il peut le modifier pour en apprendre davantage sur les autres parties, mais il peut aussi essayer d'orienter le protocole afin d'obtenir le résultat qu'il désire. Dans ce second protocole, nous faisons appel à plusieurs primitives de Calcul Multipartite Sécurisé, dont les Transferts Inconscients (*Oblivious Transfers* en anglais). Ces derniers permettent à un récepteur de récupérer un message précis parmi plusieurs, détenus par l'expéditeur, sans que ce dernier ne sache quel message a été récupéré par le récepteur et sans que celui-ci n'apprenne d'information sur les messages qu'il n'était pas censé récupérer. Il existe de nombreuses instanciations de Transferts Inconscients. Celles qui vont nous intéresser ici sont celles basées sur les *Smooth Projective Hash Functions* (SPHF). Les SPHF reposent sur un ensemble, appelé langage, et une paire de clés chacune associée à une fonction de hachage. Ces clés sont générées de telle sorte que si le mot donné en *input* dudit SPHF est un mot du langage associé à la SPHF, les deux fonctions de hachage retournent la même valeur. Cette propriété est appelée *correctness*. De plus, quand le mot donné en *input* n'est pas un mot du langage, les valeurs obtenues par les deux fonctions de hachage doivent être différentes et indiscernables. Cette propriété est appelée *smoothness*. Dans le cas où les Transferts Inconscients sont basés sur des SPHF faisant appel à de la cryptographie classique, les choses se passent bien. Cependant, quand ils sont basés sur des SPHF faisant appel à de la cryptographie post-quantique, une zone grise fait son apparition. Quand un mot est dans cette zone grise, npus ne pouvons plus prétendre à la propriété de *correctness* ni de *smoothness*. Cette incertitude laisse donc place à de potentielles attaques. Bien que des travaux aient déjà étudié la question, leur solution, faisant appel à des preuves à divulgation nulle de connaissance, alourdissent le protocole. Nous nous sommes donc posé la question suivante :

*Comment exploiter sans surcoût ces Smooth Projective Hash Functions avec une zone grise ?*

De plus, les Transferts Inconscients sont essentiellement composés avec d'autres protocoles. De ce fait, il peut être important de s'assurer que cette composition avec d'autres protocoles n'amène pas de nouvelles attaques. Un protocole qui fournit une telle sécurité est dit universellement composable. Ainsi, nous nous attendons à ce que notre futur construction soit démontrée sécurisée dans le modèle de la composabilité universelle.

Comme dit dans les premières lignes de cette section, la cryptographie n'implique plus seulement des humains, mais aussi des machines telles que des serveurs, des smartphones, etc. Nous sommes de plus en plus entourés d'objets du quotidien connectés à Internet. Caméras, ampoules, appareils électroménagers tels que frigidaires et fours, et même des capuchons de réservoir d'essence pour camion sont connectés à Internet. Les raisons d'une telle connectivité sont diverses : facilitation
de la vie, divertissement ou encore sécurité. De nombreux capteurs sont aussi reliés à Internet pour avoir accès de manière continue aux données mesurées.

Lorsque cette connectivité a lieu au sein d'un domicile nous parlons de domotique, mais nous parlerons ici plutôt de sa généralisation, dénommant l'inter-connectivité des objets reliés à Internet : l'Internet des Objets (ou Internet of Things en anglais). En 2021, alors que la population mondiale est estimée à un peu moins de 8 milliards d'habitants, le nombre d'appareils faisant partie de l'Internet des Objets est estimé à plus de 12 milliards ; chiffre n'incluant pas les appareils permettant à un utilisateur d'accéder à Internet tels que smartphones, ordinateurs, télévision. L'Internet des Objets se limite donc aux objets qui fonctionnent grâce à Internet. Ces objets sont souvent des appareils restreints, que ce soit en termes de consommation énergétique, de puissance de calcul ou encore de mémoire disponible. En effet, nous ne pouvons pas attendre d'un bouchon de réservoir d'avoir les même performances qu'un ordinateur de bureau. Ainsi, toutes ces restrictions impliquent de devoir adapter les primitives cryptographiques utilisées.

Le domaine de la cryptographie qui étudie et adapte la cryptographie aux appareils restreints est appelée Cryptographie à bas-coût (Lightweight Cryptography en anglais). Plus précisément, l'objectif de la cryptographie à bas-coût est de trouver le meilleur compromis entre faibles performances, faibles coûts et sécurité. Cela concerne aussi bien évidemment les protocoles d'échange de clés, permettant à deux appareils de partager une même clé privée. Certains de ces protocoles permettent aussi d'authentifier formellement l'appareil avec lequel ils communiquent. Parmi eux, EDHOC, pour *Ephemeral Diffie-Hellman Over COSE*, est en cours d'études et de standardisation. Le protocole EDHOC est un protocole d'échange de clés authentifié développé par le groupe de travail *Lightweight Authenticated Key Exchange* de l'Internet Engineering Task Force (IETF). Une étape cruciale avant un déploiement à grande échelle est l'analyse de sécurité d'un tel protocole. L'analyse formelle ayant déjà été réalisée, il nous a été suggéré d'en réaliser l'analyse dans le modèle calculatoire et de répondre à la question suivante :

*Le protocole d'échange de clés EDHOC fournit-il une sécurité suffisante ?*

## 1.2 Objectifs

**Apprentissage automatique préservant la confidentialité.** Avant d'aborder la question des objets, nous décrivons ici nos contraintes. La première de celles-ci est la localisation de l'évaluation du modèle sur les données. Il est assez fréquent d'envoyer ses données à un serveur pour qu'il puisse évaluer son modèle sur ces données. Cependant, dans le cas de l'authentification continue, pour des raisons de coût de communication, l'évaluation doit avoir lieu sur le mobile de l'utilisateur. Pour les mêmes raisons, il faut réduire au maximum le nombre de communications entre le serveur et le mobile. Étant donné que l'évaluation se fait sur le mobile de l'utilisateur, le serveur doit pouvoir lui envoyer le modèle qu'il stocke, en conservant un certain niveau de confidentialité. Se pose donc la question de savoir quelle technique d'apprentissage utiliser.

Il existe de multiples techniques d'apprentissage automatique. Cependant, la plupart d'entre elles utilisent des fonctions mathématiques que nous ne savons pas évaluer efficacement de manière cryptographique. La première étape est donc de déterminer à quelle technique d'apprentissage automatisé nous souhaitions ajouter une couche de cryptographie.

Ensuite, l'objectif sera de concevoir un protocole qui permet à un utilisateur d'évaluer ses données sur un modèle encodé (au sens où pas – ou peu – d'information en découle). Nous nous limiterons aux modèles à résultat binaire, c'est-à-dire ceux dont le résultat peut se résumer à accept ou reject. Dans un premier temps, nous nous concentrerons sur le modèle Honnête-mais-Curieux, puis nous essaierons d'étendre le protocole obtenu aux adversaires malveillants. Bien évidemment, les coûts, que ce soit de calcul et de communication, doivent être raisonnables et adaptés aux appareils concernés afin que l'expérience de l'utilisateur ne se retrouve pas impactée.
Après l'exécution desdits protocoles, le serveur ne doit rien avoir appris de plus sur les données de l'utilisateur que le résultat, tandis que le client ne doit rien avoir appris de confidentiel sur le modèle.

**Un protocole de Transfert Inconscient Post-Quantique Universellement Composable basé sur les SPHFs.** Comme il a été dit dans la section précédente, utiliser des SPHF basés sur la cryptographie post-quantique implique l'apparition d'une zone grise, dont nous ne pouvons pas prédire la correctness ou la smoothness. Récemment, Bettaieb et al. [BBB$^{+22a}$] ont construit une Smooth Projective Hash Function post-quantique basée sur les codes correcteurs d'erreurs, en annihilant les problématiques liées à la zone grise en utilisant des preuves à divulgation nulle de connaissance. Bien que leur travail apporte une contre-mesure à cette problématique, l'utilisation de preuves à divulgation nulle de connaissances impacte les performances des SPHF. Notre objectif était donc de résoudre cette problématique sous un autre angle, moins impactant. Être capable de contrecarrer cette zone grise éliminera les risques qu'elle soit exploitée pour de potentielles attaques. Néanmoins, cela n'engage en rien la composabilité de la SPHF qui en résulte au sein d'un protocole de Transfert Inconscient. Ainsi, il nous faudra aussi fournir une preuve de sécurité du caractère universellement composable de notre Transfert Inconscient basé sur ces SPHF.

**Analyse de Sécurité Calculatoire du protocole EDHOC.** L'objectif de cette analyse est de venir compléter les travaux déjà réalisés sur les analyses formelles du protocole EDHOC. Ce dernier est un protocole authentifié d'échange de clés dont l'authentification peut se faire par deux méthodes : en utilisant une signature ou bien en utilisant une clé Diffie-Hellman statique. C'est sur cette dernière méthode qu'il nous a été suggéré d'étudier la sécurité du protocole, notamment avec des paramètres agressifs. Pour chaque exécution du protocole, une clé de session est générée en dérivant ces clés Diffie-Hellman statiques ainsi que des clés éphémères, à usage unique. L'analyse de sécurité du protocole se divise en trois points :

* Confidentialité de la clé ou Authentification Implicite : Au plus les deux participants connaissent la clé de session finale. Cette propriété doit rester valable même si les clés statiques sont révélées (Forward Secrecy).

* Authentification Mutuelle ou Authentification Explicite : Exactement les deux participants peuvent calculer la clé de session finale

* Protection de l'Identité : Au plus les deux participants connaissent l'identité des deux parties impliquées.

## 1.3 Contributions

**Apprentissage automatique préservant la confidentialité.** Nous avons réalisé deux protocoles pour évaluer de manière sécurisée une forêt de décision avec des classes de sorties binaires. Dans notre contexte, un serveur cherche à connaître le résultat de l'évaluation d'un modèle *M* par rapport à des données *x* d'un client, puis accept ou reject ce dernier selon ce que retourne l'évaluation. Pour nos deux protocoles, nous considérons un serveur honnête-mais-curieux. Dans le premier protocole le client est, lui aussi, considéré honnête-mais-curieux puis dans le second protocole, elle est considéré malveillanre. Sachant que nous visons des applications où les interactions entre le client et le serveur doivent être minimales, nos protocoles se divisent en deux phases. Une phase préliminaire, hors-ligne, permet d'encoder le modèle du serveur, et de l'envoyer au client, indépendemment des données du client.

Dans le protocole conçu où le client est honnête-mais-curieux, l'évaluation ne nécessite qu'un flux du client vers le serveur dans la phase en-ligne pour que le protocole soit pleinement réalisé. Ce résultat surpasse les performances des autres protocoles de la littérature.
Dans le cas où le client est malveillant, notre protocole peut s'interpréter comme un compromis entre des constructions déjà existantes en ce qui concerne le nombre de flux et le coût en termes de bande passante.

Cependant, nos protocoles révèlent au serveur le nombre d'arbres (mais pas lesquels) ayant retourné accept. Cela peut se voir comme une fonctionnalité plus qu'un inconvénient sachant que nous désirons que le serveur apprenne le résultat de l'évaluation dans notre contexte. En effet, bien que la valeur retournée par les arbres soit binaire, le serveur peut adapter son comportement en fonction de la proportion d'arbres qui ont été évalués avec succès. Cela rejoint la notion d'indice de confiance que nous pouvons régulièrement retrouver dans certains cas d'usage, tel que l'authentification continue.

Dans notre contexte de sécurité malveillante, nous utilisons des Garbled Circuits qui permettent d'évaluer de manière sécurisée des circuits booléens. Bien qu'évalués dans un cadre malveillant, nous ne nécessitons aucune technique supplémentaire par rapport au cadre honnête-mais-curieux. Ainsi, nous n'avons pas besoin d'utiliser des solutions telles que Cut & Choose. Même si cette solution a été bien étudiée et optimisée [MF06, LP07, Lin13, LR14, AMPR14, WMK17], il s'agit toujours d'une solution coûteuse nécessitant $ℓ$ Garbled Circuits pour atteindre une sécurité statistique de $2^{-ℓ}$ bits. Dans une étude, Dupin et al. [DPB18] ont montré qu'un générateur malveillant peut corrompre un Garbled Circuits uniquement en ajoutant des portes logiques NOT ou en modifiant les labels utilisés de telle sorte que le circuit échoue dans certaines conditions (attaque par échec). Cependant, nous ne sommes pas sujets à ces attaques. En effet, en cas d'attaques par échec, l'adversaire sera probablement rejeté, n'apprenant aucune information sur les seuils utilisés dans les arbres. Dans le cas d'un circuit erroné (avec des portes NOT supplémentaires), nous avons introduit la notion de polarité, qui consiste en des inversions aléatoires des résultats des chemins, et donc une attaque se réduirait à deviner toutes (ou la plupart) des inversions, conduisant probablement à un rejet, sans fuite d'information.

Ces contributions ont abouti à une publication :

★ 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

Une version de travail mise à jour est disponible sur les archives HAL :

► 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

**Un protocole de Transfert Inconscient Post-Quantique Universellement Composable basé sur les SPHFs.** Plutôt qu'annihiler la zone grise propre à l'utilisation de la cryptographie post-quantique, comme l'ont fait Bettaieb et al. dans [BBB$^{+22a}$], nous avons préféré étudier les conditions requises dans l'objectif de dompter cette zone et de mieux contrôler son comportement. De cette étude a résulté la notion d'*Insolubilité de Décomposition*. Par conséquent, nous avons introduit la notion de *Smooth Projective Hash Functions with Gray Zone* (SPHFwGZ) qui est une SPHF avec la propriété supplémentaire d'Insolubilité de Décomposition. Cette propriété affirme que, étant donné une valeur témoin aléatoire, il est hautement compliqué de générer deux valeurs soit dans le langage du SPHF, soit dans la zone grise, qui soient le complémentaire l'une de l'autre, vis-à-vis de la valeur témoin.

Nous avons par la suite montré que toute *Smooth Projective Hash Functions with Gray Zone* dont le langage se base sur des chiffrés d'un schéma de chiffrement homomorphe peut servir de base à la construction d'un *Oblivious Transfer*. Cette preuve a été faite dans le modèle de Composition Universelle et repose sur la sécurité sémantique du schéma de chiffrement.
Ces contributions sont accompagnées d'instanciations de telles SPHFwGZ. La première d'entre elles s'appuie sur le Problème de Diffie-Hellman et le cryptosystème d'ElGamal. Étant donné que le déchiffrement n'échoue jamais avec le cryptosystème d'ElGamal, la zone grise est vide et l'Insolubilité de Décomposition est évidente. Nous pouvons noter qu'en réalité, une telle SPHFwGZ est de facto une SPHF. L'idée derrière cette instanciation est d'une part, de familiariser le lecteur avec notre construction, et d'une autre part, de mettre en avant le fait que cette construction fonctionne avec toute SPHF. Une seconde instanciation se base sur les réseaux euclidiens, et plus précisément sur le problème *Learning with Errors*. Cette instanciation permet de souligner la généricité de notre construction.

Ces contributions ont conduit à la publication suivante :

★ 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

Une version de travail mise à jour est disponible sur les archives HAL:

► Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Baptiste Cottier, and David Pointcheval. Post-Quantum Oblivious Transfer from Smooth Projective Hash Functions with grey¹Zone. hal-03772089, 2022. https://hal.archives-ouvertes.fr/hal-03772089

**Analyse de sécurité calculatoire du protocole EDHOC.** Nous avons réalisé la preuve de sécurité du protocole d'échange de clé authentifié EDHOC instancié avec la méthode d'authentification par clé Diffie-Hellman statique. De plus, la preuve a été réalisée avec une configuration agressive, dans le sens où la longueur de la valeur retournée par le MAC est de 64 bits.

Il s'en est conclu que la confidentialité de la clé approche les 128 bits de sécurité, ainsi que la Protection de l'Identité des deux parties. Néanmoins, l'Authentification Mutuelle atteint une sécurité de 64 bits pour l'Initiateur et le Répondant. Bien que cela soit assumé pour le Répondant – la documentation suggère un message supplémentaire si une plus forte sécurité est désirée –, dans le cas de l'Initiateur, c'est une réelle attaque que nous avons mis en exergue. Cependant, nous avons aussi prouvé qu'en apportant des modifications au protocole, sans coût calculatoire et de communication supplémentaires comparés aux performances du protocole initial, le protocole EDHOC peut atteindre une sécurité de 128 bits pour l'Authentification Mutuelle de l'Initiateur.

Ces contributions ont conduit à la publication suivante, ayant obtenu le "Best Paper Award" :

★ 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

Une version de travail mise à jour est disponible sur les archives HAL:

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

## 1.4 Organisation

Ce chapitre donne le contexte de la thèse au lecteur, et sera le seul du manuscrit rédigé en français. Cette introduction est suivie d'un résumé long de la thèse en français. Le chapitre 2 présente toutes les notions nécessaires à une compréhension complète des chapitres 3, 4 and 5. Le chapitre 3 décrit les protocoles permettant d'évaluer de manière confidentielle un modèle sur le mobile d'un client, ainsi que leurs coûts théoriques et performances pratiques sur deux cas d'usage. Dans le chapitre 4, nous détaillons la construction des Smooth Projective Hash Functions avec Zone Grise ainsi
que la construction du protocole de Transfert Inconscient qui en découle. Nous y prouvons que
ce dernier protocole est bien universellement composable, puis nous terminons ce chapitre par
deux constructions, l'une basée sur de la cryptographie classique, l'autre sur de la cryptographie
post-quantique. Le chapitre 5 décrit le protocole EDHOC tel qu'il était défini au moment de notre
analyse. Cette dernière suit immédiatement cette description, puis nous concluons en décrivant
des améliorations. Ce manuscrit se termine par une conclusion, dans laquelle nous émettons de
potentiels futurs projets de recherche ainsi que des questions ouvertes.
# 1.5 Résumé long

Le but de cette section est de présenter de manière simple et concise le contenu de cette thèse. Sa structure suivra celle de la thèse. Nous débuterons par une introduction pédagogique des diverses primitives et notions utilisées, puis développerons les contributions et résultats obtenus.

## 1.5.1 Préliminaires

Dans un premier temps, il est de coutume d'employer des prénoms pour expliquer le fonctionnement des diverses primitives, afin d'en faciliter la compréhension. L'un des acteurs est genré au féminin et le second est genré au masculin, exploitant les pronoms de ces derniers pour faciliter la compréhension. Ainsi, laissez-nous vous présenter Alice et Bob :

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

**Prénoms:** Alice, Renée, Christelle

**Rôles:** Chiffreuse, Réceptrice, Cliente

**Pronoms:** Elle, la

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

**Prénoms:** Bob, Edouard, Selim

**Rôles:** Déchiffreur, Expéditeur, Serveur

**Pronoms:** Il, lui

Leurs rôles seront nécessaires dans la suite de ce résumé.

**Chiffrement.** En cryptographie, nous distinguons deux familles de schéma de chiffrement. Dans la première famille, la clé utilisée par Alice pour chiffrer est la même que celle utilisée par Bob pour déchiffrer. Ce sont les schémas les plus simples à mettre en place, car le déchiffrement consiste essentiellement à "rembobiner" le chiffrement. Cette famille de schémas est appelée *Cryptographie Symétrique* ou *Cryptographie à clé secrète*. Dans cette section, nous serons amenés à parler d'un de ces schémas de chiffrement, le One-Time Pad.

**One-Time Pad.** Étant donné un message $m$ de longueur $k$ bits, le One-Time Pad génère une clé secrète $sk$ de longueur, elle aussi, $k$ bits. Le chiffré $c$ de $m$ avec la clé $sk$ consiste en un xor ($\oplus$) entre le message et ma clé. Formellement, nous avons $c \leftarrow \text{Enc}(sk, m) = m \oplus sk$. Pour déchiffrer, Bob calcule $c \oplus sk = m \oplus sk \oplus sk = m$.

Cependant, pour qu'un schéma de chiffrement à clé symétrique puisse être mis en place, il faut aussi transmettre de manière sécurisée ladite clé secrète à la personne avec laquelle nous souhaitons communiquer, ce qui peut parfois s'avérer compliqué. C'est pour cette raison qu'à la fin des années 70, des schémas où la notion d'une clé différente pour le chiffrement et le déchiffrement a fait son apparition. Dans ce contexte, la clé servant à chiffrer pouvait être publique, tandis que celle servant à déchiffrer devait logiquement rester secrète. Ainsi, si Alice souhaite communiquer avec Bob, elle récupère sa clé publique et lui envoie son message chiffré, que lui seul pourra déchiffrer, car il est le seul à connaître la clé de déchiffrement. De plus, étant donné que la clé de chiffrement est publique, tout le monde peut utiliser cette même clé pour communiquer avec Bob, là où dans le contexte de la cryptographie à clé secrète, une clé différente devait être associée à chaque personne voulant communiquer avec cette dernière. Cette famille de schémas, au fonctionnement asymétrique, est appelée *Cryptographie Asymétrique* ou *Cryptographie à clé publique*.

**Chiffrement homomorphe.** Parmi les schémas de chiffrement à clé publique, certains ont une propriété homomorphe. Cette propriété permet de faire des opérations sur les valeurs claires (non chiffrées), à partir de leurs valeurs chiffrées. Considérons deux valeurs $v_1$ et $v_2$ chiffrées avec un schéma de chiffrement à clé publique dont la clé publique est $pk$ (pour *public key*, en anglais).
Nous obtenons donc $c_1 = \text{Enc}(pk, v_1)$ et $c_2 = \text{Enc}(pk, v_2)$. Un schéma de chiffrement homomorphe permet de calculer un chiffré de $v_1 + v_2$ ou de $v_1 \times v_2$ sans connaître ni $v_1$, ni $v_2$. Par exemple, avec le cryptosystème de ElGamal, multiplier les chiffrés permet d'obtenir un produit des valeurs claires. Autrement dit, en multipliant $c_1$ par $c_2$, nous obtenons un chiffré de $v_1 \cdot v_2$ sans connaître ni $v_1$, ni $v_2$.

**Code d'authentification de message.** Un Code d'Authentification de Message – Message Authentication Code (MAC) en anglais – permet à Bob de s'assurer que le message reçu n'a pas été altéré. Dans ce cas, conjointement avec le message chiffré, Alice calcule un tag, une valeur calculée en fonction de la clé secrète partagée avec Bob et du message chiffré. Ensuite, Bob peut s'assurer à l'aide du tag et de la clé secrète que le message n'a pas été altéré. En effet, une propriété des Codes d'Authentification de Message est qu'ils sont difficilement falsifiables.

**Chiffrement authentifié.** Un chiffrement authentifié est un schéma de chiffrement qui inclut un Code d'Authentification de Message. Cette authentification se fait (dans ce que nous verrons dans cette thèse) en générant une valeur, appelée tag à l'aide d'une clé secrète, et du message à chiffrer. Par la suite, quand Bob déchiffre le message reçu par Alice, le processus de déchiffrement inclus une vérification du tag, et ne poursuit le déchiffrement que si la vérification réussit. De plus, similairement aux Codes d'Authentication de Message, il doit être difficile pour une adversaire de falsifier un chiffrer, lui permettant de passer la vérification du tag.

**Transfert Inconscient.** Supposons que Renée (deuxième prénom d'Alice) soit dans la plus petite banque du monde ne contenant que deux coffres-forts. L'un de ces coffres lui appartient et elle souhaite y accéder. Pour ce faire, Renée doit récupérer la clé auprès du directeur en qui elle a confiance. Malheureusement, le directeur est en congés et c'est son assistant, Edouard (deuxième prénom de Bob), en qui elle n'a pas confiance qui la reçoit. Renée ne souhaite pas lui dire quel coffre lui appartient, par soucis de confidentialité, et, logiquement, ce dernier ne veut pas lui donner les clés de chacun des coffres. La solution pour Renée est d'utiliser un Transfert Inconscient de clé, dont le processus idéal est représenté en Figure 1a.1. Renée sera la Réceptrice de la clé et Edouard sera celui qui l'enverra, donc l'Expéditeur. Nous dénotons par $C_1$ et $C_2$ les clés détenues par Edouard, et décrétons que Renée détient le coffre numéro 1.

<figure><img src="image_4.png" /><figcaption>Figure 1a.1: Protocole de Transfert Inconscient</figcaption></figure>

Le processus idéal décrit ci-dessus fait appel à un tiers de confiance qui récupère les deux clés d'Edouard et donne à Renée la clé qu'elle souhaite. Malheureusement, Renée et Edouard sont seuls et doivent recréer ce processus, à eux deux. Une façon pour Renée et Edouard de procéder afin de recréer ce processus, est de suivre les étapes suivantes.

* **Première étape** : Renée prend deux boîtes qui se ferment à l'aide d'un cadenas. Elle ouvre les deux cadenas et garde la clé de la première boîte, puis, agissant de manière honnête, jette la seconde sous les yeux d'Edouard. Ensuite, elle dispose sur chaque boîte le cadenas encore ouvert qui lui correspond, puis donne les boîtes à Edouard.

* **Deuxième étape** : Edouard met la clé du coffre numéro 1 dans la boîte numéro 1, et la clé du coffre numéro 2 dans la boîte numéro 2, ferme les deux cadenas, puis renvoie les boîtes avec les cadenas fermés à Renée.
* Troisième étape : Renée utilise la clé de cadenas qu'elle a gardé pour ouvrir la boîte numéro un, à l'abri du regard d'Edouard.

<figure><img src="image_5.png" /><figcaption>(a) Première étape</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(b) Deuxième étape</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(c) Troisième étape</figcaption></figure>

<caption>Figure 1a.2: État des boîtes pendant le protocole</caption>

De façon plus générale, un protocole de Transfert Inconscient permet à Renée de récupérer un élément auprès d'Edouard sans qu'il sache quel élément a été récupéré par Renée, et sans que Renée n'apprenne d'information sur l'élément qu'elle n'a pas reçu d'Edouard.

**Preuves à Divulgation Nulle de Connaissance.** Commençons par définir la notion de langage. Un langage $\mathcal{L}$ avec relation $\mathcal{R}$ est un ensemble d'éléments x, appelés mots, pour lesquels il existe un témoin w tels que $\mathcal{R}(x, w) = 1$. Le principe d'une Preuve à Divulgation Nulle de Connaissance est de prouver qu'un élément appartient à un langage, sans révéler d'information sur le témoin.

**Modèle de l'oracle aléatoire.** Pour simuler des valeurs aléatoires, nous utilisons des fonctions retournant des valeurs pseudo-aléatoires, appelées pseudo-random functions. Dans le cadre de preuves de sécurité, nous faisons l'hypothèse que ces valeurs sont parfaitement aléatoires en les modélisant à l'aide d'un oracle aléatoire. Quand de telles modélisations sont faites, nous nous plaçons dans le modèle de l'oracle aléatoire.

**Smooth Projective Hash Functions.** Les Smooth Hash Projective Functions, ou SPHF utilisent, elles aussi, la notion de langage. Une SPHF définie sur un langage $\mathcal{L} \subset \mathcal{X}$ avec valeurs dans $\mathcal{V}$, est définie ainsi :

* Setup($1^{\kappa}$) génère les paramètres globaux $\mathit{param}$ qui incluent une description de $\mathcal{L}$.

* $\mathit{HashKG}(\mathit{param})$ génère une clé de hash aléatoire $\mathit{hk}$. Retourne $\mathit{hk}$.

* $\mathit{ProjKG}(\mathit{hk}, x)$ dérive la clé de projection $\mathit{hp}$ depuis $\mathit{hk}$ et un mot $x$. Retourne $\mathit{hp}$.

* $\mathit{Hash}(\mathit{hk}, x)$ calcule la valeur hachée $H_{\mathit{hk}} \in \mathcal{V}$ associée au mot $x$. Retourne $H_{\mathit{hk}}$.

* $\mathit{ProjHash}(\mathit{hp}, x, w)$ calcule $H_{\mathit{hp}} \in \mathcal{V}$ utilisant un témoin $w$ lié au mot $x$. Retourne $H_{\mathit{hp}}$.

Ainsi, si $x$ est un mot de $\mathcal{L}$, nous avons $H_{\mathit{hk}} = H_{\mathit{hp}}$. Cette propriété est appelée **Correctness**. De plus, si $x$ n'est pas un mot de $\mathcal{L}$, non seulement $H_{\mathit{hk}} \neq H_{\mathit{hp}}$, mais le couple $(\mathit{hp}, H_{\mathit{hk}})$ doit aussi être indiscernable de tout autre couple $(\mathit{hp}, v)$ où $v$ est un élément aléatoire de $\mathcal{V}$. Cette propriété est appelée **Smoothness**.

**Forêt de Décision.** Une forêt de décision est un ensemble d'arbres de décision. Un arbre de décision est une succession de nœuds de décision, où chaque nœud de décision consiste en un test. Quand un échantillon est testé, selon le résultat du test, il est redirigé vers le nœud enfant correspondant. Au bout d'un certain nombre de comparaisons, l'échantillon atteindra une feuille (au sens feuille de l'arbre) de décision, indiquant la décision associée à cet échantillon.

Nous présentons en Figure 1a.3 un arbre de décision permettant de décider quel terme employer pour désigner une viennoiserie contenant des barres de chocolat selon votre position géographique. Les feuilles de décision contiennent la bonne expression à employer.

Bien évidemment, les décisions sont souvent plus complexes à prendre que dans cet exemple et nécessitent de considérer un grand nombre de critères. De plus, ces arbres sont généralement construits à partir d'un grand nombre d'observations dont la décision finale est connue. Dans notre
<figure><img src="image_8.png" /><figcaption>Figure 1a.3: Arbre de décision pour désigner une viennoiserie contenant des barres de chocolat.</figcaption></figure>

exemple, ces observations correspondraient à un sondage où nous demandons à des personnes leur
ville d'origine ainsi que le terme qu'ils emploient. Le principe d'une forêt de décision est un
ensemble d'arbres ou chaque arbre ne considère qu'une partie aléatoire des critères, ainsi qu'une
partie aléatoire des observations. Cela permet d'éviter le surapprentissage, qui donnerait trop
d'importance à une observation déviant des autres. Toujours dans notre exemple, cela pourrait
se traduire comme suit. Supposons que dans nos observations un sondé vienne d'un village, dont
il est le seul sondé. Contrairement à tous les résidents des villages alentours, il emploie le terme
pain au chocolat. Le surapprentissage aurait pour conséquence qu'une personne se retrouvant
dans ce même village, recevra la "décision" d'utiliser le terme pain au chocolat, alors que le terme
chocolatine serait plus approprié.

La décision finale se fait en prenant la décision qui est la plus souvent retournée par les arbres
de décision.

1.5.2 Évaluation sécurisée de forêts de décision

Comme énoncé plus haut, notre première contribution a été d'ajouter une couche cryptographique
à l'évaluation de Forêts de Décision dont la décision finale est une valeur binaire. Nous considérons
dans tous les cas que le Serveur a été honnêtement implémenté par Selim, mais que ce dernier
peut essayer d'apprendre des informations sur la cliente, Christelle, à partir de ce qu'il reçoit. Ainsi,
nous utiliserons Selim pour parler au nom du Serveur. Nous commençons par le cas où la cliente,
Christelle, est honnête-mais-curieuse, c'est-à-dire qu'elle suit le protocole, mais qu'elle peut tenter
d'extraire des informations à partir des messages qu'elle reçoit.

1.5.2.1 Cliente honnête-mais-curieuse

La première étape consiste à faire en sorte que Selim envoie de manière sécurisée son modèle à Christelle, tout en étant exploitable par cette dernière. Dans un premier temps, nous avons décidé de représenter les arbres comme un ensemble de branches, comme l'illustre l'exemple donné en Figure 1a.4. Dans cet exemple, nous utilisons la base de données *iris* qui permet de classifier un iris à partir de la longueur *l* et la largeur *w* de son pétale. Les données de la base n'étant pas entières, la première étape consiste à les normaliser. Pour ce faire, nous définissons $L = 10 \times (l - 1)$ et $W = 20 \times w$. Ainsi, toutes les valeurs de la base seront comprises entre 0 et $63 = 2^6 - 1$. Pour en faire un arbre de décision binaire, nous nous concentrons sur la décision affirmant ou non que l'iris en question est de l'espèce *virginica* ou non.

Étant donné qu'un pétale ne peut aboutir qu'à une seule feuille, il n'est pas nécessaire de
considérer les feuilles ayant 0 pour décision finale. En effet, si un pétale n'atteint aucune des
branches dont la décision finale est 1, cela implique que la décision finale est 0. C'est d'ailleurs
cette observation qui nous contraint à considérer les arbres binaires. Ensuite pour chacune des
branches, nous allons procéder comme suit. Pour chaque décision, nous allons utiliser un schéma
de chiffrement additivement homomorphe pour générer un chiffré pour chaque valeur possible prise
par l'échantillon pour le critère demandé, dont la valeur chiffrée dépendra de la valeur du seuil. Par
<figure><img src="image_9.png" /><figcaption>Figure 1a.4: Représentation d'un arbre de décision entraîné sur la base de données *iris* dans le cas honnête-mais-curieux</figcaption></figure>

exemple, prenons la première comparaison de la première branche : (W > 12). Si 64 valeurs sont possibles (de 0 à 63), avec un seuil à 12, nous générons dans un premier temps 13 chiffrés de 0, correspond aux valeurs comprises de 0 à 12, qui ne vérifient pas la comparaison ; puis 51 chiffrés de 1, correspondant aux valeurs de 13 à 63 qui vérifient la comparaison. Une fois que toutes les comparaisons sont encodées, Selim les envoie à Christelle.

Une fois que Christelle a reçu les branches encodées par Selim, elle récupère le chiffré correspondant à la valeur de son critère. En procédant ainsi pour chacun des nœuds, cela nous permet d'exploiter la propriété homomorphe du schéma de chiffrement. En effet, si toutes les comparaisons sont vérifiées pour une branche, Christelle n'aura que des chiffrés de 0, qu'elle pourra sommer grâce à la propriété homomorphe du schéma de chiffrement, aboutissant à un chiffré de 0. Dès qu'une des comparaisons n'est pas vérifiée, la somme ne vaut plus 0, et prend une valeur comprise entre 1 et la longueur de la branche. Rappelons que Christelle ne sait rien de la valeur des chiffrés qu'elle possède, que ce soit avant ou après la somme. Elle pourrait renvoyer les chiffrés obtenus directement à Selim pour qu'il les déchiffre et puisse prendre sa décision. Cependant, cela révèlerait le score de chaque branche. Pour empêcher Selim de récupérer la moindre information supplémentaires sur le score de ses branches, Christelle a deux modifications à apporter. La première consiste à permuter les branches pour empêcher Selim d'associer un score à une branche. Néanmoins, il pourra toujours calculer le score moyen des branches, ce qui constitue une information complémentaire comparativement à ce qu'il doit apprendre, c'est-à-dire le nombre de branches qui sont validées. C'est pourquoi Christelle multiplie les chiffrés obtenus par une valeur aléatoire. En multipliant un chiffré de 0 par une valeur aléatoire, cela reste un chiffré de 0, alors qu'en multipliant un chiffré d'une valeur non-nulle par une valeur aléatoire, cela devient un chiffré d'une valeur aléatoire. Ainsi, avoir permuté et randomisé ses scores, Christelle peut les envoyer à Selim.

Une fois en possession des scores chiffrés de Christelle, Selim les déchiffre. S'il obtient un 0 en déchiffrant, cela signifie qu'une branche a été validée. Le score global de Christelle se détermine donc en comptant le nombre de chiffrés qui ont donné 0 en étant déchiffrés. Ensuite, si ce score est suffisamment élevé pour Selim, ce dernier valide l'échantillon de Christelle. Sinon, il le rejette.

### 1.5.2.2 Cliente malveillante

Au vu de la description faite ci-dessus, si Christelle est malveillante et qu'elle ne suit pas le protocole, il est aisé pour elle de duper Selim. En effet, elle pourrait outrepasser les évaluations des branches et générer suffisamment de chiffrés de 0 pour être validée par Selim. Pour contrer cette attaque, la solution est de faire en sorte que Christelle ne sache pas quelle valeur est attendue par le serveur. Pour ce faire, nous allons à présent considérer tous les nœuds de décision dont au moins un des
nœuds fils est une feuille. Puis, pour chacun de ces nœuds, nous allons aléatoirement générer une valeur appelée *polarité*, qui déterminera l'orientation de la dernière comparaison. Quand cette polarité vaut 1, la dernière comparaison reste inchangée (en bleu). Tandis que si cette polarité vaut -1, la dernière comparaison est inversée (en rouge). Nous utilisons aussi des comparaisons factices pour éviter à Christelle de pouvoir reconstruire l'arbre en utilisant des branches toutes de même longueur et utilisant tout le temps les mêmes critères. Dans la Figure 1a.5, nous reprenons le même exemple que dans la Figure 1a.4, mais en représentant les arbres comme nous venons de le décrire. De plus, nous faisons usage de noeuds factices dont le résultat est toujours vrai ($L \le 63$ et $W \le 63$) ainsi que des noeuds dont le résultat est toujours faux ($W > 63$) – les valeurs prisent par $L$ et $W$ étant comprises entre 0 et 63. Grâce à cees noeuds factices, toutes les branches sont de même longueur et utilisent le même nombre de fois les critères.

<figure><img src="image_10.png" /><figcaption>Figure 1a.5: Représentation d'un arbre dans le cas d'une cliente malveillante. Quand la polarité vaut -1, le dernier nœud de décision est celui en rouge, tandis que si la polarité vaut 1, le dernier nœud de décision est celui en bleu.</figcaption></figure>

Ensuite, pour chaque chemin, jusqu'à la pénultième comparaison, les valeurs vérifiant la comparaison seront encodées par des chiffrés de 1 (là où ils étaient encodés par des chiffrés de 0 dans le cas précédent) et les valeurs ne la vérifiant pas seront encodées par des chiffrés de 0 (là où ils étaient encodés par des chiffrés de 1 dans le cas précédent). Pour la dernière comparaison, les valeurs allant dans le sens de la polarité seront encodées par des chiffrés de $\delta$, où $\delta$ est le nombre de comparaisons dans la branche, et les valeurs n'allant pas dans le sens de la polarité seront encodées par des chiffrés de 0.

Ensuite, Christelle fait la somme, comme dans le cas précédent. Ainsi, si un échantillon passe toutes les comparaisons, la dernière comprise, sa somme sera de $2\delta - 1$. S'il passe toutes les comparaisons sauf la dernière, la somme sera de $\delta - 1$. Dans tous les autres cas, la somme peut être une valeur comprise entre 0 et $\delta - 2$, et $\delta$ et $2\delta - 2$.

La prochaine étape consiste à convertir cette somme en un score, qui vaut $-1, 0$ ou $1$. Nous ne détaillerons pas le processus complet ici, mais l'idée est la suivante : il faut convertir un chifré de $2\delta - 1$ en un chifré de 1, un chifré de $\delta - 1$ en un chifré de $-1$, et tous les autres chiffrés en un chifré de 0.

<figure><img src="image_11.png" /><figcaption>Figure 1a.6: Correspondance entre résultat et score</figcaption></figure>

L'idée est de comparer, de manière sécurisée, la somme obtenue par Christelle avec $\delta - 1$ et $2\delta - 1$. Si la première comparaison est vraie, Christelle retourne à Selim un chifré de $-1$, si elle
est fausse, elle retourne un chiffré de 1. Pour la deuxième comparaison, c'est l'inverse. Christelle retourne un chiffré de 1 si elle est vraie, sinon elle retourne un chiffré de -1. Notre construction inclut des preuves garantissant que Christelle envoie bien les valeurs qu'elle est censée retourner à Selim, l'empêchant ainsi d'essayer de modifier son score. Ensuite, Selim fait la somme des chiffrés. Il obtient un chiffré de -2 si la première égalité est vraie (si la première est vraie, la deuxième est forcément fausse), un chiffré de 2 si la deuxième est vraie, et un chiffré de 0 dans tous les autres cas. En divisant ce chiffré par 2, nous retrouvons bien ce qui était espéré en Figure 1a.6. La prochaine étape consiste à multiplier ce score par sa polarité, ce qui donne 1 si l'échantillon est accepté par la branche, -1 si l'échantillon est rejeté par la branche, et 0 dans tous les autres cas.

Rappelons que jusqu'ici, Selim n'est en possession que de valeurs chiffrées par Christelle, qu'elle seule peut déchiffrer. Selim va alors additionner tous les chiffrés obtenus (un par branche), puis randomiser le total, avant d'envoyer le résultat obtenu à Christelle pour qu'elle le déchiffre. Cette dernière déchiffre le score global randomisé, qu'elle retourne à Selim, qui inverse la randomisation pour retrouver le score global de Christelle. Dû à la randomisation faite par Selim, la moindre tentative de triche faite par Christelle aura pour conséquence un score final totalement aléatoire, et avec forte probabilité en dehors de l'intervalle d'acceptation de Selim.

**Coûts.** Dans chacun des deux contextes, le modèle encodé est envoyé hors protocole. C'est-à-dire qu'il n'est envoyé qu'une seule fois pour plusieurs exécutions faites par la cliente. La taille de l'encodage dépend de plusieurs paramètres : le nombre de branches, le nombre de valeurs possibles prises par les critères et la longueur des branches. Plus un paramètre ci-dessus est élevé, plus le résultat sera précis, mais plus le modèle sera lourd. Le meilleur compromis est donc propre à l'utilisation qui en sera faite. Le poids du modèle va de 5 Ko pour 10 branches de longueur 2 et 4 valeurs possibles par critères, à 25 Mo pour 100 branches de longueur 16 et 256 valeurs par critère. Nous référons le lecteur à la Table 3.1 pour plus détails.

Pendant l'exécution du protocole dans le cas honnête-mais-curieux, Christelle envoie un chiffré de 512 bits par branche et le serveur n'envoie rien. Dans le cas d'une exécution avec une cliente malveillante, cela impacte les coûts de communication. La cliente envoie un peu plus de 20 Ko par branche et le serveur envoie 4 Ko par branche.

Étant donné que la cliente n'envoie qu'un seul message au serveur par exécution du protocole, cela surpasse tous les autres protocoles similaires, au prix d'une phase hors protocole assez conséquente (mais qui n'est faite qu'une fois pour plusieurs protocoles). Dans le cas malveillant, notre protocole est un compromis entre le nombre de messages envoyés et le coût de communication global du protocole. Voir Table 3.3 pour plus de détails.

**Performances.** Nos constructions ont été mises à l'épreuve à travers deux applications faisant appel aux arbres de décision : l'authentification continue et la détection de Spam. Dans les deux cas, nous obtenons un taux de faux positifs autour de 2% pour une précision globale autour de 90%.

### 1.5.3 Transfert Inconscient Universellement Composable basé sur les SPHF avec zone grise

Comme énoncé plus haut, les Transferts Inconscients peuvent reposer sur la notion de *Smooth Projective Hash Functions with Gray Zone*, une primitive que nous avons introduite qui consiste en une SPHF avec la propriété d'Insolubilité de la Décomposition. Considérons $\mathcal{X}$, un ensemble de mots, $\mathcal{L}$ et $\mathcal{L}'$ deux langages tels que $\mathcal{L} \cap \mathcal{L}' = \emptyset$ et $\mathcal{L} \cup \mathcal{L}' \subset \mathcal{X}$. Une *Smooth Projective Hash Function with Gray Zone* est alors définie comme :
* Setup($1^\kappa$) génère les paramètres globaux **param** qui incluent une description de $\mathcal{L}$ et $\mathcal{L}'$ tels que $\mathcal{L} \cap \mathcal{L}' = \emptyset$ et $\mathcal{L} \cup \mathcal{L}' \subset \mathcal{X}$.

* **HashKG(param)** génère une clé de hash aléatoire **hk**. Retourne **hk**.

* **ProjKG(hk, x)** dérive la clé de projection **hp** depuis **hk** et un mot **x**. Retourne **hp**.

* **Hash(hk, x)** calcule la valeur hachée $H_{hk} \in \mathcal{V}$ associée au mot **x**. Retourne $H_{hk}$.

* **ProjHash(hp, x, w)** calcule $H_{hp} \in \mathcal{V}$ utilisant un témoin **w** lié au mot **x**. Retourne $H_{hp}$.

Tout comme les SPHF classiques, nos SPHFwGZ verifient les propriétés suivantes, pour tout ensemble $\mathcal{L}, \mathcal{L}', \mathcal{X}$ définis à l'aide de **param**.

* **Correctness:** Pour tout **x** dans $\mathcal{L}$, $H_{hk} = H_{hp}$, où $hk \leftarrow HashKG(param)$, $hp \leftarrow ProjKG(hk, x)$, $H_{hk} \leftarrow Hash(hk, x)$, et $H_{hp} \leftarrow ProjHash(hp, x, w)$ pour le témoin **w** de $x \in \mathcal{L}$;

* **Smoothness:** Pour tout **x** dans $\mathcal{L}'$, les distributions de ($hp, H_{hk}$) et ($hp, v$) sont indiscernables, où $hk \leftarrow HashKG(param)$, $hp \leftarrow ProjKG(hk, x)$, $H_{hk} \leftarrow Hash(hk, x)$, et $v \leftarrow \mathcal{V}$;

En supplément, les ensembles $\mathcal{L}, \mathcal{L}'$ et $\mathcal{X}$ doivent aussi fournir l'Insolubilité de la Décomposition. Pour définir de manière plus formelle la notion d'Insolubilité de la Décomposition, nous introduisons la fonction **ComplementWord**:

* **ComplementWord($\rho, x$)** calcule, à partir d'un mot **x** et d'une valeur de référence $\rho$, le complémentaire $x'$ de **x**. Retourne $x'$.

Ainsi, les ensembles $\mathcal{L}, \mathcal{L}'$ et $\mathcal{X}$ fournissent l'Insolubilité de la Décomposition s'il est difficile, étant donné une valeur aléatoire $\rho$ dans $\mathcal{X}$, de générer deux valeurs **x** et **y** hors $\mathcal{L}'$ de sorte que $y = \text{ComplementWord}(\rho, x)$.

### 1.5.3.1 Construction du protocole de Transfert Inconscient

Après la configuration du protocole, la réceptrice, Renée, génère un mot $x_b$ dans $\mathcal{L}$ et son témoin, à l'aide de la fonction $\text{WordGen}\mathcal{L}$ :

* **WordGen($\mathcal{L}$, $\mathcal{L}'$, $\mathcal{X}$)** génère aléatoirement **x** dans $\mathcal{L}$, et retourne **x** ainsi que son témoin **w**.

Puis à l'aide de $\rho$, une valeur de référence commune à la réceptrice et à l'expéditeur, Renée génère $x_{1-b}$, le complément de $x_b$ relativement à $\rho$. Grâce à l'Insolubilité de la Décomposition, $x_{1-b}$ est dans $\mathcal{L}'$. Ensuite, Edouard calcule les clés de hash et de projection sur chacun des mots ainsi que les hash associés, qui serviront de masque pour les messages initiaux $m_0$ et $m_1$.

Dû à la propriété de correctness de $x_b$ dans $\mathcal{L}$, Renée pourra démasquer $m_b$, le mot qu'elle souhaite récupérer. À l'inverse, comme $x_{1-b}$ est dans $\mathcal{L}'$, la propriété de smoothness assure que Renée ne peut pas calculer $m_{1-b}$. En reprenant l'exemple pédagoqique de Transfert Inconscient donné plus haut, $x_b$ et $x_{1-b}$ peuvent être vus comme les cadenas, et le témoin **w** associé à $x_b$ en est la clé. Edouard 'ferme' les cadenas en utilisant **Hash**, que Renée ouvre en utilisant **ProjHash** et **w**.

Pour réaliser la preuve – qui ne sera pas détaillée ici – que le protocole est universellement composable, ce dernier prend une deuxième valeur commune $\sigma$. Ces valeurs communes, quand elles sont générées depuis l'ensemble adéquat, permettent à la partie honnête d'extraire les inputs des parties malveillantes, les dissuadant ainsi d'agir de manière malveillante. Plus précisément, si Renée, la réceptrice, est malveillante, Edouard sera en mesure d'extraire $b$, que Renée ne souhaite pas divulguer. De manière similaire, Renée sera en mesure de récupérer les deux messages $m_0$ et $m_1$ si Edouard est malveillant.
<table><caption>Figure 1a.7: Description du protocole de Transfert Inconscient</caption><thead><tr><th>Réceptrice</th><th>Valeur d'entrée</th><th>Expéditeur</th></tr></thead><tbody><tr><td>b &isin; {0, 1}</td><td></td><td>m<sub>0</sub>, m<sub>1</sub> &isin; M</td></tr><tr><td>&rho;</td><td>Valeur référence</td><td>&rho;</td></tr><tr><td>param &larr; Setup(&rho;)</td><td></td><td>param &larr; Setup(&rho;)</td></tr><tr><td>(x<sub>b</sub>, w) &larr; WordGenL(param)</td><td></td><td>x<sub>1</sub> &larr; ComplementWord(&rho;, x<sub>0</sub>)</td></tr><tr><td>x<sub>1-b</sub> &larr; ComplementWord(&rho;, x<sub>b</sub>)</td><td>x<sub>0</sub> &larr; &rarr;</td><td>for i in {0, 1} :<br/>hk<sub>i</sub> &larr; HashKG(param)<br/>hp<sub>i</sub> &larr; ProjKG(hk<sub>i</sub>, x<sub>i</sub>)<br/>H<sub>i</sub> &larr; Hash(hk<sub>i</sub>, x<sub>i</sub>)<br/>c<sub>i</sub> = (H<sub>i</sub> &oplus; m<sub>i</sub>, hp<sub>i</sub>)</td></tr><tr><td>H' &larr; ProjHash(c<sub>b,1</sub>, x<sub>b</sub>, w)</td><td>(c<sub>0</sub>, c<sub>1</sub>) &larr; &rarr;</td><td></td></tr><tr><td>m = H' &oplus; c<sub>b,0</sub></td><td></td><td></td></tr></tbody></table>

**Configuration depuis un schéma de chiffrement homomorphe.** Dans cette section, nous détaillons la configuration des langages $\mathcal{X}$, $\mathcal{L}$, $\mathcal{L}'$ à partir d'un schéma de chiffrement homomorphe, possiblement avec des échecs de déchiffrement. Un tel schéma de chiffrement sera dénoté par $\Pi = (\text{Setup}, \text{KGen}, \text{Enc}, \text{Dec})$.

Ainsi, $\mathcal{X}$ se définit comme étant l'ensemble des chiffrés générés par $\Pi$, tandis que $\mathcal{L}$ est l'ensemble des chiffrés de 0 et $\mathcal{L}'$ est l'ensemble des chiffrés ne se déchiffrant pas en 0. De manière plus formelle, nous avons :

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

En guise d'instanciation introductive, nous décrivons un SPHFwGZ basé sur le schéma de chiffrement d'ElGamal. Bien que sa zone grise soit vide, cela appuie le fait que notre construction peut se généraliser à tout SPHF. La seconde instanciation repose sur le schéma de chiffrement LWE. Ce schéma se base sur les réseaux euclidiens, qui sont une primitive post-quantique et présente une zone grise, qui ne pose pas de problème dans notre construction, car la propriété d'Insolubilité de la Décomposition est vérifiée.

### 1.5.4 Analyse de sécurité du protocole EDHOC

EDHOC est un protocole authentifié d'échange de clés optimisé pour être exécuté sur des appareils de l'Internet des Objets. Il permet à deux parties, un Initiateur et un Répondant, de partager une clé commune à la fin de l'exécution du protocole. Pour l'authentification, les deux parties peuvent soit utiliser des signatures digitales, soit utiliser une clé secrète statique.

C'est dans le contexte de l'utilisation de cette seconde solution pour l'Initiatrice et le Répondant que nous étudierons le protocole. Ce dernier va également générer une paire de clés éphémères (une publique, une secrète) pour chacune des parties, qui seront utilisées uniquement pour l'exécution dudit protocole. Ainsi, chaque partie possède quatre clés :

Ensuite les clés ci-dessus sont dérivées à l'aide de fonction d'expansion et d'extraction afin d'obtenir la clé de session finale. Nous n'allons pas détailler le processus de calcul de la clé ici (voir Chapitre 5, Figures 5.2 et 5.3), ni l'analyse, mais allons plutôt directement présenter les résultats obtenus.

Pour rappel, les trois points de sécurité à analyser sont les suivants

* Confidentialité de la clé : Au plus les deux participants connaissent la clé de session finale.
<table><caption>Table 1a.1: Clés des deux parties. En orange les clés du Répondant et en blanc, les clés de l'Initiatrice</caption><tr><td>X<sub>e</sub>, x<sub>e</sub></td><td>Clés publique et secrète éphémères de l'Initiatrice</td></tr><tr><td>Y<sub>e</sub>, y<sub>e</sub></td><td>Clés publique et secrète éphémères du Répondant</td></tr><tr><td>X<sub>s</sub>, x<sub>s</sub></td><td>Clés publique et secrète statiques de l'Initiatrice</td></tr><tr><td>Y<sub>s</sub>, y<sub>s</sub></td><td>Clés publique et secrète statiques du Répondant</td></tr></table>

De plus, nous devons prouver la *Perfect Forward Secrecy* qui stipule que, même si les clés statiques sont dévoilées, un attaquant ne peut pas calculer les précédentes clés de session.

* *Authentification Mutuelle* : Seuls les deux participants ont le matériel pour calculer la clé de session finale.

* *Protection de l'identité* : Au plus les deux participants connaissent l'identité des deux participants.

Pour la réalisation de la preuve, nous nous sommes placés dans le modèle de l'oracle aléatoire dans lequel les valeurs retournées par les fonctions d'expansion et d'extraction sont considérées comme étant parfaitement aléatoires.

**Résultats de l'analyse.** Sous les hypothèses de la difficulté du problème *Gap Diffie-Hellman*, de la sécurité sémantique et le caractère infalsifiable du chiffrement authentifié ainsi que dans le modèle de l'oracle aléatoire, le protocole EDHOC atteint les niveaux de sécurité suivants : environ 128 bits de sécurité pour la confidentialité de la clé ainsi que pour la protection de l'identité de chacune des parties. Cependant, pour la sécurité de l'authentification mutuelle, la sécurité n'atteint pas un niveau supérieur à 64 bits. Bien que cela soit prévu pour le Répondant qui peut atteindre une sécurité de 128 bits pour son authentification en envoyant un quatrième message comme le suggère la documentation du protocole, ce n'est pas le cas pour la sécurité de l'authentification de l'Initiatrice. En effet, la seule valeur envoyée par l'Initiatrice qui dépend de sa clé statique $x_s$ est un Code d'Authentification de Message de 64 bits de long (dû aux paramètres agressifs imposant cette longueur). Ainsi, un attaquant peut deviner ce tag avec probabilité $1/2^{64}$, ce qui implique la sécurité maximale de 64 bits. Bien qu'un chiffrement supposé authentifié soit envoyé par l'Initiatrice, il peut être calculé par n'importe quel individu souhaitant usurper l'identité de l'Initiatrice s'il devine correctement le Code d'Authentification de Message évoqué plus haut. Le choix d'utiliser un chiffrement authentifié plutôt qu'un chiffrement classique n'a donc aucun impact sur la sécurité de l'authentification de l'Initiatrice.

De plus, la sécurité de chacun de ces points dépend du nombre de protocoles simultanément exécutés. En effet, dû à l'utilisation d'une chaîne vide en tant que valeur d'entrée d'une fonction d'extraction, un attaquant peut exploiter une seule requête à l'oracle DDH pour attaquer plusieurs protocoles.

Nous présentons donc maintenant des améliorations afin d'améliorer la sécurité du protocole EDHOC

**Améliorations.** Une première amélioration consiste à remplacer la chaîne vide ci-dessus par une valeur dépendant de la session courante. Cela permet de rendre la sécurité globale indépendante du nombre de sessions exécutés simultanément. La seconde amélioration consiste à passer la taille du Code d'Authentification de Message envoyé par l'Initiatrice de 64 bits à 128 bits, et de remplacer le chiffrement authentifié par un chiffrement *One-Time Pad*. Ainsi, la sécurité de l'authentification de l'Initiatrice atteint 128 bits, et ce, sans surcoût de communication ni de calcul. En effet, les 64 bits du chiffrement authentifié sont transposés au Code d'Authentification de Message. Ainsi, le
chiffrement n'a plus besoin d'être authentifié et le *One-Time Pad* peut être utilisé sans modifier
la longueur du chiffré.
Chapter 1b

**Introduction – English version**

**2.1 Motivations**

With the recent deployment of the General Data Protection Regulation (GDPR), confidentiality
has become an essential requirement. From secret messages on pieces of paper in the playground
to inter-presidential communications, cryptography easily finds its place in human-to-human com-
munications. Nowadays, the spectrum of use of cryptography is getting wider by the day. Crypto-
graphy is no longer limited to interactions between two physical persons, but also involves servers,
phones, etc... Any device connected to the Internet uses cryptography. However, even if on the
one hand, protecting data is obviously a good feature, on the other hand, someone could need to
extract data. If we use the example of messaging services, anyone expects that only you and the
person you are messaging with can get access to your messages. However, guaranteeing such a
high confidentiality level also attracts malicious people, potentially using this messaging service to
send messages whose content may be illegal. One could therefore hope for the messaging server
to detect such content. Then, how to correctly balance confidentiality and data exploitation?
A domain of cryptography studying this problem is the secure multiparty computation. In short,
secure multiparty computation allows some parties to jointly and securely evaluate a function on
their inputs, while keeping their inputs private. Applied to our example, this would consist for a
server to be able to detect when a message contains jeopardizing content.

When data is collected, it is often used as an input to some Machine Learning model. Machine
Learning is a powerful tool with many use-cases: Email filtering, fraud detection, personalized
marketing, etc... Such protocols are often run on a server receiving data from an other device.
However, in some cases, as pictures improvement or continuous authentication, models are run
on the device itself. We now focus on the latter use-case. Continuous authentication seamlessly
 authenticates a user on his phone. This can be made by using the swipes he makes, taking
into account several features as the swipe duration, the pressure, etc... Obviously, such data are
sensitive. But the authentication model, that can be represented as a list of criteria to respect,
also needs to remain private to avoid impersonation. This problem is similar to the one described
above. Indeed, this can be reworded as the question:

*How to use Machine Learning for Continuous Authentication while remaining privacy-friendly?*

We provide an answer to this question in the third part of this thesis. Our answer provides a
protocol secure against an honest-but-curious and its upgrade to provide security against malicious
adversaries. An honest adversary follows the protocol but tries to extract as much information
as he can whereas the malicious one can deviate from the protocol to learn more information or
influence the output of the protocol. The protocol secure against malicious adversaries makes use
of a two-party computation primitive named Oblivious Transfer allowing (in its simplest form) a
receiver to receive one out of two messages from a sender. At the end of an Oblivious Transfer protocol, the receiver did learn nothing about the second message of the sender, and the sender has no clue which message has been retrieved by the receiver. Several Oblivious Transfer (OT) protocols instantiations do exist and among them, we focus on those based on Smooth Projective Hash Functions (SPHF) (also known as Hash Proof Systems). SPHFs work using a language, made of words, a pair of hash functions and a pair of keys, such that when a word of the SPHF belongs to the language, the keys, together with their respective hash functions led to the same value. This property is called correctness. Also, when a word is not in the language, the hash outputs should be different and indistinguishable from random. This property is called smoothness. Oblivious Transfers based on Smooth Projective Hash Functions are well studied and efficient when based on classical cryptography. However, when using SPHF based on post-quantum cryptography rise words where one can not claim correctness nor smoothness for this subset of words, denoted Gray Zone. Ignoring them would leave room for potential attacks. Hence, we follow some recent works on this question:

*How to deal with those Smooth Projective Hash Functions with Gray Zone?*

Moreover, as Oblivious Transfers are part of a larger protocol, we need to ensure that composing it with other protocols does not bring security weakness for the root protocol. A protocol providing such security is said to be Universally Composable. Thus, we expect our Oblivious Transfer security to be proven in the Universal Composability framework.

As said at the beginning of this section, cryptography now involves not only humans but also devices, as server, mobile phones, etc... More specifically, more and more products get connected to the Internet in our houses. Speakers, light bulb, fridges, ovens and even trucks fuel tank cap are some examples of the devices connected to the Internet. Those products may be intended to make our life easier, funnier or safer. We can imagine a surveillance camera that may tell your heating to turn on when your car is detected (using Machine Learning), and the same camera sending you a video stream of what it sees when detecting unexpected presence. This world where everything and anything can be connected to the Internet is called *Internet of Things*, or IoT in short. In 2021, the number of active IoT devices in the world is estimated at around 12 billions, while at the same time, the mondial population was estimated at less than 8 billions. However, such devices are often limited in terms of energetic consumption, computing power or available memory. The domain studying cryptography on restraint devices is called *lightweight cryptography*. In such domain, the goal is to design primitives that provide the best trade-off between efficiency, costs, and security. One of the those primitives is lightweight key exchange protocols, where two constrained devices end with a common shared key. Among the lightweight key exchange protocols, some of them provide an additional authentication of the partnered device.

One of them, **EDHOC** for *Ephemeral Diffie-Hellman Over COSE*, is in development. EDHOC is expected to become an important component in securing constrained networks and devices for the Internet of Things. The keys shared by the devices after the execution of the EDHOC protocol can be used to protect future applications. Steps of development include formal and computational security analysis. The second one was part of this thesis, leading to the **Computational Security Analysis of the EDHOC protocol**.

## 2.2 Objectives

**Privacy Preserving Machine Learning for Continuous Authentication.** As said above, continuous authentication may rely on Machine Learning. In most cases, Machine Learning operations are made on the server side. However, in the use-case of continuous authentication, it is more
relevant to make the computation on the client-side in order to reduce the communications be-
tween the client and the server. As the computation is made on the client-side, the server has
to securely send him the model. Hence, we may wonder which Machine Learning method is the
most compliant with cryptography. The choice has been made to work on Decision Forest, as
their theoretical conception is compliant with what can be done in cryptography, which is not the
case for other methods.

The objective was to add a cryptographic layer to this solution. More generally, with a Decision
Forest model stored on a server, and the client data stored on a mobile phone, to securely evaluate
the client data on the server model while keeping privacy for both of them. Indeed, the server
should not learn more information about the client data than the outcome of the protocol, and
the client should not learn information about the model, to avoid impersonation.

**A Universally Composable post-quantum Oblivious Transfer based on SPHF.** As said pre-
viously, using SPHF based on post-quantum primitives introduces a difference by opposition to
classical cryptography based ones. This difference is that a gap appears, where one can not claim
correctness nor smoothness opening the doors to potential attacks. The objective of this project
is to tame this gap. By opposition to the solution provided by [BBB$^{+22a}$], where they use zero-
knowledge proofs, we will focus on required properties on the SPHF construction to ensure the gap
does not open the doors for attacks. In addition, even if we ensured no attack is possible on the
SPHF, this is not enough to provide Universal Composability when used for building an Oblivious
Transfer protocol. Hence, we also have to prove our Oblivious Transfer construction is secure in
the Universal Composability framework.

**Computational Security Analysis of EDHOC.** The Lightweight Authenticated Key Exchange (LAKE) working group of the Internet Engineering Task Force (IETF), came to us with the project to study EDHOC. The EDHOC authenticated key exchange offers two ways to provide authentication. A peer can use a signature or a static Diffie-Hellman key previously owned. We focus on the case both peers use a static Diffie-Hellman key, together with aggressive parameters. Hence, our objectives were to prove, in this context, the security of the following requirements:

* Key Privacy or Implicit Authentication: At most both participants know the final session key

* Mutual Authentication or Explicit Authentication: Exactly both participants can compute the final session key

* Identity Protection: At most both participants know the identity of the involved peers.

**2.3 Contributions**

**Privacy Preserving Machine Learning for Continuous Authentication.** In our context, the server evaluates a model *M* on client data x, and accept or reject according to the outcome of the evaluation. We designed two protocols to securely evaluate a binary decision forest. In both those constructions the server is considered as Honest-but-Curious, but in the first construction the client is Honest-but-Curious while in the second one, we consider a malicious client. The use-cases we take into consideration requiring few interactions between the server and the client, we split the protocol in two phases. A first phase, offline, consists in the server sending its secure model to the server, and the second phase, online, consists in the evaluations.

In the setting of an Honest-but-Curious client, the evaluation simply consists in one flow
sent from the client to the server. Even if no previous work were done considering client-side
computation, this result outperforms works considering server-side computation and is optimal.
However, the extension of this protocol to the malicious setting implies two additional round-trip flows. Some previous constructions need less flows than ours, but more bandwidth, or inversely. Thus, our protocol can be seen as a trade-off between bandwidth and flows.

Our construction leaks the amount of successful paths to the server. However, rather than a real leak, this may help the server to take decisions according to this amount of successful paths, interpreted as a confidence index.

Another contribution is that, while our construction secure against malicious client uses Garbled Circuits, we do not need to use any additional techniques compared to their use in an honest-but-curious setting. Thus, we do not need to use solutions such as *Cut & Choose*. Even if *Cut & Choose* solution is well studied and optimized [MF06, LP07, Lin13, LR14, AMPR14, WMK17], it still is an expansive solution requiring $\ell$ Garbled Circuits to reach a statistic security of $2^{-\ell}$ bits. In a survey, Dupin et al. [DPB18] showed that a malicious generator can corrupt a Garbled Circuits only by adding NOT-gates or by failure attacks, but our constructions naturally provide security against these attacks in our context. Indeed, in case of failure attack, the server will reject and thus learn nothing about the threshold. If the circuit is modified, we introduced the notion of polarity, that makes the expected outcome unpredictable. Hence, a malicious client has no clue how to modify the circuit to successfully cheat and the probability to correctly modify the Garbled Circuits is the probability to correctly guess the polarity of each path.

Even if our solution has to use discrete values instead of floats – as cryptography dealing with float values is too expansive –, implying a loss of precision, we reach an accuracy of around 90% on the Spambase database as well as on a continuous authentication database.

This work has led to the following publication:

★ 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

and the (updated) working paper is available on HAL:

► 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

**A Universally Composable post-quantum Oblivious Transfer based on SPHF.** Rather than annihilate the Gray Zone specific to post-quantum-based SPHF instantiations, we introduced a new property, the Decomposition Intractability. When this property is verified, an adversary can not generate efficiently two values either in the language of the SPHF, either in that Gray Zone, that are complementary to each other, given a random element. We denote an SPHF that verifies this property a *Smooth Projective Hash Function with Gray Zone* (SPHFwGZ).

Then, we made a general construction of Oblivious Transfer protocol based on any SPHFwGZ, that has been proven secure in the Universal Composability framework. This setup has been instantiated with two such encryption schemes. The first one is the ElGamal encryption scheme. Even if the SPHFwGZ based on ElGamal does not in fact contains a gap, using it as an instantiation shows that our construction works from any SPHF as Decomposition Intractability is immediate. The second instantiation we give is based on lattices and a *Learning with Errors* (LWE) based encryption scheme. LWE encryption scheme has some decryption failures – justifying the existence of the Gray Zone – but we showed the Decomposition Intractability holds anyway. This instantiation allows to show the genericity of our construction, from classical to post-quantum cryptography.

This work has led to the following publication:

★ 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
and the (updated) working paper is available on HAL:

► Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Baptiste Cottier, and David Pointcheval. Post-Quantum Oblivious Transfer from Smooth Projective Hash Functions with grey¹Zone. hal-03772089, 2022. https://hal.archives-ouvertes.fr/hal-03772089

**Computational Security Analysis of EDHOC.** We did the security proof of the EDHOC protocol using the authentication method based on static Diffie-Hellman keys. The proof has been made considering aggressive parameters, i.e. a MAC digest length of 64 bits.

We showed, under several classical assumptions, that the EDHOC authenticated key exchange provides a nearly 128 bits security for the Key Privacy and the Identity Protection. Nevertheless, Mutual Authentication security only reaches a 64 bits security for both the Initiator and the Responder. Even if this is assumed for the Authentication Security of the Responder, as the documentation suggests him to send a fourth authenticated message to increase its security, this is not the case for the Initiator Security. However, we emphasized that with some modifications, without any extra-cost compared to the initially analyzed version, the EDHOC protocol can provide a 128-bit Mutual Authentication security. Another of our modification makes the security proof tighter by making it independent of the number of parallels running sessions.

This work has led to the following (best paper awarded) publication:

★ 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

and the (updated) working paper is available on HAL:

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

## 2.4 Organization

This chapter introduced the reader to the context of the thesis. Chapter 2 contains all the notions required to a full understanding of the content of chapter 3, chapter 4 and chapter 5. Chapter 3 introduces our work made to add a cryptographic layer to an already existing continuous authentication protocol. It contains our solutions and their performance. Next, in the chapter 4, we detailed the construction of our Smooth Projective Hash Functions with Gray Zone, and gave some instantiations of it, on both classical and post-quantum cryptography. Chapter 5 is our security proof of the EDHOC protocol and the modifications we made to increase its security without adding communication nor computation cost. The unsuccessful first project is nevertheless detailed in Appendix as it is part of the thesis. We then provide a conclusion, containing some research prospects and open questions.
# Chapter 2

# Preliminaries

In this chapter, we introduce most of the necessary notions and primitives used in the thesis.

<table><tr><td>2.1</td><td>Complexity definitions</td><td>26</td></tr><tr><td>2.2</td><td>Symmetric cryptography</td><td>26</td></tr><tr><td>2.2.1</td><td>Symmetric encryption</td><td>26</td></tr><tr><td>2.2.2</td><td>Message authentication code</td><td>29</td></tr><tr><td>2.2.3</td><td>Authenticated Encryption</td><td>30</td></tr><tr><td>2.2.4</td><td>Hash functions</td><td>31</td></tr><tr><td>2.2.5</td><td>Random oracle model</td><td>31</td></tr><tr><td>2.2.6</td><td>Pseudorandom functions</td><td>32</td></tr><tr><td>2.3</td><td>Asymmetric cryptography</td><td>32</td></tr><tr><td>2.3.1</td><td>Discrete Logarithm problem and Diffie-Hellman assumptions</td><td>32</td></tr><tr><td>2.3.2</td><td>Factorization problems</td><td>34</td></tr><tr><td>2.3.3</td><td>Public-key encryption</td><td>34</td></tr><tr><td>2.3.4</td><td>Digital signatures</td><td>36</td></tr><tr><td>2.4</td><td>Homomorphic encryption</td><td>37</td></tr><tr><td>2.5</td><td>Post-Quantum cryptography</td><td>38</td></tr><tr><td>2.6</td><td>Zero-knowledge proofs</td><td>39</td></tr><tr><td>2.7</td><td>Smooth Projective Hash Functions</td><td>40</td></tr><tr><td>2.8</td><td>Secure multi-party computation</td><td>41</td></tr><tr><td>2.8.1</td><td>Oblivious Transfers</td><td>42</td></tr><tr><td>2.8.2</td><td>Garbled Circuits</td><td>45</td></tr><tr><td>2.9</td><td>Universal Composability</td><td>51</td></tr><tr><td>2.10</td><td>Decision forest</td><td>52</td></tr></table>
## 2.1 Complexity definitions

We first define the notion of negligibility. Roughly speaking, negligibility represents the idea that a function is close enough to zero to regard it as it is. In cryptography, negligibility is often associated to probabilities. Hence, a negligible probability is a probability smaller than the inverse of any polynomial.

**Definition 2.1 - Negligeability**

A function $\varepsilon: \mathbb{N} \to \mathbb{R}$ is negligible if for every positive integer $c$, there exists an integer $N_c$ such that for all $n > N_c$, $|\varepsilon(x) - \frac{1}{x^c}|$

Similarly, we say an event $F$ happens with overwhelming probability if the probability of $\bar{F}$ (opposite event of $F$) is negligible. The notion of negligibility allows us to define the notion of computational indistinguishability.

**Definition 2.2 - Computational Indistinguishability**

Let $X = \{Xn\}_{n \in \mathbb{N}}$ and $Y = \{Yn\}_{n \in \mathbb{N}}$ be two distribution ensembles. $X$ and $Y$ are computationally indistinguishable if

$$|\Pr[A(X_n) = 1] - \Pr[A(Y_n) = 1]| < \varepsilon(n)$$

for all probabilistic polynomial time adversary $A$, where $\varepsilon$ is a negligible function.

In other words, computational indistinguishability reflects the idea that it would require an unreasonable amount of time and computation resources to distinguish those distributions. The allowed computation resources given to an adversary to cryptanalyse a cryptosystem are represented by a security parameter denoted $1^\kappa$, used to set up protocols.

## 2.2 Symmetric cryptography

The oldest cryptosystems require both parties to use the same key to encrypt and decrypt a message. This symmetric process of such cryptosystems gave its name to the global family of cryptographic primitives where a unique key is used by both parties implied in the primitive: the *Symmetric Cryptography*. We now define the most popular of those primitives, beginning with the symmetric encryption.

### 2.2.1 Symmetric encryption

Symmetric Encryption, also called Secret-Key Encryption, aims to provide confidentiality. Alice uses a secret key to encrypt her message, and then Bob uses the same key to decrypt. Some symmetric encryption schemes take as input an *Initialization Vector* that provides randomness and avoids deterministic encryption.
## Definition 2.3 - Symmetric Encryption

A symmetric encryption scheme $Π$ with messages in $\mathcal{M}$ and keys in $\mathcal{K}$ is a tuple $Π = (\text{Setup}, \text{KGen}, \text{Enc}, \text{Dec})$ of probabilistic polynomial time algorithms:

- $\text{Setup}(1^\kappa)$ generates global parameters $\text{param}$ based on the security parameter $1^\kappa$. Returns $\text{param}$.

- $\text{KGen}(\text{param})$ generates a symmetric key $\text{sk} \in \mathcal{K}$. Returns $\text{sk}$.

- $\text{Enc}(\text{sk}, \text{IV}, m)$ computes an encryption $c$ of $m \in \mathcal{M}$ using the key $\text{sk}$ and a possibly empty Initialization Vector IV. Returns $c$.

- $\text{Dec}(\text{sk}, \text{IV}, c)$ computes a decryption $m$ of $c$ using the key $\text{sk}$ and a possibly empty Initialization Vector IV. Returns $m$.

We expect the decryption correctness property: $\text{Dec}(\text{sk}, \text{IV}, \text{Enc}(\text{sk}, \text{IV}, m)) = m$.

As said previously, the main goal of symmetric encryption is to provide confidentiality. Secretly, the probability for an adversary to extract information from a ciphertext he intercepts should be negligible. The confidentiality security level is represented by the notion of *Indistinguishability under Chosen Plaintext Attacks*.

**Indistinguishability Under Chosen Plaintext Attack.** The indistinguishability game varies depending on the need or not of an Initialization Vector. We first describe the game when no IV is required, then we describe the game when IV are required.

**Without IV.** Let $\mathcal{A}$ be an adversary with access to an encryption oracle encrypting any message of his choice. After querying a polynomially bounded number of times the oracle, the adversary chooses and sends two messages $m_0$ and $m_1$, of its choice, to the challenger who samples $b \leftarrow \{0, 1\}$ and encrypts $c \leftarrow \text{Enc}(\text{sk}, m_b)$. Afterward, $c$ is sent to the adversary who, after new polynomially bounded queries to the oracle, makes a guess $b' \in \{0, 1\}$. The adversary wins if $b' = b$ and if the messages $m_0$ or $m_1$ are not in the list $\mathcal{Q}$ of messages queried to the encryption oracle. If the adversary can not guess $b$ with more than a negligible probability, $\Pi$ provides indistinguishability under chosen plaintext attacks. In other words, $\Pi$ is IND-CPA secure.

## Definition 2.4 - Ciphertext indistinguishability - Without IV

Given an encryption scheme $Π = (\text{Setup}, \text{KGen}, \text{Enc}, \text{Dec})$, the advantage $\text{Adv}_Π^{\text{IND-CPA}}(\mathcal{A})$ of the adversary $\mathcal{A}$ making polynomially-many queries to an encryption oracle in violating the IND-CPA security of $Π$ is given by

$$|\Pr[\text{Exp}_Π^{\text{IND-CPA}-1}(\mathcal{A}) = 1] - \Pr[\text{Exp}_Π^{\text{IND-CPA}-0}(\mathcal{A}) = 1]|$$

and the advantage function as:

$$\text{Adv}_Π^{\text{IND-CPA}}(t) = \max_{\mathcal{A}} (\text{Adv}_Π^{\text{IND-CPA}}(\mathcal{A}))$$

over all $\mathcal{A}$ with time-complexity at most $t$.

$$\text{Exp}_Π^{\text{IND-CPA}-b}(\mathcal{A})$$

1. $\text{param} \leftarrow \text{Setup}(1^\kappa)$

2. $\text{sk} \leftarrow \text{KGen}(\text{param})$

3. $(m_0, m_1) \leftarrow \mathcal{A}^{\text{Enc}(\text{sk}, \cdot)}(\cdot)$

4. $c \leftarrow \text{Enc}(\text{sk}, m_b)$

5. $b', \leftarrow \mathcal{A}^{\text{Enc}(\text{sk}, \cdot)}(c, m_0, m_1)$

6. **if** $m_0 \in \mathcal{Q}$ **or** $m_1 \in \mathcal{Q}$:

7. **return 0**

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

Hence, $Π$ provides IND-CPA security if $\text{Adv}_Π^{\text{IND-CPA}}(t)$ is negligible.
**On perfect secrecy.** Ideally, one may expect $Adv_{\mathbb{H}}^{\text{IND-CPA}}(t)$ to be null. In the definition given above of symmetric encryption, the key is generated before encryption, independently of the message $m$. Indeed, the key is generated according to the security parameter $1^{\kappa}$, which defines the key length.

Therefore, the size of the space of keys $\mathcal{K}$ is smaller or equal to the size of the space of messages $\mathcal{M}$.

This leads the adversary advantage to be non-null.

Nonetheless, as we use it later, we introduce now the *One-Time Pad* encryption, deviating from the above definition as the key is generated according to the length of the message to be encrypted.

**Definition 2.5 - One-Time Pad (OTP)**

Given a message $m \in \{0, 1\}^k$, the One-Time Pad encryption scheme consists in a tuple $(\text{KGen}, \text{Enc}, \text{Dec})$:

- $\text{KGen}(k)$: Given the length $k$ of the message to encrypt, samples $\text{sk} \leftarrow \{0, 1\}^k$. Return $\text{sk}$;

- $\text{Enc}(m, \text{sk})$: computes $c \leftarrow m \oplus \text{sk}$. Returns $c$;

- $\text{Dec}(c, \text{sk})$: computes $m \leftarrow c \oplus \text{sk}$. Returns $m$.

For a random key $\text{sk}$, a ciphertext $c$ can not leak any information about the plaintext as it could be an encryption of any $m \in \{0, 1\}^k$. One may also interpret the One-Time Pad encryption as a bitwise randomization. Hence, the One-Time Pad encryption provides perfect secrecy. However, this perfect secrecy is only valid if the key $\text{sk}$ is used once. Indeed, consider two ciphertexts $c_1 \leftarrow \text{Enc}(\text{sk}, m_1) = m_1 \oplus \text{sk}$ and $c_2 \leftarrow \text{Enc}(\text{sk}, m_2) \oplus \text{sk}$. Computing $c_1 \oplus c_2 = (m_1 \oplus \text{sk}) \oplus (m_1 \oplus \text{sk}) = m_1 \oplus m_2$ reveals which bits of $m_1$ and $m_2$ are equals, and if the message is long enough, a frequency analysis can reveal the messages $m_1$ and $m_2$.

**With IV.** When the encryption scheme uses an Initialization Vector, the adversary queries an encryption oracle. This oracle, when queried with a pair $(m, \text{IV})$ returns an encryption of $m$ with Initialisation Vector IV, with the property that an IV can be queried to the oracle only once for a given message. Moreover, when sending a pair of messages $(m_0, m_1)$ to the challenger, the adversary also sends an Initialization Vector IV and the challenger computes $\text{Enc}(\text{sk}, \text{IV}, m_b)$. Similarly to the case without IV, the adversary wins if $b' = b$ and if IV is not in the list $\mathcal{Q}$ of the Initialization Vectors queried to the encryption oracle. Note that messages queried do not need to be stored in $\mathcal{Q}$.

We then define the appropriate IND-CCA definition:
Definition 2.6 - Ciphertext indistinguishability - With IV

Given an encryption scheme $Π = (Setup, KGen, Enc, Dec)$ using Initialization Vectors, the advantage $Adv_{Π}^{IND-CPA}(\mathcal{A})$ of the adversary $\mathcal{A}$ making a polynomial number of queries to an encryption oracle in violating the IND-CPA security of $Π$ is given by

$$| \Pr[\mathbf{Exp}_{\Pi}^{IND-CPA-1}(\mathcal{A}) = 1] - \Pr[\mathbf{Exp}_{\Pi}^{IND-CPA-0}(\mathcal{A}) = 1] |$$

and the advantage function $Adv_{Π}^{IND-CPA}(t)$ as:

$$max_{\mathcal{A}}(Adv_{\Pi}^{IND-CPA}(\mathcal{A}))$$

over all $\mathcal{A}$ with time-complexity at most $t$.

$$\mathbf{Exp}_{\Pi}^{IND-CPA-b}(\mathcal{A})$$

1. $\mathbf{param} \leftarrow \text{Setup}(1^{\kappa})$

2. $\mathbf{sk} \leftarrow \mathbf{KGen}(\mathbf{param})$

3. $(m_0, m_1, \text{IV}) \leftarrow \mathcal{A}^{\text{Enc}(\mathbf{sk}, \cdot \cdot \cdot)}(\cdot)$

4. $\mathbf{c} \leftarrow \mathbf{Enc}(\mathbf{sk}, \text{IV}, m_b)$

5. $\mathbf{b}' \leftarrow \mathcal{A}^{\text{Enc}(\mathbf{sk}, \cdot \cdot \cdot)}(\mathbf{c}, m_0, m_1)$

6. **if** $\text{IV} \in \mathcal{Q}$:

7. **return** 0

8. **else return** $\mathbf{b} = \mathbf{b}'$

Hence, $Π$ provides IND-CPA security if $Adv_{Π}^{IND-CPA}(t)$ is negligible.

In addition to confidentiality, cryptography may also be used to provide integrity and authentication. If Alice wants to give Bob the possibility to ensure the message he receives has not been altered by an eavesdropper, he may use Message Authentication Codes (MAC).

### 2.2.2 Message authentication code (MAC)

When using Message Authentication Codes, Alice generates a value named *tag*, using a key $k$ she shares with Bob. As the key is secret, an eavesdropper is supposed not to be able to compute a MAC. Hence, when Bob verifies the validity of the tag, he ensures the message has not been altered (*integrity*) and was indeed sent by Alice (*authentication*). We denote by MAC the function computing the Message Authentication Code, and by tag the output of MAC.

Definition 2.7 - Message Authentication Code

A message authentication code MAC with messages in $\mathcal{M}$ and keys in $\mathcal{K}$ is a tuple $(\mathbf{KGen}, \mathbf{MAC}, \mathbf{Vf})$ of probabilistic polynomial-time algorithms:

- $\mathbf{KGen}(1^n)$ samples a key $k \in \mathcal{K}$. Returns $k$.

- $\mathbf{MAC}(k, m)$ given a message $m \in \mathcal{M}$ and $\mathbf{sk}$, computes the tag $\tau$ associated to $m$. Returns $\tau$.

- $\mathbf{Vf}(k, m, \tau)$ verifies if $\tau = \mathbf{MAC}(k, m)$. Returns a bit $b$ set to 1 if the verification succeeds and 0 otherwise.

We expect the verification correctness property : $\mathbf{Vf}(k, m, \mathbf{MAC}(k, m)) = 1$. As MAC are used to provide integrity, we define a proper security definition of what integrity is. Someone else than Alice should only have a negligible probability to pass the verification test, i.e. forge a valid tag. Hence, we introduce the notion of Existential Unforgeability under Chosen Messages Attack (EUF-CMA).

**Existential Unforgeability under Chosen Messages Attack (EUF-CMA).** Let $k \leftarrow \mathbf{KGen}(1^{\kappa})$ and $\mathcal{A}$ be an adversary with access to an oracle knowing the key $k$ and able to compute the tag of any message of its choice. $\mathcal{A}$ wins if after a polynomially bounded number of queries, he can
generate a tag $\tau$ for a message $m$ not in the list $\mathcal{D}$ of previously queried messages to the oracle, such that $Vf(k, m, \tau) = 1$.

**Definition 2.8 - Existential Unforgeability under Chosen Messages Attack (EUF-CMA)**

Given a MAC scheme MAC = (KGen, Enc, Dec), the advantage of the adversary $\mathcal{A}$ making polynomially-many queries to a MAC oracle in violating the EUF-CMA security of MAC is given by:

$$ \mathrm{Adv}_{\mathrm{MAC}}^{\mathrm{EUF-CMA}}(\mathcal{A}) = \Pr[\mathbf{Exp}_{\mathrm{MAC}}^{\mathrm{EUF-CMA}}(\mathcal{A}) = 1] $$

and the advantage function $\mathrm{Adv}_{\mathrm{MAC}}^{\mathrm{EUF-CMA}}(t)$ as

$$ \mathrm{Adv}_{\mathrm{MAC}}^{\mathrm{EUF-CMA}}(t) = \max_{\mathcal{A}} (\mathrm{Adv}_{\mathrm{MAC}}^{\mathrm{EUF-CMA}}(\mathcal{A})) $$

over all $\mathcal{A}$ with time-complexity at most $t$.

Hence, MAC provides EUF-CMA security if $\mathrm{Adv}_{\mathrm{MAC}}^{\mathrm{EUF-CMA}}(t)$ is negligible.

$$ \frac{\mathbf{Exp}_{\mathrm{MAC}}^{\mathrm{EUF-CMA}}(\mathcal{A}, 1^{\kappa})}{\begin{array}{@{}l@{}} 1. \ k \leftarrow \mathcal{K}\mathrm{Gen}(1^{\kappa}) \\ 2. \ (m, \tau) \leftarrow \mathcal{A}^{\mathrm{MAC}(k, \cdot)}() \\ 3. \ \mathbf{if} \ m \in \mathcal{D} : \mathbf{return} \ 0 \\ 4. \ \mathbf{else} \ \mathbf{return} \ Vf(k, m, \tau) \end{array}} $$

It is possible to combine both Symmetric Encryption and MAC under a single primitive, called *Authenticated Encryption*.

### 2.2.3 Authenticated encryption (with associated data)

Authenticated Encryption combines the confidentiality of a Symmetric Encryption and the authentication and integrity of a Message Authentication Code. In authenticated encryption, the encryption process generates the ciphertext and the associated tag, while the decryption returns either the plaintext, or an error if the authentication fails.

There exists three approaches to combine the MAC and the encryption process: Encrypt-then-MAC, Encrypt-and-MAC, MAC-then-Encrypt. In this thesis, we will only meet the Mac-then-Encrypt approach. Hence, we use Authenticated Encryption to denote MtE-Authenticated Encryption When receiving an authenticated encryption, Bob first decrypts the ciphertext and verifies the tag validity. If the verification fails, Bob aborts. A variant of Authenticated Encryption, *Authenticated Encryption with Associated Data (AEAD)* allows Alice to send authenticated plain data to Bob. When the additional data contains some information about the context of the protocol, this prevents a reuse of the ciphertext by an attacker.

**Definition 2.9 - Authenticated encryption**

An authenticated encryption (with possibly empty Associated Data $d$) scheme (with MtE approach) $\Pi$ with messages in $\mathcal{M}$ and keys in $\mathcal{K}$ is a tuple $\Pi = (\mathrm{Setup}, \mathrm{KGen}, \mathrm{Enc}, \mathrm{Dec})$ of probabilistic polynomial time algorithms:

- $\mathrm{Setup}(1^\kappa)$ generates global cryptosystem parameter $\mathrm{param}$ based on the security parameter. Returns $\mathrm{param}$

- $\mathrm{KGen}(\mathrm{param})$ generates a symmetric encryption key $\mathrm{sk}$. Returns $\mathrm{sk}$.

- $\mathrm{Enc}(\mathrm{sk}, \mathrm{IV}, m, d)$ computes a tag $t \leftarrow \mathrm{MAC}(\mathrm{sk}, m \parallel d)$ and next, an encryption $c$ of $m \parallel t$ using the key $\mathrm{sk}$ and potentially an Initialization Vector IV. Returns $C = (c \parallel d)$.

- $\mathrm{Dec}(\mathrm{sk}, \mathrm{IV}, C)$ parses $C$ as $(c \parallel d)$ and obtains $m \parallel t$ by decrypting $c$ using $\mathrm{sk}$ and IV. Returns $m \parallel d$ if $Vf(\mathrm{sk}, m \parallel d, t) \neq 1$, and aborts otherwise.

We expect the decryption correctness property : $\mathrm{Dec}(\mathrm{sk}, \mathrm{IV}, \mathrm{Enc}(\mathrm{sk}, \mathrm{IV}, m, d)) = m \parallel d$. The
correctness of the MAC is implicit as the decryption process terminates only if the MAC verification returns 1. Formally, the verification correctness property ensures $\text{Dec}(\text{sk}, \text{IV}, \text{Enc}(\text{sk}, \text{IV}, m, d)) \neq \bot$.

Another important and widely used symmetric primitive providing data integrity is hash functions.

### 2.2.4 Hash functions

A hash function $H$ is a one-way compression function. Namely, given an input $m$ of arbitrary length, it must be easy to compute $h \leftarrow H(m)$ of fixed length, while given $h$, it must be hard to compute $m$.

**Definition 2.10 - Hash Functions**

A hash function with output length $l_H$ is a polynomial-time algorithm $H$ such that:

- $H(m)$: On input with an arbitrary length string $m \in \{0, 1\}^*$, output a digest $h \in \{0, 1\}^{l_H}$

With hash functions, the verification consists in recalculating the same hash on the same string. A use of hash functions is file integrity checking, for instance, before digitally signing them. By computing a hash on the file to be signed, it ensures the signature can not be used for other files. Indeed, an adversary cannot computationally generate a file with the same hash value, and can not generate two different files with the same hash value. More precisely, from a hash function we expect the following properties:

- *Pre-image resistance*: Given a hash value $h$, an adversary should not be able to find $m$ such that $H(m) = h$ with overwhelming probability.

- *Second pre-image resistance*: Given a message $m_1$, an adversary should not be able to find $m_2$ such that $H(m_1) = H(m_2)$ with overwhelming probability.

- *Collision resistance*: An adversary should not be able to find two messages $m_1, m_2$ such that $H(m_1) = H(m_2)$. Due to the birthday attack, this implies a digest size at least twice as long as the required bit-security with overwhelming probability.

In cryptography, we expect an extra pseudo-random property. Indeed, if we set $\tilde{m}$ as $m$ with a single random bit flip, we expect $(m, H(\tilde{m}))$ to be indistinguishable from $(m, h \leftarrow \{0, 1\}^{l_{\text{hash}}})$. In the rest of the document, hash functions implicitly are *cryptographic hash functions*.

### 2.2.5 Random oracle model

When hash functions are modelized using a random oracle returning perfectly random digest for security proofs, we say the proof is made in the *Random Oracle Model* [BR93].

**Definition 2.11 - Random Oracle Model**

If a protocol is proven in the Random Oracle Model, calls to a hash function $H$ are replaced with calls to an oracle $\mathcal{O}_H$. When calling $H$ on $m$, the oracle acts as follows

- If $m$ has never been queried before, $\mathcal{O}_H$ generates $s_m \leftarrow \{0, 1\}^{l_H}$, returns $s_m$ and stores $[m, s_m]$

- If $m$ has ever been queried, $\mathcal{O}_H$ returns $s_m$
### 2.2.6 Pseudorandom functions

Pseudorandom functions (PRF) take as input a random key and are used to generate output computationally indistinguishable from truly random output.

**Definition 2.12 - Pseudorandom Function (PRF)**

Let $F$ be a function with input a random key $k \in \{0, 1\}^s$ and some input $x \in \{0, 1\}^m$. The advantage of the adversary $\mathcal{A}$ making polynomially-many queries to the oracle in breaking the randomness of $F$ is given by:

$$ \mathrm{Adv}_F^{\mathrm{PRF}}(\mathcal{A}) = |\mathrm{Pr}[\mathrm{Exp}_F^{\mathrm{PRF}-1}(\mathcal{A}) = 1] - \mathrm{Pr}[\mathrm{Exp}_F^{\mathrm{PRF}-0}(\mathcal{A}) = 1]| $$

and the advantage function $\mathrm{Adv}_F^{\mathrm{PRF}}(t)$ as

$$ \mathrm{Adv}_F^{\mathrm{PRF}}(t) = \max_{\mathcal{A}}(\mathrm{Adv}_F^{\mathrm{PRF}}(\mathcal{A})) $$

over all $\mathcal{A}$ with time-complexity at most $t$.

Hence, $F$ is a pseudorandom function if $\mathrm{Adv}_F^{\mathrm{PRF}}(t)$ is negligible.

$$ \mathrm{Exp}_F^{\mathrm{PRF}-b}(\mathcal{A}, 1^\kappa) $$

1. $k \leftarrow \{0, 1\}^\kappa$

2. $b' \leftarrow \mathcal{A}^{F_b(k, \cdot)}$

3. **return** $b = b'$

Oracles details

$$ F_1(k, x) = F(k, x) $$

$$ F_2(k, x) \leftarrow \{0, 1\}^m $$

Pseudorandom functions are a good option to build MACs. Under the properties of a PRF, we reach the EUF-CMA property of a MAC. Moreover, when the PRF is implemented with a random oracle, the EUF-CMA property is statistical.

## 2.3 Asymmetric cryptography

The main drawback of the symmetric encryption is the fact the key has to be previously shared between Alice and Bob to securely communicate. To overcome this problem, two ideas are introduced by Withfield Diffie and Martin Hellman in their seminal article [DH76]. The first one is to securely share a key over an untrusted channel, and the second one is to design cryptosystems where no shared key is required. In [DH76], only the first idea, latter called Diffie-Hellman key exchange, is instantiated, while the second idea waited one more year to be concretized by Rivest, Shamir and Adleman [RSA78], leading to the RSA cryptosystem. Both those solutions rely on mathematical problems and security assumptions we define hereunder.

### 2.3.1 Discrete Logarithm problem and Diffie-Hellman assumptions

We begin by introducing the Discrete Logarithm problem.

**Definition 2.13 - Discrete Logarithm (DL)**

Let $\mathcal{G}$ be a cyclic group of order $p$ with generator $g$. Given $h \leftarrow \mathcal{G}$, the discrete logarithm problem for the group $\mathcal{G}$ consists in finding $x \in \mathbb{Z}_p$ such that $g^x = h$

We now introduce assumptions related to the Discrete Logarithm Problem.
## Definition 2.14 - Computational Diffie-Hellman (CDH)

Let $\mathbb{G}$ be a cyclic group of order $p$. The Computational Diffie-Hellman assumption states that given a tuple $(g, g^u, g^v)$ where $u$ and $v$ were drawn at random from $\mathbb{Z}_p$, it is hard to compute $g^{uv}$. More precisely the advantage of the adversary $\mathcal{A}$ in violating the Computational Diffie-Hellman assumption in $\mathbb{G}$, is given by:

$$ \mathrm{Adv}_{\mathbb{G}}^{\mathrm{CDH}}(\mathcal{A}) = \Pr[\mathrm{Exp}_{\mathbb{G}}^{\mathrm{CDH}}(\mathcal{A}) = 1] $$

and the advantage function $\mathrm{Adv}_{\mathbb{G}}^{\mathrm{CDH}}(t)$ as

$$ \mathrm{Adv}_{\mathbb{G}}^{\mathrm{CDH}}(t) = \max_{\mathcal{A}} (\mathrm{Adv}_{\mathbb{G}}^{\mathrm{CDH}}(\mathcal{A})) $$

over all $\mathcal{A}$ with time-complexity at most $t$.

Hence, the CDH assumption is hard in $\mathbb{G}$ if $\mathrm{Adv}_{\mathbb{G}}^{\mathrm{CDH}}(t)$ is negligible.

$$ \frac{\mathrm{Exp}_{\mathbb{G}}^{\mathrm{CDH}}(\mathcal{A})}{\mathbb{Z}_p} $$

1. $u, v \leftarrow \mathbb{Z}_p$

2. $U \leftarrow g^u, V \leftarrow g^v$

3. $Z \leftarrow \mathcal{A}(U, V)$

4. **return** $Z = g^{uv}$

From now, we denote by DH-tuple a tuple $(g, g^u, g^v, g^{u \cdot v})$.

The second assumption considers the ability to decide if a given tuple is a DH-tuple. We then introduce the Decisional Diffie-Hellman.

## Definition 2.15 - Decisional Diffie-Hellman (DDH)

Let $\mathbb{G}$ be a cyclic group of order $p$. The Decisional Diffie-Hellman assumption states that given $g^u$ and $g^v$, where $u, v$ were drawn at random from $\mathbb{Z}_p$, the value $g^{uv}$ is indistinguishable from $g^r$, $r \leftarrow \mathbb{Z}_p$. More precisely the advantage of the adversary $\mathcal{A}$ in violating the Decisional Diffie-Hellman assumption in $\mathbb{G}$, is given by:

$$ \mathrm{Adv}_{\mathbb{G}}^{\mathrm{DDH}}(\mathcal{A}) = \left| \Pr[\mathrm{Exp}_{\mathbb{G}}^{\mathrm{DDH}-1}(\mathcal{A}) = 1] - \Pr[\mathrm{Exp}_{\mathbb{G}}^{\mathrm{DDH}-0}(\mathcal{A}) = 1] \right| $$

and the advantage function $\mathrm{Adv}_{\mathbb{G}}^{\mathrm{DDH}}(t)$ as

$$ \mathrm{Adv}_{\mathbb{G}}^{\mathrm{DDH}}(t) = \max_{\mathcal{A}} (\mathrm{Adv}_{\mathbb{G}}^{\mathrm{DDH}}(\mathcal{A})) $$

over all $\mathcal{A}$ with time-complexity at most $t$.

Hence, the DDH assumption is hard in $\mathbb{G}$ if $\mathrm{Adv}_{\mathbb{G}}^{\mathrm{DDH}}(t)$ is negligible.

$$ \frac{\mathrm{Exp}_{\mathbb{G}}^{\mathrm{DDH}-b}(\mathcal{A})}{\mathbb{Z}_p} $$

1. $u, v, r \leftarrow \mathbb{Z}_p$

2. $U \leftarrow g^u, V \leftarrow g^v$

3. $W_0 \leftarrow g^{uv}, W_1 \leftarrow g^r$

4. $b' \leftarrow \mathcal{A}(U, V, W_b)$

5. **return** $b = b'$

A last stronger assumption lets the CDH-adversary make polynomially bounded queries to an oracle that can decide if a given tuple (other than the one instantiated in the problem) $(g, g^a, g^b, g^c)$ is a DH-tuple or not.
### Definition 2.16 - Gap Diffie-Hellman (GDH)

Let $\mathbb{G}$ be a cyclic group. The Gap Diffie-Hellman assumption states that given $g^u$ and $g^v$, where $u, v$ were drawn at random from $\mathbb{Z}_p$, the value $g^{uv}$ is hard to compute, even when the adversary has access to a DDH oracle returning 1 if a tuple $(g, g^a, g^b, g^c)$ is a Diffie-Hellman tuple, and 0 otherwise. More precisely the advantage of the adversary $\mathcal{A}$ in violating the Computational Diffie-Hellman assumption in $\mathbb{G}$ making polynomially-many queries to the DDH oracle is given by:

$$ \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\mathcal{A}) = \Pr[\mathbf{Exp}_{\mathbb{G}}^{\mathrm{GDH}}(\mathcal{A}) = 1] $$

and the advantage function $\mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(t)$ as

$$ \mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(t) = \max_{\mathcal{A}} (\mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(\mathcal{A})) $$

over all $\mathcal{A}$ with time-complexity at most $t$.

Hence, the GDH assumption is hard in $\mathbb{G}$ if $\mathrm{Adv}_{\mathbb{G}}^{\mathrm{GDH}}(t)$ is negligible.

$$ \begin{array}{l} \mathbf{Exp}_{\mathbb{G}}^{\mathrm{GDH}}(\mathcal{A}) \\ \quad 1. \quad u, v \leftarrow \mathbb{Z}_p \\ \quad 2. \quad U \leftarrow g^u, V \leftarrow g^v \\ \quad 3. \quad Z \leftarrow \mathcal{A}^{\mathrm{DDH}(\cdot, \cdot, \cdot)}(U, V) \\ \quad 4. \quad \mathbf{return} \ Z = g^{uv} \end{array} $$

## 2.3.2 Factorization problems

Another widely use problem in public key encryption is the Factorization Problem.

### Definition 2.17 - Factorisation Problem

Let $N$ be a composite number. The factorization problem consists in finding one factor of $N$.

In most of the cases this problem is easy. However, when $N$ is known to be a product of two large prime numbers ($N$ is called semiprime), the factorization problem becomes hard. Another problem relying on the factorization problem is the RSA problem.

### Definition 2.18 - RSA problem

Let $N = pq$ be a product of two large numbers and $2 < e < N$ such that $e$ and $\Phi(N) = (p - 1)(q - 1)$ are coprime. Given $c \in \mathbb{Z}_n$, the RSA problem consists in finding $m$ such that $m^e = c \mod N$

## 2.3.3 Public-key encryption

A public-key cryptosystem, or asymmetric cryptosystem, generates a secret key sk, and a public key pk associated to this secret key. The public key is used for encryption, and, as it is public, should not reveal any information about sk, the secret key used for decryption.

### Definition 2.19 - Public-Key Encryption

A public-key encryption scheme $\Gamma$ with messages in $\mathcal{M}$ and keys in $\mathcal{K}$ is a tuple of probabilistic polynomial-time algorithms $\Gamma = (\mathrm{Setup}, \mathrm{KGen}, \mathrm{Enc}, \mathrm{Dec})$ such that:

- $\mathrm{Setup}(1^\kappa)$ generates global cryptosystem parameter $\mathrm{param}$ based on the security parameter. Returns $\mathrm{param}$.

- $\mathrm{KGen}(\mathrm{param})$ generates a secret key sk and its associated public key pk. Returns $(\mathrm{pk}, \mathrm{sk})$.

- $\mathrm{Enc}(\mathrm{pk}, m)$ computes an encryption $c$ of $m \in \mathcal{M}$ using the key pk. Returns $c$.

- $\mathrm{Dec}(\mathrm{sk}, c)$ computes a decryption $m$ of $c$ using the key sk. Returns $m$.
We expect the decryption correctness property : With $\mathit{param} \leftarrow \mathit{Setup}(1^{\kappa})$ and $(\mathit{pk}, \mathit{sk}) \leftarrow \mathit{KGen}(\mathit{param})$, $\mathit{Dec}(\mathit{sk}, \mathit{Enc}(\mathit{pk}, m)) = m$. A single public key can therefore be used by as many people that wish to use it. This reduces the amount of required key in multiparty communication setting. Hence, consider a class of $n$ students, where each student should be able to privately send a message to any other student. When using symmetric encryption, one key is needed by pair of students, i.e. $n(n+1)/2$ keys, while in the context of asymmetric encryption, only $2n$ keys, one public and one private per student, are required. However, in contrast to symmetric cryptography that is fast, asymmetric cryptography is slow due to more complex computations.

Analogously to the symmetric encryption, an asymmetric encryption scheme $\Gamma$ may provide ciphertext indistinguishability under chosen plaintext attacks.

**Definition 2.20 - Ciphertext indistinguishability under Chosen Plaintext Attacks - IND-CPA**

Given an encryption scheme $\Gamma = (\mathit{Setup}, \mathit{KGen}, \mathit{Enc}, \mathit{Dec})$, the advantage $\mathit{Adv}_{\Gamma}^{\mathit{IND-CPA}}(\mathcal{A})$ of the adversary in violating the IND-CPA security of $\Gamma$ is given by

$$| \Pr[\mathbf{Exp}_{\Gamma}^{\mathit{IND-CPA}-1}(\mathcal{A}) = 1] - \Pr[\mathbf{Exp}_{\Gamma}^{\mathit{IND-CPA}-0}(\mathcal{A}) = 1] |$$

and the advantage function $\mathit{Adv}_{\Gamma}^{\mathit{IND-CPA}}(t)$ as

$$\mathit{Adv}_{\Gamma}^{\mathit{IND-CPA}}(t) = \max_{\mathcal{A}}(\mathit{Adv}_{\Gamma}^{\mathit{IND-CPA}}(\mathcal{A}))$$

over all $\mathcal{A}$ with time-complexity at most $t$.

Hence, $\Gamma$ provides IND-CPA security if $\mathit{Adv}_{\Gamma}^{\mathit{IND-CPA}}(t)$ is negligible.

$$\mathbf{Exp}_{\Gamma}^{\mathit{IND-CPA}-b}(\mathcal{A})$$

1. $\mathit{param} \leftarrow \mathit{Setup}(1^{\kappa})$

2. $(\mathit{pk}, \mathit{sk}) \leftarrow \mathcal{S} \mathit{KGen}(\mathit{param})$

3. $(m_0, m_1) \leftarrow \mathcal{A}(\mathit{pk})$

4. $c \leftarrow \mathcal{S} \mathit{Enc}(\mathit{pk}, m_b)$

5. $b' \leftarrow \mathcal{A}(c, m_0, m_1)$

6. **return** $b = b'$

In addition to the IND-CPA property, a public-key encryption scheme may provide INDistinguishability under Chosen Ciphertext Attack.

**Indistinguishability Under Chosen Ciphertexts Attack.** Two notions of such indistinguishability are widely known : IND-CCA1 and IND-CCA2. To better understand the nuance between these two notions, consider the following indistinguishability games.

The challenger generates a pair of keys $(\mathit{pk}, \mathit{sk})$. Then the adversary has access to a decryption oracle, which given a ciphertext, returns its decryption. After a polynomially bounded number of queries, the adversary sends two messages $m_0, m_1$ of his choice to the challenger. The challenger samples $b \in \{0, 1\}$ and returns an encryption $c$ of $m_b$ to the adversary. In the IND-CCA2 game, the adversary is given a new polynomially bounded access to the decryption oracle, while in the IND-CCA1 game, no access to the decryption oracle is given before the adversary makes a guess $b'$ corresponding to the message $m_b$ he thinks $c$ is an encryption of, based on $\mathit{pk}, c, m_0$ and $m_1$. If the adversary queries $\mathcal{D}$ with the challenge $c$, the game will return 0 and queries from the adversary are no longer answered. The adversary therefore wins if $b = b'$ and the challenge $c$ is not in the list $\mathcal{D}$ of ciphertexts queried to the decryption oracle.
## Definition 2.21 - Ciphertext indistinguishability under Chosen Ciphertexts Attacks - IND-CCA

Let $\Gamma = (\text{Setup}, \text{KGen}, \text{Enc}, \text{Dec})$ be an asymmetrical encryption scheme. The advantage $\text{Adv}_{\Gamma}^{\text{IND-CCA}\mu}(\mathcal{A})$ of the adversary $\mathcal{A}$ in violating the IND-CCA$\mu$ security of $\Gamma$, $\mu \in \{1, 2\}$, making polynomially-many global queries to the decryption oracle, is given by:

$$| \Pr[\text{Exp}_{\Gamma}^{\text{IND-CCA}\mu-1}(\mathcal{A}) = 1] - \Pr[\text{Exp}_{\Gamma}^{\text{IND-CCA}\mu-0}(\mathcal{A}) = 1]|$$

and the advantage function $\text{Adv}_{\Gamma}^{\text{IND-CCA}\mu}(t)$ as

$$\text{Adv}_{\Gamma}^{\text{IND-CCA}\mu}(t) = \max_{\mathcal{A}}(\text{Adv}_{\Gamma}^{\text{IND-CCA}\mu}(\mathcal{A}))$$

over all $\mathcal{A}$ with time-complexity at most $t$.

Hence, $\Gamma$ provides IND-CCA$\mu$ security if $\text{Adv}_{\Gamma}^{\text{IND-CCA}\mu}(t)$ is negligible.

$$\text{Exp}_{\Gamma}^{\text{IND-CCA}\mu-b}(\mathcal{A}, 1^{\kappa})$$

1. $\text{param} \leftarrow \text{Setup}(1^{\kappa})$

2. $(\text{pk}, \text{sk}) \leftarrow \$ \text{KGen}(\text{param})$

3. $(m_0, m_1) \leftarrow \mathcal{A}^{\text{Dec}(\text{sk}, \cdot)}(\text{pk})$

4. $c \leftarrow \$ \text{Enc}(\text{pk}, m_b)$

5. $b' \leftarrow \mathcal{A}^{\text{Dec}_{\mu}(\text{sk}, \cdot)}(c, m_0, m_1, \text{pk})$

6. **if** $c \in \mathcal{Q}: \text{return } 0$

7. **else return** $b = b'$

Oracles Description

$$\text{Dec}_1(\text{sk}, \cdot) = \emptyset$$

$$\text{Dec}_2(\text{sk}, \cdot) = \text{Dec}(\text{sk}, \cdot)$$

In addition to asymmetric encryption, the use of a different key for the encryption and the decryption led to a new primitive, digital signatures.

### 2.3.4 Digital signatures

The idea behind digital signatures is the same as the idea behind handwritten signatures: they aim to provide integrity and authentication. In addition, a signature scheme may provide non-repudiation. Signatures rely on the fact that only the owner of a secret key is supposed to know it. Hence, when signing, Alice uses her secret key to compute a tag, that Bob, and anyone can verify using Alice's public key.

#### Definition 2.22 - Digital Signatures

A Digital Signature scheme $\Sigma$ with messages in $\mathcal{M}$ and keys in $\mathcal{K}$ is a tuple of probabilistic polynomial time $\Sigma = (\text{Setup}, \text{KGen}, \text{Sign}, \text{Vf})$ as follows:

- $\text{Setup}(1^{\kappa})$ generates the global parameters $\text{param}$ from $1^{\kappa}$. Returns $\text{param}$.

- $\text{KGen}(\text{param})$ generates a secret key $\text{sk}$ and a public key $\text{pk}$. Returns $(\text{sk}, \text{pk})$.

- $\text{Sign}(\text{sk}, m)$ generates a signature $\sigma$ of $m$ with the key $\text{sk}$. Returns $\sigma$.

- $\text{Vf}(\text{pk}, \sigma)$ verifies if the signature $\sigma$ is a valid signature using the public key $\text{pk}$. Returns 1 if $\sigma$ is a valid signature and 0 otherwise.

We expect the decryption correctness property: With $\text{param} \leftarrow \text{Setup}(1^{\kappa})$ and $(\text{pk}, \text{sk}) \leftarrow \text{KGen}(\text{param})$, $\text{Vf}(\text{pk}, \text{Sign}(\text{sk}, m)) = 1$. Similarly to MAC, one should not be able to forge signatures:

**Existential Unforgeability under Chosen Messages Attack.** Let $\text{sk} \leftarrow \text{KGen}(1^{\kappa})$ and $\mathcal{A}$ be an adversary with access to an oracle knowing the key $\text{sk}$ and able to compute the tag of any message. $\mathcal{A}$ wins if after a polynomially bounded number of queries, he can generate a signature $\sigma$ for a message $m$ not in the list $\mathcal{Q}$ of previously queried messages to the oracle, such that $\text{Vf}(\text{pk}, m, \sigma) = 1$.
Definition 2.23 - Existential Unforgeability under Chosen Messages Attack (EUF-CMA)

Given a signature scheme $\Sigma = (\text{Setup}, \text{KGen}, \text{Sign}, \text{Vf})$, the advantage of the adversary $\mathcal{A}$ making polynomially-many queries to a signature oracle in violating the EUF-CMA security of $\Sigma$ is given by:

$$ \mathrm{Adv}_{\Sigma}^{\mathrm{EUF-CMA}}(\mathcal{A}) = \Pr[\mathbf{Exp}_{\Sigma}^{\mathrm{EUF-CMA}}(\mathcal{A}) = 1] $$

and the advantage function $\mathrm{Adv}_{\Sigma}^{\mathrm{EUF-CMA}}(t)$ as

$$ \mathrm{Adv}_{\Sigma}^{\mathrm{EUF-CMA}}(t) = \max_{\mathcal{A}} (\mathrm{Adv}_{\Sigma}^{\mathrm{EUF-CMA}}(\mathcal{A})) $$

over all $\mathcal{A}$ with time-complexity at most $t$.

$$ \frac{\mathbf{Exp}_{\Sigma}^{\mathrm{EUF-CMA}}(\mathcal{A}, 1^{\kappa})}{\mathbf{Exp}_{\Sigma}^{\mathrm{EUF-CMA}}(\mathcal{A}, \kappa)} $$

1. $\mathbf{sk} \leftarrow \mathbf{KGen}(1^{\kappa})$

2. $(m, \sigma) \leftarrow \mathcal{A}^{\mathrm{Sign}(\mathbf{sk}, \cdot)}(\cdot)$

3. **if** $m \in \mathfrak{Q}$: **return** 0

4. **else return** $\mathrm{Vf}(\mathbf{pk}, \sigma)$

Hence, $\Sigma$ provides EUF-CMA security if $\mathrm{Adv}_{\Sigma}^{\mathrm{EUF-CMA}}(t)$ is negligible.

## 2.4 Homomorphic encryption

One of the most popular tool for Secure Multiparty Computation is Homomorphic Encryption. This primitive allows to evaluate a circuit on encrypted data. Depending on the circuit family, homomorphic encryption schemes are split into three variants:

* Partially Homomorphic Encryption: Unbounded computation of a single operation among additive and multiplicative homomorphism. Those are to most popular of the homomorphic encryption algorithms. An example of such an encryption scheme is denoted in figure 2.1.

* Somewhat / Leverage Homomorphic Encryption: Circuits that allow an unbounded computation of additions and finite computation of multiplications.

* Fully Homomorphic Encryption: unbounded computation of both additive and multiplicative Homomorphism. Such systems have a long time thought to be unfeasible until the seminal thesis of Gentry [Gen09] in which the first FHE scheme is designed, based on lattices. However, such cryptosystems are not efficient.

More formally, one can define:

Definition 2.24 - Homomorphic Encryption

An Homomorphic Encryption Scheme $\Gamma$ is a tuple of probabilistic polynomial time algorithms (Setup, KGen, Enc, Eval, Dec) :

- Setup(1$^{\kappa}$) generates the global parameters $\mathbf{param}$ from 1$^{\kappa}$. Returns $\mathbf{param}$.

- KGen($\mathbf{param}$) generates and outputs a secret key $\mathbf{sk}$ and its associated public key $\mathbf{pk}$. Returns $(\mathbf{pk}, \mathbf{sk})$.

- Enc($\mathbf{pk}, m$) computes an encryption $c$ of $m \in \mathcal{M}$ using the key $\mathbf{pk}$. Returns $c$.

- Eval($\mathbf{pk}, \mathcal{C}, \{c_i\}$) computes $c'$, an evaluation of the circuit $\mathcal{C}$ using ciphertexts $\{c_i\}$ and public key $\mathbf{pk}$. Returns $c'$.

- Dec($\mathbf{sk}, c$), computes a decryption $m$ of $c$ using the key $\mathbf{sk}$. Returns $m$.

In table 2.1, we detail variants of homomorphic encryption, according to the maximum additive and maximum multiplicative depth of the circuit, together with examples of such cryptosystems:

In this thesis, we use several times a well-known homomorphic encryption scheme, namely the Elgamal encryption scheme: Let $\mathcal{G}$ be a cyclic group of prime order $q$, with generator $g$:
<table><caption>Table 2.1: Summary of the Homomorphic Encryption families</caption><thead><tr><th>+</th><th>×</th><th>Family of Γ</th><th>Examples</th></tr></thead><tbody><tr><td>∞</td><td>0</td><td>Additive Homomorphic Encryption</td><td>[GM82, Pai99]</td></tr><tr><td>0</td><td>∞</td><td>Multiplicative Homomorphic Encryption</td><td>[RSA78, EIG85]</td></tr><tr><td>∞</td><td>k ∈ Z</td><td>Somewhat Homomorphic Encryption</td><td>[BGN05, AGH10]</td></tr><tr><td>∞</td><td>∞</td><td>Fully Homomorphic Encryption</td><td>[Gen09]</td></tr></tbody></table>

<table><caption>Figure 2.1: ElGamal Encryption Scheme</caption><thead><tr><th>KGen(1<sup>κ</sup>)</th><th>Enc(pk, m)</th><th>Dec(sk, m)</th></tr></thead><tbody><tr><td>1. x &larr; $Z<sub>q</sub></td><td>1. r &larr; $Z<sub>q</sub></td><td>1. m = c<sub>2</sub> &middot; c<sub>1</sub><sup>-sk</sup></td></tr><tr><td>2. y &larr; g<sup>x</sup></td><td>2. c<sub>1</sub> = g<sup>r</sup></td><td>2. <b>return</b> m</td></tr><tr><td>3. pk &larr; (g, y, q)</td><td>3. c<sub>2</sub> = (m &middot; y<sup>r</sup>)</td><td></td></tr><tr><td>4. sk &larr; x</td><td>4. <b>return</b> C = (c<sub>1</sub>, c<sub>2</sub>)</td><td></td></tr><tr><td>5. <b>return</b> (pk, sk)</td><td></td><td></td></tr></tbody></table>

To understand the homomorphic properties of ElGamal, consider two encryptions $C = (c_1, c_2) = \text{Enc(pk, m)}$ and $C' = (c'_1, c'_2) = \text{Enc(pk, m')}$ and compute $C'' = (c_1 \times c'_1, c_2 \times c'_2)$. We have:

$$c_1'' = c_1 \times c_1' = g^r \times g^{r'} = g^{r+r'} \quad \text{and}$$

$$c_2'' = c_2 \times c_2' = ((m \cdot y^r)) \times ((m' \cdot y'^r)) = (m \cdot m') \cdot y^{r+r'}$$

The pair $C'' = (c_1'', c_2'')$ is a ciphertext for $m \cdot m'$. Hence, we have

$$C'' = \text{Enc(pk, } m \cdot m') = \text{Enc(pk, } m) \cdot \text{Enc(pk, } m')$$

ElGamal cryptosystem therefore is a multiplicative homomorphic scheme. We can convert the ElGamal encryption scheme to an additive encryption scheme by encrypting $g^m$ rather than $m$. The obtained encryption scheme is denoted *lifted* ElGamal encryption scheme. However, using a *lifted* version of ElGamal implies discrete logarithm computations.

## 2.5 Post-Quantum cryptography

Due to the Shor's algorithm [Sho94], asymmetric cryptosystems based on the RSA and Discrete Logarithm problems are no longer secure when using quantum computers. Thus, the National Institute of Standards and Technologies launched a program to standardize post-quantum Public-Key Encryption / Key Encryption Mechanism and Signature. Starting from 59 PKE/KEM schemes and 23 signatures, four have been standardized [SAB+20, LDK+20, PFH+20, HBD+20] after Round 3 and three are still in the running to be standardized [AAB+22, ABB+22, ABC+22]. In reality, a fourth candidate [JAC+22] also reached round 4. However, the security of its signature relies on an Isogeny-Based assumption of which an efficient attack has been published [CD22], making this candidate obsolete. The three candidates still in competition are all based on Code-Based Cryptography, while already standardized candidates use Hash-Based Cryptography or Lattice-Based Cryptography. It is the latter that is briefly introduced here.
### Definition 2.25 - Lattices

A lattice $L \subset \mathbb{R}^n$ is the set of all linear combinations of vector from a basis $B = \{b_1, \dots, b_n\}$:

$$L = \left\{ \sum_{i=0}^{n} a_i b_i , a_i \in \mathbb{Z} \right\}$$

We now introduce some computational problems based on lattices. We begin with the basic Shortest Vector Problem.

### Definition 2.26 - Shortest Vector Problem (SVP)

Given a lattice $L$, the Shortest Vector Problem consists in finding the shortest non-zero vector in $L$. In other words, giving a lattice $L$ and its basis $B$, find $x \in L$ such that

$$\|x\| = \lambda(L) := \min_{v \in L \setminus \{0\}} \|v\|$$

A weaker version of the SVP includes a factor $\gamma$ representing the relaxation of the previous problem where the goal is not necessary to find the shortest vector, but a vector more or less close to the shortest vector, according to $\gamma$.

### Definition 2.27 - Approximate Shortest Vector Problem (SVP$_{γ}$)

Given an $n$-dimensional lattice $L$ and its basis $B$, find $x \in L$ such that

$$\|x\| \le \gamma(n) \cdot \lambda(L) = \min_{v \in L \setminus \{0\}} \|v\|$$

A last problem consists in deciding if the shortest vector of a given lattice has a norm smaller than 1 or higher than the parameter $\gamma$.

### Definition 2.28 - Decisional Approximate Shortest Vector Problem (GapSVP$_{γ}$)

Given a basis $B$ of an $n$-dimensional lattice $L = L(B)$ where either $\lambda(L) \le 1$ or $\lambda(L) > \gamma(n)$, determine which is the case.

We now introduce another problem, namely the Learning With Errors (LWE) problem. This problem is not a variation of the SVP problem, but in his seminal paper [Reg05], Regev proved that solving the worst-case hardness of this problem can be reduced to the GapSVP$_{γ}$ problem.

### Definition 2.29 - Learning With Errors (LWE)

Let $q \ge 2$, and $\chi$ be a distribution over $\mathbf{G}$. Given a polynomial number of samples, the Learning With Errors problem $\text{LWE}_{\chi,q}$ consists in distinguishing the two following distributions:

- $(\mathbf{a}, \langle \mathbf{a}, \mathbf{s} \rangle + e)$, where $\mathbf{a}$ is uniform in $\mathbf{G}_q^n$, $e \leftarrow \chi$, and $\mathbf{s} \in \mathbf{G}_q^n$ is a fixed secret chosen uniformly, and where $\langle \mathbf{a}, \mathbf{s} \rangle$ denotes the standard inner product.

- $(\mathbf{a}, b)$, where $\mathbf{a}$ is uniform in $\mathbf{G}_q^n$, and $b$ is uniform in $\mathbf{G}_q^n$.

## 2.6 Zero-knowledge proofs

A Zero-knowledge proof (ZKP) is an interactive protocol between a prover $P$, who wants to prove to a verifier $V$ that he knows a witness $w$ for a given statement $x$ in a language.
## Definition 2.30 - Language

A language $\mathcal{L}$ is a subset of a space of words $\mathcal{X}$ with witness relation $\mathfrak{R}_\mathcal{L}$ such that

$$ \mathcal{L} = \{x \in \mathcal{X} \mid \exists w \text{ s.t. } \mathfrak{R}_{\mathcal{L}}(x, w) = 1\}. $$

At the end of the protocol, the verifier should have learned nothing more about the statement than its veracity. Zero-Knowledge proofs can be made non-interactive, and we only consider such Non-Interactive Zero-Knowledge proofs (NIZK) in the remaining of the thesis.

## Definition 2.31 - Zero-Knowledge proofs

A Non-Interactive Zero-knowledge Proof NIZK is a tuple of probabilistic polynomial time NIZK = (Setup, ZKGen, ZKVerify, ZKSim) as follows:

- Setup(1$^{κ}$) generates global parameters param based on the security parameter. Returns param.

- ZKGen(x, $\mathcal{L}$, w) generates $\pi_x$, a zero-knowledge proof of the statement ($x \in \mathcal{L}$), using the witness w property and the relation $\mathfrak{R}_\mathcal{L}$. Returns $\pi_x$.

- ZKVerify(x, $\mathcal{L}$, $\pi_x$) verifies if $\pi_x$ is a correct proof of the statement ($x \in \mathcal{L}$). Returns accept if true, reject otherwise.

- ZKSim(x, $\mathcal{L}$) simulates a proof $\pi_x$ of any (possibly false) statement ($x \in \mathcal{L}$) without any witness. Returns $\pi_x$.

A zero-knowledge proof of knowledge requires three properties:

- Completeness: ZKGen always generate an acceptable proof when $x \in \mathcal{L}$;

- Soundness: no adversary can generate an acceptable proof when $x \notin \mathcal{L}$, but with negligible probability;

- Zero-Knowledge: ZKSim(x, $\mathcal{L}$) generates proofs that are indistinguishable to proofs generated by ZKGen(x, $\mathcal{L}$, w), on valid statements but without the witness.

When the verifier is assumed to be honest, we use Honest Verifier Zero Knowledge (HVZK) proofs

## 2.7 Smooth Projective Hash Functions

Introduced in 2002 [CS02], Smooth Projective Hash Functions (SPHF), also known as Hash Proof Systems (HPS), initially aimed to be the first public key encryption scheme secure against chosen ciphertext attacks. Nowadays, SPHF are mainly used for Honest Verifier Zero Knowledge Proofs or witness encryption. SPHFs are based on languages. More precisely, Smooth Projective Hash Functions work on NP-languages $\mathcal{L} \subset \mathcal{X}$. They require two keys: a randomly generated key hk, based on the description of $\mathcal{L}$, and a second key hp computed depending on hk. On the one hand, the key hk is used to link a word $x \in \mathcal{X}$ to its hash $H_{hk}$. On the other hand, the key hp is used together with a word $x \in \mathcal{X}$ and a witness w to compute a hash $H_{hp}$. For every word $x \in \mathcal{L}$ and its witness w, we have $H_{hk} = H_{hp}$. This is the correctness property of an SPHF. In opposition, when $x \notin \mathcal{L}$, $H_{hk}$ should be indistinguishable from random.
Definition 2.32 - Smooth Projective Hash Function

An SPHF defined on $\mathcal{L} \subset \mathcal{X}$ with values in $\mathcal{V}$ is defined by five algorithms:

- Setup($1^{\kappa}$) generates the global parameters $\mathbf{param}$ from $1^{\kappa}$, which includes a description of $\mathcal{L}$. Returns $\mathbf{param}$.

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

- ProjKG($\mathbf{hk}, [x]$) derives the projection key $\mathbf{hp}$, potentially based on a word $x$. Returns $\mathbf{hp}$.

- Hash($\mathbf{hk}, x$) computes the hash value $H_{\mathbf{hk}} \in \mathcal{V}$ associated to the word $x$. Returns $H_{\mathbf{hk}}$.

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

Those algorithms should ensure two requirements:

* **Correctness:** For any $x \in \mathcal{L}$, with witness $w$ such that $\mathcal{R}_{\mathcal{L}}(x, w) = 1$, we have $H_{\mathbf{hk}} = H_{\mathbf{hp}}$.

* **Smoothness:** For any $x \in \mathcal{X} \setminus \mathcal{L}$, the distributions of $(\mathbf{hp}, H_{\mathbf{hk}})$ and $(\mathbf{hp}, v \leftarrow \mathcal{V})$ are indistinguishable.

A summary of the definition and properties of SPHF is depicted in Figure 2.2.

<figure><img src="image_12.png" /><figcaption>Figure 2.2: Smooth Projective Hash Functions Summary from [Ben16]</figcaption></figure>

The aforementioned definition of Smooth Projective Hash Function states that the key $\mathbf{hp}$ may be computed according to $x$. In the initial definition provided by Cramer and Shoup [CS02], the key $\mathbf{hp}$ does not depend on $x$. Hence, an SPHF using this definition is denoted CS-SPHF and is expected to provide CS-smoothness. A first variation has been provided by Gennaro and Lindell in [GL03], where $\mathbf{hp}$ depends on $x$, leading to the notion of GL-SPHF and GL-smoothness. A second variant, introduced by Katz and Vaikuntanathan in [KV09] considers the ability for an attacker to maliciously generate the word $x$ after seeing the projection key $\mathbf{hp}$. In KV-SPHF, the projection depends only on the hashing key and ensure the smoothness holds even if the word $x$ is chosen after having seen the projection key.

The definitions of Gennaro and Lindell will be enough for the project introduced in section 2.1. Therefore, when using SPHF, we implicitly refer to GL-SPHF, with GL-smoothness.

## 2.8 Secure multi-party computation

Suppose you are millionaire and at a restaurant table with a millionaire friend. You agree to let the richest of you pay the bill, but do not want to reveal your exact wealth. How to proceed ? A first solution is to find a trusted third person, who will take knowledge of your wealth as well as your friend's. Then, he will compare them and tell who pays. However, if you do not even trust your friend, who will you trust? So let's update the problem: *How to proceed without telling anyone your wealth?*
This problem, known as the Yao's millionaires' Problem, was stated by Andrew Yao in [Yao86]. While the notion of secure computation was first introduced by Shamir, Rivest and Adleman consider a mental poker game [SRA81], Yao formally introduced it as secure two-party computation (2PC). More formally, secure two-party computation implies two parties, commonly denoted Alice and Bob with respective inputs $x_A$ and $x_B$. Their goal is to compute

$$z = (z_A, z_B) = (f_A(x_A, x_B), f_B(x_A, x_B))$$

where $f_A(x_A, x_B)$ is the output returned to Alice and $f_B(x_A, x_B)$ the output returned to Bob. In terms of privacy, Bob should learn nothing more about Alice's input than what he learns from his output, and vice versa.

<figure><img src="image_13.png" /><figcaption>Figure 2.3: Secure two-party computation protocol</figcaption></figure>

In a multiparty secure computation protocol, we do not only consider the adversary as an external eavesdropper, but also as one of the participants. In the latter case, his power is defined according to his ability to deviate from the protocol.

**MPC security models.** If the adversarial party is forced to follow the protocol, but can try to extract information from the transcript of the protocol, he is said to be *Honest-but-Curious*. If he can deviate from the protocol, he is said to be *malicious*. A goal of a malicious party is not only to extract sensitive information, he also may orient the protocol in a well-chosen way. In [GMW87], Goldreich et al. introduced a compiler, converting a protocol secure against *Honest-but-Curious* adversaries into a protocol secure against malicious adversaries. However, protocols secure against malicious adversaries are often inefficient. Thus, Aumann and Lindell introduced *covert* adversaries [AL07]. Rather than preventing malicious adversaries, the model of covert adversaries detects (with good probability) and reports malicious adversaries, potentially bringing discredit on them.

We now describe the main primitives to perform secure multiparty computation.

### 2.8.1 Oblivious Transfers

Oblivious Transfers (OT), first introduced in [EGL82] are a primitive widely used as a component of larger multiparty computation protocols as they allow a party to obliviously retrieve a value from another party, with privacy guarantees for both of them.

An Oblivious Transfer, in its simplest form, is a cryptographic primitive implying a *sender* with two messages $(m_0, m_1)$ and a *receiver* with a selection bit $b$. The receiver aims to retrieve $m_b$, such that the sender does not learn any information about $b$. Also, the receiver must not learn any information about $m_{1-b}$. As a secure two-party computation, an instantiation of an Oblivious Transfer can be written as: $f(b, (m_0, m_1)) = (m_b, \emptyset)$. This basic protocol can be generalized, where the receiver aims to retrieve $k$ messages among $n$ and is denoted $k$-out-of-$n$ OT.

We now give a formal definition of an Oblivious Transfer protocol:
<figure><img src="image_14.png" /><figcaption>Figure 2.4: Oblivious Transfer protocol</figcaption></figure>

**Definition 2.33 - Oblivious Transfer**

An Oblivious Transfer OT can be defined using a tuple of PPT algorithms $\text{OT} =$ ($\text{Encode}$, $\text{Compute}$, $\text{Decode}$) as follows:

- $\text{Encode}(b)$ generates a pair $\tilde{b} = (\tilde{b}_{\text{Enc}}, \tilde{b}_{\text{Dec}})$. Returns $\tilde{b}$

- $\text{Compute}((m_0, m_1), \tilde{b}_{\text{Enc}})$ encodes $m_0$ and $m_1$ as $(\tilde{m}_0, \tilde{m}_1)$ using the encoded expected bit $\tilde{b}_{\text{Enc}}$. Returns $(\tilde{m}_0, \tilde{m}_1)$

- $\text{Decode}((\tilde{m}_0, \tilde{m}_1), \tilde{b}_{\text{Dec}})$ decodes $(\tilde{m}_0, \tilde{m}_1)$ using $\tilde{b}_{\text{Dec}}$. Returns $m_b$

We now describe two simple constructions, one that is proven secure in the honest-but-curious model, while the other one is secure against malicious parties.

**Bellare-Micali's Construction [BM90].** We first introduce the construction from Bellare and Micali. This construction relies on the discrete logarithm problem and uses ElGamal encryption scheme.

<figure><img src="image_15.png" /><figcaption>Figure 2.5: Bellare-Micali's Oblivious Transfer</figcaption></figure>

This construction is secure against honest-but-curious adversaries under the DDH assumption. However, in the case of a malicious receiver, we can not prove whether the DDH assumption is enough to guarantee the security. At least, no proof has been provided so far. Hence, we can not exclude the case where the receiver generates $pk_0$ and $pk_1$, knowing partial information about each private keys, allowing her to extract information about both $m_0$ and $m_1$. Even if she is not able to totally recover $m_0$ and $m_1$, knowing any bit of information about more than a message is considered as a security leak. For example, being able to extract a single bit of $m_0 + m_1$, even without extracting $m_0$ or $m_1$ is a security leak that makes the protocol unsecure.

We now describe an Oblivious Transfer protocol from Naor and Pinkas, safe against malicious adversaries.

**Naor-Pinkas construction [NP01].** Consider a group $\mathcal{G}$ where the DDH assumption holds.
<figure><img src="image_16.png" /><figcaption>Figure 2.6: Naor-Pinkas’ Oblivious Transfer construction</figcaption></figure>

In this protocol, the protection against malicious adversaries is provided by the randomization of $Y, Z_b$ and $Z_{1-b}$. Indeed, $(X, Y, Z_b)$ is a DDH tuple, and so is $(X, Y'_b, Z'_b)$, but as $Z_0 \neq Z_1$, the tuple $(X, Y, Z_{1-b})$ can not be a DDH tuple. In addition, the randomization operated by the sender transforms $(X, Y, Z_b)$ in a perfectly inoperable random tuple $(X, Y'_{1-b}, Z_{1-b})$.

In some context, one may be required to compute many Oblivious Transfers. To reduce costs, a solution is to use Extended Oblivious Transfers.

### 2.8.1.1 Extended Oblivious Transfer [IKNP03]

When it comes to large amount of Oblivious Transfers to compute, using classical Oblivious Transfers as described previously may represent a massive communication cost. Suppose the receiver gets $\sigma = (\sigma_1, \dots, \sigma_n)$ as input and the sender gets $((m_0^0, m_0^1), \dots, (m_n^0, m_n^1))$ with $n \gg k = |m'_i|$.

<figure><img src="image_17.png" /><figcaption>Figure 2.7: Initial Sender and Receiver inputs</figcaption></figure>

The first step of OT extension is to generate new inputs. The receiver, Alice, generates a random bit-matrix $T$ of size $n \times k$ and generates $k$ pairs $(T_i, T_i \oplus \sigma)$. The sender, Bob, generates a random string $s \in \{0, 1\}^k$.

<figure><img src="image_18.png" /><figcaption>Figure 2.8: New Sender and Receiver inputs</figcaption></figure>

One may guess the next step by comparing Figures 2.7 and 2.8. Alice and Bob will proceed to $k \ll n$ standard Oblivious Transfers but with Alice as sender and Bob as receiver. After the $k$
Oblivious Transfers, Bob has *k* strings, each of length *n* bits. We denote by $Q_i$ the *i*-th message retrieved by Bob. We have:

$$Q_i = \begin{cases} T_i & \text{if } s_i = 0. \\ T_i \oplus \sigma & \text{if } s_i = 1. \end{cases}$$

Let $T^j$ and $Q^j$ denoting the *j*-th column of $T$ and $Q$. We have $T_i^j = Q_i^j$ when $\sigma_j = 0$ no matter the value of $s_i$. When $\sigma_j = 1$, this has an impact only when $s_i = 1$. More precisely, when $\sigma_j = 1$ we have $T_i^j = Q_i^j \oplus s_i$. Hence, we have:

$$T^j = \begin{cases} Q^j & \text{if } \sigma_j = 0. \\ Q^j \oplus s & \text{if } \sigma_j = 1. \end{cases}$$

With this relation, Bob can now send to Alice the initial messages. Given a hash function $H$, Bob computes and sends

$$y_j^0 = H(j, Q^j) \oplus m_0^j \quad \text{and} \quad y_j^1 = H(j, Q^j \oplus s) \oplus m_1^j$$

Finally Alice computes $m_{\sigma_j}^j = H(j, T^j) \oplus y_j^{\sigma_j}$, the list of the *j*-th bit of each message $m_{i, \sigma_i}$.

### 2.8.2 Garbled Circuits

In this section, we describe the Garbled Circuits as a technique. We refer the reader to [BHR12] for a definition of Garbled Schemes as a primitive. The Introduction of Garbled Circuits is first credited to Andrew Yao as he introduced the idea in the oral presentation of [Yao86]. Then, this idea was first put down on paper in 1987 [GMW87] while the first appearance of the term Garbled Circuits is in 1990 [BMR90].

A circuit is a boolean representation of a function. This representation uses logical gates as computation steps. A logical gate is a small function taking 1 bit as input (NOT) or 2 (AND, OR, NAND, NOR, XOR or XNOR) and returning one bit as output. As NOT, OR, NAND, NOR and XNOR gates can be rewritten using only AND and XOR gates, this is enough to focus on those two logical gates. AND returns 1 only if both inputs bit equal 1 and 0 if at least one of the input bit is 0. XOR computes the exclusive-OR and returns 1 only if the input bits are not equal, and 0 otherwise.

<table><thead><tr><th>α</th><th>β</th><th>α ∧ β</th></tr></thead><tbody><tr><td>0</td><td>0</td><td>0</td></tr><tr><td>0</td><td>1</td><td>0</td></tr><tr><td>1</td><td>0</td><td>0</td></tr><tr><td>1</td><td>1</td><td>1</td></tr></tbody></table>

(a)

<table><thead><tr><th>α</th><th>β</th><th>α ⊕ β</th></tr></thead><tbody><tr><td>0</td><td>0</td><td>0</td></tr><tr><td>0</td><td>1</td><td>1</td></tr><tr><td>1</td><td>0</td><td>1</td></tr><tr><td>1</td><td>1</td><td>0</td></tr></tbody></table>

(b)

<caption>Table 2.2: Truth table for the AND logical gate, denoted $\land$ (a) and the XOR logical gate, denoted $\oplus$ (b)</caption>

When a circuit is garbled, that can be seen as an "encryption" of the circuit. A Garbled Circuits implies two parties, a *Garbler* that is interpreted by Gisele, and an *evaluator*, that is represented by Edmond. Input bits are represented with random keys, also called labels, that only the garbler can invert to associated bits. Then, using *Oblivious Transfers*, the evaluator retrieves the encoding of his bits, generated by the garbler, and can then evaluate the circuit using the ciphetexts computed by the generator. Finally, to convert the output label of the circuit, the garbler sends, together with the circuit and her input labels, a transition table mapping output label with the corresponding output bit.

We first describe the garbling phase as it was initially done in [Yao86], using double encryption.
### 2.8.2.1 Garbling

The initial garbling solution uses a double symmetric encryption $Π$. Given a function $f: \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}^*$, Gisele first represents $f$ as a circuit $C_f$ made of AND and XOR gates. Then, gates after gates, Gisele garbles the circuit $C_f$. For each gate, she generates three pairs of keys : a pair $(k_0^G, k_1^G)$ for the wire 1, defined as Gisele's input wire, a pair $(k_0^E, k_1^E)$ for the wire 2, set as Edmond's wire, and a pair $(k_0^{out}, k_1^{out})$ for the output wire.

First, let us focus on the case where Gisele's input is 0, and Edmond's input is 0. Her key will be $k_0^G$ and Edmond's key will be $k_0^E$. Looking at the Table 2.2, the output of the non-garbled gate is $0 \land 0 = 0$ which associated key is $k_0^{out}$. Hence, Gisele computes $E_{k_0^G, k_0^E}(k_0^{out}) = Π.Enc(H(k_0^G||k_0^E), k_0^{out})$ where $H$ is a Hash Function. Applying the same process for all possible cases leads to the table obtained in Table 2.3.

<table><caption>Table 2.3: Unpermuted Garbled Table for an AND gate</caption><thead><tr><th>wire 1</th><th>wire 2</th><th>output</th><th>G's key</th><th>E's key</th><th>Output key</th><th>Garbled Table</th></tr></thead><tbody><tr><td>0</td><td>0</td><td>0</td><td>$k_0^G$</td><td>$k_0^E$</td><td>$k_0^{out}$</td><td>$E_{k_0^G, k_0^E}(k_0^{out})$</td></tr><tr><td>0</td><td>1</td><td>0</td><td>$k_0^G$</td><td>$k_1^E$</td><td>$k_0^{out}$</td><td>$E_{k_0^G, k_1^E}(k_0^{out})$</td></tr><tr><td>1</td><td>0</td><td>0</td><td>$k_1^G$</td><td>$k_0^E$</td><td>$k_0^{out}$</td><td>$E_{k_1^G, k_0^E}(k_0^{out})$</td></tr><tr><td>1</td><td>1</td><td>1</td><td>$k_1^G$</td><td>$k_1^E$</td><td>$k_1^{out}$</td><td>$E_{k_1^G, k_1^E}(k_1^{out})$</td></tr></tbody></table>

Analogously, the garbling of an XOR gate is given in Table 2.4.

<table><caption>Table 2.4: Unpermuted Garbled Table for an XOR gate</caption><thead><tr><th>wire 1</th><th>wire 2</th><th>output</th><th>G's key</th><th>E's key</th><th>Output key</th><th>Garbled table</th></tr></thead><tbody><tr><td>0</td><td>0</td><td>0</td><td>$k_0^G$</td><td>$k_0^E$</td><td>$k_0^{out}$</td><td>$E_{k_0^G, k_0^E}(k_0^{out})$</td></tr><tr><td>0</td><td>1</td><td>1</td><td>$k_0^G$</td><td>$k_1^E$</td><td>$k_1^{out}$</td><td>$E_{k_0^G, k_1^E}(k_1^{out})$</td></tr><tr><td>1</td><td>0</td><td>1</td><td>$k_1^G$</td><td>$k_0^E$</td><td>$k_1^{out}$</td><td>$E_{k_1^G, k_0^E}(k_1^{out})$</td></tr><tr><td>1</td><td>1</td><td>0</td><td>$k_1^G$</td><td>$k_1^E$</td><td>$k_0^{out}$</td><td>$E_{k_1^G, k_1^E}(k_0^{out})$</td></tr></tbody></table>

Once the garbler generated a garbled table, she permutes its entry such that an entry index does not depend on the inputs. Then, when garbling the last gate, she generates the transition table $((k_0^{out}, 0); (k_1^{out}, 1))$, later allowing the evaluator to convert the inoperable output key in an output bit. Once done, Gisele sends the Garbled Circuits $\tilde{C}_f$ containing the garbled tables, the transition table $T$, and its input keys $k_\alpha^G = (k_{i,\alpha}[i])$ to Edmond (where $k_{\alpha}[i]$ is the label corresponding to $i$-th bit of $\alpha$), who will proceed to the evaluation.

### 2.8.2.2 Evaluation

When the evaluator receives the garbled tables, the input labels of Gisele and the transition table from Gisele, he has to retrieve the keys $k_\beta^E = (k_{i,\beta}[i])$ corresponding to his input. As, on the one hand, Edmond wants his input to remain private and, on the other hand, if Gisele reveals both keys for each input wire, this would allow Edmond to decrypt two entries by garbled tables. The solution for Edmond is to retrieve his key using one Oblivious Transfer by input bit, where Gisele will be the sender and Edmond the receiver. Once Edmond retrieved his keys, he evaluates each gate, where for each gate, Edmond has two keys, $k_A$ and $k_B$, that he used to decrypt entries of the corresponding Garbled Table. Once a decryption success, detected thanks to some padding, the freshly obtained key as output of the gate is now either used as an input of another gate, or is converted to an output bit thanks to a transition table.
**Cost.** We can see that for each gate, the garbler needs to generate a four entry garbled table (one for each key combination). Denoting $n_{AND}$ the amount of AND gates, $n_{XOR}$ the amount of XOR gates and $\kappa$ the security parameter (i.e. the bit-length of the keys), the total communication cost is of $4(n_{AND} + n_{XOR}) \cdot \kappa$ bits. Also, the Evaluator will have to decrypt the four entries in the worst cases and 2.5 keys on average. This can be considerably reduced, using optimizations.

### 2.8.2.3 Optimizations

We now present the main optimizations leading to the best performances for implementing Garbled Circuits. As a toy example, we describe the ciphertexts obtained for all optimizations for a circuit computing $\underbrace{(A \land B)}_{D} \oplus C$. Without optimization, the resulting garbled table are:

<figure><img src="image_19.png" /><figcaption>Table 2.5: Garbled tables - Without optimizations</figcaption></figure>

**FreeXOR.** In 2008, Kolesnikov et al. introduced freeXOR [KS08]. The freeXOR technique applies to XOR gates and works as follows: The garbler first randomly generates $k_0^G$ and $k_0^E$ and a random offset $\Delta \in \{0, 1\}^\kappa$. Then she sets $k_1^G = k_0^G \oplus \Delta$, $k_1^E = k_0^E \oplus \Delta$ and $k_0^{out} = k_0^G \oplus k_0^E$, $k_1^{out} = k_0^{out} \oplus \Delta$. With such a setup, the evaluator can evaluate a XOR gate simply by computing a XOR between both input keys. Figure 2.9 shows the correctness of this optimization by testing all possible key combination.

<figure><img src="image_20.png" /><figcaption>Figure 2.9: FreeXOR optimization</figcaption></figure>

This optimization does not require the garbler to send a garbled table to the evaluator as the evaluation is made by xoring the two input keys. Hence, the communication and computation cost of XOR gates are free with this optimization.

As the evaluation of XOR gates are now free, the total communication and computation cost of the protocol relies only on the AND gates. Recall that without optimization, the evaluation of an AND gate costs 4 ciphertexts and 2.5 decryptions on average.

**Point and Permute.** To reduce the amount of decryptions, Beaver et al. introduced the Point and Permute (P&P) optimization in [BMR90]. When considering an AND gate with the keys $(k_0^G, k_1^G)$; $(k_0^E, k_1^E)$, Gisele samples random signal bits $p_G$ and $p_E$, and update the keys as
<table><caption>Table 2.6: Garbled tables - With FreeXOR</caption><tr><td>E<sub>k<sub>1</sub><sup>A</sup>,k<sub>0</sub><sup>B</sup></sub>(k<sub>0</sub><sup>D</sup>)</td></tr><tr><td>E<sub>k<sub>0</sub><sup>A</sup>,k<sub>1</sub><sup>B</sup></sub>(k<sub>0</sub><sup>D</sup>)</td></tr><tr><td>E<sub>k<sub>1</sub><sup>A</sup>,k<sub>1</sub><sup>B</sup></sub>(k<sub>1</sub><sup>D</sup>)</td></tr><tr><td>E<sub>k<sub>0</sub><sup>A</sup>,k<sub>0</sub><sup>B</sup></sub>(k<sub>0</sub><sup>D</sup>)</td></tr></table>

$$ (k_0^G, k_1^G) \leftarrow (k_0^G \| p_G, k_1^G \| \overline{p_G}) \text{ and } (k_0^E, k_1^E) \leftarrow (k_0^E \| p_E, k_1^E \| \overline{p_E}). $$

Then, the garbler permutes the garbled gates according to the signal bits. Consider the input keys $k_0^G$ and $k_0^E$, their respective signal bit is $p_G$ and $p_E$. Thus, the garbled table entry $E_{k_0^G, k_0^E}(k_0^{out})$ has for index $2 \times p_G + p_E$. The garbler acts in the same way, mutatis mutandis, for the other key combinations. When evaluating, Edmond extracts the signal bit of each key used as inputs of the gate and deduces the index of the ciphertext to decrypt. This reduces the computational cost from 2.5 decryptions in average to a single decryption in any case.

As this is the best computational cost we can expect for an AND gate, we now introduce optimizations to reduce the communication cost of the AND gates. Also, now that the evaluator has only one decryption to proceed, no more padding is required, and we can set $E_{k_A, k_B}(k_{out}) = k_{out} \oplus H(k_A||k_B)$ where $H$ is a hash function.

**Garbled Row Reduction 3.** Let $k_A \in \{k_0^G, k_1^G\}$ and $k_B \in \{k_0^E, k_1^E\}$ be input keys with signal bit at 0. In [NPS99], Naor et al. introduced Garble Row Reduction 3 (GRR3) where $k_{out}$ is set as $Dec_{k_A, k_B}(0)$. The garbler therefore only needs to send three ciphertexts instead of four, and decrypts as before, where the encryption at index 0 of the AND gate garbled table is 0. This reduces the communication cost by a factor $\frac{1}{4}$.

<table><caption>Table 2.7: Garbled tables - With Garbled Row Reduction 3</caption><tr><td>E<sub>k<sub>0</sub><sup>A</sup>,k<sub>1</sub><sup>B</sup></sub>(k<sub>0</sub><sup>D</sup>)</td></tr><tr><td>E<sub>k<sub>1</sub><sup>A</sup>,k<sub>1</sub><sup>B</sup></sub>(k<sub>1</sub><sup>D</sup>)</td></tr><tr><td>E<sub>k<sub>0</sub><sup>A</sup>,k<sub>0</sub><sup>B</sup></sub>(k<sub>0</sub><sup>D</sup>)</td></tr></table>

**Garbled Row Reduction 2.** Pinkas et al. in [PSSW09] introduced Garbled Row Reduction 2 (GRR2). They use polynomial interpolation to reduce the communication cost such that only two ciphertexts by AND gate are required. The idea is to generate two polynomials. To convert labels to coordinates, Gisele acts as follows: Given two keys $k_A, k_B$, the abscissa is $1+2 \times p(k_A)+p(k_B)$ where $p(\cdot)$ extracts the signal bits, while the ordinate is given by $H(k_A||k_B)$, where $H$ is a hash function. For the sake of simplicity, we set $p_G = 0$ and $p_E = 1$, hence the four points are:

$$ (1, H(k_0^G||k_1^E)), (2, H(k_0^G||k_0^E)), (3, H(k_1^G||k_1^E)), (4, H(k_1^G||k_0^E)). $$

We have seen in Table 2.3 that three combinations of keys yield to the output label $k_0^{out}$ and only one to $k_1^{out}$. Hence, the first step is to interpolate the points associated to these three combinations, generating a degree-2 polynomial $P$. In our case, those points are

$$ (1, H(k_0^G||k_1^E)), (2, H(k_0^G||k_0^E)), (4, H(k_1^G||k_0^E)). $$

The key $k_0^{out}$ is set as $P(0)$. As the evaluator will only know one point of the polynomial, he needs two more points to compute the interpolation and retrieve $k_0^{out}$. Those points are set as $(5, P(5))$
and $(6, P(6))$. Then, the garbler interpolates $(5, P(5))$ and $(6, P(6))$ with the remaining point (in our case $(3, H(k_1^G || k_1^E)$)) to generate a second polynomial $Q$. This implies that $P(5) = Q(5)$ and $P(6) = Q(6)$. Similarly, the key $k_1^{out}$ is set as $P(0)$. The ciphertexts of the gate Gisele sends to Edmond are $P(5)$ and $P(6)$. Finally, the evaluator interpolates $(5, P(5))$ and $(6, P(6))$ with the hash of the input labels.

The reader may note that with this optimization, there is no way to maintain the offset used in the FreeXOR optimization. Hence, the GRR2 optimization is not compatible with the FreeXOR optimization. However, the GRR2 can also be applied to the XOR gates with this method. The idea is nearly the same as for AND gates, except that, as both outputs bit are returned in two combinations, one generate two affine polynomials $P$ and $Q$, and the ciphertexts consist in $P(5)$ and $Q(5)$. A graphical representation of this optimization is depicted in Figure 2.10.

<figure><img src="image_21.png" /><figcaption>Figure 2.10: Graphical representation of GRR2 with an AND gate on the left and an XOR gate on the right. In orange is the polynomial $P$ associated to bit output 0, and in green the polynomial $Q$ associated to the bit output 1.</figcaption></figure>

Hence, we have two ciphertexts by gate, whether it is an AND gate or an XOR gate. This made the GRR2 optimization better than combining GRR3 and FreeXOR if there is less than twice more XOR gates than AND gates.

<table><caption>Table 2.8: Garbled tables - With Garbled Row Reduction 2 optimization</caption><tr><td>P(5)</td><td>P(5)</td></tr><tr><td>P(6)</td><td>Q(5)</td></tr></table>

However, in 2015, Zahur et al. introduced HalfGates, resulting in a two-ciphertexts table, compatible with the freeXOR optimization.

**HalfGates.** In [ZRE15], Zahur et al. introduced Halfgates where they used the fact that for any $r \in \{0, 1\}$:

$$a \wedge b = (a \wedge r) \oplus (a \wedge (b \oplus r)).$$

The Halfgates optimization sets $r = p_B$, the random select bit for the wire $B$.

**A - Garbler's half gate.** In the first half gate, Gisele knows $r$. Thus, the output only depends on $a$. If $a = 0$, the output of the half gate is always 0, hence the first ciphertext is $H(k_0^A) \oplus k_0^G$. If $a = 1$, the output depends on the value of $r$, hence the second ciphertext is $H(k_1^A) \oplus k_r^G$. When evaluating, Edmond looks at the select bit of $k_A$ and xor the corresponding ciphertext with $H(k_A)$.
**Correctness.** If $a = 0$, we have $k^A = k_0^A$. Edmond then computes

$$ (H(k_0^G) \oplus k_0^G) \oplus H(k^A) = H(k_0^G) \oplus k_0^G \oplus H(k_0^G) = k_0^G = k_{0\wedge r}^G. $$

If $a = 1$, we have $k^A = k_1^A$, Edmond then computes

$$ (H(k_1^G) \oplus k_r^G) \oplus H(k^A) = H(k_1^G) \oplus k_r^G \oplus H(k_1^G) = k_r^G = k_{1\wedge r}^G. $$

Edmond indeed computed $k_{a\wedge r}^G$.

**B - Evaluator's half gate.** In the second half gate, Edmond can retrieve $b \oplus r$ without learning information about $r$. Indeed, if $b = 0$, $b \oplus r = r = p(k_0^E)$ by definition while if $b = 1$, $b \oplus r = \bar{r} = p(k_1^E)$. Hence, $s = b \oplus r = p(k_0^E)$, allowing Edmond to retrieve $s$ without knowing $b$. The process for the evaluator half gate is trickier as Edmond has to behave differently according to $s$. First, Gisele computes $H(k_r^B) \oplus k_0^E$ as the first ciphertext and $H(k_{1-r}^B) \oplus k_0^G \oplus k_0^E$ as the second ciphertext. When evaluating, Edmond extracts $s$ based on select bit of his key.

**Correctness.** If $s = b \oplus r = 0$, Edmond takes the first ciphertext and computes

$$ (H(k_r^B) \oplus k_0^E) \oplus H(k_b^B) = k_0^E = k_{a\wedge 0}^E. $$

If $s = b \oplus r = 1$, he takes the second ciphertext and computes

$$ (H(k_{1-r}^B) \oplus k_0^G \oplus k_0^E) \oplus H(k_b^E) \oplus k_0^G \oplus a\Delta = k_0^E \oplus a\Delta = k_{a\wedge 1}^E. $$

Edmond indeed computed $k_{a\wedge(b\oplus r)}^E$.

**C - Two halves make a whole.** The final step for Edmond consists in computing $k_{out} = k^G \oplus k^E$. Table 2.11 shows the correctness of the HalfGates optimization.

<table><caption>Figure 2.11: Correctness table for the HalfGates optimization</caption><thead><tr><th>a</th><th>b</th><th>r</th><th>k<sup>G</sup><sub>a∧r</sub></th><th>k<sup>E</sup><sub>a∧(b⊕r)</sub></th><th>k<sub>out</sub></th><th>a∧b</th></tr></thead><tbody><tr><td rowspan="4">0</td><td rowspan="2">0</td><td>0</td><td>k<sub>0</sub><sup>G</sup></td><td>k<sub>0</sub><sup>E</sup></td><td>k<sub>0</sub><sup>G</sup> ⊕ k<sub>0</sub><sup>E</sup> = k<sub>0</sub><sup>out</sup></td><td>0</td></tr><tr><td>1</td><td>k<sub>0</sub><sup>G</sup></td><td>k<sub>0</sub><sup>E</sup></td><td>k<sub>0</sub><sup>G</sup> ⊕ k<sub>0</sub><sup>E</sup> = k<sub>0</sub><sup>out</sup></td><td>0</td></tr><tr><td rowspan="2">1</td><td>0</td><td>k<sub>0</sub><sup>G</sup></td><td>k<sub>0</sub><sup>E</sup></td><td>k<sub>0</sub><sup>G</sup> ⊕ k<sub>0</sub><sup>E</sup> = k<sub>0</sub><sup>out</sup></td><td>0</td></tr><tr><td>1</td><td>k<sub>0</sub><sup>G</sup></td><td>k<sub>0</sub><sup>E</sup></td><td>k<sub>0</sub><sup>G</sup> ⊕ k<sub>0</sub><sup>E</sup> = k<sub>0</sub><sup>out</sup></td><td>0</td></tr><tr><td rowspan="4">1</td><td rowspan="2">0</td><td>0</td><td>k<sub>1</sub><sup>G</sup> = k<sub>0</sub><sup>G</sup> ⊕ Δ</td><td>k<sub>1</sub><sup>E</sup> = k<sub>0</sub><sup>E</sup> ⊕ Δ</td><td>k<sub>1</sub><sup>G</sup> ⊕ k<sub>1</sub><sup>E</sup> = k<sub>0</sub><sup>G</sup> ⊕ Δ ⊕ k<sub>0</sub><sup>E</sup> ⊕ Δ = k<sub>0</sub><sup>out</sup></td><td>0</td></tr><tr><td>1</td><td>k<sub>1</sub><sup>G</sup></td><td>k<sub>1</sub><sup>E</sup> = k<sub>0</sub><sup>E</sup> ⊕ Δ</td><td>k<sub>0</sub><sup>G</sup> ⊕ k<sub>1</sub><sup>E</sup> = k<sub>0</sub><sup>G</sup> ⊕ k<sub>0</sub><sup>E</sup> ⊕ Δ = k<sub>0</sub><sup>out</sup> ⊕ Δ = k<sub>1</sub><sup>out</sup></td><td>1</td></tr><tr><td rowspan="2">1</td><td>0</td><td>k<sub>1</sub><sup>G</sup></td><td>k<sub>1</sub><sup>E</sup></td><td>k<sub>1</sub><sup>G</sup> ⊕ k<sub>0</sub><sup>E</sup> = k<sub>0</sub><sup>G</sup> ⊕ Δ ⊕ k<sub>0</sub><sup>E</sup> = k<sub>0</sub><sup>out</sup> ⊕ Δ = k<sub>1</sub><sup>out</sup></td><td>1</td></tr><tr><td>1</td><td>k<sub>1</sub><sup>G</sup></td><td>k<sub>0</sub><sup>E</sup></td><td>k<sub>1</sub><sup>G</sup> ⊕ k<sub>0</sub><sup>E</sup> = k<sub>0</sub><sup>G</sup> ⊕ Δ ⊕ k<sub>0</sub><sup>E</sup> = k<sub>0</sub><sup>out</sup> ⊕ Δ = k<sub>1</sub><sup>out</sup></td><td>1</td></tr></tbody></table>

We have seen that the garbler generates two ciphertexts by AND gate. However, for each AND gate, Gisele can use the Garble Row Reduction 3 optimization and set $k_0^G = H(k_0^A)$ making the first ciphertext of the garbler half gate equal to zero. Similarly, by setting $k_0^E = H(k_1^B)$, the first ciphertext of the evaluator half gate is zero. As a consequence, Zahur et al. reduce communication cost to two ciphertexts by AND gate while remaining compatible with the FreeXOR optimization.
<table><caption>Table 2.9: Garbled tables - With HalfGates optimization</caption><tr><td>H(k<sub>1</sub><sup>A</sup>) &oplus; k<sub>r</sub><sup>D</sup></td></tr><tr><td>H(k<sub>1-r</sub><sup>B</sup>) &oplus; k<sub>0</sub><sup>D</sup> &oplus; H(k<sub>r</sub><sup>B</sup>)</td></tr></table>

### 2.8.2.4 From honest-but-curious to malicious Security

The evaluator does not really know if the circuit garbled by Gisele is exactly the one she was supposed to garble. She may act maliciously and garble a circuit leaking information about Edmond's input or direct the result in a way benefiting her.

**Circuit Consistency.** Hence, to provide circuit consistency, one may use the Cut & Choose technique [LP07]. This technique constrains the garbler to generate and send $\lambda$ circuits $\tilde{C}_1, \dots, \tilde{C}_\lambda$. Then, the evaluator generates $\sigma \leftarrow \$ \{0, 1\}^\lambda$ and asks Gisele to prove the subset of circuits $\{\tilde{C}_i \text{ s.t. } \sigma_i = 1\}$ by sending him the randomness she uses for garbling. Using the randomness received from Gisele, Edmond verifies the circuits he received. If they are all valid, Gisele and Edmond proceed normally with the remaining circuits. The final output is the majority output. Hence, as each circuit is checked with probability $\frac{1}{2}$, Gisele can cheat with probability $2^{-\lambda/2}$.

However, guaranteeing circuit consistency is not enough to prevent malicious attacks. Indeed, Gisele may also manipulate the inputs. We now show how to prevent input inconsistency.

**Input Consistency.** On the remaining circuits, Gisele may provide different inputs for each circuit. Taking the example of a circuit computing an inner product, Gisele sets her input to the $i$-th circuit as a vector of 0 except a 1 at $i$-th position such that the output is the $i$-th bit of Edmond's input. Hence, Gisele knows if Edmond's input contains more 0's or more 1's. To counteract this input consistency, one may use commitments, MAC or hash functions.

Lastly, Gisele may set Edmond's input labels such that the evaluation fails depending on Edmond's input. The solution [LP07] to counter the attack is to modify Edmond's input using error correcting codes. This solution has an impact on the circuit size and does not prevent from selective failure, but it avoids Gisele to extract information on Edmond's input.

## 2.9 Universal Composability

Consider a protocol between $n$ parties denoted $P_1, \dots, P_n$, with inputs $x_1, \dots, x_n$ and respective outputs $(y_1, \dots, y_n)$. In an *Ideal World*, we can imagine a trusted third party, called a *Functionality* and denoted $\mathcal{F}$. As $\mathcal{F}$ is trusted by all parties, they can privately send it their respective inputs. Then, $\mathcal{F}$ executes the protocol and returns the outputs to the respective parties. We denote by $\phi$ the protocol in such an ideal world.

However, in the real world, we can not rely on such a trusted third party. We have to consider the potential attacks made by an adversary $\mathcal{A}$. Therefore, the aim of a protocol running in the real world is to act similarly to the functionality running in the ideal world. As the adversary is part of the protocol, the distinguisher in this case is the environment, denoted $\mathcal{Z}$. The environment chooses the inputs $x_1, \dots, x_n$ of the parties $P_1, \dots, P_n$ and then has to distinguish between an execution of $\Pi$ with the adversary $\mathcal{A}$ that has access to the communication between the parties but not their inputs nor outputs, and the execution of $\phi$ with an ideal adversary $\mathcal{S}$ interacting solely with the functionality $\mathcal{F}$.
Definition 2.34 - UC-emulation

We say that a protocol $Π$ UC-emulates the protocol $φ$ if for any real adversary $A$ there exists an ideal simulator $S$ such that for all environments $Z$ we have:

$$UC-EXEC_{\phi,S,Z} \approx UC-EXEC_{\pi,A,Z}$$

and a protocol $Π$ UC-realizes an ideal functionality $F$ if $Π$ UC-emulates the ideal protocol for $F$.

We represent in Figure 2.12 the Ideal/Real world paradigm represented by an execution of both the ideal and real protocol, and their interactions with their respective adversary $S$ and $A$, and the communication with the environment $Z$.

<figure><img src="image_22.png" /><figcaption>Figure 2.12: The Real/Ideal World paradigm, inspired from [GMP$^{+}$08]</figcaption></figure>

If the protocol $Π$ UC-realizes the functionality $F$ only if it is composed with a protocol $Π'$ that UC-realizes the functionality $F'$, we say that the protocol $Π$ UC-realizes $F$ in the $F'$-hybrid model.

## 2.10 Decision forest

Machine Learning (ML) is a branch of Artificial Intelligence giving algorithms the ability to learn from data and therefore improve their accuracy with the time. It is widely used nowadays by example for facial or vocal recognition, meteorological predictions, traffic... A popular technique to achieve Machine Learning is to use Decision Trees. A Decision Tree consists in branches, decision nodes and decision leaves. A decision node contains a predicate, taking a sample as input and outputting either **false** or **true**. According to the output of this predicate, the sample is directed to the corresponding next decision node, or decision leaf. When a sample reaches a decision leaf, it gets associated to a prediction. Either this prediction is a label (YES/NO, brands, animal species, etc...) and the decision tree is a classification tree, either the prediction is a value (house price, drive length, etc...) and the decision tree is a regression tree. In Figure 2.13, we build a decision tree answering the question: "Is it worth to take some time looking for a funny Decision Tree example?"

We call *depth* of the tree the maximum number of nodes from the root to a leaf. In Figure 2.13, the depth of the tree is 3.

A Decision Forest consists in a set of Decision Trees. Each tree returns a label, and the global label is the value returned a maximum number of time. However, if all trees of the forest are trained on the same database, they will all be very similar leading to *overfitting*. When a model
<figure><img src="image_23.png" /><figcaption>Figure 2.13: Decision Classification Tree deciding if it is worth to take some time looking for a funny Decision Tree Example. Blue boxes denote decision nodes, green and red boxes denote decision nodes.</figcaption></figure>

overfits a set of data, it corresponds too closely to a particular set of data and can make future prediction erroneous.

<figure><img src="image_24.png" /><figcaption>Figure 2.14: Representation of a good fitting and overfitting (LATEX code from Tex StackExchange)</figcaption></figure>

Overfitting may happen if the tree is too deep, making the model very specific to the training data. To overcome this problem, an idea is to select random features and random observations. Choosing random observations is named *tree bagging* while choosing random features is named *feature sampling*. By mutual agreement, with a database of *m* observations × *n* features, we sample (with replacement) √*m* observations and √*n* features. In Figure 2.15, we take the example of a 4 × 9 database. The tree bagging operation results in a 2 × 9 database, then after the feature sampling, we retrieve the final training dataset (in green), with size 2 × 4, as due to draw replacement, a column has been drawn twice.

<figure><img src="image_25.png" /><figcaption>Figure 2.15: Database Sampling. The final training dataset is in green</figcaption></figure>
# Chapter 3

## Secure decision forest evaluation

This chapter describes a protocol to securely evaluate binary decision trees, that are decision trees with binary outcome. Initially, this project has been motivated by the will to add a cryptographic layer to an already existing continuous authentication protocol based on Machine Learning. In continuous authentication, users are authenticated using a set of features that strengthen usual authentication credentials such as passwords or security tokens. When the user's identity needs to be validated after some time interval or after some inactivity, continuous authentication offers a user-friendly experience as it avoids interrupting legitimate users and reduces the number of times they have to authenticate explicitly. The usual scenario of continuous authentication consists of a server authenticating users based on behavioral biometrics. A variety of features such as keystroke patterns, swiping gestures and scrolling duration are collected on the user's device and sent to the server. The server then evaluates the client inputs with respect to its model in order to make an authentication decision. The model is usually generated during a training step using a dedicated training dataset.

It goes without saying that adding a privacy layer to such a protocol finds more applications than continuous authentication. Indeed, over the past years, companies have tremendously increased the amount of data they collect from their users. These data are often feed to machine learning algorithms in order to turn them into valuable business insights that are used to develop innovative services. In addition to continuous authentication, other applications include fraud detection in banking systems, recommendation services as well as spam detection. Collecting and processing these data raises privacy concerns since they generally contain sensitive information regarding users. Besides, the models used to evaluate these data may contain critical business information that also need to be protected. We consider the general case where a client who holds sensitive data interacts with a server who holds a decision forest model in order to jointly evaluate the client inputs with respect to the server model. Our goal is to ensure that the privacy of both the client and the server are guaranteed on their respective inputs. We also investigate the scenario where the client is malicious and intends to bias the outcome of the protocol.

The work presented in this chapter led to a publication in the 16th International Conference on Availability, Reliability and Security (ARES21):

★ 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

<figure><img src="image_26.png" /></figure>
# Contents

<table><tr><td>3.1</td><td>Honest-but-curious client and server</td><td>56</td></tr><tr><td>3.1.1</td><td>Model encoding</td><td>56</td></tr><tr><td>3.1.2</td><td>Evaluation description</td><td>57</td></tr><tr><td>3.1.3</td><td>Protocol security</td><td>57</td></tr><tr><td>3.2</td><td>Malicious client and honest-but-curious server</td><td>61</td></tr><tr><td>3.2.1</td><td>Model encoding</td><td>62</td></tr><tr><td>3.2.2</td><td>Protocol overview</td><td>63</td></tr><tr><td>3.2.3</td><td>Formal description</td><td>64</td></tr><tr><td>3.2.4</td><td>Protocol security</td><td>67</td></tr><tr><td>3.3</td><td>Performances and applications</td><td>72</td></tr><tr><td>3.3.1</td><td>Storage and bandwidth costs</td><td>72</td></tr><tr><td>3.3.2</td><td>Comparison with related works</td><td>74</td></tr><tr><td>3.4</td><td>Application to continuous authentication and spam filtering</td><td>75</td></tr></table>

# Notations

In addition to global notations, we list here the notations used in the chapter

## Decision Trees Notations

M Model on the server

C Encoding of the model

P Number of paths

δ (Max) depth of the paths

ν Feature range ([0 .. 2^ν − 1])

τ Global threshold

pᵢ Polarity of the i-th path

(tᵢⱼ) Threshold in the j-th node of the i-th path

(vᵢⱼ) Orientation of the comparison of the j-th node of the i-th path

(xᵢⱼ) Feature of the comparison of the j-th node of the i-th path

## Garbled Circuits Notations

C Garbling of circuit C.

T Garbled Circuits input labels

T Transition tables

D Output labels

## Other

ζ NIZK proofs

[[ m ]] Encryption of m
## 3.1 Honest-but-curious client and server

The first step of the protocol elaboration was to find the best way to encode the model while keeping privacy and being efficient. The model can be sent offline, and used multiple times. We can imagine for example the model updating itself each morning and is then usable online the whole day by the user.

### 3.1.1 Model encoding

As one of our requirements is a client-side computation, we first have to find the best way to represent and encode the decision forest. The first observation is that saving the structure of the tree implies leakage of the order of the required feature. Indeed, when evaluating, the first used feature would be the feature at the root of the tree and this violates the server privacy. Leaking used feature is an acceptable leakage, but leaking the position of the node in the tree in which the feature is used is a higher leakage, and we do not consider it as acceptable. Thus, we choose to "decompose" the tree as set of paths. Hence, rather than direct a sample through the correct nodes, to reach a single leaf, the sample will go through all possible paths leading to a leaf deciding 1. Indeed, as we consider binary output decision trees, only considering paths with label 1 is equivalent to evaluate the whole tree. Before encoding, we assume that the model has been computed on a normalized database, where each value is a positive integer smaller than $2^\nu$. In this chapter, we use the well-known iris database classing iris species, as an example. We consider a petal with length $\ell$ and width $w$ as features. Width goes from 0.1 cm to 2.5 cm and length from 1 cm to 6.9 cm. We thus normalize by defining $L$ as $(10(\ell - 1))$ and $W$ as $20w$ leading to integer values in $[0..63 = 2^6 - 1]$. The model is trained to decide if a sample corresponds to the virginica species or not. Figure 3.1 shows the transition from the classical representation of a decision tree, to our representation for its encoding with the iris database example.

<figure><img src="image_27.png" /><figcaption>Figure 3.1: Decision tree representation for the normalized Iris database, in the Honest-but-Curious setting.</figcaption></figure>

Now, we define $P$ as the number of paths of which label is 1 and $\delta$ as the depth of the deepest path, and for each path $i$, and each node at depth $j$ of path $i$, we define as $x_{i,j}$ the value of the feature, that will be compared to a threshold $t_{i,j}$ according to $v_{i,j}$, the orientation of the threshold. More precisely, we have $v_{i,j} = 1$ when the expected result is $x_{i,j} \le t_{i,j}$ and $v_{i,j} = 0$ otherwise. This allows us to define a model $\mathcal{M}$ as $\mathcal{M} = (P, \delta, \nu, \tau, (t_{i,j}, v_{i,j})_{i \in [P], j \in [\delta]})$.

Then, we use an Additive Homomorphic Encryption AHE = (Setup, KGen, Enc, Dec) with plaintexts in $\mathbb{Z}_q$, and define an additional algorithm MultScal such that, given the security parameter $1^\kappa$, with $\text{param} \leftarrow \text{Setup}(1^\kappa)$, $(\text{pk}, \text{sk}) \leftarrow \text{KGen}(\text{param})$, $\alpha \in \mathbb{Z}_q$ and a ciphertext $c_1 \leftarrow \text{Enc}(\text{pk}, m_1)$, MultScal($\text{pk}, \alpha, c_1$) returns an encryption of $\alpha \cdot m_1$. Finally, for each $i \in \mathfrak{S}_P$, $j \in \mathfrak{S}_\delta$, a ciphertext $C_{i,j}^k$ is computed for each comparison node $(i, j)$ and each possible input value $k \in [2^\nu]$ as follows:
$$C_{i,j}^k = \begin{cases} \text{AHE.Enc(pk, } 1 - v_{i,j}) = \llbracket 1 - v_{i,j} \rrbracket & \text{if } k \le t_{i,j}; \\ \text{AHE.Enc(pk, } v_{i,j}) = \llbracket v_{i,j} \rrbracket & \text{otherwise.} \end{cases}$$

As $v_{i,j} = 1$ when the expected comparison result is $(x_{i,j} \le t_{i,j})$ and $v_{i,j} = 0$ otherwise, $C_{i,j}^k$ is a ciphertext of 0 (respectively a ciphertext of 1) whenever the input value $k$ satisfies (respectively does not satisfy) the comparison. One can see that the number of $C_{i,j}^k$ ciphertexts is exponential with respect to $\nu$, but we stress that one only needs a few bits of precision in order to get a meaningful outcome. This number is thus linear in the number of comparisons in practice. The whole process described above is defined as the EncodeModel algorithm, taking the homomorphic encryption public key pk and a model $\mathcal{M}$ as input and returning $\mathcal{C} = \{C_{i,j}^k\}_{k \in [2^\nu]_{i \in [P], j \in [\delta]}}$.

We now describe the remaining of the protocol, step by step.

### 3.1.2 Evaluation description

Once the client is in possession of an encoded model $\mathcal{C}$, he will evaluate a new sample $x = (x_{i,j})_{i \in [P], j \in [\delta]}$, where $x_{i,j}$ is a $\nu$-bits value, by evaluating it path after path. When evaluating the path $i \in [P]$, for each comparison $j \in [\delta]$ of the path, the client sets $[[S_{i,j}]] = C_{i,j}^{x_{i,j}}$. Then he computes the homomorphic sum of the comparisons: $[[S_i]] = \bigoplus_j [[S_{i,j}]]$. This evaluation algorithm is denoted by EvaluatePaths which takes as input the public homomorphic key pk, the client input $x$, an encoded model $\mathcal{C}$ and returns $\mathcal{S}$, the set of the encryptions $[[S_i]]$ of the score of the $i$-th path. If all the comparisons of a path are valid, then $[[S_i]]$ is an encryption of 0. Otherwise, if at least one comparison fails, $[[S_i]]$ encrypts a value in $[1..\delta]$.

Sending the ciphertexts $\mathcal{S}$ as they are, would lead to some leakage. Indeed, the server would learn the score of each branch. By consequent, the next algorithm consists in the randomization of the scores. In reality, two randomizations are required. Indeed, the scores need to be randomized, and the paths need to be permuted. No permutation would allow the server to learn which path is valid, and which are not, while no randomization of the score, even if paths are permuted, leaks the mean score of the client. Thus, the client first samples $\pi \leftarrow_S \mathcal{G}_P$ and $(\alpha_i)_{i \in [P]}$, then for $i \in [1..P]$, he sets $[[\tilde{S}_i]] = \text{MultScal}(\text{pk}, \alpha_i, [[S_{\pi(i)}]]) = [[\alpha_i \cdot S_{\pi(i)}]]$. We denote this algorithm by RandomizeScores, taking the public encryption key pk and the ciphertext set $\mathcal{S}$ and returns $\tilde{\mathcal{S}}$, the set of randomized and permuted ciphertexts.

We depicted the evaluation (without the final randomization) with the example of the iris database in Figure 3.2. Ciphertexts crossed by samples are homomorphically added. Samples crossing only green ciphertexts therefore result in an encryption of 0, while ciphertexts crossing at least one red ciphertext returns a non-null value. Once randomized, encryption of zeros remains encryption of zeros, while encryption of non-zero values become encryption of random values.

Now, encryptions are sent to the server, who evaluates the model. To do this, he decrypts each ciphertext in $\tilde{\mathcal{S}}$ and counts those decrypting as 0 to retrieve the amount of successful paths $\mathcal{S}$ and thus, makes a decision according to a threshold $\tau$. More precisely, if $\mathcal{S} > \tau$, the server returns accept and returns reject otherwise. This final algorithm is denoted EncodeModel and takes the secret homomorphic encryption key sk, the set $\tilde{\mathcal{S}}$ of randomized ciphertexts and the threshold $\tau$, and returns a label in $\{\text{accept, reject}\}$.

The resulting protocol in the Honest-but-Curious setting is formalized represented in Figure 3.3.

### 3.1.3 Protocol security

In this section, we first show the correctness and soundness of our protocol. We then provide a proof of both the client and server privacy.
<figure><img src="image_28.png" /><figcaption>Figure 3.2: Client-side evaluation phase (before randomization) with four normalized samples. From left to right: iris-setosa, iris-versicolor, iris-virginica, iris-virginica. Encryptions of 1 are represented with red boxes whereas encryptions of 0 are represented with green boxes.</figcaption></figure>

**Correctness and Soundness.** The correctness of our protocol directly follows from the construction of the ciphertexts. If all the comparisons are correct, each $S_{i,j}$ is equal to 0 and the sum $S_i$ equals 0 (correctness). Otherwise, at least one $S_{i,j}$ equals 1 and $S_i$ does not equal 0 (soundness). After the client randomizes the $S_i$, zeros are still zeros, while other $S_i$ become random values. When decrypting, the server counts the zeros. The threshold $\tau$ is applied for the final decision.

**Client Privacy.** An honest-but-curious server should not learn any information on the client samples, except what it can learn from the outcome, namely the number of successful paths (See Figure 3.3, on the left). We thus consider the following adversary $\mathcal{A}$ against the privacy of the client: $\mathcal{A}$ first chooses a model $\mathcal{M}$ for the server and two sets of possible inputs $(\mathbf{x}_0, \mathbf{x}_1)$ for the client. It also provides the random tape $\rho$ of the server. The adversary sees the transcript between a server using $\mathcal{M}$ and $\rho$, and a client using $\mathbf{x}_b$ for a random bit $b$, and it should guess $b$. There is the natural restriction that $\mathcal{M}(\mathbf{x}_0) = \mathcal{M}(\mathbf{x}_1)$. The random tape $\rho$ will be used by the server for encoding the model $\mathcal{M}$. In the client-privacy security game (see Figure 3.4), we denote the advantage of any adversary $\mathcal{A}$ by

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

In our scheme, the client privacy is provided thanks to the permutation and randomization of the encrypted scores. From the expected outcome, one can encrypt the correct number of 0, and the other values are non-zero random values. One can then randomize and permute them. This is indistinguishable from the server point of view. The server then only learns the number of successful paths. But we have to formally prove it.

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