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

[ ]:

[ ]:


Notebook on github