Cryptage homomorphic de Craig Gentry¶
Un cryptage homomorphe préserve l’addition et la multiplication : une addition sur des nombres cryptés est égale au résultat crypté de l’addition sur les nombres non cryptées. Craig Gentry a proposé un tel cryptage dans son article Fully Homomorphic Encryption over the Integers. Le système de cryptage encrypte et décrypte des bits (0 ou 1).
Définition du cryptage¶
\(KeyGen(\lambda)\)
La clé secrète \(sk\) est un entier impair \(p\) codé sur \(\eta\) bits : \(p\in (2\mathbb{Z}+1) \cap [2^{\eta}, 2^{\eta+1}[\).
La clé publique \(pk\) est une séquence de \(\tau+1\) entiers aléatoires tirés selon un loi \(\mathcal{D}_{\gamma,\rho}(p)\). La séquence \((x_0, ..., x_{\tau})\) (doit vérifier \(x_0\) est impair et \(r_p(x_0)\) est pair. Il faut recommencer si ce n’est pas le cas. Chaque entier est codé sur au plus \(\gamma\) bits.
\(Encrypt(pk, m\in \{0,1\})\)
Choisir un ensemble aléatoire \(S \subset \{1, ..., \tau\}\) et un entier aléatoire \(r\) dans l’intervalle \(]-2^{\rho'}, 2^{\rho'}[\). Calculer \(c = (m + 2r + 2\sum_{i \in S} x_i) \mod x_0\).
\(Evaluate(pk, C, c_1, ..., c_t)\)
La fonction \(C\) effectue des opérations sur \(t\) bits. Le résultat est \(c\).
\(Decrypt(sk, c)\)
Le résultat cherché est \((c \mod p) \mod 2\).
Avec : (valeurs suggérées par l’article mais d’autres sont possibles
\(\rho = \lambda\)
\(\rho' = 2\lambda\)
\(\eta \sim O(\lambda^2)\)
\(\gamma \sim O(\lambda^5)\)
\(\tau = \gamma + \lambda\)
Pour simuler une loi \(\mathcal{D}_{\gamma,\rho}(p)\), choisir \(q\) tel que \(q \in \mathbb{Z} \cap \left[0, \frac{2^{\gamma}}{p}\right[\), \(r\) tel que \(r \in \mathbb{Z} \cap \left]-2^{\rho}, 2^{\rho}\right[\) et calculer \(x = pq+r\).
\(r_p(x)\) est le reste de la division entière de \(x\) par \(p\), reste choisi dans l’intervalle \(\left]-\frac{p}{2}, \frac{p}{2}\right]\).
Exercice 1 : implémenter le cryptage¶
[ ]:
Exercice 2 : vérifier que le cryptage est stable par addition et multiplication¶
[ ]:
Exercice 3 : implémententer l’addition entière¶
[ ]:
Exercice 4 : implémenter la multiplication entière¶
[ ]:
[ ]: