La démo­cra­ti­sa­tion du séquen­çage du génome humain, ouvrant les portes de la méde­cine per­son­na­li­sée, pro­voque aus­si beau­coup d'inquiétudes au sujet de la pro­tec­tion des don­nées. La séquence unique de l'ADN d'un indi­vi­du, en effet, peut indi­quer entre autres les pré­dis­po­si­tions à des mala­dies, la tolé­rance à diverses sub­stances, les traits poten­tiels de la des­cen­dance, le phé­no­type de l'individu, son ori­gine, etc.

Dans les "bio­banques", des bases de don­nées com­pre­nant le code géné­tique de nom­breux volon­taires sont en cours de construc­tion et ne feront que gran­dir. A titre d'exemple, le CHUV de Lau­sanne, pré­cur­seur euro­péen dans le domaine, pos­sède actuel­le­ment dans les 15'000 échan­tillons de sang de patients volon­taires et en pré­voit 50'000, majo­ri­tai­re­ment des­ti­nés au séquen­çage, d'ici 2017. Natu­rel­le­ment, les admi­nis­tra­teurs de bio­banques sont conscients que la sécu­ri­té de l'information est une ques­tion capi­tale dont il faut se pré­oc­cu­per — tech­ni­que­ment et léga­le­ment — avant de com­men­cer à séquen­cer en masse.

Car qu'arriverait-il si des gens mal inten­tion­nés tom­baient par un heu­reux hasard sur une base de don­nées reliant l'identité d'un grand nombre de per­sonnes à leur génome ? Sans même par­ler d'utilisations cri­mi­nelles, on pour­rait par exemple les vendre pour une for­tune à des assu­rances-mala­die qui pour­raient choi­sir leurs clients ou adap­ter leurs primes. Par ailleurs, même si la séquence est ano­nyme, on peut ima­gi­ner dans le futur pou­voir retrou­ver à qui elle appar­tient sim­ple­ment en la com­pa­rant au phé­no­type de la per­sonne.

On a donc tout inté­rêt à pro­té­ger au mieux les don­nées géné­tiques. Heu­reu­se­ment, du coté infor­ma­tique, il y a du pro­grès. Même si la méthode que je vais vous pré­sen­ter ici n'a rien de spé­ci­fique à la bio­lo­gie, elle offre une oppor­tu­ni­té inté­res­sante de résoudre le pro­blème.

L'encryption homomorphique

Le sché­ma de cryp­tage le plus répan­du actuel­le­ment est le sys­tème clé pri­vée-clé publique RSA. Très rapide, il sera pour­tant caduc aus­si­tôt qu'un véri­table ordi­na­teur quan­tique sera dis­po­nible. De plus, cryp­ter la base de don­nées c'est bien, mais à terme on veut uti­li­ser ces don­nées pour les ana­ly­ser. Il faut donc décryp­ter l'information, faire le cal­cul (sur des machines pas for­cé­ment sûres), puis ré-encryp­ter le résul­tat, ce qui signi­fie qu'à un moment don­né, l'information non cryp­tée est lisible, résul­tat de l'analyse com­pris.

Une solu­tion à ce pro­blème porte le nom d'"encryption homo­mor­phique", une méthode ren­due pos­sible en théo­rie par un cer­tain Craig Gen­try et qui a été amé­lio­rée depuis au point d'être uti­li­sable en pra­tique. Ce que cette méthode a de génial, c'est qu'on peut effec­tuer les cal­culs direc­te­ment sur les don­nées encryp­tées, sans jamais les déco­der ! Pour sché­ma­ti­ser, on peut enco­der le chiffre 3 en "asdf" et 4 en "qwer" dans la base de don­nées, puis sur un ser­veur dis­tant cal­cu­ler "asdf * qwer" qui donne "djfh76gz" en retour, et ce der­nier une fois décryp­té vau­dra… 12. Magique.

Fonctionnement

Je base mes expli­ca­tion sur cet excellent billet, en essayant tou­te­fois de res­ter moins tech­nique. Pour coder un bit ,

