5.4 Multiplication Matricielle
5.4.1 Algorithme de multiplication matricielle
na·ive
Soient deux matrices carrées A E nxn
et B E nxn, le produit matriciel C =
A x B s'obtient par:
cij = Xn aik x bk j
pour 1 ~ i ~ n, 1 ~ j ~ n k=1
5.4 Multiplication Matricielle 59
Mémoire de Master 2 Recherche 59 MOUYOUME
DIEUDONNE(c) UYI
Algorithm 3 Multiplication matricielle
naïve
Fonction ProduitMatriciel(A, B)
Entrée: A ?
Rn×n, B ?
Rn×n
Sortie : C ?
Rn×n tel que C =
A × B début
C ? 0n×n
pour i ? 1 to m
faire pour j ? 1 to n
faire
pour k ? 1 to n
faire
C[i, j] ? C[i,
j] + A[i, k] ×
B[k, j]
Retourner C
La complexité temporelle est en
O(n3).
5.4.2 Algorithme de multiplication homomorphe
matricielle
Algorithm 4 Algorithme de multiplication
matricielle homomorphe
Entrée: M1, M2 ?
Zn×n, A (paramètre de
sécurité)
Sortie : M3 = M1 × M2
Fonction MultFHE(A)
début
Génération des clés
(pk, sk) ? KeyGen(A)
Phase de chiffrement
pour i ? [1, n]
faire
pour j ? [1,n]
faire
Qmi1j
Enc(pk, M1[i, j])
Qmi2j
Enc(pk, M2[i, j])
Calcul homomorphe
pour i ? [1, n]
faire
pour j ? [1,n]
faire
Jci jK
?1101] pour k ? [1,
n] faire
Jci jK
?FHE-Add(QcijK,
FHE-Mult(Qmik1]],
Qmk2jK))
Phase de déchiffrement pour i ?
[1, n] faire
pour j ? [1,n]
faire
M3[i, j] ? Dec(sk,
QcijK)
retourner M3
La complexité temporelle de cet algorithme est en
O(n3).
5.5 Tests 60
Mémoire de Master 2 Recherche 60 MOUYOUME
DIEUDONNE(c) UYI
5.5 Tests
Pour les tests, nous avons créé dans chaque dossier
contenant le script .cpp un CMakeList.txt. La compilation et
l'exécution de chaque projet se font en suivant les étapes
suivantes:
5.5.1 Le cas de SEAL
Il suffit de suivre les étapes suivantes:
1 cd SEAL
2 cd nom du dossier du projet
3 sudo cmake -S . B build
4 sudo cmake build build
5 sudo cmake install build
6 ./nom de l'exécutable
5.5.2 Le cas de OpenFHE
Il suffit de suivre les étapes suivantes:
1 cd Openfhe-development
2 cd nom du dossier du projet
3 mkdir build
4 cd build
5 sudo cmake ..
6 sudo make
7 ./nom de l'exécutable
5.5.3 Le cas de PALISADE
Il suffit de suivre les étapes suivantes:
1 cd palisade
2 cd nom du dossier du projet
3 mkdir build
4 cd build
5 sudo cmake ..
6 sudo make
7 ./nom de l'exécutable
5.6 Exécution des programmes 61
Mémoire de Master 2 Recherche 61 MOUYOUME
DIEUDONNE(c) UYI
5.6 Exécution des programmes
Dans cette section, nous montrons comment les différents
programmes sont exécutés au cas par cas.
5.6.1 Cas de SEAL
Pour le cas de SEAL avec les cryptosystèmes BGV et BFV,
les figures 5.2 et 5.3 ci-dessous montrent les étapes à suivre
pour exécuter les différents programmes.
FIGURE 5.2 - Exécution du programme avec BGV FIGURE 5.3 -
Exécution du programme avec BFV
| 
