💻 computer science

Triple-Hoisted Baby-Step Giant-Step Linear Transformation over CKKS Homomorphic Encryption and Hardware Accelerator

Este artigo apresenta um algoritmo baby-step giant-step com triplo içamento e um acelerador de hardware FPGA correspondente otimizado para memória que reduzem significativamente as rotações de texto cifrado, o acesso à memória fora do chip e a latência computacional para transformações lineares na criptografia homomórfica CKKS.

Autores originais: Sajjad Akherati, Xinmiao Zhang

Publicado 2026-05-19

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Sajjad Akherati, Xinmiao Zhang

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ê é um agente secreto tentando resolver um quebra-cabeça complexo, mas só pode trabalhar com as peças enquanto elas estão trancadas dentro de um cofre pesado e indestrutível. Você não pode abrir o cofre para ver as peças, mas ainda precisa reorganizá-las para resolver o quebra-cabeça. Este é o desafio da Criptografia Homomórfica (HE): realizar cálculos em dados que permanecem criptografados o tempo todo.

Este artigo apresenta uma nova forma super eficiente de resolver um tipo específico de quebra-cabeça chamado Transformação Linear (uma operação matemática usada intensamente em Inteligência Artificial e redes neurais) enquanto os dados ainda estão trancados no cofre.

Aqui está a explicação da solução deles usando analogias simples:

1. O Problema: O "Trabalho Pesado" de Mover Dados

No mundo dos dados criptografados, mover uma peça de informação de um lugar para outro dentro do cofre é incrivelmente caro. É como tentar subir um piano de cauda por uma escada; exige muito tempo, energia e equipamentos especiais (chamados de "chaves de rotação").

O Jeito Antigo: Para resolver o quebra-cabeça, os métodos anteriores precisavam subir o piano pela escada milhares de vezes. Isso criava um enorme engarrafamento, atrasando tudo e exigindo um armazém gigantesco (memória) para armazenar todas as chaves e etapas intermediárias.
O Gargalo: O maior atraso não era realmente fazer a matemática; era correr constantemente de um lado para o outro até o "armazém" (memória fora do chip) para pegar chaves e dados. Isso é como um chef correr até o mercado para cada pitada de sal.

2. A Solução: O Sistema de Elevador "Triplicamente Elevado"

Os autores propõem um novo algoritmo chamado Triple-Hoisted Baby-Step Giant-Step (TH-BSGS).

O Conceito "Baby-Step Giant-Step": Imagine que você precisa caminhar 100 milhas. Em vez de dar 100 passadas minúsculas, você dá 10 "passos gigantes", e para cada passo gigante, você dá 10 "passos de bebê". Isso reduz o número total de vezes que você precisa parar e verificar seu mapa.
A Inovação "Triplicamente Elevada": Versões anteriores deste método tinham duas camadas desses passos. Os autores perceberam que podiam dividir os "passos de bebê" ainda mais, criando uma terceira camada.
- A Analogia: Pense em "elevar" como usar um guindaste para levantar caixas pesadas. No método antigo, você tinha que parar e reorganizar as caixas toda vez que levantava uma camada. O novo método "Triplicamente Elevado" configura um sistema onde você pode levantar três camadas de caixas de uma vez, sem parar para reorganizá-las. Você faz o trabalho pesado uma vez, e a matemática flui suavemente.
- O Resultado: Isso reduz drasticamente o número de vezes que você precisa "mover o piano" (realizar rotações de texto cifrado).

3. O Hardware: Uma "Linha de Montagem" Personalizada

Mesmo com um algoritmo melhor, o hardware precisa ser construído para corresponder. Os autores projetaram um acelerador FPGA personalizado (um chip de computador especializado).

O Truque do "Circuito de Permutação": Uma parte majoritária do processo envolve embaralhar dados (como reorganizar cartas em um baralho). Normalmente, isso exige muito espaço de armazenamento temporário (memória scratchpad) e leva muito tempo.
- A Inovação: Os autores descobriram um padrão específico na forma como os dados são embaralhados. Em vez de usar uma máquina de embaralhar genérica e bagunçada, eles construíram uma esteira rolante personalizada que segue exatamente esse padrão.
- O Benefício: Esta esteira personalizada é duas vezes mais rápida e requer metade do espaço dos projetos anteriores, porque não precisa parar e armazenar dados em buffers temporários.

4. A Otimização de Memória: A Cozinha "Just-in-Time"

O artigo também redesenhou o caminho dos dados para minimizar as viagens até o "mercado" (memória fora do chip).

