Resumo Técnico: Implementação Vetorizada de SQIsign Utilizando AVX-512

Declaração do Problema

O SQIsign é o único esquema de assinatura baseado em isogenia submetido ao processo de padronização de Criptografia Pós-Quântica do NIST. Embora ofereça tamanhos compactos de chave e assinatura baseados na dureza do problema do anel de endomorfismos para curvas elípticas supersingulares, sua implementação prática é atualmente dificultada por procedimentos de assinatura computacionalmente intensivos. O gargalo de desempenho reside primariamente nos componentes do "lado da curva" (curve-side), que incluem aritmética extensa sobre grandes corpos primos ($\mathbb{F}_p$) e suas extensões quadráticas ($\mathbb{F}_{p^2}$), operações de curva elíptica (dobra de pontos e multiplicação escalar) e avaliações de isogenia de dimensões superiores sobre superfícies abelianas polarizadas principalmente (PPAS). As implementações de referência existentes dependem fortemente de aritmética escalar, utilizando frequentemente a biblioteca GNU Multiple Precision Arithmetic Library (GMP) para componentes de álgebra de quatérnios, o que limita o rendimento (throughput).

Metodologia

Este artigo apresenta a primeira implementação vetorizada abrangente dos componentes do "lado da curva" do SQIsign utilizando a arquitetura de conjunto de instruções AVX-512 Integer Fused Multiply-Add (IFMA). Os autores redesenharam sistematicamente a pilha computacional para explorar o paralelismo SIMD (Single Instruction, Multiple Data) em todas as principais camadas algorítmicas, enquanto observam explicitamente que os componentes de álgebra de quatérnios (IdealToIsogeny) permanecem escalares e não otimizados neste trabalho.

Estratégias Técnicas Principais

1. Aritmética de Corpo Finito ($\mathbb{F}_p$ e $\mathbb{F}_{p^2}$):

   • Representação: A implementação adota uma representação de radix-$2^{51}$ para elementos de corpo, decompondo-os em cinco membros (limbs) de 51 bits. Este tamanho foi escolhido para caber dentro das faixas inferiores de 52 bits de canais de 64 bits, evitando overflow durante as operações IFMA, ao mesmo tempo em que reserva espaço para redução diferida.
   • Paralelização: Uma estratégia de paralelização $(8 \times 1)$ é empregada na camada $\mathbb{F}_p$, processando oito elementos de corpo independentes simultaneamente dentro de um único registrador ZMM de 512 bits.
   • Extensões: Para $\mathbb{F}_{p^2}$, os autores implementam três padrões distintos de paralelização — $(8 \times 1 \times 1)$, $(4 \times 2 \times 1)$ e $(2 \times 4 \times 1)$ — para equilibrar o rendimento e a pressão de registradores dependendo dos requisitos algorítmicos específicos (ex: operações em lote vs. paralelismo de componentes internos).
   • Instruções: O design aproveita as instruções vpmadd52luq e vpmadd52huq para executar multiplicações paralelas de $52 \times 52$ bits com capacidades de multiply-add fundido, reduzindo significativamente as contagens de instruções para multiplicação de Montgomery e propagação de carry.

2. Operações de Curva Elíptica:

   • Dobra de Pontos (Point Doubling): Os autores otimizaram a dobra de pontos tanto para coordenadas apenas-$x$ (curvas de Montgomery) quanto para coordenadas projetivas completas (Jacobianas e Jacobianas Modificadas). Para coordenadas apenas-$x$, eles consistentemente omitem etapas de normalização em contextos vetorizados para manter o fluxo de dados, enquanto a normalização é aplicada apenas quando múltiplos pontos são dobrados simultaneamente para maximizar o paralelismo.
   • Multiplicação Escalar: A implementação vetoriza a escada de Montgomery (Montgomery ladder), a escada de três pontos e a escada de duas dimensões (LadderBiscalar). Uma contribuição fundamental é uma estratégia de vetorização de quatro vias redesenhada para a função xDBLADD que acomoda o formato de parâmetro geral $(A_{24}:C_{24})$ usado em criptografia baseada em isogenia, evitando as dependências de forma especial de tentativas de vetorização anteriores.
   • Pairings (Emparelhamentos): O artigo aborda os cálculos de emparelhamento de Tate-Lichtenbaum usados para geração de base. Ao fundir uma dobra de ponto com duas adições diferenciais, os autores criaram um algoritmo cubicalDBLADDADD que gera os emparelhamentos necessários usando três multiplicações paralelas de quatro vias e um quadrado paralelo de quatro vias.

