💻 computer science

Homomorphic encryption schemes based on coding theory and polynomials

Esta pesquisa apresenta o estado da arte em esquemas de criptografia homomórfica que utilizam teoria de códigos e polinômios para permitir computações seguras em dados criptografados sem a necessidade de descriptografia.

Autores originais: Giovanni Giuseppe Grimaldi

Publicado 2026-06-04

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Giovanni Giuseppe Grimaldi

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

A Visão Geral: O Problema da "Caixa Trancada"

Imagine que você tem um segredo muito valioso (seus dados privados) e quer pedir a um amigo (um servidor na nuvem) para fazer alguns cálculos com ele. O problema é que você não confia no seu amigo. Se você der o segredo a ele, ele pode espiar. Se você der a caixa trancada, ele não consegue fazer os cálculos.

A Criptografia Homomórfica é como uma caixa trancada mágica. Ela permite que seu amigo balance a caixa, misture o conteúdo e até multiplique os itens dentro dela, tudo isso enquanto a caixa permanece trancada. Quando ele lhe devolver a caixa, você a destranca e o resultado dentro é a resposta correta para o problema matemático, mesmo que seu amigo nunca tenha visto os números reais.

Este artigo é um levantamento (uma grande revisão) de diferentes maneiras pelas quais as pessoas tentaram construir essas "caixas mágicas". O autor agrupa esses métodos em duas famílias principais:

Teoria da Codificação: Construir caixas baseadas em padrões e códigos de correção de erros (como consertar um CD riscado).
Polinômios: Construir caixas baseadas em equações algébricas complexas (como resolver um quebra-cabeça gigante).

Parte 1: A Família da "Teoria da Codificação" (Os Combinadores de Padrões)

Esses esquemas tratam os dados como uma mensagem escrita em um código específico. Se você somar ou multiplicar duas mensagens codificadas, o resultado ainda é um código válido, mas pode ficar um pouco "ruidoso" (como estática em um rádio).

O Esquema de Armknecht et al.: Imagine um jogo onde você esconde uma mensagem secreta dentro de uma longa lista de números. Você sabe exatamente quais números são os "bons" e quais são os "ruins" (ruído). A segurança reside no fato de que um invasor não sabe qual é qual.
- O Problema: É como uma caixa "Parcialmente Homomórfica". Você pode somar coisas para sempre, mas só pode multiplicar algumas poucas vezes antes que o ruído fique alto demais para ser compreendido.
Esquemas de Challa & Gunta: Estes utilizam um tipo específico de código chamado Reed-Muller. Pense nisso como uma grade de luzes. Você esconde sua mensagem no padrão de luzes. Para criptografar, você embaralha a grade e esconde as luzes "reais" entre outras aleatórias.
- O Problema: Os autores afirmam que estes são "Totalmente Homomórficos" (você pode fazer matemática ilimitada), mas o artigo observa que eles dependem de ideias de segurança "não padronizadas". Eles ainda não foram provados seguros contra todos os hackers modernos e ninguém os utiliza na vida real atualmente.
O Esquema de Bogdanov & Lee: Este tentou usar uma versão modificada de um código famoso (Reed-Solomon).
- O Resultado: Falhou. O artigo explica que hackers encontraram um truque astuto (usando "códigos de quadrados") para descobrir o padrão secreto. Uma vez que eles conheciam o padrão, podiam abrir qualquer caixa. Este esquema é considerado quebrado.
O Esquema de Aguilar-Melchor et al.: Este utiliza códigos de "Métrica de Rank". Imagine que os dados não são apenas uma lista de números, mas uma grade de números onde o "peso" do erro importa.
- O Problema: Permite adições ilimitadas, mas apenas uma multiplicação. Para fazer mais, você precisa de um botão especial de "atualização" (bootstrapping), mas o artigo diz que o método de atualização específico deles é inseguro.

