Resumen Técnico: Búsqueda de Embeddings Privada con Consultas Compactas Cifradas bajo Cifrado Totalmente Homomórfico

Planteamiento del Problema

En el aprendizaje automático preservador de la privacidad (PPML) utilizando Cifrado Totalmente Homomórfico (FHE), surge un cuello de botella crítico durante la inferencia de modelos que dependen de entradas discretas, como el Procesamiento de Lenguaje Natural (NLP) y los sistemas de recomendación. Estos modelos suelen comenzar con una capa de embedding, que mapea un índice discreto (por ejemplo, un token de palabra) a un vector continuo.

Bajo FHE, el servidor no puede realizar el acceso estándar a la memoria basado en un índice cifrado. En su lugar, la búsqueda debe realizarse mediante aritmética homomórfica. Los enfoques existentes enfrentan un compromiso (trade-off):

1. Búsqueda del lado del cliente: El cliente envía el vector de embedding cifrado. Esto incurre en una sobrecarga de comunicación masiva proporcional a la dimensión del embedding ($d$), lo cual es prohibitivo para tablas grandes (por ejemplo, GloVe con 1.9M de tokens).
2. Búsqueda del lado del servidor con Generación de One-Hot: El cliente envía un escalar índice compacto cifrado. El servidor debe entonces construir homomórficamente un vector one-hot para seleccionar el embedding. Un trabajo previo (Kim et al., ICML 2024) logra esto utilizando una Función Indicadora Cifrada (EIF), pero esto requiere $O(p \log p)$ operaciones homomórficas (donde $p$ es el tamaño de la tabla), consumiendo una profundidad multiplicativa significativa y convirtiéndose en el costo dominante en el pipeline de inferencia.

El objetivo es lograr una Búsqueda de Embedding Privada (PEL) que mantenga una comunicación compacta del cliente (enviando solo un índice escalar) mientras minimiza el costo de computación homomórfica del servidor, evitando el costoso paso de la generación de one-hot.

Metodología: Evaluación de Vectores Independientes (IVE)

Los autores proponen la Evaluación de Vectores Independientes (IVE), un método que evita por completo la construcción de un vector one-hot.

Idea Central

El servidor no requiere estrictamente un vector one-hot ($e_j$) para recuperar el embedding $M_j$. Solo requiere una representación del índice $j$ que sea linealmente independiente a través de diferentes índices. Si un conjunto de vectores $\{v_j\}$ es linealmente independiente, existe una matriz de cambio de base $L$ tal que $L v_j = e_j$. Consecuentemente, la recuperación del embedding puede reescribirse como:
$$M_j = M e_j = M (L v_j) = (M L) v_j$$
Dado que $M$ y $L$ son conocidos en texto plano, el servidor puede precomputar la matriz $M' = ML$. La tarea en línea se desplaza de generar un vector one-hot a evaluar el vector $v_j$ homomórficamente.

Construcción de Vectores y Estabilidad

Para asegurar la eficiencia y la estabilidad numérica bajo el esquema CKKS (que soporta aritmética aproximada):

1. Eficiencia: Los vectores $v_j$ se construyen utilizando potencias sucesivas de un único valor cifrado $\alpha_j$. Esto permite al servidor generar los componentes del vector usando operaciones aritméticas estándar (multiplicaciones) en lugar de pruebas de igualdad complejas.
2. Estabilidad: Para prevenir la amplificación de errores durante el cambio de base, la matriz $L$ debe estar bien condicionada (idealmente ortogonal). Los autores utilizan una matriz de Transformada de Coseno Discreta (DCT). Al utilizar raíces de la unidad y separar las partes reales e imaginarias, construyen una base ortogonal que se alinea con las capacidades de aritmética compleja de CKKS.

Flujo Algorítmico

1. Cliente: Cifra el índice $j$ en un valor $\alpha_j$ (derivado de raíces de la unidad) y lo transmite como una consulta escalar compacta.
2. Servidor (Fase IVE):
   • Recibe el $\alpha_j$ cifrado.
   • Computa las potencias $\alpha_j^0, \alpha_j^1, \dots, \alpha_j^{p/2}$ usando un árbol de multiplicación (profundidad logarítmica).
   • Separa las partes real e imaginaria mediante conjugación para formar el vector $v_j$.
   • Este proceso requiere $O(p)$ operaciones homomórficas, una reducción significativa respecto a las $O(p \log p)$ requeridas para la generación de one-hot.
