# <span style="color:black">Fully Homomorphic Encryption</span>

#### Por Gelois

Fully Homomorphic Encryption (FHE) es una tecnología que permite realizar cálculos sobre datos cifrados, donde solo el propietario de la clave puede descifrar el resultado. Originalmente fue llamada “Privacy Homomorphism” y fue introducida por Rivest, Adleman y Dertouzos en 1978. Fue considerado como el “Santo Grial de la Criptografía” porque nadie había podido hacerlo aplicable, pero en 2009 fue completamente desarrollado por Craig Gentry en su tesis doctoral. Esto permitió el cifrado homomórfico completo al permitir realizar operaciones en datos cifrados, donde solo el propietario de la clave puede descifrar el resultado del cálculo sin conocer los datos originales. Desde entonces, se ha vuelto crucial en el cifrado en la nube y en las capas de procesamiento de nueva generación.

## <span style="color:black">Cómo trabaja las FHE</span>

**Definiciones:**
- **Plaintext:** es el dato en limpio (es decir, datos sin cifrar).
- **Ciphertext:** es el dato encriptado.

**Algoritmos en un esquema de cifrado por llave pública:**

1. **KeyGen(Parámetros_de_seguridad) → llaves:** Este algoritmo recibe ciertos parámetros de seguridad como entrada y luego genera las llaves necesarias para el esquema de cifrado.
2. **Encrypt(Plaintext, llave pública, randomness) → Ciphertext:** El proceso de cifrado utiliza un texto sin cifrar, una clave y una fuente de aleatoriedad (necesaria para asegurar que el cifrado no sea predecible). El resultado es el texto cifrado o encriptado.
3. **Decrypt(Ciphertext, llave privada) → Plaintext:** El algoritmo de descifrado toma como entradas un texto cifrado y una clave. Produce como resultado el texto plano correspondiente.

### Homomorfismo

Es una función entre dos estructuras algebraicas (como grupos, anillos, o espacios vectoriales) que preserva la operación de la estructura. En otras palabras, un homomorfismo mantiene la relación entre los elementos de las dos estructuras.

**Homomorfismos en Grupos:** si $(G, ∗)$ y $(H, ⋅)$ son dos grupos, una función f: $G → H$ se llama homomorfismo si para todos los elementos $a, b ∈ G$ se cumple que:
$$f(a ∗ b) = f(a) ⋅ f(b)$$
Esto significa que la operación ∗ en el grupo G se preserva a través de la función f al ser transformada en la operación ⋅ en el grupo H.

**Homomorfismos de Anillos:** para anillos, que tienen dos operaciones (suma y multiplicación), un homomorfismo f entre dos anillos $(R, +, ⋅)$ y $(S, ⊕, ⊗)$ debe cumplir:
- **Preservación de la suma:**
$$f(a + b) = f(a) ⊕ f(b)$$
- **Preservación de la multiplicación:**
$$f(a ⋅ b) = f(a) ⊗ f(b)$$

Gracias a esta relación, se permiten cálculos en el espacio del Plaintext y el espacio del Ciphertext.

### Cifrado homomórfico

**Propiedades Homomórficas:**
Para dos valores \( x \) y \( y \):

- **Suma:**
$$\text{Encrypt}(x) + \text{Encrypt}(y) = \text{Encrypt}(x + y)$$

- **Multiplicación:**
$$\text{Encrypt}(x) \cdot \text{Encrypt}(y) = \text{Encrypt}(x \cdot y)$$

**Ejemplo Práctico:**
Supongamos que tenemos los siguientes valores:
\( x = 5 \)
\( y = 10 \)

Si aplicamos el cifrado:
- $\text{Encrypt}(5)$ podría ser, por ejemplo, un número cifrado $E(x)$.
- $\text{Encrypt}(10)$ sería otro número cifrado $E(y)$.

