Cifrado homomórfico

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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.[1] 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.[2] 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.[3] 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.[4] 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,[5] 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[editar]

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

RSA sin relleno[editar]

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[editar]

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[editar]

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_1r_2)^2 = \mathcal{E}(b_1 \oplus b_2)

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

Benaloh[editar]

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_1r_2)^c = \mathcal{E}(x_1 + x_2 \;\bmod\; c )

Paillier[editar]

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_1r_2)^m = \mathcal{E}( x_1 + x_2 \;\bmod\; m)

Otros sistemas criptográficos parcialmente homomórficos[editar]

Cifrado totalmente homomórfico[editar]

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).[6]

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 morfirmos 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.[7] 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[8] 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[nota 1] de profundidad arbitraria, usando criptografía basada en retículos (en inglés: lattice-based cryptography),[9] según anunciaba la compañía IBM en junio de 2009.[10] [11]

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.[12]

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.[13] En el trabajo de Van Dijk, publicado en 2009 junto con Craig Gentry, Shai Halevi y Vinod Vaikuntanathan,[14] 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.[15]

Implementaciones[editar]

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.[16]

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.[17] 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[18]

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.[19] En abril de 2013, IBM liberó en GitHub la primera versión de HElib,[20] una librería que implementa el sistema de cifrado homomórfico de Brakerski, Gentry y Vaikuntanathan (BGV),[21] escrita en lenguaje C++ y bajo licencia GNU GPL.[22]

Hacia aplicaciones de Internet totalmente seguras[editar]

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.[23] [24] [25] [26] [27] 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[editar]

