💻 computer science

GPU Acceleration of Learning With Errors KEMs Using OpenACC for Post-Quantum Cryptography

Este artículo presenta una implementación acelerada por GPU de un Mecanismo de Encapsulación de Claves basado en Aprendizaje con Errores (LWE) utilizando OpenACC, demostrando aceleraciones significativas (hasta 208×) y una eficiencia energética mejorada en GPUs de NVIDIA, particularmente en el Grace Hopper Superchip, en comparación con sistemas tradicionales basados en CPU y H100.

Autores originales: Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

Publicado 2026-06-02

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando cerrar un cofre del tesoro con una llave tan compleja que incluso un robot superinteligente del futuro (una computadora cuántica) no podría abrirla. Este es el objetivo de la Criptografía Post-Cuántica. El "candado" específico en el que se centra este artículo se llama Aprendizaje con Errores (LWE, por sus siglas en inglés).

Piensa en LWE como intentar resolver un rompecabezas matemático gigante donde alguien ha añadido intencionalmente un poco de "estática" o "ruido" a la señal. Es fácil crear el ruido, pero increíblemente difícil filtrarlo para encontrar el mensaje original sin la clave secreta. El problema es que resolver este rompecabezas en una computadora estándar es como intentar mover una montaña grano de arena a la vez: toma una eternidad.

Aquí explicamos de forma sencilla lo que hicieron los investigadores para acelerar esto:

1. El Problema: La CPU es un Camión Lento

Los autores comenzaron con una versión de este cifrado que se ejecuta en un procesador de computadora estándar (la CPU). Descubrieron que la CPU estaba sufriendo. Era como un solo camión de reparto intentando mover miles de cajas. Cada vez que necesitaba mover una caja (un trozo de datos) desde el almacén (memoria) hasta la plataforma del camión, tenía que detenerse, cargarla y conducirla. El camión pasaba la mayor parte del tiempo esperando, no trabajando.

2. La Solución: La GPU es una Flota de Drones

Para solucionar esto, trasladaron el trabajo pesado a una GPU (Unidad de Procesamiento Gráfico). Si la CPU es un solo camión de reparto, la GPU es una flota de miles de pequeños y superrápidos drones.

La Analogía: En lugar de un camión transportando una caja a la vez, la GPU puede transportar miles de cajas simultáneamente.
La Herramienta: Utilizaron un lenguaje de programación llamado OpenACC. Piensa en esto como un control remoto universal. En lugar de reescribir todo el manual de instrucciones para los drones (lo cual sería difícil y propenso a errores), simplemente apuntaron el control remoto a las instrucciones existentes del camión y dijeron: "¡Oye, tú también haz esto, pero más rápido!". Esto facilitó la actualización del software sin romperlo.

3. El Cuello de Botella: El Generador de "Ruido"

En este cifrado, necesitas mucho "ruido" aleatorio para que el rompecabezas sea difícil.

La Forma Antigua: La CPU generaba el ruido, lo escribía y luego lo llevaba a la GPU. Esto era como si el conductor del camión se detuviera a escribir una lista de compras, condujera a la tienda, comprara los artículos y regresara conduciendo. Se desperdiciaba mucho tiempo.
La Solución: Instalaron un "generador de ruido" directamente dentro del almacén de la GPU. Ahora, los drones pueden generar su propio ruido aleatorio en el acto. No necesitan esperar a que el camión les traiga el material. Esto redujo el tiempo de espera drásticamente.

4. El Truco de la "Agrupación" (Batching)

El proceso de cifrado implica resolver 256 rompecabezas diminutos a la vez (uno por cada bit de un mensaje).

La Forma Antigua: La GPU resolvía un rompecula, se detenía, esperaba instrucciones, resolvía el siguiente, se detenía, esperaba... como un chef cocinando un huevo a la vez y esperando a que la estufa se enfriara entre cada uno.
La Solución: Utilizaron una estrategia llamada Agrupación Intra-Operación (Intra-Operation Batching). Esto es como si el chef pusiera los 256 huevos en una sartén gigante y los cocinara todos juntos. La GPU realiza un gran "lanzamiento" para resolver los 256 rompecabezas simultáneamente, ahorrando una cantidad masiva de tiempo.

5. Los Resultados: Velocidad y Energía

Los investigadores probaron esto en diferentes tipos de computadoras superrápidas (GPUs) y lo compararon con el método antiguo de la CPU.

