Aplicar operaciones homomórficas en grandes datos cifrados
Actualmente experimentando con el cifrado homomórfico utilizando la biblioteca PALISADE .
Quiero aplicar operaciones simples de he como sumas y multiplicaciones en grandes entradas cifradas. Por ejemplo, la entrada A[3200]y la entrada B[4096]se cifran tanto los vectores / matrices de valores int. Con esas dos entradas Enc(A)y Enc(B)quiero aplicar una multiplicación:
EvalMult(Enc(A[0]), Enc(B[42]))
*0 and 42 denoting the indexes of the corresponding inputs
** no SIMD needed
En lo que a mí respecta, la implementación de los requisitos descritos anteriormente podría resolverse de dos maneras diferentes:
Empaque las entradas en un solo texto cifrado (como SIMD) y para las operaciones que podría utilizar
EvalIndexAt()para obtener el valor correcto de la entrada cifrada.Cifre cada valor de A y B por separado.
No estoy muy seguro de cuál de las soluciones descritas sería la mejor en términos de eficiencia . El primer enfoque tiene la gran ventaja de que solo se necesita un proceso de cifrado para toda la entrada, pero esto tiene la desventaja de que siempre tengo que acceder al elemento correcto usando el EvalAtIndex()método y cuanto más grandes son las entradas, más lento es el cálculo de los get EvalAtIndexKeyGen(). (Al menos en mi máquina)
El segundo enfoque parece encajar mejor porque EvalAtIndex()no es necesario, pero tiene el costo de cifrar cada valor por separado, lo que lleva bastante tiempo.
¿Alguna recomendación de pensamientos?
Respuestas
Gracias por la pregunta.
El principal beneficio del enfoque n. ° 1 (SIMD) es que puede realizar la suma y multiplicación de vectores (de 4096 o más enteros / números reales) utilizando una única suma o multiplicación homomórfica (muy eficiente). La rotación (llamada EvalAtIndexen PALISADE) es una operación adicional que permite acceder a índices individuales o realizar una suma eficiente (como en el producto interno), multiplicación de matrices, etc. Este enfoque también tiene un factor de expansión de texto cifrado mucho menor (por 4096x o más) que enfoque # 2. Generalmente, la opción # 1 se prefiere en la práctica (y no puedo pensar en ningún caso de uso real en el que me gustaría ir con la opción # 2).
Para minimizar el costo de la multiplicación, tal vez podría empaquetar el vector en bloques contiguos para que necesite una sola rotación para un bloque. Por ejemplo,
EvalMult(Enc(A[0:5]),Enc(B[42:47))
Otra técnica que puede utilizar es EvalFastRotation(disponible solo para CKKS y BGVrns en PALISADE v1.10.x). Si necesita múltiples rotaciones del mismo texto cifrado, puede precalcular algo para el texto cifrado y luego usar rotaciones más baratas (el mayor beneficio se logra para el cambio de clave BV); consultehttps://gitlab.com/palisade/palisade-development/-/blob/master/src/pke/examples/advanced-real-numbers.cpp para un ejemplo.
También hay formas de minimizar la cantidad de claves que se generarán si necesita varias rotaciones (solo calcule aproximadamente una raíz cuadrada de la cantidad de rotaciones necesarias), por ejemplo, utilizando la técnica de paso de bebé a paso gigante descrita en https://eprint.iacr.org/2018/244 (estas técnicas se pueden implementar en su aplicación basada en PALISADE).
También puede usar un orden especial para empaquetar un vector si se conoce el patrón para realizar la multiplicación (de esta manera, su rotación preparará varios bloques a lo largo del vector usando una sola operación de rotación). Las rotaciones son cíclicas (envolventes) tanto en CKKS como en BGVrns cuando el número de espacios de texto plano (tamaño de lote) es igual a ring dimension/ 2. Si tiene un vector más pequeño que ese, siempre puede clonar / replicar el vector pequeño tantas veces como sea necesario para llenar ring dimension/ 2.
En resumen, la mayor mejora de la eficiencia se puede lograr si piensa en su problema en términos de vectores similares a SIMD. Luego, puede reformular su problema / modelo para aprovechar al máximo el conjunto de herramientas que proporciona HE. En cierto modo, esto es similar a programar usando instrucciones vectorizadas, por ejemplo, AVX, o programación orientada a matrices (como en MATLAB).