{"id":1707,"date":"2014-07-11T15:51:38","date_gmt":"2014-07-11T13:51:38","guid":{"rendered":"http:\/\/blog.nebule.org\/?p=1707"},"modified":"2016-03-29T19:01:12","modified_gmt":"2016-03-29T17:01:12","slug":"prise-dempreinte-homomorphique","status":"publish","type":"post","link":"http:\/\/blog.nebule.org\/?p=1707","title":{"rendered":"Prise d’empreinte homomorphique"},"content":{"rendered":"

Les objets manipul\u00e9s par nebule<\/a> sont identifi\u00e9s, et donc r\u00e9f\u00e9renc\u00e9s, par leurs empreintes respectives. Ces empreintes sont cryptographiques afin de pouvoir s’assurer que c’est bien le bon objet, afin de pouvoir avoir confiance dans l’int\u00e9grit\u00e9 de son contenu. Il est possible dans un seul cas d’avoir plus d’une empreinte par objet, c’est si celles-ci sont calcul\u00e9es avec des algorithmes diff\u00e9rents (cf Collisions d’empreintes multi-algorithmique<\/a>).<\/p>\n

Cependant, si la propri\u00e9t\u00e9 cryptographique des empreintes est indispensable \u00e0 la confiance, elle entra\u00eene un manque de souplesse dans le r\u00e9f\u00e9rencement des objets. Rien dans la valeur de l’empreinte ne trahis une partie de son contenu. L’empreinte cryptographique refl\u00e8te uniquement l’int\u00e9gralit\u00e9 de l’objet. On ne peux pas s’en servir pour retrouver des objets proches dans leur contenu. Tout au plus peut-on v\u00e9rifier si deux objets sont identiques… ce qui n’a pas d’int\u00e9r\u00eat puisque dans ce cas c’est tout simplement le m\u00eame objet.<\/p>\n

Sub-division d’objet<\/h2>\n

La premi\u00e8re solution pour r\u00e9soudre ce probl\u00e8me est d’utiliser des sous-parties d’un objet comme des objets propres, et de les identifier comme tels. Le lien de type s<\/code> permet justement de li\u00e9 l’objet principal \u00e0 ses morceaux.<\/p>\n

C’est notamment ce qui est fait dans les logiciels de Paire-\u00e0-Paire (P2P – Peer to Peer). Pour qu’un fichier puisse \u00eatre t\u00e9l\u00e9charg\u00e9 depuis de multiples sources, celui-ci est pr\u00e9-d\u00e9coup\u00e9 en morceaux de taille identique pr\u00e9-d\u00e9finit. Chaque morceau \u00e0 une empreinte propre et peut \u00eatre v\u00e9rifi\u00e9 \u00e0 la r\u00e9ception. Chaque morceau est t\u00e9l\u00e9charg\u00e9 sur une et une seule source, mais plusieurs morceaux sont t\u00e9l\u00e9charg\u00e9s simultan\u00e9ment depuis plusieurs sources. On augmente ainsi le d\u00e9bit r\u00e9el de r\u00e9ception du fichier voulu m\u00eame si les sources ont individuellement un faible d\u00e9bit d’\u00e9mission. \u00c9videmment, si chaque morceau est valide, le fichier dans son ensemble ne peut qu’\u00eatre valide.<\/p>\n

Une recherche sur mot cl\u00e9 peut avantageusement tirer partie de ce syst\u00e8me puisqu’une recherche se fera uniquement sur l’empreinte du morceau correspondant \u00e0 la recherche. Toute la difficult\u00e9 est de bien choisir ces morceaux.<\/p>\n

Pour du texte, c’est facile. Pour une recherche sur des images ou des vid\u00e9os, c’est d\u00e9j\u00e0 beaucoup moins \u00e9vident. Mais quoique l’on trouve, c’est toujours une liste d’objets qui contiennent cette petite sous-partie m\u00eame si le reste n’a absolument aucun rapport.<\/p>\n

Empreinte homomorphique<\/h2>\n

Une autre solution consiste \u00e0 essayer de trouver des objets qui ont le plus de contenu en commun. Ce serait une sorte de repr\u00e9sentation miniature du contenu de l’objet. On veut quelque chose qui se rapproche plus de l’empreinte des doigts de pieds. On regarde d’abord que cela \u00e0 bien la forme d’un pied, puis on regarde plus en d\u00e9tail certaines parties morphologiques pour d\u00e9terminer si les deux pieds sont proches.<\/p>\n

On pourrait partir sur le syst\u00e8me de sous-d\u00e9coupage utilis\u00e9 par le P2P. Chaque objet est d\u00e9coup\u00e9 en petits morceaux de taille identique. Ainsi, si deux objets ont un ou des morceaux en commun, on pourra en d\u00e9duire que ceux-ci sont proches.
\nMais cette m\u00e9thode pose un probl\u00e8me. Si on prend un objet et que l’on en fait une copie avec pour seule diff\u00e9rence un caract\u00e8re suppl\u00e9mentaire dans le premier bloc de donn\u00e9es, alors tous les blocs seront vus comme diff\u00e9rents alors que les objets ont clairement des parties communes.
\nOn pourrait imaginer essayer d’optimiser la m\u00e9thode en travaillant sur des blocs de tailles variables. Mais quels crit\u00e8res adopter pour ajuster les tailles de blocs en fonction des donn\u00e9es ?<\/p>\n

Je propose une m\u00e9thode comme base de r\u00e9flexion \u00e0 d\u00e9faut pour l’instant d’\u00eatre adopt\u00e9e.
\nSi on regarde le travail d’un logiciel de compression de donn\u00e9es, on constate qu’il recherche les occurrences multiples de donn\u00e9es dans l’ensemble d’un document. Il le fait sans tenir compte de la s\u00e9mantique de ce qu’il trouve. Ainsi des mots tr\u00e8s proches s\u00e9mantiquement ne seront pas agr\u00e9g\u00e9s parce que diff\u00e9rents. Ensuite, le logiciel de compression fait un classement statistique pour d\u00e9terminer les occurrences multiples qu’il serait avantageux de r\u00e9duire. Une phrase qui appara\u00eet quelques fois permet une bonne optimisation. Un mot qui appara\u00eet plusieurs permet aussi un gain de place facile.
\nSi on reprend le m\u00eame principe d’analyse, m\u00eame sans tenir compte de la s\u00e9mantique des mots, on peut s’attendre \u00e0 ce que les plus grandes occurrences de mots ou de phrases repr\u00e9sentent le ou les sujets du document. C’est ce que fontnotamment les moteurs de recherches (Google, Bing, Yahoo…) lorsqu’ils moulinent les pages web, mais avec l’analyse s\u00e9mantique en plus.
\nL’empreinte homomorphique est constitu\u00e9e des 20 premi\u00e8res occurrences redondantes avec leur poids respectifs. L’occurrence peut \u00eatre repr\u00e9sent\u00e9e par une petite empreinte (CRC) de fa\u00e7on \u00e0 avoir une taille fixe, mettons 16 caract\u00e8res hexad\u00e9cimaux. Le poids peut \u00eatre repr\u00e9sent\u00e9 en pourcentage sur 4 caract\u00e8res hexad\u00e9cimaux (entre 0000<\/code> et ffff<\/code>).
\nVue comme \u00e7a, l’empreinte g\u00e9n\u00e9r\u00e9e n’est plus tout \u00e0 fait homomorphique et n’a pas de propri\u00e9t\u00e9s cryptographique.On obtient une empreinte homomorphique de 400 caract\u00e8res hexad\u00e9cimaux.<\/p>\n

Ainsi, plusieurs documents parlants d’un m\u00eame sujet ont de fortes chances d’avoir une m\u00eame empreinte parque bien que diff\u00e9rents ils auront les m\u00eames occurrences redondantes.<\/p>\n

Un certain nombre de donn\u00e9es annexes vont figurer dans les donn\u00e9es utilis\u00e9es pour la comparaison. Par exemple on peut retrouver les en-t\u00eates internes des documents bureautique. Il faut peut-\u00eatre pr\u00e9-filtrer les documents en fonction de leur type pur. Par exemple, un simple fichier texte et un fichier complexe de traitement de texte se verront expurg\u00e9s de tout ce qui est en-t\u00eate et donn\u00e9es internes, puis on en gardera que les caract\u00e8res imprimables convertis en minuscule, sans ponctuation…<\/p>\n

Conclusion<\/h2>\n

Une empreinte homomorphique peut \u00eatre utilis\u00e9e avantageusement en compl\u00e9ment de l’empreinte cryptographique. Elle n’a d’int\u00e9r\u00eat que pour des objets ayant suffisamment de contenu. Il faut pr\u00e9voir un seuil minimum en dessous duquel elle n’est pas calcul\u00e9e. Cette empreinte homomorphique est li\u00e9e \u00e0 l’objet par un lien de type l avec comme objet m\u00e9ta \u00ab\u00a0nebule\/objet\/homomorphe\u00a0\u00bb. Cet objet \u00e0 usage r\u00e9serv\u00e9 est ajout\u00e9 \u00e0 la documentation<\/a>.<\/p>\n

Mais dans tous les cas, en l’absence de propri\u00e9t\u00e9s cryptographique, une empreinte homomorphique ne doit pas<\/span> \u00eatre utilis\u00e9e dans les liens<\/span><\/strong>. L’usage n’est pas le m\u00eame, on fait soit de l’int\u00e9grit\u00e9<\/em>, soit du r\u00e9f\u00e9rencement<\/em>.<\/p>\n","protected":false},"excerpt":{"rendered":"

Les objets manipul\u00e9s par nebule sont identifi\u00e9s, et donc r\u00e9f\u00e9renc\u00e9s, par leurs empreintes respectives. Ces empreintes sont cryptographiques afin de pouvoir s’assurer que c’est bien le bon objet, afin de pouvoir avoir confiance dans l’int\u00e9grit\u00e9 de son contenu. Il est possible dans un seul cas d’avoir plus d’une empreinte par objet, c’est si celles-ci sont … Continuer la lecture de Prise d’empreinte homomorphique<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[72,3,4,93,96,110,24],"tags":[],"_links":{"self":[{"href":"http:\/\/blog.nebule.org\/index.php?rest_route=\/wp\/v2\/posts\/1707"}],"collection":[{"href":"http:\/\/blog.nebule.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.nebule.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.nebule.org\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.nebule.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1707"}],"version-history":[{"count":1,"href":"http:\/\/blog.nebule.org\/index.php?rest_route=\/wp\/v2\/posts\/1707\/revisions"}],"predecessor-version":[{"id":2183,"href":"http:\/\/blog.nebule.org\/index.php?rest_route=\/wp\/v2\/posts\/1707\/revisions\/2183"}],"wp:attachment":[{"href":"http:\/\/blog.nebule.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1707"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.nebule.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1707"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.nebule.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1707"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}