¿Aplicaciones prácticas de algoritmos de cifrado homomórficos?

https://stackoverflow.com/questions/1023981

06-07-2019
|

Pregunta

Parece que estaban sucediendo cosas interesantes en criptografía: el primer cifrado homomórfico esquema apareció recientemente ( explicación , HT ). Hablando en términos generales, es una forma de codificar x en f (x) de manera que pueda calcular f (x + y) fácilmente sabiendo < code> f (x) y f (y) aunque no puede restaurar fácilmente x y y (y lo mismo para f (x * y) ).

¿Cuáles son las aplicaciones prácticas para esquemas de este tipo (una vez que se ha establecido su seguridad)? Para mí, parece que podrían hacer que los algoritmos de escritura para manipular datos privados sean mucho más fáciles.

Aquí están mis pensamientos :

votación electrónica
comprobar la integridad de los datos privados
¿hay alguna posibilidad de que ayude a la privacidad en general?

Ejemplo : Tengo cuentas con los bancos A, B, C. La entidad X quiere confirmar que tengo más de $ 1000 en total; con gusto aceptaría declaraciones de los bancos A, B, C o D, pero desafortunadamente no tengo suficiente dinero en ninguna cuenta. El Banco A cifra la información sobre mis $ 500 dólares con mi clave pública; Del mismo modo, los bancos B y C cifran la información de que tengo $ 200 y $ 300 respectivamente. Envían estos datos a X, que los agrega a un número que demuestro que, de hecho, está cifrado en $ 1000 (cifrando $ 1000 con mi clave pública y demostrando que el resultado es el mismo). He probado algo sin revelar a X cuánto dinero tengo en cada cuenta.

Otro ejemplo : Los buenos ciudadanos X_1, ..., X_n se unen para seleccionar uno de los dos candidatos, uno de los cuales es liber bebiendo café con leche A l mientras otro es un B amante de las armas portadoras de biblias (todos los nombres son ficticios). Deciden que quieren que la votación sea privada pero rápida. Envían sus votos en formato vectorial (1, vote_A, vote_B, vote_None) encriptados a la Comisión Electoral que los agrega públicamente y obtiene el resultado en el formulario (count, count_A, count_B, count_None) . Después de verificar que count = count_A + count_B + count_None , los funcionarios declaran la victoria de uno de los candidatos, después de lo cual la elección es declarada inválida por el juez por alguna razón no relacionada con la votación electrónica y peleó en el corte por los próximos 10 años, pero bueno, ese no es mi problema de todos modos.

Notas : - Creo que ese ejemplo en particular fue posible con RSA incluso antes, ya que solo requiere homomorfismo en una operación. La esperanza es que podamos tener cosas radicalmente más interesantes con más operaciones, así que, ¡inventen ejemplos!

Me gustaría especialmente ver respuestas que contengan código y / o desarrollen marcos que tengan la posibilidad de ser utilizados en la práctica, la razón es que SO no es un panel de discusión teórico de ciencias de la computación.
El algoritmo homomórfico, para repetir lo que se dijo a continuación en los comentarios, permite crear un programa que manejaría datos sin conocerlos. Desafortunadamente, los tipos de programas son algo limitados: no puede tener if (x = 0) ... porque x está encriptado y cada paso es muy lento ( hay algunas redes involucradas).

Solución

Aquí hay un tiro salvaje en la oscuridad:

Estamos pensando en proteger el texto sin formato de la persona que realiza el cálculo en él. Pero, ¿qué pasaría si el objetivo fuera proteger tanto el texto sin formato como el algoritmo?

Tomemos, por ejemplo, máquinas de resonancia magnética. La parte más cara de la máquina de resonancia magnética es el algoritmo en el que la máquina analiza los datos de resonancia magnética. Debido a esto, están fuertemente protegidos por dispositivos de hardware diseñados para destruir el programa antes de permitir que un tercero que no sea de confianza (o cualquier otra persona) lo examine.

Si un fabricante de MRI pudiera centralizar la computación de datos de MRI, sería una reducción fantástica en el riesgo de perder su algoritmo. Sin embargo, las leyes les impiden acceder a datos privados de pacientes.

¡Entonces! El cifrado homomórfico permite que esto suceda donde los datos del paciente y el algoritmo están protegidos. El cifrado homomórfico `` completo '' (es decir, inducir un homomorfismo en anillo en los datos cifrados) permite un conjunto de cálculos mucho más eficiente y robusto para operar en los datos.

Otros consejos

Como un friki de PKI, si la criptofunción homomórfica también fuera un sistema de clave asimétrica, entonces tienes algunas posibilidades realmente interesantes en el mundo de la firma. El firmante podría potencialmente firmar el mensaje y un destinatario podría retransmitir la parte del mensaje y la parte correspondiente del texto cifrado a un tercero.

