Exécuter un algorithme sur les données à distance et s'assurer que la réponse n'a pas été falsifiée

8

Je pense à ce problème informatique / crypto / base de données depuis des années et je veux juste savoir s'il existe déjà des solutions. Pour être honnête, je ne sais même pas à quel domaine ce problème appartient exactement.

En bref: la personne A a une liste de données, une autre personne (B) a un algorithme qui attribue un score à chaque élément de cette liste, puis additionne tous ces scores pour fournir un score global pour toute la liste. Comment pouvons-nous exécuter l'algorithme sur la liste des données afin que les données soient extrêmement sécurisées (de préférence sans jamais quitter la personne A) mais pour que la personne B puisse être certaine que l'algorithme a fonctionné correctement et n'a pas été falsifié.

Voici un exemple: Anna et Bob vivent dans un grand village. Anna a une liste sur son ordinateur de toutes les choses qu'elle a faites dans le village, bonnes et mauvaises. Bob a créé un algorithme de notation très simple pour ces listes, qui s'exécute sur chaque élément de la liste et lui donne un score, puis additionne tous ces chiffres pour donner à Anna un score final. Ce score permet à Bob de savoir à quel point Anna est bénéfique pour la communauté du village et est spécifique à son opinion. (C'est plus qu'un exemple car c'est en fait le système que je veux créer)

Cependant Anna ne veut pas donner à Bob sa liste, car alors il a accès à des informations potentiellement embarrassantes (tout le monde a des squelettes dans son placard). Cependant, Bob ne fait pas confiance à Anna pour exécuter ses algorithmes elle-même, car elle peut simplement mentir et dire à Bob que le score était très élevé afin que Bob soit plus susceptible de l'aider.

Il y a quelques solutions auxquelles j'ai déjà pensé, mais toutes ont des problèmes:

A. Trouver une personne au hasard pour prendre les données et exécuter l'algorithme et renvoyer le score, mais il peut être difficile de s'assurer que cette personne au hasard ne connaît pas Anna et d'essayer de l'aider ou de faire une copie des données et d'essayer plus tard pour le retrouver et faire chanter Anna.

B. Laissez Anna exécuter l'algorithme, mais en quelque sorte coder un code de contrôle dans les scores, par exemple, au lieu de noter un événement comme 1, notez-le comme 1.0000000000797, de telle manière que Bob puisse plus tard l'utiliser comme code de contrôle pour voir si le donné le score est correct. Cependant, cette vérification pourrait également être utilisée à mauvais escient par Bob pour indiquer quelles choses spécifiques Anna a faites. Je peux également imaginer qu'un tel système serait trivial à rétroconcevoir afin qu'Anna puisse donner un faux score avec un code de contrôle correct, étant donné qu'Anna doit avoir un accès complet à l'algorithme de Bob pour l'exécuter.

C. Le village crée un serveur sécurisé pour prendre ces données et algorithmes et les exécuter ensemble. Cependant, Anna et Bob ne font pas suffisamment confiance à quiconque pour le faire et ne font pas de copie des données ni ne modifient les scores, sauf s'il existe une architecture fondamentalement sécurisée pour le faire. Je préférerais également que ce soit un système P2P.

Robin A
la source
Et si l'algorithme de notation de Bob est, par exemple, la représentation binaire de si Anna a fait ou n'a pas fait chacune des choses de la liste? (Donc 1 * <Anna a-t-elle fait la chose 1> + 2 * <Anna a-t-elle fait la chose 2> + 4 * <Anna a-t-elle fait la chose 3> ...) Ensuite, Bob aura accès aux données d'Anna uniquement en fonction de la sortie du algorithme de notation.
TLW
1
Je me demande si le cryptage homomorphe a un rôle à jouer ici? Il résout cependant le problème inverse - il permet à un autre système de calculer des données sans connaître les valeurs avec lesquelles il travaille.
Alan Wolfe
@TLW Je ne sais pas vraiment si je comprends ce que vous dites ... qui exécute l'algorithme dans cette situation et comment pouvons-nous être sûrs que la valeur finale n'est pas interceptée et falsifiée?
Robin A

Réponses:

9

Dans la communauté cryptographique, cette tâche est connue sous le nom de calcul délégué ou délégation vérifiable. Vous souhaitez laisser le serveur (le "cloud") faire le travail pour vous, mais vous voulez également que le cloud vous donne la preuve qu'il a effectivement effectué le calcul (et n'a pas simplement sorti une sortie aléatoire et s'est enfui avec votre argent).

Un pointeur, du haut de ma tête, est «Délégation de calcul: preuves interactives pour les moldus» (Goldwasser, Kalai et Rothblum, J. ACM (62), 2015). D'autres solutions existent probablement, regardez à l'intérieur.

A sonné.
la source
1

Il existe un nouveau domaine de cryptage homomorphique qui correspond généralement à vos besoins:

Le chiffrement homomorphique est une forme de chiffrement qui permet d'effectuer des calculs sur du texte chiffré, générant ainsi un résultat chiffré qui, une fois déchiffré, correspond au résultat des opérations effectuées sur le texte en clair.

L'entité de traitement ne peut rien savoir du texte crypté, il n'apparaît que sous forme de données aléatoires, il ne peut que corrompre le calcul et le client a besoin d'un moyen de détecter / se défendre contre les données / calculs corrompus. cela peut être fait avec des résumés de messages et des calculs tolérants aux pannes .

Le chiffrement homomorphique n'a été démontré que théoriquement possible un peu récemment, il est donc plus à des stades conceptuels et ne semble pas être mis en œuvre beaucoup dans la pratique jusqu'à présent, mais finalement l'idée est qu'il pourrait apparaître comme une capacité (par exemple similaire à d'autres services standard comme virtualisation) sur de grands clusters de calcul standardisés, par exemple Amazon ECC ou Google Compute Engine .

vzn
la source
Cela ne répond pas à la question posée. Le chiffrement homomorphique ne permet pas (en soi) à B de vérifier que l'algorithme a fonctionné correctement et que les données n'ont pas été falsifiées. Le cryptage homomorphique garantit uniquement la confidentialité, pas l'intégrité, mais la question concerne l'intégrité.
DW
la question porte sur «l'exécution à distance d'un algorithme sur les données», ce qui est la raison d'être du chiffrement homomorphique, et la réponse répond directement à cela, ainsi que les préoccupations supplémentaires liées à la falsification des messages et des techniques de calcul tolérantes aux pannes.
vzn