Implementation and Optimization of HQC Decoding on NPU-Integrated Devices

Definição do Problema

O Hamming Quasi-Cyclic (HQC) foi selecionado pelo NIST como um Mecanismo de Encapsulamento de Chave (KEM) baseado em códigos para fornecer diversidade algorítmica junto à criptografia pós-quântica baseada em reticulados (lattices). Embora o HQC dependa de códigos de correção de erros (especificamente códigos Reed-Muller e Reed-Solomon concatenados) para segurança, sua implementação prática em plataformas móveis e embarcadas é dificultada pelo alto custo computacional de seu procedimento de decodificação.

Implementações existentes em CPUs restritas ou hardware especializado (FPGAs, RISC-V) mostraram que o desempenho do HQC é fortemente dependente de como os kernels de decodificação são mapeados para o backend de execução. No entanto, as plataformas móveis modernas integram cada vez mais Unidades de Processamento Neural (NPUs) com aceleradores vetoriais (como o Qualcomm Hexagon Vector eXtensions, ou HVX) projetados primariamente para IA e processamento de sinais. O desafio abordado neste trabalho é que a decodificação do HQC não pode ser acelerada eficientamente por uma tradução direta de decodificadores escalares para esses backends vetoriais. O processo de decodificação envolve dependências de dados complexas, regras de desempate específicas e padrões de acesso à memória irregulares (por exemplo, em FFTs aditivas) que não se alinham naturalmente com a execução vetorial do tipo SIMD.

Metodologia

Os autores propõem uma implementação de decodificação HQC otimizada de ponta a ponta visando o backend vetorial Hexagon/HVX em dispositivos Qualcomm integrados com NPU. Em vez de usar um motor de inferência de tensores, o trabalho foca no modelo de execução vetorial, que suporta operações SIMD largas, aritmética por lane e reduções.

A metodologia envolve a decomposição do decodificador HQC em seus componentes constituintes Reed-Muller (interno) e Reed-Solomon (externo) e o redesenho dos kernels dominantes para se adequarem aos layouts de dados e padrões de execução amigáveis ao HVX:

1. Otimização da Decodificação Reed-Muller:

   • Transformada de Hadamard Vetorizada: Os autores redesenham a transformada de Hadamard rápida para o código Reed-Muller duplicado interno. Eles utilizam intrinsics de HVX (ex: VDEALH, VADDH, VSUBH) para realizar adições e subtrações paralelas por lane, substituindo os estágios de butterfly sequenciais da implementação escalar.
   • Seleção de Pico Equivalente a Escalar: Um desafio crítico é preservar a regra de desempate do decodificador escalar (selecionar o menor índice entre coeficientes com mesma magnitude máxima). Os autores implementam uma busca vetorizada que computa magnitudes, identifica todos os candidatos a pico e realiza uma redução de mínimo vetorial nos índices candidatos para garantir a equivalência bit a bit com a referência escalar.

2. Otimização da Decodificação Reed-Solomon:

   • Aritmética de Campo Finito Orientada para HVX: Para operações vetorizadas (computação de síndrome e busca de Chien), os autores substituem a multiplicação escalar baseada em tabelas por um método de Horner bit-serial usando primitivas xtime. Isso permite a multiplicação escalar-por-vetor através das lanes do HVX sem depender de grandes tabelas de busca que causariam falhas de cache ou exigiriam indexação complexa.
   • Computação de Síndrome Vetorizada: Em vez de computar síndromes sequencialmente, a implementação empacota potências do elemento primitivo em vetores e acumula os resultados via operações XOR em todos os índices de síndrome simultaneamente.
   • Busca de Chien de Suporte Encurtado: Reconhecendo que a FFT aditiva usada em implementações escalares possui dependências sequenciais inadequadas para o HVX, os autores a substituem por uma busca de Chien de suporte encurtado. Este método avalia o polinômio localizador de erro sobre pontos de suporte públicos usando vetores empacotados, permitindo a avaliação paralela através das lanes do HVX enquanto mantém a natureza sequencial dos coeficientes do polinômio.
   • Tratamento de Berlekamp-Massey: A computação do polinômio localizador de erro (algoritmo Berlekamp-Massey) é inerentemente sequencial e curta (máximo de 16 coeficientes para HQC-128). Os autores mantêm esta etapa como escalar, mas otimizam suas multiplicações de campo finito usando métodos de logaritmo/antilogaritmo baseados em tabelas, já que a vetorização traz pouco benefício para loops tão curtos.

