# Etude de performance du crypto-système homomorphe sur le calcul matriciel

Safouane Benelkadi

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

## To cite this version:

Safouane Benelkadi. Etude de performance du crypto-système homomorphe sur le calcul matriciel. [Rapport de recherche] Institut d'informatique d'Auvergne - Université Clermont Auvergne. 2020. hal-03423558

HAL Id: hal-03423558

https://uca.hal.science/hal-03423558v1

Submitted on 10 Nov 2021

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

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

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Étude de performance du cryptosystème homomorphe sur le calcul matriciel

Safouane E. BENELKADI

encadré par Mr. Pascal LAFOURCADE

https://forge.clermont-universite.fr/projects/matrix-multiplication-cmake
# Table des matières

<table><tr><td>1 Introduction</td><td>1</td></tr><tr><td>2 Méthodes de multiplication matricielles utilisés</td><td>2</td></tr><tr><td>2.1 Algorithmes de multiplication matricielle</td><td>2</td></tr><tr><td>2.1.1 Algorithme naïve de multiplication matricielle</td><td>2</td></tr><tr><td>2.1.2 Algorithme de Strassen de multiplication matricielle</td><td>2</td></tr><tr><td>2.1.3 Algorithme de Strassen amélioré de multiplication matricielle</td><td>4</td></tr><tr><td>3 Librairies homomorphes utilisées</td><td>4</td></tr><tr><td>3.1 Microsoft Simple Encrypted Arithmetic Library (SEAL)</td><td>4</td></tr><tr><td>3.2 Homomorphic Encryption Library HELIB</td><td>5</td></tr><tr><td>4 Chiffrement homomorphe</td><td>5</td></tr><tr><td>4.1 Technique du chiffrement homomorphe</td><td>6</td></tr><tr><td>5 Algorithmes implémentant le chiffrement homomorphe</td><td>6</td></tr><tr><td>5.1 Algorithme Client</td><td>6</td></tr><tr><td>5.2 Algorithme Serveur</td><td>7</td></tr><tr><td>5.3 Algorithmes de multiplication matricielle chiffré</td><td>7</td></tr><tr><td>5.4 Optimisation</td><td>7</td></tr><tr><td>6 Résultats</td><td>8</td></tr><tr><td>6.1 Complexité de l'algorithme Naïve implementer avec SEAL pour différents nombres de multiplication de matrice A</td><td>8</td></tr><tr><td>6.2 Complexité de l'algorithme Strassen implementer avec SEAL pour différents nombres de multiplication de matrice A</td><td>9</td></tr><tr><td>6.3 Complexité de l'algorithme Naïve implementer avec HELIB pour différents nombres de multiplication de matrice A</td><td>10</td></tr><tr><td>6.4 Complexité de l'algorithme Strassen implementer avec HELIB pour différents nombres de multiplication de matrice A</td><td>11</td></tr><tr><td>6.5 Comparaison de performance entre l'algorithme naïve et strassen implémenté en SEAL pour A.A</td><td>12</td></tr><tr><td>6.6 Comparaison de performance entre l'algorithme naïve et strassen implémenté en HELIB pour A.A</td><td>13</td></tr><tr><td>6.7 Comparaison de performance entre la bibliothèque SEAL et HELIB sur l'algorithme naïve pour A.A</td><td>14</td></tr><tr><td>6.8 Comparaison de performance entre la bibliothèque SEAL et HELIB sur l'algorithme naïve pour A.A.A</td><td>15</td></tr><tr><td>6.9 Comparaison de performance entre la bibliothèque SEAL et HELIB sur l'algorithme naïve pour A.A.A.A</td><td>16</td></tr><tr><td>6.10 Comparaison de performance entre la bibliothèque SEAL et HELIB sur l'algorithme naïve pour A.A</td><td>17</td></tr><tr><td>6.11 Comparaison de performance entre la bibliothèque SEAL et HELIB sur l'algorithme naïve pour A.A.A</td><td>18</td></tr><tr><td>6.12 Comparaison de performance entre la bibliothèque SEAL et HELIB sur l'algorithme naïve pour A.A.A.A</td><td>19</td></tr><tr><td>7 Observations</td><td>20</td></tr><tr><td>8 Conclusion</td><td>20</td></tr></table>
Deux librairies de chiffrement homomorphe *Microsoft Simple Encrypted Arithmetic Library (SEAL)* [2] et *Homomorphic Encryption Library (HELib)*[3] sont comparé en performance sur de la multiplication matricielle. L'algorithme de Strassen de multiplication matricielle ainsi que l'algorithme naïve de multiplication matricielle sont implémenté et comparé avant et après l'intégration des librairies de chiffrement homomorphe à l'implémentation des deux algorithme. Un troisième algorithme se basant sur l'algorithme de Strassen basculant sur l'algorithme naïve est implémenté et comparé avant et après l'intégration avec les deux librairies de chiffrement homomorphe.

