💻 computer science

GPU Acceleration of Learning With Errors KEMs Using OpenACC for Post-Quantum Cryptography

Este artigo apresenta uma implementação acelerada por GPU de um Mecanismo de Encapsulamento de Chave baseado em Learning with Errors (LWE) usando OpenACC, demonstrando acelerações significativas (até 208×) e melhor eficiência energética em GPUs NVIDIA, particularmente no Grace Hopper Superchip, em comparação com sistemas tradicionais baseados em CPU e H100.

Autores originais: Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

Publicado 2026-06-02

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando trancar um baú de tesouro com uma chave tão complexa que nem mesmo um robô superinteligente do futuro (um computador quântico) conseguiria abrir. Este é o objetivo da Criptografia Pós-Quântica. O "cadeado" específico em que este artigo se concentra é chamado de Aprendizado com Erros (Learning With Errors - LWE).

Pense no LWE como tentar resolver um enorme quebra-cabeça matemático onde alguém adicionou intencionalmente um pouco de "estática" ou "ruído" ao sinal. É fácil criar o ruído, mas incrivelmente difícil filtrá-lo para encontrar a mensagem original sem a chave secreta. O problema é que resolver esse quebra-cabeça em um computador padrão é como tentar mover uma montanha grão de areia por vez — leva uma eternidade.

Aqui está o que os pesquisadores fizeram para acelerar isso, explicado de forma simples:

1. O Problema: A CPU é o Caminhão Lento

Os autores começaram com uma versão desta criptografia que roda em um processador de computador padrão (a CPU). Eles descobriram que a CPU estava com dificuldades. Era como um único caminhão de entrega tentando mover milhares de caixas. Cada vez que precisava mover uma caixa (um pedaço de dado) do armazém (memória) para a carroceria do caminhão, ele tinha que parar, carregar e dirigir. O caminhão passava a maior parte do tempo esperando, não trabalhando.

2. A Solução: A GPU é a Frota de Drones

Para resolver isso, eles transferiram o trabalho pesado para uma GPU (Unidade de Processamento Gráfico). Se a CPU é um único caminhão de entrega, a GPU é uma frota de milhares de pequenos drones super-rápidos.

A Analogia: Em vez de um caminhão carregando uma caixa por vez, a GPU pode carregar milhares de caixas simultaneamente.
A Ferramenta: Eles usaram uma linguagem de programação chamada OpenACC. Pense nisso como um controle remoto universal. Em vez de reescrever todo o manual de instruções para os drones (o que seria difícil e propenso a erros), eles apenas apontaram o controle remoto para as instruções existentes do caminhão e disseram: "Ei, você faz essa parte também, mas de forma mais rápida!" Isso tornou fácil atualizar o software sem quebrá-lo.

3. O Gargalo: O Gerador de "Ruído"

Nesta criptografia, você precisa de muito "ruído" aleatório para tornar o quebra-cabeça difícil.

O Jeito Antigo: A CPU gerava o ruído, escrevia-o e depois o levava até a GPU. Isso era como o motorista do caminhão parando para escrever uma lista de compras, dirigindo até a loja, comprando os itens e voltando. Isso desperdiçava muito tempo.
A Correção: Eles instalaram um "gerador de ruído" diretamente dentro do armazém da GPU. Agora, os drones podem gerar seu próprio ruído aleatório no local. Eles não precisam esperar que o caminhão traga para eles. Isso reduziu drasticamente o tempo de espera.

4. O Truque do "Agrupamento" (Batching)

O processo de criptografia envolve resolver 256 pequenos quebra-cabeças de uma vez (um para cada bit de uma mensagem).

O Jeito Antigo: A GPU resolvia um quebra-cabeça, parava, esperava instruções, resolvia o próximo, parava, esperava... como um chef cozinhando um ovo de cada vez e esperando o fogão esfriar entre cada um.
A Correção: Eles usaram uma estratégia chamada Agrupamento Intra-Operação (Intra-Operation Batching). Isso é como o chef colocando todos os 256 ovos em uma panela gigante de uma só vez e cozinhando todos juntos. A GPU faz um grande "lançamento" para resolver todos os 256 quebra-cabeças simultaneamente, economizando uma quantidade massiva de tempo.

5. Os Resultados: Velocidade e Energia

Os pesquisadores testaram isso em diferentes tipos de computadores super-rápidos (GPUs) e compararam com o antigo método da CPU.

