💻 computer science

Multi-Input Ciphertext Multiplication for Homomorphic Encryption

Este artigo propõe um método otimizado de multiplicação de cifrados com múltiplas entradas para Criptografia Homomórfica que vai além de duas entradas por meio de computações reformuladas, chaves de avaliação adicionais e uma abordagem de reescalonamento multinível, resultando em arquiteturas de hardware que reduzem significativamente a área lógica e a latência em comparação com projetos anteriores.

Autores originais: Sajjad Akherati, Xinmiao Zhang

Publicado 2026-05-19

📖 5 min de leitura🧠 Leitura aprofundada

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 chef de cozinha tentando assar um bolo, mas há um detalhe: você deve fazer toda a mistura e o assamento usando luvas de forno grossas e pesadas que impedem você de sentir os ingredientes ou ver a tigela. Isso é a Criptografia Homomórfica (CH). Ela permite que computadores realizem operações matemáticas em dados "criptografados" (a massa do bolo dentro das luvas) sem jamais descriptografá-los (tirar as luvas). Isso mantém segredos seguros, sejam seus registros médicos ou seu saldo bancário.

No entanto, fazer matemática com essas "luvas" é incrivelmente lento e bagunçado. O maior gargalo é a multiplicação. Na criptografia padrão, você só pode multiplicar dois ingredientes de cada vez. Mas muitas tarefas modernas, como treinar uma IA para reconhecer uma doença ou analisar tendências financeiras complexas, exigem multiplicar muitos ingredientes (textos cifrados) juntos de uma só vez.

Este artigo apresenta uma nova maneira super eficiente de multiplicar esses ingredientes criptografados, especificamente para um método de criptografia popular chamado CKKS. Aqui está a explicação de sua descoberta usando analogias simples:

1. O Problema: A "Cozinha Bagunçada"

Quando você multiplica números criptografados, o "ruído" (a bagunça criada pelas luvas de forno) fica cada vez mais alto. Se você multiplicar muitos números de uma vez sem limpar, o ruído afoga os dados reais e o resultado torna-se lixo.

Para corrigir isso, o sistema de criptografia precisa realizar uma etapa de "limpeza" chamada Redimensionamento após cada multiplicação. Pense nisso como parar para limpar o balcão e colocar os ingredientes de volta em ordem.

O Jeito Antigo: Se você precisasse multiplicar 10 ingredientes, o método antigo era como uma esteira rolante onde você multiplicava dois, parava para limpar, multiplicava mais dois, parava para limpar, e assim por diante. Era lento e exigia muitos suprimentos de limpeza (recursos de hardware).
A Tentativa Anterior de "Três Ingredientes": O trabalho anterior dos autores mostrou que você poderia multiplicar três ingredientes de uma vez, o que era mais rápido. Mas ainda havia muitas etapas de limpeza desnecessárias.

2. A Solução: A "Linha de Montagem Inteligente"

Os autores propõem duas grandes melhorias para tornar esse processo mais rápido e menor:

A. A "Limpeza de Um Passo" (Multiplicação com 3 Entradas Melhorada)

Em seu novo design para multiplicar três ingredientes, eles perceberam que estavam fazendo a limpeza (Redimensionamento) e o reorganizar (Relinearização) de uma maneira desajeitada e indireta.

A Analogia: Imagine que você tem três tigelas de massa. O método antigo era misturá-las, despejar a mistura em uma nova tigela, limpar as tigelas antigas, despejar a mistura novamente e limpar de novo.
A Correção: Eles redesenharam o processo para que você possa misturar e limpar em um movimento suave. Eles descobriram como combinar as etapas de limpeza para que você não precise parar e limpar o balcão tantas vezes.
O Resultado: Seu novo "misturador de três tigelas" é 50% mais rápido (latência) e ocupa 15% menos espaço no chip (área) em comparação com seu melhor design anterior.

B. A "Limpeza em Grupo" (Multiplicação com Múltiplas Entradas)

E se você precisar multiplicar quatro, cinco ou até doze ingredientes de uma vez?

