Posté par Rolinh .
En réponse à la dépêche Le chiffrement homomorphe.
Évalué à 10.
Dernière modification le 14 janvier 2014 à 09:58.
La dépêche n'est effectivement pas très clair à ce sujet. J'ai fait un état de l'art relativement complet (env. 15 pages + référence de publications) l'été dernier et, ayant donc un peu étudié le sujet, je vais essayer d'apporter une réponse plus claire.
Premièrement, afin d'être bien clair et au risque de répéter un peu ce qui est dit dans la dépêche, un système de chiffrement est considéré pleinement homomorphique dès lors qu'il support les opérations d'additions et de multiplication un nombre arbitraire de fois. Ce dernier point n'est pas précisé dans la dépêche mais est néanmoins important. En effet, le système de chiffrement de Boneh-Goh-Nissim par exemple support à la fois l'addition et la multiplication. Cependant, ce n'est pas un système de chiffrement homomorphique complet car seul l'addition est supportée un nombre illimité de fois. La multiplication, elle, ne peut être effectuée qu'une seule fois (éventuellement suivie d'autres additions).
Pour répondre maintenant vraiment à la question, il est nécessaire de prendre un peu de recul et de se rappeler qu’un ordinateur calcule une fonction en effectuant des opérations sur des bits 1 et 0. Il utilise l’opération AND pour effectuer une multiplication et l’opération XOR pour une addition :
L’algèbre de Boole se base sur trois fonctions logiques fondamentales : AND, OR et NOT. À partir de ces trois fonctions de base, n’importe quelle fonction peut être dérivée. Ainsi, XOR étant la combinaison de AND et OR, il est possible de créer n’importe quelle fonction à partir de XOR et AND.
Par exemple, une fonction permettant de rechercher une chaîne dans un texte est, d’une manière simplifiée, un XOR. En considérant la représentation binaire de la chaîne, il suffit d’effectuer un XOR avec le texte entier et lorsque le résultat vaut 0, cela veut dire que la chaîne a été trouvée. Si, à présent, à la place des bits b1 et b2 , leur version chiffrée x1 et x2 est utilisée et qu’il existe deux fonctions Eadd telle que Eadd(x1, x2 ) = x1 ×ばつ x2 et Emult telle que Emult(x1, x2) = x1 + x2 , alors il est possible d’effectuer des AND et XOR et donc d’appliquer n’importe quelle fonction arbitraire sur des bits chiffrés. La fonction de recherche évoquée tout à l’heure peut ainsi être effectuée sur avec une chaîne et un texte chiffrés.
Les plaintext et les ciphertext possèdent une structure en anneau. Au sens mathématique, un anneau est ensemble A muni de deux opérations nommées addition et multiplication tel que A muni de l’addition est un groupe commutatif, que la multiplication est associative et distributive par rapport à l’addition et que l’addition possède un élément neutre. Étant donné que l’addition et la multiplication sont complètes au sens de Turing sur un anneau, il est alors possible de créer un circuit logique de taille polynomiale constitué de portes effectuant l’addition et la multiplication. Dès lors, il suffit de pouvoir implémenter les deux fonctions Eadd et Emult pour avoir un système de chiffrement homomorphique complet.
Formellement, un système homomorphique complet est donc défini ainsi:
Soit Sk en ensemble de ciphertext valides pour n’importe quel k.
Pour c1 , c2 ∈ Sk, cADD = ADD(c1 , c2 ), cM ULT = M U LT (c1 , c2 ).
Alors:
DECk (cADD ) = DECk (c1) + DECk(c2 )
et
DECk(cM U LT ) = DECk (c1) ×ばつ DECk (c2 )
J'espère que cela apporte un début de réponse. Je tâcherais de publier mon document sur le chiffrement homomorphique un de ces quatre mais je me rappelle qu'il avait besoin d'une bonne relecture afin de corriger des erreurs de français et autre.
[^] # Re: J'ai pas tout compris...
Posté par Rolinh . En réponse à la dépêche Le chiffrement homomorphe. Évalué à 10. Dernière modification le 14 janvier 2014 à 09:58.
La dépêche n'est effectivement pas très clair à ce sujet. J'ai fait un état de l'art relativement complet (env. 15 pages + référence de publications) l'été dernier et, ayant donc un peu étudié le sujet, je vais essayer d'apporter une réponse plus claire.
Premièrement, afin d'être bien clair et au risque de répéter un peu ce qui est dit dans la dépêche, un système de chiffrement est considéré pleinement homomorphique dès lors qu'il support les opérations d'additions et de multiplication un nombre arbitraire de fois. Ce dernier point n'est pas précisé dans la dépêche mais est néanmoins important. En effet, le système de chiffrement de Boneh-Goh-Nissim par exemple support à la fois l'addition et la multiplication. Cependant, ce n'est pas un système de chiffrement homomorphique complet car seul l'addition est supportée un nombre illimité de fois. La multiplication, elle, ne peut être effectuée qu'une seule fois (éventuellement suivie d'autres additions).
Pour répondre maintenant vraiment à la question, il est nécessaire de prendre un peu de recul et de se rappeler qu’un ordinateur calcule une fonction en effectuant des opérations sur des bits 1 et 0. Il utilise l’opération AND pour effectuer une multiplication et l’opération XOR pour une addition :
b1 AND b2 = 1 si b1 = b2 = 1, sinon 0 ⇒ b1 ×ばつ b2
b1 XOR b2 = 0 si b1 = b2 , sinon 1 ⇒ b1 + b2 (modulo 2)
L’algèbre de Boole se base sur trois fonctions logiques fondamentales : AND, OR et NOT. À partir de ces trois fonctions de base, n’importe quelle fonction peut être dérivée. Ainsi, XOR étant la combinaison de AND et OR, il est possible de créer n’importe quelle fonction à partir de XOR et AND.
Par exemple, une fonction permettant de rechercher une chaîne dans un texte est, d’une manière simplifiée, un XOR. En considérant la représentation binaire de la chaîne, il suffit d’effectuer un XOR avec le texte entier et lorsque le résultat vaut 0, cela veut dire que la chaîne a été trouvée. Si, à présent, à la place des bits b1 et b2 , leur version chiffrée x1 et x2 est utilisée et qu’il existe deux fonctions Eadd telle que Eadd(x1, x2 ) = x1 ×ばつ x2 et Emult telle que Emult(x1, x2) = x1 + x2 , alors il est possible d’effectuer des AND et XOR et donc d’appliquer n’importe quelle fonction arbitraire sur des bits chiffrés. La fonction de recherche évoquée tout à l’heure peut ainsi être effectuée sur avec une chaîne et un texte chiffrés.
Les plaintext et les ciphertext possèdent une structure en anneau. Au sens mathématique, un anneau est ensemble A muni de deux opérations nommées addition et multiplication tel que A muni de l’addition est un groupe commutatif, que la multiplication est associative et distributive par rapport à l’addition et que l’addition possède un élément neutre. Étant donné que l’addition et la multiplication sont complètes au sens de Turing sur un anneau, il est alors possible de créer un circuit logique de taille polynomiale constitué de portes effectuant l’addition et la multiplication. Dès lors, il suffit de pouvoir implémenter les deux fonctions Eadd et Emult pour avoir un système de chiffrement homomorphique complet.
Formellement, un système homomorphique complet est donc défini ainsi:
Soit Sk en ensemble de ciphertext valides pour n’importe quel k.
Pour c1 , c2 ∈ Sk, cADD = ADD(c1 , c2 ), cM ULT = M U LT (c1 , c2 ).
Alors:
DECk (cADD ) = DECk (c1) + DECk(c2 )
et
DECk(cM U LT ) = DECk (c1) ×ばつ DECk (c2 )
J'espère que cela apporte un début de réponse. Je tâcherais de publier mon document sur le chiffrement homomorphique un de ces quatre mais je me rappelle qu'il avait besoin d'une bonne relecture afin de corriger des erreurs de français et autre.