Découverte :
Vers une meilleure encryption des données génétiques

Des rotors de la machine Enigma. Crédits : pl.wikipedia.org

Des rotors de la machine Enigma.
Crédits : MisterMatt - pl.wikipedia.org (CC BY-SA 3.0)

La démocratisation du séquençage du génome humain, ouvrant les portes de la médecine personnalisée, provoque aussi beaucoup d'inquiétudes au sujet de la protection des données. La séquence unique de l'ADN d'un individu, en effet, peut indiquer entre autres les prédispositions à des maladies, la tolérance à diverses substances, les traits potentiels de la descendance, le phénotype de l'individu, son origine, etc.

Dans les "biobanques", des bases de données comprenant le code génétique de nombreux volontaires sont en cours de construction et ne feront que grandir. A titre d'exemple, le CHUV de Lausanne, précurseur européen dans le domaine, possède actuellement dans les 15'000 échantillons de sang de patients volontaires et en prévoit 50'000, majoritairement destinés au séquençage, d'ici 2017. Naturellement, les administrateurs de biobanques sont conscients que la sécurité de l'information est une question capitale dont il faut se préoccuper - techniquement et légalement - avant de commencer à séquencer en masse.

Car qu'arriverait-il si des gens mal intentionnés tombaient par un heureux hasard sur une base de données reliant l'identité d'un grand nombre de personnes à leur génome ? Sans même parler d'utilisations criminelles, on pourrait par exemple les vendre pour une fortune à des assurances-maladie qui pourraient choisir leurs clients ou adapter leurs primes. Par ailleurs, même si la séquence est anonyme, on peut imaginer dans le futur pouvoir retrouver à qui elle appartient simplement en la comparant au phénotype de la personne.

On a donc tout intérêt à protéger au mieux les données génétiques. Heureusement, du coté informatique, il y a du progrès. Même si la méthode que je vais vous présenter ici n'a rien de spécifique à la biologie, elle offre une opportunité intéressante de résoudre le problème.

L'encryption homomorphique

Le schéma de cryptage le plus répandu actuellement est le système clé privée-clé publique RSA. Très rapide, il sera pourtant caduc aussitôt qu'un véritable ordinateur quantique sera disponible. De plus, crypter la base de données c'est bien, mais à terme on veut utiliser ces données pour les analyser. Il faut donc décrypter l'information, faire le calcul (sur des machines pas forcément sûres), puis ré-encrypter le résultat, ce qui signifie qu'à un moment donné, l'information non cryptée est lisible, résultat de l'analyse compris.

Une solution à ce problème porte le nom d'"encryption homomorphique", une méthode rendue possible en théorie par un certain Craig Gentry et qui a été améliorée depuis au point d'être utilisable en pratique. Ce que cette méthode a de génial, c'est qu'on peut effectuer les calculs directement sur les données encryptées, sans jamais les décoder ! Pour schématiser, on peut encoder le chiffre 3 en "asdf" et 4 en "qwer" dans la base de données, puis sur un serveur distant calculer "asdf * qwer" qui donne "djfh76gz" en retour, et ce dernier une fois décrypté vaudra... 12. Magique.

Fonctionnement

Je base mes explication sur cet excellent billet, en essayant toutefois de rester moins technique. Pour coder un bit B \;(B=0 \;\mbox{ou}\; B=1),

  1. On génère une clé binaire K de longueur n choisie : un vecteur aléatoire rempli de 0 et 1.
  2. On cherche un vecteur réel C tel que C\cdot K \pmod{2} =_\epsilon B. Notez le \epsilon sous le signe d'égalité, on y reviendra. La multiplication est un produit scalaire.

 

C, un vecteur de longueur n aussi, est alors une version cryptée de B. On crypte un message complet en cryptant chaque bit de chaque caractère (en principe 1 caractère ASCII = 7 bits).

Pour décrypter c'est tout simple : si on connaît K et C, on n'a qu'à les multiplier (mod 2) et arrondir le résultat.

Si on y réfléchit, tel que je l'ai présenté là le système n'est pas sûr du tout : sans connaître la clé, il suffit d'encoder n fois le bit 1, résoudre le système de n équations à n inconnues qui en résulte, et on trouve la clé...