Velocidade: No computador mais novo e poderoso que testaram (o Superchip Grace Hopper), o novo método deles foi 208 vezes mais rápido do que o antigo método da CPU.
- Analogia: Se o antigo caminhão levava 3 horas para entregar um pacote, a nova frota de drones faz isso em menos de um minuto.
- Eles foram capazes inclusive de resolver tamanhos de quebra-cabeças tão grandes que a antiga CPU ficaria sem memória e travaria.
Energia: O novo método também utilizou menos energia. O computador Grace Hopper usou cerca de metade da energia para fazer o mesmo trabalho em comparação com um computador padrão com um tipo diferente de GPU rápida.
- Analogia: É como fazer a mesma entrega usando um carro híbrido em vez de um caminhão gastador de combustível.

6. Por Que Isso Importa

O artigo mostra que, ao usar esses "drones" (GPUs) e truques inteligentes de gestão (OpenACC, agrupamento e ruído no dispositivo), podemos tornar esses cadeados superseguros e à prova de computação quântica práticos para uso. Sem esses ganhos de velocidade, a matemática é lenta demais para ser útil no mundo real. Com eles, podemos proteger nossos dados contra futuros computadores quânticos sem ter que esperar dias para que um único cadeado se feche.

Em resumo: Eles pegaram um método de criptografia lento e pesado e deram a ele um enorme impulso de velocidade ao usar milhares de pequenos trabalhadores (GPUs) que trabalham juntos, geram seus próprios suprimentos e param de esperar por instruções. O resultado é um sistema que é centenas de vezes mais rápido e muito mais eficiente em termos de energia.

Resumo Técnico: Aceleração de GPU de KEMs baseados em Learning With Errors usando OpenACC

Declaração do Problema
O advento de computadores quânticos de grande escala ameaça os atuais protocolos criptográficos assimétricos (ex: RSA, ECC) por meio do algoritmo de Shor. A Criptografia Pós-Quântica (PQC) emergiu como uma solução, com esquemas baseados em reticulados (lattice-based), particularmente aqueles que dependem do problema Learning With Errors (LWE), sendo centrais para Mecanismos de Encapsulamento de Chave (KEMs). No entanto, os esquemas baseados em LWE introduzem um overhead computacional significativo devido a operações matriciais de grande escala e geração de aleatoriedade, tornando-os frequentemente impraticáveis para aplicações de alto rendimento (throughput) no lado do servidor em arquiteturas padrão de CPU. Embora a aceleração por GPU tenha sido explorada para PQC, a maioria das implementações existentes depende de otimizações específicas de CUDA, limitando a portabilidade e a produtividade do desenvolvedor. Além disso, a portabilidade ingênua muitas vezes falha ao não abordar gargalos como a latência de transferência de memória host-device e a serialização da geração de números aleatórios.

Metodologia
Os autores propõem um Mecanismo de Encapsulamento de Chave (KEM) baseado em "LWE puro" (evitando estruturas algébricas adicionais como Ring-LWE) e desenvolvem uma implementação orientada para GPU utilizando o modelo de programação baseado em diretivas OpenACC. O trabalho procede através das seguintes etapas metodológicas:

Implementação de Linha de Base (Baseline): Uma implementação em C++ do LWE-KEM foi paralelizada usando OpenMP para CPUs multicore. O esquema utiliza a transformada Fujisaki-Okamoto (FO) para alcançar segurança IND-CCA2, envolvendo as fases de KeyGen, Encaps e Decaps.
Portabilidade e Otimização OpenACC: O código de CPU foi portado para GPUs usando OpenACC. Para superar gargalos de desempenho, os autores implementaram três estratégias primárias:
- Agrupamento Intra-Operação (Intra-Operation Batching): Em vez de processar 256 bits de mensagens independentes sequencialmente (o que dispararia lançamentos de kernel e transferências de memória separados), a implementação funde todas as 256 criptografias em um único lançamento de kernel de GPU. Isso expõe um paralelismo de grão fino ( $256 \times n$ itens de trabalho) e amortiza o overhead de invocação.
- Geração de Números Aleatórios Residente no Dispositivo (Device-Resident RNG): Reconhecendo que a transferência de vetores de ruído aleatório via PCIe cria um gargalo severo, os autores integraram a biblioteca RNGonGPU. Esta biblioteca implementa um Gerador de Bits Aleatórios Determinístico (DRBG) AES-256 diretamente na GPU. Apenas uma semente de 64 bits é transferida do host para o dispositivo, reduzindo o volume de transferência de dados em aproximadamente seis ordens de magnitude em comparação com a transferência de vetores de ruído pré-gerados.
- Gerenciamento Explícito de Dados: Os autores evitaram a Memória Unificada do CUDA em favor de diretivas explícitas enter data e exit data para controlar as transferências host-device de forma determinística, minimizando comunicações desnecessárias e garantindo a consistência dos dados apenas em pontos de sincronização específicos (ex: antes do hashing).
Paralelização de Kernel: As multiplicações matriz-vetor, o custo computacional dominante, foram paralelizadas hierarquicamente. Para criptografia/descriptografia, criptografias de mensagens independentes foram atribuídas a gangs do OpenACC, enquanto os componentes do texto cifrado foram computados concorrentemente através de lanes de vetor.

