Cifrado homomórfico

El cifrado homomórfico es un tipo de cifrado en el que una operación algebraica concreta, sobre un texto original (en inglés: plaintext o cleartext), equivale a otra operación algebraica (no necesariamente la misma) sobre el mismo texto cifrado.​ De esta manera, si realizamos operaciones sobre datos cifrados y posteriormente desciframos el resultado, obtendremos lo mismo que si realizamos esas mismas operaciones (o equivalentes) sobre los datos originales.​ De forma que si: ${\mathit {Cif}}$ representa la función de cifrado y ${\mathit {Des}}$ la función de descifrado, en el cifrado homomórfico se cumple la igualdad:

${\mathit {Des}}{\big (}o_{p}^{'}\left({\mathit {\Psi }}_{1},...,{\mathit {\Psi }}_{n}\right){\big )}=o_{p}\left(r_{1},...,r_{n}\right)$

donde ${\mathit {\Psi }}_{i}={\mathit {Cif}}\left(r_{i}\right)$, $o_{p}$ representa una operación algebraica sobre el dato o texto original y $o_{p}^{'}$ representa la operación equivalente en el texto cifrado. Es importante recalcar que $o_{p}^{'}$ puede ser igual o diferente que $o_{p}$.

La siguiente igualdad es un ejemplo de cifrado homomórfico:

${\mathcal {C}}_{r1}(t_{1})\odot {\mathcal {C}}_{r2}(t_{2})={\mathcal {C}}_{r}(t_{1}\oplus t_{2})$

donde ${\mathcal {C}}_{r}(t)$ representa la función de cifrado del texto $t$ usando el valor aleatorio $r$, el operador $\odot$ representa la operación binaria producto y el operador $\oplus$ la operación binaria suma.​ De esta manera, por medio del cifrado homomórfico, el resultado del producto sobre dos textos cifrados es idéntico a cifrar el resultado de la operación equivalente (en este caso la suma) sobre los mismos textos sin cifrar.

Esta característica es deseable en las arquitecturas de sistemas de comunicación actuales. El cifrado homomórfico permitiría encadenar entre sí diferentes servicios sin necesidad de exponer los datos de cada uno de los servicios, por ejemplo: una cadena de servicios independientes de diversas empresas podrían: 1) calcular la tasa impositiva, 2) el tipo de cambio y 3) el envío de una operación comercial, sin exponer los datos de cada uno de los servicios involucrados en la operación completa.​ Los sistemas de cifrado homomórfico son criptográficamente maleables por diseño. La propiedad homomórfica de algunos sistemas criptográficos o criptosistemas (en inglés: cryptosystems) puede utilizarse para desarrollar sistemas de votación seguros,​ funciones resumen (en inglés: hash functions) anti-colisión, sistemas de recuperación de información privada, y permitir el uso generalizado de la computación en nube (en inglés: cloud computing), garantizando la confidencialidad de los datos procesados.

Hay diversos sistemas criptográficos eficientes que son parcialmente homomórficos, y gran número de sistemas completamente homomórficos que son menos eficientes. Aunque un sistema criptográfico que es involuntariamente homomórfico puede ser objeto de ataques aprovechando debilidades en sus principios básicos, si se diseña meticulosamente, puede utilizarse para realizar operaciones de cómputo de forma segura.

Sistemas criptográficos parcialmente homomórficos

En los siguientes ejemplos, la notación ${\mathcal {E}}(x)$ se usa para representar el cifrado del mensaje $x$.

RSA sin relleno

En el sistema criptográfico RSA, dada cierta clave pública definida como el módulo $m$ y el exponente $e$, entonces el cifrado de un mensaje $x$ se expresa como: ${\mathcal {E}}(x)=x^{e}\;{\bmod {\;}}m$. La propiedad homomórfica viene dada por la expresión:

${\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})=x_{1}^{e}\cdot x_{2}^{e}\;{\bmod {\;}}m=(x_{1}\cdot x_{2})^{e}\;{\bmod {\;}}m={\mathcal {E}}(x_{1}\cdot x_{2})$

ElGamal