Velocidad: En la computadora más nueva y potente que probaron (el Superchip Grace Hopper), su nuevo método fue 208 veces más rápido que el viejo método de la CPU.
- Analogía: Si el viejo camión tardaba 3 horas en entregar un paquete, la nueva flota de drones lo hace en menos de un minuto.
- Incluso pudieron resolver tamaños de rompecabezas que eran tan enormes que la CPU antigua se habría quedado sin memoria y habría fallado.
Energía: El nuevo método también utilizó menos energía. La computadora Grace Hopper utilizó aproximadamente la mitad de la energía para hacer el mismo trabajo en comparación con una computadora estándar con un tipo diferente de GPU rápida.
- Analogía: Es como realizar la misma entrega pero usando un auto híbrido en lugar de un camión que consume mucha gasolina.

6. Por qué es Importante

El artículo demuestra que, mediante el uso de estos "drones" (GPUs) y trucos inteligentes de gestión (OpenACC, agrupación y ruido en el dispositivo), podemos hacer que estos candados ultra seguros y resistentes a la computación cuántica sean prácticos de usar. Sin estas aceleraciones, las matemáticas son demasiado lentas para ser útiles en el mundo real. Con ellas, podemos asegurar nuestros datos contra futuras computadoras cuánticas sin tener que esperar días para que un solo candado se cierre.

En resumen: Tomaron un método de cifrado lento y de carga pesada y le dieron un impulso de velocidad masivo utilizando miles de trabajadores diminutos (GPUs) que trabajan juntos, generan sus propios suministros y dejan de esperar instrucciones. El resultado es un sistema que es cientos de veces más rápido y mucho más eficiente energéticamente.

Resumen Técnico: Aceleración por GPU de Mecanismos de Encapsulamiento de Claves con Problemas de Aprendizaje con Errores mediante OpenACC

Declaración del Problema
El advenimiento de computadoras cuánticas a gran escala amenaza los protocolos criptográficos asimétricos actuales (p. ej., RSA, ECC) mediante el algoritmo de Shor. La Criptografía Post-Cuántica (PQC) ha emergido como una solución, siendo los esquemas basados en redes (lattices), particularmente aquellos que dependen del problema de Aprendizaje con Errores (LWE), fundamentales para los Mecanismos de Encapsulamiento de Claves (KEM). Sin embargo, los esquemas basados en LWE introducen una carga computacional significativa debido a las operaciones matriciales de gran escala y la generación de aleatoriedad, lo que a menudo los vuelve impracticables para aplicaciones de alto rendimiento en el lado del servidor sobre arquitecturas de CPU estándar. Si bien se ha explorado la aceleración por GPU para la PQC, la mayoría de las implementaciones existentes dependen de optimizaciones específicas de CUDA, lo que limita la portabilidad y la productividad del desarrollador. Además, la migración ingenua a menudo no aborda cuellos de botella como la latencia de transferencia de memoria host-dispositivo y la serialización de la generación de números aleatorios.

Metodología
Los autores proponen un Mecanismo de Encapsulamiento de Claves (KEM) basado en LWE "puro" (evitando estructuras algebraicas adicionales como Ring-LWE) y desarrollan una implementación orientada a GPU utilizando el modelo de programación basado en directivas OpenACC. El trabajo procede a través de los siguientes pasos metodológicos:

Implementación de Referencia: Una implementación en C++ del LWE-KEM fue paralelizada utilizando OpenMP para CPUs multinúcleo. El esquema utiliza la transformación de Fujisaki-Okamoto (FO) para lograr seguridad IND-CCA2, involucrando las fases de KeyGen, Encaps y Decaps.
Portabilidad y Optimización con OpenACC: El código de CPU fue portado a GPUs utilizando OpenACC. Para superar los cuellos de botella de rendimiento, los autores implementaron tres estrategias primarias:
- Agrupación Intra-Operación (Intra-Operation Batching): En lugar de procesar 256 bits de mensajes independientes de forma secuencial (lo que activaría lanzamientos de kernels y transferencias de memoria separados), la implementación fusiona las 256 encriptaciones en un único lanzamiento de kernel de GPU. Esto expone un paralelismo de grano fino ( $256 \times n$ elementos de trabajo) y amortiza la sobrecarga de invocación.
- Generación de Números Aleatorios Residente en el Dispositivo (RNGonGPU): Reconociendo que la transferencia de vectores de ruido pregenerados sobre PCIe crea un cuello de botella severo, los autores integraron la librería RNGonGPU. Esta librería implementa un Generador de Bits Determinista (DRBG) basado en AES-256 directamente en la GPU. Solo se transfiere una semilla de 64 bits del host al dispositivo, reduciendo el volumen de transferencia de datos aproximadamente seis órdenes de magnitud en comparación con la transferencia de vectores de ruido pregenerados.
- Gestión Explícita de Datos: Los autores evitaron la Memoria Unificada de CUDA en favor de directivas explícitas enter data y exit data para controlar las transferencias host-dispositivo de manera determinista, minimizando la comunicación innecesaria y asegurando la consistencia de los datos solo en puntos de sincronización específicos (p. ej., antes del hashing).
Paralelización de Kernels: Las multiplicaciones de matriz-vector, el costo computacional dominante, fueron paralelizadas jerárquicamente. Para la encriptación/desencriptación, las encriptaciones de mensajes independientes se asignaron a gangs de OpenACC, mientras que los componentes del criptograma se computaron concurrentemente a través de los carriles (lanes) de los vectores.

