Hace un tiempo tomé el curso CS355 (Criptografía Avanzada) en Stanford. Nos enseñaron tres de los estudiantes de doctorado de Dan, Dima Kogan, Florian Tramer y Saba Eskandarian. Los tres profesores de doctorado tienen cada uno sus propias características y sus direcciones de investigación también son muy diferentes. Dima se centra en la tecnología de protección de la privacidad PIR (Private Information Retri), Florian se centra en la investigación de ML y blockchain, y Saba se centra en la prueba de conocimiento cero.
El curso CS355 cubre casi todo el contenido en el campo de la criptografía desde la antigüedad hasta el presente. Desde la primera función unidireccional (función unidireccional), hasta la ecuación elíptica (ECC) y el emparejamiento, y finalmente hasta algunos MPC populares, conocimiento cero, recuperación de información privada (PIR), algoritmos completamente homomórficos, etc. . Dado que la clase acaba de terminar hace dos días, organicé una serie de notas mientras el contenido del conocimiento aún estaba en mi memoria superficial. El contenido del curso es muy interesante, compartiré el resto contigo más adelante cuando tenga tiempo ~
En este número, hablaremos sobre el recientemente popular cifrado totalmente homomórfico (FHE) y la tecnología de cifrado basada en celosía que lo acompaña.
¿Qué es el cifrado totalmente homomórfico?
Creo que muchos amigos han oído hablar del nombre de cifrado totalmente homomórfico (FHE). En los últimos años, ha habido cada vez más temas sobre la protección de la privacidad personal y también se han popularizado ampliamente una serie de tecnologías de aplicación de criptografía, incluido el cifrado homomórfico.
Para comprender mejor este tema, me gustaría presentar brevemente la definición de cifrado totalmente homomórfico.
Revisión del sistema de cifrado
Antes de comenzar, repasemos el sistema de cifrado más tradicional.
Todos sabemos que si desea crear un sistema de cifrado, a menudo necesita una clave. A través de esta clave, podemos cifrar la información de texto sin formato en texto cifrado en un extremo y luego usar la clave para cambiar el texto cifrado a su apariencia original en el otro extremo. Sin esta Clave, sería difícil que otras personas supieran qué información hemos transmitido.
La ilustración anterior muestra básicamente el panorama general de todos los sistemas de cifrado habituales. Todos los sistemas de cifrado, si utilizamos un método de descripción más formal, sin duda hacen tres cosas:
Los amigos que saben algo sobre algoritmos de cifrado definitivamente conocerán los más comunes. Algunos algoritmos de cifrado, como AES, RSA, etc. Todo el mundo debe saber también que, en términos generales, los sistemas de cifrado se dividen en dos tipos: sistemas de cifrado simétrico y sistemas de cifrado asimétrico. Los tres pasos que describimos aquí son realmente aplicables a cualquier sistema de cifrado. Si es simétrico, entonces la clave utilizada para cifrar y descifrar es la misma. Si se trata de un sistema asimétrico, entonces se utiliza la clave pública para el cifrado y una clave privada diferente para el descifrado.
En la investigación de criptografía, cada vez que vemos la definición de un nuevo sistema, a menudo tenemos que establecer las propiedades que debería tener el sistema.
La principal importancia de la seguridad semántica es que un espectador no puede distinguir entre dos mensajes cifrados. Entonces, si un intruso espía la red y ve la información cifrada que envío, siempre que el sistema de cifrado que uso sea semánticamente seguro, entonces puedo estar seguro de que el intruso no puede obtener ninguna información sobre el contenido cifrado del texto cifrado.
Después de satisfacer las dos propiedades anteriores, un sistema de cifrado se vuelve sólido.
Después de comprender de qué se trata el sistema de cifrado, podemos prestar atención a este texto cifrado que parece un código confuso generado aleatoriamente. Todos sabemos que no obtendremos ninguna información con sólo mirar el texto cifrado. Pero, ¿significa esto que si no hay clave y sólo texto cifrado, no podemos hacer nada?
Todos sabemos la respuesta: realmente no.
A esta propiedad la llamamos homomorfismo aditivo. Esto significa que el texto cifrado mantiene una sutil relación algebraica con el texto original anterior. Si sumamos el texto cifrado, podemos obtener el nuevo texto cifrado sumando el texto original. Del mismo modo, se puede concluir que también existen algoritmos de cifrado aditivamente homomórficos. Podemos multiplicar el texto cifrado generado por un algoritmo multiplicativamente homomórfico y luego obtener el texto cifrado correspondiente al resultado de multiplicar los textos originales. En todo el proceso, no necesitamos conocer ninguna información relacionada con la clave, simplemente combinamos el texto cifrado que parece un código aleatorio confuso.
Por ejemplo: sistema de votación anónima
A continuación, demos un ejemplo para describir vívidamente la practicidad del cifrado homomórfico.
Todos sabemos cómo es la votación en línea: si el jefe de una empresa quiere iniciar una ola de votaciones, debe elegir si la empresa debe adoptar el sistema 996. Luego, el jefe puede pedirle a TI que configure un servidor y permita que los empleados presenten sus opciones: vote 0 para significar que no quieren y vote 1 para significar que quieren. Después del período de votación final, el jefe puede sumar todos los votos. Si el total final de todos los votos supera la mitad del número de empleados, la empresa comenzará con 996.
Este mecanismo de votación parece muy simple, pero hay un gran problema de privacidad: si el jefe quiere que todos los empleados sean 996, pero solo inicia deliberadamente esta votación para pescar a las autoridades para ver qué empleado no está dispuesto a trabajar horas extras, entonces el jefe Puede confiarle tranquilamente a su hermano menor que escuche a escondidas Internet, registre las opciones presentadas por cada empleado y finalmente vea quién votó 0. Como resultado, los empleados tienen mucho miedo y no se atreven a expresar sus sentimientos.
Si podemos utilizar un algoritmo de cifrado homomórfico aditivo, entonces este problema se puede resolver fácilmente.
Por supuesto, este sistema todavía está muy incompleto: por ejemplo, el departamento de TI puede ayudar directamente al jefe a descifrar los votos de todos y registrarlos en un documento. Existen otras herramientas criptográficas que pueden ayudarnos a solucionar este problema. Por razones de espacio, no se darán más explicaciones aquí.
Pero llegados a este punto, deberíamos poder sentir el poder del algoritmo de cifrado homomórfico. Podemos entenderlo de esta manera: a través del algoritmo de cifrado homomórfico, los usuarios pueden realizar algún tipo de cálculo proxy seguro (Secure Delegated Computation) con un servidor remoto (nube) que no es de confianza. Los usuarios pueden utilizar tecnología de cifrado homomórfico para cifrar su entrada privada confidencial y confiarla a la nube, luego la nube puede realizar un cierto grado de cálculo sobre los datos cifrados y finalmente obtener el resultado cifrado que el usuario desea y devolverlo al usuario de la nube. Finalmente, el usuario puede utilizar la clave de descifrado para abrir el resultado. Durante todo el acuerdo, la parte delegada (la nube) nunca podrá ver ninguna información útil relacionada con aportaciones privadas.
### Clasificación de sistemas de cifrado homomórficos.
Después de comprender aproximadamente las dos propiedades homomórficas más básicas, otros conceptos se vuelven muy fáciles de entender. Desde una perspectiva sistemática, los sistemas de cifrado homomórficos se dividen aproximadamente en cuatro categorías: homomorfismo parcial, homomorfismo aproximado, homomorfismo completo de series finitas y homomorfismo completo.
A continuación, echemos un vistazo a las definiciones específicas de cada categoría.
Cifrado parcialmente homomórfico
La etapa más elemental del cifrado homomórfico se denomina cifrado parcialmente homomórfico, que se define como el texto cifrado que tiene una sola característica homomórfica. Esta etapa incluye los dos modos de homomorfismo aditivo y homomorfismo multiplicativo que describimos anteriormente.
¡Obtenemos el texto cifrado correspondiente a la multiplicación de estos dos mensajes! Esta es la propiedad del homomorfismo multiplicativo. Podemos continuar superponiendo nuevos textos cifrados encima de este texto cifrado, de modo que podamos obtener cualquier multiplicación entre textos cifrados.
Como dijimos en el párrafo anterior, si queremos multiplicar las entradas privadas y obtener una combinación lineal entre ellas, no se puede completar un algoritmo de cifrado simple parcialmente homomórfico (RSA, ElGamal). Por tanto, debemos pasar a la siguiente etapa.
La siguiente etapa del cifrado parcialmente homomórfico es el cifrado aproximadamente homomórfico, que es un paso más hacia el cifrado totalmente homomórfico que queremos lograr. Si tenemos un algoritmo de cifrado aproximadamente homomórfico, entonces podemos calcular la suma y la multiplicación en el texto cifrado al mismo tiempo. Sin embargo, cabe señalar que debido a que esta etapa es aproximadamente homomórfica (Algo homomórfica), el número de sumas y multiplicaciones que se pueden realizar es muy limitado, y la función F que se puede calcular también está dentro de un rango limitado.
No hay muchos ejemplos comunes de cifrado aproximadamente homomórfico en esta etapa. Si decimos que el ejemplo mejor entendido debería ser el algoritmo de cifrado de grupo cíclico basado en emparejamiento.
Arriba analizamos brevemente el algoritmo de cifrado ElGamal basado en grupos cíclicos ordinarios. Todos sabemos que este algoritmo es aditivamente homomórfico, lo que significa que puede obtener combinaciones lineales entre textos cifrados arbitrarios. De hecho, en algunos grupos cíclicos especiales, también podemos encontrar algunas propiedades de homomorfismo multiplicativo débiles.
Esta limitación demuestra que el sistema es aproximadamente homomórfico, ya que no podemos calcular la función F de lógica y profundidad arbitrarias.
Cifrado homomórfico completamente nivelado
Después de llegar a la siguiente etapa, estamos un paso más cerca del objetivo del homomorfismo total.
Esta etapa se denomina cifrado totalmente homomórfico de series finitas. En esta etapa, ya podemos realizar cualquier combinación de suma y multiplicación en el texto cifrado sin ninguna limitación en el número de veces.
Cifrado totalmente homomórfico (FHE)
Después de muchas llamadas, finalmente llega el cifrado totalmente homomórfico (FHE) que estamos esperando ver.
Como su nombre indica, un sistema de cifrado totalmente homomórfico no tiene restricciones en los métodos de cálculo. Podemos combinar arbitrariamente textos cifrados para formar nuevos textos cifrados sin una clave, y el nuevo texto cifrado, independientemente de la complejidad computacional, se puede restaurar perfectamente al texto original.
Cuando llegamos a esta etapa, el cálculo del agente seguro mencionado anteriormente se vuelve factible. Si podemos encontrar un sistema de cifrado totalmente homomórfico más eficiente, podremos enviar de forma segura todos los cálculos locales a la nube sin filtrar ningún dato.
Definición de sistema de cifrado totalmente homomórfico
Antes de comenzar la discusión sobre la historia de los sistemas totalmente homomórficos a continuación, podemos definir sistemáticamente la definición formal de sistemas totalmente homomórficos. Un sistema de cifrado totalmente homomórfico tiene un total de cuatro algoritmos:
## Revisión histórica del cifrado totalmente homomórfico
Antes de comenzar a aprender cómo se implementa el algoritmo de cifrado totalmente homomórfico, también podríamos echar un vistazo a cómo surgió el concepto de cifrado totalmente homomórfico.
El concepto de FHE (completamente homomórfico) se propuso a finales de los años 1970. En 1978, Rivest, Adleman y Dertouzos, varios nombres importantes de la criptografía, mencionaron por primera vez en su artículo Sobre bancos de datos y homomorfismos de privacidad la idea de un sistema que puede realizar ciertos cálculos en texto cifrado y operar indirectamente en el texto original. Más tarde, esta idea se resumió y se denominó cifrado totalmente homomórfico.
Se puede ver que el concepto de cifrado totalmente homomórfico se ha propuesto durante mucho tiempo. Sorprendentemente, en 1976, dos años antes de que se publicara el artículo, ¡acababa de proponerse el protocolo de intercambio de claves Diffle-Hellman! Esto demuestra que la imaginación de los expertos en criptografía sigue siendo muy rica.
Cuando se propuso el concepto de FHE, toda la comunidad académica quedó conmovida y comenzó una búsqueda de décadas, tratando de encontrar un algoritmo perfecto con propiedades totalmente homomórficas. Pero en las últimas décadas, la gente ha probado todas las opciones imaginables, pero no puede encontrar una opción que satisfaga todas las condiciones para ser completamente homomórfico y cuya seguridad pueda demostrarse fácilmente.
Hasta 2009, el doctor Craig Gentry, que estudiaba en Stanford, de repente tuvo una idea y superó las dificultades del algoritmo FHE. En su tesis doctoral, presentó por primera vez un sistema de cifrado totalmente homomórfico, razonable y seguro. Este sistema se basa en el supuesto de red ideal. El sistema totalmente homomórfico propuesto por Gentry09 a menudo se denomina sistema de cifrado totalmente homomórfico de primera generación.
En el artículo de Gentry, también mencionó un concepto crucial llamado Bootstrapping. Bootstrapping es una técnica de procesamiento especial para texto cifrado. Después del procesamiento, puede "actualizar" un texto cifrado con ruido cercano al valor crítico en un nuevo texto cifrado con muy poco ruido. Mediante Bootstrapping, el ruido de un sistema en serie finita nunca puede exceder el valor crítico, convirtiéndose así en un sistema completamente homomórfico. De esta forma, podemos calcular homomórficamente F de cualquier tamaño.
Después del gran avance de Gentry, todo el círculo de la criptografía volvió a caer en la locura y todos comenzaron a luchar para encontrar un sistema totalmente homomórfico más eficiente y versátil basado en las ideas propuestas por Gentry.
En 2011, dos grandes, Brakerski y Vaikuntanathan, propusieron un nuevo sistema de cifrado totalmente homomórfico, que se basa en el aprendizaje con errores (LWE), otra suposición del cifrado reticular. Ese mismo año, Brakerski, Gentry y Vaikuntanathan completaron el sistema y lo publicaron oficialmente. El sistema totalmente homomórfico que inventaron se llama sistema BGV para abreviar. El sistema BGV es un sistema de cifrado homomórfico de nivel limitado, pero se puede convertir en un sistema completamente homomórfico mediante Bootstrapping. En comparación con el sistema propuesto por Gentry09, el sistema BGV utiliza un supuesto LWE más realista. En términos generales, llamamos al sistema BGV el sistema de cifrado totalmente homomórfico de segunda generación.
En 2013, Gentry regresó. Gentry, Sahai y Waters han lanzado un nuevo sistema de cifrado GSW totalmente homomórfico. El sistema GSW es similar al BGV en que tiene propiedades totalmente homomórficas de series finitas. Se basa en el supuesto LWE más simple y puede ser completamente homomórfico mediante Bootstrapping. Generalmente nos referimos al sistema GSW como el sistema de cifrado totalmente homomórfico de tercera generación.
Después de 2013, la criptosfera básicamente floreció. Basado en el sistema totalmente homomórfico original de tres generaciones, han surgido varios diseños nuevos, dedicados a optimizar y acelerar la eficiencia operativa de los sistemas BGV y GSW. IBM desarrolló una biblioteca informática totalmente homomórfica de código abierto HElib basada en el sistema BGV y la trasplantó con éxito a las principales plataformas móviles. Al mismo tiempo, hay otro proyecto de código abierto, TFHE, que también vale la pena mencionar. TFHE se basa en el sistema GSW, con varias optimizaciones y aceleraciones agregadas, y ahora es muy famoso.
Además de desarrollar bibliotecas tradicionales totalmente homomórficas, muchos equipos también están estudiando cómo acelerar mejor el cálculo de algoritmos de cifrado totalmente homomórficos a través de hardware heterogéneo como GPU, FPGA y ASIC. Por ejemplo, cuFHE es un conocido sistema de cifrado totalmente homomórfico acelerado por GPU basado en CUDA.
Desde la perspectiva actual, han pasado 11 años desde que Gentry llamó a la puerta del sistema totalmente homomórfico. Hoy en día, la investigación sobre FHE está en auge en la industria y muchas personas están estudiando sistemas totalmente homomórficos desde diferentes perspectivas y requisitos de aplicación. Hasta hoy, ya contamos con una variedad de métodos de implementación FHE factibles, pero lo que todos siguen persiguiendo es la eficiencia del funcionamiento del sistema FHE. Tomando como ejemplo la biblioteca FHE de vanguardia actual, calcular homomórficamente alguna lógica relativamente simple en una plataforma móvil puede tomar tan solo decenas de milisegundos y hasta decenas de segundos. Estas unidades de tiempo son extremadamente lentas para los sistemas informáticos.
Cómo hacer que el sistema FHE funcione de manera más eficiente en plataformas heterogéneas sigue siendo un misterio sin resolver. Si este problema se resuelve una vez, convertir todos los cálculos informáticos a completamente homomórficos y hacer que los agentes realicen cálculos en nubes de terceros será un futuro fácil.
La relación entre FHE y MPC
Antes de finalizar el artículo, me gustaría añadir unas palabras sobre la relación entre FHE y MPC. MPC significa Computación Multipartita Segura, que es computación multipartita confiable. Por lo general, significa que varias partes tienen sus propios datos privados y no quieren revelarlos a otros, pero quieren utilizar sus propios datos para calcular una función F juntos y compartir los resultados del cálculo.
MPC es en realidad un campo muy conocido y estudiado durante mucho tiempo. Desde que el criptógrafo Yao Qizhi lanzó sus Circuitos confusos en el siglo pasado, el campo de MPC ha ganado un amplio reconocimiento y se han producido muchos avances. Ahora ya tenemos muchas bibliotecas MPC que se pueden usar y también tienen cierta eficiencia operativa.
Los amigos que conocen MPC pueden tener muchas preguntas después de ver la difícil historia de los sistemas de cifrado totalmente homomórficos: ¿Por qué no se puede reemplazar directamente el cifrado totalmente homomórfico por un protocolo MPC?
De hecho, un protocolo MPC puede sustituir completamente a un protocolo FHE. Solo necesitamos usar el usuario y la entrada privada como parte en un protocolo, y luego usar el servidor de computación proxy remoto como otra parte, que cumple con las condiciones para la ejecución del protocolo MPC. Solo a través de ciertas interacciones, la computación proxy puede ser realizado Y el servidor no puede ver la entrada privada.
Pero hay un punto muy importante que hemos pasado por alto: dado que MPC es interactivo, el usuario y el servidor necesitan calcular y comunicarse juntos para completar el protocolo. Esto entra en conflicto con el requisito más fundamental de la informática de agentes FHE. Si el usuario necesita permanecer en línea todo el tiempo para completar el acuerdo y también pagar parte de la potencia informática, entonces, de hecho, el cálculo no es "proxy" en absoluto y ambas partes solo hacen más cálculos por el bien de la seguridad de la información. . Esto también explica por qué el campo de MPC ha logrado grandes avances, pero el campo de FHE aún es desconocido, porque los dos sistemas resuelven problemas completamente diferentes.
## Próxima parada: sistema de cifrado GSW totalmente homomórfico
Al ver esto, todos deben tener un conocimiento muy profundo del sistema de cifrado totalmente homomórfico.
En la siguiente parada, podemos aprender sobre el sistema de cifrado totalmente homomórfico GSW mencionado anteriormente. Aunque esta es la tercera generación de sistemas totalmente homomórficos, creo que entre los tres sistemas de Gentry09, BGV y GSW, GSW es el que tiene menos suposiciones, la estructura más simple y el más fácil de entender. Y ahora hay muchas bibliotecas de código abierto (como TFHE) creadas en base al sistema GSW.
Por razones de espacio, finalizaremos este artículo aquí. En el próximo artículo, primero aprenderemos los conceptos básicos del sistema GSW: el sistema de cifrado basado en celosía y el problema LWE. Una vez que se comprende el problema de LWE, el problema que resuelve GSW queda muy claro.
Ver originales
Esta página puede contener contenido de terceros, que se proporciona únicamente con fines informativos (sin garantías ni declaraciones) y no debe considerarse como un respaldo por parte de Gate a las opiniones expresadas ni como asesoramiento financiero o profesional. Consulte el Descargo de responsabilidad para obtener más detalles.
Una exploración preliminar del cifrado totalmente homomórfico: la definición y revisión histórica de FHE
Autor: Steven Yue
Hace un tiempo tomé el curso CS355 (Criptografía Avanzada) en Stanford. Nos enseñaron tres de los estudiantes de doctorado de Dan, Dima Kogan, Florian Tramer y Saba Eskandarian. Los tres profesores de doctorado tienen cada uno sus propias características y sus direcciones de investigación también son muy diferentes. Dima se centra en la tecnología de protección de la privacidad PIR (Private Information Retri), Florian se centra en la investigación de ML y blockchain, y Saba se centra en la prueba de conocimiento cero.
El curso CS355 cubre casi todo el contenido en el campo de la criptografía desde la antigüedad hasta el presente. Desde la primera función unidireccional (función unidireccional), hasta la ecuación elíptica (ECC) y el emparejamiento, y finalmente hasta algunos MPC populares, conocimiento cero, recuperación de información privada (PIR), algoritmos completamente homomórficos, etc. . Dado que la clase acaba de terminar hace dos días, organicé una serie de notas mientras el contenido del conocimiento aún estaba en mi memoria superficial. El contenido del curso es muy interesante, compartiré el resto contigo más adelante cuando tenga tiempo ~
En este número, hablaremos sobre el recientemente popular cifrado totalmente homomórfico (FHE) y la tecnología de cifrado basada en celosía que lo acompaña.
¿Qué es el cifrado totalmente homomórfico?
Creo que muchos amigos han oído hablar del nombre de cifrado totalmente homomórfico (FHE). En los últimos años, ha habido cada vez más temas sobre la protección de la privacidad personal y también se han popularizado ampliamente una serie de tecnologías de aplicación de criptografía, incluido el cifrado homomórfico.
Para comprender mejor este tema, me gustaría presentar brevemente la definición de cifrado totalmente homomórfico.
Revisión del sistema de cifrado
Antes de comenzar, repasemos el sistema de cifrado más tradicional.
Todos sabemos que si desea crear un sistema de cifrado, a menudo necesita una clave. A través de esta clave, podemos cifrar la información de texto sin formato en texto cifrado en un extremo y luego usar la clave para cambiar el texto cifrado a su apariencia original en el otro extremo. Sin esta Clave, sería difícil que otras personas supieran qué información hemos transmitido.
En la investigación de criptografía, cada vez que vemos la definición de un nuevo sistema, a menudo tenemos que establecer las propiedades que debería tener el sistema.
La principal importancia de la seguridad semántica es que un espectador no puede distinguir entre dos mensajes cifrados. Entonces, si un intruso espía la red y ve la información cifrada que envío, siempre que el sistema de cifrado que uso sea semánticamente seguro, entonces puedo estar seguro de que el intruso no puede obtener ninguna información sobre el contenido cifrado del texto cifrado.
Después de satisfacer las dos propiedades anteriores, un sistema de cifrado se vuelve sólido.
Después de comprender de qué se trata el sistema de cifrado, podemos prestar atención a este texto cifrado que parece un código confuso generado aleatoriamente. Todos sabemos que no obtendremos ninguna información con sólo mirar el texto cifrado. Pero, ¿significa esto que si no hay clave y sólo texto cifrado, no podemos hacer nada?
Todos sabemos la respuesta: realmente no.
A esta propiedad la llamamos homomorfismo aditivo. Esto significa que el texto cifrado mantiene una sutil relación algebraica con el texto original anterior. Si sumamos el texto cifrado, podemos obtener el nuevo texto cifrado sumando el texto original. Del mismo modo, se puede concluir que también existen algoritmos de cifrado aditivamente homomórficos. Podemos multiplicar el texto cifrado generado por un algoritmo multiplicativamente homomórfico y luego obtener el texto cifrado correspondiente al resultado de multiplicar los textos originales. En todo el proceso, no necesitamos conocer ninguna información relacionada con la clave, simplemente combinamos el texto cifrado que parece un código aleatorio confuso.
Por ejemplo: sistema de votación anónima
A continuación, demos un ejemplo para describir vívidamente la practicidad del cifrado homomórfico.
Todos sabemos cómo es la votación en línea: si el jefe de una empresa quiere iniciar una ola de votaciones, debe elegir si la empresa debe adoptar el sistema 996. Luego, el jefe puede pedirle a TI que configure un servidor y permita que los empleados presenten sus opciones: vote 0 para significar que no quieren y vote 1 para significar que quieren. Después del período de votación final, el jefe puede sumar todos los votos. Si el total final de todos los votos supera la mitad del número de empleados, la empresa comenzará con 996.
Este mecanismo de votación parece muy simple, pero hay un gran problema de privacidad: si el jefe quiere que todos los empleados sean 996, pero solo inicia deliberadamente esta votación para pescar a las autoridades para ver qué empleado no está dispuesto a trabajar horas extras, entonces el jefe Puede confiarle tranquilamente a su hermano menor que escuche a escondidas Internet, registre las opciones presentadas por cada empleado y finalmente vea quién votó 0. Como resultado, los empleados tienen mucho miedo y no se atreven a expresar sus sentimientos.
Si podemos utilizar un algoritmo de cifrado homomórfico aditivo, entonces este problema se puede resolver fácilmente.
Por supuesto, este sistema todavía está muy incompleto: por ejemplo, el departamento de TI puede ayudar directamente al jefe a descifrar los votos de todos y registrarlos en un documento. Existen otras herramientas criptográficas que pueden ayudarnos a solucionar este problema. Por razones de espacio, no se darán más explicaciones aquí.
Pero llegados a este punto, deberíamos poder sentir el poder del algoritmo de cifrado homomórfico. Podemos entenderlo de esta manera: a través del algoritmo de cifrado homomórfico, los usuarios pueden realizar algún tipo de cálculo proxy seguro (Secure Delegated Computation) con un servidor remoto (nube) que no es de confianza. Los usuarios pueden utilizar tecnología de cifrado homomórfico para cifrar su entrada privada confidencial y confiarla a la nube, luego la nube puede realizar un cierto grado de cálculo sobre los datos cifrados y finalmente obtener el resultado cifrado que el usuario desea y devolverlo al usuario de la nube. Finalmente, el usuario puede utilizar la clave de descifrado para abrir el resultado. Durante todo el acuerdo, la parte delegada (la nube) nunca podrá ver ninguna información útil relacionada con aportaciones privadas.
Después de comprender aproximadamente las dos propiedades homomórficas más básicas, otros conceptos se vuelven muy fáciles de entender. Desde una perspectiva sistemática, los sistemas de cifrado homomórficos se dividen aproximadamente en cuatro categorías: homomorfismo parcial, homomorfismo aproximado, homomorfismo completo de series finitas y homomorfismo completo.
A continuación, echemos un vistazo a las definiciones específicas de cada categoría.
Cifrado parcialmente homomórfico
La etapa más elemental del cifrado homomórfico se denomina cifrado parcialmente homomórfico, que se define como el texto cifrado que tiene una sola característica homomórfica. Esta etapa incluye los dos modos de homomorfismo aditivo y homomorfismo multiplicativo que describimos anteriormente.
¡Obtenemos el texto cifrado correspondiente a la multiplicación de estos dos mensajes! Esta es la propiedad del homomorfismo multiplicativo. Podemos continuar superponiendo nuevos textos cifrados encima de este texto cifrado, de modo que podamos obtener cualquier multiplicación entre textos cifrados.
Cifrado homomórfico aproximado (Cifrado algo homomórfico)
Como dijimos en el párrafo anterior, si queremos multiplicar las entradas privadas y obtener una combinación lineal entre ellas, no se puede completar un algoritmo de cifrado simple parcialmente homomórfico (RSA, ElGamal). Por tanto, debemos pasar a la siguiente etapa.
La siguiente etapa del cifrado parcialmente homomórfico es el cifrado aproximadamente homomórfico, que es un paso más hacia el cifrado totalmente homomórfico que queremos lograr. Si tenemos un algoritmo de cifrado aproximadamente homomórfico, entonces podemos calcular la suma y la multiplicación en el texto cifrado al mismo tiempo. Sin embargo, cabe señalar que debido a que esta etapa es aproximadamente homomórfica (Algo homomórfica), el número de sumas y multiplicaciones que se pueden realizar es muy limitado, y la función F que se puede calcular también está dentro de un rango limitado.
No hay muchos ejemplos comunes de cifrado aproximadamente homomórfico en esta etapa. Si decimos que el ejemplo mejor entendido debería ser el algoritmo de cifrado de grupo cíclico basado en emparejamiento.
Arriba analizamos brevemente el algoritmo de cifrado ElGamal basado en grupos cíclicos ordinarios. Todos sabemos que este algoritmo es aditivamente homomórfico, lo que significa que puede obtener combinaciones lineales entre textos cifrados arbitrarios. De hecho, en algunos grupos cíclicos especiales, también podemos encontrar algunas propiedades de homomorfismo multiplicativo débiles.
Esta limitación demuestra que el sistema es aproximadamente homomórfico, ya que no podemos calcular la función F de lógica y profundidad arbitrarias.
Cifrado homomórfico completamente nivelado
Después de llegar a la siguiente etapa, estamos un paso más cerca del objetivo del homomorfismo total.
Esta etapa se denomina cifrado totalmente homomórfico de series finitas. En esta etapa, ya podemos realizar cualquier combinación de suma y multiplicación en el texto cifrado sin ninguna limitación en el número de veces.
Cifrado totalmente homomórfico (FHE)
Después de muchas llamadas, finalmente llega el cifrado totalmente homomórfico (FHE) que estamos esperando ver.
Como su nombre indica, un sistema de cifrado totalmente homomórfico no tiene restricciones en los métodos de cálculo. Podemos combinar arbitrariamente textos cifrados para formar nuevos textos cifrados sin una clave, y el nuevo texto cifrado, independientemente de la complejidad computacional, se puede restaurar perfectamente al texto original.
Cuando llegamos a esta etapa, el cálculo del agente seguro mencionado anteriormente se vuelve factible. Si podemos encontrar un sistema de cifrado totalmente homomórfico más eficiente, podremos enviar de forma segura todos los cálculos locales a la nube sin filtrar ningún dato.
Definición de sistema de cifrado totalmente homomórfico
Antes de comenzar la discusión sobre la historia de los sistemas totalmente homomórficos a continuación, podemos definir sistemáticamente la definición formal de sistemas totalmente homomórficos. Un sistema de cifrado totalmente homomórfico tiene un total de cuatro algoritmos:
Antes de comenzar a aprender cómo se implementa el algoritmo de cifrado totalmente homomórfico, también podríamos echar un vistazo a cómo surgió el concepto de cifrado totalmente homomórfico.
El concepto de FHE (completamente homomórfico) se propuso a finales de los años 1970. En 1978, Rivest, Adleman y Dertouzos, varios nombres importantes de la criptografía, mencionaron por primera vez en su artículo Sobre bancos de datos y homomorfismos de privacidad la idea de un sistema que puede realizar ciertos cálculos en texto cifrado y operar indirectamente en el texto original. Más tarde, esta idea se resumió y se denominó cifrado totalmente homomórfico.
Se puede ver que el concepto de cifrado totalmente homomórfico se ha propuesto durante mucho tiempo. Sorprendentemente, en 1976, dos años antes de que se publicara el artículo, ¡acababa de proponerse el protocolo de intercambio de claves Diffle-Hellman! Esto demuestra que la imaginación de los expertos en criptografía sigue siendo muy rica.
Cuando se propuso el concepto de FHE, toda la comunidad académica quedó conmovida y comenzó una búsqueda de décadas, tratando de encontrar un algoritmo perfecto con propiedades totalmente homomórficas. Pero en las últimas décadas, la gente ha probado todas las opciones imaginables, pero no puede encontrar una opción que satisfaga todas las condiciones para ser completamente homomórfico y cuya seguridad pueda demostrarse fácilmente.
Hasta 2009, el doctor Craig Gentry, que estudiaba en Stanford, de repente tuvo una idea y superó las dificultades del algoritmo FHE. En su tesis doctoral, presentó por primera vez un sistema de cifrado totalmente homomórfico, razonable y seguro. Este sistema se basa en el supuesto de red ideal. El sistema totalmente homomórfico propuesto por Gentry09 a menudo se denomina sistema de cifrado totalmente homomórfico de primera generación.
En el artículo de Gentry, también mencionó un concepto crucial llamado Bootstrapping. Bootstrapping es una técnica de procesamiento especial para texto cifrado. Después del procesamiento, puede "actualizar" un texto cifrado con ruido cercano al valor crítico en un nuevo texto cifrado con muy poco ruido. Mediante Bootstrapping, el ruido de un sistema en serie finita nunca puede exceder el valor crítico, convirtiéndose así en un sistema completamente homomórfico. De esta forma, podemos calcular homomórficamente F de cualquier tamaño.
Después del gran avance de Gentry, todo el círculo de la criptografía volvió a caer en la locura y todos comenzaron a luchar para encontrar un sistema totalmente homomórfico más eficiente y versátil basado en las ideas propuestas por Gentry.
En 2011, dos grandes, Brakerski y Vaikuntanathan, propusieron un nuevo sistema de cifrado totalmente homomórfico, que se basa en el aprendizaje con errores (LWE), otra suposición del cifrado reticular. Ese mismo año, Brakerski, Gentry y Vaikuntanathan completaron el sistema y lo publicaron oficialmente. El sistema totalmente homomórfico que inventaron se llama sistema BGV para abreviar. El sistema BGV es un sistema de cifrado homomórfico de nivel limitado, pero se puede convertir en un sistema completamente homomórfico mediante Bootstrapping. En comparación con el sistema propuesto por Gentry09, el sistema BGV utiliza un supuesto LWE más realista. En términos generales, llamamos al sistema BGV el sistema de cifrado totalmente homomórfico de segunda generación.
En 2013, Gentry regresó. Gentry, Sahai y Waters han lanzado un nuevo sistema de cifrado GSW totalmente homomórfico. El sistema GSW es similar al BGV en que tiene propiedades totalmente homomórficas de series finitas. Se basa en el supuesto LWE más simple y puede ser completamente homomórfico mediante Bootstrapping. Generalmente nos referimos al sistema GSW como el sistema de cifrado totalmente homomórfico de tercera generación.
Después de 2013, la criptosfera básicamente floreció. Basado en el sistema totalmente homomórfico original de tres generaciones, han surgido varios diseños nuevos, dedicados a optimizar y acelerar la eficiencia operativa de los sistemas BGV y GSW. IBM desarrolló una biblioteca informática totalmente homomórfica de código abierto HElib basada en el sistema BGV y la trasplantó con éxito a las principales plataformas móviles. Al mismo tiempo, hay otro proyecto de código abierto, TFHE, que también vale la pena mencionar. TFHE se basa en el sistema GSW, con varias optimizaciones y aceleraciones agregadas, y ahora es muy famoso.
Además de desarrollar bibliotecas tradicionales totalmente homomórficas, muchos equipos también están estudiando cómo acelerar mejor el cálculo de algoritmos de cifrado totalmente homomórficos a través de hardware heterogéneo como GPU, FPGA y ASIC. Por ejemplo, cuFHE es un conocido sistema de cifrado totalmente homomórfico acelerado por GPU basado en CUDA.
Desde la perspectiva actual, han pasado 11 años desde que Gentry llamó a la puerta del sistema totalmente homomórfico. Hoy en día, la investigación sobre FHE está en auge en la industria y muchas personas están estudiando sistemas totalmente homomórficos desde diferentes perspectivas y requisitos de aplicación. Hasta hoy, ya contamos con una variedad de métodos de implementación FHE factibles, pero lo que todos siguen persiguiendo es la eficiencia del funcionamiento del sistema FHE. Tomando como ejemplo la biblioteca FHE de vanguardia actual, calcular homomórficamente alguna lógica relativamente simple en una plataforma móvil puede tomar tan solo decenas de milisegundos y hasta decenas de segundos. Estas unidades de tiempo son extremadamente lentas para los sistemas informáticos.
Cómo hacer que el sistema FHE funcione de manera más eficiente en plataformas heterogéneas sigue siendo un misterio sin resolver. Si este problema se resuelve una vez, convertir todos los cálculos informáticos a completamente homomórficos y hacer que los agentes realicen cálculos en nubes de terceros será un futuro fácil.
La relación entre FHE y MPC
Antes de finalizar el artículo, me gustaría añadir unas palabras sobre la relación entre FHE y MPC. MPC significa Computación Multipartita Segura, que es computación multipartita confiable. Por lo general, significa que varias partes tienen sus propios datos privados y no quieren revelarlos a otros, pero quieren utilizar sus propios datos para calcular una función F juntos y compartir los resultados del cálculo.
MPC es en realidad un campo muy conocido y estudiado durante mucho tiempo. Desde que el criptógrafo Yao Qizhi lanzó sus Circuitos confusos en el siglo pasado, el campo de MPC ha ganado un amplio reconocimiento y se han producido muchos avances. Ahora ya tenemos muchas bibliotecas MPC que se pueden usar y también tienen cierta eficiencia operativa.
Los amigos que conocen MPC pueden tener muchas preguntas después de ver la difícil historia de los sistemas de cifrado totalmente homomórficos: ¿Por qué no se puede reemplazar directamente el cifrado totalmente homomórfico por un protocolo MPC?
De hecho, un protocolo MPC puede sustituir completamente a un protocolo FHE. Solo necesitamos usar el usuario y la entrada privada como parte en un protocolo, y luego usar el servidor de computación proxy remoto como otra parte, que cumple con las condiciones para la ejecución del protocolo MPC. Solo a través de ciertas interacciones, la computación proxy puede ser realizado Y el servidor no puede ver la entrada privada.
Pero hay un punto muy importante que hemos pasado por alto: dado que MPC es interactivo, el usuario y el servidor necesitan calcular y comunicarse juntos para completar el protocolo. Esto entra en conflicto con el requisito más fundamental de la informática de agentes FHE. Si el usuario necesita permanecer en línea todo el tiempo para completar el acuerdo y también pagar parte de la potencia informática, entonces, de hecho, el cálculo no es "proxy" en absoluto y ambas partes solo hacen más cálculos por el bien de la seguridad de la información. . Esto también explica por qué el campo de MPC ha logrado grandes avances, pero el campo de FHE aún es desconocido, porque los dos sistemas resuelven problemas completamente diferentes.
Al ver esto, todos deben tener un conocimiento muy profundo del sistema de cifrado totalmente homomórfico.
En la siguiente parada, podemos aprender sobre el sistema de cifrado totalmente homomórfico GSW mencionado anteriormente. Aunque esta es la tercera generación de sistemas totalmente homomórficos, creo que entre los tres sistemas de Gentry09, BGV y GSW, GSW es el que tiene menos suposiciones, la estructura más simple y el más fácil de entender. Y ahora hay muchas bibliotecas de código abierto (como TFHE) creadas en base al sistema GSW.
Por razones de espacio, finalizaremos este artículo aquí. En el próximo artículo, primero aprenderemos los conceptos básicos del sistema GSW: el sistema de cifrado basado en celosía y el problema LWE. Una vez que se comprende el problema de LWE, el problema que resuelve GSW queda muy claro.