En el sistema criptográfico ElGamal, dado un grupo $G$ con clave pública $(G,q,g,h)$, donde $h=g^{x}$, y $x$ representa la clave privada, el cifrado de un mensaje $m$ se expresa como: ${\mathcal {E}}(m)=(g^{r},m\cdot h^{r})$, para un $r\in \{0,\ldots ,q-1\}$ aleatorio. La propiedad homomórfica viene dada por la expresión:

${\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})=(g^{r_{1}},x_{1}\cdot h^{r_{1}})(g^{r_{2}},x_{2}\cdot h^{r_{2}})=(g^{r_{1}+r_{2}},(x_{1}\cdot x_{2})h^{r_{1}+r_{2}})={\mathcal {E}}(x_{1}\cdot x_{2})$

Goldwasser-Micali

En el sistema criptográfico Goldwasser-Micali, dada cierta clave pública definida como el módulo $m$ y la cuadrática no residual $x$, entonces el cifrado de un bit $b$ se expresa como: ${\mathcal {E}}(b)=x^{b}r^{2}\;{\bmod {\;}}m$, para un $r\in \{0,\ldots ,m-1\}$ aleatorio. La propiedad homomórfica viene dada por la expresión:

${\mathcal {E}}(b_{1})\cdot {\mathcal {E}}(b_{2})=x^{b_{1}}r_{1}^{2}x^{b_{2}}r_{2}^{2}=x^{b_{1}+b_{2}}(r_{1}r_{2})^{2}={\mathcal {E}}(b_{1}\oplus b_{2})$

donde $\oplus$ denota la suma de módulo 2 o suma binaria (XOR).

Benaloh

En el sistema criptográfico Benaloh, dada cierta clave pública definida como el módulo $m$ y la base $g$, con un tamaño de bloque $c$, entonces el cifrado del mensaje $x$ se expresa como: ${\mathcal {E}}(x)=g^{x}r^{c}\;{\bmod {\;}}m$, para un $r\in \{0,\ldots ,m-1\}$ aleatorio. La propiedad homomórfica viene dada por la expresión:

${\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})=(g^{x_{1}}r_{1}^{c})(g^{x_{2}}r_{2}^{c})=g^{x_{1}+x_{2}}(r_{1}r_{2})^{c}={\mathcal {E}}(x_{1}+x_{2}\;{\bmod {\;}}c)$

Paillier

En el sistema criptográfico Paillier, dada cierta clave pública definida como el módulo $m$ y la base $g$, entonces el cifrado de un mensaje $x$ se expresa como: ${\mathcal {E}}(x)=g^{x}r^{m}\;{\bmod {\;}}m^{2}$, para un $r\in \{0,\ldots ,m-1\}$ aleatorio. La propiedad homomórfica viene dada por la expresión:

${\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})=(g^{x_{1}}r_{1}^{m})(g^{x_{2}}r_{2}^{m})=g^{x_{1}+x_{2}}(r_{1}r_{2})^{m}={\mathcal {E}}(x_{1}+x_{2}\;{\bmod {\;}}m)$

Otros sistemas criptográficos parcialmente homomórficos

• Criptosistema Okamoto–Uchiyama
• Criptosistema Naccache–Stern
• Criptosistema Damgård–Jurik
• Criptosistema Boneh–Goh–Nissim

Cifrado totalmente homomórfico

Cada uno de los ejemplos mencionados anteriormente permite el cálculo homomórfico de una sola operación (ya sea producto o suma) en textos origen (plaintexts). Un sistema de cifrado homomórfico que soporta tanto la suma como el producto (preservando así la estructura en anillo de los textos origen) se conoce como cifrado totalmente homomórfico (en inglés: fully homomorphic encryption, FHE). Utilizando este esquema, cualquier circuito puede ser homomorficamente evaluado, lo que permite la construcción de programas que pueden procesar datos cifrados de entrada y producir datos cifrados de salida. Puesto que estos programas nunca descifran los datos de entrada, pueden ejecutarse en equipos no confiables sin necesidad de revelar los datos de entrada y su estado interno. La existencia de un sistema criptográfico eficiente y completamente homomórfico tendría grandes implicaciones prácticas en la externalización de sistemas de cómputo privados, por ejemplo, en el contesto de la computación en nube (cloud computing).​