Le but final est de comparer les performances temporelles des même algorithmes sur le même environnement intégrant différentes librairies de chiffrement homomorphe sur des matrices de tailles croissantes. L'opération matricielle est $A.A$ avec $A$ une matrice carrée de taille $k$ variable où $k$ est une puissance de 2.

**Mots-clés** : Chiffrement homomorphe, Algorithme de Strassen de multiplication matricielle, Microsoft SEAL, HELib, Complexité temporelle.

# 1 Introduction

Le but du chiffrement homomorphe est d'autoriser les calculs sur les données chiffrées. Les données peuvent ainsi demeurer confidentielles lors de leur traitement afin de pouvoir effectuer des tâches utiles sur les données stockées dans des environnements non sécurisés. À l'époque des calculs distribués et des réseaux hétérogènes, il s'agit sans nul doute d'un avantage décisif.

Un cryptosystème homomorphe est similaire aux autres formes de chiffrement public, dans le sens où il emploie une clé publique pour chiffrer les données et autorise uniquement la personne disposant de la clé privée correspondante à accéder aux données déchiffrées. Ce qui la différencie toutefois des autres formes de chiffrement est son recours à un système algébrique pour permettre à une personne d'effectuer un ensemble de calculs sur les données chiffrées.

La problématique est de vérifier l'impact de performance des opérations d'évaluateur appliqués directement sur des données chiffrées grâce au chiffrement homomorphe, et de comparé l'impact sur la performance en temps causé par les deux librairies de chiffrement homomorphe. Les opérations seront des multiplications matricielles sur des matrices carrées de tailles variables, en implémentant les algorithmes de Strassen et naïve de multiplication matricielle et un troisième algorithme basculant entre les deux en se basant sur la taille $k$ de la matrice carrée où $k$ est une puissance de 2.

Pour cela il est nécessaire d'implémenter les algorithmes de multiplication matricielle et de récolter des données de performance en temps sur les opérations arithmétique appliqués sur des données non chiffrées, et des opérations d'évaluateur appliquées sur des données chiffrées en intégrant les deux librairies à l'implémentation des algorithmes de multiplication matricielle, cela sur le même environnement. Et de les comparer.
# 2 Méthodes de multiplication matricielles utilisés

## 2.1 Algorithmes de multiplication matricielle

### 2.1.1 Algorithme naïve de multiplication matricielle

La définition de la multiplication matricielle classique (appelée naïve) est que si $C = AB$ pour une matrice $n \times m$ et une matrice $p \times q$, alors $C$ est une matrice $np$ avec des entrées Algorithme de multiplication matricielle

$$c_{ij} = \sum_{k=1}^{m} a_{ik}b_{kj}$$

**Algorithm 1 Algorithme Naïve de multiplication matricielle**

**Entrés** : Matrices $A, B$ **Sortie** : Matrice $C$

for $i = 1, ..., n$ do

for $j = 1, ..., p$ do

Soit $Somme = 0$

for $k = 1, ..., m$ do

$Somme = Somme + A_{i,k} \cdot B_{k,j}$

$C_{i,j} = Somme$

end for

end for

end for

