Cryptage homomorphic de Craig Gentry - correction¶

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). Correction.

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