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