Les cryptosystème vus précédemment n'étaient pas complètement homomorphes. En effet, RSA et Paillier ne sont pas homomorphes pour toutes les opérations, ils sont respectivement homomorphes pour la multiplication uniquement ou pour l'addition uniquement. Les cryptosystèmes comme DGHV et GSW présentés tels quels ne peuvent réaliser qu'un nombre donné d'opérations. Nous allons voir qu'il existe toutefois un procédé, le bootstrap (ou réamorçage), qui permet de pallier à cette contrainte de nombre limite d'opérations.
On rappelle qu'un cryptosystème "somewhat" homomorphe a, pour toute fonction \(f\) qui peut être exprimée sous la forme d'un circuit de profondeur donnée, la relation suivante : $$f(\overline{a_1},\overline{a_2},\ldots,\overline{a_k}) = \overline{f(a_1,a_2,\ldots,a_k)}$$ (où \(\overline{m}\) représente le chiffré de \(m\)) Maintenant, imaginons qu'un cryptosytème soit fait de telle façon qu'il puisse évaluer sa propre fonction de déchiffrement, on aurait la relation suivante : $$Dec(\overline{s},\overline{c}) = \overline{Dec(s,c)}$$ Creusons encore le raisonnement, supposons que nous ayons à notre disposition une clé secrète \(s\) chiffrée à l'aide d'une clé publique \(p_2\) quelconque : \(\overline{s}\). Supposons de plus que nous ayons un chiffré \(c\) qui résulte d'un certain nombre d'opérations et qui est donc bruité. A présent, chiffrons \(c\) à l'aide de \(p_2\) : on obtient \(\overline{c}\). On peut alors exprimer la fonction de déchiffrement sous la forme d'un circuit et utiliser la relation précédente : $$c_2 = Dec(\overline{s},\overline{c}) = \overline{Dec(s,c)} = \overline{m}$$ Ainsi, à partir d'un chiffré \(c\) bruité on a obtenu un chiffré \(c_2\) bien moins bruité puisqu'il est égal à \(\overline{Dec(s,c)}\) et que \(Dec(s,c)\) est débruité. On a en quelque sorte déchiffré et rechiffré \(c\) avec \(p_2\) d'un seul coup. On a donc là une intuition de comment réduire le bruit des chiffrés, tout en les gardant chiffrés.
Dans sa thèse fondatrice de 2009, Gentry a pour la première fois mis en avant cette intuition et démontré le théorême du Bootstrap :
Suppose that \((G,E,D)\) is a CPA circular secure somewhat homomorphic encryption scheme for the family \(F\) and suppose that for every pair of ciphertexts \(c,c′\) the map \(Dec(c)-NAND-Dec(c′)\) is in \(F\). Then \((G,E,D)\) can be turned a fully homomorphic encryption scheme.
Expliquons cela :
Reprenons le Théorème du Bootstrap et déterminons concrètement comment le mettre en place : On pose la situation suivante : Alice a besoin d'effectuer d'importants calculs, elle souhaite donc envoyer ses données à Bob, qui possède la puissance de calcul nécessaire. Toutefois, elle souhaite garder ses données secrètes : Alice et Bob vont donc utiliser un cryptosystème homomorphe. Alice envoie à Bob sa clé publique \(p\), un message chiffré avec cette clé \(c\), une autre clé publique \(p_2\), ainsi que la clé secrète \(s\) qui a bien entendu été chiffrée, avec \(p_2\) : \(\overline{s}\). Bob effectue donc des opérations sur \(c\), jusqu'à ce que le bruit devienne trop important. Il décide donc de réinitialiser ce bruit à l'aide du procédé du Bootstrap :