Cifrado homomórfico: privacidad en la nube

[Aberroncho]

Copio aquí un par de entradas del blog Hackerdo sobre el cifrado homomórfico. Yo no había oído hablar de él y me ha parecido un tema interesante:

Fuente: Hackerdo

El cómputo en nube se ha puesto indudablemente de moda, convirtiendo al explorador web en la única herramienta necesaria para que, por medio de una conexión a Internet, se pueda utilizar una gran cantidad de software que ahora es ofrecido como servicio. Irónicamente, gran parte del software que se ofrece como servicio realiza tareas para las que existe software que puede utilizarse de manera local, con muchas más opciones y mejor rendimiento. Los únicos añadidos que distinguen al software como servicio son generalmente aquellas de compartir con multiples usuarios y la flexibilidad de hacerlo en cualquier lugar y con cualquier dispositivo.

Cuando se trata de procesar información privada tenemos el problema de que, para procesarla, el prestador de servicio la conocerá en todo momento, desde que la recibe, mientras la procesa y una vez obtenido el resultado, el cual, conocerá antes que nosotros. Tenemos entonces que depender del proovedor del servicio y sus políticas de privacidad, los proovedores, aunque sean Microsoft o Google, nunca serán realmente confiables y la historia nos lo demuestra. El problema resultante es un problema criptográfico importante que trata de resolver la siguiente pregunta: ¿Existe una forma de envíar una información cifrada, que un sistema la procese sin tener que descifrarla y nos dé un resultado cifrado con la misma llave que nuestra entrada original?

Las funciones de cifrado E(p) = c toman una entrada de texto plano p y nos devuelven un texto cifrado c, un conjunto de estas funciones, las cuales tienen la propiedad de que una operación realizada en p sea equivalente a otra operación realizada en c, son denominadas funciones de cifrado homomórfico. Los sistemas criptográficos cuya función de cifrado E, preserva la operación de suma: E(a+b) = E(a) + E(b) y la operación de multiplicación: E(a*b) = E(a) * E(b) son llamados sistemas criptográficos homomórficos completos (preservan la estructura de anillo), mientras que los que preservan solo una de las operaciones son llamados sistemas criptográficos homomórficos parciales.

El interés en los sistemas criptográficos homomórficos completos se da por el hecho de que, al existir dos operaciones que son preservadas en el sistema, es posible evaluar circuitos lógicos de manera homomórfica, es decir, con entradas y salidas cifradas, lo que permite también construir programas en los que los datos puedan ser evaluados sin necesidad de descifrarlos y cuyo resultado estará también cifrado. Con esto se resolvería el problema de confianza en los programas de terceros, pues el proovedor de servicio sería incapaz de conocer la información en ningún momento de la ejecución del programa.

La idea no es nueva, fue concebida en los años 70′s, sin embargo, la dificultad del problema no permitió que se encontraran sistemas completamente homomórficos hasta el año 2009, en el que Craig Gentry desrrolla el primero en su tesis doctoral. Posteriormente, Marten van Dijk, Craig Gentry, Shai Halevi y Vinod Vaikuntanathan presentaron un segundo sistema. Estos son los únicos sistemas existentes en la actualidad, así como refinamientos posteriores de los mismos, sin embargo su eficiencia no permite aún un uso práctico.

La investigación respecto a este tipo de sistemas criptográficos continúa y aunque abre la puerta a la seguridad en la nube, vale la pena preguntarnos ¿por qué no preferimos la seguridad del cómputo hecho en nuestra propia computadora?

Fuente: Hackerdo

Recientemente les hablamos sobre el cifrado homomórfico y los benficios que un sistema criptográfico completamente homomórfico representa para cuestiones de privacidad y principalmente para "cómputo en nube". Mencionamos que los únicos sistemas criptográficos completamente homomórficos, desarrollados por Craig Gentry y otros, son muy ineficientes y por lo tanto no son usables.

El convertir los sistemas criptográficos existentes en sistemas que puedan ser utilizados de manera eficiente es una tarea complicada que podría requerir de muchos años de investigación. Para acelerar el proceso, la Agencia de Investigación de Proyectos Avanzados de Defensa (DARPA por sus siglas en inglés) de Estados Unidos, planea catalizar la investigación mediante el financiamiento de diversos círculos de investigación, y ya ha comenzado.

El día 30 de marzo, DARPA anunció un contrato con Galois Inc. por 5 millones de dólares para trabajar en la investigación de este problema criptográfico. La agencia tiene planeado invertir 20 millones de dólares en estas investigaciones durante los próximos 5 años. El programa, que ha sido nombrado Programming Computation on Encrypted Data y abreviado PROCEED, planea que se realicen más contratos con compañías de investigación como Galois y con equipos de académicos para poder disminuir en varios órdenes de magnitud, el tiempo que toma el cómputo de los sistemas criptográficos completamente homomórficos.

Por su parte la Agencia de Investigación de Proyectos Avanzados en Inteligencia (IARPA por sus siglas en inglés) de Estados Unidos, lanzó en diciembre pasado un llamado para propuestas sobre un proyecto que se enfoca, de la misma forma que PROCEED, en encontrar una forma de cifrar datos y que estos puedan ser utilizados y manipulados sin descifrar. El proyecto de IARPA se denomina Security And Privacy Assurance Research abreviado SPAR.

La meta de ambos proyectos es lograr que el tiempo de cómputo del sistema criptográfico desarrollado por Craig Gentry sea reducido por un factor de 10 millones, o en su defecto, reducirlo a 100,000 veces el tiempo de cómputo sobre datos no cifrados. Gentry ya ha logrado realizar un avance, que aunque tampoco resulta utilizable, puede ser mas flexible y podría ser utilizado en estas investigaciones. Gentry no dió mas detalles, dado que no se ha publicado aún su investigación.

En este punto, podemos preguntarnos por qué dos agencias de los Estados Unidos están tan interesadas en este problema. Las aplicaciones se extienden mas allá de lo que discutimos en la entrada anterior sobre privacidad en la nube, pues se puede utilizar también para sistemas de votación electrónica y para sistemas con DRM perfecto.

[APOKLIPTICO]

2. Shamir threshold: Este algoritmo permitirá que N personas tengan un "pedazo" de secreto "s" y que si k personas (k menor que s) se juntan puedan reconstruir el secreto "s" de tal manera que los pedazos de secreto nunca podrán construirse a partir k-1 personas.

Por ejemplo, imaginen que una bóveda es de 10 personas, pero por alguna extraña razón quieren que si se juntan cualesquiera 3 personas de esos 10 puedan abrirla. La bóveda tiene un password y este solo se puede construir cuando se juntan 3 personas y no menos. (Este algoritmo utiliza polinomios de Lagrange)

Sacado de http://b3ck.blogspot.com/

Este es el "Shamir threshold", a pesar de que no se aplica 100% a la computación en nube, podría llegar a implementarse en una distribución que lo necesite, en definitiva, es como dice el texto que posteó Aberroncho, pero permite que el mensaje se pueda ver, sin tener necesariamente todas las "llaves". Es un algoritmo complejo, pero muy util en ciertas situaciones.

Un saludo y excelente aporte. En cuanto pueda, voy a postear algo sobre "Zero Knowledge proof", un algoritmo que permite afirmar con un 50% de probabilidad de éxito, que una persona tiene una información, sin que esa persona comparta esa información. Si se hace más de una vez, el riesgo de error se disminuye a porcentajes muy bajos (con 10 veces estamos hablando de una 0,09765625% de probabilidad de error).

Un abrazo
APOKLIPTICO