O Jeito Antigo: Você construiria uma longa linha de "misturadores de duas tigelas". Você mistura dois, limpa, mistura mais dois, limpa, depois mistura os resultados, limpa novamente. Isso cria uma linha muito longa (alta "profundidade multiplicativa"), o que significa que o ruído se acumula muito rápido.
A Nova Estratégia: Os autores perceberam que, se você agrupar seus ingredientes de maneira diferente, pode fazer uma "Limpeza em Grupo".
- Em vez de limpar após cada etapa individual, eles desenvolveram um truque matemático (chamado Multi-Redimensionamento) que permite esperar e limpar várias camadas de bagunça de uma só vez.
- A Analogia: Imagine que você está lavando louça. Em vez de lavar um prato, secá-lo e guardá-lo, depois lavar uma xícara, secá-la e guardá-la, você lava uma pilha inteira de louça, depois seca a pilha inteira e depois guarda tudo. Você faz a "secagem" (a parte cara e lenta) apenas uma vez para todo o grupo.
O Resultado: Ao reorganizar como agrupam os ingredientes (o "particionamento"), eles podem combinar essas etapas de limpeza. Para multiplicar entre 4 e 12 ingredientes, seu novo método economiza 32% do espaço e reduz o tempo pela metade (45% mais rápido) em comparação com a antiga linha "dois por dois".

3. Por Que Isso Importa (De Acordo com o Artigo)

O artigo foca estritamente na arquitetura de hardware — o design físico do chip de computador que faz essa matemática.

Eles provaram que, ao mudar como a matemática é organizada (o algoritmo) e como o chip é construído (a arquitetura), é possível realizar matemática criptografada complexa muito mais rápido.
Eles mencionam especificamente que isso ajuda em aplicações como aprendizado de máquina, diagnóstico médico e análise financeira, porque esses campos frequentemente exigem multiplicar muitos pontos de dados criptografados juntos.

Resumo

Pense neste artigo como a invenção de uma nova cozinha super eficiente para um chef que não pode tirar suas luvas de forno.

Eles descobriram como misturar três ingredientes de uma vez sem fazer bagunça.
Eles inventaram uma maneira de limpar múltiplas camadas de bagunça ao mesmo tempo, em vez de uma por uma.
O resultado é uma cozinha que é menor, mais rápida e requer menos energia para manter segredos seguros enquanto realiza matemática complexa.

Os autores não testaram isso em pacientes reais ou contas bancárias reais neste artigo; eles apenas provaram que a máquina projetada para fazer esse trabalho é significativamente melhor do que as máquinas que tínhamos antes.

Resumo Técnico: Multiplicação de Cifras com Múltiplas Entradas para Criptografia Homomórfica

Declaração do Problema
A criptografia homomórfica (HE), particularmente o esquema RNS-CKKS, permite operações aritméticas sobre dados criptografados, o que é crítico para aplicações que preservam a privacidade, como aprendizado de máquina e diagnóstico médico. No entanto, os esquemas HE padrão definem a multiplicação de cifras apenas para duas entradas. Muitas aplicações práticas, como aproximações polinomiais de alta ordem para funções de ativação de redes neurais (por exemplo, ReLU), árvores de decisão e sequenciamento genômico, exigem a multiplicação de múltiplas cifras ( $n > 2$ ).

As abordagens existentes para lidar com a multiplicação de múltiplas entradas geralmente encadeiam múltiplos multiplicadores de duas entradas em uma estrutura de árvore binária. Este método sofre de duas ineficiências primárias:

Alta Latência e Área: Multiplicar sequencialmente $n$ cifras usando unidades de duas entradas resulta em sobrecarga de hardware e latência significativas.
Crescimento de Ruído e Sobrecarga de Redimensionamento: Cada multiplicação aumenta o nível de ruído, tornando necessária uma operação de redimensionamento (rescaling) para restaurar a escala da mensagem. Em uma árvore binária padrão, o redimensionamento deve ocorrer após cada etapa de multiplicação para evitar o crescimento exponencial do ruído. Isso resulta em um grande número de unidades de redimensionamento, cada uma exigindo operações caras de Transformada Numérica Teórica (NTT) e Transformada Numérica Teórica Inversa (INTT), aumentando significativamente a complexidade computacional e o uso de recursos de hardware.

Metodologia
O artigo propõe um framework para multiplicação direta de $n$ cifras que minimiza a profundidade multiplicativa e a complexidade de hardware. A metodologia divide-se em duas contribuições principais:

