sistemas significado probabilistico homomorphic homomorficos homomorfico ejemplos determinista cifrado security encryption cryptography privacy voting

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



homomorphic encryption (10)

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

Pueden realizar operaciones con datos encriptados en la nube en lugar de llevarlo de la nube a lo local y volver a colocarlo en la nube. Además, no es necesario cifrar-descifrar-realizar operaciones-encriptar tuberías, encriptar-realizar operaciones estaría bien.

Parece que había cosas interesantes sucediendo en la criptografía: el primer esquema de cifrado homomórfico apareció recientemente ( explanation , HT ). Hablando en términos generales, es una forma de codificar x en f(x) manera que se puede calcular f(x+y) conociendo f(x) f(y) a pesar de que no se pueden restaurar fácilmente x e 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 :

  1. votación electrónica
  2. verificando la integridad de los datos privados
  3. ¿Hay alguna posibilidad de que ayude a la privacidad en general?

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

Otro ejemplo : buenos ciudadanos X_1, ..., X_n se están uniendo para seleccionar uno de los dos candidatos, uno de los cuales es un liber bebiendo latte, mientras que otro es un amante de armas Bible (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 la forma (count, count_A, count_B, count_None) . Después de verificar que count = count_A + count_B + count_None , los oficiales declaran la victoria de uno de los candidatos, luego de lo cual el juez declara la elección inválida por algún motivo no relacionado con la votación electrónica y se combate en la corte durante los próximos 10 años, pero, oye, ese no es mi problema de todos modos.

Notas : - Creo que esos ejemplos particulares ya eran posibles con RSA, ya que solo requiere homomorphicity en una operación. La esperanza es que podamos tener cosas radicalmente más interesantes con más operaciones, así que, ¡vengan con ejemplos!

  • Especialmente me gustaría ver respuestas que contengan código y / o desarrollen marcos que tengan la posibilidad de ser utilizados en la práctica, y la razón es que SO no es un foro de discusión teórico sobre informática.

  • El algoritmo homomórfico, para repetir lo que se dice a continuación en los comentarios, permite crear un programa que gestionaría los datos sin conocerlos. Desafortunadamente, los tipos de programas son algo limitados: no se puede tener if (x=0) ... porque x está encriptado, y cada paso es muy lento (hay algunos enredos involucrados).

Aquí hay un tiro salvaje en la oscuridad:

Estamos pensando en proteger el texto plano de la persona que realiza el cálculo en él. Pero, ¿y si el objetivo era proteger tanto el texto plano como el algoritmo?

Tomemos, por ejemplo, máquinas de MRI. La parte más costosa de la máquina de MRI 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 permitirse ser examinados por una parte que no es de confianza (o cualquier otra persona para el caso).

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 el acceso a datos privados de pacientes.

¡Asi que! El cifrado homomórfico permite que esto suceda cuando los datos del paciente y el algoritmo están protegidos. El cifrado "completamente" homomórfico (es decir, inducir un homomorfismo en anillo en los datos encriptados) permite un conjunto mucho más eficiente y sólido de cálculos para operar en los datos.

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

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

Señales de usuario:

signo (texto llano, clave privada) = texto cifrado

y transmite:

enviar (texto plano, texto cifrado, certificado)

La aplicación obtiene segmentos:

texto plano = deseadoPlaintexto + otroPlaintexto

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

if ciphertext :: texto simple then ?? :: desiredPlaintext

para encontrar el texto cifrado deseado

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

enviar (textoPlanete 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 simple también siendo homomórfico. Si no, esto no va a funcionar ... o no se aplica ningún algoritmo hash.

Esto podría ser muy útil en casos en los que desee 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 sistema simple de pedido de paquetes: envío una solicitud web para comprar una colección de artículos. Para estar súper seguro, firmo una orden de compra que confirma que deseo (y prometo pagar) un número de artículos, enviados a una ubicación específica, en una fecha específica y con información de pago específica. Ahora ... la aplicación web querrá que sucedan varias cosas:

  • Las finanzas deben cargar mi cuenta y comenzar a recibir un pago de mi parte
  • El inventario necesita extraer los artículos del inventario, o resolver cualquier problema de falta de stock
  • El envío necesita recibir del inventario y mover las cosas a mi dirección

No hay motivo para que Inventory o Shipping sepan cómo pago mi factura. Y puede que no haya ninguna razón para que las finanzas conozcan mi dirección de envío ... En cada caso, el TextoPágina 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 el de Amazon.com que usaba libros en los que la entidad que compré (Amazon) es diferente de la entidad que proporciona el artículo (el vendedor de libros usados).

Al leer el artículo sobre la criptografía de celosía, 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.

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

Entonces, ¿cómo puedes usar esto?

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

Primero los datos:

Probablemente no queremos que el cliente tenga que haber encriptado todos los datos que vamos a buscar, para que pueda proporcionar un 1 cifrado y un 0 encriptado al servidor, y dejar que use la estructura de anillo para construir enteros encriptados arbitrarios para nosotros, o podemos simplemente usar esos directamente como bits. De esta 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 por cada bit), para los bits solo proporciona el bit encriptado 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 * y luego + (1 - cond) * else utilizando 1 como verdadero y 0 como falso en cond, para que pueda salirse con la suya usando la aritmética incorporada de su anillo para hacer sus circuitos más superficiales.

Por otro lado, es posible que también hayamos pre-cifrado algunos datos, pero dado que tendrás que seguir reciclando el mismo conjunto de claves para usarlo, se vuelve muy difícil hacerlo bien.

Entonces, ahora tenemos datos proporcionados por el servidor. Ahora, encripte las cosas que no quiere que el servidor sepa, como qué es lo que está buscando, y pídales que lo alimenten también en el 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, asignarlo a una forma que pueda reducir de manera económica.

Luego, reduzca esos fragmentos usando circuitos más pequeños, como por ejemplo un monoide simple que tenga un resultado muy limitado. (es decir, mapea para obtener un bit que indica si encontraste una coincidencia, y luego reduces contando esos bits con un pequeño circuito sumador)

Ya que solo necesita construir el circuito lógicamente y simular su ejecución en estos bits encriptados en el anillo homomórfico, probablemente podría implementarlo relativamente rápido usando un DSL pequeño, es decir, algo así como Lava en Haskell, suponiendo que haya obtenido las piezas de encriptación homomórficas.

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

Entonces, para resumir,

  1. Proporcione al servidor un 1 y 0 cifrado y cualquier metainformación encriptada para su mapa y reduzca las funciones.
  2. 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.
  3. 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 cualquier metainfo del mapa encriptado.
  4. Entregar el resultado al cliente para su descifrado

El problema con el algoritmo de cifrado homomórfico existente es que solo se puede ejecutar un circuito poliglotámico (NC1) con él, lo que descarta casi cualquier cosa interesante de forma algorítmica.

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

El voto electrónico es de hecho una aplicación práctica del cifrado homomórfico, es decir, http://heliosvoting.org/

La aplicación más importante de cifrado homomórfico sería en la 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 sofisticados servicios de minería de datos, sin que tenga que revelar realmente 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 computar en su nombre, y devolverle los datos encriptados. Eso sería realmente fantástico para las empresas que buscan pasar a sistemas basados ​​en la nube, pero tienen preocupaciones de privacidad / IP que les impiden hacerlo.

Otra posible aplicación, 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, procesamiento de tarjetas de crédito, etc.

Sin embargo, mantendré mi emoción hasta que el plan se pruebe rigurosamente y se considere seguro. Los algos de encriptación tienen la notoria costumbre de fallar en su primera prueba, ir a una revisión y repetir el ciclo hasta que sean "certificados" por alguna autoridad gubernamental.

La informática distribuida como SETI @ Home, los proyectos de plegado 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 donde las personas pueden recibir pagos para proporcionar estos recursos para proyectos comerciales. Sin embargo, ninguna empresa responsable desea 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.

No sé cuán caro va a ser el cálculo 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 hacerlo

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

Lo cual se podría calcular haciendo primero SUM(f(x)) luego descifrándolo a SUM(x) .