Implementation and Optimization of HQC Decoding on NPU-Integrated Devices

Planteamiento del Problema

El algoritmo Hamming Quasi-Cíclico (HQC) ha sido seleccionado por el NIST como un Mecanismo de Encapsulamiento de Claves (KEM) basado en códigos para proporcionar diversidad algorítmica junto con la criptografía post-cuántica basada en retículos. Aunque HQC depende de códigos de corrección de errores (específicamente códigos Reed-Muller y Reed-Solomon concatenados) para su seguridad, su despliegue práctico en plataformas móviles y embebidas se ve obstaculizado por el alto costo computacional de su procedimiento de decodificación.

Las implementaciones existentes en CPUs restringidas o hardware especializado (FPGAs, RISC-V) han demostrado que el rendimiento de HQC depende fuertemente de cómo los núcleos de decodificación se mapean al backend de ejecución. Sin embargo, las plataformas móviles modernas integran cada vez más Unidades de Procesamiento Neuronal (NPU) con aceleradores vectoriales (como las extensiones vectoriales Hexagon de Qualcomm, o HVX) diseñados principalmente para IA y procesamiento de señales. El desafío abordado en este trabajo es que la decodificación de HQC no puede acelerarse eficientamente mediante una traducción directa de decodificadores escalares a estos backends vectoriales. El proceso de decodificación implica dependencias de datos complejas, reglas de desempate específicas y patrones de acceso a memoria irregulares (por ejemplo, en las FFTs aditivas) que no se alinean naturalmente con la ejecución vectorial de estilo SIMD.

Metodología

Los autores proponen una implementación de decodificación de HQC optimizada de extremo a extremo dirigida al backend vectorial Hexagon/HVX en dispositivos Qualcomm con integración de NPU. En lugar de utilizar un motor de inferencia tensorial, el trabajo se centra en el modelo de ejecución vectorial, que soporta operaciones SIMD anchas, aritmética por carriles (lane-wise) y reducciones.

La metodología consiste en descomponer el decodificador HQC en sus componentes constituyentes Reed-Muller (interno) y Reed-Solomon (externo) y rediseñar los núcleos dominantes para que se ajusten a disposiciones de datos y patrones de ejecución favorables para HVX:

1. Optimización de la Decodificación Reed-Muller:

   • Transformada de Hadamard Vectorizada: Los autores rediseñan la transformada rápida de Hadamard para el código Reed-Muller duplicado interno. Utilizan intrínsecos de HVX (por ejemplo, VDEALH, VADDH, VSUBH) para realizar sumas y restas paralelas por carriles, reemplazando las etapas de mariposa secuenciales de la implementación escalar.
   • Selección de Pico Equivalente a Escalar: Un desafío crítico es preservar la regla de desempate del decodificador escalar (seleccionar el índice más pequeño entre los coeficientes con magnitud máxima igual). Los autores implementan una búsqueda vectorizada que calcula magnitudes, identifica todos los candidatos a pico y realiza una reducción de mínimo vectorial sobre los índices candidatos para asegurar la equivalencia a nivel de bits con la referencia escalar.

2. Optimización de la Decodificación Reed-Solomon:

   • Aritmética de Campo Finito Orientada a HVX: Para las operaciones vectorizadas (cálculo de síndrome y búsqueda de Chien), los autores reemplazan la multiplicación escalar basada en tablas por un método de Horner bit-serial utilizando primitivas xtime. Esto permite la multiplicación escalar-por-vector a través de los carriles HVX sin depender de grandes tablas de búsqueda que causarían fallos de caché o requerirían indexación compleja.
   • Cálculo de Síndromes Vectorizado: En lugar de calcular los síndromes secuencialmente, la implementación empaqueta las potencias del elemento primitivo en vectores y acumula los resultados mediante operaciones XOR a través de todos los índices de los síndromes simultáneamente.
   • Búsqueda de Chien de Soporte Acortado: Reconociendo que la FFT aditiva utilizada en las implementaciones escalares tiene dependencias secuenciales no aptas para HVX, los autores la reemplazan con una búsqueda de Chien de soporte acortado. Este método evalúa el polinomio localizador de errores sobre puntos de soporte públicos utilizando vectores empaquetados, lo que permite la evaluación paralela a través de los carriles HVX mientras mantiene la naturaleza secuencial de los coeficientes del polinomio.
   • Manejo de Berlekamp-Massey: El cálculo del polinomio localizador de errores (algoritmo de Berlekamp-Massey) es inherentemente secuencial y corto (máximo 16 coeficientes para HQC-128). Los autores mantienen esta etapa como escalar, pero optimizan sus multiplicaciones de campo finito utilizando métodos de logaritmo/antilogaritmo basados en tablas, ya que la vectorización aporta pocos beneficios para bucles tan cortos.