**Realizando Cálculos Cifrados:**
- Al aplicar la operación de suma sobre los valores cifrados:
$$E(5) + E(10) = E(15)$$

- Al aplicar la operación de multiplicación:
$$E(5) \cdot E(10) = E(50)$$

Al descifrar los resultados, obtendremos los mismos valores que si hubiéramos realizado las operaciones en los números originales.

## Learning With Errors (LWE)

La seguridad del LWE se basa en la dificultad (provablemente reducible) de resolver el **Problema del Vector Más Corto (SVP)** en una red. Introducido por Oded Regev en 2005, el LWE se centra en la dificultad de encontrar los valores que resuelven la ecuación:

$$ B = A \cdot s + e $$

donde:
- **A** y **B** son conocidos,
- **s** es el mensaje secreto,
- **e** es un error aleatorio (ruido).

La introducción de este error aleatorio **e** (llamado ruido) hace que la ecuación sea difícil de resolver. Cuando hay mucho ruido, las operaciones de suma y multiplicación se complican y pueden introducir errores en estas operaciones.

### La Definición de LWE

Llamamos $X_\sigma$ a la distribución gaussiana redondeada sobre $\mathbb{Z}_q$. Cuando escribimos $e_i \leftarrow X_\sigma$, esto significa que $e_i$ es extraído según la distribución $X_\sigma$. Dicho de otra manera, extraemos $e_i$ en $\mathbb{Z}_q$ tal que:

$$
Pr(e_i = x) = \left( x - \frac{1}{2} \right) x + \frac{1}{2} f_{\sigma,q}(x) \, dx
$$

También extraemos los vectores $a_i$ al azar, pero con la distribución uniforme.

**El problema LWE**: Sea $q > 0$ un módulo, $m, n > 0$ enteros, $\sigma$ una desviación estándar, y $\chi_\sigma$ la distribución gaussiana redondeada sobre $\mathbb{Z}_q$ con desviación estándar $\sigma$. Dados \(m\) muestras de la forma

$$
(a_i, \langle a_i, s \rangle + e_i),
$$

donde $a_i$ se distribuye uniformemente al azar en $\mathbb{Z}_q^n$ y $e_i \leftarrow \chi_\sigma$, el objetivo es encontrar el secreto $s \in \mathbb{Z}_q^n$.

### Esquema de Cifrado con Clave Secreta

Utilizaremos el estándar para el cifrado con clave secreta es el AES. Para Presentar este cifrado basado en LWE (Learning With Errors) solo como un paso preliminar hacia el esquema de cifrado público LWE completamente desarrollado.

### Parámetros

Los parámetros públicos del esquema son $n > 0$, $q > 0$, y la distribución de errores $\chi_\sigma$. Requerimos que $\sigma$ sea lo suficientemente pequeño con respecto a $q$ para asegurar que $\Pr(|e_i| \leq q/4)$ sea alto. La clave secreta es un vector $s \in \mathbb{Z}^n_q$.

### Cifrado

Asumimos que queremos cifrar un mensaje $\mu \in \{0, 1\}$ (es decir, un solo bit). Los mensajes más largos deben descomponerse en bits que se cifran uno por uno. Los pasos para el cifrado son los siguientes:

1. **Dibujar** $a \in \mathbb{Z}^n_q$ de manera uniforme al azar. Lo cual se genera un vector $a$ aleatorio de $\mathbb{Z}^n_q$.

2. **Dibujar** $e \leftarrow \chi_\sigma$. Donde se elige un errr $e$ em la distribucción de $\chi_\sigma$
3. **Devuelve** $$c = (a, \langle a, s \rangle + e + \mu \cdot \left\lfloor \frac{q}{2} \right\rfloor),$$ donde $\langle x \rangle$ es el redondeo de $x \in \mathbb{R}$ al entero más cercano.