1. On génère une clé binaire de lon­gueur choi­sie : un vec­teur aléa­toire rem­pli de 0 et 1.
2. On cherche un vec­teur réel tel que . Notez le sous le signe d'égalité, on y revien­dra. La mul­ti­pli­ca­tion est un pro­duit sca­laire.

 

, un vec­teur de lon­gueur  aus­si, est alors une ver­sion cryp­tée de B. On crypte un mes­sage com­plet en cryp­tant chaque bit de chaque carac­tère (en prin­cipe 1 carac­tère ASCII = 7 bits).

Pour décryp­ter c'est tout simple : si on connaît et , on n'a qu'à les mul­ti­plier (mod 2) et arron­dir le résul­tat.

Si on y réflé­chit, tel que je l'ai pré­sen­té là le sys­tème n'est pas sûr du tout : sans connaître la clé, il suf­fit d'encoder fois le bit 1, résoudre le sys­tème de équa­tions à incon­nues qui en résulte, et on trouve la clé…

C'est là que le entre en jeu. Si on n'a pas mais presque : , alors les algo­rithmes per­met­tant de résoudre les sys­tèmes linéaires étant instables numé­ri­que­ment, les erreurs s'accumulent rapi­de­ment et il est impos­sible de retrou­ver la clé de cette manière. On va donc volon­tai­re­ment ajou­ter un peu de "bruit" à notre vec­teur , de sorte qu'en connais­sant la clé on retrouve tou­jours la même réponse (il suf­fit d'arrondir le résul­tat du pro­duit sca­laire), mais qu'il devienne impos­sible de devi­ner la clé.

Preuve que ça marche

Ce qu'il est impor­tant de mon­trer main­te­nant, c'est pour­quoi on peut cal­cu­ler direc­te­ment sur les valeurs cryp­tées. En fait, dans un ordi­na­teur et sur des binaires, il n'y a pas une infi­ni­té de fonc­tions pour les­quelles il faut véri­fier cette pro­prié­té : toutes les opé­ra­tions de base (shift, addi­tion, sous­trac­tion, mul­ti­pli­ca­tion, divi­sion) dérivent de l'addition binaire.

Jus­te­ment, "homo­mor­phique", même s'il sonne comme un terme com­pli­qué, signi­fie sim­ple­ment "linéaire". Au sens mathé­ma­tique, ça signi­fie prin­ci­pa­le­ment qu'appliquer la fonc­tion à deux élé­ments et les addi­tion­ner, c'est la même chose que les addi­tion­ner d'abord et appli­quer la fonc­tion ensuite. Ici on va mon­trer que le sché­ma d'encryption est linéaire pour l'addition binaire.

Une addi­tion de deux nombres binaires peut être réa­li­sée à l'aide des deux opé­ra­tions "par bit" XOR et AND. On peut véri­fier que le XOR de deux bits s'obtient en les addi­tion­nant (mod 2), et le AND en les mul­ti­pliant.

Il suf­fit donc de mon­trer que pour ces deux opé­ra­tions, l'appliquer avant ou après cryp­tage donne un résul­tat iden­tique. Voi­là la démons­tra­tion pour le XOR — celle pour le AND prend un peu plus de place (voir ici, au para­graphe "Mul­ti­pli­ca­tion is a bit more tri­cky").

Pre­nons deux bits et qu'on encode dans des vec­teurs et . Alors

Donc

ou

,

ce qui montre que , une fois déco­dé, donne le résul­tat de .

Autre­ment dit, on peut faire le cal­cul direc­te­ment sur les valeurs cryp­tées et obte­nir le même résul­tat.

Sécurité

On tra­vaille tou­jours avec les don­nées sous leur forme cryp­tée, soit. Mais il faut encore qu'elles ne soient pas faciles à décryp­ter. On a mon­tré qu'ajouter un peu de "bruit" ne per­met­tait pas une réso­lu­tion tri­viale, ce qui ne signi­fie pas encore que le sché­ma est sûr.

Heu­reu­se­ment, on peut mon­trer que la réso­lu­tion est un pro­blème clas­sé NP-dif­fi­cile (NP-hard : dont la réso­lu­tion est impos­sible en un temps poly­no­mial). De plus, contrai­re­ment à quelques-uns de ces pro­blèmes dont cer­taines confi­gu­ra­tions ini­tiales sont simples à résoudre et d'autres très dif­fi­ciles, il est dif­fi­cile dans le cas moyen (ave­rage-case hard). Tout cela le rend très pro­ba­ble­ment imper­méable à des adap­ta­tions connues d'algorithmes quan­tiques tels que celui de Shor qui menace bien­tôt vos clés RSA.

La cause, c'est que le pro­blème est équi­valent à une recherche du plus petit vec­teur d'un réseau. Un réseau, au sens mathé­ma­tique, c'est l'espace géné­ré par tous les mul­tiples entiers des vec­teurs de base. Par exemple, l'ensemble des nombres entiers est un réseau à 1 dimen­sion (on l'appelle Z), ain­si que l'ensemble des entiers pairs (2Z) ou des mul­tiples de 17 (17Z). Il est plus com­mun de nom­mer 2 comme géné­ra­teur de 2Z, mais on pour­rait aus­si choi­sir 9 et 29, puisque . A par­tir de 9 et 29, il est déjà plus dif­fi­cile de déter­mi­ner que le plus petit vec­teur est 2. Main­te­nant ima­gi­nez le même pro­blème en deux dimen­sions (un "grillage"), où on doit en gros trou­ver la taille des "mailles" à par­tir de seule­ment quelques points quel­conques du grillage, puis en N dimen­sions.

