¿Se puede usar un cifrado totalmente homomórfico para la ejecución de código ajeno?

Después de leer esta respuesta hace un tiempo, me interesé por el cifrado totalmente homomórfico. Después de leer la introducción de la tesis de Gentry, comencé a preguntarme si su esquema de cifrado podría usarse para la ejecución de código ajeno como se define en el tercer párrafo.

En un esquema de cifrado totalmente homomórfico, generalmente ciframos algunos datos, los enviamos a un entorno hostil donde se calcula una determinada función en los datos, cuyo resultado se devuelve (encripta), sin que el adversario descubra cuáles son los datos recibidos o El resultado de la función es.

Con la ejecución de código ajeno quiero decir que ciframos un fragmento de código diseñado para resolver algún problema P y enviarlo a un entorno hostil. El adversario quiere usar C para resolver P , pero no queremos que sepa cómo funciona C. Si tiene una entrada I para P , puede encriptar I y luego usar (algún esquema de encriptación activado) C con I , que luego devuelve la salida O ( no encriptada) (la solución de P para la entrada $C$$P$$C$$P$$C$$I$$P$$I$$C$$I$$O$$P$$I$) El esquema de cifrado asegura que el adversario nunca descubra cómo funciona el código, es decir, para él funciona como un oráculo.

El uso práctico principal (se me ocurre) para tal esquema de cifrado sería hacer que la piratería sea más difícil o incluso imposible.

La razón por la que creo que esto puede ser posible utilizando un esquema de cifrado totalmente homomórfico es porque podemos ejecutar circuitos arbitrarios en datos cifrados, en particular una máquina universal de Turing. Luego podríamos encriptar el código como si fueran datos y luego usar el circuito para una máquina Turing universal en estos datos encriptados para ejecutar el código.

Planteo esto como una pregunta aquí porque no sé si esta idea es utilizable: nunca llegué mucho más allá de la introducción de la tesis de Gentry, y mi conocimiento sobre la criptografía es limitado. Además, no sé si ya hay un término de uso frecuente para la ejecución de código ajeno: intenté buscar la idea en Google pero sin saber el término apropiado no encontré nada.

Se me ocurren múltiples problemas que pueden causar problemas con este enfoque. En primer lugar, si utilizamos un cifrado totalmente homomórfico sin modificación, el resultado del cálculo ( ) se cifrará. Por tanto, sería inútil para el adversario que desea utilizar su código para resolver P . Si bien esto podría ser útil para, digamos, la computación en la nube, esto no es lo que quiero lograr.$O$$P$

En segundo lugar, debido a que estamos usando circuitos y no máquinas de Turing arbitrarias, no podemos usar cantidades arbitrarias de memoria: estamos limitados a una cantidad predeterminada de memoria. Esto significa que si queremos ejecutar un programa de esta manera, su huella de memoria siempre será la misma, es decir, su uso máximo de memoria.

Por último, las constantes involucradas seguramente matarían cualquier uso práctico de dicho sistema, pero creo que la idea es interesante.

Desafortunadamente, hay un resultado que teóricamente prohíbe la "ejecución de código ajeno":

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan y Ke Yang. Sobre la (Im) posibilidad de Ofuscar Programas , AVANCES EN CRIPTOLOGÍA - CRYPTO 2001.

Aquí están los enlaces:

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

El resumen lee:

Informalmente, un ofuscador es un "compilador" (eficiente, probabilístico) que toma como entrada un programa (o circuito) P y produce un nuevo programa O ( P ) que tiene la misma funcionalidad que P pero es "ilegible" en algún sentido . Los ofuscadores, si existen, tendrían una amplia variedad de aplicaciones criptográficas y de teoría de la complejidad, que van desde la protección de software hasta el cifrado homomórfico y los análogos teóricos de la complejidad del teorema de Rice. La mayoría de estas aplicaciones se basan en una interpretación de la condición de "ilegibilidad" en la ofuscación que significa que O ( P $\cal O$$P$$\cal O(P)$$P$$\cal O(P)$es una "caja virtual negro", en el sentido de que todo lo que uno puede calcular de manera eficiente dado , se podría también eficientemente calcular dado acceso oráculo para P .$\cal O(P)$$P$

En este trabajo, iniciamos una investigación teórica de la ofuscación. Nuestro principal resultado es que, incluso bajo formalizaciones muy débiles de la intuición anterior, la ofuscación es imposible. Probamos esto construyendo una familia de funciones que son inherentemente no ofuscables en el siguiente sentido: hay un predicado π tal que (a) dado cualquier programa que calcule una función f en F , el valor π ( f ) puede calcularse eficientemente , pero (b) dado el acceso Oracle a una función (seleccionada al azar) f en F , ningún algoritmo eficiente puede calcular π ( f $\cal F$$\pi$$f$$\cal F$$\pi(f)$$f$$\cal F$$\pi(f)$ mucho mejor que adivinar al azar.

$\rm{TC}$ $0$

De hecho, si bien el cifrado totalmente homomórfico es muy útil para ejecutar código entre múltiples partes que no son de confianza (consulte, por ejemplo, este documento ), necesita algún tipo de interacción, cuando la parte que calcula la salida cifrada lo envía a la parte que conoce la clave secreta .

La noción que está buscando suena sospechosamente cercana a la ofuscación de software, para lo cual probamos un resultado imposible mencionado anteriormente. También escribí una vez una descripción informal de ese documento, que algunas personas pueden encontrar útil.

Dado este resultado de imposibilidad, hay dos formas (no disjuntas) de relajar la definición: restringiendo las clases de programas / funciones que se requiere ofuscar, o dando una noción más flexible de seguridad.

El segundo enfoque es quizás posible, y observamos algunas nociones débiles de ofuscación en nuestro artículo. Sin embargo, tenga en cuenta que nuestro ataque recupera por completo el código fuente original de algún programa, sin importar cómo esté ofuscado. Entonces, de alguna manera, tendría que hacer una definición de seguridad que sea trivial para el caso de nuestros contraejemplos.

El primer enfoque se realizó para todas las funcionalidades restringidas (p. Ej., Funciones de punto), pero nuevamente hay que asegurarse de que la clase no contenga nuestro contraejemplo, lo que significa que no debería contener funciones pseudoaleatorias.