Criptosistema Gentry

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 19 de diciembre de 2017; las comprobaciones requieren 78 ediciones .

El criptosistema Gentry (del apellido del creador Craig Gentry) es la primera construcción posible para un criptosistema completamente homomórfico basado en criptografía de celosía . Fue propuesto por primera vez por Craig Gentry en 2009 [1] y fue el tema de su tesis doctoral. El esquema Gentry admite operaciones de suma y multiplicación en texto cifrado, lo que le permite crear anillos para implementar cualquier cálculo arbitrario. Posteriormente, tuvo muchas mejoras y modificaciones con el fin de mejorar su rendimiento.

Descripción del algoritmo

El esquema utiliza [2] celosías ideales J en cadenas de polinomios módulo . La forma normal hermítica de una red ideal tiene la forma [2] : $f_{n}(x)=x^{n}+1$

$HNF(J)=\quad \left[{\begin{array}{ccccc}d&0&0&0&0\\-r&1&0&0&0\\-[r^{2}]_{d}&0&1&0&0\\-[r^{2 }]_{d}&0&0&0&0\\\vpuntos &&&\dpuntos &\\-[r^{n-1}]_{d}&0&0&0&1\end{matriz}}\right]$ , donde yr es la raíz del módulo d. ${\ estilo de visualización d = det (J)}$ $f_{n}(x)$

Generación de claves [2]

Se elige un enrejado entero arbitrario n-dimensional v, donde cada entrada se elige aleatoriamente como un número de t bits. Con este vector v, se define formalmente el polinomio , así como la matriz de rotación correspondiente: $v_{i}$ ${\displaystyle v(x)=\sum_{i\mahop {=} 0}^{n-1}v_{i}x^{i))$

$V=\quad \left[{\begin{matriz}{ccccc}v_{0}&v_{1}&v_{2}&&v_{n-1}\\-v_{n-1}&v_{0} &v_{1}&&v_{n-2}\\-v_{n-2}&v_{n-1}&v_{0}&&v_{n-3}\\&&&\dpuntos &\\-v_{1}&- v_{2}&-v_{3}&&v_{0}\end{matriz}}\right]$

El inverso de se calcula módulo , es decir, un polinomio de grado como máximo n-1, que es . Entonces la matriz $v(x)$ $f_{n}(x)$ $w(x)$ $v(x)*w(x)=const{\bmod {f}}_{n}(x)$

$W=\quad \left[{\begin{matriz}{ccccc}w_{0}&w_{1}&w_{2}&&w_{n-1}\\-w_{n-1}&w_{0} &w_{1}&&w_{n-2}\\-w_{n-2}&w_{n-1}&w_{0}&&w_{n-3}\\&&&\dpuntos &\\-w_{1}&- w_{2}&-w_{3}&&w_{0}\end{matriz}}\right]$

es la inversa de , es decir , donde es la matriz identidad. $V$ $V*W=const*I$ $yo$

También se verifica que la forma normal hermitiana para tiene la forma indicada anteriormente, es decir, todas las columnas excepto la de la izquierda forman la matriz identidad. En este caso, la matriz completa se puede obtener usando los elementos r y d. $V$ $V$

La clave pública será la matriz dada por los números r y d. La clave privada serán dos polinomios . $V$ $(v,w)$

Cifrado [2]

Que sea necesario cifrar un poco ${\ estilo de visualización {m \ en (0,1)))$

En la entrada está el bit b y la clave pública V. Se elige el vector de ruido cuyas componentes toman valores 0,1,-1. Luego se calcula el vector y el texto cifrado se calcula mediante la fórmula [2] $tu$ ${\ estilo de visualización a = 2 * u + b * e_ {1))$ $c=a{\bmod {V}}=a-([a*V^{-1}]*V)$

Aquí, para una base V del espacio L y un vector c dado, la expresión se usa para denotar un vector tal que [2] $c{\bmod {V}}$ $c'\in P(V)$ $cc'\in L$

Descifrado [2]

La entrada tiene un vector C y matrices V y W. El bit original b se obtiene como resultado de la operación:

$b=a{\bmod {2}}=(c{\bmod {V}}){\bmod {2}}=(c*(W/d)){\bmod {2}}$

Homomorfismo [2]

El cifrado es homomórfico con respecto a las operaciones de suma y multiplicación. Para realizar sumas o multiplicaciones de textos cifrados, es necesario realizar estas operaciones en la base V

Resistencia [3]

Gentry justificó la seguridad de su esquema con dos problemas: el problema de la complejidad del peor caso de criptografía en redes ideales y el problema de la suma de subconjuntos. Ambos problemas son -difíciles, por lo que la estabilidad del sistema se reduce a un problema -difícil. $notario público$ $notario público$

Defectos

Una desventaja significativa de este esquema es que la ejecución de los cálculos conduce a la acumulación de errores [4] y, después de que se excede , se vuelve imposible descifrar el mensaje. Una de las soluciones a este problema es volver a cifrar los datos después de un cierto número de operaciones, sin embargo, esta opción reduce el rendimiento de los cálculos y requiere un acceso constante a la clave secreta [3] . $pags$

Diagrama simplificado de Gentry

Se considera un esquema que es homomórfico con respecto a la operación de suma solamente [4] .

Generación de claves

