HEAAN ( Cifrado homomórfico para aritmética de números aproximados ) es una biblioteca de cifrado homomórfico (HE) de código abierto que implementa un esquema HE aproximado propuesto por Cheon , Kim, Kim y Song (CKKS). [1] La primera versión de HEAAN se publicó en GitHub [2] el 15 de mayo de 2016, y más tarde se lanzó una nueva versión de HEAAN con un algoritmo de arranque [3] . Actualmente, la última versión es la versión 2.1.
Espacio de texto sin formato CKKS
A diferencia de otros esquemas HE, el esquema CKKS admite aritmética aproximada sobre números complejos (por lo tanto, números reales). Más precisamente, el espacio de texto plano del esquema CKKS es para algún entero de potencia de dos . Para lidiar con el vector complejo de texto plano de manera eficiente, Cheon et al. métodos propuestos de codificación / decodificación de texto plano que explotan un isomorfismo de anillo.
Método de codificación
Dado un vector de texto plano y un factor de escala , el vector de texto plano se codifica como un polinomio por computación dónde denota la función de redondeo de coeficientes.
Método de decodificación
Dado un polinomio de mensaje y un factor de escala , el polinomio del mensaje se decodifica en un vector complejo por computación .
Aquí el factor de escala nos permite controlar el error de codificación / decodificación que se produce por el proceso de redondeo. Es decir, se puede obtener la ecuación aproximada controlando dónde y denotan el algoritmo de codificación y decodificación, respectivamente.
De la propiedad isomorfa del anillo del mapeo , por y , la siguiente retención:
- ,
- ,
dónde denota el producto de Hadamard de los vectores de la misma longitud. Estas propiedades garantizan la exactitud aproximada de los cálculos en el estado codificado cuando el factor de escala se elige apropiadamente.
Algoritmos
El esquema CKKS consiste básicamente en esos algoritmos: generación de claves, cifrado, descifrado, suma y multiplicación homomórfica y cambio de escala. Para un entero positivo, dejar ser el anillo cociente de modulo . Dejar, y ser distribuciones sobre que generan polinomios con coeficientes pequeños. Estas distribuciones, el módulo inicialy la dimensión del anillo están predeterminados antes de la fase de generación de claves.
Generación de claves
El algoritmo de generación de claves es el siguiente:
- Muestra un polinomio secreto .
- Muestra (resp. ) uniforme al azar de (resp. ), y .
- Generar una clave secreta , una clave pública y una clave de evaluación .
Cifrado
El algoritmo de cifrado es el siguiente:
- Muestra un polinomio secreto efímero .
- Para un polinomio de mensaje dado , generar un texto cifrado .
Descifrado
El algoritmo de descifrado es el siguiente:
- Para un texto cifrado dado , enviar un mensaje .
El descifrado genera un valor aproximado del mensaje original, es decir, , y el error de aproximación está determinado por la elección de distribuciones . Al considerar operaciones homomórficas, los errores de evaluación también se incluyen en el error de aproximación. Las operaciones homomórficas básicas, suma y multiplicación, se realizan de la siguiente manera.
Adición homomórfica
El algoritmo de adición homomórfica es el siguiente:
- Dados dos textos cifrados y en , producción .
La exactitud se mantiene como .
Multiplicación homomórfica
El algoritmo de multiplicación homomórfica es el siguiente:
- Dado dos texto cifrado y en , calcular . Producción.
La exactitud se mantiene como .
Tenga en cuenta que el error de aproximación (en el mensaje) crece exponencialmente en el número de multiplicaciones homomórficas. Para superar este problema, la mayoría de los esquemas HE suelen utilizar una técnica de conmutación de módulo que fue introducida por Brakerski, Gentry y Vaikuntanathan. [4] En el caso de HEAAN, el procedimiento de cambio de módulo se denomina reescalado. El algoritmo de cambio de escala es muy simple en comparación con el algoritmo original de Brakerski-Gentry-Vaikuntanathan. Al aplicar el algoritmo de cambio de escala después de una multiplicación homomomórfica, el error de aproximación crece linealmente, no exponencialmente.
Reescalado
El algoritmo de cambio de escala es el siguiente:
- Dado un texto cifrado y un nuevo módulo , generar un texto cifrado reescalado .
El procedimiento total del esquema CKKS es el siguiente: Cada vector de texto plano que consta de números complejos (o reales) se codifica en primer lugar como un polinomio por el método de codificación, y luego encriptado como un texto cifrado . Después de varias operaciones homomórficas, el texto cifrado resultante se descifra como un polinomio y luego decodificado como un vector de texto sin formato que es el resultado final.
Seguridad
La seguridad IND-CPA del esquema CKKS se basa en la suposición de dureza del problema de aprendizaje de anillo con errores (RLWE), la variante de anillo del muy prometedor problema duro basado en celosía Aprendizaje con errores (LWE). Actualmente, los ataques más conocidos para RLWE sobre un anillo ciclotómico de potencia de dos son los ataques LWE generales, como el ataque dual y el ataque primario. La seguridad de bits del esquema CKKS basado en ataques conocidos fue estimada por el estimador LWE de Albrecht. [5]
Biblioteca
Hasta ahora se han publicado las versiones 1.0, 1.1 y 2.1. La versión 1.0 es la primera implementación del esquema CKKS sin bootstrapping. En la segunda versión, se adjuntó el algoritmo de arranque para que los usuarios puedan abordar cálculos homomórficos a gran escala. En la versión 2.1, actualmente la última versión, la multiplicación de elementos de anillo ense aceleró utilizando la transformación rápida de Fourier (FFT) - implementación de la transformación teórica de números optimizada (NTT).
Referencias
- ^ Cheon, Jung Hee; Kim, Andrey; Kim, Miran; Song, Yongsoo (2017). "Cifrado homomórfico para aritmética de números aproximados". Takagi T., Peyrin T. (eds) Avances en criptología - ASIACRYPT 2017 . ASIACRYPT 2017. Springer, Cham. págs. 409–437. doi : 10.1007 / 978-3-319-70694-8_15 .
- ^ Andrey Kim; Kyoohyung Han; Miran Kim; Canción de Yongsoo. "Una biblioteca HE aproximado HEAAN" . Consultado el 15 de mayo de 2016 .
- ^ Jung Hee Cheon , Kyoohyung Han, Andrey Kim, Miran Kim y Yongsoo Song. Bootstrapping para cifrado homomórfico aproximado . En EUROCRYPT 2018 (springer) .
- ^ Z. Brakerski, C. Gentry y V. Vaikuntanathan. Cifrado totalmente homomórfico sin Bootstrapping . En ITCS 2012
- ^ Martin Albrecht. Estimaciones de seguridad para el problema del aprendizaje con errores, https://bitbucket.org/malb/lwe-estimator