Applications pratiques des algorithmes de chiffrement homomorphes?

Question

Il semble que la cryptographie présente des éléments intéressants: le premier cryptage homomorphique un schéma est récemment apparu ( explication , HT ). En gros, c’est une façon de coder x en f (x) de façon à pouvoir calculer f (x + y) en sachant < code> f (x) et f (y) même si vous ne pouvez pas restaurer facilement x et y (et même pour f (x * y) ).

Quelles sont les applications pratiques des systèmes de ce type (une fois leur sécurité établie)? Pour moi, il semble qu’ils pourraient faciliter l’écriture d’algorithmes de manipulation de données privées.

Voici mes pensées :

1. vote électronique
2. vérification de l'intégrité des données privées
3. existe-t-il une chance qui aiderait la vie privée en général?

Exemple : j'ai des comptes auprès des banques A, B et C. L'entité X souhaite confirmer que son total est supérieur à 1 000 dollars; il accepterait volontiers les déclarations des banques A, B, C ou D, mais malheureusement, je n'ai pas assez d'argent sur un seul compte. La banque A crypte les informations concernant mes 500 dollars avec ma clé publique; De même, les banques B et C chiffrent l’information selon laquelle j’ai 200 $ et 300 $ respectivement. Ils envoient ces données à X qui les ajoute à un numéro dont je démontre qu'il est en fait chiffré à 1 000 dollars (en chiffrant 1 000 dollars avec ma clé publique et en démontrant que le résultat est identique). J'ai prouvé quelque chose sans divulguer à X le montant de mon compte.

Autre exemple : les bons citoyens X_1, ..., X_n font équipe pour sélectionner l'un des deux candidats, l'un d'entre eux étant le liber buveur de lait au lait A l un autre est un amoureux des armes à feu B (tous les noms sont fictifs). Ils décident qu'ils veulent que le vote soit privé mais rapide. Ils envoient leurs votes au format vectoriel (1, vote_A, vote_B, vote_None) cryptés à la commission électorale qui les ajoute publiquement et obtient le résultat sous la forme (count, count_A, count_B, count_None) . Après avoir vérifié que count = count_A + count_B + count_None , les fonctionnaires déclarent la victoire de l'un des candidats, après quoi l'élection est déclarée invalide par le juge pour une raison non liée au vote électronique et s'est battue dans les tribunal pour les 10 prochaines années, mais, hé, ce n'est pas mon problème de toute façon.

Remarques : - Je pense que cet exemple particulier était déjà possible avec RSA, car il ne nécessite qu'une homomorphicité en une seule opération. L'espoir est que nous puissions avoir des choses radicalement plus intéressantes avec plus d'opérations - alors, donnez des exemples!

• J'aimerais particulièrement voir des réponses contenant du code et / ou des cadres de développement pouvant être utilisés, le motif étant SO n'est pas un forum de discussion informatique théorique.

• L’algorithme homomorphique, qui répète ce qui est dit ci-dessous dans les commentaires, permet de créer un programme permettant de gérer les données sans les connaître. Malheureusement, les types de programmes sont quelque peu limités: vous ne pouvez pas avoir si (x = 0) ... car x est crypté, et chaque étape est très lente ( des réseaux sont impliqués).

Answer 1

Voici un tir sauvage dans le noir:

Nous envisageons de protéger le texte en clair de la personne qui effectue le calcul à ce sujet. Mais que se passerait-il si l'objectif était de protéger à la fois le texte en clair ET l'algorithme?

Prenons, par exemple, les appareils IRM. La partie la plus chère de la machine IRM est l’algorithme dans lequel la machine analyse les données de résonance magnétique. Pour cette raison, ils sont fortement protégés par des périphériques matériels conçus pour détruire le programme avant de se laisser examiner par une partie non approuvée (ou par quiconque d'ailleurs).

Si un fabricant d’IRM pouvait centraliser l’informatique par IRM, le risque de perdre son algorithme serait formidablement réduit. Cependant, les lois les empêchent d'accéder aux données privées des patients.

Alors! Le cryptage homomorphique permet que cela se produise lorsque les données du patient et l'algorithme sont tous deux protégés. Le chiffrement "totalement" homomorphique (c'est-à-dire induisant un homomorphisme en anneau sur les données chiffrées) permet à un ensemble de calculs beaucoup plus efficace et robuste de fonctionner sur les données.

Answer 2

En tant que geek de l’ICP, si la cryptofonction homomorphique était également un système de clé asymétrique, vous disposiez de possibilités vraiment intéressantes dans le monde de la signature. Le signataire pourrait potentiellement signer le message et un destinataire pourrait retransmettre la partie du message et la partie correspondante du texte chiffré à un tiers.

En notation de fonction, ce serait:

Signes utilisateur:

signe (texte brut, clé privée) = texte crypté

et transmet:

envoyer (texte en clair, texte chiffré, certificat)

L'application obtient des segments:

texte clair = désiréPlaintext + autrePlaintext

