Resumen Técnico: Implementación Vectorizada de SQIsign utilizando AVX-512

Planteamiento del Problema

SQIsign es el único esquema de firma digital basado en isogenias presentado al proceso de estandarización de Criptografía Post-Cuántica del NIST. Si bien ofrece tamaños de clave y firma compactos basados en la dureza del problema del anillo de endomorfismos para curvas elípticas supersingularas, su despliegue práctico se ve actualmente obstaculizado por procedimientos de firma computacionalmente intensivos. El cuello de botella del rendimiento reside principalmente en los cálculos del "lado de la curva" (curve-side), que incluyen aritmética extensiva sobre grandes campos primos ($\mathbb{F}_p$) y sus extensiones cuadráticas ($\mathbb{F}_{p^2}$), operaciones de curva elíptica (doble de puntos y multiplicación escalar) y evaluaciones de isogenias de dimensiones superiores sobre superficies abelianas principalmente polarizadas (PPAS). Las implementaciones de referencia existentes dependen fuertemente de la aritmética escalar, utilizando a menudo la biblioteca GNU Multiple Precision Arithmetic Library (GMP) para los componentes de álgebra de cuaterniones, lo que limita el rendimiento (throughput).

Metodología

Este artículo presenta la primera implementación vectorizada integral de los componentes del "lado de la curva" de SQIsign utilizando la arquitectura de conjunto de instrucciones AVX-512 Integer Fused Multiply-Add (IFMA). Los autores rediseñaron sistemáticamente la pila computacional para explotar el paralelismo SIMD (Single Instruction, Multiple Data) en todas las capas algorítmicas principales, mientras que señalan explícitamente que los componentes de álgebra de cuaterniones (IdealToIsogeny) permanecen escalares y no optimizados en este trabajo.

Estrategias Técnicas Principales

1. Aritmética de Campos Finitos ($\mathbb{F}_p$ y $\mathbb{F}_{p^2}$):

   • Representación: La implementación adopta una representación de radix-$2^{51}$ para los elementos del campo, descomponiéndolos en cinco limb (segmentos) de 51 bits. Este tamaño se elige para encajar dentro de los canales de 52 bits inferiores de los registros de 64 bits, evitando el desbordamiento durante las operaciones IFMA mientras se reserva espacio para la reducción diferida.
   • Paralelización: Se emplea una estrategia de paralelización $(8 \times 1)$ en la capa de $\mathbb{F}_p$, procesando ocho elementos de campo independientes simultáneamente dentro de un único registro ZMM de 512 bits.
   • Extensiones: Para $\mathbb{F}_{p^2}$, los autores implementan tres patrones de paralelización distintos—$(8 \times 1 \times 1)$, $(4 \times 2 \times 1)$ y $(2 \times 4 \times 1)$—para equilibrar el rendimiento y la presión de los registros dependiendo de los requisitos algorítmicos específicos (por ejemplo, operaciones por lotes frente a paralelismo de componentes internos).
   • Instrucciones: El diseño aprovecha las instrucciones vpmadd52luq y vpmadd52huq para ejecutar ocho multiplicaciones paralelas de $52 \times 52$ bits con capacidades de multiplicación-acumulación fusionada, reduciendo significativamente los conteos de instrucciones para la multiplicación de Montgomery y la propagación de acarreo.

2. Operaciones de Curva Elíptica:

   • Doble de Puntos (Point Doubling): Los autores optimizaron el doble de puntos tanto para coordenadas solo-$x$ (curvas de Montgomery) como para coordenadas proyectivas completas (Jacobianas y Jacobianas Modificadas). Para las coordenadas solo-$x$, omiten consistentemente los pasos de normalización en contextos vectorizados para mantener el flujo de datos, mientras que la normalización se aplica solo cuando se duplican múltiples puntos simultáneamente para maximizar el paralelismo.
   • Multiplicación Escalar: La implementación vectoriza la escalera de Montgomery, la escalera de tres puntos y la escalera bidimensional (LadderBiscalar). Una contribución clave es una estrategia de vectorización de cuatro vías rediseñada para la función xDBLADD que acomoda el formato de parámetros general $(A_{24}:C_{24})$ utilizado en la criptografía basada en isogenias, evitando las dependencias de forma especial de intentos de vectorización previos.
   • Emparejamientos (Pairings): El artículo aborda los cálculos de emparejamiento de Tate-Lichtenbaum utilizados para la generación de bases. Al fusionar un doble de punto con dos adiciones diferenciales, los autores crearon un algoritmo cubicalDBLADDADD que genera los emparejamientos requeridos utilizando tres multiplicaciones paralelas de cuatro vías y un cuadrado paralelo de cuatro vías.