Multiplicador de Três Entradas Aprimorado:
Os autores reformulam primeiro o processo de multiplicação de três entradas. No trabalho preliminar [26], a relinearização e o redimensionamento eram realizados separadamente, exigindo múltiplas operações ModUp/ModDown e numerosos blocos (I)NTT. O novo design:
- Reformula a Relinearização: Ao mover o fator de escala $P^{-1}$ para a conversão de base (BConv) e a multiplicação da chave de avaliação, o design elimina etapas de escala separadas.
- Otimiza o Redimensionamento: Os autores reestruturam o caminho de dados para realizar o redimensionamento no domínio original antes da NTT final, em vez de no domínio NTT. Isso permite a eliminação de operações (I)NTT redundantes.
- Resultado: Essas mudanças reduzem o número de blocos (I)NTT no caminho de dados de oito para quatro, efetivamente reduzindo pela metade o comprimento do caminho de dados.
Extensão para Múltiplas Entradas com Redimensionamento Combinado:
Para estender a multiplicação para $n > 3$ entradas sem aumentar a profundidade multiplicativa, o artigo introduz:
- Chaves de Avaliação Generalizadas: Novas chaves de avaliação ( $ek_t$ ) são introduzidas para relinearizar os termos polinomiais de grau superior ( $d_t s^t$ ) gerados pela multiplicação de $n$ cifras, reduzindo o resultado de volta a um formato de dois polinômios.
- Algoritmo de Redimensionamento Múltiplo (Multi-RS): Uma análise teórica identifica condições sob as quais múltiplas operações de redimensionamento podem ser atrasadas e combinadas. Os autores propõem um algoritmo que realiza $\mu$ operações de redimensionamento concatenadas usando o mesmo número de operações (I)NTT que um único redimensionamento. Isso é alcançado transformando a entrada para o domínio INTT, realizando redimensionamento iterativo no domínio dos coeficientes e transformando de volta, utilizando constantes pré-calculadas para fundir as operações.
- Diretrizes de Particionamento de Entrada: O artigo fornece diretrizes para particionar $n$ entradas em grupos (por exemplo, $(n_1, n_2, \dots, n_m)$ ) para maximizar o número de operações de redimensionamento combinadas, mantendo a profundidade multiplicativa ótima de $\lceil \log_2 n \rceil$ . Isso envolve a criação de estruturas de árvore desbalanceadas sempre que possível para agrupar mais entradas antes de uma etapa de redimensionamento.

Principais Contribuições

Reformulação Algorítmica: Uma nova formulação para multiplicação de três entradas que combina computações intermediárias, reduzindo o número de operações (I)NTT e encurtando o caminho de dados.
Framework de Múltiplas Entradas: Uma extensão da multiplicação de cifras para $n$ entradas arbitrárias usando chaves de avaliação generalizadas e um multiplicador em estrutura de árvore.
Redimensionamento Combinado: Um novo algoritmo de redimensionamento múltiplo que reduz a complexidade de realizar múltiplos redimensionamentos à de um único redimensionamento, independentemente do número de etapas combinadas ( $\mu$ ).
Arquitetura de Hardware: Projeto de arquiteturas de hardware totalmente pipelineadas para os multiplicadores propostos, incluindo unidades ModUp, ModDown e de redimensionamento otimizadas.

Resultados
Os designs propostos foram sintetizados usando o processo GlobalFoundries 22FDX com parâmetros $N=2^{16}$ , $L=K=24$ e $w=64$ .

Multiplicador de Três Entradas: Em comparação com o trabalho anterior [26], o multiplicador de três entradas aprimorado alcança uma redução de 15% na área lógica e uma redução de 50% na latência. Também reduz os requisitos de memória em aproximadamente 20% devido a menos unidades (I)NTT.
Multiplicadores de Múltiplas Entradas ( $n=4$ a $12$): Em comparação com uma implementação de base usando uma árvore binária de multiplicadores de duas entradas, o método proposto alcança uma redução média de 32% na área total e uma redução de 45% na latência.
Eficiência de Redimensionamento: Para entradas que não são potências de dois (por exemplo, $n=17$ ), o particionamento otimizado combinado com redimensionamento múltiplo reduz o número total de unidades de redimensionamento (e operações (I)NTT associadas) em aproximadamente 47% em comparação com a abordagem padrão de árvore binária.

Significância
O artigo afirma que essas melhorias abordam o gargalo da multiplicação de múltiplas entradas em HE, o que é essencial para aplicações complexas de preservação de privacidade. Ao reduzir a complexidade de hardware e a latência da multiplicação de cifras, a arquitetura proposta torna mais viável a implantação de HE em ambientes com recursos limitados ou de alto rendimento. O trabalho demonstra que, através da reformulação algorítmica e do particionamento cuidadoso das entradas, a sobrecarga do gerenciamento de ruído (redimensionamento) pode ser significativamente minimizada sem comprometer a segurança ou a correção do esquema de criptografia. Os autores observam que trabalhos futuros focarão em simplificar ainda mais os multiplicadores para números ainda maiores de entradas.