Il est aus­si pos­sible de véri­fier que les don­nées ont été trai­tées par la bonne fonc­tion et que le résul­tat retour­né est bien celui atten­du (pas tru­qué ou inter­cep­té en route par un tiers mal­veillant), ce qui est néces­saire en pra­tique pour avoir un pro­to­cole uti­li­sable. Enfin, le sché­ma s'étend natu­rel­le­ment à un pro­to­cole à clé publique, comme le RSA actuel.

Limitations

Mal­heu­reu­se­ment, c'est encore assez lent. De nom­breux tra­vaux mathé­ma­tiques ont déjà amé­lio­ré le temps de cal­cul de "âge de l'Univers" à "quelques minutes", ce qui est très bien. Aux der­nières nou­velles (essais au CHUV de Lau­sanne), il fal­lait 127ms pour encryp­ter l'information d'une variante (SNP) du génome humain. Faites le cal­cul pour encryp­ter toutes les variantes d'un seul indi­vi­du : … envi­ron 15 jours. Et il y en a 100'000 à trai­ter comme ça.

Je veux essayer !

Le prin­cipe a l'air très simple. Mais pour avoir essayé de pro­gram­mer moi-même quelques fonc­tions qui montrent le fonc­tion­ne­ment, je peux vous dire que ce n'est pas si évident à faire pro­pre­ment. Pour une véri­table librai­rie, voir par exemple HElib, qui d'ailleurs affiche plus de 30'000 lignes de C++.