3. Integração do Sistema:

   • A implementação roda em um kit de desenvolvimento Snapdragon 8 Gen 2 usando a interface FastRPC para descarregar tarefas do host CPU para o cDSP (Hexagon DSP).
   • Para mitigar o alto overhead de inicialização do FastRPC (aprox. 557 µs), os autores empregam uma estratégia de lote (batching), processando múltiplas instâncias de decodificação em uma única chamada remota para amortizar o custo de comunicação.

Principais Contribuições

• Identificação de Adequação Vetorial: O artigo estabelece que a decodificação HQC é um candidato natural para aceleração Hexagon/HVX devido à estrutura vetorial inerente de seus vetores de confiabilidade, coeficientes de Hadamard e vetores de síndrome.
• Redesenho de Kernel: Os autores apresentam um redesenho completo dos kernels de decodificação dominantes:
  • Uma transformada de Hadamard Reed-Muller vetorizada e seleção de pico que preserva estritamente as regras de desempate escalares.
  • Multiplicação de campo finito e computação de síndrome orientadas para HVX.
  • Uma busca de Chien de suporte encurtado vetorizada que substitui a FFT aditiva escalar.
• Avaliação de Desempenho: O trabalho fornece uma avaliação abrangente usando tanto o simulador preciso de ciclos do Hexagon quanto experimentos em dispositivo real no Snapdragon 8 Gen 2.
• Escalabilidade: Os princípios de otimização são demonstrados para se estender do HQC-128 para HQC-192 e HQC-256, com ajustes para tamanhos de bloco e acumulação multi-vetor para conjuntos de suporte maiores.

Resultados

A avaliação demonstra melhorias substanciais em latência, eficiência energética e offloading da CPU host:

• Resultados do Simulador (HQC-128): A implementação otimizada reduz o custo de decodificação de 953.763 para 41.471 Pcycles por decodificação, representando um ganho de velocidade de 23,00× e uma redução de 95,7% nos ciclos do processador. A análise de subestágios mostra ganhos massivos, como a redução da transformada de Hadamard Reed-Muller de 263.175 para 17.950 Pcycles.
• Resultados em Dispositivo Real (Snapdragon 8 Gen 2):
  • Latência: O backend suportado por NPU com loteamento (batching) atinge ganhos de latência de 2,07× (HQC-128), 1,85× (HQC-192) e 1,96× (HQC-256) comparado à linha de base escalar da CPU ARM.
  • Eficiência Energética: A implementação melhora a eficiência energética em 18,13× (HQC-128), 11,77× (HQC-192) e 16,81× (HQC-256).
  • Offloading da CPU: O tempo de CPU host por decodificação é reduzido em 99,0%–99,7%, liberando efetivamente o processador de aplicação para outras tarefas enquanto a decodificação roda no cDSP.
• Nota de Overhead: Os autores observam que o custo da fronteira FastRPC é significativo (~531–553 µs por chamada). Os ganhos relatados em dispositivo real são alcançados especificamente através do loteamento (batching) de múltiplas decodificações em uma única chamada; uma abordagem de "uma decodificação por chamada" seria significativamente mais lenta (5,4× a 15× mais lenta) devido a este overhead.

Significância e Alegações

O artigo afirma que plataformas móveis integradas com NPU podem servir como backends eficazes para decodificação criptográfica pós-quântica estruturada, desde que os kernels subjacentes sejam reformulados em torno do modelo de execução vetorial disponível.

• Diversidade Algorítmica: O trabalho apoia o objetivo do NIST de diversidade criptográfica ao demonstrar que esquemas baseados em códigos como o HQC podem ser implantados eficientmente em hardware móvel moderno, não apenas esquemas baseados em reticulados.
• Utilização de Hardware: Destaca que aceleradores vetoriais (HVX), frequentemente reservados para IA, são bem adequados para primitivas criptográficas com estruturas de dados regulares, ofereção um caminho para segurança pós-quântica eficiente em dispositivos de consumo sem a necessidade de hardware criptográfico dedicado.
• Modéstia sobre Segurança: Os autores declaram explicitamente que sua implementação atual não é de tempo constante (constant-time). Eles reconhecem que o uso de aritmética de campo finito baseada em tabelas e a lógica de Berlekamp-Massey com ramificações introduzem potenciais vulnerabilidades de canal lateral (tempo e potência). Eles enquadram isso como uma otimização focada em desempenho, deixando o desenvolvimento de um backend totalmente de tempo constante e resistente a canais laterais como trabalho futuro.
• Trabalho Futuro: Os autores identificam a integração destas otimizações de decodificação com a multiplicação de polinômios esparsos acelerada (o outro grande custo na decapsulação HQC) como o próximo passo lógico para a aceleração total da decapsulação.