En notación de funciones, eso sería:

Signos de usuario:

signo (texto sin formato, clave privada) = texto cifrado

y transmite:

enviar (texto sin formato, texto cifrado, certificado)

La aplicación obtiene segmentos:

plaintext = deseadoPlaintext + otherPlaintext

y calcula la misma conversión de texto cifrado, usando algo como:

if ciphertext :: plaintext then ?? :: deseadoPlaintext

para encontrar el texto cifrado deseado

La aplicación reenvía el contenido deseado solo al servicio externo:

enviar (texto plano deseado, texto cifrado deseado, certificado)

Y el servicio puede verificar este mensaje como si el usuario lo hubiera enviado directamente.

Esto depende del algoritmo hash utilizado para comprimir el texto sin formato que también es homomórfico. Si no, esto no va a funcionar ... o que no se aplica ningún algoritmo hash.

Esto podría ser muy útil en los casos en que desea que un servicio externo haga algo en respuesta a una solicitud de usuario firmada, pero no desea exponer todo lo que el usuario envió a ese servicio externo.

Un ejemplo sería un simple sistema de pedidos de paquetes: le envío a una aplicación web una solicitud para comprar una colección de artículos. Para estar súper seguro, firmo una orden de compra que confirma que quiero (y prometo pagar) algunos # de artículos, enviados a una ubicación específica, en una fecha específica y con cierta información de pago específica. Ahora ... la aplicación web querrá que sucedan varias cosas:

Finanzas necesita cargar mi cuenta y comenzar a recibir un pago mío
El inventario debe retirar los artículos del inventario o resolver cualquier problema de falta de inventario
El envío debe recibir del inventario y mover las cosas a mi dirección

No hay ninguna razón para que Inventario o Envío sepan cómo pago mi factura. Y puede que no haya razón para que las finanzas conozcan mi dirección de envío ... En cada caso, el Texto plano deseado y el Texto cifrado deseado cambian, dependiendo de quién sea el receptor. Esto es aún más potente en un sistema como Amazon.com libros usados ??donde la entidad que compré (Amazon) es diferente de la entidad que proporciona el artículo (el vendedor de libros usados).

Al leer el documento sobre la criptografía reticular, suena más como un sistema de clave simétrica ... que no es tan propicio para firmar mensajes.

Sobre el concepto de "nunca digas nunca", no diría que no era razonable usarlo para aplicaciones de privacidad. Pero parece claramente problemático que pueda encontrar múltiples formas de pasar del texto cifrado al texto sin formato.

La mayor aplicación de cifrado homomórfico sería en minería de datos, en mi humilde opinión. El uso de este algo podría resolver los problemas de privacidad y descubrimiento de tendencias al mismo tiempo. Por ejemplo, supongamos que su empresa aloja su información de ventas en algún proveedor de SAS. Ahora, ese proveedor podría brindarle servicios sofisticados de minería de datos, sin que tenga que revelar su información real. Básicamente, podría enviar sus datos a un proveedor de cómputo, hacer que utilice sus ciclos de CPU para calcular en su nombre y enviarle de vuelta los datos cifrados. Eso sería realmente fantástico para las empresas que buscan cambiar a sistemas basados ??en la nube, pero que tienen problemas de privacidad / IP que les impiden hacerlo.

Otra aplicación potencial, en un nivel más bajo y más personal, sería el manejo de todo tipo de datos financieros. El ejemplo extendido de ilya puede aplicarse a la presentación de declaraciones de impuestos por parte de su contador sin ver realmente su información financiera, el procesamiento de tarjetas de crédito, etc.

Sin embargo, mantendría mi entusiasmo hasta que el esquema se pruebe rigurosamente y se considere seguro. Los algos de encriptación tienen la notoria costumbre de reprobar su primera prueba, realizar una revisión y repetir el ciclo hasta que estén "certificados". por alguna autoridad gubernamental.

Puede que le interese ver la versión bastante negativa de Bruce Schneier sobre el cifrado homomórfico en:

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

No sé qué tan costoso será el cálculo de f (x) + f (x) , pero tal vez podría usarse como una forma de implementar una base de datos encriptada.