A Estratégia: Eles dividiram o cálculo em seis fases distintas. Em cada fase, carregam exatamente o que é necessário, fazem todo o trabalho com esses dados enquanto eles estão na bancada (memória no chip) e só então avançam para a próxima fase.
O Resultado: Isso impede que o sistema busque dados constantemente. Comparado aos melhores projetos anteriores, essa abordagem reduziu a quantidade de dados buscados no armazém externo em 2,9 a 4,2 vezes.

O Resumo Final

Os autores testaram seu novo sistema em um chip de alto desempenho (Xilinx Virtex UltraScale+). Comparado aos melhores aceleradores de hardware existentes para esta tarefa:

Velocidade: Eles tornaram o cálculo 5,8 vezes mais rápido (em termos de tempo puro de computação).
Eficiência: Eles reduziram a necessidade de buscar dados na memória externa em 2,9 vezes.
Custo: Eles alcançaram isso sem precisar de recursos de hardware significativamente maiores (chips e memória) do que os melhores projetos anteriores.

Em resumo, eles encontraram uma maneira mais inteligente de organizar o trabalho e construíram uma ferramenta especializada para fazê-lo, transformando um processo lento e engarrafado em uma operação de alta velocidade e otimizada.

Resumo Técnico: Transformação Linear Triple-Hoisted Baby-Step Giant-Step sobre Criptografia Homomórfica CKKS e Acelerador de Hardware

Declaração do Problema
A Criptografia Homomórfica (HE), particularmente o esquema CKKS, permite computações que preservam a privacidade sobre dados criptografados, o que é crítico para aplicações como diagnóstico médico, análise financeira e sequenciamento de genoma. Uma operação fundamental em redes neurais e transformadores baseados em HE é a Transformação Linear (HE-LT). Embora o método diagonal permita HE-LT ao empacotar diagonais de matrizes em polinômios, ele exige um número proibitivo de rotações de texto cifrado para matrizes de alta dimensão. Essas rotações envolvem operações complexas de automorfismo e troca de chaves, levando a uma sobrecarga computacional significativa e a um acesso massivo à memória fora do chip. Aceleradores de hardware existentes, mesmo aqueles que utilizam decomposição Baby-Step Giant-Step (BSGS) e técnicas de dupla elevação (double-hoisting), ainda sofrem com latência substancial e gargalos de largura de banda de memória, frequentemente exigindo centenas de gigabytes de transferência de dados fora do chip para conjuntos de parâmetros típicos.

Metodologia
O artigo propõe uma solução abrangente que aborda tanto a complexidade algorítmica quanto o fluxo de dados de hardware:

