Le chiffrement DGHV

Introduction

Ce cryptosystème a été créé par l'équipe Dijk-Gentry-Halevi-Vaikuntanathan (DGHV) en 2010 suite aux travaux de Craig Gentry sur le chiffrement homomorphe.

Ce chiffrement permet d'effectuer des opérations homomorphes (additions et multiplication) sur des entiers chiffrés. Le but de ce cryptosystème est de construire un cryptosystème totalement homormorphe plus simple que le premier développé en 2009 par Craig Gentry.

Le chiffrement de DGHV repose sur le problème du PGCD approché (Approximate Greatest Common Divisor) et sur le problème de la somme de sous-ensembles (Sparse Subset Sum Problem). Le problème de la somme de sous-ensemble permet de réaliser un chiffrement avec la clef publique sécurisé, et le problème du PGCD approché intervient pour la génération de la clef publique.

Algorithme

Il existe deux versions du chiffrement DGHV. La première est un chiffrement symétrique, cela signifie que nous n'utilisons qu'une seule clef, et que seule la personne détenant cette clef peut chiffrer ou déchiffrer un message. La seconde version est un chiffrement asymétrique. Dans ce cas nous utilisons deux clefs, une clef publique qui permet de chiffrer le message, et une clef privée qui permet de le déchiffrer.

La méthode de déchiffrement est la même pour les deux versions. En revanche, c'est la méthode de chiffrement qui change. Dans le cas asymétrique, nous devons générer une clef publique à partir de la clef privée, mais la clef publique ne doit pas laisser transparaître la clef privée.

Dans un premier temps, nous allons vous présenter le principe du chiffrement symétrique, qui permet d'expliquer plus facilement le caractère homomorphe de ce chiffrement. Puis, nous vous proposerons une démonstration du chiffrement asymétrique.

Principe du chiffrement symétrique DGHV

Nous chiffrons notre message en y ajoutant du bruit aléatoire, ainsi que la clef privée multipliée par un nombre aléatoire. Ce chiffrement ne permet de chiffrer que des \(0\) et des \(1\), il faut donc convertir notre message en binaire avant de le chiffrer.

Contrairement au chiffrement RSA, le chiffrement DGHV est un chiffrement probabiliste. Cela signifie que le chiffré de \(0\) ou \(1\) n'est jamais identique, même si la clef est la même. Cela est rendu possible par le bruit, \(r\), qui est généré et ajouté à chaque processus de chiffrement.

1. Soit \(p\) la clef privée, nombre impair aléatoire tel que \( p \in [2^{etha-1}, 2^{etha}] \). Soit \(q\) un nombre entier aléatoire. Soit \(r\) le bruit aléatoire, avec \(2*r < p/2\).
2. Chiffrement : \(c = p*q + 2r + m\)
3. Déchiffrement : \(m = c \mod p \mod 2 = (p*q + 2r + m \mod p) \mod 2 \)

Génération des clefs pour le chiffrement asymétrique

Le principe du déchiffrement asymétrique est le même que présenté précédemment. En revanche, le chiffrement diffère. Au lieu de chiffrer nos messages avec la clef privée, nous allons les chiffrer avec une clef publique.

Nous devons donc générer dans un premier temps une clef publique à partir de notre clef privée, et celle-ci doit suffisamment cacher la clef privée pour que la sécurité de notre système soit assuré, cela signifie que l'on ne doit pas être capable de retrouver la clef privée à partir de la clef publique.

Nous allons maintenant présenter le principe du cryptosystème DGHV asymétrique.

1. Taille des paramètres:

   \(lambda\) : le degré de sécurité

   \(etha = lambda * lambda\) : la taille de la clef privée p.

   \(theta\) : le nombre de \(x_i\) composant la clef publique.

   \(gamma\) avec \( (gamma > etha)\) : la taille de \(q\). \(q\) doit être plus grand que \(p\) pour cacher efficacement \(p\).

   \(rho\) : La taille du bruit.

   Pour que la sécurité du système soit optimale, \(rho = 2*lambda\). Cependant, dans notre cas nous sommes limités par la taille de \(p\) à cause de contraintes techniques, nous avons donc négligé ce paramètre pour limiter le bruit et obtenir de meilleures performances dans le cadre de notre démonstrateur.

   Pour que la sécurité du système soit prouvée, \( \lambda \lt rho \lt etha \lt \gamma \lt \theta \).* Dans notre démonstrateur, nous ne respectons la première et la dernière égalité .