C'est là que le \epsilon entre en jeu. Si on n'a pas C\cdot K \pmod{2} = B mais presque : C\cdot K \pmod{2} - B \leq \epsilon, alors les algorithmes permettant de résoudre les systèmes linéaires étant instables numériquement, les erreurs s'accumulent rapidement et il est impossible de retrouver la clé de cette manière. On va donc volontairement ajouter un peu de "bruit" à notre vecteur C, de sorte qu'en connaissant la clé on retrouve toujours la même réponse (il suffit d'arrondir le résultat du produit scalaire), mais qu'il devienne impossible de deviner la clé.

Preuve que ça marche

Un "semi-additionneur" des bits A et B à partir d'une porte XOR et d'une porte AND. S est la somme et C la retenue ("carry"). Crédits : en.wikipedia.org

Un "semi-additionneur" des bits A et B à partir d'une porte XOR et d'une porte AND. S est la somme et C la retenue ("carry").
Crédits : Cburnett - en.wikipedia.org (CC A-SA 3.0)

Ce qu'il est important de montrer maintenant, c'est pourquoi on peut calculer directement sur les valeurs cryptées. En fait, dans un ordinateur et sur des binaires, il n'y a pas une infinité de fonctions pour lesquelles il faut vérifier cette propriété : toutes les opérations de base (shift, addition, soustraction, multiplication, division) dérivent de l'addition binaire.

Justement, "homomorphique", même s'il sonne comme un terme compliqué, signifie simplement "linéaire". Au sens mathématique, ça signifie principalement qu'appliquer la fonction à deux éléments et les additionner, c'est la même chose que les additionner d'abord et appliquer la fonction ensuite. Ici on va montrer que le schéma d'encryption est linéaire pour l'addition binaire.

Une addition de deux nombres binaires peut être réalisée à l'aide des deux opérations "par bit" XOR et AND. On peut vérifier que le XOR de deux bits s'obtient en les additionnant (mod 2), et le AND en les multipliant.

Il suffit donc de montrer que pour ces deux opérations, l'appliquer avant ou après cryptage donne un résultat identique. Voilà la démonstration pour le XOR - celle pour le AND prend un peu plus de place (voir ici, au paragraphe "Multiplication is a bit more tricky").

Prenons deux bits B et B' qu'on encode dans des vecteurs C et C'. Alors

C\cdot K = B + \epsilon \pmod{2}
C'\cdot K = B' + \epsilon' \pmod{2}

Donc

(C + C')\cdot K = (B + B') + (\epsilon + \epsilon') \pmod{2}

ou

(C + C')\cdot K =_{2\epsilon} (B + B')  \pmod{2},

ce qui montre que C + C', une fois décodé, donne le résultat de B + B'.

Autrement dit, on peut faire le calcul directement sur les valeurs cryptées et obtenir le même résultat.

Sécurité

garde_suisse

Avec la garde suisse, la sécurité est garantie.
Crédits : Harris Walker (CC Attribution 2.0 Generic)

On travaille toujours avec les données sous leur forme cryptée, soit. Mais il faut encore qu'elles ne soient pas faciles à décrypter. On a montré qu'ajouter un peu de "bruit" ne permettait pas une résolution triviale, ce qui ne signifie pas encore que le schéma est sûr.

Heureusement, on peut montrer que la résolution est un problème classé NP-difficile (NP-hard : dont la résolution est impossible en un temps polynomial). De plus, contrairement à quelques-uns de ces problèmes dont certaines configurations initiales sont simples à résoudre et d'autres très difficiles, il est difficile dans le cas moyen (average-case hard). Tout cela le rend très probablement imperméable à des adaptations connues d'algorithmes quantiques tels que celui de Shor qui menace bientôt vos clés RSA.

La cause, c'est que le problème est équivalent à une recherche du plus petit vecteur d'un réseau. Un réseau, au sens mathématique, c'est l'espace généré par tous les multiples entiers des vecteurs de base. Par exemple, l'ensemble des nombres entiers est un réseau à 1 dimension (on l'appelle Z), ainsi que l'ensemble des entiers pairs (2Z) ou des multiples de 17 (17Z). Il est plus commun de nommer 2 comme générateur de 2Z, mais on pourrait aussi choisir 9 et 29, puisque 1\cdot 29 - 3\cdot 9 = 2. A partir de 9 et 29, il est déjà plus difficile de déterminer que le plus petit vecteur est 2. Maintenant imaginez le même problème en deux dimensions (un "grillage"), où on doit en gros trouver la taille des "mailles" à partir de seulement quelques points quelconques du grillage, puis en N dimensions.

Il est aussi possible de vérifier que les données ont été traitées par la bonne fonction et que le résultat retourné est bien celui attendu (pas truqué ou intercepté en route par un tiers malveillant), ce qui est nécessaire en pratique pour avoir un protocole utilisable. Enfin, le schéma s'étend naturellement à un protocole à clé publique, comme le RSA actuel.

Limitations

Malheureusement, c'est encore assez lent. De nombreux travaux mathématiques ont déjà amélioré le temps de calcul de "âge de l'Univers" à "quelques minutes", ce qui est très bien. Aux dernières nouvelles (essais au CHUV de Lausanne), il fallait 127ms pour encrypter l'information d'une variante (SNP) du génome humain. Faites le calcul pour encrypter toutes les variantes d'un seul individu : ... environ 15 jours. Et il y en a 100'000 à traiter comme ça.

Je veux essayer !

Le principe a l'air très simple. Mais pour avoir essayé de programmer moi-même quelques fonctions qui montrent le fonctionnement, je peux vous dire que ce n'est pas si évident à faire proprement. Pour une véritable librairie, voir par exemple HElib, qui d'ailleurs affiche plus de 30'000 lignes de C++.

Voici tout de même quelques bouts de code (en Julia, mais c'est complètement arbitraire) qui auront au moins le mérite de montrer à quoi ressemblent des données une fois cryptées, et d'illustrer un peu le sujet. A vous de l'améliorer/corriger/compléter/oublier autant que vous le souhaitez.

On va encoder, au hasard, le nombre 23 (sous sa forme binaire) :

Tout d'abord, on génère une clé binaire aléatoire K :

On commence par savoir encoder 1 bit à la fois grâce à notre clé :

Ici le bit 0 :

Puis on l'utilise pour coder un message entier (ici une chaîne de caractères '0'/'1', comme "10111") :

Un simple nombre est donc transformé en une matrice réelle qui grandit avec la taille de la clé et le nombre de bits utilisés pour représenter le message - d'où la lenteur du système.

Pour décoder, on multiplie la forme encodée par la clé et on arrondit :

On voit qu'on retrouve la forme binaire de 23.

Comme on n'a pas ajouté le terme de bruit, il est facile de trouver la clé en encodant suffisamment de fois le bit 1 :

Maintenant en exercice, vous pouvez vous amuser à programmer, toujours dans l'espace des valeurs cryptées, les fonctions qui correspondent à XOR et AND, puis grâce à elles la fonction d'addition, et finalement comparez le résultat de l'addition de deux entiers, une fois décryptée, avec le résultat connu.

Conclusion

Alors l'encryption homomorphique, pour bientôt ? En pratique, pas tout de suite. Si c'est clairement le Graal des cryptologues, il faudrait encore trouver le moyen d'accélérer les calculs. En attendant, les bonnes vieilles clés RSA devraient tenir bon quelques années.

Un autre côté bien frustrant à installer des systèmes aussi sophistiqués, c'est qu'aussi sûre que soit la protection des données personnelles des patients... ceux-ci la publieront librement tout seuls de leur côté. Qu'un site internet qui vous promette de trouver votre âme soeur génétique en échange de votre consentement à partager ces infos, et voilà, les génomes se baladent sur le web.

Quelques références

Un article dans Nature qui a fait du bruit.

Le travail de thèse original de Craig Venter Gentry.

Un billet de blog fantastique (en anglais) et sa suite qui ont pas mal inspiré mon article.

Une implémentation en C pour l'encryption homomorphique : HElib.

 

Merci à Yoann M. et Sylvain P. pour leur relecture

  • À propos de
  • Bioinformaticien @ CHUV / UNIL
    Diplômé EPFL en mathématiques appliquées.
    Développement software, analyse de données génomiques.

Laisser un commentaire