.. _gentryintegerencryptioncorrectionrst: ================================================= Cryptage homomorphic de Craig Gentry - correction ================================================= .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/td2a_algo/gentry_integer_encryption_correction.ipynb|*` 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. .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: Définition du cryptage ---------------------- :math:`KeyGen(\lambda)` - La clé secrète :math:`sk` est un entier impair :math:`p` codé sur :math:`\eta` bits : :math:`p\in (2\mathbb{Z}+1) \cap [2^{\eta}, 2^{\eta+1}[`. - La clé publique :math:`pk` est une séquence de :math:`\tau+1` entiers aléatoires tirés selon un loi :math:`\mathcal{D}_{\gamma,\rho}(p)`. La séquence :math:`(x_0, ..., x_{\tau})` (doit vérifier :math:`x_0` est impair et :math:`r_p(x_0)` est pair. Il faut recommencer si ce n’est pas le cas. Chaque entier est codé sur au plus :math:`\gamma` bits. :math:`Encrypt(pk, m\in \{0,1\})` Choisir un ensemble aléatoire :math:`S \subset \{1, ..., \tau\}` et un entier aléatoire :math:`r` dans l’intervalle :math:`]-2^{\rho'}, 2^{\rho'}[`. Calculer :math:`c = (m + 2r + 2\sum_{i \in S} x_i) \mod x_0`. :math:`Evaluate(pk, C, c_1, ..., c_t)` La fonction :math:`C` effectue des opérations sur :math:`t` bits. Le résultat est :math:`c`. :math:`Decrypt(sk, c)` Le résultat cherché est :math:`(c \mod p) \mod 2`. **Avec :** (valeurs suggérées par l’article mais d’autres sont possibles - :math:`\rho = \lambda` - :math:`\rho' = 2\lambda` - :math:`\eta \sim O(\lambda^2)` - :math:`\gamma \sim O(\lambda^5)` - :math:`\tau = \gamma + \lambda` - Pour simuler une loi :math:`\mathcal{D}_{\gamma,\rho}(p)`, choisir :math:`q` tel que :math:`q \in \mathbb{Z} \cap \left[0, \frac{2^{\gamma}}{p}\right[`, :math:`r` tel que :math:`r \in \mathbb{Z} \cap \left]-2^{\rho}, 2^{\rho}\right[` et calculer :math:`x = pq+r`. - :math:`r_p(x)` est le reste de la division entière de :math:`x` par :math:`p`, reste choisi dans l’intervalle :math:`\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 --------------------------------------------------