La cualidad homomórfica, de un sistema completamente homomórfico, también puede ser descrita por la teoría de categorías. De esta manera, si $C$ es la categoría de objetos que representa ciertos números enteros (es decir, flujos finitos de datos) cuyos morfismos son funciones computables, entonces (idealmente) en un sistema completamente homomórfico, la función de cifrado, equivale a un functor desde $C$ hacia sí mismo.^{[cita requerida]}

La utilidad del cifrado completamente homomórfico está manifiestamente reconocida desde hace tiempo. El problema de implementar tal sistema fue propuesto por primera vez durante el año en que se estaba desarrollando el algoritmo RSA.​ La solución fue más difícil de alcanzar, durante más de 30 años se estuvo trabajando en este problema, y no estaba claro si el cifrado completamente homomórfico llegaría a ser posible. Durante este periodo de tiempo, la mejor aproximación fue el sistema criptográfico Boneh-Goh-Nissim, que permitía la evaluación de un número ilimitado de operaciones de suma, pero a lo sumo una multiplicación.

En el año 2009, el estudiante de la Universidad de Stanford Craig Gentry, mientras trabajaba en su tesis doctoral​ y hacía prácticas en el centro de investigación de IBM, propone el primer sistema de cifrado completamente homomórfico capaz de evaluar circuitos​ de profundidad arbitraria, usando criptografía basada en retículos (en inglés: lattice-based cryptography),​ según anunciaba la compañía IBM en junio de 2009.​​

El trabajo de Craig parte de un sistema de cifrado genérico, parcialmente homomórfico, y que se limita a evaluar polinomios de bajo grado sobre datos cifrados, usando retículos ideales. Esta limitación se debe a que cada texto cifrado contiene ruido, dicho ruido aumenta a medida que se suman y multiplican textos cifrados, hasta que finalmente el texto cifrado resultante se hace indescifrable. A continuación, el trabajo de Craig, muestra como modificar ligeramente el sistema de cifrado para que sea capaz de evaluar su propio circuito de descifrado, y establece que dicho sistema modificado se puede transformar en un sistema de cifrado genérico completamente homomórfico (dicho sistema se conoce en inglés como bootstrappable encryption scheme). Por último, demuestra que cualquier sistema de cifrado homomórfico bootstrappable puede convertirse en un sistema de cifrado completamente homomórfico, a través de un proceso recursivo autocontenido. En el caso particular de los sistemas homomórficos de Craig, basados en retículos ideales, el procedimiento de bootstrapping regenera de manera efectiva el texto cifrado, reduciendo el ruido asociado, de modo que los textos cifrados pueden sumarse y multiplicarse sin riesgo de que el texto cifrado resultante sea indescifrable. Craig fundamenta la seguridad de su sistema en la supuesta dificultad de dos problemas: ciertos problemas del peor caso en retículos ideales, y la escasa influencia del problema de la suma de subconjuntos.

En cuando al rendimiento, los textos cifrados con el sistema de Craig conservan su tamaño, dado que éste no depende en absoluto de la complejidad de la función que se evalúa sobre el texto cifrado, y el tiempo de cálculo depende linealmente del número de operaciones ejecutadas. Sin embargo, en gran cantidad de aplicaciones, el sistema no tiene utilidad debido a que el tamaño del texto cifrado, y el tiempo requerido para el cálculo, aumentan bruscamente si aumenta el nivel de seguridad. Para obtener un nivel de seguridad $2^{k}$ contra $k$ ataques conocidos, el tiempo de cálculo y el tamaño del texto cifrado son polinomios de alto grado en $k$. Stehle y Steinfeld consiguen reducir sustancialmente la dependencia de $k$, por medio de mejoras que permiten que el cálculo sea casi $k^{3,5}$ por cada operación booleana de la función que se está evaluando.​

