## 2.6 Conclusion

Dans ce chapitre, nous avons proposé une solution de masquage qui fait partie de la famille DSM. Cette solution, en plus de permettre de masquer les deux opérations d'addition et de multiplication, permet également de détecter et de corriger les erreurs. En terme de performance algorithmique, il s'agit d'un masquage de complexité linéaire, donc compatible avec les composants à faible capacité, en particulier les objets connectés ou les IoTs (Internet of Things). La génération d'un masque aléatoire est souvent une opération coûteuse, dans ce schéma le masque de taille $8n$ est généré à partir d'une graine de taille 8 bits.

Pour mesurer la résistance de ce schéma, nous lui avons fait subir l'attaque de BRUNEAU et al. [BGH+16] qui consiste à chercher une corrélation entre le poids de HAMMING du masque choisi et toutes les valeurs possibles. D'après les résultats (Figure 2.2), bien que le masque PDSM soit généré à partir d'une graine de 8 bits (r), il reste plus résistant qu'un masquage classique d'ordre 2, et légèrement moins résistant par rapport à IPM (le masquage basé sur le produit scalaire) et SSM (le masquage basé sur le partage du secret). Cependant, il sera intéressant pour la suite d'étudier une version généralisée de ce schéma, en ajoutant plusieurs masques afin d'obtenir une meilleur résistance face aux attaques à l'ordre supérieur dans le modèle probing.
# Deuxième partie

## LA CRYPTOGRAPHIE BASÉE SUR L'IDENTITÉ
<figure><img src="image_29.png" /></figure>
# 1 | Introduction

## Sommaire

<table><tr><td>1.1</td><td>Rappels sur la théorie des groupes</td><td>92</td></tr><tr><td>1.2</td><td>Les courbes elliptiques</td><td>94</td></tr><tr><td>1.2.1</td><td>Définition</td><td>94</td></tr><tr><td>1.2.2</td><td>Les formules d'addition et doublement</td><td>95</td></tr><tr><td>1.2.3</td><td>Le groupe de torsion</td><td>96</td></tr><tr><td>1.2.4</td><td>Le couplage sur les courbes elliptiques</td><td>97</td></tr><tr><td>1.2.5</td><td>L'échange des clés à trois</td><td>98</td></tr><tr><td>1.2.6</td><td>La signature courte</td><td>98</td></tr><tr><td>1.3</td><td>Le schéma de Boneh et Franklin</td><td>99</td></tr><tr><td>1.3.1</td><td>Les avantages du schéma de Boneh et Franklin (BF-IBE)</td><td>100</td></tr><tr><td>1.3.2</td><td>Le schéma BF-IBE</td><td>100</td></tr><tr><td>1.3.3</td><td>La sécurité du schéma BF-IBE</td><td>102</td></tr><tr><td>1.3.4</td><td>L'enrôlement et la mise à jour des clés</td><td>105</td></tr><tr><td>1.4</td><td>Critiques et améliorations</td><td>105</td></tr><tr><td>1.4.1</td><td>Émission sécurisée des clés</td><td>106</td></tr><tr><td>1.4.2</td><td>Conclusion</td><td>109</td></tr></table>
Nous allons consacrer ce chapitre à l'étude du schéma IBE de BONEH et FRANKLIN, premier schéma efficace de chiffrement basé sur l'identité. Pour commencer, nous allons d'abord rappeler quelques notions de base sur la théorie des groupes, et en particulier sur les courbes elliptiques. Ensuite, nous allons utiliser ces outils pour expliquer le fonctionnement du schéma BF-IBE (en anglais : *Boneh and Franklin Identity Based Encryption*). Nous allons également présenter quelques améliorations qui ont été proposées par la communauté pour balayer les critiques qu'a subi le schéma.

## 1.1 Rappels sur la théorie des groupes

La construction des cryptosystèmes à clé publique tels que IBE ou RSA est souvent liée aux propriétés que l'on trouve dans la théorie des groupes. Dans cette section, nous allons faire quelques rappels sur les bases de la théorie des groupes.

**Définition 26 (Un groupe)**

Un groupe $(G, *)$ est un ensemble $G$ auquel est associée une opération $*$ (appelée aussi “la loi de composition”) vérifiant les quatre propriétés suivantes :

- $\forall x, y \in G, \quad x * y \in G;$

- $\forall x, y, z \in G, \quad x * (y * z) = (x * y) * z;$

- Il existe un élément neutre $e \in G$ tel que $\forall x \in G, \quad x * e = x;$

- $\forall x \in G, \text{ il existe un élément inverse } x^{-1} \text{ tel que } x * x^{-1} = e.$

Si en plus l'opération $*$ est commutative ($x*y = y*x$), on dit que $G$ est un groupe abélien.

**Propriété 17**

Voici quelques propriétés de base sur les groupes :

- L'élément neutre $e$ est unique. En effet, s'il existe un autre élément neutre $e'$, alors : $e' * e = e = e'$;

- L'inverse de l'élément neutre est lui-même;

- Chaque élément de $G$ possède un seul inverse. En effet, s'il existe deux inverses $x_1$ et $x_2$ pour un seul élément $x$, alors : $x_1 * (x * x_2) = x_1 * e = x_1 = (x_1 * x) * x_2 = e * x_2 = x_2$.

**Définition 27 (Un sous-groupe)**

Une partie $H \subset G$ est un sous-groupe de $G$ si :

- $e \in H$;

- pour tout $x, y \in H$, on a $x * y \in H$;

- pour tout $x \in H$, on a $x^{-1} \in H$.

**Propriété 18**

Soit $H$ un sous-groupe de $G$, et $r, s$ deux éléments de $G$. Nous avons : $Hr = Hs$
(respectivement $rH = sH$) si et seulement si : $r * s^{-1} \in H$ (respectivement $s^{-1} * r \in H$). Sinon, $Hr$ et $Hs$ (respectivement $rH$ et $sH$) n'ont aucun élément en commun.

**Preuve :**

Nous avons :

$$ 
\begin{align*}
Hr = Hs &\implies r \in Hs \\
&\implies \exists h \in H \mid h * s = r \\
&\implies h = r * s^{-1} \in H.
\end{align*}
$$

$$ 
\begin{align*}
r * s^{-1} \in H &\implies H(r * s^{-1}) = H \\
&\implies (Hr)s^{-1} = H \\
&\implies Hr = Hs.
\end{align*}
$$

Supposons qu'il existe un élément commun $h \in Hr \cap Hs$, alors, il existe $h_1, h_2 \in H$ tels que : $h_1 * r = h_2 * s = h$ ce qui implique que : $r = h_1^{-1} * h_2 * s$, donc $r * s^{-1} = h_1^{-1} * h_2 \in H$ ce qui signifie que $Hr = Hs$ par le premier résultat. ■

