Compartir tecnología

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Recursos de aprendizaje:
Cifrado totalmente homomórfico I: teoría y fundamento (Profesor Yu Yu de la Universidad Jiao Tong de Shanghai)
Cifrado totalmente homomórfico II: teoría y construcción del cifrado totalmente homomórfico (Profesor Xiang Xie)

---

Hoy en día, los esquemas de cifrado totalmente homomórficos de segunda generación (como BGV y BFV) y de tercera generación se basan en LWE. Ahora los esquemas avanzados totalmente homomórficos también se basan en LWE, por lo que este artículo resume el conocimiento básico de LWE.
Primero considere, queremos cifrar un número$s$, ahora usando una serie de$a_i$bien$s$Cifrar y obtener$a_{i}s$, de hecho, se puede resolver resolviendo el máximo común divisor MCD$s$ .Sin embargo, si se agrega un ruido aleatorio${mi}_i$,conseguir$a_{i}s+{mi}_i$, entonces será difícil de resolver$s$ valor. Este proceso es mi simple comprensión de LWE. El llamado error es un ruido.

El proceso de cálculo del cifrado totalmente homomórfico se divide en tres pasos: generación de claves KeyGen, cifrado Enc, cálculo homomórfico Eval y descifrado Dec. ,

Generación de claves:

Primero construya la ecuación anterior,$s\cdot A+mi=sA+mi$y luego obtener la clave pública pk ($-A$y$sA+mi$empalme), y la clave privada sk ($s$ y 1 empalme). Por tanto, se obtiene que el resultado de la multiplicación entre pk y sk es el ruido aleatorio e (cercano a 0).

Enc：

La clave pública pk utilizada para el cifrado, r es un vector aleatorio que contiene solo 0 o 1, y m es la información que se va a cifrar (colocada en el bit más bajo del vector).

Dic:

Después de calcular el producto interno de la clave privada sk utilizada para el descifrado y ct, busque el mod 2 para obtener el resultado del descifrado.

Prueba de corrección:

Multiplique sk y pk para obtener 2e (la condición que cumple KeyGen) y luego haga el producto interno con r para obtener un ruido pequeño y uniforme. El resultado final es m+ un ruido pequeño y uniforme, por lo que el ruido puede eliminarse con el mod 2. Obtenga el resultado del descifrado m. Es por eso que el ruido construido es 2e, no e. Tengo entendido que al construir un ruido aleatorio par, es conveniente usar el mod 2 para eliminar el ruido durante el descifrado.

Prueba de seguridad:

Cuando pk es pseudoaleatorio y r tiene una entropía suficientemente alta (es decir, ¿la aleatoriedad es fuerte?), tanto pk como pk multiplicado por r son pseudoaleatorios. Después de agregar vectores naturales y con m, el resultado del cifrado también es pseudoaleatorio.

La siguiente es la descripción formulada del maestro Xiang Xie:
Fórmula de cifrado: texto cifrado c = clave pública pk ✖️ aleatorio r + texto sin formato m
Fórmula de descifrado: texto plano m = <texto cifrado sk, clave privada sk> mod q mod 2

Sobre esta base, el mod 2 se puede utilizar para descifrar el valor del texto sin formato m. Siempre que el ruido sea lo suficientemente pequeño, se puede garantizar la precisión.
Hay algo que es necesario distinguir aquí: lo anterior$PAGAGK=(A,b=A{s}^{\prime }+2mi)$es la solución BGV y BFV es$PAGAGK=(A,b=A{s}^{\prime }+mi)$, la diferencia es que BGV codifica información en bits bajos, mientras que BFV codifica mensajes en bits altos (se explicará cuando aprenda BFV).

Eval (homomorfismo aditivo y homomorfismo multiplicativo):

Tenga en cuenta que la suma o multiplicación homomórfica generará una acumulación significativa de ruido y la multiplicación tiene una tendencia de crecimiento cuadrático.
Luego hablemos de cómo descifrar el resultado de la multiplicación homomórfica. Puede ver la siguiente fórmula: La multiplicación de dos textos cifrados equivale a hacer el producto tensorial del texto cifrado y la clave privada respectivamente, y luego hacer el producto interno. Obviamente, tanto el texto cifrado como la clave privada han duplicado su tamaño. El ejemplo es una prueba de equivalencia.