3. Evaluaciones de Isogenia:

   • Dimensión 1 y 2: Los autores aplicaron estrategias de loteo (batching) a las evaluaciones de isogenia. En lugar de procesar puntos secuencialmente, entrelazan las coordenadas de múltiples puntos a través de los carriles AVX-512 para saturar los multiplicadores SIMD. Este enfoque se aplica tanto a las 4-isogenias en curvas elípticas como a las $(2,2)$-isogenias en superficies abelianas (PPAS), utilizando aritmética de coordenadas theta.

4. Contexto de Arquitectura:

   • El artículo aborda las concepciones erróneas sobre la obsolescencia de AVX-512, señalando que la próxima arquitectura AVX10 de Intel (revisión 10.2, programada para finales de 2026) estandarizará estas capacidades tanto en núcleos de rendimiento como de eficiencia, asegurando la viabilidad a largo plazo.

Contribuciones Clave

1. Vectorización Integral de las Operaciones del Lado de la Curva de SQIsign: El trabajo proporciona la primera vectorización completa de los componentes del "lado de la curva" de SQIsign utilizando AVX-512IFMA, cubriendo aritmética de campos primos, extensiones cuadráticas, operaciones de curva elíptica (incluyendo multiplicación escalar y emparejamientos) y evaluaciones de isogenia tanto en una como en dos dimensiones. Los componentes de álgebra de cuaterniones permanecen escalares.
2. Análisis de Vectorización Extendido en x86-64: A diferencia de los esfuerzos previos de vectorización basados en ARM (por ejemplo, De Feo et al. usando NEON), este trabajo explora un rango significativamente más amplio de funciones en la plataforma x86-64, incluyendo estrategias complejas de multiplicación escalar y operaciones de coordenadas theta. Los diseños algorítmicos se consideran agnósticos a la arquitectura, ofreciendo una base para la migración a otras plataformas SIMD como ARM SVE o RISC-V.
3. Optimizaciones Generalizables: Las técnicas desarrolladas para el doble de puntos, la multiplicación escalar por lotes y la aritmética de puntos theta vectorizada se presentan como fundamentos metodológicos aplicables a otros criptosistemas basados en isogenias que utilizan variedades abelianas de mayor dimensión, independientemente de las variantes específicas de SQIsign.

Resultados Experimentales

La implementación fue evaluada mediante pruebas de rendimiento en una CPU Intel Core i7-11700F (2.50GHz) ejecutando Ubuntu 24.04. Los resultados se comparan con la implementación de referencia oficial (optimizada para Broadwell con limb de 64 bits).

• Ganancias de Rendimiento:
  • Generación de Claves: Aceleraciones que van desde $1.03\times$ hasta $1.28\times$.
  • Firma (Signing): Aceleraciones que van desde $1.08\times$ hasta $1.26\times$.
  • Verificación: Aceleraciones que van desde $1.46\times$ hasta $1.84\times$.
• Combinado con Qlapoti: Al combinarse con la tecnología Qlapoti, la implementación logra una aceleración de $2.69\times$ para la firma y una mejora de $3.18\times$ para la verificación en el nivel de seguridad I de NIST.
• Disparidad de Verificación: El artículo observa que la verificación se beneficia más significativamente que la firma porque la verificación depende exclusivamente de las operaciones vectorizadas del lado de la curva, mientras que la firma aún involucra operaciones de álgebra de cuaterniones que actualmente se ejecutan mediante GMP escalar (un componente no optimizado en este trabajo).

Significado y Reivindicaciones

Los autores afirman que este trabajo demuestra que la vectorización SIMD representa una dimensión de optimización crítica pero poco explorada para los esquemas basados en isogenias post-cuánticos.

• Independencia de los Avances Algorítmicos: Las optimizaciones son ortogonales a los recientes refinamientos algorítmicos de alto nivel (como Qlapoti o Superglue). Esto implica que las ganancias de rendimiento logradas mediante la vectorización son multiplicativas; las futuras innovaciones a nivel de protocolo pueden aplicarse sobre esta base vectorizada para acumular mejoras de rendimiento.
• Viabilidad a Largo Plazo: Al enfatizar la estandarización de las capacidades de AVX-512 en las futuras arquitecturas de Intel (AVX10), el artículo argumenta que estas técnicas de optimización no son un arreglo temporal, sino un camino sostenible para una criptografía basada en isogenias eficiente.
• Universalidad: Se afirma que la metodología es aplicable a diversas construcciones basadas en isogenias (por ejemplo, SQIsignHD, SQIsign2D-East, SQIPrime) porque todas ellas dependen de los mismos primitivos subyacentes (aritmética de $\mathbb{F}_{p^2}$, coordenadas theta y operaciones de curva elíptica) que son los objetivos de esta optimización.

El artículo concluye que, si bien el "lado de los cuaterniones" de SQIsign sigue siendo un cuello de botella escalar, la vectorización del "lado de la curva" cierra significativamente la brecha entre la compacidad teórica y la eficiencia de despliegue práctico.