**Définition 28 (L'ordre du groupe)**

Un groupe est dit fini si le nombre de ses éléments est fini. Dans ce cas, son cardinal est appelé l'ordre du groupe, il est noté $|G|$.

**Définition 29 (L'ordre d'un élément)**

L'ordre d'un élément $x \in G$ est le plus petit entier $n$ tel que $x * \cdots * x = x^n = e$. $$ \underbrace{x * \cdots * x}_{n \text{ fois}} = x^n = e $$

**Théorème 4 (Théorème de LAGRANGE)**

L'ordre d'un élément $x \in G$ divise toujours l'ordre de $G$.

**Preuve :**

Il suffit de démontrer que l'ordre du sous-groupe généré par $x$ divise l'ordre de $G$. Notons $H$ le sous-groupe généré par $x$ (i.e. $H = \{x^i \mid 1 \le i \le \text{ordre}(x)\}$). Soit $r_1 \in G$, nous avons $|Hr_1| = |H|$, et soit $r_2 \in G \setminus Hr_1$, d'après la propriété 18, $Hr_1$ et $Hr_2$ dont disjoints, i.e. $|Hr_1 \cup Hr_2| = 2|H|$. De la même manière, nous pouvons continuer à choisir un $r_i \in G \setminus Hr_1 \cup Hr_2 \cup \cdots \cup Hr_{i-1}$ jusqu'à un certain entier $i = n$ tel que : $|G| = n|H|$ avec $G = Hr_1 \cup \cdots \cup Hr_n$. ■

**Définition 30 (Un groupe cyclique)**

Un groupe $G$ est dit cyclique s'il existe un élément $g \in G$ tel que : $\forall x \in G$, il existe un entier $n$ vérifiant $x = g^n$. Dans ce cas, $g$ est appelé générateur du groupe $G$.
## Définition 31 (Un anneau)

Un anneau est un ensemble non vide $A$ muni de deux lois de composition internes, l'une notée comme une addition et l'autre comme une multiplication, vérifiant les propriétés suivantes :

- $A$ est un groupe abélien pour l'addition (on note $0$ son élément neutre);

- La multiplication est associative : $\forall x, y, z \in A, (xy)z = x(yz)$;

- La multiplication est distributive par rapport à l'addition (à gauche et à droite) : $\forall x, y, z \in A, x(y+z) = xy + xz$ et $(x+y)z = xz + yz$;

- Si en plus la multiplication est commutative ($xy = yx$) alors on dit que $A$ est *commutatif*;

- On dit que $A$ est *unitaire* si en plus la multiplication admet un élément neutre (que l'on note 1).

## Définition 32 (Un sous-anneau)

Soit $A$ un anneau. On appelle sous-anneau de $A$ toute partie non-vide $B$ de $A$ qui vérifie les deux conditions suivantes :

- $B$ est un sous-groupe du groupe additif de $A$;

- Pour tout $x, y \in B$ on a $xy \in B$.

## Définition 33 (Un corps)

On appelle corps commutatif (ou plus simplement corps) tout anneau commutatif unitaire dans lequel tout élément non-nul est inversible.

## 1.2 Les courbes elliptiques

### 1.2.1 Définition

La première utilisation des courbes elliptiques en cryptographie remonte au milieu des années 80, lorsque MILLER [Mil85] puis KOBLITZ [Kob87] ont proposé indépendamment les courbes elliptiques comme outils pour la cryptographie.

#### Définition 34 (Une courbe elliptique)

Une courbe elliptique $E$, définie sur un corps fini $\mathbb{F}$ dont la caractéristique est différente de 2 et 3, est un ensemble “de points” défini par :

$$E = \{(x, y) \in \mathbb{F}^2 \mid y^2 = x^3 + ax^2 + b\} \cup \{P_{\infty}\},$$

tel que : $\Delta = 4a^3 + 27b^2 \neq 0$.

$P_{\infty}$ est un élément supplémentaire appelé *point à l'infini* de la courbe.

Les courbes elliptiques ont une structure de groupe qui constitue un remplacement idéal pour les groupes traditionnels basés sur la théorie des nombres, tels que Diffie-Hellman ou ElGamal. Une courbe elliptique $E$ sur un corps fini $\mathbb{F}$ est munie d'une
structure de groupe abélien dont l'élément neutre est le point à l'infini. On peut définir une opération d'addition de points (notée +) de la façon suivante :

- $\forall P \in E, P + P_{\infty} = P$;

- L'opposé de $P = (x, y) \in E$ est défini par $-P = (x, -y)$;

- Soient $P$ et $Q$ deux points de la courbe $E$, la droite passant par $P$ et $Q$ (ou la tangente sur $P$ si $P = Q$) recoupe la courbe $E$ en un troisième point $R \in E$, ce dernier est par définition l'opposé de $P + Q$ i.e. $P + Q = -R$.

<figure><img src="image_30.png" /><figcaption>FIGURE 1.1 – Représentation graphique de la courbe : $y^2 = x^3 - 2x + 1$ sur $\mathbb{R}$</figcaption></figure>

### 1.2.2 Les formules d'addition et doublement

Comme le point à l'infini est un élément neutre, nous allons présenter dans cette partie la formule qui permet de calculer la somme de deux points finis d'une courbe. La figure 1.1 montre que la somme de deux points différents $P = (x_P, y_P)$ et $Q = (x_Q, y_Q)$, tels que $x_P \neq x_Q$, est l'opposé du point d'intersection de la droite (PQ) avec la courbe. Ainsi, pour calculer les coordonnées de $P + Q$, nous allons commencer par calculer l'équation la droite (PQ) en fonction des coordonnées de
P et Q. Le coefficient directeur de cette droite est :

$$ \lambda = \frac{y_Q - y_P}{x_Q - x_P}. \qquad (1.1) $$

La droite (PQ) a donc pour équation $y = \lambda x + \mu$ où $\mu = \lambda x_P + y_P$. Elle coupe la courbe E en un troisième point R dont les coordonnées $(x_R, y_R)$ vérifient simultanément :

$$ \begin{cases} y_R = \lambda x_R + \mu & \text{car } R \text{ appartient à la droite (PQ)} \\ y_R^2 = x_R^3 + ax_R + b & \text{car } R \text{ appartient à la courbe E} \end{cases} $$

En résolvant ce système d'équations, on trouve les formules suivantes :

$$ \begin{cases} x_S = \lambda^2 - x_P - x_Q \\ y_S = -\lambda(x_S - x_P) - y_P \end{cases} \qquad (1.2) $$

avec $(x_S, y_S) = (x_R, -y_R) = P + Q$.

Pour calculer le double d'un point P, c'est-à-dire $2P$ (i.e. lorsque $P = Q = (x_P, y_P)$), le raisonnement précédent s'applique également, en considérant la tangente en P sur la courbe. Les formules de l'équation 1.2 restent valables, seule la valeur de $\lambda$ est différente. Dans ce cas, il faudra considérer le coefficient directeur de la tangente qui est donné par l'équation :

$$ \lambda = \frac{3x_P^2 + a}{2y_P}. \qquad (1.3) $$

Le dernier cas qui reste, c'est quand nous avons deux points P et Q qui sont symétriques par rapport à l'axe des abscisses (i.e. $x_P = x_Q$ et $y_P = -y_Q$), dans ce cas nous avons : $P = -Q$ et donc $P + Q = P - P = P_\infty$.

### 1.2.3 Le groupe de torsion

**Définition 35 (Multiplication par un entier)**

Pour tout entier relatif $n$, la multiplication par $n$, notée $[n]$ et définie par : $[n] : P \mapsto nP$, est un morphisme de $E$ vers $E$ (avec $nP = \underbrace{P + \cdots + P}_{n \text{ fois}}$).

**Définition 36 (Groupe de $n$-torsion)**

Pour tout entier $n$, le groupe de $n$-torsion d'une courbe elliptique $E$ est le noyau de l'isogénie de multiplication par $n$, on le note $E[n]$ :

$$ E[n] = \{P \in E \mid nP = P_\infty\}. $$
Le corps $\mathbb{F}$ étant supposé algébriquement clos, le polynôme $x^3 + ax + b$ a trois racines dans $\mathbb{F}$. La courbe étant lisse ($\Delta \neq 0$), ces trois racines sont distinctes. Donc il existe toujours trois points distincts (les points spéciaux) dans $E$, qui sont $P_\alpha = (\alpha, 0)$, $P_\beta = (\beta, 0)$, $P_\gamma = (\gamma, 0)$ tels que : $x^3 + ax + b = (x-\alpha)(x-\beta)(x-\gamma)$. Les points spéciaux se distinguent des autres points de la courbe par le fait d'être les seuls points d'ordre 2.

### 1.2.4 Le couplage sur les courbes elliptiques

La cryptographie basée sur les courbes elliptique est souvent liée aux fonctions bilinéaires admissibles.

**Définition 37 (Fonction bilinéaire admissible)**

Soient $q$ un nombre premier, ($G_1, +$) un groupe fini d'ordre $q$ noté additivement, et ($G_2, \times$) un groupe fini d'ordre $q$ également mais noté multiplicativement. Comme $q$ est premier, ces groupes sont cycliques. On note $P$ un générateur de $G_1$.

Une application $\beta : G_1 \times G_1 \rightarrow G_2$ est dite admissible pour la cryptographie bilinéaire si elle possède les quatre propriétés suivantes :

- Elle est bilinéaire : $\forall P, Q \in G_1, \forall a, b \in \mathbb{Z}, \beta(aP, bQ) = \beta(P, Q)^{ab}$;

- Elle est non dégénérée : $\beta(P, P) \neq 1$;

- Elle est efficacement calculable : il existe un algorithme de complexité polynomiale qui, à partir de $P$ et $Q$ dans $G_1$, calcule la valeur de $\beta(P, Q)$;

- Étant donnés $P, aP, bP$ et $Q$ dans $G_1$, il doit être en pratique impossible de trouver la valeur de $\beta(P, Q)^{ab}$. Cela implique en particulier que le problème du logarithme discret doit être difficile dans $G_1$.

Les deux fonctions bilinéaires admissibles souvent utilisées en cryptographie basée sur les courbes elliptiques sont le couplage de TATE et le couplage de WEIL. La forme originale de ces deux fonctions nécessite des opérations mathématiques complexes. Afin de gagner en performance, beaucoup de schémas cryptographiques ont été conçus en utilisant une notation abstraite de ces fonctions. La sécurité de ces schémas cryptographiques est basée sur le problème BDH (en anglais : *Bilinear Diffie-Hellman Problem*).

La bilinéarité des couplages a permis la construction de protocoles originaux et l'amélioration des protocoles existants :

- L'échange de DIFFIE-HELLMAN entre trois parties (JOUX 2001);

- Les schémas de signature courte (BONEH, LYNN, SHACHAM 2001);

- La cryptographie basée sur l'identité (BONEH et FRANKLIN 2001).
## 1.2.5 L'échange des clés à trois

Nous commençons par le principe classique d'échange de Diffie-Hellman à trois. Soient Alice, Bob et Charlie trois utilisateurs qui veulent échanger une clé secrète commune pour l'utiliser dans un algorithme de chiffrement symétrique. Ils commencent par se mettre d'accord sur le choix d'un groupe de points ($G, +$) d'ordre $p$ et d'un point générateur $P \in G$. Chaque utilisateur va choisir une clé secrète dans $\mathbb{Z}_p : a$ pour Alice, $b$ pour Bob, et $c$ pour Charlie.

- Alice calcule $aP$ et l'envoie à Bob,

- Bob calcule $bP$ et l'envoie à Charlie,

- Charlie calcule $cP$ et l'envoie à Alice.

- Alice obtient $cP$. Elle calcule $acP$ et l'envoie à Bob,

- Bob obtient $aP$. Il calcule $abP$ et l'envoie à Charlie.

- Charlie obtient $bP$. Elle calcule $bcP$ et l'envoie à Alice.

Enfin chaque utilisateur va multiplier la clé reçue par sa clé secrète pour obtenir la clé commune $abcP$ comme illustré dans la figure 1.2.

<figure><img src="image_31.png" /><figcaption>FIGURE 1.2 – Le schéma classique d'échange de clé à trois</figcaption></figure>

JOUX en 2000 a décrit l'échange de DIFFIE-HELLMAN à trois avec un seul tour d'échange [Jou00] en utilisant une fonction bilinéaire admissible $e : G_1 \times G_1 \rightarrow G_2$ :

- Alice envoie $aP$ à Bob et Charlie,

- Bob envoie $bP$ à Alice et Charlie,

- Charlie envoie $cP$ à Alice et Bob.

Chaque utilisateur calculera ensuite la clé commune : $e(bP, cP)^a = e(aP, cP)^b = e(aP, bP)^c = e(P, P)^{abc}$.

## 1.2.6 La signature courte

Pour assurer l'intégrité et l'authentification des messages, des schémas de signatures ont été mis en place. BONEH, LYNN, et SHACHAM [BLS01] ont proposé en 2001 un protocole de signature courte à base de couplage dont les signatures sont assez courtes. Les paramètres du schéma sont :
- Une fonction bilinéaire admissible $e : G_1 \times G_1 \to G_2$;

- Un générateur $P \in G_1$;

- Une fonction de hachage : $\mathcal{H} : \{0, 1\}^* \to G_1$.

Pour signer un message $M$, Alice choisit un secret $a \in \mathbb{Z}_p$ ensuite :

- Elle calcule sa clé publique $aP$;

- Elle calcule $H = \mathcal{H}(M) \in G_1$;

- Elle envoie à Bob le couple : $M, aH$.

Pour vérifier la signature, il suffit de tester l'égalité $e(\mathcal{H}(M), aP) \stackrel{?}{=} e(aH, P)$.

### 1.3 Le schéma de Boneh et Franklin

Dans une infrastructure à clé publique classique, l'existence d'une autorité de certification (CA) est essentielle. Les utilisateurs d'une clé publique doivent s'assurer que la clé secrète associée est possédée par l'entité correcte. Cette assurance peut être fournie en ayant une autorité de certification de confiance qui lie la clé publique d'une entité et son identité sous la forme d'un certificat signé. Si cette signature est valide, alors les données intégrées dans le certificat sont correctes. Comme nous l'avons détaillé dans la partie 1.5.3, la gestion de ces certificats est souvent compliquée à mettre en œuvre et présente plusieurs défauts.

En 2001, BONEH et FRANKLIN ont introduit leur système de chiffrement basé sur l'identité, aussi connu sous le nom IBE (en anglais : *Identity Based Encryption*) [BF01]. Sa mise en œuvre repose sur un groupe de points sur une courbe elliptique (souvent un groupe de $n$-torsion) et la fonction bilinéaire correspondante pour effectuer les calculs nécessaires.

Une architecture IBE est composée de quatre algorithmes principaux :

- **Initialisation** : Prend un paramètre de sécurité $k$ et renvoie les paramètres publics du système et la clé maître. Les paramètres du système comprennent une description d'un espace de messages fini $\mathcal{M}$, une description d'un espace de texte chiffré fini $\mathcal{C}$, les fonctions mathématiques utilisées (la courbe elliptique, la fonction de couplage et la fonction de hachage). Les paramètres du système seront connus publiquement, tandis que la clé maître sera connue uniquement par le générateur de clé privée appelé le PKG (en anglais : *Public Key Generator*).

- **Extraction** : Prend comme paramètres d'entrée la clé maître et une identité $id \in \{0, 1\}^*$, et renvoie une clé secrète associée $S$. L'identité est une chaîne arbitraire qui sera utilisée comme clé publique grâce à une fonction de hachage et $S$ correspond à la clé de déchiffrement privée correspondante. L'algorithme Extraction permet donc d'extraire une clé privée à partir d'une clé publique grâce à la clé maître, ce qui signifie que seul le PKG est capable d'exécuter cet algorithme.
- **Chiffrement** : Prend comme paramètres d'entrée l'identité du destinataire id et le message clair $M \in \mathcal{M}$. Il retourne un texte chiffré $C \in \mathcal{C}$.

- **Déchiffrement** : Prend comme paramètres d'entrée un texte chiffré $C \in \mathcal{C}$ et la clé secrète du destinataire légitime $S$. Il retourne le texte clair $M \in \mathcal{M}$. Ces algorithmes doivent satisfaire la contrainte de cohérence standard, à savoir quand $S$ est la clé secrète générée par l'algorithme Extract quand on lui donne id comme clé publique, alors :

$$ \forall M \in \mathcal{M}, \quad \mathrm{Dec}(\mathrm{Enc}(M, id), S) = M, \qquad (1.4) $$

avec Enc et Dec désignant les algorithmes de chiffrement et déchiffrement respectivement.

## 1.3.1 Les avantages du schéma de Boneh et Franklin (BF-IBE)

Le principal avantage d'un IBE est qu'il permet d'extraire une clé publique à partir d'une chaîne de caractères arbitraire. Cette caractéristique nous offre plusieurs options :

- La révocation des clés : Pour gérer la révocation des clés, plus précisément l'expiration des clés, BONEH et FRANKLIN ont proposé de concatenéner l'identité de l'utilisateur avec une date de validité. Grâce à ce mécanisme, il est possible de chiffrer des messages valables à partir d'une date précise.

- L'usurpation d'identité : Les algorithmes de chiffrements basés sur les problèmes d'arithmétique nécessitent l'intervention d'une autorité de certification afin d'approuver l'identité du possesseur d'une clé publique. Tandis que dans un schéma IBE, il n'est nul besoin de faire cette vérification, puisque la clé publique est générée par n'importe quel utilisateur.

- La sauvegarde des clés : Les clés secrètes des utilisateurs sont générées par le PKG, il est donc toujours possible de les régénérer en cas de perte.

## 1.3.2 Le schéma BF-IBE

Pour bien distinguer les données publiques et les données sensibles, nous avons choisi de mettre toute valeur sensible en couleur rouge.

### Initialisation

- Entrée : Le paramètre de sécurité $k$;

- Choisir un nombre premier $p$ de longueur $k$;

- Choisir la clé maître $s \in \mathbb{Z}_p$;
— Choisir une fonction bilinéaire admissible $e : \mathbb{G} \times \mathbb{G} \to \mathbb{G}_T$;

— Choisir une fonction de hachage $\mathcal{H}_1 : \{0, 1\}^* \to \mathbb{G}$;

— Choisir une fonction de hachage $\mathcal{H}_2 : \mathbb{G}_T \to \mathcal{M}$, avec $\mathcal{M}$ l'ensemble des messages;

— Choisir un élément générateur du système : $P \in \mathbb{G}$;

— Calculer la clé publique du PKG : $Y = sP$;

— Sortie : $PP = (\mathbb{G}, \mathbb{G}_T, e, P, Y, \mathcal{H}_1, \mathcal{H}_2), \mathit{MSK} = s$.

Le premier algorithme renvoie les paramètres publiques du système (PP), et la clé maître MSK (en anglais : *Master Secret Key*) possédée par le PKG, cette clé sera utilisée par l'algorithme **Extraction** pour générer les clés secrètes des utilisateurs.

Extraction

— Entrée : Une identité $id \in \{0, 1\}^*$;

— Calculer la clé publique de l'utilisateur : $Q_{id} = \mathcal{H}_1(id) \in \mathbb{G}$;

— Calculer la clé secrète de l'utilisateur : $S_{id} = sQ_{id} \in \mathbb{G}$;

— Sortie : $Q_{id}, S_{id}$.

Comme son nom l'indique, l'algorithme **Extraction** permet d'extraire une clé secrète $S_{id}$ à partir d'une clé publique $Q_{id}$. La clé publique est calculée grâce à une fonction de hachage à partir d'une chaîne de caractères arbitraire appelée *id* (l'identité). Il peut s'agir du nom de l'utilisateur, son adresse mail, un identifiant ou autre. Il est également possible de concaténer cette chaîne avec une date précise dans le futur, afin de s'assurer que le possesseur ne peut pas déchiffrer avant cette date.

Chiffrement

— Entrée : Un message $M \in \mathcal{M}$, l'identité du destinataire $id \in \{0, 1\}^*$;

— Choisir une valeur aléatoire $r \in \mathbb{Z}_p^*$;

— Calculer $g_{id} = e(\mathcal{H}_1(id), Y) \in \mathbb{G}_T$;

— Calculer $U = rP \in \mathbb{G}$;

— Calculer $V = M \oplus \mathcal{H}_2(g_{id}^r) \in \mathcal{M}$;

— Sortie : $C = (U, V) \in \mathbb{G} \times \mathcal{M}$.

Grâce à l'aléa $r$ qui intervient dans le processus de chiffrement, cet algorithme peut renvoyer des cryptogrammes différents pour un même message. Il s'agit bien d'un chiffrement non-déterministe. Cette propriété ajoute une nouvelle couche de sécurité pour ce chiffrement.
## Déchiffrement

— Entrée : Un cryptogramme $C = (U, V) \in \mathbb{G} \times \mathcal{M}$;

— Calculer $M = V \oplus \mathcal{H}_2(e(S_{id}, U))$;

— Sortie : $M \in \mathcal{M}$.

Pour vérifier la propriété 1.4 pour l'algorithme Déchiffrement il suffit de montrer que : $g_{id}^r = e(S_{id}, U)$, nous avons :

$$ 
\begin{align*}
e(S_{id}, U) &= e(sQ_{id}, rP) \\
&= e(Q_{id}, sP)^r \\
&= e(\mathcal{H}_1(id), Y)^r \\
&= g_{id}^r.
\end{align*}
$$

## 1.3.3 La sécurité du schéma BF-IBE

La sécurité du système de chiffrement BF-IBE repose sur la difficulté du problème Diffie-Hellman bilinéaire (aussi appelé BDH : en anglais *Bilinear Diffie-Hellman*).

### Définition 38 (Le problème BDH)

Soient $\mathbb{G}, \mathbb{G}_T$ deux groupes d'ordre premier $p, e : \mathbb{G} \times \mathbb{G} \to \mathbb{G}_T$ une fonction bilinéaire admissible, et $P$ un élément générateur de $\mathbb{G}$. Le problème BDH consiste à calculer $e(P, P)^{abc} \in \mathbb{G}_T$ étant donné $P, aP, bP, cP$ pour $a, b, c, \in \mathbb{Z}_p$.

On dit qu'un algorithme $\mathcal{A}$ a l'avantage $\epsilon$ pour résoudre le problème BDH si :

$$ \mathrm{Pr} [\mathcal{A}(P, aP, bP, cP) = e(P, P)^{abc}] \geq \epsilon. \qquad (1.5) $$

Il existe aussi une version décisionnelle du problème (DBDH), qui consiste à trouver un distingueur entre $e(P, P)^{abc}$ et une valeur aléatoire dans $\mathbb{G}_T$.

### Définition 39 (Le problème DBDH)

Soient trois entiers $a, b, c \in \mathbb{Z}_q^*, P \in \mathbb{G} \setminus \{P_\infty\}$ un point de la courbe, et $T \in \mathbb{G}_T$. Le problème DBDH (en anglais : *Decisional Bilinear Diffie-Hellman*) consiste à déterminer si $T = e(P, P)^{abc}$ ou un élément aléatoire dans $\mathbb{G}_T$, avec $e : \mathbb{G} \times \mathbb{G} \to \mathbb{G}_T$ une fonction bilinéaire admissible.

Pour analyser la sécurité de certaines constructions cryptographiques, BELLARE et ROGAWAY ont introduit un modèle de sécurité appelé modèle d'oracle aléatoire [BR93].

### Définition 40 (Oracle aléatoire)

Un oracle aléatoire est une fonction $\mathcal{H} : X \to Y$ choisie uniformément au hasard dans l'ensemble de toutes les fonctions $h : X \to Y$ (on suppose que $Y$ est un ensemble fini). Un algorithme peut interroger l'oracle aléatoire pour n'importe quelle valeur d'entrée $x \in X$ et recevoir la valeur $\mathcal{H}(x)$ en réponse.
Les oracles aléatoires servent à modéliser les fonctions de hachage utilisées en
cryptographie telles que SHA-2 (voir le tableau 1.1). Notez que la sécurité dans le
modèle oracle aléatoire n'implique pas la sécurité dans le monde réel, néanmoins
le modèle oracle aléatoire est un outil très utile pour la validation des construc-
tions cryptographiques. Pour l'adapter aux schémas IBE, BONEH et FRANKLIN
ont renforcé le modèle IND-CCA pour faire face à un adversaire qui possède des
clés privées correspondant aux identités de son choix. Les schémas IBE sont prou-
vés sûrs selon des scénarios d'attaques très proches des scénarios des schémas
de chiffrement à clé publique, avec en plus quelques spécificités pour la fonction
Extraction. Dans le cas d'un IBE, un adversaire est autorisé à accéder à un oracle
d'extraction qui permet de calculer la clé privée à partir d'une identité id.

Les modèles d'attaques : Avant d'introduire les modèles de sécurité dans le cadre d'IBE, rappelons d'abord la liste des modèles d'attaques connues en cryptanalyse :

KPA : L'attaque à clair connu (en anglais : *Known Plaintext Attack*) est un modèle d'attaque où l'attaquant a accès à la fois au texte en clair, et à son cryptogramme.

CPA : L'attaque à clair choisi (en anglais : *Chosen Plaintext Attack*) est un modèle d'attaque qui suppose que l'attaquant peut obtenir les textes chiffrés pour des messages en clair choisis. Le but de l'attaque est d'obtenir des informations qui réduisent la sécurité du schéma de chiffrement. Cette attaque est plus puissante que KPA car le cryptanalyste peut choisir des textes en clair spécifiques qui donneront plus d'informations sur la clé secrète.

CCA : L'attaque à cryptogramme choisi (en anglais : *Chosen Ciphertext Attack*) est un modèle d'attaque où l'attaquant peut recueillir des informations en obtenant les clairs associés à des cryptogrammes choisis. À partir de ces informations, l'adversaire peut tenter de récupérer la clé secrète utilisée pour le déchiffrement.

CPA2 : Il s'agit d'une version modifiée de CPA où l'attaquant peut demander les textes chiffrés des textes en clair supplémentaires après avoir vu les textes chiffrés pour certains textes en clair.

Le modèle IND-ID-CPA : Attaques adaptatives à clairs choisis.

Premièrement, considérons le concept plus faible de sécurité sémantique qui suppose un attaquant interne capable d'émettre des requêtes à un oracle d'extraction (algorithme *Extraction*), qui lui permet d'extraire la clé privée correspondant à des identités de son choix. Le succès de l'attaquant IND-ID-CPA est formalisé par son avantage dans le jeu suivant :

Initialisation : Le challenger choisit un paramètre de sécurité *k* et exécute l'algorithme *Initialisation*. Il retourne à l'adversaire *A* les paramètres publics, et garde la clé maître *s*.
**Phase 1** : L'adversaire peut effectuer adaptativement des requêtes à l'oracle d'extraction $\mathcal{O}(id_i)$ qui lui retourne la clé privée $S_{id}$. À la fin de cette phase, l'adversaire retourne deux messages de même longueur $m_0$ et $m_1$ et une identité id' avec une restriction sur id', pour laquelle $\mathcal{A}$ ne doit pas faire de requête d'extraction de clé privée dans les phase 1 et 2.

**Challenge** : Le challenger tire un bit aléatoire $b \in \{0,1\}$ et calcule le cryptogramme $c = \text{Chiffrement}(S_{id'}, id', m_b)$, et l'envoie à l'adversaire.

**Phase 2** : Comme dans la première phase, l'adversaire peut effectuer adaptative-ment des requêtes à l'oracle d'extraction $\text{Extraction}(id_i)$ qui lui retourne la clé privée $S_{id}$, où $id_i \neq id'$.

**Réponse** : À la fin de son attaque, l'adversaire retourne son estimation $b' \in \{0,1\}$ de $b$ et il gagne le défi si $b' = b$. L'avantage de $\mathcal{A}$ et donné par : $\text{Adv}_{\mathcal{E},\mathcal{A}}(k) = |\text{Pr}[b = b'] - 1/2|$.

## Définition 41

Un schéma IBE $\mathcal{E}$ est sémantiquement sûr contre les attaques adaptatives à clairs choisis si pour tout adversaire IND-ID-CPA en temps polynomial $\mathcal{A}$ la fonction $\text{Adv}_{\mathcal{E},\mathcal{A}}(k)$ est négligeable.

## Le modèle IND-ID-CCA : Attaques adaptatives à chiffrés choisis.

Dans ce modèle l'attaquant $\mathcal{A}$ est supposé pouvoir accéder de manière adaptative à un oracle de déchiffrement, mais également à un oracle lui donnant les clés privées correspondant à des identités de son choix. Le succès de l'attaquant IND-ID-CCA est formalisé par son avantage dans le jeu suivant :

**Initialisation** : Le challenger choisit un paramètre de sécurité $k$ et exécute l'algorithme **Initialisation**. Il retourne à l'adversaire $\mathcal{A}$ les paramètres publics et garde la clé secrète maitre $s$.

**Phase 1** : L'adversaire peut effectuer de manière adaptative les requêtes à :

- L'oracle d'extraction $\mathcal{O}_{\text{Extract}}(id_i)$ : qui retourne la clé privée $S_{id_i}$.

- L'oracle de déchiffrement $\mathcal{O}_{\text{Dec}}(c_i, id_i)$ : qui renvoie le clair (s'il existe) qui correspond au chiffré $c_i$ pour l'identité $id_i$.

A la fin de cette phase, l'adversaire retourne deux messages $(m_0, m_1)$ de même longueur et une identité id' avec une restriction sur id', pour laquelle $\mathcal{A}$ ne doit pas faire de requête d'extraction de clé privée dans les phase 1 et 2.

**Challenge** : Le challenger tire un bit aléatoire $b \in \{0,1\}$ et calcul le chiffré $c = \text{Chiffrement}(id', m_b)$, et l'envoie à l'adversaire.

**Phase 2** : A la manière de la première phase, l'adversaire peut effectuer adaptativement les requêtes à :
— L'oracle d'extraction $O_{Extract}(id_i)$ : qui retourne la clé privée $S_{id_i}$ où $id_i \neq id'$.

— L'oracle de déchiffrement $O_{Dec}(c_i, id_i)$ : qui renvoie le clair (s'il existe) qui correspond au chiffré $c_i$ pour l'identité $id_i$ où $c_i \neq c$.

**Réponse** : À la fin de son attaque, l'adversaire retourne son estimation $b' \in \{0, 1\}$ de $b$. Il gagne le jeu si $b' = b$ et l'avantage de $\mathcal{A}$ et donné par : $Adv_{\mathcal{E},\mathcal{A}}(k) = |\Pr[b = b'] - 1/2|$.

**Définition 42**

Un schéma IBE $\mathcal{E}$ est sémantiquement sûr contre les attaques adaptatives à chiffrés choisis si pour tout adversaire IND-ID-CCA en temps polynomial $\mathcal{A}$, la fonction $Adv_{\mathcal{E},\mathcal{A}}(k)$ est négligeable.

BONEH et FRANKLIN ont prouvé que dans un modèle d'oracle aléatoire, le protocole était sémantiquement sécurisé selon l'hypothèse BDH. Cela signifie qu'un attaquant opérant dans un certain cadre et capable de casser le système IBE pourrait tout aussi bien être utilisé pour résoudre BDH.

### 1.3.4 L'enrôlement et la mise à jour des clés

La politique de distribution des clés est un point important dans un SGC (Schéma de Gestion des Clés). En effet, en cryptographie asymétrique, il est décisif de distinguer l'envoi d'une clé publique sur un canal non sécurisé et l'envoi d'une clé privée sur un canal sécurisé. La distribution des clés privées se fait généralement pendant la phase d'enrôlement et la phase de mise à jour des clés (rekeying).

Pour enrôler un utilisateur, ce dernier doit envoyer une requête au PKG qui assurera l'authenticité de l'identité de cet utilisateur. Le PKG exécutera ensuite l'algorithme Extraction pour générer la clé de l'utilisateur et la lui transmettra accompagnée des paramètres publics du système (PP) sur un canal sécurisé (par exemple : sur un support physique comme une clé usb, ou une carte à puce). Il est toujours possible pour l'utilisateur de vérifier l'exactitude de ses clés en testant :

$$e(Q_{id}, Y) \stackrel{?}{=} e(S_{id}, P). \qquad (1.6)$$

En effet, ces deux valeurs valent $e(Q_{id}, P)^s$ qui dépend de la clé maître du PKG. Pour mettre à jour les clés dans le schéma BF-IBE, il suffit de générer une nouvelle clé maître MSK, tout en gardant la précédente dans un lieu sûr (un coffre) pour les besoins judiciaires que nous avons évoqués dans la partie 1.5.3.

## 1.4 Critiques et améliorations

Depuis son apparition, BF-IBE est visé par deux critiques principales :
1. **Le problème de centralisation** : Dans ce schéma, le PKG détient tout le pouvoir, il est capable d'extraire à lui seul les clé secrètes de tous les utilisateurs, ce qui lui permet de déchiffrer toutes les communications, les falsifier, et même usurper les identités.

2. **Le problème de révocation** : Le cas de révocation d'une entité est rarement traité dans les schémas de gestion de clés basés sur l'identité. Dans le schéma BF-IBE, le destinataire doit interroger le PKG à chaque communication pour obtenir sa clé de déchiffrement. Bien que cette option empêche les utilisateurs révoqués de déchiffrer, elle oblige le PKG à rester en écoute pour valider chaque échange entre utilisateurs, et établir à chaque fois un canal sécurisé pour communiquer la clé de déchiffrement.

Au fur et à mesure, plusieurs auteurs ont proposé des solutions pour résoudre le problème de centralisation. AL-RIYAMI et PATERSON [AP03] ont construit CL-PKC (en anglais : *Certificatless Public Key Cryptography*) qui permet à toute entité valide de construire ses propres clés privées et publiques. Bien que ce système résolve le problème de centralisation, il ne résout pas complètement celui de l'autorité de séquestre (*Key Escrow Problem*) [XZQ05]. De plus, la mise à jour des clés doit se faire sur un canal privé.

LEE et al. [LBD+04] ont présenté un schéma IBE non centralisé. Le schéma définit plusieurs autorités de protection des clés appelées KPA (en anglais : *Key Privacy Authoritie*) en plus de l'autorité standard qui est le PKG. Dans ce schéma, chaque autorité possède sa propre clé maître (MSK) et participe à l'exécution de l'algorithme *Extraction*.

### 1.4.1 Émission sécurisée des clés

Comme nous l'avons mentionné, le schéma ESC [LBD+04] (*Émission Sécurisée des Clés*) est un IBE qui possède plusieurs autorités. Soient $s_0 \in \mathbb{Z}_p$ la clé maître du PKG, et $s_1, \dots, s_n$ la clé maître de $KPA_1, \dots, KPA_n$ respectivement. La clé publique du système dans ce cas est : $Y = s_0s_1\dots s_nP$; de plus, chaque autorité $i$ possède sa propre clé publique $P_i = s_iP$ pour $0 \le i \le n$. Pour calculer $Y$, chaque autorité calcule $Y_i = s_iY_{i-1}$ et l'envoie à l'autorité $i+1$, tel que $Y_0 = s_0P = P_0$ (voir la figure 1.3). Une fois le calcul terminé et publié, chaque autorité est capable de vérifier l'exactitude des $Y_i$ en vérifiant l'égalité suivante :

$$e(Y_i, P) \stackrel{?}{=} e(Y_{i-1}, P_i).$$

En effet, cette valeur équivaut : $e(Y_i, P) = e(s_iY_{i-1}, P) = e(Y_{i-1}, s_iP) = e(Y_{i-1}, P_i) = e(Y_{i-1}, P)^{s_i}$, et seul $KPA_i$ est capable de générer $Y_i$ qui satisfait ce test. Après la phase *Initialisation*, il faudra redéfinir la nouvelle version de l'algorithme *Extraction*. Contrairement à BF-IBE, dans cette version l'utilisateur et
<figure><img src="image_32.png" /><figcaption>FIGURE 1.3 – Génération de la clé publique du système dans le schéma d'ESC</figcaption></figure>

les KPA participent aussi à l'exécution de cet algorithme. Soit $\mathcal{H}_3 : \mathbb{G}_T \to \mathbb{Z}_p$ une fonction de hachage qui s'ajoute désormais aux paramètres publics, l'algorithme Extraction est défini ainsi :

Extraction

— Par l'utilisateur :

— Générer une clé temporaire $x \stackrel{\$}{\leftarrow} \mathbb{Z}_p$;

— Calculer $X = xP$;

— Envoyer $id, X$ au PKG.

— Par le PKG : Il valide l'authenticité de l'utilisateur puis calcule :

— La clé publique : $Q_{id} = \mathcal{H}(id, \text{PKG}, \text{KPA}_1, \dots, \text{KPA}_n)$;

— La clé partielle masquée de l'utilisateur :

$$Q_0 = \mathcal{H}_3(e(s_0 X, P_0)) s_0 Q_{id}; \qquad (1.7)$$

— Signature pour vérifier l'intégrité : $\text{Sign}(Q_0) = s_0 Q_0$;

— Envoie $(Q_0, \text{Sign}(Q_0))$ au KPA$_1$.

— Par $\text{KPA}_i$ :

— Vérifie la signature : $e(\text{Sign}(Q_{i-1}), P) \stackrel{?}{=} e(Q_{i-1}, P_{i-1})$;

— Calcule :

$$Q_i = \mathcal{H}_3(e(s_i X, P_i)) s_i Q_{i-1}; \qquad (1.8)$$

— Signe : $\text{Sign}(Q_i) = s_i Q_i$;

— Envoie $(Q_i, \text{Sign}(Q_i))$ au KPA$_{i+1}$ sauf pour le cas $i = n$, dans ce cas le KAP$_n$ envoie les clés à l'utilisateur.

— Par l'utilisateur : L'utilisateur reçoit $Q_n, \text{Sign}(Q_n)$ puis :

— Vérifie la signature : $e(\text{Sign}(Q_n), P) \stackrel{?}{=} e(Q_n, P_n)$;

— Calcule la clé privée :

$$S_{id} = \frac{Q_n}{\prod_{i=0}^{n} \mathcal{H}_3(e(P_i, P_i)^x)}; \qquad (1.9)$$
— Vérifie la clé privée : $e(S_{id}, P) \stackrel{?}{=} e(Q_{id}, Y)$.

L'utilisateur commence par choisir une clé secrète temporaire $x$, cette clé va servir à la fin de l'algorithme pour extraire (démasquer) la clé secrète $Q_n$. Chaque autorité $i$ génère sa part de la clé secrète de l'utilisateur notée $Q_i$, cette clé ($Q_i$) est protégée par un masque $\mathcal{H}_3(e(s_i X, P_i))$ que seul l'utilisateur ou l'autorité $i$ peut calculer. En effet, nous avons : $e(s_i X, P_i) = e(s_i x P, P_i) = e(s_i P, P_i)^x = e(P_i, P_i)^x$. Ainsi, par les équations 1.8 et 1.7, nous obtiendrons :

$$Q_n = \underbrace{\mathcal{H}_3(e(s_0 X, P_0)) \dots \mathcal{H}_3(e(s_n X, P_n))}_{\text{le masque}} \underbrace{s_0 \dots s_n Q_{id}}_{S_{id}} . \quad (1.10)$$

Par conséquent, seul l'utilisateur légitime (ou la réunion de toutes les autorités) est capable de démasquer $Q_n$ et d'en extraire sa clé privée $S_{id}$ (équation 1.9).

<figure><img src="image_33.png" /><figcaption>FIGURE 1.4 – L’algorithme Extraction dans un schéma d’ESC</figcaption></figure>

Étant donné que les échanges se font sur un canal public (voir la figure 1.4), il est important de protéger les communications contre les attaques de l'homme du milieu. Pour ce faire, chaque autorité signe son envoi envers sa voisine pour authentifier la donnée envoyée.

Enfin, l'utilisateur calcule sa clé privée $S_{id}$ et le dernier test permet de vérifier l'exactitude de l'ensemble des calculs, et que la clé privée est bien composée de $s_0 \dots, s_n$. En effet, sans ce test, il est possible qu'une des autorités corrompues utilise une fausse clé maître pour perturber le système.
## 1.4.2 Conclusion

Dans ce schéma, nous distinguons le rôle du PKG, qui s'occupe d'authentifier les futurs utilisateurs et qui participe à la génération de leur clé, et le rôle des KPA, qui s'occupent uniquement de la protection de la clé privée de l'utilisateur.

Bien que ce schéma résolve le problème de centralisation, ainsi que celui de l'auto-rité de séquestre, nous remarquons que le problème de révocation reste ouvert ; de plus, comme l'expliquent XU et al. [XZQ05] dans ce schéma, il ne suffira pas de s'authentifier uniquement auprès du PKG. En effet, un PKG corrompu est capable de générer une fausse valeur $x'$ et $X' = xP$ et lancer l'exécution de l'algorithme Extraction avec ces valeurs au lieu de $x$ et $X$ de l'utilisateur légitime.

Dans le chapitre suivant, nous allons présenter une version améliorée de ce schéma, dans laquelle nous traitons le cas du PKG corrompu, la révocation, la mise à jour des clés, ainsi que la simplification des calculs.
<figure><img src="image_34.png" /></figure>
## 2 | Amélioration d'IBE

### Sommaire

<table><tr><td>2.1</td><td>Introduction</td><td>112</td></tr><tr><td>2.2</td><td>Les paramètres du système</td><td>112</td></tr><tr><td>2.3</td><td>L'extraction de la clé privée</td><td>113</td></tr><tr><td>2.3.1</td><td>L'enrôlement</td><td>113</td></tr><tr><td>2.3.2</td><td>La mise à jour des clés</td><td>115</td></tr><tr><td>2.4</td><td>Analyse de sécurité</td><td>116</td></tr><tr><td>2.5</td><td>La révocation des clés</td><td>117</td></tr><tr><td>2.5.1</td><td>La problématique</td><td>117</td></tr><tr><td>2.5.2</td><td>Les solutions existantes</td><td>118</td></tr><tr><td>2.5.3</td><td>La solution proposée</td><td>118</td></tr><tr><td>2.6</td><td>Récapitulatif</td><td>119</td></tr></table>
## 2.1 Introduction

Dans le chapitre précédent, nous avons présenté le schéma IBE de Boneh et Franklin, ainsi que le schéma ESC pour la protection des clés. La combinaison de ces deux technologies donne naissance à un schéma décentralisé où, seul l'utilisateur est capable de construire sa clé. En même temps, dans le cadre de la procédure "e-discovery", il est toujours possible à une autorité judiciaire d'obtenir la clé privée d'une entité en combinant le pouvoir du PKG et celui des KPAs.

Bien que le schéma que nous avons présenté (ainsi que d'autres) résolve le problème de centralisation, sont souvent négligés le problème de révocation et la mise à jour des clés (rekeying). En effet, dans le schéma précédent, pour éviter l'usurpation d'identité par le PKG, il est nécessaire d'authentifier chaque utilisateur auprès de toutes les autorités (PKG et KPAs). Étant donné que l'authentification est généralement une procédure longue, car elle nécessite un contact direct avec l'autorité concernée, il est préférable de minimiser de manière optimale ce besoin.

Dans ce chapitre, nous présentons une nouvelle architecture de gestion des clés qui combine les avantages d'un schéma PKI et IBE [DT16]. Rappelons qu'une infrastructure de gestion de clés décrit trois phases principales :

- l'enrôlement : correspond à l'inscription des utilisateurs;

- la mise à jour des clés : correspond à la réinitialisation de toutes les clés privées après la fin de leurs dates de validité;

- la révocation : vise à annuler l'enregistrement d'un utilisateur, et donc l'empêcher de déchiffrer les futurs messages chiffrés.

## 2.2 Les paramètres du système

Dans l'architecture que nous proposons, nous distinguons deux types d'autorités :

- Le PKG statique ($PKG_0$) : il s'agit d'une autorité gérée par un officier de sécurité, qui participe uniquement à la phase d'enrôlement. Son rôle est d'authentifier les utilisateurs, et de leur fournir une clé privée partielle.

- Le PKG dynamique ($PKG_1$) : il s'agit d'une autorité qui participe à la protection de la clé privée de l'utilisateur, et s'occupe de la mise à jour des clés. Pour cette raison, le PKG dynamique met à jour sa clé maître plus régulièrement que le PKG statique, ainsi sans avoir un impacte sur toutes les clés des utilisateurs.

Sans perte de généralité, nous allons considérer un seul PKG dynamique. L'algorithme d'initialisation prend en entrée un paramètre de sécurité $k$, et renvoie les paramètres publics $PP$ et les deux clés maîtres $s_0$ du $PKG_0$ et $s_1$ du $PKG_1$.
Initialisation

— Entrée : Le paramètre de sécurité $k$;

— Choisir un nombre premier $p$ de longueur $k$;

— Choisir la clé maître du PKG statique : $s_0 \in \mathbb{Z}_p$;

— Choisir la clé maître du PKG dynamique : $s_1 \in \mathbb{Z}_p$;

— Choisir une fonction bilinéaire admissible $e : \mathbb{G}_0 \times \mathbb{G}_1 \to \mathbb{G}_T$;

— Choisir une fonction de hachage $\mathcal{H}_1 : \{0, 1\}^* \to \mathbb{G}_1$;

— Choisir une fonction de hachage $\mathcal{H}_2 : \mathbb{G}_T \to \mathcal{M}$, où $\mathcal{M}$ est l'ensemble des messages;

— Choisir deux générateurs : $P \in \mathbb{G}_0$ et $P' \in \mathbb{G}_1$;

— Calculer la clé publique du PKG statique : $P_0 = s_0 P$;

— Calculer les clés publiques du PKG dynamique : $P_1 = s_1 P$ et $P'_1 = s_1 P'$;

— Calculer la clé publique du système : $Y = s_0 s_1 P$;

— Sortie : $PP = (\mathbb{G}, \mathbb{G}_T, e, P, Y, \mathcal{H}_1, \mathcal{H}_2)$, $MSK = s_0, s_1$.

La clé publique $Y$ est calculée par le PKG dynamique à partir de la clé $P_0$, puisque $Y = s_0 s_1 P = s_1 P_0$. Bien entendu, il est toujours possible à quiconque de vérifier ce calcul en testant :

$$e(Y, P') \stackrel{?}{=} e(P_0, P'_1). \qquad (2.1)$$

En effet, toujours grâce à la bilinéarité de $e$, nous avons : $e(Y, P') = e(s_0 s_1 P, P') = e(s_0 P, s_1 P') = e(P_0, P'_1)$.

## 2.3 L'extraction de la clé privée

Pour l'algorithme Extraction, nous distinguons la phase d'enrôlement où l'utilisateur obtient sa première clé, et la phase de mise à jour, où la crypto-période de la clé est achevée.

### 2.3.1 L'enrôlement

La phase d'enrôlement commence par une authentification auprès du PKG statique, qui valide l'identité de l'entité concernée, et génère sa clé partielle $S_p$. Cette clé (privée) sera utilisée uniquement pour authentifier l'utilisateur auprès du PKG dynamique, et générer la clé privée.

**Étape 1.** Par le PKG statique :

— Authentification et validation de l'identité de l'utilisateur;
— Calculer la clé publique de l'utilisateur : $Q_{id} = H_1(id) \in \mathbb{G}_1$;

— Calculer la clé partielle de l'utilisateur : $S_p = s_0Q_{id} \in \mathbb{G}_1$;

— Sortie : $Q_{id}, S_p$.

L'utilisateur reçoit sa clé partielle en passant par un canal sécurisé, et vérifie son exactitude grâce au test 2.2. Ce test permet de valider que le PKG statique a bien utilisé sa clé maître $s_0$ pour calculer la clé partielle. Une fois le test validé, l'utilisateur génère un masque $t$ qu'il va garder jusqu'à la fin de la phase d'enrôlement. Ce masque permet de protéger la clé partielle $S_p$. Enfin, l'utilisateur envoie la clé partielle masquée $S_{p,t}$, ainsi que les clés publiques $P_t, Q_t$ pour valider les tests 2.3 et 2.4 sur un canal public.

**Étape 2.** Par l'utilisateur :

— L'utilisateur valide si ce test est satisfait :

$$e(P, S_p) \stackrel{?}{=} e(P_0, Q_{id}); \qquad (2.2)$$

— L'utilisateur choisit un masque temporaire $t \in \mathbb{Z}_p$;

— Calcule la clé partielle masquée : $S_{p,t} = tS_p \in \mathbb{G}_1$;

— Calcule la clé publique masquée : $Q_t = tQ_{id} \in \mathbb{G}_1$;

— Calcule : $P_t = tP \in \mathbb{G}_0$;

— Envoie : $id, S_{p,t}, Q_t, P_t$ au PKG dynamique.

Le PKG statique reçoit la requête de l'utilisateur. D'abord, il vérifie que $Q_t = tQ_{id}$ grâce au test 2.3, ceci confirme que $Q_t$ porte l'identité $id$. Ensuite, il vérifie que $S_{p,t} = s_0Q_t$ grâce au test 2.4 qui confirme que l'utilisateur a été validé par le PKG statique, et qu'il a obtenu sa clé partielle. Après la validation de ces deux tests, le PKG statique calcule la clé privée masquée : $S_t$ et l'envoie à l'utilisateur sur un canal public.

**Étape 3.** Par le PKG dynamique :

— Le PKG dynamique valide si ces deux tests sont satisfaits :

$$e(P, Q_t) \stackrel{?}{=} e(P_t, Q_{id}); \qquad (2.3)$$

$$e(P, S_{p,t}) \stackrel{?}{=} e(P_0, Q_t); \qquad (2.4)$$

— Calcule la clé privée masquée : $S_t = s_1S_{p,t} = ts_0s_1Q_{id}$;

— Envoie : $S_t$ à l'utilisateur.
L'utilisateur reçoit sa clé masquée, il vérifie grâce au test 2.5 que la clé reçue vaut bien $ts_0s_1Q_{id}$. Après la validation du test, l'utilisateur extrait sa clé privée $S_{id}$ en démasquant la clé reçue.

**Étape 4.** Par l'utilisateur :

— L'utilisateur valide si ce test est satisfait :

$$e(tY, Q_{id}) \stackrel{?}{=} e(P, S_t); \qquad (2.5)$$

— Calcule la clé secrète : $S_{id} = \frac{1}{t}S_t$.

À la fin de la phase d'enrôlement l'utilisateur possède : la clé publique $Q_{id}$, la clé privée $S_{id}$ et la clé partielle $S_p$. La figure 2.1 résume les échanges entre l'utilisateur et les deux PKG.

<figure><img src="image_35.png" /><figcaption>FIGURE 2.1 – Récapitulatif de la phase d'enrôlement</figcaption></figure>

### 2.3.2 La mise à jour des clés

La phase de mise à jour des clés, ou “rekeying”, est un composant indispensable dans un schéma de gestion des clés. En effet, pour des mesures de sécurité, les clés cryptographiques possèdent souvent une date d’expiration, ce que nous appelle une crypto-période. À la fin de la crypto-période, l'utilisateur doit lancer le programme de rekeying afin d’obtenir une nouvelle clé. Souvent, dans une PKI ou
dans les schémas IBE, cette phase est considérée identique à la phase d'enrôlement. Cependant, dans le schéma que nous présentons dans ce chapitre, nous avons essuyé de distinguer ces deux étapes. Étant donné que les communications passent sur un canal public avec le PKG dynamique, nous proposons que ce dernier soit le seul à intervenir pour mettre à jour les clés des utilisateurs. Pour ce faire, le PKG dynamique génère une nouvelle clé maître $s'_1$ et lance l'algorithme de mise à jour. Les utilisateurs vont ensuite se servir de la clé partielle $S_p$ et exécuter les étapes 3 et 4 de la phase d'enrôlement pour obtenir la nouvelle clé secrète $S_{id}$.

<figure><img src="image_36.png" /><figcaption>FIGURE 2.2 – Récapitulatif de la phase de mise à jour des clés</figcaption></figure>

La mise à jour de la clé $s_0$ impacte tous les paramètres publics qui en dépendent, en particulier la clé publique du PKG dynamique ($P_1 = s_1 P$), et la clé publique du système $Y = s_0s_1P$. Pour calculer la nouvelle clé $Y'$ nous avons :

$$Y' = \frac{s'_1}{s_1} Y = s_0 s'_1 P .$$

Il est toujours possible à quiconque de vérifier ce calcul grâce au test de l'équation 2.1.

## 2.4 Analyse de sécurité

La clé privée d'un utilisateur étant calculée de manière coopérative par plusieurs PKGs (statiques et dynamiques), la confidentialité de la clé privée de l'utilisateur est préservée si au moins un seul PKG statique reste honnête. Seul l'utilisateur légitime connaissant la clé de masquage $t$ peut extraire et calculer sa clé privée.
Dans le cas de plusieurs autorité statiques, l'utilisateur sera amené à s'authentifier auprès de chacune de celles-ci pour obtenir sa clé partielle finale, cette condition est obligatoire afin de se protéger contre l'usurpation d'identité [XZQ05].

Le schéma proposé émet une véritable clé privée basée sur l'identité. Il peut donc être combiné avec d'autres schémas basés sur l'identité comme la signature basée sur l'identité, le chiffrement basé sur les attributs, etc.

Nous définissons IBE2 comme étant une extension des schémas IBE ordinaires. Ainsi les modèles de sécurité IND-ID-CPA et IND-ID-CCA (voir la page 102) restent similaires saufs à la phase 1 et 2 où l'attaquant peut accéder à la fois à la clé privée $S_{id}$ et à la clé partielle $S_p$. Il suffit de remarquer qu' IBE classique est un cas particulier d'IBE2 dans ces deux modèles. En effet, dans le cadre d'IBE classique $S_p = Q_{id}$ avec $s_0 = 1$. Ainsi, si l'attaquant IND-ID-CPA ou IND-ID-CCA réussit son attaque sur IBE2 alors, il est toujours possible d'utiliser la même attaque sur IBE classique.

## 2.5 La révocation des clés

### 2.5.1 La problématique

Entre deux crypto-périodes $T_i$ et $T_{i+1}$ il est toujours possible qu'un utilisateur quitte le système pour plusieurs raisons : fin de contrat, licenciement, perte de clé, matériel défectueux ou compromis, etc. Il est donc important de définir une stratégie de révocation des clés. Dans une PKI, la révocation est gérée par le service d'annuaire, qui s'occupe d'ajouter les certificats révoqués dans la CRL (la liste des certificats révoqués), cette liste est signée par l'autorité de certification afin de prouver son intégrité. Au fur et à mesure, la CRL ne cesse d'augmenter, ce qui provoque une latence pendant la validation des certificats. À cause de ce problème, une grande partie des clients PKI effectuent leur validation de manière incomplète.

Dans le schéma BF-IBE, il n'existe aucun moyen de communiquer aux expéditeurs qu'une identité a été révoquée, car seule la clé publique du PKG et l'identité du destinataire sont nécessaires pour chiffrer un message. Avec un tel mécanisme, la mise à jour régulière des clés privées semble être la seule solution au problème de révocation. Cela signifie que tous les utilisateurs, que leurs clés aient été révoquées ou non, doivent régulièrement entrer en contact avec le PKG, prouver leur identité et obtenir de nouvelle clé privée. Le PKG doit rester en ligne pour toutes ces transactions, et un canal sécurisé doit être établi entre le PKG et chaque utilisateur pour transmettre la clé privée. Prenant en compte l'évolutivité du déploiement d'IBE, nous pouvons déduire que, pour un très grand nombre d'utilisateurs, cela peut vite devenir une impasse.
## 2.5.2 Les solutions existantes

Le problème de révocation est un problème bien étudié dans le cadre d'une PKI traditionnelle, et plusieurs solutions ont été proposées [Mic08, ALO98, Gen03, Goy07]. Cependant, les articles sur IBE négligent souvent les mécanismes de révocation. HANAOKA et al. [HHSI05] proposent un moyen pour les utilisateurs de renouveler périodiquement leurs clés privées sans interagir avec le PKG. Le PKG affiche uniquement les informations de mise à jour des clés, ce qui est beaucoup plus pratique. Cependant, chaque utilisateur doit posséder un dispositif matériel inviolable. L'autre solution proposée consiste à combiner IBE avec un schéma de partage de secret [BDTW01, LQ03]. Dans ce cadre, il existe un tiers de confiance, appelé médiateur, qui détient les partages des clés privées de tous les utilisateurs et qui les aide à déchiffrer chaque cryptogramme. Ainsi, si une identité est révoquée, le médiateur est invité à cesser d'aider l'utilisateur.

## 2.5.3 La solution proposée

Pour surmonter le problème de révocation, nous proposons de combiner la solution utilisée dans une PKI qui est la CRL, et les avantages qu'offre le schéma IBE. L'idée consiste à concevoir une liste des identités révoquées que nous appelons IRL (en anglais : *Identity Revocation List*). Cette liste doit respecter les conditions suivantes :

- effacer la liste après chaque crypto-période. Ainsi, nous pouvons révoquer les entités en temps réel sans augmenter constamment l'IRL. Étant donné que les PKGs sont capables de restituer les clés, il n'est donc nul besoin de garder une sauvegarde des clés révoquées;

- modifier l'IRL n'est accessible qu'à l'officier (ou les officiers) de sécurité, et elle est signée par les deux PKG afin de prouver son intégrité;

- stocker uniquement les identités révoquées;

- choisir la crypto-période de façon à rendre l'IRL vide la plupart du temps, ainsi elle n'affectera pas la fluidité du trafic réseau.

<figure><img src="image_37.png" /><figcaption>FIGURE 2.3 – La politique de révocation</figcaption></figure>
### 2.6 Récapitulatif

Dans ce chapitre, nous avons présenté une architecture IBE qui apporte des solutions sur les problématiques qui touchent ce genre de schémas, en particulier : la décentralisation, l'autorité de séquestre, et la révocation. Nous avons choisi d'améliorer la solution proposée par BYOUNGCHEON et al. sur la sécurisation des clés. La valeur ajoutée consiste à simplifier la procédure d'enrôlement en minimisant les calculs.

Le masque utilisé par BYOUNGCHEON et al. pour protéger la clé privée est composé de plusieurs calculs de fonctions de hachage (équation 1.10), tandis que le masque dans le schéma présenté dans ce chapitre consiste en une seule valeur *t* générée par l'utilisateur.

Nous avons également démontré que la signature des échanges pour la phase d'enrôlement n'est pas nécessaire. En effet, grâce au différents tests que nous avons présentés, nous constatons que les clés sont auto-signées.

Il faut noter également la différence entre les rôles du PKG statique, qui est une autorité isolée (hors-ligne), et du PKG dynamique, qui est quant à lui connecté au réseau. Cette distinction a trois avantages :

- la protection du système contre les différentes attaques informatiques, étant donné que le PKG statique est toujours hors-ligne;

- l'authentification de l'utilisateur auprès du PKG statique est simplifiée, il suffit de démontrer qu'il possède la clé partielle générée par le PKG statique;

- la simplification de la mise à jour des clés avec l'intervention du PKG statique uniquement.

Enfin, pour résoudre le problème de révocation, nous avons intégré dans le système une liste des certificats révoqués (IRL) ; cette solution permet d'obtenir une révocation en temps réel sans attendre la fin de la crypto-période.
<figure><img src="image_38.png" /></figure>
Dans ce manuscrit nous avons exposé deux problématiques qui touchaient la cryptographie symétrique et asymétrique. L'objectif de ce travail était d'analyser ces problématiques, montrer une partie des travaux réalisés par la communauté, et enfin présenter notre valeur ajoutée pour traiter ces problèmes. Dans ce chapitre de conclusion, nous allons rappeler brièvement les deux sujets :

- Le masquage pour lutter contre les attaques par canaux auxiliaires et les attaques par injection de fautes;

- Les infrastructures de gestion des clés.

Nous mettons l'accent sur les lignes importantes que nous avons traitées, et les améliorations possibles que nous prévoyons pour après la thèse.

## 3.1 La protection contre les attaques par canaux auxiliaires et les attaques par injection de faute

### 3.1.1 Rappel

Le premier sujet concerne la cryptographie symétrique, nous avons traité la vulnérabilité des systèmes de chiffrement, en particulier du standard du chiffrement symétrique, l'AES, face aux attaques par canaux auxiliaires (SCA<fnref n="1" />) et les attaques par injection de faute (FIA<fnref n="2" />), et nous avons montré qu'il est primordial de masquer les données sensibles durant le chiffrement pour lutter contre ces attaques.

Nous avons vu que l'implémentation d'un système de chiffrement sur un composant électronique, (par exemple : une carte à puce ou une carte FPGA), est souvent plus sensible aux attaques comparée à une implémentation sur un ordinateur classique.

La simple mesure de la consommation électrique du composant pendant l'exécution d'une opération de chiffrement (ou déchiffrement) peut révéler des informations sur les données traitées. D'un autre côté, par le principe de KERCKHOFFS, il est fortement recommandé de publier les algorithmes de chiffrement et les proto-coles utilisés. Un attaquant ayant un accès physique au composant électronique, connaissant son architecture et les algorithmes qu'il exécute, est capable de prédire la clé secrète contenue dans ce composant.

### 3.1.2 Le masquage

L'implémentation des algorithmes cryptographiques nécessite un soin particulier afin d'assurer une bonne protection contre les attaques de type SCA et FIA. En

<footnote n="1">1. *Side Channel Attacks*</footnote>

<footnote n="2">2. *Fault Injection Attack*</footnote>
effet, la complexité des opérations ne doit pas dépendre des données sensibles. Pour éviter ce genre de situations, il est conseillé de masquer les valeurs sensibles avant de les traiter.

La conception d'une fonction de masquage implique la modification de la structure du système de chiffrement ciblé. Pour chaque transformation $f$ qui compose ce système de chiffrement, il faut construire une transformation alternative $f'$ telle que : $f'(\text{mask}(x)) = \text{mask}(f(x))$.

Nous avons vu dans la première partie plusieurs schémas de masquage, et nous avons remarqué qu'ils ne protègent pas tous contre les deux attaques SCA et FIA simultanément. Le masquage classique, le masquage basé sur le partage du secret et le masquage basé sur le produit scalaire permettent tous de masquer l'addition et la multiplication et protéger ainsi contre SCA. D'un autre côté, le masquage de la multiplication dans DSM est un problème ouvert. Nous avons remarqué également que la complexité algorithmique des opérations (notamment le masquage de la multiplication) est quadratique, ceci entraîne un coût non négligeable pour les composants à faibles ressources.

Pour surmonter ces obstacles, et construire un nouveau schéma de masquage, nous avons défini les objectifs suivants :

- masquer les deux opérations, addition et multiplication ;

- détecter (et corriger si besoin) les erreurs potentielles pendant l'exécution de l'algorithme de chiffrement ou déchiffrement ;

- minimiser le coût des opérations.

Pour atteindre ces objectifs nous avons utilisé la même structure que celle du schéma ODSM. Ce dernier, étant basé sur les codes LCD, sa conception possède une structure proche de celle des codes correcteurs. De plus, il permet de masquer et rafraîchir le masque de manière simple et rapide. Cependant, nous avons modifié la représentation des données traitées afin d'augmenter le nombre de manipulations possibles. Dans le schéma original les opérations se font sur un espace vectoriel, tandis que le nouveau schéma traite les données dans un corps fini. Étant donné que la multiplication est commutative dans un corps fini, cette propriété nous avait permis de concevoir un masquage de complexité linéaire pour la multiplication. De plus, avec cette nouvelle représentation, il est possible également de détecter les erreurs potentielles de manière plus efficace. En effet, il n'est plus besoin de garder en mémoire le masque utilisé pour détecter les erreurs. Dans la nouvelle structure, selon le choix des paramètres $\vec{g}$ et $\vec{h}$ il est possible de détecter et même corriger les erreurs sans connaître le masque utilisé $r$.

Les paramètres $\vec{g}$ et $\vec{h}$ que nous avons utilisés dans l'exemple 11 de la page 87 permettent de concevoir un code correcteur $\mathcal{K}$ de distance minimale 3 :

$$ \mathcal{K} = \{ \vec{z} = \vec{c} \oplus \vec{d} \mid \forall (\vec{c}, \vec{d}) \in \mathcal{C} \times \mathcal{D} \} \subset \mathbb{F}_{2^s}^n . $$

Ainsi, pour $n = 3$ il est possible de détecter jusqu'à 2 erreurs. En général, pour une
longueur *n* petite, il est possible de faire une recherche exhaustive des paramètres $\vec{g}$ et $\vec{h}$ pour obtenir un code *K* d'une capacité de détection optimale.

## 3.1.3 Perspectives

Il sera intéressant pour la suite d'étudier le choix des paramètres $\vec{g}$ et $\vec{h}$ pour des longueurs plus grandes, trouver des propriétés capables de générer facilement les codes *C* et *D* optimaux de ce masquage. L'objectif sera de trouver, pour un paramètre de sécurité *d*, deux vecteurs $\vec{g}$ et $\vec{h}$ qui satisferont les critères de ce schéma de masquage, et qui forment un code *K* dont la capacité de détection d'erreurs est maximale pour une longueur *n* minimale.

Nous avions démontré que ce masquage protège bien contre les attaques monovariées. Cependant, nous n'avons pas de preuve en ce qui concerne les attaques multivariées, en particulier pour une longueur *n* assez grande. Il sera donc intéressant d'étudier le comportement de ce masquage face à ces attaques, et voir s'il existe un seuil auquel il peut protéger.

Une autre piste à explorer, concerne l'utilisation de ce masquage dans d'autres systèmes de chiffrement symétrique. La fonction de substitution du 3DES par exemple utilise deux représentations différentes ($F_2^6$ en entrée, et $F_2^4$ en sortie). Il sera donc intéressant de trouver une généralisation de ce masquage pour les systèmes de chiffrement qui utilisent des représentations multiples.

## 3.2 Les infrastructures de gestion des clés

### 3.2.1 Rappel

Le deuxième sujet que nous avons traité concerne la cryptographie asymétrique. Pour sécuriser les communications entre un ensemble d'utilisateurs, il est préférable d'utiliser des systèmes de chiffrement symétriques. Ces derniers, sont souvent plus rapides et efficaces pour chiffrer une grande quantité de données. D'un autre côté, il est nécessaire également d'utiliser des systèmes de chiffrement asymétrique pour assurer l'échange de clés. Dans la deuxième partie de ce manuscrit, nous avons présenté les problématiques liées à la gestion des clés dans un système asymétrique. La mise en place d'une architecture de gestion de clés est souvent confrontée à plusieurs obstacles tels que : l'usurpation d'identité, le problème de révocation, la centralisation, la sauvegarde des clés privées ...

Ces problématiques remontent au début des années quatre-vingt. Il a fallu trouver un moyen pour authentifier les clés afin de se protéger contre l'attaque de l'homme au milieu (voir la section 1.4.2 page 13). SHAMIR a proposé alors le concept de la cryptographie basée sur l'identité (IBE). Ce concept consiste principalement
à intégrer l'identité dans la clé publique. La conception d'un tel crypto-système étant un problème ouvert, les constructeurs ont adopté la solution PKI. Celle-ci consiste à ajouter une autorité de certification (CA) qui assurera l'authenticité des clés.

Plus tard, en 2001, BONEH et FRANKLIN ont proposé le premier système de chiffrrement efficace de type IBE, ce dernier, basé sur le problème Diffie-Hellman bilinéaire, a résolu le problème d'usurpation d'identité. Cette solution utilise l'accouplement bilinéaire sur un groupe de points d'une courbe elliptique. Le schéma est composé d'une seule autorité (PKG) qui assure la génération des clés privées à partir d'une chaîne de caractères arbitraires. Le PKG possède une clé maître qui permet de faire cette extraction de clé secrète à partir d'une clé publique, ce qui signifie que la sécurité du système repose entièrement sur cette clé maître.

Le schéma initial de BONEH et FRANKLIN (BF-IBE) avait également plusieurs inconvénients :

1. Le problème de centralisation : Dans ce schéma, le PKG détient tout le pouvoir, il est capable de produire à lui seul les clés secrètes de tous les utilisateurs, ce qui lui permet de déchiffrer toutes les communications, les falsifier, et même usurper les identités.

2. Le problème de révocation : Dans le schéma BF-IBE, le destinataire doit interroger le PKG à chaque communication pour obtenir sa clé de déchiffrement. Bien que cette option empêche les utilisateurs révoqués de déchiffrer, elle oblige le PKG de rester en écoute pour valider chaque échange entre utilisateurs, et établir à chaque fois un canal sécurisé pour communiquer la clé de déchiffrement.

Plusieurs auteurs ont proposé des solutions pour résoudre le problème de centralisation. AL-RIYAMI et PATERSON [AP03] ont construit CL-PKC (Certificatless Public Key Cryptography) qui permet à une entité valide de construire ses propres clés privées et publiques.

LEE et al. [LBD+04] ont présenté un schéma IBE non centralisé. Le schéma définit plusieurs autorités de protection des clés appelées KPA (Key Privacy Authority) en plus de l'autorité standard qui est le PKG. Dans ce schéma, chaque autorité possède sa propre clé maître (MSK) et participe à l'exécution de l'algorithme d'extraction de la clé privée des utilisateurs.

Bien que ces systèmes, et d'autres ont résolu le problème de centralisation, le problème de l'autorité de séquestre (Key Escrow Problem) [XZQ05] qui consiste en d'autres termes à appliquer la procédure e-discovery (voir l'exigence 5 de la section 1.5.2) persiste encore.
## 3.2.2 Les solutions proposées et les perspectives

Pour résoudre les problématiques que nous avons citées, nous avons présenté dans le chapitre 2 un schéma qui combine les caractéristiques suivantes :

- un schéma décentralisé où seul l'utilisateur est capable de reconstruire sa clé privée;

- il est possible de reconstruire la clé privée d'un utilisateur en combinant les clés maîtres des autorités, ainsi respecte la procédure "e-discovery" sans utiliser un matériel de stockage sécurisé comme un HSM;

- la mise à jour des clés se fait sur un canal public;

- la révocation des utilisateurs moins coûteuse grâce à l'IRL que l'on vide à chaque mise à jour des clés.

Cette solution optimise également les calculs effectués durant la phase d'enrôle-ment, et assure l'intégrité des échanges entre l'utilisateur et les différentes autorités. IBE-2 est un schéma capable de s'adapter avec d'autres systèmes basés sur l'iden-tité comme le chiffrement/signature basé(e) sur les attributs. Il sera intéressant de combiner IBE2 avec les solutions existantes afin d'apporter une meilleure gestion de clés.
Table des figures

<table>
  <tbody>
    <tr>
      <td>1.1</td>
      <td>Comparaison entre la cryptographie symétrique et asymétrique</td>
      <td>5</td>
    </tr>
    <tr>
      <td>1.2</td>
      <td>Une machine de TURING pour calculer le successeur d'un entier</td>
      <td>8</td>
    </tr>
    <tr>
      <td>1.3</td>
      <td>Le rôle des MdT pour classifier les problèmes mathématiques</td>
      <td>10</td>
    </tr>
    <tr>
      <td>1.4</td>
      <td>Diffie-Hellman</td>
      <td>14</td>
    </tr>
    <tr>
      <td>1.5</td>
      <td>L'attaque de l'homme du milieu</td>
      <td>14</td>
    </tr>
    <tr>
      <td>1.6</td>
      <td>La phase d'enrôlement dans une PKI</td>
      <td>17</td>
    </tr>
    <tr>
      <td>1.7</td>
      <td>La phase communication dans une PKI</td>
      <td>18</td>
    </tr>
    <tr>
      <td>1.8</td>
      <td>La distribution des clés dans un schéma IBE</td>
      <td>19</td>
    </tr>
    <tr>
      <td>1.9</td>
      <td>Le schéma général d'un système de communication</td>
      <td>24</td>
    </tr>
    <tr>
      <td>1.10</td>
      <td>L'encodage pour les codes linéaires</td>
      <td>25</td>
    </tr>
    <tr>
      <td>1.11</td>
      <td>Illustration d'un code parfait</td>
      <td>27</td>
    </tr>
    <tr>
      <td>1.12</td>
      <td>L'opération de chiffrement pour l'AES-128</td>
      <td>35</td>
    </tr>
    <tr>
      <td>2.1</td>
      <td>Représentation graphique de l'ensemble des éléments du masquage DSM.</td>
      <td>78</td>
    </tr>
    <tr>
      <td>2.2</td>
      <td>Comparaison du taux de réussite d'une attaque SCA d'ordre 2 par rapport au nombre de traces entre le masquage PDSM et l'état de l'art.</td>
      <td>84</td>
    </tr>
    <tr>
      <td>1.1</td>
      <td>Représentation graphique de la courbe : y<sup>2</sup> = x<sup>3</sup> - 2x + 1 sur R</td>
      <td>95</td>
    </tr>
    <tr>
      <td>1.2</td>
      <td>Le schéma classique d'échange de clé à trois</td>
      <td>98</td>
    </tr>
    <tr>
      <td>1.3</td>
      <td>Génération de la clé publique du système dans le schéma d'ESC</td>
      <td>107</td>
    </tr>
    <tr>
      <td>1.4</td>
      <td>L'algorithme Extraction dans un schéma d'ESC</td>
      <td>108</td>
    </tr>
    <tr>
      <td>2.1</td>
      <td>Récapitulatif de la phase d'enrôlement</td>
      <td>115</td>
    </tr>
    <tr>
      <td>2.2</td>
      <td>Récapitulatif de la phase de mise à jour des clés</td>
      <td>116</td>
    </tr>
    <tr>
      <td>2.3</td>
      <td>La politique de révocation</td>
      <td>118</td>
    </tr>
  </tbody>
</table>
<figure><img src="image_39.png" /></figure>
Liste des tableaux

<table><tr><td>1.1</td><td>Les fonctionnalités des différents algorithmes cryptographiques</td><td>12</td></tr><tr><td>1.2</td><td>Le nombre de tours en fonction de la taille des clés.</td><td>33</td></tr><tr><td>1.1</td><td>Le nombre d'opérations pour chacune des transformations de l'AES avec la méthode masquage RP.</td><td>52</td></tr><tr><td>2.1</td><td>Une vision globale sur la complexité algorithmique de chaque fonction en terme de nombre d'opérations.</td><td>83</td></tr><tr><td>2.2</td><td>Comparatif entre PDSM et l'état de l'art</td><td>83</td></tr></table>
<figure><img src="image_40.png" /></figure>
# Index alphabétique

## A

<table><tr><td>Anneau</td><td>94</td></tr><tr><td>Authentification</td><td>5</td></tr></table>

## B

<table><tr><td>BDH</td><td>97, 102</td></tr></table>

## C

<table><tr><td>CA</td><td>16</td></tr><tr><td>Capacité de correction</td><td>26</td></tr><tr><td>Certificat électronique</td><td>15</td></tr><tr><td>CÉSAR</td><td>2</td></tr><tr><td>Confidentialité</td><td>5</td></tr><tr><td>Confusion</td><td>33</td></tr><tr><td>Corps</td><td>94</td></tr><tr><td>Courbe elliptique</td><td>94</td></tr><tr><td>CRL</td><td>16</td></tr><tr><td>CSR</td><td>17</td></tr></table>

## D

<table><tr><td>Diffusion</td><td>33</td></tr><tr><td>Distance de HAMMING</td><td>25</td></tr><tr><td>Distance minimale</td><td>25</td></tr><tr><td>DS</td><td>16</td></tr><tr><td>Dual</td><td>25</td></tr></table>

## E

<table><tr><td>e-discovery</td><td>20</td></tr><tr><td>ESC</td><td>106</td></tr></table>

## F

<table><tr><td>Factorisation</td><td>9</td></tr><tr><td>FAN</td><td>28</td></tr><tr><td>FIA</td><td>40</td></tr></table>

<table><tr><td>Fonction à sens unique</td><td>10</td></tr></table>

## G

<table><tr><td>groupe</td><td>92</td></tr></table>

## I

<table><tr><td>Intégrité</td><td>5</td></tr></table>

## L

<table><tr><td>LCD</td><td>63</td></tr><tr><td>LEMS</td><td>62</td></tr><tr><td>Logarithme discret</td><td>9</td></tr></table>

## M

<table><tr><td>MITM</td><td>13</td></tr></table>

## N

<table><tr><td>n-torsion</td><td>96</td></tr></table>

## P

<table><tr><td>PEM</td><td>17</td></tr><tr><td>PKI</td><td>15</td></tr><tr><td>Probing Attack</td><td>43</td></tr><tr><td>Processus métier</td><td>20</td></tr></table>

## R

<table><tr><td>RA</td><td>16</td></tr><tr><td>Random Oracle Model</td><td>102</td></tr><tr><td>Répudiation</td><td>5</td></tr><tr><td>RS</td><td>16</td></tr></table>

## S

<table><tr><td>SCA</td><td>40</td></tr><tr><td>SGC</td><td>105</td></tr><tr><td>SSS</td><td>53</td></tr></table>
<figure><img src="image_41.png" /></figure>
Publications et conférences :

[CDGT18] Claude Carlet and Abderrahman Daif and Sylvain Guilley and Cédric Tavernier. Polynomial direct sum masking to protect against both SCA and FIA. *Journal of Cryptographic Engineering*, Aug 2018.

[DT16] Abderrahman Daif and Cédric Tavernier. An efficient certificateless key management architecture to solve IBE and PKI issues. In *Fifteenth International Workshop on Algebraic and Combinatorial Coding Theory*, pages 111-116, 2016.

[CDD$^{+}$15] Claude Carlet and Abderrahman Daif and Jean-Luc Danger and Sylvain Guilley and Zakaria Najm and Xuan Thuy Ngo and Thi-bault Porteboeuf and Cédric Tavernier. Optimized linear complementary codes implementation for hardware trojan prevention. In *European Conference on Circuit Theory and Design, ECCTD 2015*, Trondheim, Norway, pages 1-4, 2015.

[ABB$^{+}$15] Mickael Avril and Laurie Basta and Laurent Bouillet and Abderrahman Daif and Gregory Landais and Cédric Tavernier. Identity based cryptography for smart-grid protection. In *Proceedings of 9th international conference on computer engineering and applications*, pages 1-10, 2015.
<figure><img src="image_42.png" /></figure>
Bibliographie

[ABB+15] Mickael Avril, Laurie Basta, Laurent Bouillet, Abderrahman Daif, Gregory Landais, and Cédric Tavernier. Identity based cryptography for smart-grid protection. In *Proceedings of 9th international conference on computer engineering and applications*, pages 1–10, 2015. Cited on pages 19 and 133.

[AK97] Ross J. Anderson and Markus G. Kuhn. Low Cost Attacks on Tamper Resistant Devices. In *Security Protocols, 5th International Workshop, Paris, France, April 7-9, 1997, Proceedings*, pages 125–136, 1997. Cited on page 40.

[ALO98] William Aiello, Sachin Lodha, and Rafail Ostrovsky. Fast Digital Identity Revocation (Extended Abstract). In *Advances in Cryptology - CRYPTO '98, 18th Annual International Cryptology Conference, Santa Barbara, California, USA, August 23-27, 1998, Proceedings*, pages 137–152, 1998. Cited on page 118.

[ANS16] ANSSI. Recommandations de sécurité relatives à TLS, 2016. https://www.ssi.gouv.fr/uploads/2016/09/guide_tls_v1.1.pdf. Cited on page 6.

[AP03] Sattam S. Al-Riyami and Kenneth G. Paterson. Certificateless Public Key Cryptography. In *Advances in Cryptology - ASIACRYPT 2003, 9th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, November 30 - December 4, 2003, Proceedings*, pages 452–473, 2003. Cited on pages 106 and 125.

[BCC+14] Julien Bringer, Claude Carlet, Hervé Chabanne, Sylvain Guilley, and Houssem Maghrebi. Orthogonal Direct Sum Masking - A Smartcard Friendly Computation Paradigm in a Code, with Builtin Protection against Side-Channel and Fault Attacks. In *Information Security Theory and Practice. Securing the Internet of Things - 8th IFIP WG 11.2 International Workshop, WISTP 2014, Heraklion, Crete, Greece,*
*June 30 - July 2, 2014. Proceedings*, pages 40–56, 2014. Cited on pages 64 and 69.

[BDL01] Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. On the Importance of Eliminating Errors in Cryptographic Computations. *J. Cryptology*, 14(2):101–119, 2001. Cited on page 40.

[BDTW01] Dan Boneh, Xuhua Ding, Gene Tsudik, and Chi-Ming Wong. A Method for Fast Revocation of Public Key Certificates and Security Capabilities. In *10th USENIX Security Symposium, August 13-17, 2001, Washington, D.C., USA*, 2001. Cited on page 118.

[BF01] Dan Boneh and Matthew K. Franklin. Identity-Based Encryption from the Weil Pairing. In *Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings*, pages 213–229, 2001. Cited on pages 19 and 99.

[BFG15] Josep Balasch, Sebastian Faust, and Benedikt Gierlichs. Inner Product Masking Revisited. In *Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I*, pages 486–510, 2015. Cited on page 59.

[BFGV12] Josep Balasch, Sebastian Faust, Benedikt Gierlichs, and Ingrid Verbauwhede. Theory and Practice of a Leakage Resilient Masking Scheme. In *Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Proceedings*, pages 758–775, 2012. Cited on page 59.

[BGH$^{+}$16] Nicolas Bruneau, Sylvain Guilley, Annelie Heuser, Olivier Rioul, François-Xavier Standaert, and Yannick Teglia. Taylor Expansion of Maximum Likelihood Attacks for Masked and Shuffled Implementations. In *Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I*, pages 573–601, 2016. Cited on page 88.

[BGW88] Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). In *Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA*, pages 1–10, 1988. Cited on pages 53 and 57.

[BLS01] Dan Boneh, Ben Lynn, and Hovav Shacham. Short Signatures from the Weil Pairing. In *Advances in Cryptology - ASIACRYPT 2001, 7th June 30 - July 2, 2014. Proceedings*, pages 40–56, 2014. Cited on pages 64 and 69.
*International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9-13, 2001, Proceedings*, pages 514–532, 2001. Cited on page 98.

[BR93] Mihir Bellare and Phillip Rogaway. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In *CCS '93, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, November 3-5, 1993.*, pages 62–73, 1993. Cited on page 102.

[BS03] Johannes Blömer and Jean-Pierre Seifert. Fault Based Cryptanalysis of the Advanced Encryption Standard (AES). In *Financial Cryptography, 7th International Conference, FC 2003, Guadeloupe, French West Indies, January 27-30, 2003, Revised Papers*, pages 162–181, 2003. Cited on page 40.

[Car13] Claude Carlet. *Correlation-Immune Boolean Functions for Leakage Squeezing and Rotating S-Box Masking against Side Channel Attacks*. 2013. Cited on page 62.

[CDD$^{+}$15] Claude Carlet, Abderrahman Daif, Jean-Luc Danger, Sylvain Guilley, Zakaria Najm, Xuan Thuy Ngo, Thibault Porteboeuf, and Cédric Tavernier. Optimized linear complementary codes implementation for hardware trojan prevention. In *European Conference on Circuit Theory and Design, ECCTD 2015, Trondheim, Norway, August 24-26, 2015*, pages 1–4, 2015. Cited on pages 71 and 133.

[CDG$^{+}$14] Claude Carlet, Jean-Luc Danger, Sylvain Guilley, Houssem Maghrebi, and Emmanuel Prouff. Achieving side-channel high-order correlation immunity with leakage squeezing. *J. Cryptographic Engineering*, 4(2):107–121, 2014. Cited on page 62.

[CDGM12] Claude Carlet, Jean-Luc Danger, Sylvain Guilley, and Houssem Maghrebi. Leakage Squeezing of Order Two. *IACR Cryptology ePrint Archive*, 2012:567, 2012. Cited on page 62.

[CDGT18] Claude Carlet, Abderrahman Daif, Sylvain Guilley, and Cédric Tavernier. Polynomial direct sum masking to protect against both SCA and FIA. *Journal of Cryptographic Engineering*, Aug 2018. Cited on pages 76, 77, and 133.

[CJRR99] Suresh Chari, Charanjit S. Jutla, Josyula R. Rao, and Pankaj Rohatgi. Towards Sound Approaches to Counteract Power-Analysis Attacks. In *Advances in Cryptology - CRYPTO '99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings*, pages 398–412, 1999. Cited on page 40.
[DH76] Whitfield Diffie and Martin E. Hellman. New directions in cryptogra-
phy. *IEEE Trans. Information Theory*, 22(6):644–654, 1976. Cited
on pages 4 and 13.

[DQ86] Yvo Desmedt and Jean-Jacques Quisquater. Public-Key Systems Based on the Difficulty of Tampering (Is There a Difference Between DES and RSA?). In *Advances in Cryptology - CRYPTO '86, Santa Barbara, California, USA, 1986, Proceedings*, pages 111-117, 1986. Cited on pages 6 and 19.

[DR00] Joan Daemen and Vincent Rijmen. Rijndael for AES. In *AES Candidate Conference*, pages 343–348, 2000. Cited on pages 4 and 32.

[DT16] Abderrahman Daif and Cédric Tavernier. An efficient certificateless key management architecture to solve IBE and PKI issues. In *Fifteenth International Workshop on Algebraic and Combinatorial Coding Theory*, pages 111–116, 2016. Cited on pages 112 and 133.

[FK92] David Ferraiolo and Richard Kuhn. Role-Based Access Controls. 15th National Computer Security Conference (NCSC), 1992.

[GCMZ12] Aijun Ge, Cheng Chen, Chuangui Ma, and Zhenfeng Zhang. Short and Efficient Expressive Attribute-Based Signature in the Standard Model. *IACR Cryptology ePrint Archive*, 2012:125, 2012.

[Gen03] Craig Gentry. Certificate-Based Encryption and the Certificate Revocation Problem. In *Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings*, pages 272-293, 2003. Cited on page 118.

[GM11] Louis Goubin and Ange Martinelli. Protecting AES with Shamir's Secret Sharing Scheme. In *Cryptographic Hardware and Embedded Systems - CHES 2011 - 13th International Workshop, Nara, Japan, September 28 - October 1, 2011. Proceedings*, pages 79-94, 2011. Cited on pages 53 and 55.

[GMO01] Karine Gandolfi, Christophe Mourtel, and Francis Olivier. Electromagnetic Analysis: Concrete Results. In *Cryptographic Hardware and Embedded Systems - CHES 2001, Third International Workshop, Paris, France, May 14-16, 2001, Proceedings*, number Generators, pages 251-261, 2001. Cited on page 40.

[Goy07] Vipul Goyal. Certificate Revocation Using Fine Grained Certificate Space Partitioning. In *Financial Cryptography and Data Security, 11th International Conference, FC 2007, and 1st International Workshop on Usable Security, USEC 2007, Scarborough, Trinidad and Tobago,*
February 12-16, 2007. Revised Selected Papers, pages 247-259, 2007.
Cited on page 118.

[GP99] Louis Goubin and Jacques Patarin. DES and Differential Power Analysis (The "Duplication" Method). In *Cryptographic Hardware and Embedded Systems, First International Workshop, CHES'99, Worcester, MA, USA, August 12-13, 1999, Proceedings*, pages 158-172, 1999.
Cited on page 40.

[GPSW06] Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters. Attribute-based encryption for fine-grained access control of encrypted data. In *Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, Alexandria, VA, USA, October 30 - November 3, 2006*, pages 89-98, 2006.

[GRR98] Rosario Gennaro, Michael O. Rabin, and Tal Rabin. Simplified VSS and Fast-Track Multiparty Computations with Applications to Threshold Cryptography. In *Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC '98, Puerto Vallarta, Mexico, June 28 - July 2, 1998*, pages 101-111, 1998.
Cited on page 57.

[Ham50] Richard Wesley Hamming. Error detecting and error correcting codes. *The Bell System Technical Journal*, 29(2):147-160, April 1950. Cited on page 23.

[HHSI05] Yumiko Hanaoka, Goichiro Hanaoka, Junji Shikata, and Hideki Imai. Identity-Based Hierarchical Strongly Key-Insulated Encryption and Its Application. In *Advances in Cryptology - ASIACRYPT 2005, 11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, December 4-8, 2005, Proceedings*, pages 495-514, 2005. Cited on page 118.

[HJW00] Detlef Hühnlein, Michael J. Jacobson Jr., and Damian Weber. Towards Practical Non-interactive Public Key Cryptosystems Using Non-maximal Imaginary Quadratic Orders. In *Selected Areas in Cryptography, 7th Annual International Workshop, SAC 2000, Waterloo, Ontario, Canada, August 14-15, 2000, Proceedings*, pages 275-287, 2000. Cited on pages 6 and 19.

[ISW03] Yuval Ishai, Amit Sahai, and David A. Wagner. Private Circuits : Securing Hardware against Probing Attacks. In *Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings*, pages 463-481, 2003. Cited on page 42.
[JLQ99] Marc Joye, Arjen K. Lenstra, and Jean-Jacques Quisquater. Chinese Remaindering Based Cryptosystems in the Presence of Faults. *J. Cryptology*, 12(4):241–245, 1999. Cited on page 40.

[Jou00] Antoine Joux. A One Round Protocol for Tripartite Diffie-Hellman. In *Algorithmic Number Theory, 4th International Symposium, ANTS-IV, Leiden, The Netherlands, July 2-7, 2000, Proceedings*, pages 385–394, 2000. Cited on page 98.

[Kah74] David Kahn. *The codebreakers*. Weidenfeld and Nicolson, 1974. Cited on page 40.

[KJJ99] Paul C. Kocher, Joshua Jaffe, and Benjamin Jun. Differential Power Analysis. In *Advances in Cryptology - CRYPTO '99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings*, pages 388–397, 1999. Cited on page 40.

[Kob87] Neal Koblitz. Elliptic curve cryptosystems. *Mathematics of computation*, 48(177):203–209, 1987. Cited on page 94.

[Koc96] Paul C. Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In *Advances in Cryptology - CRYPTO '96, 16th Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 1996, Proceedings*, pages 104–113, 1996. Cited on page 40.

[LBD$^{+04}$] Byoungcheon Lee, Colin Boyd, Ed Dawson, Kwangjo Kim, Jeongmo Yang, and Seungjae Yoo. Secure Key Issuing in ID-based Cryptography. In *ACSW Frontiers 2004, 2004 ACSW Workshops - the Australasian Information Security Workshop (AISW2004), the Australasian Workshop on Data Mining and Web Intelligence (DMWI2004), and the Australasian Workshop on Software Internationalisation (AWSI2004)*. *Dunedin, New Zealand, January 2004*, pages 69–74, 2004. Cited on pages 106 and 125.

[Liu68] Chung Laung Liu. *Introduction to combinatorial mathematics*, volume 181. McGraw-Hill New York, 1968. Cited on page 53.

[LQ03] Benoît Libert and Jean-Jacques Quisquater. Efficient revocation and threshold pairing based cryptosystems. In *Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, PODC 2003, Boston, Massachusetts, USA, July 13-16, 2003*, pages 163–171, 2003. Cited on page 118.

[Mas92] James L. Massey. Linear codes with complementary duals. *Discrete Mathematics*, 106-107:337–342, 1992. Cited on page 63.
[Mes00] Thomas S. Messerges. Using Second-Order Power Analysis to Attack DPA Resistant Software. In *Cryptographic Hardware and Embedded Systems - CHES 2000, Second International Workshop, Worcester, MA, USA, August 17-18, 2000, Proceedings*, pages 238-251, 2000. Cited on pages 42 and 55.

[Mic08] Silvio Micali. Efficient certificate revocation, february 2008. US Patent 7,337,315. Cited on page 118.

[Mil85] Victor S. Miller. Use of Elliptic Curves in Cryptography. In *Advances in Cryptology - CRYPTO '85, Santa Barbara, California, USA, August 18-22, 1985, Proceedings*, pages 417-426, 1985. Cited on page 94.

[Mul54] David E. Muller. Application of Boolean algebra to switching circuit design and to error detection. *Trans. I.R.E. Prof. Group on Electronic Computers*, 3(3):6-12, 1954. Cited on page 28.

[MY91] Ueli M. Maurer and Yacov Yacobi. Non-interactive Public-Key Cryptography. In *Advances in Cryptology - EUROCRYPT '91, Workshop on the Theory and Application of Cryptographic Techniques, Brighton, UK, April 8-11, 1991, Proceedings*, pages 498-507, 1991. Cited on pages 6 and 19.

[NSGD12] Maxime Nassar, Youssef Souissi, Sylvain Guilley, and Jean-Luc Dan-ger. RSM: A small and fast countermeasure for AES, secure against 1st and 2nd-order zero-offset SCAs. In *2012 Design, Automation & Test in Europe Conference & Exhibition, DATE 2012, Dresden, Germany, March 12-16, 2012*, pages 1173-1178, 2012. Cited on page 62.

[PR07] Emmanuel Prouff and Matthieu Rivain. A Generic Method for Secure SBox Implementation. In *Information Security Applications, 8th International Workshop, WISA 2007, Jeju Island, Korea, August 27-29, 2007, Revised Selected Papers*, pages 227-244, 2007. Cited on page 62.

[PR11] Emmanuel Prouff and Thomas Roche. Higher-Order Glitches Free Implementation of the AES Using Secure Multi-party Computation Protocols. In *Cryptographic Hardware and Embedded Systems - CHES 2011 - 13th International Workshop, Nara, Japan, September 28 - October 1, 2011. Proceedings*, pages 63-78, 2011. Cited on pages 53 and 55.

[QS01] Jean-Jacques Quisquater and David Samyde. ElectroMagnetic Analysis (EMA): Measures and Counter-Measures for Smart Cards. In *Smart Card Programming and Security, International Conference on Research in Smart Cards, E-smart 2001, Cannes, France, September 19-21, 2001, Proceedings*, pages 200-210, 2001. Cited on page 40.
[QS02] Jean-Jacques Quisquater and David Samyde. Eddy current for ma-
gnetic analysis with active sensor. In Proceedings of Esmart, volume
2002, 2002. Cited on page 40.

[Ree54] Irving Stoy Reed. A class of multiple-error-correcting codes and the decoding scheme. *Transactions of the IRE Professional Group on Information Theory*, 4(4):38–49, September 1954. Cited on page 28.

[RP10] Matthieu Rivain and Emmanuel Prouff. Provably Secure Higher-Order Masking of AES. In *Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop, Santa Barbara, CA, USA, August 17-20, 2010. Proceedings*, pages 413–427, 2010. Cited on pages 44 and 85.

[RPD09] Matthieu Rivain, Emmanuel Prouff, and Julien Doget. Higher-Order Masking and Shuffling for Software Implementations of Block Ciphers. In *Cryptographic Hardware and Embedded Systems - CHES 2009, 11th International Workshop, Lausanne, Switzerland, September 6-9, 2009, Proceedings*, pages 171–188, 2009. Cited on pages 41 and 42.

[RR01] Josyula R. Rao and Pankaj Rohatgi. EMpowering Side-Channel Attacks. *IACR Cryptology ePrint Archive*, 2001:37, 2001. Cited on page 40.

[RS60] I. Reed and G. Solomon. Polynomial Codes Over Certain Finite Fields. *Journal of the Society for Industrial and Applied Mathematics*, 8(2):300–304, 1960. Cited on page 55.

[RSA78] Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A Meth-
thod for Obtaining Digital Signatures and Public-Key Cryptosystems.
*Commun. ACM*, 21(2):120–126, 1978. Cited on page 4.

[SA02] Sergei P. Skorobogatov and Ross J. Anderson. Optical Fault Induction Attacks. In *Cryptographic Hardware and Embedded Systems - CHES 2002, 4th International Workshop, Redwood Shores, CA, USA, August 13-15, 2002, Revised Papers*, pages 2–12, 2002. Cited on page 40.

[Sha49] Claude Elwood Shannon. Communication theory of secrecy systems. *Bell Labs Technical Journal*, 28(4):656–715, 1949. Cited on page 32.

[Sha79] Adi Shamir. How to Share a Secret. *Commun. ACM*, 22(11):612–613, 1979. Cited on page 53.

[Sha84] Adi Shamir. Identity-Based Cryptosystems and Signature Schemes. In *Advances in Cryptology, Proceedings of CRYPTO '84, Santa Barbara, California, USA, August 19-22, 1984, Proceedings*, pages 47–53, 1984. Cited on pages 6 and 18.
[SP06] Kai Schramm and Christof Paar. Higher Order Masking of the AES. In *Topics in Cryptology - CT-RSA 2006, The Cryptographers' Track at the RSA Conference 2006, San Jose, CA, USA, February 13-17, 2006, Proceedings*, pages 208-225, 2006. Cited on page 42.

[SW63] Claude Elwood Shannon and Warren Weaver. *A Mathematical Theory of Communication*. University of Illinois Press, Champaign, IL, USA, 1963. Cited on page 23.

[SW05] Amit Sahai and Brent Waters. Fuzzy Identity-Based Encryption. In *Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings*, pages 457-473, 2005.

[Tan87] Hatsukazu Tanaka. A Realization Scheme for the Identity-Based Cryptosystem. In *Advances in Cryptology - CRYPTO '87, A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings*, pages 340-349, 1987. Cited on pages 6 and 19.

[TI89] Shigeo Tsujii and Toshiya Itoh. An ID-based cryptosystem based on the discrete logarithm problem. *IEEE Journal on Selected Areas in Communications*, 7(4):467-473, 1989. Cited on pages 6 and 19.

[XZQ05] Chunxiang Xu, Junhui Zhou, and Zhiguang Qin. A Note on Secure Key Issuing in ID-based Cryptography. *IACR Cryptology ePrint Archive*, 2005:180, 2005. Cited on pages 106, 109, 117, and 125.