3. Avaliações de Isogenia:

   • Dimensão 1 & 2: Os autores aplicaram estratégias de lote (batching) para avaliações de isogenia. Em vez de processar pontos sequencialmente, eles intercalam coordenadas de múltiplos pontos através de canais AVX-512 para saturar multiplicadores SIMD. Esta abordagem é aplicada tanto a 4-isogenias em curvas elípticas quanto a $(2,2)$-isogenias em superfícies abelianas (PPAS), utilizando aritmética de coordenadas theta.

4. Contexto de Arquitetura:

   • O artigo aborda equívocos sobre a obsolescência do AVX-512, observando que a futura arquitetura Intel AVX10 (revisão 10.2, programada para o final de 2026) padronizará essas capacidades tanto em núcleos de performance quanto de eficiência, garantindo viabilidade a longo prazo.

Principais Contribuições

1. Vetorização Abrangente das Operações do Lado da Curva do SQIsign: O trabalho fornece a primeira vetorização completa dos componentes do "lado da curva" do SQIsign usando AVX-512IFMA, cobrindo aritmética de corpo primo, extensões quadráticas, operações de curva elíptica (incluindo multiplicação escalar e emparelhamentos) e avaliações de isogenia tanto em uma quanto em duas dimensões. Os componentes de álgebra de quatérnios permanecem escalares.
2. Análise de Vetorização Estendida em x86-64: Diferente de esforços anteriores de vetorização baseados em ARM (ex: De Feo et al. usando NEON), este trabalho explora uma gama significativamente mais ampla de funções na plataforma x86-64, incluindo estratégias complexas de multiplicação escalar e operações de coordenadas theta. Os designs algorítmicos são notados como agnósticos à arquitetura, oferecendo uma base para migração para outras plataformas SIMD como ARM SVE ou RISC-V.
3. Otimizações Generalizáveis: As técnicas desenvolvidas para dobra de pontos, multiplicação escalar em lote e aritmética de ponto theta vetorizada são apresentadas como fundamentos metodológicos aplicáveis a outros criptossistemas baseados em isogenia que utilizam variedades abelianas de dimensões superiores, independentemente de variantes específicas do SQIsign.

Resultados Experimentais

A implementação foi testada em um processador Intel Core i7-11700F (2.50GHz) rodando Ubuntu 24.04. Os resultados são comparados com a implementação de referência oficial (otimizada para Broadwell com membros de 64 bits).

• Ganhos de Desempenho:
  • Geração de Chave (Key Generation): Acelerações variando de $1.03\times$ a $1.28\times$.
  • Assinatura (Signing): Acelerações variando de $1.08\times$ a $1.26\times$.
  • Verificação (Verification): Acelerações variando de $1.46\times$ a $1.84\times$.
• Combinado com Qlapoti: Quando combinado com a tecnologia Qlapoti, a implementação alcança um ganho de velocidade de $2.69\times$ para assinatura e uma melhoria de $3.18\times$ para verificação no nível de segurança NIST I.
• Disparidade de Verificação: O artigo observa que a verificação se beneficia mais significativamente do que a assinatura porque a verificação depende exclusivamente das operações vetorizadas do lado da curva, enquanto a assinatura ainda envolve operações de álgebra de quatérnios executadas via GMP escalar (um componente não otimizado neste trabalho).

Significância e Alegações

Os autores alegam que este trabalho demonstra que a vetorização SIMD representa uma dimensão de otimização crítica, porém subexplorada, para esquemas baseados em isogenia pós-quânticos.

• Independência de Avanços Algorítmicos: As otimizações são ortogonais aos recentes refinamentos algorítmicos de alto nível (como Qlapoti ou Superglue). Isso implica que os ganhos de desempenho alcançados através da vetorização são multiplicativos; futuras inovações de nível de protocolo podem ser aplicadas sobre esta base vetorizada para potencializar os ganhos de desempenho.
• Viabilidade a Longo Prazo: Ao enfatizar a padronização das capacidades AVX-512 nas futuras arquiteturas Intel (AVX10), o artigo argumenta que estas técnicas de otimização não são uma correção temporária, mas um caminho sustentável para uma criptografia baseada em isogenia eficiente.
• Universalidade: A metodologia é alegada como aplicável a várias construções baseadas em isogenia (ex: SQIsignHD, SQIsign2D-East, SQIPrime) porque todas elas dependem dos mesmos primitivos ($\mathbb{F}_{p^2}$ arithmetic, coordenadas theta e operações de curva elíptica) que são os alvos desta otimização.

O artigo conclui que, embora o "lado do quatérnio" do SQIsign permaneça um gargalo escalar, a vetorização do "lado da curva" reduz significativamente a lacuna entre a compacidade teórica e a eficiência de implantação prática.