Retourner $C$

Complexité de l'algorithme naïve est de :

$$O(8^{\log_2 n}) = O(N^{\log_2 8}) = O(N^3)$$

### 2.1.2 Algorithme de Strassen de multiplication matricielle

Nous avons les trois matrices $A, B$ et $C$ sont divisées en matrices par blocs de taille égale :

$$A = \begin{bmatrix} A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{bmatrix}, B = \begin{bmatrix} B_{1,1} & B_{1,2} \\ B_{2,1} & B_{2,2} \end{bmatrix}, C = \begin{bmatrix} C_{1,1} & C_{1,2} \\ C_{2,1} & C_{2,2} \end{bmatrix}$$

Où :

$$A_{i,j}, B_{i,j}, C_{i,j} \in R^{2^{n-1} \times 2^{n-1}}$$

La force de l'algorithme de Strassen réside dans un ensemble de sept nouvelles matrices $M_i$ qui vont servir à exprimer les $C_{i,j}$ avec seulement 7 multiplications au lieu de 8 pour l'algorithme naïve :

$$M_1 := (A_{1,1} + A_{2,2})(B_{1,1} + B_{2,2})$$

$$M_2 := (A_{2,1} + A_{2,2})B_{1,1}$$

$$M_3 := A_{1,1}(B_{1,2} - B_{2,2})$$

$$M_4 := A_{2,2}(B_{2,1} - B_{1,1})$$

$$M_5 := (A_{1,1} + A_{1,2})B_{2,2}$$

$$M_6 := (A_{2,1} - A_{1,1})(B_{1,1} + B_{1,2})$$

$$M_7 := (A_{1,2} - A_{2,2})(B_{2,1} + B_{2,2})$$

Les $C_{i,j}$ sont alors exprimées comme :

$$C_{1,1} = M_1 + M_4 - M_5 + M_7$$

$$C_{1,2} = M_3 + M_5$$

$$C_{2,1} = M_2 + M_4$$

$$C_{2,2} = M_1 - M_2 + M_3 + M_6$$
Le procédé est reproduit récursivement jusqu'à ce que les matrices A et B soient « de petite taille », la définition de ce qu'est considéré comme la petite taille est ce qui nous mènera vers le troisième algorithme.

La complexité de l'algorithme de Strassen est de :

$$O([7 + o(1)]^n) = O(N^{\log_2 7 + o(1)}) \approx O(N^{2.8074})$$

**Algorithm 2** Algorithme **Strassen** de multiplication matricielle

**Entrés :** Matrices A, B, Entier Dimension

if Dimension == 1 then

Retourner A.B

end if

k =: Dimension

for i =: 1, ..., k do

for j =: 1, ..., k do

$$A_{1,1}[i][j] := A[i][j]$$

$$A_{1,2}[i][j] := A[i][k + j]$$

$$A_{2,1}[i][j] := A[k + i][j]$$

$$A_{2,2}[i][j] := A[k + i][k + j]$$

$$B_{1,1}[i][j] := B[i][j]$$

$$B_{1,2}[i][j] := B[i][k + j]$$

$$B_{2,1}[i][j] := B[k + i][j]$$

$$B_{2,2}[i][j] := B[k + i][k + j]$$

end for

end for

$M_1 := \text{Strassen}(A_{1,1} + A_{2,2}, B_{1,1} + B_{2,2}, k);$

$M_2 := \text{Strassen}(A_{2,1} + A_{2,2}, B_{1,1}, k);$

$M_3 := \text{Strassen}(A_{1,1}, B_{1,2} - B_{2,2}, k);$

$M_4 := \text{Strassen}(A_{2,2}, B_{2,1} - B_{1,1}, k);$

$M_5 := \text{Strassen}(A_{1,1} + A_{1,2}, B_{2,2}, k);$

$M_6 := \text{Strassen}(A_{2,1} - A_{1,1}, B_{1,1} + B_{1,2}, k);$

$M_7 := \text{Strassen}(A_{1,2} - A_{2,2}, B_{2,1} + B_{2,2}, k);$