Algoritmo Triple-Hoisted BSGS (TH-BSGS):
Os autores estendem o algoritmo BSGS de dupla elevação existente, decompondo ainda mais o "baby step" em duas camadas, criando uma estrutura de três camadas ( $n = n'_1 n'_2 n'_3$ ).
- Triple Hoisting (Elevação Tripla): A técnica é aplicada em todas as três camadas de rotações. Ao reordenar os cálculos e aplicar automorfismos inversos às chaves de troca, o algoritmo garante que a operação Decompose (uma etapa custosa de troca de chaves) seja realizada apenas uma vez para todas as rotações internas em uma camada.
- ModDown Adiado: Semelhante aos métodos de elevação anteriores, as operações ModDown são adiadas e combinadas. No projeto proposto, ModDown é aplicado apenas às somas acumuladas e não aos produtos intermediários, reduzindo significativamente o número de operações modulares necessárias.
- Flexibilidade de Trade-off: Ao ajustar os fatores de decomposição $n'_1, n'_2, n'_3$ , o algoritmo permite trade-offs flexíveis entre o número de chaves de troca necessárias (memória) e a complexidade computacional.
Caminho de Dados Otimizado para Memória:
Para abordar a latência causada pelo acesso à memória fora do chip, o algoritmo TH-BSGS é particionado em seis fases distintas.
- Particionamento de Fases: O algoritmo é reestruturado para que os dados sejam lidos da memória fora do chip, processados com resultados intermediários armazenados e reutilizados no chip, e escritos de volta apenas ao final de cada fase.
- Reutilização de Dados: O projeto maximiza a reutilização de memória no chip, agendando cuidadosamente o carregamento de chaves de troca e membros de polinômios. Por exemplo, nas camadas intermediárias, as chaves de troca são carregadas na memória no chip e reutilizadas em múltiplas iterações para minimizar o tráfego.
- Ajuste de Paralelismo: Seis parâmetros de paralelismo ( $m_1$ a $m_6$ ) são introduzidos para equilibrar o processamento de chaves de troca, membros de polinômios e textos cifrados, garantindo que o projeto se encaixe dentro das restrições de memória no chip do FPGA (por exemplo, 43 MB no Xilinx U280).
Arquitetura do Acelerador de Hardware:
Um acelerador baseado em FPGA eficiente foi projetado para implementar o algoritmo proposto.
- Circuito de Permutação Otimizado: Um novo circuito de permutação é introduzido para implementar o automorfismo $\phi_r$ . Ao explorar as propriedades específicas do automorfismo no domínio NTT e a ordem de armazenamento reversa por bits dos coeficientes, o projeto reduz o número de multiplexadores pela metade em comparação com trabalhos anteriores e elimina a necessidade de buffers de memória scratchpad. Isso reduz a latência da operação de permutação pela metade.
- Componentes Modulares: A arquitetura inclui uma matriz de Elementos de Processamento (PE) que suporta NTT, INTT e operações coeficiente a coeficiente; uma matriz de Adicionadores em Árvore (TA) para somatórios; e uma matriz de Circuito de Permutação (PC).

Principais Contribuições

Inovação Algorítmica: A proposta do algoritmo Triple-Hoisted BSGS, que decompõe ainda mais o baby step para reduzir o número de rotações de texto cifrado e operações Decompose em comparação com a abordagem de dupla elevação.
Otimização do Caminho de Dados: Uma estratégia de otimização de memória baseada em fases que reduz drasticamente o tráfego de memória fora do chip, maximizando a reutilização de dados no chip, especificamente adaptada aos cálculos reordenados do algoritmo TH-BSGS.
Eficiência de Hardware: O desenvolvimento de um acelerador de hardware com um circuito de permutação simplificado que reduz a latência de automorfismo em 50% e elimina o bufferamento extra de memória.

Resultados Experimentais
O projeto foi sintetizado em dispositivos Xilinx Virtex UltraScale+ (U280) e avaliado contra aceleradores de hardware de última geração (incluindo FAME, CHAM e projetos de [25]) sob três conjuntos de parâmetros HE diferentes (Conjunto-A, Conjunto-B, Conjunto-C) que suportam segurança de 128 bits.

Acesso à Memória Fora do Chip: O projeto proposto reduz o acesso à memória fora do chip em 2,9× a 4,2× em comparação com o melhor projeto anterior (FAME) sob as mesmas configurações de parâmetros. Em comparação com o método diagonal, as melhorias atingem até 10,6× na redução do acesso à memória.
Latência Computacional: O acelerador proposto alcança uma redução de 2,9× a 10,6× na latência computacional em comparação com aceleradores de hardware anteriores.
Utilização de Recursos: O projeto mantém os requisitos de recursos de hardware (LUTs, FFs, DSPs, BRAMs) comparáveis ou ligeiramente melhores do que as soluções existentes, apesar dos ganhos de desempenho significativos.
Comparação Algorítmica: Embora o algoritmo TH-BSGS reduza o requisito de memória para chaves de troca em aproximadamente 3,65× em comparação com o algoritmo BSGS de dupla elevação (DH-BSGS), a complexidade computacional geral permanece semelhante à do DH-BSGS e BSGS, pois as multiplicações de polinômios dominam a complexidade total.

Significado
O artigo afirma que o algoritmo TH-BSGS proposto e seu acelerador de hardware associado representam um avanço significativo na eficiência da HE-LT. Ao abordar simultaneamente a sobrecarga algorítmica da troca de chaves e o gargalo de hardware do acesso à memória fora do chip, o projeto permite transformações lineares que preservam a privacidade mais rápidas e escaláveis. A redução no tráfego de memória fora do chip é particularmente crítica, pois as transferências de dados constituem a maior parte da latência nas operações de HE-LT. O trabalho demonstra que a decomposição adicional do baby step, combinada com otimização rigorosa do caminho de dados e hardware especializado, pode produzir melhorias substanciais de desempenho sem aumentar os custos de recursos de hardware. Trabalhos futuros são notados como focados em otimizar ainda mais as transformações lineares para aplicações específicas.

1. O Problema: O "Trabalho Pesado" de Mover Dados

2. A Solução: O Sistema de Elevador "Triplicamente Elevado"

3. O Hardware: Uma "Linha de Montagem" Personalizada

4. A Otimização de Memória: A Cozinha "Just-in-Time"

O Resumo Final

Mais como este