Referencias[editar]

  1. Martínez, Santi; Mateu, Víctor; Tomàs, Rosana; Valls, Magda. Criptografía ordenable para bases de datos. http://gef2012.mondragon.edu/recsi2012/es/programa/recsi2012_submission_62.pdf. Consultado el 9 de marzo de 2014. 
  2. Yang, Pan; Gui, Xiaolin; Yao, Jing; Lin, Jiancai; Tian, Feng (diciembre 2013). «ICDM: An Encryption That Supports Unlimited Times Homomorphic Arithmetic Operations on Encrypted Data» (en inglés). Computational Science and Engineering (CSE), 2013 IEEE 16th International Conference:  pp. 1220-1225. doi:10.1109/CSE.2013.181. 
  3. Soriano Ibáñez, Miquel (13 de marzo de 2009). «Seguridad en los procesos de voto electrónico remoto: registro, votación, consolidación de resultados y auditoria». TDX (Theses and Dissertations Online):  pp. 29-30. ISBN 9788469225073. http://www.tdx.cat/handle/10803/7043. 
  4. Stuntz, Craig (18 de marzo de 2010). «What is Homomorphic Encryption, and Why Should I Care?» (en inglés).
  5. Rivest, Ron (29 de octubre de 2002). «Lecture Notes 15: Voting, Homomorphic Encryption» (en inglés).
  6. Micciancio, Daniele (1 de marzo de 2010). Association for Computing Machinery (ed.): «A First Glimpse of Cryptography's Holy Grail» (en inglés). Consultado el 17 de marzo de 2010.
  7. Rivest, Ronald; Adleman, Len; Dertouzos, Michael (1978). «On data banks and privacy homomorphisms» (en inglés). Foundations of secure computation 4 (11):  pp. 169-180. http://smartech.gatech.edu/xmlui/bitstream/handle/1853/40598/g-36-619_142482.pdf#page=181. 
  8. Gentry, Craig. «A Fully Homomorphic Encryption Scheme (Ph.D. thesis)» (en inglés).
  9. Gentry, Craig (2009). escrito en Bethesda, MD, USA. «Fully Homomorphic Encryption Using Ideal Lattices» (en inglés). ACM. STOC '09 (New York, NY, USA):  pp. 169-178. doi:10.1145/1536414.1536440. http://0-doi.acm.org.cataleg.uoc.edu/10.1145/1536414.1536440. 
  10. Fishkind, Ari. «IBM Researcher Solves Longstanding Cryptographic Challenge» (en inglés). Consultado el 22 de febrero de 2014.
  11. Michael Cooney (25 de junio de 2009). Computer World (ed.): «IBM touts encryption innovation» (en inglés). Consultado el 14 de julio de 2009.
  12. Stehle, Damien; Ron Steinfeld (19 de mayo de 2010). International Association for Cryptologic Research (ed.): «Faster Fully Homomorphic Encryption» (en inglés). Consultado el 15 de septiembre de 2010.
  13. Gentry, Craig (2010). «Computing arbitrary functions of encrypted data» (en inglés). Communications of the ACM 53 (3):  pp. 97-105. http://crypto.stanford.edu/craig/easy-fhe.pdf. 
  14. Van Dijk, Marten; Gentry, Craig; Halevi, Shai; Vaikuntanathan, Vinod (2010). «Fully homomorphic encryption over the integers» (en inglés). Advances in Cryptology--EUROCRYPT 2010 (Springer):  pp. 24-43. https://eprint.iacr.org/2009/616.pdf. 
  15. Levieil, Eric; Naccache, David (2008). «Cryptographic test correction» (en inglés). Public Key Cryptography--PKC 2008 (Springer):  pp. 85-100. http://f3.tiera.ru/2/Cs_Computer%20science/CsLn_Lecture%20notes/Public%20Key%20Cryptography%20-%20PKC%202008,%2011%20conf.(LNCS4939,%20Springer,%202008)(ISBN%209783540784395)(408s).pdf#page=96. 
  16. Riggio, Roberto; Sicari, Sabrina (2009) (en inglés). Secure aggregation in hybrid mesh/sensor networks. IEEE.  pp. 1-6. http://disi.unitn.it/~riggio/lib/exe/fetch.php?media=publications:sasn2009.pdf. 
  17. Smart, Nigel; Vercauteren, Frederik (2010). «Fully homomorphic encryption with relatively small key and ciphertext sizes» (en inglés). Public Key Cryptography--PKC 2010 (Springer):  pp. 420-443. http://www.math.leidenuniv.nl/~dfreeman/smart.pdf. 
  18. Gentry, Craig; Halevi, Shai (2010). «A working implementation of fully homomorphic encryption» (en inglés). Presentation de EUROCRYPT. http://eurocrypt2010rump.cr.yp.to/9854ad3cab48983f7c2c5a2258e27717.pdf. 
  19. Coron, Jean-SébastienDavid; Tibouchi, Mehdi (2012). «Public key compression and modulus switching for fully homomorphic encryption over the integers» (en inglés). Advances in Cryptology--EUROCRYPT 2012 (Springer):  pp. 446-464. https://eprint.iacr.org/2011/440.pdf. 
  20. Gupta, C.P.I. (octubre 2013). «A fully homomorphic encryption scheme with symmetric keys with application to private data processing in clouds» (en inglés). Network of the Future (NOF), 2013 Fourth International Conference:  pp. 1-4. doi:10.1109/NOF.2013.6724526. 
  21. Brakerski, ZvikaCraig; Vaikuntanathan, Vinod (2011). «Fully Homomorphic Encryption without Bootstrapping» (en inglés). Cryptology ePrint Archive, Report 2011/277. http://eprint.iacr.org/2011/277.pdf. 
  22. Halevi, Shai. «An Implementation of homomorphic encryption». Consultado el 8 de marzo de 2014.
  23. Gahi, YoussefMouhcine; El-Khatib, Khalil (2011). «A secure database system using homomorphic encryption schemes» (en inglés). DBKDA 2011, The Third International Conference on Advances in Databases, Knowledge, and Data Applications:  pp. 54-58. http://www.thinkmind.org/download.php?articleid=dbkda_2011_3_20_30074. 
  24. Gahi, Y.M.; El-Khatib, K. (diciembre 2011). «Encrypted processes for oblivious data retrieval» (en inglés). Internet Technology and Secured Transactions (ICITST), 2011 International Conference:  pp. 514-518. http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6148390&isnumber=6148349. 
  25. Gahi, Y.M.; El-Khatib, K. (2012). «Privacy Preserving Scheme for Location-Based Services» (en inglés). In The Journal of Information Security:  pp. 105–112. http://www.scirp.org/journal/PaperInformation.aspx?PaperID=18792. 
  26. Gahi, Y.M.; El-Khatib, K. (2012). «A fully private video on-Demand service». The 25th IEEE annual Canadian Conference on Electrical and Computer Engineering:  pp. 1–4. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6334991&queryText%3Dgahi. 
  27. Gahi, Y.M.; El-Khatib, K. (2012). «An encrypted trust-based routing protocol». The 2012 IEEE Conference on Open Systems:  pp. 1–5. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6417643&queryText%3Dgahi. 

Notas[editar]

  1. En este contexto, se entiende por circuito cualquier serie de operaciones que se realizan sobre un texto cifrado. La palabra circuito se toma del modelado matemático de circuitos digitales basasados en puertas lógicas, véase álgebra de Boole, puerta lógica y circuitos de conmutación.

Enalces externos[editar]