Puede almacenar 1 millón de filas de algunos datos cifrados como f (x_1) , f (x_2) , ... f (x_n) . Podrías hacer



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


 Que podría calcularse primero haciendo  SUM (f (x))  y luego descifrándolo en  SUM (x) .



	
		
	
	
			 Con esto puede ejecutar un circuito arbitrario no recursivo de profundidad acotada, por lo que, dada una longitud de clave logarítmica, puede ejecutar un algoritmo NC1 (básicamente un circuito booleano de avance). 

 Entonces, ¿cómo puedes usar esto? 

 Veamos Mapa / Reducción de un circuito y esquema de reducción sobre un conjunto de entradas. 

 Primero los datos: 

 Probablemente no queremos que el cliente tenga que encriptar todos los datos que vamos a buscar, por lo que puede proporcionar un 1 encriptado y un 0 encriptado al servidor, y dejar que use la estructura de anillo para construir enteros cifrados arbitrarios para nosotros, o simplemente podemos usarlos directamente como bits. De esa forma, el servidor puede proporcionar algunos o todos los datos que estamos buscando. Para los enteros, puede construirlos mediante aritmética campesina (doble o doble y agregar 1 para cada bit), para los bits solo proporciona el bit cifrado apropiado. 

 Podemos mezclar y combinar valores booleanos y enteros en nuestros diseños, obteniendo un if / then / else (que requiere evaluar el estilo SIMD de ambas ramas) evaluando cond * then + (1 - cond) * else usando 1 como verdadero y 0 como falso en cond, para que pueda salirse con la suya utilizando la aritmética de su anillo para hacer que sus circuitos sean más superficiales. 

 Por otro lado, es posible que también hayamos encriptado previamente algunos datos, pero dado que tendrá que seguir reciclando el mismo conjunto de claves para usarlo, esto se vuelve realmente difícil de hacer. 

 Entonces, ahora tenemos datos proporcionados por el servidor. Ahora, encripte las cosas que no desea que el servidor sepa, como qué es lo que está buscando, y pídales que también las incorporen al circuito en los puntos correctos, digamos como una entrada adicional a su función de mapa. 

 Deberíamos poder mapear un circuito arbitrario similar a NC1 sobre cada entrada para extraer un campo, multiplicar algunos valores y, en general, mapearlo en una forma que pueda reducir a bajo costo. 

 Luego reduzca esos fragmentos utilizando circuitos más pequeños, como por ejemplo para un monoide simple que tenga un resultado muy bien limitado por tamaño. (es decir, asigna para obtener un bit que indica si encontró una coincidencia, y luego reduce contando esos bits con un pequeño circuito sumador) 

 Dado que solo necesita construir el circuito lógicamente y simular su ejecución en estos bits cifrados en el anillo homomórfico, probablemente podría implementarlo relativamente rápido usando un DSL pequeño, es decir, algo como Lava en Haskell, suponiendo que tenga el cifrado homomórfico piezas rectas. 

 Además, tenga en cuenta que cada puerta es  seriamente  costosa de ejecutar. 

 Entonces, para resumir, 


 Dele al servidor un 1 y 0 encriptados y cualquier metainformación encriptada para su mapa y reduzca las funciones. 
 Para cada punto de datos, codifíquelo en su anillo homomórfico, alimente su circuito de mapa tanto la entrada como la metainformación para obtener un valor adecuado para la reducción. 
 En un árbol binario equilibrado (u otra disposición equilibrada para minimizar la altura del árbol), aplique su operación de reducción a la salida de su circuito y a cualquier metainformación de mapa cifrada. 
 Entregue el resultado al cliente para descifrarlo 
	


	
		
	
	
			 El problema con el algoritmo de cifrado homomórfico existente es que solo puede ejecutar un circuito polilogarítmico (NC1) con él, lo que descarta casi cualquier cosa interesante algorítmicamente. 

 Además, no parece que la complejidad de la codificación sea de ninguna manera menor que la complejidad de ejecutar el circuito poliligarítmico usted mismo, por lo que no ha recogido ningún trabajo libre a primera vista, a menos que haga algo particularmente complicado con 
	


	
		
	
	
			 La informática distribuida como SETI @ Home, los proyectos de plegamiento de proteínas, etc., son bastante populares porque aprovechan la donación de tiempo de CPU y electricidad de miles de usuarios. Aún más interesante sería un modelo en el que las personas puedan recibir un pago por proporcionar estos recursos para proyectos comerciales. Sin embargo, ninguna compañía responsable quiere enviar sus datos a miles de computadoras anónimas para su procesamiento. Si puede aplicar algoritmos de manera eficiente a los datos cifrados, es posible delegar el procesamiento a cualquier persona sin una relación de confianza. 
	


	
		
	
	
			 La votación electrónica es de hecho una aplicación práctica de cifrado homomórfico, es decir,  http://heliosvoting.org/  
	


	
		
	
	
			 Algunas aplicaciones bancarias pueden volverse más rápidas con la ayuda del cifrado homomórfico. 

 Pueden realizar operaciones con datos cifrados en la nube en lugar de llevarlos de la nube a la local y volver a colocarlos en la nube. Tampoco es necesario cifrar-descifrar-realizar operaciones-cifrar canalización, cifrar-realizar operaciones estaría bien.



	
		
			Licenciado bajo: CC-BY-SA con atribución
			No afiliado a StackOverflow