et calcule la même conversion de texte chiffré, en utilisant quelque chose comme:

si ciphertext :: texte clair alors ?? :: désiréPlaintext

pour trouver le texte chiffré souhaité

L'application transfère le contenu souhaité uniquement vers un service externe:

envoyer (texte désiré, texte désiré, texte désiré, certificat)

Et le service peut vérifier ce message comme si l'utilisateur l'avait envoyé directement.

Cela dépend de l’algorithme de hachage utilisé pour compresser le texte en clair, qui est également homomorphe. Sinon, cela ne fonctionnera pas ... ou qu'aucun algorithme de hachage n'est appliqué.

Cela peut être très utile dans les cas où vous souhaitez qu'un service externe réponde à une demande d'utilisateur signé, mais que vous ne souhaitez pas exposer tout ce que l'utilisateur a envoyé à ce service externe.

Un exemple serait un simple système de commande de paquets - j'envoie une demande à une application Web pour qu'elle achète une collection d'articles. Pour être super sécurisé, je signe un bon de commande confirmant que je veux (et promets de payer) un certain nombre d'articles expédiés à un endroit précis, à une date précise et avec certaines informations de paiement. Maintenant .. l’application Web voudra que plusieurs choses se passent:

• Les finances doivent charger mon compte et commencer à recevoir un paiement de ma part
• L’inventaire doit extraire les articles du stock ou régler tout problème de rupture de stock
• L’expédition doit recevoir l’inventaire et transférer le contenu à mon adresse

Inventaire ou expédition n’ont aucune raison de savoir comment je règle ma facture. Et il n’ya peut-être aucune raison pour que les finances connaissent mon adresse d’expédition ... Dans chaque cas, les textes désirés en texte modifié et en texte crypté souhaité varient en fonction du destinataire. C’est encore plus puissant dans un système comme Amazon.com: livres usagés où l’entité achetée (Amazon) est différente de l’entité fournissant l’article (le libraire utilisé).

En lisant le document sur la cryptographie sur réseau, cela ressemble plus à un système à clé symétrique ... qui ne favorise pas vraiment la signature des messages.

Sur le concept de "ne jamais dire jamais", je ne dirais pas qu’il était déraisonnable de l’utiliser pour des applications de protection de la vie privée. Mais il semble clairement gênant que vous trouviez plusieurs façons de passer d'un texte crypté à un texte en clair.

Answer 3

La plus grande application du cryptage homomorphique serait dans l’exploration de données, à mon humble avis. L'utilisation de cet algorithme pourrait résoudre à la fois les problèmes de confidentialité et de découverte des tendances. Par exemple, supposons que votre entreprise héberge ses informations de vente sur certains fournisseurs SAS. Désormais, ce fournisseur peut vous fournir des services d’exploration de données sophistiqués sans que vous ayez à révéler vos véritables informations. Fondamentalement, vous pourrez envoyer vos données à un fournisseur de calcul, le faire utiliser ses cycles de calcul pour calculer en votre nom et vous renvoyer les données cryptées. Ce serait vraiment fantastique pour les entreprises qui envisagent de passer à des systèmes basés sur le cloud, mais qui ont des problèmes de confidentialité / de propriété intellectuelle les empêchant de le faire.

Une autre application potentielle, à un niveau moins élevé et plus personnel, serait le traitement de toutes sortes de données financières. L’exemple d’ilya étendu peut s’appliquer à la production de déclarations de revenus par votre comptable sans consulter vos informations financières, le traitement de vos cartes de crédit, etc.

Cependant, je maintiendrais mon enthousiasme jusqu'à ce que le projet soit testé rigoureusement et jugé sûr. Les algos de chiffrement ont l’habitude notoire d’échouer leur premier test, d’aller en révision et de répéter le cycle jusqu’à ce qu’ils soient "certifiés". par une autorité gouvernementale.

Answer 4

Vous pourriez être intéressé par la vision plutôt négative de Bruce Schneier sur le cryptage homomorphique à l'adresse:

http://www.schneier.com /blog/archives/2009/07/homomorphic_enc.html?nc=11

Answer 5

Je ne sais pas à quel point le calcul f (x) + f (x) va être coûteux, mais il pourrait peut-être être utilisé pour implémenter une base de données cryptée.

Vous pouvez stocker 1 million de lignes de données chiffrées sous la forme f (x_1) , f (x_2) , ... f (x_n) . Tu pourrais faire

SELECT SUM(x)
FROM Foo
WHERE y = 'some value'

Ce qui pourrait être calculé en commençant par SUM (f (x)) , puis en le déchiffrant en SUM (x) .

Answer 6

Grâce à cela, vous pouvez exécuter un circuit arbitraire non récursif de profondeur délimitée. Ainsi, avec une longueur de clé logarithmique, vous pouvez exécuter un algorithme NC1 (un circuit booléen à feed-forward).

Alors, comment pouvez-vous l'utiliser?

Regardons Map / Réduire un circuit et un schéma de réduction sur un ensemble d’entrées.