Resumo da Teoria da Codificação: Essas ideias são matematicamente belas e engenhosas, mas muitas estão quebradas, são não comprovadas ou são teóricas demais para serem usadas em aplicações do mundo real hoje.

Parte 2: A Família dos "Polinômios" (Os Resolvedores de Equações)

Esses esquemas tratam os dados como coeficientes em uma equação polinomial gigante (como $3x^2 + 5x + 2$ ). Eles dependem do fato de que somar ou multiplicar essas equações é fácil, mas descobrir os ingredientes secretos a partir do resultado é incrivelmente difícil.

Dasgupta & Pal / DGHV: Estes utilizam matemática de inteiros simples com "ruído". Imagine tentar adivinhar um número secreto olhando para um número que é o segredo mais um pouco de estática aleatória.
- Status: Estas são ideias fundamentais que ajudaram a iniciar o campo, mas são lentas e usadas principalmente para fins teóricos agora.
BFV, BGV e CKKS: Estes são as estrelas do show. São as caixas "Totalmente Homomórficas" que realmente funcionam no mundo real.
- BFV & BGV: São como calculadoras de precisão. São ótimas para matemática exata (como contar dinheiro ou consultas em bancos de dados). Elas são "Niveladas", o que significa que você pode decidir quão profunda será a matemática antes que a caixa fique muito ruidosa.
- CKKS: Esta é a "Calculadora Aproximada". É projetada para números reais (como temperatura ou preços de ações). Ela aceita um pouco de erro de arredondamento, o que a torna muito mais rápida e perfeita para IA e aprendizado de máquina.
GSW: Este é um esquema teórico muito importante. Provou que você pode construir um sistema totalmente homomórfico usando um tipo específico de matemática de matrizes. É o avô de muitos esquemas rápidos modernos.
FHEW / TFHE: Estes são os Demônios da Velocidade. Introduziram um truque chamado "bootstrapping".
- A Analogia: Imagine que sua caixa fica ruidosa após cada problema matemático. O bootstrapping é como uma "máquina de limpeza" que pega a caixa ruidosa, limpa a estática e coloca os dados em uma caixa nova e silenciosa. O TFHE pode fazer essa limpeza tão rápido (em menos de um segundo) que você pode fazer qualquer quantidade de matemática, não importa o quão complexa seja.

Resumo dos Polinômios: Estes são o padrão da indústria atual. São seguros, práticos e usados em muitas bibliotecas de software hoje.

O Veredito Final: Dois Lados da Mesma Moeda

O autor conclui que, embora essas duas famílias (Codificação vs. Polinômios) pareçam diferentes, elas são, na verdade, primas.

A Teoria da Codificação vê os dados como uma "mensagem ruidosa" que precisa ser decodificada.
Os Polinômios veem os dados como uma "equação ruidosa" que precisa ser resolvida.

A Principal Conclusão:
O artigo traça uma linha clara no chão:

Os esquemas de Teoria da Codificação são majoritariamente teóricos. São interessantes para matemáticos, mas muitos foram quebrados ou carecem da prova de segurança necessária para o uso no mundo real.
Os esquemas de Polinômios/Anéis (como BFV, BGV, CKKS, TFHE) são os vencedores práticos. Eles são construídos sobre pressupostos de segurança sólidos, são rápidos o suficiente para serem úteis e estão atualmente impulsionando a tecnologia para computação em nuvem segura.

O artigo termina dizendo que, embora atualmente dependamos dos "vencedores" de polinômios, as ideias da teoria da codificação ainda são valiosas. Elas podem deter a chave para descobertas futuras, desde que os pesquisadores consigam resolver os problemas de segurança e velocidade que as limitam atualmente.

Resumo Técnico: Esquemas de Criptografia Homomórfica Baseados em Teoria de Códigos e Polinômios

Declaração do Problema

A criptografia homomórfica (HE) permite o cálculo seguro sobre dados criptografados sem a necessidade de descriptografia, uma capacidade crucial para a computação em nuvem com preservação de privacidade. Embora a criptografia totalmente homomórfica (FHE) permita cálculos arbitrários, a implementação prática enfrenta desafios significativos em relação à eficiência, gestão de ruído e fundamentos de segurança.