2. Génération de la clef privée:

   p nombre impair aléatoire et \( p \in [2^{\eta-1}, 2^{\eta}] \).

3. Génération de la clef publique x :

   Nous souhaitons générer une clef publique à partir de notre clef privée, sans pouvoir retrouver la clef privée à travers celle-ci.

   Nous allons donc générer différents chiffrés de zéro, nommés \(x_i\), avec la méthode symétrique. Notre clef publique sera un vecteur de \(x_i\).

   $$ x_i = p*q_i+2*r_i $$

   \(x_0\) est le maximum des \(x_i\) et doit être impair.

   $$x = [x_0, x_1, x_2 ... x_\tau]$$

Chiffrement

Maintenant, nous souhaitons chiffrer notre message avec la clef publique. Il ne doit pas être possible de déchiffrer notre message avec la clef publique, nous ne pouvons donc pas simplement remplacer notre clef privée par notre nouvelle clef publique dans notre processus de chiffrement.

Nous allons donc chiffrer notre message avec un sous-ensemble aléatoire des \( x_i \) de notre clef publique. Ainsi, il ne sera pas possible de déchiffrer le message uniquement avec notre clef publique, car nous ne saurons pas quels \( x_i \) ont servi à chiffrer le message.

$$ c = (m + 2*r + \sum b_i * x_i) \mod x_0 \ avec\ b_i = \{0,1\} $$ \( (\sum b_i * x_i \mod x_0) \) est équivalent à \( (\sum b_i * x_i - z * x_0) \), avec \(z\) un entier positif. Donc \(c\) est bien de la forme \( c = m + 2*r + p*q \), donc le déchiffrement est possible. \( (\sum b_i * x_i) \) est un sous-ensemble de la clef publique x.

Déchiffrement

$$ m = (c \mod p) \mod 2 $$

Chiffrement totalement homomorphe

Dans le cas symétrique comme dans le cas asymétrque, le chiffré doit être de la forme \( c = m + 2*r + p*q \), avec p la clef privée. Nous allons montrer que ce chiffrement est totalement homomorphe, c'est-à-dire que nous pouvons effectuer des additions et des multiplications sur les données chiffrées.

Soient m1, m2, deux messages à chiffrer, $$c_1 = m_1 + 2 * r_1 + p * q_1 , c_2 = m_2 + 2 * r_2 + p * q_2 $$ Montrons que DGHV est homormophe pour l'addition: \( \ \ c_1 + c_2 = m_1 + 2 * r_1 + p * q_1 + m_2 + 2 * r_2 + p * q_2 \\ \Leftrightarrow c_1 + c_2 = m_1 + m_2 + 2 * (r_1 + r_2 ) + p * (q_1 + q_2) \\ \Leftrightarrow Dec(c_1 + c_2) = m_1 + m_2 + 2 * (r_1 + r_2 ) + p * (q_1 + q_2) \mod p \mod 2 \\ \Leftrightarrow Dec(c_1 + c_2) = m_1 + m_2 + 2 * (r_1 + r_2 ) \mod 2 \\ \Leftrightarrow Dec(c_1 + c_2) = m_1 + m_2 \\ \) Montrons que DGHV est homormophe pour la multiplication: \( \ \ c_1 * c_2 = (m_1 + 2 * r_1 + p * q_1) * (m_2 + 2 * r_2 + p * q_2) \\ \Leftrightarrow c_1 * c_2 = m_1 * m_2 + 2 * r_2 * m_1 + p * q_2 * m_1 \\ \quad + (2 * r_1) * m_2 + (2 * r_1) * 2 * r_2 + (2 * r_1) * p * q_2 \\ \quad + (p * q_1) * m_2 + (p * q_1) * 2 * r_2 + (p * q_1) * p * q_2 \\ \Leftrightarrow c_1 * c_2 = m_1 * m_2 \\ \quad + 2 * (r_2 * m_1 + r_1 * m_2 + 2 * r_1 * r_2) \\ \quad + p * ( 2 * r_1 * q_2 + 2 * q_1 * r_2 + q_2 * m_1 + q_1 * m_2 + p * q_1 * q_2) \\ \Leftrightarrow Dec(c_1 * c_2) = m_1 * m_2 \\ \quad + 2 * (r_2 * m_1 + r_1 * m_2 + 2 * r_1 * r_2) \\ \quad + p * ( 2 * r_1 * q_2 + 2 * q_1 * r_2 + q_2 * m_1 + q_1 * m_2 + p * q_1 * q_2) \mod p \mod 2 \\ \Leftrightarrow Dec(c_1 * c_2) = m_1 * m_2 \\ \quad + 2 * (r_2 * m_1 + r_1 * m_2 + 2 * r_1 * r_2) \mod 2 \\ \Leftrightarrow Dec(c_1 * c_2) = m_1 * m_2 \\ \) On remarque que pour l'addition, la taille du bruit est \(2*(r1+r2)\), alors que pour la multiplication, le bruit est de \(2 * (r_2 * m_1 + r_1 * m_2 + 2 * r_1 * r_2)\).