$C_{1,1} := M_1 + M_4 - M_5 + M_7$

$C_{1,2} := M_3 + M_5$

$C_{2,1} := M_2 + M_4$

$C_{2,2} := M_1 - M_2 + M_3 + M_6$

for i =: 1, ..., k do

for j =: 1, ..., k do

$$C[i][j] := C_{1,1}[i][j]$$

$$C[i][k + j] := C_{1,2}[i][j]$$

$$C[k + i][j] := C_{2,1}[i][j]$$

$$C[k + i][k + j] := C_{2,2}[i][j]$$

end for

end for

Retourner C;
### 2.1.3 Algorithme de Strassen amélioré de multiplication matricielle

Il n'est pas nécessaire ou désirable d'utiliser l'algorithme Strassen de multiplication matricielle jusqu'au valeurs scalaires, En le comparant avec l'algorithme naïve de multiplication matricielle, l'algorithme de Strassen ajoute une perte de performance considérable de $O(n^2)$, dans l'addition et la soustraction, donc en dessous d'une certaine taille de bloc de matrices, l'utilisation de la multiplication conventionnelle est plus optimale.

<table><caption>**Algorithm 3** Algorithme Strassen amélioré de multiplication matricielle</caption><tr><td>Entrés</td><td>Matrices A, B, Entier Limite</td></tr><tr><td>if</td><td>Taille des matrices A,B inférieurs ou égale à Limite then</td></tr><tr><td></td><td>Retourner AlgorithmeNaive( A, B )</td></tr><tr><td>else</td><td>Continuez Algorithme Strassen</td></tr><tr><td>end if</td><td></td></tr></table>

## 3 Librairies homomorphes utilisées

### 3.1 Microsoft Simple Encrypted Arithmetic Library (SEAL)

Microsoft SEAL est une bibliothèque de cryptage homomorphique open source (sous licence MIT), développée par le Cryptography and Privacy Research Group de Microsoft. Microsoft SEAL est écrit en C++ standard moderne et peut être compilée et exécutée dans de nombreux environnements différents.

Microsoft SEAL permet d'effectuer des ajouts et des multiplications sur des entiers chiffrés ou des nombres réels. D'autres opérations, telles que la comparaison chiffrée, le tri ou les expressions régulières, ne sont pas évaluable dans la plupart des cas sur des données chiffrées à l'aide de cette technologie. Par conséquent, seules les parties de calcul cloud critiques pour la confidentialité des programmes doivent être implémentées avec Microsoft SEAL.

Il n'est pas toujours facile ou direct de traduire un calcul non chiffré en un calcul sur des données chiffrées, par exemple, il n'est pas possible de créer une branche sur des données chiffrées. Microsoft SEAL a une courbe d'apprentissage abrupte et oblige l'utilisateur à comprendre de nombreux concepts spécifiques au cryptage homomorphique, même si au final l'API n'est pas trop compliquée. Même si un utilisateur est capable de programmer et d'exécuter un calcul spécifique à l'aide de Microsoft SEAL, la différence entre les implémentations efficaces et inefficaces peut être de plusieurs ordres de grandeur, et il peut être difficile pour les nouveaux utilisateurs de savoir comment améliorer les performances de leur calcul.

Microsoft SEAL est livré avec deux schémas de chiffrement homomorphes différents avec des propriétés très différentes. Le schéma BFV permet d'effectuer l'arithmétique modulaire sur des entiers chiffrés. Le schéma CKKS permet des ajouts et des multiplications sur des nombres réels ou complexes chiffrés, mais ne donne que des résultats approximatifs. Dans des applications telles que la sommation de nombres réels chiffrés, l'évaluation de modèles d'apprentissage automatique sur des données chiffrées ou le calcul des distances d'emplacements chiffrés, CKKS sera de loin le meilleur choix. Pour les applications où des valeurs exactes sont nécessaires, le schéma BFV est le seul choix.
## 3.2 Homomorphic Encryption Library HELib

HELib est une bibliothèque logicielle open source (Apache License v2.0) qui implémente le cryptage homomorphique (HE). Les schémas actuellement disponibles sont les implémentations du schéma de Brakerski-Gentry-Vaikuntanathan (BGV) avec bootstrapping et le schéma de nombre approximatif de Cheon-Kim-Kim-Song (CKKS), ainsi que de nombreuses optimisations pour accélérer l'évaluation homomorphe, en se concentrant principalement sur utilisation efficace des techniques d'emballage de texte chiffré Smart-Vercauteren et des optimisations Gentry-Halevi-Smart. HELib a été principalement développé par Shai Halevi et Victor Shoup, peu de temps après que Craig Gentry était chercheur chez IBM, la version initiale étant le 5 mai 2013.

HELib prend en charge un «langage d'assemblage pour HE», fournissant des routines de bas niveau (définir, ajouter, multiplier, déplacer, etc.), une gestion automatique sophistiquée du bruit, un bootstrapping BGV amélioré, le multi-threading et également le support des objets Ptxt (texte en clair) qui imite la fonctionnalité des objets Ctxt (texte chiffré). Le rapport Conception et mise en œuvre de HELib contient des détails supplémentaires. HELib est écrit en C++17 et utilise la bibliothèque mathématique NTL.

Le cryptosystème sous-jacent sert d'équivalent d'une «plate-forme matérielle» pour HELib, en ce qu'il définit un ensemble d'opérations qui peuvent être appliquées de manière homomorphique, et spécifie leur coût. Cette «plate-forme» est un environnement SIMD (un peu similaire à Intel SSE et autres).

# 4 Chiffrement homomorphe

Le chiffrement homomorphe fait référence à des schémas de chiffrement qui permettent au cloud de calculer directement sur les données chiffrées, sans exiger que les données soient d'abord déchiffrées. Les résultats de ces calculs chiffrés restent chiffrés et ne peuvent être déchiffrés qu'avec la clé secrète (par le propriétaire des données). De multiples schémas de chiffrement homomorphes avec des capacités et des compromis différents ont été inventés au cours de la dernière décennie ; la plupart d'entre eux sont des schémas de chiffrement à clé publique, bien que la fonctionnalité de clé publique ne soit pas toujours nécessaire.

Le chiffrement homomorphe n'est pas une technologie générique : seuls certains calculs sur des données chiffrées sont possibles. Il est également livré avec une surcharge de performances substantielle, de sorte que les calculs déjà très coûteux à effectuer sur des données non cryptées sont susceptibles d'être irréalisables sur des données cryptées. De plus, les données cryptées avec un cryptage homomorphe sont plusieurs fois plus volumineuses que les données non cryptées, il peut donc ne pas avoir de sens de crypter, par exemple, des bases de données entières de grande taille, avec cette technologie. Au lieu de cela, des cas d'utilisation significatifs se trouvent dans des scénarios où des exigences de confidentialité strictes interdisent complètement le calcul cloud non chiffré, mais les calculs eux-mêmes sont assez légers.

En règle générale, les schémas de chiffrement homomorphes ont une seule clé secrète qui est détenue par le propriétaire des données. Pour les scénarios où plusieurs propriétaires de données privées différents souhaitent s'engager dans le calcul collaboratif, le cryptage homomorphe n'est probablement pas une solution raisonnable.

Le cryptage homomorphe ne peut pas être utilisé pour permettre aux data scientists de contourner le RGPD. Par exemple, il n'existe aucun moyen pour un service cloud d'utiliser le chiffrement homomorphe pour tirer des informations à partir des données client chiffrées. Au lieu de cela, les résultats des calculs chiffrés restent chiffrés et ne peuvent être déchiffrés que par le propriétaire des données, par exemple, un client du service cloud.
## 4.1 Technique du chiffrement homomorphe

Étant donné $C$ l'espace des chiffrés, $M$ l'espace des messages, et $F$ l'espace des fonctions évaluables, on définit un chiffrement homomorphe sur $F$ le quadruplet d'algorithmes $(\mathcal{K}, \mathcal{E}, \mathcal{D}, \text{Eval})$ tel que :