Entonces la pregunta es, ¿cómo restaurar el tamaño del texto cifrado y el tamaño de la clave privada después de la multiplicación homomórfica? Este es el problema que resuelve el cambio de clave.

La siguiente es la descripción del maestro Xiang Xie:

Cambio de clave

El objetivo es restaurar el tamaño del texto cifrado y la clave privada a un tamaño lineal.

Ahora encuentre la multiplicación de los textos cifrados c1 y c2:

El proceso anterior se basa en el concepto de descomposición de bits:

La siguiente es la descripción del maestro Xiang Xie:

El objetivo del cambio de clave: convertir la clave privada$\tilde{s}$abajo$\tilde{C}$ Convertir a clave privada$s$abajo$C$,y$\tilde{C}$y$C$Todos están cifrados con el mismo texto sin formato.
Un concepto central aquí es la clave de cambio de clave (KSK), que significa usar una clave privada.$s$cifrar$\tilde{s}$。

A través del proceso de cambio de clave, la clave privada se puede derivar de$s\otimes s$se volvió lineal$s$, mientras que el texto cifrado cambia de$\tilde{C}$se volvió lineal$C$ .Y se puede ver en la última línea de la fórmula que después del cambio de clave$⟨C,s⟩$y el original$⟨\tilde{C},s\otimes s⟩$Hay una diferencia de ruido entre$2{\tilde{C}}^{yo}\widetilde{mi}$ ¡Esta parte puede ser muy grande! Por lo tanto, todavía no hay forma de implementar el cambio de clave aquí.

Aquí se presenta una matriz de gadget G:

Por lo tanto, el proceso de cambio de clave queda como sigue:

En este punto, el error añadido es muy pequeño.
En resumen, a través del cambio de clave, la clave privada original$\tilde{s}=s\otimes s$abajo$\tilde{C}=C\otimes C$, se convierte en una clave privada$s$abajo$C$, preste atención a la clave después del cambio de clave$s,C$No son los valores originales (nueva verificación).

Para BGV, el ruido de la suma aumenta linealmente y el ruido de la multiplicación aumenta al cuadrado. Aunque el cambio de clave puede admitir la multiplicación (limitando sk para que sea extremadamente grande), el ruido es en realidad un ruido muy pequeño agregado al ruido de multiplicación original. también es muy grande. Por lo tanto, es necesario reducir aún más este ruido.

Reducción del módulo

Hasta ahora, los cálculos homomórficos de multiplicación y suma con una pequeña profundidad se han implementado a través de LWE. El cambio de clave utiliza una nueva clave para cada capa. Sin embargo, a medida que la profundidad del cálculo se profundiza, la expansión del ruido es explosiva, por lo que aún no está nivelada. FHE (puede calcular FHE a una profundidad específica).
Ahora esperamos implementar un FHE que pueda calcular una cierta profundidad sin usar bootstrapping, lo que requiere conversión de módulo.

No entiendo muy bien el proceso intermedio. En resumen, se trata de transformar el texto cifrado c del módulo de dominio q al módulo de dominio p (p <).
Aquí hay un ejemplo específico:
Si no se realiza la reducción del módulo, el ruido crecerá en una tendencia exponencial doble a medida que la profundidad se profundiza y se producirán errores de descifrado después del nivel >= 3.

Si se realiza la reducción del módulo en cada nivel, el ruido también se mantendrá dentro de un rango de valores absolutos, a costa de una reducción continua del módulo.

Entonces, si desea implementar un FHE nivelado, puede establecer un módulo$B^d$, entonces puedes calcular una profundidad de$d$circuito (donde$B$ es el límite superior de ruido del texto cifrado actualizado).Calculado$d$Después de la profundidad, el módulo debe reducirse a$B$ , para garantizar que no haya ningún error al descifrar en este momento. BGV es un FHE nivelado.