Un cryptage entièrement homomorphe peut-il être utilisé pour l'exécution de code inconsciente?

Après avoir lu cette réponse il y a quelque temps, je me suis intéressé au cryptage entièrement homomorphe. Après avoir lu l'introduction de la thèse de Gentry, j'ai commencé à me demander si son schéma de cryptage pouvait être utilisé pour l'exécution de code inconscient tel que défini dans le troisième paragraphe.

Dans un schéma de cryptage entièrement homomorphe, nous cryptons généralement certaines données, les envoyons à un environnement hostile où une certaine fonction est calculée sur les données, dont le résultat est ensuite renvoyé (crypté), sans que l'adversaire ne découvre ce que les données reçues ou le résultat de la fonction est.

Avec une exécution de code inconsciente, je veux dire que nous chiffrons un morceau de code conçu pour résoudre un problème et l'envoyons dans un environnement hostile. L'adversaire veut utiliser pour résoudre , mais nous ne voulons pas qu'il sache comment fonctionne. S'il a une entrée pour , il peut chiffrer puis utiliser (un schéma de chiffrement sur) avec , qui renvoie ensuite la sortie ( non chiffrée) (la solution de pour l'entrée$C$$P$$C$$P$$C$$I$$P$$I$$C$$I$$O$$P$$I$). Le schéma de chiffrement garantit que l'adversaire ne découvre jamais comment fonctionne le morceau de code, c'est-à-dire qu'il fonctionne comme un oracle.

La principale utilisation pratique (je peux y penser) d'un tel schéma de cryptage serait de rendre le piratage plus difficile, voire impossible.

La raison pour laquelle je pense que cela peut être possible en utilisant un schéma de cryptage entièrement homomorphe est parce que nous pouvons exécuter des circuits arbitraires sur des données cryptées, en particulier une machine de Turing universelle. Nous pourrions alors chiffrer le code comme s'il s'agissait de données, puis utiliser le circuit d'une machine Turing universelle sur ces données chiffrées pour exécuter le code.

Je pose cela comme une question ici parce que je ne sais pas si cette idée est utilisable: je n'ai jamais été beaucoup plus loin que l'introduction de la thèse de Gentry, et mes connaissances sur la cryptographie sont limitées. De plus, je ne sais pas s'il existe déjà un terme souvent utilisé pour l'exécution de code inconscient: j'ai essayé de rechercher l'idée sur Google, mais sans connaître le terme approprié, je n'ai rien trouvé.

Il y a plusieurs problèmes auxquels je peux penser qui peuvent causer des problèmes avec cette approche. Premièrement, si nous utilisons un cryptage entièrement homomorphe sans modification, le résultat du calcul ( ) serait crypté. Il serait donc inutile de l'adversaire qui souhaite utiliser votre code pour résoudre . Bien que cela puisse être utile, par exemple, pour le cloud computing, ce n'est pas ce que je veux atteindre.$O$$P$

Deuxièmement, parce que nous utilisons des circuits et non des machines de Turing arbitraires, nous ne pouvons pas utiliser des quantités de mémoire arbitraires: nous sommes limités à une quantité de mémoire prédéterminée. Cela signifie que si nous voulons exécuter un programme de cette manière, son empreinte mémoire sera toujours la même, à savoir son utilisation maximale de la mémoire.

Enfin, les constantes impliquées tueraient presque certainement toute utilisation pratique d'un tel système, mais je pense que l'idée est néanmoins intéressante.

Malheureusement, il y a un résultat qui interdit théoriquement "l'exécution de code inconsciente":

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan et Ke Yang. Sur la (Im) possibilité d' obscurcir les programmes , AVANCES EN CRYPTOLOGIE - CRYPTO 2001.

Voici les liens:

• http://www.wisdom.weizmann.ac.il/~oded/p_obfuscate.html
• http://eprint.iacr.org/2001/069
• http://www.springerlink.com/content/telalqdcx3n600uf/

Le résumé se lit comme suit:

De manière informelle, un obscurcisseur est un "compilateur" (efficace et probabiliste) qui prend en entrée un programme (ou circuit) et produit un nouveau programme qui a la même fonctionnalité que mais qui est "illisible" " en quelques sortes. Les obscurcisseurs, s'ils existent, auraient une grande variété d'applications cryptographiques et théoriques de complexité, allant de la protection logicielle au cryptage homomorphique aux analogues théoriques de la complexité du théorème de Rice. La plupart de ces applications sont basées sur une interprétation de la condition "d'illisibilité" dans l'obscurcissement comme signifiant que est une "boîte noire virtuelle", en ce sens que tout ce que l'on peut calculer efficacement avec$\cal O$$P$$\cal O(P)$$P$$\cal O(P)$$\cal O(P)$, On pourrait aussi efficacement calculer avoir accès oracle à .$P$

Dans ce travail, nous entamons une investigation théorique de l'obfuscation. Notre résultat principal est que, même sous des formalisations très faibles de l'intuition ci-dessus, l'obscurcissement est impossible. Nous le prouvons en construisant une famille de fonctions qui sont intrinsèquement inviolables dans le sens suivant: il existe un prédicat tel que (a) étant donné tout programme qui calcule une fonction dans , la valeur peut être calculé efficacement, mais (b) avec un accès Oracle à une fonction (sélectionnée au hasard) dans , aucun algorithme efficace ne peut calculer beaucoup mieux que la devinette aléatoire.$\cal F$$\pi$$f$$\cal F$$\pi(f)$$f$$\cal F$$\pi(f)$

Nous étendons notre résultat d'impossibilité de plusieurs façons, y compris même les obscurcisseurs qui (a) ne sont pas nécessairement calculables en temps polynomial, (b) ne préservent qu'environ la fonctionnalité, et (c) n'ont besoin de travailler que pour des modèles de calcul très restreints ). Nous excluons également plusieurs applications potentielles des obfuscateurs, en construisant des schémas de signature, des schémas de cryptage et des familles de fonctions pseudo-aléatoires «non brouillables».$\rm{TC}$ $0$

En effet, bien que le cryptage entièrement homomorphe soit très utile pour exécuter du code entre plusieurs parties non fiables (voir par exemple, ce document ), vous avez besoin d'une sorte d'interaction, lorsque la partie qui calcule la sortie cryptée l'envoie à la partie qui connaît la clé secrète .

La notion que vous recherchez semble étrangement proche de l'obscurcissement logiciel, pour lequel nous avons prouvé un résultat d'impossibilité mentionné ci-dessus. J'ai également écrit une fois un aperçu informel de ce document, que certaines personnes peuvent trouver utile.

Étant donné ce résultat d'impossibilité, il y a deux façons (non disjointes) que l'on peut assouplir la définition: soit en restreignant les classes de programmes / fonctions que l'on doit masquer, soit en donnant une notion plus lâche de la sécurité.

La deuxième approche est peut-être possible, et nous remarquons quelques notions faibles de type obscurcissement dans notre article. Cependant, notez que notre attaque récupère complètement le code source d'origine d'un programme, peu importe comment il est obscurci. Il faudrait donc en quelque sorte faire une définition de sécurité qui banalise pour le cas de nos contre-exemples.

La première approche a été faite pour toutes les fonctionnalités restreintes (par exemple, les fonctions ponctuelles), mais encore une fois, il faut s'assurer que la classe ne contient pas notre contre-exemple, ce qui signifie à peu près qu'elle ne devrait pas contenir de fonctions pseudo-aléatoires.