Voi­ci tout de même quelques bouts de code (en Julia, mais c'est com­plè­te­ment arbi­traire) qui auront au moins le mérite de mon­trer à quoi res­semblent des don­nées une fois cryp­tées, et d'illustrer un peu le sujet. A vous de l'améliorer/corriger/compléter/oublier autant que vous le sou­hai­tez.

On va enco­der, au hasard, le nombre 23 (sous sa forme binaire) :

julia> message = bin(23)

"10111"

Tout d'abord, on génère une clé binaire aléatoire K :
function generate_key(N=20)

    key = rand(0:1, N)

    while countnz(key) == 0     # on ne veut pas une cle avec 0 partout

        key = rand(0:1, N)

    end

    return key

end
julia> K = generate_key(20)

20-element Array{Int64,1}:

 0 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 0

On commence par savoir encoder 1 bit à la fois grâce à notre clé :
function encode_1bit(bit, key)

    last1 = findin(key,1)[end]  # dernier bit non-zero

    c = Float64[]
    total = 0

    noise = 0                   # pas de bruit pour le moment !!

    for i=1:length(key)

        a = rand()*2 - 1

        if i == last1

            push!(c, key[i]-total-(1-bit)+noise)

        else

            push!(c, a)

        end

        if key[i] != 0

            total = total + a

        end

    end

    return c

end

Ici le bit 0 :
julia> encode_1bit(0, K)

20-element Array{Float64,1}:

 -0.841112   0.376839  -0.64088  -0.0220782   0.91517  -0.341114   0.365112  -0.650964  -0.528641   0.00648227   0.146742   0.435683   0.36608   0.822643  -0.361396  -0.259946  -0.694225   0.811952   0.169222   0.398963

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

    message = map(int, split(message,""))  # string -> array de 0/1

    encrypted = zeros(length(key), length(message))

    for (i,bit) in enumerate(message)

        c = encode_1bit(bit, key)

        encrypted[:,i] = c

    end

    return encrypted

end
julia> C = encode(message, K)

20x5 Array{Float64,2}:

 -0.348828   0.696748    -0.683862    0.714204    0.982248

 -0.875624   0.689617     0.925301    0.0433602   0.0421338

  0.700639  -0.592715    -0.340894   -0.452295   -0.0494057

  0.504052  -0.169575    -0.144381    0.206843    0.941349

  0.431316  -0.928031    -0.0359552   0.118174    0.142373

 -0.377039   0.481692    -0.472779    0.800013    0.529427

  0.752665  -0.202764     0.432656   -0.587943   -0.975236

 -0.623157  -0.701443     0.151177    0.071244    0.789276

  0.959001   0.00547738   0.574379    0.604067   -0.929959

 -0.838194  -0.93639     -0.131882   -0.565128   -0.839332

 -0.387583   0.189935    -0.652823    0.106463   -0.881375

  0.586078  -0.602708     0.682506   -0.711591    0.706119

  0.730341   0.148296     0.25684    -0.273813    0.860193

 -0.310579   0.93636      0.778648   -0.105344   -0.0819126

 -0.830075   0.544769     0.962231    0.271662    0.916679

 -0.9015    -0.748283    -0.0365485   0.0349416   0.326137

 -0.838072   0.976137    -0.0814949  -0.12174     0.072706

 -0.848451  -0.164284    -0.0186105   0.84279    -0.104672

 -0.913316   0.892514    -0.473587    1.21131     0.53348

 -0.547914   0.378009     0.825841   -0.920965   -0.742074

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 :
function decode_1bit(encrypted_bit, key)

    return abs(round((key' * encrypted_bit)[1] % 2))

end
function decode(encrypted, key)

    M = size(encrypted,2)

    decrypted = zeros(Int, M)

    for i in 1:M

        decrypted[i] = decode_1bit(encrypted[:,i], key)

    end

    return join(decrypted)

end
julia> decode(C,K)

"10111"

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 :
# Now suppose we don't have the key

# We generate N encryptions of 1 and solve the system

function hack()

    K = generate_key(10)

    println("Test key:", K)

    N = length(K)

    encrypt = zeros(N, N)

    for i=1:N

        encrypt[:,i] = encode_1bit(1, K)

    end

    O = ones(N)

    guess = int(encrypt' \ O)

    if guess == K

        println("Guessed the key !!! :", K)

    else:

        println("Failed to guess the key")

    end

end
julia> hack()

Test key:[1,1,1,1,0,1,0,0,0,1]
Guessed the key !!! :[1,1,1,1,0,1,0,0,0,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
      
          
        Vous avez aimé ? Dites-le nous !      
            
      
                  
                      
                  
                      
                  
                      
                  
                      
                  
                      
              
    
    
          Soumettre        
      Moyenne : 0 / 5. Nb de votes : 0    
    
      Pas encore de vote pour cet article.