Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts

Resumen Técnico: Escaneos de Prefijo No Conmutativos Óptimos en Rotación en Distribuciones de Orden Bit-Revertido

Planteamiento del Problema

En el cifrado homomórfico empaquetado (HE), específicamente en el esquema CKKS, las operaciones SIMD permiten la computación paralela sobre vectores cifrados. Sin embargo, la comunicación entre ranuras (slots) requiere rotaciones cíclicas (automorfismos de Galois), que son operaciones costosas que implican el cambio de clave (key switching). El costo de una rotación depende de la disposición física de los datos.

El artículo aborda el problema de realizar computaciones de prefijo ordenadas (escaneos o scans) sobre $n = 2^m$ elementos de un monoide asociativo, posiblemente no conmutativo, cuando los datos están almacenados en un orden de inversión de bits (bit-reversed order). Esta disposición es común en transformadas rápidas y conversiones de empaquetado.

El desafío central es que un escaneo de "predecesor transportado" estándar (que duplica recursivamente la distancia hacia los predecesores lógicos) incurre en un alto costo de enrutamiento en una disposición de inversión de bits. Debido a que la inversión de bits permuta los índices lógicos, un desplazamiento lógico simple por $2^t$ se descompone en múltiples clases de desplazamientos cíclicos distintos. En consecuencia, una implementación directa requiere $R_{direct} = \sum_{t=0}^{m-1} (m-t) = \frac{m(m+1)}{2}$ rotaciones. Los autores investigan si este costo triangular es una propiedad inherente de la computación de prefijo en disposiciones de inversión de bits o un artefacto de la topología de enrutamiento específica.

Metodología y Construcción

El artículo introduce un invariante de replicación-agregación para reducir el conteo de rotaciones de cuadrático a lineal.

1. Replicación Semántica: En lugar de enrutar cada ranura a su predecesor lógico exacto, la construcción mantiene un estado donde cada ranura dentro de un bloque lógico alineado almacena el agregado completo de dicho bloque.
2. Intercambio de Bloques Hermanos: En cada nivel $d$ del escaneo (combinando bloques de tamaño $2^d$), el algoritmo rota el estado agregado por un desfase específico $s_d = 2^{m-d-1}$.
   • Bajo la inversión de bits, los dos hijos de un bloque padre ocupan cosenos físicos separados exactamente por $s_d$.
   • Una rotación por $s_d$ mapea una ranura a alguna posición en el bloque hermano. Debido a que el agregado del hermano está replicado en todas sus ranuras, cualquier posición en el bloque hermano proporciona el valor semántico correcto.
   • Esto permite que una única rotación cíclica dirigida suministre agregados válidos para ambas orientaciones de los hijos simultáneamente, preservando la corrección para monoides no conmutativos mediante máscaras públicas que seleccionan el orden de los operandos.
3. Formulación de Escaneo Exclusivo: Los autores implementan un escaneo exclusivo (que devuelve el prefijo antes del elemento actual). Esto evita la necesidad de un desplazamiento de predecesor lógico final para recuperar el acarreo entrante para la corrección de dígitos, un requisito que de otro modo reintroduciría el enrutamiento sensible a la disposición.
4. Pruebas de Límite Inferior: El artículo establece que $m$ rotaciones es un límite inferior global para cualquier circuito que compute un resultado que dependa de todos los $2^m$ entradas en este modelo. La prueba se basa en un argumento de suma de subconjuntos: si se usan $R$ rotaciones, como máximo $2^R$ desplazamientos de entrada distintos pueden alcanzar una salida fija. Para cubrir todas las $2^m$ entradas, es necesario que $R \ge m$. Además, el artículo demuestra que lograr este límite requiere que los desplazos de rotación formen una base 2-ádica completa (un desplazamiento para cada valoración $0, \dots, m-1$).

Contribuciones Clave