Principais Contribuições

Implementação de Código Aberto: Os autores fornecem uma implementação de código aberto de um KEM baseado em LWE puro tanto para CPU (OpenMP) quanto para GPU (OpenACC), permitindo benchmarks reproduzíveis.
Otimização Baseada em Diretivas: Um conjunto de otimizações orientadas para GPU aplicáveis a uma ampla classe de esquemas LWE, demonstrando que modelos baseados em diretivas (OpenACC) podem alcançar alto desempenho sem a necessidade de conhecimento profundo em CUDA.
Avaliação Abrangente: Um estudo detalhado de desempenho, eficiência energética e escalabilidade através de múltiplas gerações de GPUs NVIDIA (Volta, Ampere, Hopper) e arquiteturas (x86 + Hopper vs. Superchip Grace Hopper baseado em ARM).

Resultos
A avaliação foi conduzida em várias plataformas, incluindo o NVIDIA GH200 Grace Hopper Superchip, A100 e V100S.

Aceleração (Speedup): A implementação otimizada OpenACC alcançou acelerações significativas sobre a linha de base multithread de CPU. No GH200, as acelerações atingiram até 208× para tamanhos de problema grandes ( $n=4096$ ). A implementação em GPU começou a superar a linha de base de CPU em $n \ge 256$ .
Escalabilidade: A implementação em GPU demonstrou escalabilidade superior em comparação com a versão de CPU à medida que os tamanhos de problema aumentavam, lidando efetivamente com conjuntos de parâmetros (ex: $n=32768$ ) que eram impraticáveis de processar em CPUs devido à contenção de memória e overhead de sincronização.
Eficiência Energética: No Superchip GH200, a implementação alcançou uma redução de 1,78× na energia por solução em comparação com um sistema x86 + H100, impulsionada principalmente pelo menor consumo de energia da CPU baseada em ARM. A melhoria no tempo de solução no GH200 vs. x86+Hopper foi mais modesta (1,19×).
Escalonamento Arquitetural: A análise entre gerações (V100S $\to$ A100 $\to$ GH200) revelou que o escalonamento de desempenho é impulsionado principalmente pela largura de banda da Memória de Alta Largura de Banda (HBM). No entanto, conforme a largura de banda aumenta, o overhead relativo da geração de elementos de matriz sob demanda (custo aritmético) e os custos fixos da transformada FO no lado da CPU começam a limitar o escalonamento, deslocando o gargalo de puramente limitado pela memória para uma mistura de restrições de computação e sincronização.
Impacto da Otimização: O profiling mostrou que a implementação ingênua era dominada pela computação no lado do host e transferências PCIe (inanição da GPU/GPU starvation). A implementação otimizada deslocou o gargalo para a sincronização, com a atividade da GPU sustentada em ~98% do tempo de iteração.

Significância
O artigo afirma que seus resultados destacam a eficácia da aceleração por GPU para cargas de trabalho criptográficas baseadas em LWE computacionalmente exigentes. Ao utilizar OpenACC, os autores demonstram um caminho para uma PQC de alto desempenho que equilibra programabilidade e desempenho, evitando a necessidade de codificação de baixo nível em CUDA. O trabalho sugere que, com as otimizações apropriadas (especificamente o agrupamento intra-operação e o RNG residente no dispositivo), os esquemas LWE "puros" — que oferecem suposições de segurança mais conservadoras, mas custos computacionais mais altos — podem se tornar práticos em plataformas heterogêneas modernas. O estudo também ressalta a importância de co-otimizar todo o pipeline heterogêneo, pois as operações no lado da CPU e os interconectores restringem cada vez mais a escalabilidade nas próximas gerações de arquiteturas. Um trabalho futuro é proposto para estender esta abordagem para ambientes multi-GPU e outras arquiteturas de aceleradores (AMD, Intel).