3. Integración del Sistema:

   • La implementación se ejecuta en un kit de desarrollo Snapdragon 8 Gen 2 utilizando la interfaz FastRPC para descargar tareas desde la CPU host hacia el cDSP (Hexagon DSP).
   • Para mitigar la alta sobrecarga de la inicialización de FastRPC (aprox. 557 µs), los autores emplean una estrategia de loteo (batching), procesando múltiples instancias de decodificación en una sola llamada remota para amortizar el costo de comunicación.

Contribuciones Clave

• Identificación de la Idoneidad Vectorial: El artículo establece que la decodificación de HQC es un candidato natural para la aceleración Hexagon/HVX debido a la estructura vectorial inherente de sus vectores de confiabilidad, coeficientes de Hadamard y vectores de síndrome.
• Rediseño de Núcleos: Los autores presentan un rediseño completo de los núcleos de decodificación dominantes:
  • Una transformada de Hadamard de Reed-Muller vectorizada y selección de picos que preserva estrictamente las reglas de desempate escalares.
  • Multiplicación de campo finito y cálculo de síndrome orientados a HVX.
  • Una búsqueda de Chien de soporte acortado vectorizada que reemplaza la FFT aditiva escalar.
• Evaluación de Rendimiento: El trabajo proporciona una evaluación exhaustiva utilizando tanto el simulador preciso de ciclos de Hexagon como experimentos en dispositivos reales en un Snapdragon 8 Gen 2.
• Escalabilidad: Los principios de optimización se demuestran extensibles desde HQC-128 hasta HQC-192 y HQC-256, con ajustes para tamaños de bloque y acumulación de múltiples vectores para conjuntos de soporte más grandes.

Resultados

La evaluación demuestra mejoras sustanciales en latencia, eficiencia energética y descarga de la CPU host:

• Resultados del Simulador (HQC-128): La implementación optimizada reduce el costo de decodificación de 953,763 a 41,471 Pcycles por decodificación, lo que representa una aceleración de 23.00× y una reducción del 95.7% en los ciclos del procesador. El análisis de las subetapas muestra ganancias masivas, como la reducción de la transformada de Hadamard de Reed-Mumbler de 263,175 a 17,950 Pcycles.
• Resultados en Dispositivo Real (Snapdragon 8 Gen 2):
  • Latencia: El backend soportado por NPU con loteo logra aceleraciones de latencia de 2.07× (HQC-128), 1.85× (HQC-192) y 1.96× (HQC-256) en comparación con la línea base escalar de la CPU ARM.
  • Eficiencia Energética: La implementación mejora la eficiencia energética en 18.13× (HQC-128), 11.77× (HQC-192) y 16.81× (HQC-256).
  • Descarga de la CPU (Offloading): El tiempo de la CPU host por decodificación se reduce en un 99.0%–99.7%, liberando efectivamente al procesador de aplicaciones para otras tareas mientras la decodificación se ejecuta en el cDSP.
• Nota sobre la Sobrecarga: Los autores señalan que el costo del límite FastRPC es significativo (~531–553 µs por llamada). Las ganancias reportadas en el dispositivo real se logran específicamente mediante el loteo (batching) de múltiples decodificaciones en una sola llamada; un enfoque de "una decodificación por llamada" sería significamente más lento (de 5.4× a 15× más lento) debido a esta sobrecarga.

Significado y Reivindicaciones

El artículo afirma que las plataformas móviles integradas con NPU pueden servir como backends efectivos para la decodificación criptográfica post-cuántica estructurada, siempre que los núcleos subyacentes se reformulen en torno al modelo de ejecución vectorial disponible.

• Diversidad Algorítmica: El trabajo respalda el objetivo de diversidad criptográfica del NIST al demostrar que los esquemas basados en códigos como HQC pueden desplegarse eficientemente en hardware móvil moderno, no solo en esquemas basados en retículos.
• Utilización de Hardware: Destaca que los aceleradores vectoriales (HVX), a menudo reservados para la IA, son muy adecuados para las primitivas criptográficas con estructuras de datos regulares, ofreciendo un camino para la seguridad post-cuántica eficiente en dispositivos de consumo sin requerir hardware criptográfico dedicado.
• Modestia sobre la Seguridad: Los autores declaran explícitamente que su implementación actual no es de tiempo constante (constant-time). Reconocen que el uso de aritmética de campo finito basada en tablas y la lógica de Berlekamp-Massey con ramificaciones introduce posibles vulnerabilidades de canal lateral (tiempo y potencia). Enmarcan esto como una optimización centrada en el rendimiento, dejando el desarrollo de un backend totalmente de tiempo constante y resistente a canales laterales como trabajo futuro.
• Trabajo Futuro: Los autores identifican la integración de estas optimizaciones de decodificación con la multiplicación de polinomios dispersos acelerada (el otro costo principal en la decapsulación de HQC) como el siguiente paso lógico hacia la aceleración completa de la decapsulación.