$\mathcal{K}: \mathbb{N} \rightarrow PK \times SK$ : la fonction de génération des clefs;

$\mathcal{E}: M \rightarrow C$ est la fonction de chiffrement;

$\mathcal{D}: C \rightarrow M$ est la fonction de déchiffrement;

$\text{Eval}: F \times C \times C \rightarrow C$ est la fonction d'évaluation.

On souhaite avoir les propriétés suivantes :

La correction :

$\mathcal{D}(\mathcal{E}(m)) = m;$

L'homomorphisme :

$\forall f \in F, \mathcal{D}(\text{Eval}(f, C_1, C_2)) = f(\mathcal{D}(C_1), \mathcal{D}(C_2)).$

Le système de chiffrement homomorphe utilise deux clés de chiffrement asymétrique. L'implémentation considère un espace de confiance (appelé client) ou les matrices sont créées, chiffrés et déchiffrés. Un deuxième espace de non confiance (appelé serveur) est considéré pour être utilisé pour uniquement appliqués les fonctions implémentant les algorithmes de multiplication de matrices chiffrés. Il est cruciale de garder la clé de déchiffrement dite clé privé inaccessible en dehors de l'espace de confiance, la clé de chiffrement dite clé public peut être transmise à l'espace de non confiance si cela est nécessaire.

Aucune clé ne sera transmise à l'espace de non confiance, le contexte sera transmis car nécessaire à la création de d'évaluateur qui contient les méthodes arithmétique.

# 5 Algorithmes implémentant le chiffrement homomorphe

## 5.1 Algorithme Client

**Algorithm 4 CLIENTMultiplicationChiffres :**

**Entrés :** Entier $k$

Création de matrices $A, B, C$ de dimensions $k$

Création du contexte de chiffrement

Création de la clepublique et cleprive à partir du contexte

Soit $T = k.k$ la taille d'une matrice.

Chiffrement de $T$ entiers en utilisant clepublique.

Remplissage des matrices $A, B$ avec les entiers chiffrés.

$C = SERVEURMultiplicationChiffres(A, B, C, Option, contexte)$

Déchiffrement des valeurs contenus dans $C$ en utilisant cleprive
## 5.2 Algorithme Serveur

**Algorithm 5 SERVEUR**
**Multiplication Chiffres :**

**Entrés :** Matrices : *A*, *B*, *C*, Entier : *Option*

if *Option* = 0 **then**

AlgorithmeNaiveChiffrer(*A*,*B*,*C*, *Contexte*)

else

if *Option* = 1 **then**

AlgorithmeStrassenChiffrer(*A*,*B*,*C*, *Contexte*)

else

AlgorithmeStrassenAmeliorerChiffrer(*A*,*B*,*C*, *Contexte*)

end if

end if

Retourner *C*

## 5.3 Algorithmes de multiplication matricielle chiffré

Les algorithmes de multiplication matricielle chiffré Naïve, Strassen et Strassen amélioré sont algorithmiquement identique. L'implémentation est différente car les librairies de chiffrement homomorphe utilise des instructions et méthodes spéciales pour appliquer les opérations arithmétique sur les valeurs chiffrés. Cela nécessite d'instancier un évaluateur à partir du contexte, puis utiliser les méthodes arithmétique de d'évaluateur en substitution aux opérations classique.

## 5.4 Optimisation

L'algorithme de Strassen est un algorithme récursive, implémenter en C++ et nécessitant énormément d'optimisation et de technicité afin d'exploiter son potentiel.

L'algorithme itérative naïve est un algorithme simple utilisant des additions et multiplication algébrique très optimisé sur les architecture actuelle.

Algorithmiquement l'avantage de l'algorithme Strassen sur l'algorithme naïve est évident en comparant leurs complexité en temps, néanmoins l'implémentation prends en considération d'autres facteurs, notamment l'architecture de la machine, et l'expertise dans le C++.