Contribuciones Clave

Implementación de Código Abierto: Los autores proporcionan una implementación de código abierto de un KEM basado en LWE puro tanto para CPU (OpenMP) como para GPU (OpenACC), permitiendo comparativas (benchmarks) reproducibles.
Optimización Basada en Directivas: Un conjunto de optimizaciones orientadas a GPU aplicables a una amplia clase de esquemas LWE, demostrando que los modelos basados en directivas (OpenACC) pueden alcanzar un alto rendimiento sin necesidad de una experiencia profunda en CUDA.
Evaluación Exhaustiva: Un estudio detallado de rendimiento, eficiencia energética y escalabilidad a través de múltiples generaciones de GPUs NVIDIA (Volta, Ampere, Hopper) y arquitecturas (x86 + Hopper vs. el Superchip basado en ARM Grace Hopper).

Resultos
La evaluación se realizó en varias plataformas, incluyendo el Superchip NVIDIA GH200 Grace Hopper, A100 y V100S.

Aceleración (Speedup): La implementación optimizada de OpenACC logró aceleraciones significativas sobre la base de referencia de CPU multihilo. En la plataforma GH200, las aceleraciones alcanzaron hasta 208× para tamaños de problema grandes ( $n=4096$ ). La implementación de GPU comenzó a superar la base de referencia de CPU cuando $n \ge 256$ .
Escalabilidad: La implementación de GPU demostró una escalabilidad superior en comparación con la versión de CPU a medida que aumentaban los tamaños del problema, manejando eficazmente conjuntos de parámetros (p. ej., $n=32768$ ) que eran impracticables de procesar en CPUs debido a la contención de memoria y la sobrecarga de sincronización.
Eficiencia Energética: En el Superchip GH200, la implementación logró una reducción de 1.78× en la energía por solución en comparación con un sistema x86 + H100, impulsada principalmente por el menor consumo de energía de la CPU basada en ARM. La mejora en el tiempo de solución de GH200 vs. x86+Hopper fue más modesta (1.19×).
Escalamiento Arquitectónico: El análisis transgeneracional (V100S $\to$ A100 $\to$ GH200) reveló que el escalamiento del rendimiento está impulsado principalmente por el ancho de banda de la Memoria de Alto Ancho de Banda (HBM). Sin embargo, a medida que el ancho de banda aumenta, la sobrecarga relativa de la generación de elementos de matriz bajo demanda (costo aritmético) y los costos fijos de la transformación FO en el lado de la CPU comienzan a limitar el escalamiento, desplazando el cuello de botella de ser puramente limitado por memoria a una mezcla de restricciones de cómputo y sincronización.
Impacto de la Optimización: El perfilado mostró que la implementación ingenua estaba dominada por la computación en el host y las transferencias PCIe (inanición de la GPU). La implementación optimizada desplazó el cuello de botella hacia la sincronización, con una actividad de la GPU sostenida al ~98% del tiempo de iteración.

Significancia
El artículo afirma que sus resultados resaltan la efectividad de la aceleración por GPU para cargas de trabajo criptográficas basadas en LWE computacionalmente exigentes. Al aprovechar OpenACC, los autores demuestran un camino hacia una PQC de alto rendimiento que equilibra la programabilidad y el rendimiento, evitando la necesidad de codificación de bajo nivel en CUDA. El trabajo sugiere que, con las optimizaciones adecuadas (específicamente la agrupación intra-operación y el RNG residente en el dispositivo), los esquemas LWE "puros" —que ofrecen supuestos de seguridad más conservadores pero mayores costos computacionales— pueden volverse prácticos en plataformas heterogéneas modernas. El estudio también subraya la importancia de co-optimizar el flujo completo heterogéneo, ya que las operaciones en el lado de la CPU y los interconectores restringen cada vez más la escalabilidad en las arquitecturas de próxima generación. Se propone como trabajo futuro extender este enfoque a entornos multi-GPU y otras arquitecturas de aceleradores (AMD, Intel).