1. Construcción de Escaneo Óptima: Un algoritmo de escaneo inclusivo y exclusivo que logra $R = m$ rotaciones y $D = m$ de profundidad de monoide para disposiciones de inversión de bits. Esto reduce el conteo de rotaciones de la topología directa de $O(m^2)$ a $O(m)$.
2. Rigidez de la Optimidad: Una caracterización de todos los circuitos óptimos. Si un circuito utiliza exactamente $m$ rotaciones, los desplazos deben formar una base 2-ádica completa. Esto demuestra que el perfil de rotación es rígido, incluso si la topología del circuito varía.
3. Frontera de Claves de Rotación: Un análisis del compromiso entre el número de desplazos con clave directa ($K$) y el número de llamadas de rotación en línea ($R$).
   • El artículo deriva un límite inferior de producto: $\prod (c_j + 1) \ge 2^m$, donde $c_j$ es el número de veces que se usa la clave $j$.
   • Cuando $K$ divide a $m$, la frontera exacta se demuestra como $R^* = K \cdot (2^{m/K} - 1)$.
4. Instanciación Radix-CKKS: Aplicación del escaneo exclusivo para la propagación exacta de acarreo y préstamo en aritmética de base en Radix-CKKS. Esto permite la comparación de enteros y la aritmética modular sin restaurar el orden natural ni realizar un desplazamiento final.
5. Eficiencia de Loteo (Batching): Demostración de que los ahorros de rotación se mantienen para entrelazados de mayor importancia de dígito (digit-major interleavings) totalmente ocupados, donde $g$ enteros independientes se empaquetan en un solo texto cifrado sin multiplicar el conteo de rotaciones.

Resultados y Evaluación

Los autores implementaron el algoritmo en Lattigo (Go) y lo compararon con dos líneas base:

1. Predecesor Directo de Inversión de Bits: El enfoque ingenuo de $O(m^2)$ rotaciones.
2. Normalizar–Escanear–Restaurar: Una línea base que convierte los datos a orden natural, escanea y convierte de vuelta.

Hallazgos Clave en $m=7$ (128 ranuras):

• Rotaciones: Reducidas de 28 (directo) a 7 (replicado).
• Claves de Evaluación: El almacenamiento se redujo en un 70.0% (908.6 MB $\to$ 272.6 MB).
• Memoria: El uso de pico de memoria (heap) se redujo en un 63.9% (2.30 GB $\to$ 830.5 MB).
• Latencia: El escaneo replicado mejoró la latencia de escaneo aislado en un 19.9% sobre el método de predecesor directo.
• Pipeline de Extremo a Extremo: En un pipeline descendente de profundidad 5, el escaneo replicado evitó una operación completa de bootstrapping requerida por la línea base de normalizar-restaurar. Esto produjo una mejora de velocidad media de 4.31$\times$ (IC 95% [3.69, 4.92]).

El artículo señala que, si bien "normalizar–escanear–restaurar" tiene una latencia aislada menor para $m$ pequeños debido a menos composiciones de monoide, el escaneo replicado es más rápido para $m \ge 5$ y ofrece una eficiencia de recursos superior (claves, memoria, niveles de módulo).

Significancia y Reivindicaciones

El artículo afirma que preservar una representación SIMD de inversión de bits no impone una sobrecarga de rotación inevitable para la computación de prefijo ordenado. La significancia radica en:

• Romper la Barrera Cuadrática: Demostrar que el costo de $O(m^2)$ de enrutamiento directo en disposiciones de inversión de bits no es inherente, sino que puede reducirse al límite teórico de $O(m)$ mediante la replicación semántica.
• Compromisos de Recursos: Establecer que la reducción en el costo de enrutamiento (rotaciones) y el almacenamiento de claves proviene a expensas de un mayor trabajo de monoide empaquetado ($2m-1$ composiciones frente a $m$) y un segundo vector de estado vivo. El artículo argumenta que este compromiso es favorable para pipelines profundos donde los niveles de módulo y el bootstrapping son los cuellos de botella.
• Exactitud: Proporcionar límites inferiores exactos y caracterizaciones de frontera para la gestión de claves de rotación, yendo más allá de las optimizaciones heurísticas hacia límites demostrables para patrones de dependencia específicos.

El trabajo se presenta como una optimización específica para la restricción de la disposición de inversión de bits, distinta de la teoría general de redes de prefijos, y se valida mediante pruebas combinatorias rigurosas y evaluación empírica en una implementación estándar de CKKS.