En 2010 l'algorithme de Strassen était plus performant que l'algorithme naïve de 10% en basculant vers l'algorithme naïve a partir d'une taille de matrice de 1000 [1]. Avant cette date l'algorithme de Strassen était plus performant en basculant sur des matrices de tailles 32 à 128 [5]. Plus récemment en 2016 une performance de plus de 20% que l'algorithme naïve en basculant a partir de matrices de taille de 512 [4], Ces évolutions et changement de performance sont du aux constantes évolutions et optimisations architecturales des machines qui influencent sur les performances observées.

Une solution serait d'implémenter l'algorithme de Strassen sous forme d'une récursion terminale. Cela nous conduira à implémenter un algorithme Strassen ayant un appel récursive comme dernière instruction.
# 6 Résultats

## 6.1 Complexité de l'algorithmé Naïve implementer avec SEAL pour différents nombres de multiplication de matrice A

<figure><img src="image_3.png" /><figcaption>FIGURE 1 – Complexité de l’algorithmé naïve implementer avec SEAL pour différents nombres de multiplication de matrice A</figcaption></figure>
6.2 Complexite de l'algorithmes Strassen implementer avec SEAL pour différents nombres de multiplication de matrice A

<figure><img src="image_4.png" /><figcaption>FIGURE 2 – Complexité de l’algorithmes strassen implémenter avec SEAL pour différents nombres de multiplication de matrice A</figcaption></figure>
6.3 Complexite de l’algorithme Naive implementer avec HELIB pour différents nombres de multiplication de matrice A

<figure><img src="image_5.png" /><figcaption>FIGURE 3 – Complexité de l’algorithme naïve implémenter avec HELIB pour différents nombres de multiplication de matrice A</figcaption></figure>
6.4 Complexite de l'algorithme Strassen implementer avec HELIB pour différents nombres de multiplication de matrice A

<figure><img src="image_6.png" /><figcaption>FIGURE 4 – Complexité de l'algorithme strassen implémenter avec HELIB pour différents nombres de multiplication de matrice A</figcaption></figure>
6.5 Comparaison de performance entre l’algorithme naïve et strassen implémenté en SEAL pour A.A

<figure><img src="image_7.png" /><figcaption>FIGURE 5 – Comparaison de performance entre l’algorithme naïve et strassen implémenté en SEAL pour A.A</figcaption></figure>
6.6 Comparaison de performance entre l’algorithme naïve et strassen implémenté en HELIB pour A.A

<figure><img src="image_8.png" /><figcaption>FIGURE 6 – Comparaison de performance entre l’algorithme naïve et strassen implémenté en SEAL pour A.A</figcaption></figure>
6.7 Comparaison de performance entre la bibliothèque SEAL et HELIB sur l'algorithme naive pour A.A

<figure><img src="image_9.png" /><figcaption>FIGURE 7 – Comparaison de performance entre la bibliothèque SEAL et HELIB sur l’algorithme naive pour A.A</figcaption></figure>
6.8 Comparaison de performance entre la bibliothèque SEAL et HELIB sur l'algorithme naïve pour A.A.A

<figure><img src="image_10.png" /><figcaption>FIGURE 8 – Comparaison de performance entre la bibliothèque SEAL et HELIB sur l’algorithme naïve pour A.A.A</figcaption></figure>
6.9 Comparaison de performance entre la bibliothèque SEAL et HELIB sur l'algorithme naïve pour A.A.A.A.A

<figure><img src="image_11.png" /><figcaption>FIGURE 9 – Comparaison de performance entre la bibliothèque SEAL et HELIB sur l’algorithme naïve pour A.A.A.A.A</figcaption></figure>
6.10 Comparaison de performance entre la bibliothèque SEAL et HELIB sur l'algorithme naive pour A.A

<figure><img src="image_12.png" /><figcaption>FIGURE 10 – Comparaison de performance entre la bibliothèque SEAL et HELIB sur l’algorithme Strassen pour A.A</figcaption></figure>
6.11 Comparaison de performance entre la bibliothèque SEAL et HELIB sur l'algorithme naïve pour A.A.A