Opérations binaires et circuits booléens

Comme nous l'avons vu précédemment, le chiffrement DGHV permet de chiffrer uniquement des 0 et 1, c'est-à-dire un seul bit à la fois. Comment chiffrer de plus grands nombres ? Comment effectuer des opérations sur des nombres composés de plusieurs bits ?

Tout message doit d'abord être converti en écriture binaire. Lors du déchiffrement, nous ne pouvons également déchiffrer que des 0 et des 1. La structure binaire doit donc être conservée tout au long des opérations chiffrées.

Nous ne pouvons donc pas utiliser les opérations classiques de calcul. Pour multiplier deux nombres, nous ne pouvons pas utiliser l'opérateur *, et pour additionner, nous ne pouvons pas utiliser l'opérateur +. En effet, si nous additionnons 1+1 avec l'opérateur classique, nous trouvons 2, qui dans l'environnement chiffré, est équivalent à 0, or nous souhaitons obtenir [1,0], qui est l'écriture en binaire de 2.

Nous utilisons donc des opérations qui fonctionnent uniquement avec la logique du binaire, ce sont les circuits booléens. Ces circuits fonctionnent avec différents types de portes logiques, par exemple la porte ET et la porte OU-EXCLUSIF.

AND : a * b

XOR : a + b

Ces circuits représentent des programmes informatiques. Ils permettent de réaliser toute sorte d'opérations, comme par exemple l'addition.

Additionneur complet (a + b + carry)

$$ somme = a \oplus b $$ $$ retenue = ( somme \land carry ) \oplus ( a \land b) $$

Exemple:

$$ 3 = (11)_2 \\ 2 = (10)_2 $$ Première étape : demi-additionneur avec a = 1, b = 0 $$ somme = 1 \oplus 0 = 1 \\ retenue = 1 \land 0 = 0 $$ Deuxième étape : additionneur complet avec a = 1, b = 1, retenue = 0 $$ somme = 1 \oplus 1 = 0 \\ retenue = ( 0 \land 0 ) \oplus ( 1 \land 1) = 1 $$ Résultat : $$5 = (1 0 1)_2$$

Multiplication

Comme il n'est pas possible de multiplier deux nombres directement, nous allons multiplier les bits 2 à 2, puis additionner les résultats, comme lorsque l'on pose une multiplication.

Exemple: $$5 = (1 0 1)_2$$ Nous posons la multiplication, puis nous additionnons chaque ligne grâce à notre additionneur complet binaire. $$ \begin{matrix} & & & & 1 & 0 & 1 \\ & & & \times & 1 & 0 & 1 \\ \hline \\ & & & & 1 & 0 & 1 \\ & & + & 0 & 0 & 0 & 0 \\ & + & 1 & 0 & 1 & 0 & 0 \\ \hline \\ & = & 1 & 1 & 0 & 0 & 1 \\ \end{matrix} $$

Pour aller plus loin

Une implémentation du chiffrement DGHV avec SageMath.
https://github.com/coron/FHE

Si vous souhaitez découvrir comment le cryptosystème DGHV peut être transformé en chiffrement "Fully" homomorphe, vous pouvez consulter l'article suivant :
Fully Homomorphic Encryption over the Integers

L'article suivant présente des techniques de compression de la clef publique de DGHV :
Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers.