PIP-NTT: Towards a Scalable Memory-Parallelized Accelerator for Iterative NTT in PQC

Resumo Técnico: PIP-NTT: Rumo a um Acelerador de Memória Paralelizada e Escalável para NTT Iterativa em PQC

Declaração do Problema
A Criptografia Pós-Quântica (PQC) baseada em redes, especificamente esquemas como ML-KEM (Kyber) e ML-DSA (Dilithium) padronizados pelo NIST, depende fortemente da Transformada Numérica de NTT (Number Theoretic Transform) para multiplicação de polinômios eficiente. Os aceleradores de hardware existentes para NTT iterativa enfrentam um compromisso entre throughput e utilização de recursos. Projetos de alto throughput empregam pipelining profundo e grandes matrizes de memória ou múltiplas unidades butterfly, o que acarreta uma sobrecarga de área substancial, inadequada para plataformas com restrição de recursos. Por outro lado, projetos otimizados para área frequentemente dependem de esquemas de memória "ping-pong" e unidades butterfly únicas. Embora esses reduzam a pegada de hardware, eles inerentemente limitam a escalabilidade, o paralelismo e a otimização de frequência, criando gargalos de desempenho. Além disso, a etapa de redimensionamento (rescaling) exigida após a NTT Inversa (INTT) frequentemente envolve multiplicação ou divisão modular dispendiosas, adicionando ao atraso do caminho crítico.

Metodologia
Os autores propõem o "PIP-NTT", um acelerador de NTT unificado, pipelined e com paralelismo de memória, projetado para equilibrar eficiência de área com throughput computacional. A metodologia é construída sobre três inovações principais:

1. Unidade Butterfly Unificada e Pipelined (DSE): Os autores realizaram uma Exploração de Espaço de Design (DSE) abrangente de unidades butterfly de Cooley–Tukey (CT) e Gentleman–Sande (GS). Eles avaliaram oito variantes arquiteturais, variando de uma base não-pipelined até designs utilizando pipelining de grão grosso e fino. O design ideal, uma unidade butterfly com 8 estágios de pipeline (8SP-BU), integra redução modular (usando o método de Barrett) e operações aritméticas com registradores posicionados estrategicamente dentro do caminho de dados para maximizar a frequência de operação enquanto minimiza a sobrecarga de área.
2. Redimensionamento Livre de Multiplicação: Para a etapa de redimensionamento da INTT ($a \cdot n^{-1} \mod q$), os autores exploram a congruência específica do módulo do Kyber ($q=3329$), onde $n^{-1} \equiv -13 \pmod{3329}$. Em vez de um circuito de shift-add complexo ou divisão, eles implementam uma arquitetia leve usando duplicações e adições modulares para computar $13a$, seguida de uma negação condicional. Isso elimina a necessidade de um multiplicador de propósito geral nesta etapa.
3. Estratégia de Paralelismo de Memória: Para superar as limitações dos esquemas tradicionais de memória ping-pong sem aumentar a pegada total de memória, os autores introduzem uma técnica usando quatro blocos de memória menores (cada um de tamanho $n/4$) em vez de dois blocos maiores. Os coeficientes são armazenados em pares adjacentes. Uma rede de swap baseada em multiplexadores reordena as saídas com base no offset da etapa atual ($\delta$). Isso permite que duas unidades butterfly operem concorrentemente. Quando o offset é grande ($\delta \ge n/4$), todos os quatro blocos de memória e ambas as unidades butterfly são utilizados; quando o offset é pequeno ($\delta < n/4$), o sistema alcança paralelismo parcial com dois blocos ativos. Esta estratégia reduz pela metade os ciclos de clock em comparação com designs iterativos de unidade única, mantendo a mesma capacidade total de memória.

Principais Contribuições

• Arquitetura Butterfly Otimizada: Uma unidade butterfly CT/GS unificada alcançando um aumento de frequência de 46 MHz (baseline) para 298 MHz através de pipelining de grão fino, com apenas 1,32× de sobrecarga de área.
• Redimensionamento Eficiente: Uma arquitetura de redimensionamento livre de multiplicação para a INTT que reduz o uso de Slice e LUT em 1,67× e 1,84×, respectivamente, em comparação com uma implementação padrão de 7 termos de shift-add.
• Paralelismo de Memória Escalável: Uma organização de memória inovadora usando quatro blocos de tamanho $n/4$ e uma rede de swap para permitir paralelismo parcial na NTT iterativa, reduzindo os ciclos de clock em 50% sem aumentar o custo total de memória.
• Acelerador Integrado (PIP-NTT): Uma implementação completa em FPGA do PIP-NTT integrando duas unidades butterfly otimizadas e o esquema de paralelismo de memória, suportando tanto transformadas Diretas (FNTT) quanto Inversas (INTT) para parâmetros do Kyber ($n=256, q=3329$).

Resultados Experimentais
O design PIP-NTT foi implementado nas plataformas FPGA Xilinx Virtex-7 e Artix-7.

• Desempenho: O acelerador opera a 200 MHz, computando uma única FNTT ou INTT em 2,60 µs (520 ciclos de clock).
• Eficiência: Em termos de Produto Área-Tempo (ATP), o PIP-NTT alcança:
  • 2,67× mais eficiência comparado aos aceleradores de NTT mais otimizados em área na literatura.
  • 1,48× mais eficiência comparado aos aceleradores de NTT de maior velocidade.
• Uso de Recursos: O design utiliza 156 slices, 426 LUTs e 379 Flip-Flops no Virtex-7, demonstrando uma pegada altamente compacta em relação ao seu throughput.

Significância e Alegações
O artigo afirma que o PIP-NTT oferece uma solução versátil para futuros hardwares criptográficos ao abordar efetivamente os compromissos de escalabilidade e eficiência inerentes aos designs de NTT iterativa. Ao desacoplar o paralelismo do custo total de memória através da proposta estratégia de paralelismo de memória, o design permite alto throughput sob rigorosas restrições de área. Os autores enfatizam que a arquitetura não é limitada ao Kyber; a natureza agnóstica a radix e ao esquema da estratégia de memória e o design modular da unidade butterfly permitem a adaptação para outros esquemas de PQC (como Dilithium) e variações de tamanhos de anel com modificações mínimas. O trabalho posiciona o PIP-NTT como uma abordagem equilibrada e eficiente em recursos, adequada para diversos cenários de implantação, de sistemas embarcados a data centers.