O artigo aborda o panorama dos esquemas de HE categorizando-os em duas famílias algébricas primárias: aquelas baseadas em teoria de códigos e aquelas baseadas em polinômios (frequentemente realizadas através de estruturas baseadas em reticulados/lattices). O problema central é realizar um levantamento do estado da arte nesses domínios específicos, analisando sua construção, suposições de segurança e viabilidade prática. O artigo destaca uma dicotomia: embora muitas propostas baseadas em teoria de códigos sejam algebricamente elegantes, elas frequentemente dependem de suposições de segurança não padronizadas ou foram quebradas, ao passo que os esquemas baseados em polinômios/anéis tornaram-se o padrão para a HE prática e segura.

Metodologia

O artigo emprega uma metodologia de levantamento abrangente, revisando e analisando esquemas criptográficos específicos da literatura. A análise é estruturada em duas seções principais:

Esquemas Baseados em Teoria de Códigos: Os autores examinam esquemas onde o processo de criptografia envolve a codificação de mensagens em palavras de código (ou palavras de código ruidosas) de códigos lineares. Conceitos-chave incluem:
- Códigos de Avaliação: Uso de avaliação polinomial sobre corpos finitos (ex: Reed-Muller, Reed-Solomon) para definir a estrutura do código.
- Códigos de Métrica de Posto (Rank Metric Codes): Utilização de peso de posto e códigos ideais sobre corpos de extensão.
- Mecanismos de Segurança: Dependência de problemas como o Problema de Códigos Sincronizados de Decodificação (DSCP), Decodificação de Posto Ideal (IRSD) ou a dificuldade de identificar localizações "boas" vs. "ruins" em uma palavra de código.
Esquemas Baseados em Polinômios: Os autores revisam esquemas onde a estrutura algébrica subjacente é definida por anéis de polinômios (frequentemente anéis quocientes como $Z[x]/(x^n+1)$ ). Conceitos-chave incluem:
- Suposições de Reticulados (Lattice Assumptions): A maioria dos esquemas modernos baseia-se nos problemas de Aprendizado com Erros (LWE) ou Ring-LWE (RLWE).
- Gestão de Ruído: Técnicas como bootstrapping, relinearização e mudança de módulo para controlar o crescimento do ruído durante as operações homomórficas.
- Aritmética Aproximada: Esquemas projetados para computações de números reais/complexos (ex: CKKS).

O artigo detalha os algoritmos (Keygen, Encrypt, Decrypt, Eval) para esquemas específicos, incluindo Armknecht et al., Challa-Gunta, Bogdanov-Lee, Aguilar-Melchor et al., Dasgupta-Pal, BFV, BGV, CKKS, GSW, FHEW/TFHE e DGHV.

Contribuições Principais e Resultados

1. Análise de Esquemas Baseados em Teoria de Códigos

O levantamento revela que, embora os esquemas baseados em teoria de códigos ofereçam estruturas algébricas interessantes, eles enfrentam obstáculos significativos de segurança e praticidade:

Armknecht et al.: Um esquema algo homomórfico baseado em códigos de avaliação e códigos de Reed-Muller. A segurança depende do DSCP. É de chave simétrica e suporta um número limitado de multiplicações.
Challa-Gunta: Dois esquemas de chave simétrica (versões vetorial e matricial) baseados em códigos de Reed-Muller que alegam FHE. O artigo observa que estes dependem de alegações de segurança não padronizadas (ocultação de posições de palavras de código) e carecem de implementação prática.
Bogdanov-Lee: Um esquema assimétrico algo homomórfico baseado em códigos de Reed-Solomon modificados. Resultado: O artigo afirma explicitamente que este esquema está quebrado. Um ataque baseado em distinguidor usando a dimensão do "código quadrado" permite que um adversário recupere o conjunto secreto de coordenadas e decifre qualquer texto cifrado em tempo polinomial.
Aguilar-Melchor et al.: Um esquema de chave simétrica baseado em códigos ideais de métrica de posto aleatórios. Suporta uma multiplicação de texto cifrado. Resultado: O mecanismo de bootstrapping proposto é considerado inseguro porque o número de chaves de bootstrapping excede o limiar para resolver o problema IRSD subjacente.

