Esquemas BGV y BFV para operaciones con enteros

BGV (Brakerski-Gentry-Vaikuntanathan, 2012) es un esquema FHE por niveles basado en RLWE. Admite sumas y multiplicaciones arbitrarias sobre textos planos enteros empaquetados. «Por niveles» significa que admite circuitos de hasta una profundidad fija L sin bootstrapping.

BGV y BFV codifican los textos planos como polinomios en Z_t[x]/(x^n+1), donde t es un módulo pequeño del texto plano (por ejemplo, t=65537). Cada polinomio codifica n valores enteros, uno por coeficiente. La aritmética sobre los textos cifrados opera simultáneamente en los n valores, lo que proporciona paralelismo SIMD.

BGV reduce el ruido mediante el cambio de módulo: después de cada multiplicación, el módulo q del texto cifrado se reduce de Q_L a Q_{L-1}. Esto divide el ruido por Q_L/Q_{L-1}, manteniéndolo dentro de los límites que permiten descifrar. La profundidad del circuito L corresponde a L niveles de módulo.

BFV (Brakerski/Fan-Vercauteren, 2012) es similar a BGV, pero utiliza una estrategia diferente de gestión del ruido: invariancia de escala. BFV no requiere un cambio de módulo; en su lugar, reescala el texto cifrado después de la multiplicación. Es más sencillo de implementar y se utiliza en Microsoft SEAL.

Mediante el teorema chino del resto sobre el anillo de texto plano, cada texto cifrado puede contener n/2 valores enteros independientes (ranuras). Una operación de suma de textos cifrados suma en paralelo los n/2 pares. Una multiplicación multiplica todos los pares. Rendimiento: n/2 operaciones enteras por operación de texto cifrado.

Después de multiplicar dos textos cifrados de grado 1, el resultado tiene grado 2 (3 componentes). La relinealización utiliza claves de evaluación (relin keys) para volver a convertirlo en un texto de grado 1, a cambio de añadir ruido. Este paso es necesario después de cada multiplicación.

from seal import EncryptionParameters, scheme_type, SEALContext, KeyGenerator, Encryptor, Evaluator, Decryptor parms = EncryptionParameters(scheme_type.bfv) parms.set_poly_modulus_degree(4096) parms.set_coeff_modulus(CoeffModulus.BFVDefault(4096)) parms.set_plain_modulus(PlainModulus.Batching(4096, 20))

La rotación del texto cifrado desplaza cíclicamente las n/2 ranuras del texto plano. Es útil para: reducción mediante suma (acumular todas las ranuras en una), multiplicación matriz-vector (rotar y acumular) y convoluciones (desplazar y multiplicar). Requiere claves de Galois (claves de rotación precalculadas).

BFV con n=8192: suma ~10 µs, multiplicación ~5 ms (con relinealización). Bootstrapping (si es necesario): 30-60 segundos. Lote de 4096 enteros: ~1 µs amortizado por entero y multiplicación. Es inviable para tiempo real, pero viable para análisis sin conexión.

Para elegir n y q: SEAL recomienda n=4096 para una seguridad de 128 bits con Q < 2^109; n=8192 para circuitos más grandes. El estándar de HE (homomorphicencryption.org) proporciona tablas de parámetros. Utilice siempre los parámetros recomendados: las elecciones personalizadas pueden poner en peligro fácilmente la seguridad.

Consultas a bases de datos cifradas (buscar registros cifrados sin descifrarlos). Análisis genómico privado (calcular estadísticas sobre ADN cifrado). Agregaciones financieras cifradas (sumar saldos de cuentas cifrados sin ver los datos individuales). Evaluación segura de modelos.

¿Qué técnica utiliza BGV para gestionar el crecimiento del ruido después de las multiplicaciones?

BGV y BFV realizan aritmética entera cifrada mediante RLWE. La codificación por lotes proporciona paralelismo SIMD. BGV utiliza el cambio de módulo; BFV utiliza la invariancia de escala. La relinealización restaura el grado después de la multiplicación. Siguiente: CKKS para aritmética aproximada y ML.