<figure><img src="image_13.png" /><figcaption>FIGURE 11 – Comparaison de performance entre la bibliothèque SEAL et HELIB sur l’algorithme Strassen pour A.A.A</figcaption></figure>
6.12 Comparaison de performance entre la bibliothèque SEAL et HELIB sur l'algorithme naïve pour A.A.A.A

<figure><img src="image_14.png" /><figcaption>FIGURE 12 – Comparaison de performance entre la bibliothèque SEAL et HELIB sur l’algorithme Strassen pour A.A.A.A.A</figcaption></figure>
# 7 Observations

Les algorithmes naïve et Strassen amélioré implémentés avec *Microsoft SEAL* démontrent une complexité exponentielle pour l'opération $A^k$ avec $k \in \{2, 3, 4\}$ et *Aunematricecarre*, la différence de complexité observée sur un même algorithme pour différentes valeurs de $k$ est ascendante et stable quand la valeur de $k$ augmente. L'algorithme Strassen est plus efficace et rapide que l'algorithme naïve. **Figure 1 et 2.**

Les algorithmes naïve et Strassen amélioré implémentés avec *HElib* démontrent une complexité exponentielle pour l'opération $A^k$ avec $k \in \{2, 3\}$, la différence de complexité observée sur l'algorithme Strassen amélioré pour différentes valeurs de $k$ est ascendante et stable quand la valeur de $k$ augmente. L'algorithme naïve a une complexité non stable pour $k = 3$ et s'arrête de fonctionner à cause du *bruit* qui devient trop grand. L'algorithme Strassen est plus efficace et rapide que l'algorithme naïve. Microsoft SEAL donne de mauvais résultat à partir de $K = 4$. **Figure 3 et 4.**

L'algorithme naïve implémenter sur *Microsoft SEAL* et *HElib* démontre une grande différence de performance entre les deux bibliothèques, *SEAL* est très performante comparé à *HELIB*. **Figure 7, 8 et 9.**

L'algorithme naïve implémenter sur *Microsoft SEAL* et *HElib* démontre une grande différence de performance entre les deux bibliothèques, *SEAL* est très performante comparé à *HELIB*. **Figure 10, 11 et 12.**

Le chiffrement homomorphe est d'une complexité trop importante pour envisager de l'implémenter à l'état actuelle dans des opérations de traitement de données qui sont déjà très complexe avec des opérations en texte clair.

# 8 Conclusion

*Microsoft SEAL* est plus performante que *HElib* pour les opérations de multiplication matricielle en complexité de temps, *Microsoft SEAL* a une meilleure gestion du *bruit* lui permettant d'avoir des limites supérieurs à *HELIB*, mais n'avertis pas en cas de problème pendant le déchiffrement du au bruit cela nécessite un contrôle manuel.

L'algorithme de Strassen amélioré est plus efficace que l'algorithme naïve.

Le chiffrement homomorphe est limité parce que chaque texte chiffré est bruyant dans un certain sens, et ce bruit augmente à mesure que l'on ajoute et multiplie les textes chiffrés, jusqu'à ce que finalement le bruit rende le texte chiffré résultant indéchiffrable. Donc le chiffrement homomorphe doit être utilisé pour des cas spécifiques en tenant en compte ces faiblesse notamment le bruit.

# Références

[1] Alexandru ALBERTO Paolo; Nicolau. *Using Recursion to Boost ATLAS's Performance*. Sixth Int'l Symp. on High Performance Computing. 2005.

[2] Rachel Player HAO CHEN Kim Laine. *Simple Encrypted Arithmetic Library* - *SEAL v2.1*. 2017.

[3] *Homomorphic Encryption Library*.

[4] Jianyu HUANG. *Strassen's Algorithm Reloaded*. International Conference for High Performance Computing, Networking, Storage and Analysis (SC'16). 2016.

[5] Steven S SKIENA. §8.2.3 "Matrix multiplication", The Algorithm Design Manual, Berlin, New York: 1998.