D'abord les données:

Nous ne voulons probablement pas que le client ait besoin de chiffrer toutes les données que nous allons rechercher. Vous pouvez donc lui fournir un 1 chiffré et un 0 chiffré, et le laisser utiliser la structure en anneau pour construire entiers chiffrés arbitraires pour nous, ou nous pouvons simplement utiliser ceux-ci directement sous forme de bits. De cette manière, le serveur peut fournir une partie ou la totalité des données que nous recherchons. Pour les entiers, il peut les construire par l'arithmétique paysanne (double ou double et ajouter 1 pour chaque bit), pour les bits, il fournit simplement le bit crypté approprié.

Nous pouvons mélanger et faire correspondre des valeurs booléennes et entières dans nos conceptions, en obtenant un if / then / else (qui nécessite d'évaluer le style SIMD des deux branches) en évaluant cond * then + (1 - cond) * else en utilisant 1 comme vrai et 0 comme faux dans les conditions, vous pouvez donc vous en tirer en utilisant l’arithmétique intégrée de votre anneau pour rendre vos circuits plus superficiels.

D’autre part, nous avons peut-être aussi pré-chiffré certaines données, mais comme vous devez continuer à recycler le même jeu de clés pour l’utiliser, cela devient vraiment délicat à obtenir.

Nous avons donc maintenant des données fournies par le serveur. Cryptez à présent les éléments que vous ne voulez pas que le serveur sache, comme ce que vous recherchez, et demandez-leur de les insérer au bon endroit dans le circuit, par exemple en tant qu’entrée supplémentaire dans votre fonction de carte.

Nous devrions pouvoir mapper un circuit arbitraire de type NC1 sur chaque entrée pour extraire un champ, multiplier certaines valeurs et le mapper de manière générale sous une forme que vous pouvez réduire à moindre coût.

Réduisez ensuite ces fragments en utilisant davantage de petits circuits, par exemple pour un monoïde simple dont le résultat est bien limité en taille. (c’est-à-dire que vous mappez pour obtenir un bit qui indique si vous avez trouvé une correspondance, puis vous réduisez en comptant ces bits avec un petit circuit additionneur)

Etant donné que vous devez seulement construire le circuit de manière logique et simuler son exécution sur ces bits chiffrés dans l'anneau homomorphique, vous pouvez probablement le mettre en œuvre relativement rapidement à l'aide d'un petit DSL, c'est-à-dire quelque chose comme Lava in Haskell, en supposant que vous disposiez du chiffrement homomorphique. pièces droites.

N'oubliez pas non plus que chaque porte est sérieusement coûteuse à exécuter.

Donc, pour résumer,

1. Attribuez au serveur les valeurs chiffrées 1 et 0 et tous les metainfo chiffrés pour votre carte et les fonctions réduites.
2. Pour chaque point de données, encodez-le dans votre anneau homomorphique, alimentez votre circuit de carte à la fois en entrée et en méta-information pour obtenir une valeur adaptée à la réduction.
3. Dans un arbre binaire équilibré (ou tout autre arrangement équilibré pour minimiser la hauteur de l’arbre), appliquez votre opération de réduction à la sortie de votre circuit et de toute métainfo de carte chiffrée.
4. Transmettez le résultat au client pour déchiffrement

Answer 7

Le problème de l’algorithme de chiffrement homomorphique existant est que vous ne pouvez exécuter qu’un circuit polylogarithmique (NC1) avec celui-ci, ce qui exclut presque tout ce qui est intéressant d’un point de vue algorithmique.

De plus, il ne semble pas que la complexité de l’encodage soit inférieure à celle d’exécuter vous-même le circuit polylogarithmique. Vous n’avez donc pas eu l’impression de travail gratuit au premier abord, à moins que vous ne fassiez quelque chose de particulièrement délicat avec il.

Answer 8

L'informatique distribuée telle que SETI @ Home, les projets de repliement de protéines, etc., sont assez populaires car ils exploitent le don de temps processeur et d'électricité de milliers d'utilisateurs. Encore plus intéressant serait un modèle où les gens peuvent être payés pour fournir ces ressources à des projets commerciaux. Cependant, aucune entreprise responsable ne souhaite envoyer ses données à des milliers d'ordinateurs anonymes à des fins de traitement. Si vous pouvez appliquer efficacement des algorithmes aux données chiffrées, il devient possible de déléguer le traitement à toute personne ne disposant pas d'une relation de confiance.

Answer 9

Le vote électronique est en effet une application pratique du cryptage homomorphique, à savoir http://heliosvoting.org/

Answer 10

Certaines applications bancaires peuvent devenir plus rapides avec l’aide du cryptage homomorphique.

Ils peuvent effectuer des opérations avec des données chiffrées sur le cloud au lieu de les passer du cloud au local et de les replacer sur le cloud. De plus, il n'est pas nécessaire de chiffrer, déchiffrer, exécuter le pipeline d'opérations, les opérations de chiffrer et d'exécuter sont acceptables.