Además del trabajo expuesto en su tesis doctoral, Craig Gentry publicó en la edición de marzo de 2010 de la revista Comunicaciones de la ACM (en inglés: Communications of the ACM), un análisis sobre un sistema de cifrado propuesto por Marten Van Dijk.​ En el trabajo de Van Dijk, publicado en 2009 junto con Craig Gentry, Shai Halevi y Vinod Vaikuntanathan,​ se propone otro sistema de cifrado completamente homomórfico basado en el de Craig, pero que no requiere el uso de retículos ideales. En lugar de partir del sistema de cifrado parcialmente homomórfico de Craig, basado en retículos ideales, se parte de un sistema más simple basado en números enteros. El sistema es conceptualmente más simple que el de Craig, pero tiene propiedades similares en cuanto a homomorfísmo y eficiencia. El componente parcialmente homomórfico al que se hace referencia en el trabajo de Van Dijk es similar otro sistema de cifrado propuesto por Levieil y Naccache in 2008, y también a un sistema propuesto por Bram Cohen en 1998. Sin embargo, el método de Cohen ni tan siquiera permite la operación de suma de manera homomórfica. El sistema Levieil-Naccache permite la operación de suma de manera homomórfica, y puede ser modificado para soportar un número limitado de multiplicaciones.​

Implementaciones

En 2009, Riggio y Sicari dieron a conocer una aplicación práctica de cifrado homomórfico para una red de comunicaciones inalámbrica de arquitectura híbrida: en este caso de sensores (en inglés: wireless sensor network, WSN) y en malla (en inglés: wireless mesh network, WMN). El sistema permite múltiples envíos de datos entre nodos, de manera transparente, que son capaces de realizar análisis estadísticos de diferentes parámetros (temperatura, humedad, etc) procedentes de una WSN y garantizando al mismo tiempo tanto el cifrado como la autenticación entre nodos.​

En 2010, Nigel P. Smart y Frederik Vercauteren presentaron una versión refinada del sistema de Craig, que proporcionaba claves y tamaños de textos cifrados más reducidos, pero que no era totalmente práctico.​ En la última sesión de Eurocrypt 2010, Craig Gentry y Shai Halevi presentaron una implementación funcional de un sistema de cifrado completamente homomórfico (es decir, el procedimiento completo de bootstrapping) junto con las estadísticas de rendimiento​

En 2012, Coron, Naccache y Tibouchi propusieron una técnica que permitía reducir el tamaño de la clave publica del sistema de Van Dijk a 600 KB.​ En abril de 2013, IBM liberó en GitHub la primera versión de HElib,​ una librería que implementa el sistema de cifrado homomórfico de Brakerski, Gentry y Vaikuntanathan (BGV),​ escrita en lenguaje C++ y bajo licencia GNU GPL.​

Hacia aplicaciones de Internet totalmente seguras

Los principios en los que se fundamenta el cifrado homomórfico pueden servir como punto de partida para mejorar los sistemas de seguridad (o aplicaciones) que almacenan y manipulan datos de carácter personal o sensibles. Esta garantía de protección deriva de la capacidad, que tiene el sistema de cifrado homomórfico, de realizar operaciones aritméticas sobre datos cifrados. Basándose en un sistema de cifrado completamente homomórfico, Youssef Gahi desarrolló el esquema básico, y el diseño de unos circuitos genéricos, fácilmente adaptables, que pueden preservar de manera efectiva la privacidad y confidencialidad entre diversos sistemas o aplicaciones.​​​​​ El modelo propuesto por Gahi, acepta datos de entrada cifrados y luego los procesa en función de las directrices marcadas por el usuario, sin llegar a descifrarlos nunca, y ofreciendo la garantía de que sólo el usuario que solicito el procesado de los datos tiene la capacidad de descifrarlos. De esta manera, el sistema permite a los clientes utilizar determinados servicios, ofrecidos por aplicaciones o sistemas remotos, con la confianza de que no existe riesgo de que sus datos sean revelados, incluso cuando los servidores sean de dudosa reputación.

Véase también

• Homomorfismo
• Firmas homomórficas para codificación de red
• Computación verificable mediante un sistema totalmente homomórfico

Enalces externos

• Homomorphic encryption en Cryptology Pointers
• The Homomorphic Encryption Project
• The Open Source hcrypt Project
• American Scientist article
• HElib - Librería de cifrado homomórfico escrita en C++ bajo licencia GNU GPL
• Translucent Database - Una arquitectura basada en estos principios.