3. Servidor (Fase PCMM):
   • Realiza una Multiplicación de Matriz-Texto Plano (PCMM) entre la matriz precomputada $M' = ML$ y el vector generado $v_j$.
   • Esto produce el vector de embedding cifrado.

Principales Contribuciones

1. Evaluación de Vectores Independientes (IVE): Un nuevo algoritmo que reemplaza la generación de one-hot cifrada por la evaluación de una familia de vectores linealmente independientes. Esto reduce la complejidad de generación de vectores de $O(p \log p)$ a $O(p)$ operaciones homomórficas.
2. Base Ortogonal vía DCT: La instanciación de IVE utilizando una matriz ortogonal basada en DCT asegura la estabilidad numérica, mitigando la amplificación de error inherente a la aproximación de CKKS al realizar el cambio de base.
3. Pipeline de PEL Integrado: Los autores integran IVE con PCMM para manejar consultas por lotes (batches) de manera eficiente. Este pipeline soporta múltiples consultas de tokens simultáneamente, amortizando el costo a través de los slots SIMD de CKKS.
4. Implementación de Extremo a Extremo: El método se implementa dentro de un pipeline de clasificación de texto estilo FastText, demostrando su viabilidad para tareas de inferencia prácticas y sensibles a la privacidad.

Resultados Experimentales

Los autores evaluaron IVE-PEL frente al estado del arte anterior (Kim et al.) utilizando tres conjuntos de datos de embeddings (GloVe.6B.50d, GloVe.42B.300d, y GPT-2) y una inferencia FastText de extremo a extremo en el conjunto de datos Enron-Spam.

• Aceleración en la Generación de Vectores: IVE-PEL reduce significativamente el tiempo dedicado a la generación de vectores. Para un tamaño de subtabla de $\log p = 10$, el tiempo de VecGen cayó de ~424 ms (Kim et al.) a ~3.15 ms (IVE-PEL) en GloVe.6B.50d, lo que representa una aceleración de 134.6× en esta etapa específica.
• Aceleración del Pipeline Total: El tiempo de búsqueda amortizado mejoró de 18.5× a 78.4× dependiendo del conjunto de datos y la dimensión del embedding. Las mayores ganancias se observaron en escenarios donde la generación de vectores era el costo dominante.
• Profundidad Multiplicativa: IVE-PEL consume aproximadamente 1/3 de la profundidad multiplicativa requerida por el método de generación de one-hot, permitiendo tamaños de subtabla más grandes y una mejor calidad de compresión sin agotar el presupuesto de ruido de CKKS.
• Impacto de Extremo a Extremo: En la tarea de clasificación Enron-Spam, reemplazar el método one-hot con IVE redujo la participación de la generación de vectores en el tiempo total de inferencia cifrada del 99.6% al 66.3%, reduciendo sustancialmente la latencia general.

Significado y Reivindicaciones

El artículo afirma que IVE-PEL aborda el "punto de diseño faltante" en la búsqueda de embeddings privada: lograr una comunicación compacta del cliente (índices escalares) sin incurrir en el costo prohibitivo de la generación de one-hot homomórfica en el servidor.

Al desacoplar la necesidad de una base one-hot del proceso de recuperación, los autores demuestran que la búsqueda de embeddings privada puede ser práctica para clientes ligeros y modelos a gran escala. Los resultados sugieren que IVE-PEL hace que el embedding en el lado del servidor sea una alternativa viable para la búsqueda de embeddings en el lado del cliente, permitiendo la inferencia eficiente y preservadora de la privacidad para modelos de NLP y sistemas de recomendación sin sacrificar la confidencialidad de los índices de entrada del usuario. El método mantiene la precisión de los modelos subyacentes (como lo evidencian los resultados de clasificación de sentimiento de IMDB y detección de spam) mientras mejora drásticamente la eficiencia computacional.