2. Análise de Esquemas Baseados em Polinômios

O levantamento identifica os esquemas baseados em polinômios/anéis como o padrão atual para HE segura e prática:

Dasgupta-Pal & DGHV: Esquemas iniciais baseados em aritmética de inteiros e no problema do Máximo Divisor Comum Aproximado (AGCD). São algo homomórficos, mas podem ser tornados totalmente homomórficos via bootstrapping.
BFV, BGV, CKKS, GSW: Estes são esquemas totalmente homomórficos nivelados e assimétricos baseados em LWE/RLWE.
- BFV/BGV: Suportam aritmética exata sobre anéis finitos. Utilizam relinearização para lidar com o crescimento do grau dos textos cifrados durante a multiplicação.
- CKKS: Suporta aritmética aproximada, tornando-o adequado para aplicações de dados reais/complexos.
- GSW: Um esquema fundamental que utiliza textos cifrados baseados em matrizes e o operador "Flatten".
FHEW/TFHE: Esquemas totalmente homomórficos projetados para bootstrapping rápido de circuitos booleanos. Operam sobre o toro e utilizam gate bootstrapping para renovar o ruído, permitindo profundidade de circuito ilimitada.

3. Síntese Comparativa

O artigo fornece uma visão comparativa (Tabela 1) destacando uma grande divisão:

Esquemas Baseados em Teoria de Códigos: Frequentemente importantes conceitualmente, mas frequentemente sofrem de suposições de segurança não padronizadas, falta de validação moderna ou vulnerabilidades específicas (ex: Bogdanov-Lee). Eles permanecem primariamente teóricos ou conceituais.
Esquemas Baseados em Polinômios/Anéis: Construídos sobre suposições de dureza bem estabelecidas (LWE, RLWE) que são centrais para a criptografia pós-quântica. Estes esquemas levaram a implementações práticas, bibliotecas de software e são amplamente utilizados tanto para aritmética exata quanto aproximada.

Significância e Alegações

O artigo afirma que a distinção entre abordagens de "teoria de códigos" e "polinômios" não deve ser vista como uma separação rígida de objetos disjuntos. Em vez disso, elas representam um espectro comum de criptografia homomórfica algébrica:

Núcleo Algébrico: Ambas as famílias codificam informações em objetos algébricos estruturados (palavras de código ou polinômios) e exploram a compatibilidade desta estrutura com adição e multiplicação.
Diferença de Paradigma: O contraste reside na formulação de correção e segurança. Os esquemas baseados em teoria de códigos formulam problemas em termos de decodificação (interpolação a partir de erros ocultos), enquanto os esquemas de polinômios os formulam em termos de aritmética ruidosa sobre anéis estruturados.
Estado Atual: O artigo conclui que, embora os esquemas baseados em reticulados (polinômios) dominem atualmente tanto a teoria quanto a prática devido a fundações de segurança robustas e eficiência, as abordagens baseadas em teoria de códigos permanecem uma direção de pesquisa vital. Elas oferecem paradigmas de design alternativos e levantam questões matemáticas independentes sobre problemas de decodificação.

O artigo identifica vários problemas abertos, incluindo a necessidade de esquemas baseados em códigos com suposições padrão (como LWE), bootstrapping seguro e eficiente fora do ambiente de reticulados, e análises de segurança sistemáticas para propostas não padronizadas. Ele enfatiza que a mera existência de uma estrutura algébrica atraente é insuficiente; uma suposição de dureza robusta e controle preciso de ruído são essenciais para um esquema de HE convincente.