Se selecciona un número , módulo del cual funcionará el esquema. $norte$
Se elige una clave secreta , un número aleatorio, mucho más grande , tal que gcd $sk$ $norte$ ${(sk,n)=1}$
Se elige una clave pública : un conjunto de números grandes tales que , donde es un número aleatorio pequeño, es un número aleatorio arbitrario. $paquete$ ${\ estilo de visualización [a_{1},..a_{i}]}$ $a_{i}=r*sk+e*n$ $r$ $mi$

Cifrado

La entrada contiene el texto a cifrar y la clave pública. El texto cifrado será la suma de un número arbitrario de elementos de la clave pública y el texto sin formato.

descifrado

La entrada contiene un texto cifrado y números y . El resto de dividir el texto cifrado por y por se calcula secuencialmente . El resultado será el mensaje original. $norte$ $sk$ $norte$ $sk$

homomorfismo

Para obtener la suma de los textos y , basta con sumar los textos cifrados y realizar la operación de descifrado. En realidad: $m_{{1}}$ $m_{{2}}$ ${D(E(m_{1},pk)+E(m_{2},pk))=D(m_{1}+m_{2}+\sum_{i\mahop {=} 0 }^{n}C_{i}pk_{i})=D(m_{1}+m_{2}+C_{1}^{'}sk+C_{2}^{'}n)=m_{ 1}+m_{2}}$

La ventaja de este esquema es la facilidad de implementación y los bajos requerimientos de recursos. Las desventajas incluyen un conjunto finito de claves públicas y solo un homomorfismo parcial.

Implementación de Smart y Wertcauteren

El primer intento de implementar el esquema Gentry fue realizado en 2010 por Smart y Werkauteren [5] . Para la implementación, eligieron un esquema que utiliza celosías ideales para un determinante simple. Tales estructuras están representadas por dos números enteros (independientemente de su tamaño). Smart y Wertkauteren propusieron un método de descifrado en el que la clave secreta es un solo número entero. Así, los científicos lograron implementar un circuito homomórfico homogéneo, pero no pudieron implementar la técnica Gentry en el caso de parámetros suficientemente grandes y, por lo tanto, no lograron obtener un circuito cargable y completamente homomórfico.

El principal obstáculo en esta implementación fue la dificultad de generar claves para esquemas homogéneos: en primer lugar, los esquemas deben generar una gran cantidad de "candidatos" para encontrar una clave para la cual el determinante es simple - hasta candidatos cuando se trabaja con estructuras de dimensión . Además, incluso después de encontrar la variante óptima, la complejidad de calcular la clave secreta correspondiente a esta estructura es igual, al menos para redes de dimensión . Por estas razones, los científicos no han podido generar claves dimensionales . Además, Smart y Vercauteren estimaron que el polinomio de descifrado tendrá un grado de varios cientos, y esto requiere el uso de una red de al menos dimensión para el procedimiento con sus parámetros , lo que supera significativamente las capacidades computacionales del procedimiento de generación de claves [ 2] . ${\ estilo de visualización {n^{1,5))}$ $norte$ ${{\tilde {O}}(n^{2,5}})}$ $norte$ ${\ estilo de visualización {n> 2048}}$ ${\ estilo de visualización {n = 2 ^ {27}}}$ ${\displaystyle {(\aprox. 1,3\times 10^{8)))))$

Esquema completamente homomórfico de Gentry

En 2011, Craig Gentry, junto con Shai Halevi, presentó [2] una implementación práctica para un esquema de cifrado totalmente homomórfico, similar al utilizado en trabajos anteriores por Smart y Wertcauteren. La optimización principal consiste en un método de generación de claves para el cifrado básico relativamente homomórfico que no requiere una inversión polinomial completa. Esto reduce la complejidad asintótica de a cuando se trabaja con redes dimensionales (y en la práctica reduce el tiempo de cálculo de muchas horas a varios minutos). ${{\tilde {O}}(n^{2,5}})}$ ${{\tilde {O}}(n^{1,5}})}$ $norte$

Notas

↑ Craig Gentry. "UN ESQUEMA DE ENCRIPTACIÓN TOTALMENTE HOMOMORFICO" Archivado el 5 de febrero de 2017 en Wayback Machine Una disertación presentada al departamento de informática y al comité de estudiantes graduados de la Universidad de Standford, 2009.
↑ 1 2 3 4 5 6 7 8 9 10 Craig Gentry y Shai Halevi. "Implementación del esquema de cifrado completamente homomórfico de Gentry" Archivado el 22 de diciembre de 2017 en la investigación de Wayback Machine IBM.
↑ 1 2 Trubey I.A. CIFRADO HOMOMORFO: SEGURIDAD DE LA COMPUTACIÓN EN LA NUBE Y OTRAS APLICACIONES (REVISIÓN). Informática. 2015;(1):90-101.
↑ 1 2 Alumyan A.S., Glazunov I.A., Tishin V.V. "Cifrado homomórfico" Archivado el 22 de diciembre de 2017 en el artículo de Wayback Machine para la XXI Conferencia científica y práctica internacional "Comunidad científica de estudiantes: INVESTIGACIÓN INTERDISCIPLINARIA" (Rusia, Novosibirsk, 18 de mayo de 2017)
↑ NP SmartF. Vercauteren. "Cifrado totalmente homomórfico con tamaños de clave y texto cifrado relativamente pequeños" Archivado el 22 de diciembre de 2017 en Wayback Machine , 2010.