- $a$: Un vector aleatorio que se usa para ocultar la clave secreta s.
- $⟨a, s⟩$: Producto interno de a y s, ofusca la clave secreta.
- $e$: Un pequeño error aleatorio que añade ruido, crucial para la seguridad.
- $µ · ⌊q/2⌋$: Representa el mensaje (0 o 1), sumando un valor grande si µ = 1, para diferenciar los bits cifrados.

### Descifrado

Supongamos que hemos recibido $c = (a, b)$. Con el conocimiento de $s$, podemos realizar la operación:
$$
b - \langle a, s \rangle = e + \mu \cdot \left\lfloor \frac{q}{2} \right\rfloor.
$$

Dado que solicitamos que $|e| \leq q/4$ con alta probabilidad, sabemos que:

- Si $\mu = 0 \), \( e + \mu \cdot \left\lfloor \frac{q}{2} \right\rfloor$ es menor que $q/4$ con alta probabilidad. El resultado es pequeño, cercano a 0.
- Si $\mu = 1 \), \( e + \mu \cdot \left\lfloor \frac{q}{2} \right\rfloor$ es mayor que $q/4$ con alta probabilidad. El resultado es grande, cercano a q/2

Ejemplo:

### Parámetros

- $q = 5$
- $n = 3$
- Clave secreta $s = (1, 0, 1)$
- Mensaje $\mu = 0$
- Vector $a = (2, 4, 1)$
- Error $e = 1$

### 1. **Cifrado (Encryption)**

El ciphertext es $c = ((2, 4, 1), 4)$. Aquí está el desglose:

$$
\langle a, s \rangle + e + \mu \cdot \left\lfloor \frac{q}{2} \right\rfloor = 2 \cdot 1 + 4 \cdot 0 + 1 \cdot 1 + 1 + 0 \cdot 2 = 2 + 0 + 1 + 1 = 4
$$

Por lo tanto, el ciphertext es:

$$
c = ((2, 4, 1), 4)
$$

### 2. **Descifrado (Decryption)**

Recibimos el ciphertext $c = ((2, 4, 1), 4)$.

1. **Producto interno $\langle a, s \rangle$:**

$$
\langle (2, 4, 1), (1, 0, 1) \rangle = 2 \cdot 1 + 4 \cdot 0 + 1 \cdot 1 = 2 + 0 + 1 = 3
$$

2. **Restamos el valor $4$ recibido en el ciphertext:**

$$
b - \langle a, s \rangle = 4 - 3 = 1
$$

3. **Comparamos el resultado con $\left\lfloor \frac{q}{2} \right\rfloor = \left\lfloor \frac{5}{2} \right\rfloor = 2$:**

- Si $|b - \langle a, s \rangle| < 2$, el mensaje es $\mu = 0$.
- Si $|b - \langle a, s \rangle| \geq 2$, el mensaje es $\mu = 1$.

En este caso:

$$
|1| < 2
$$

Por lo tanto, el mensaje original es $\mu = 0$.

### Conclusión

El mensaje descifrado es $\mu = 0$.

### Hacia el cifrado de clave pública desde LWE

Para convertir el esquema de cifrado de clave secreta en un esquema de clave pública, se aprovecha la linealidad de los cifrados. Considera los siguientes cifrados de $\mu = 0$:

- $c1 = (a1, \langle a1, s \rangle + e1)$
- $c2 = (a2, \langle a2, s \rangle + e2)$

La suma de estos dos cifrados es:

$$
c1 + c2 = (a1 + a2, \langle a1, s \rangle + \langle a2, s \rangle + e1 + e2) = (a1 + a2, \langle a1 + a2, s \rangle + e1 + e2)
$$

Aquí, $a = a1 + a2$ y $e = e1 + e2$. Si el error $e$ sigue cumpliendo que $|e| \leq \frac{q}{4}$ con alta probabilidad, el procedimiento de descifrado será correcto con alta probabilidad. Para cifrar $\mu = 1$, se añade $\left\lfloor \frac{q}{2} \right\rfloor$ al segundo componente del cifrado.

Para producir $m$ cifrados de $\mu = 0$, se muestrean vectores $a_i$ y errores $e_i$ aleatoriamente. La suma de estos cifrados sigue siendo un cifrado de $\mu = 0$.

La clave pública se compone de la matriz $A$ cuyas filas son los vectores $a_i$, y el vector $b$ donde $b_i = \langle a_i, s \rangle + e_i$. La clave privada para el descifrado sigue siendo $s$ como en el esquema de clave secreta.

Para cifrar un mensaje usando múltiples cifrados de $\mu = 0$, se usa:

$$
(x \cdot A, \langle x, b \rangle)
$$

donde $x$ es un vector de bits que indica qué cifrados de $\mu = 0$ se deben sumar. Si $|e| \leq \frac{q}{4m}$, el descifrado será exitoso con alta probabilidad. Esto garantiza que la suma de hasta $m$ errores $e_i$ tendrá un valor absoluto menor a $\frac{q}{4}$.

## Manejando el Ruido

El diagrama a continuación representa una encriptación, donde cada componente puede expresarse como un coeficiente en un polinomio o un vector. La altura del elemento representa el tamaño de los coeficientes. Nota que en el primer paso, el ruido inicial es pequeño.


A medida que aumenta el número de cálculos (operaciones), vemos un crecimiento correspondiente en el ruido. El crecimiento en el ruido puede describirse como exponencial, polinómico, lineal, constante o logarítmico.


A medida que aumenta el número de cálculos (operaciones), vemos un crecimiento correspondiente en el ruido. El crecimiento en el ruido puede describirse como exponencial, polinómico, lineal, constante o logarítmico.


### Tipos de manejo de ruido

Las técnicas de gestión de ruido en FHE buscan controlar o reducir el nivel de ruido para mantener la corrección de los cálculos. Los principales tipos de gestión de ruido incluyen:

- **Bootstrapping:** Mantiene la corrección de los cálculos en datos encriptados al reducir el impacto del ruido acumulado.

- **Modulous Switching:** Gestión ligera del ruido sin uso de clave secreta, reescalando ciphertexts. Es más efectivo cuando se aplica después de cada multiplicación homomórfica.

- **Batching:** Aumenta la eficiencia al empaquetar múltiples textos en claro en el mismo ciphertext para que FHE pueda realizarse en múltiples entradas.

### Bootstrapping


El bootstrapping es una técnica que implica ejecutar el procedimiento de descifrado de manera homomórfica sin revelar el mensaje y utilizando la clave secreta cifrada. Para entender cómo es posible, es importante tener en cuenta que podemos producir una serie de puertas XOR y AND (o sumas y multiplicaciones) que realizan la operación de descifrado.

### Modelos de Cálculo Homomórfico

Para diseñar cálculos de Cifrado Homomórfico (HE), es importante elegir el enfoque adecuado según las características requeridas:

1. **Circuitos Booleanos**
- **Características:**
- Comparación rápida de números.
- Soporte para circuitos booleanos arbitrarios.
- Arranque rápido (procedimiento de refresco de ruido).
- **Esquemas Seleccionados:**
- Gentry-Sahai-Waters (GSW)
- Fastest Homomorphic Encryption in the West (FHEW)
- Fast Fully Homomorphic Encryption over the Torus (TFHE)

2. **Aritmética Modular (Exacta)**
- **Características:**
- Cálculos SIMD eficientes sobre vectores de enteros (usando batching).
- Aritmética de enteros de alta precisión rápida.
- Multiplicación escalar rápida.
- Diseño por niveles (frecuentemente usado sin arranque).
- **Esquemas Seleccionados:**
- Brakerski-Vaikuntanathan (BV)
- Brakerski-Gentry-Vaikuntanathan (BGV)
- Brakerski/Fan-Vercauteren (BFV)

3. **Aritmética de Números Aproximados**
- **Características:**
- Aproximación polinómica rápida.
- Inverso multiplicativo y Transformada Discreta de Fourier relativamente rápidos.
- Cálculos aproximados profundos, como aprendizaje de regresión logística.
- Cálculos SIMD eficientes sobre vectores de números reales (usando batching).
- Diseño por niveles (frecuentemente usado sin arranque).
- **Esquemas Seleccionados:**
- Cheon-Kim-Kim-Song (CKKS)

### Esquemas de Encriptación Homomórfica Completa (FHE)

- **BGV y BFV:** Los esquemas BGV (2011) y BFV (2012) mejoraron el rendimiento al introducir el concepto de Learning With Errors (LWE). BGV redujo el tiempo de operación de minutos a segundos, mientras que BFV utilizó anillos polinomiales (Ring-LWE) en lugar de ecuaciones lineales. Son adecuados para aplicaciones de recuperación de información y consultas de bases de datos.

- **TFHE:** La Encriptación Homomórfica Completa sobre el Torus (TFHE) (2016) mejoró el bootstrapping con una tabla de búsqueda, reduciendo los tiempos de segundos a milisegundos. Aunque originalmente solo soportaba circuitos booleanos, versiones como TFHErs permiten bootstrapping sobre enteros, siendo adecuada para cálculos generales.

- **CKKS:** CKKS (2016) es ideal para trabajar con números reales en problemas de aprendizaje automático, regresiones y cálculos estadísticos. Maneja aritmética aproximada, lo que lo hace menos adecuado para aplicaciones que requieren precisión financiera.


## Aplicaciones Evidentes de FHE

1. **Tokens ERC20 Confidenciales**
- **Descripción:** FHE se usa para mantener ocultos los saldos de tokens, permitiendo que solo el titular vea su propio balance.
- **Proceso:**
- Cifra la cantidad transferida.
- Verifica el saldo del remitente.
- Ejecuta la transferencia en la cadena.
- **Ejemplo:** Implementaciones de Zama y Fhenix.

2. **Emparejamiento de Órdenes en Pools**
- **Descripción:** Los traders envían órdenes cifradas; FHE encuentra coincidencias sin conocer los detalles.
- **Proceso:**
- Envío cifrado de órdenes.
- Encontrar coincidencias sin detalles.
- Ejecutar la orden en el mercado público.
- **Ejemplo:** Implementaciones de Zama y Sunscreen.

3. **Votación Privada**
- **Descripción:** Los votos para DAOs se mantienen confidenciales, protegiendo detalles como montos y decisiones.
- **Proceso:**
- Cifra el contrato de tokens.
- Procesa cambios en la delegación de votos con FHE.
- Contar y gestionar votos cifrados.
- **Ejemplo:** Contrato COMP y Gobernador.

4. **Subastas a Ciegas**
- **Descripción:** Las ofertas se mantienen cifradas y FHE determina la oferta más alta sin revelar los detalles.
- **Proceso:**
- Ofertas cifradas.
- Determinar la oferta más alta.
- Ejecutar y devolver ofertas.
- **Ejemplo:** Subastas a ciegas en cadena usando FHE.

### Fuentes
- [Privacy Scaling Explorations](https://mirror.xyz/privacy-scaling-explorations.eth/wQZqa9acMdGS7LTXmKX-fR05VHfkgFf9Wrjso7XxDzs)
- [CCS HE Tutorial Slides](https://homomorphicencryption.org/wp-content/uploads/2018/10/CCS-HE-Tutorial-Slides.pdf?ref=blog.sunscreen.tech)
- [Intro to Fully Homomorphic Encryption for Engineers](https://blog.sunscreen.tech/an-intro-to-fully-homomorphic-encryption-for-engineers/)
- [LWE PDF](https://www.usf-crypto.org/wp-content/uploads/2022/10/LWE.pdf)