🔢 mathematics

Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

Este artigo apresenta um ataque de recuperação de chave em tempo polinomial que quebra todos os conjuntos de parâmetros propostos do esquema de criptografia Enhanced Gabidulin Matrix Codes (EGMC) ao combinar técnicas combinatórias e algébricas para recuperar uma chave secreta equivalente, reduzindo assim o nível de segurança de 128 bits alegado para apenas 35 bits.

Autores originais: Thai Hung Le

Publicado 2026-08-05

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Thai Hung Le

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 a internet como uma cidade gigante e movimentada onde todos tentam enviar mensagens secretas. Para manter essas mensagens seguras contra olhos curiosos, usamos fechaduras digitais chamadas criptografia. Por muito tempo, cientistas têm construído essas fechaduras usando quebra-cabeças matemáticos complexos que são fáceis de criar, mas incrivelmente difíceis de resolver sem a chave. Recentemente, um novo tipo de fechadura foi proposto usando um tipo especial de matemática envolvendo grades de números e "rank" (que é apenas uma forma sofisticada de medir quanta informação está realmente compactada dentro da grade). Os criadores desta nova fechadura pensaram que tinham adicionado uma camada de "ruído" — como estática em um rádio — para esconder a forma real da fechadura, fazendo com que ela parecesse uma bagunça aleatória para qualquer um tentando invadi-la. Eles alegaram que este novo design era tão seguro que nem mesmo um computador quântico super-rápido poderia quebrá-lo, e prometeram que seria minúsculo e eficiente, perfeito para o futuro da comunicação segura.

No entanto, assim como o truque de um mágico que depende de uma destreza específica das mãos, esta nova fechadura tinha uma falha oculta. Um pesquisador chamado Thai Hung Le descobriu que o "ruído" não estava de fato escondendo a forma secreta tão bem quanto todos pensavam. Usando uma mistura inteligente de adivinhação e trabalho de detetive algébrico, o pesquisador encontrou uma maneira de remover as camadas de estática e revelar a estrutura original e oculta por baixo. É como se alguém tivesse construído uma casa de cartas com um projeto secreto, coberto-a com névoa, e depois percebesu que, se você apenas olhasse para a névoa pelo ângulo certo, o projeto ainda era vagamente visível. Esta descoberta é um grande negócio porque significa que as novas fechaduras não são tão seguras quanto o anunciado, e as pessoas que as desenharam precisam repensar seus projetos antes de começarem a usá-las para proteger nossos dados.

A Grande Descoberta do Artigo

Neste artigo, Thai Hung Le apresenta uma nova maneira de quebrar os esquemas de criptografia "Enhanced Gabidulin Matrix Code" (EGMC). Esses esquemas foram introduzidos recentemente como uma forma de criar chaves de criptografia muito pequenas e eficientes que poderiam sobreviver a ataques de futuros computadores quânticos. A segurança desses esquemas baseava-se na ideia de que, se você pegasse uma grade de números especialmente estruturada e adicionasse linhas e colunas aleatórias (o "ruído"), tornaria impossível distinguir a diferença entre o código real e uma bagunça completamente aleatória.

O autor mostra que essa suposição está errada. Em vez de tentar força bruta para cada possível maneira de remover o ruído (o que levaria uma eternidade), o artigo introduz um ataque "híbrido". Imagine que você está tentando encontrar um padrão específico em um mosaico gigante e embaralhado. O jeito antigo era adivinhar a posição de cada azulejo. Este novo método é mais inteligente: ele adivinha a posição de apenas uma linha de azulejos e, então, usa a matemática para descobrir instantaneamente onde o restante dos azjos deve estar.

O artigo detalha duas maneiras principais de fazer isso:

Adivinhando as Colunas: O atacante adivinha como as colunas da grade foram embaralhadas e então usa álgebra para resolver como as linhas foram embaralhadas.
Adivinhando as Linhas: O atacante adivinha como as linhas da grade foram embaralhadas e então resolve para as colunas.

Uma vez que o atacante descobre o embaralhamento, ele pode remover o ruído aleatório e revelar a estrutura original e oculta. O artigo prova que essa estrutura é um "código Gabidulin", que é um tipo de quebra-cabeça matemático que é, na verdade, bastante fácil de resolver uma vez que você conhece o padrão secreto.

O Que o Artigo Realmente Quebra

O autor não encontra apenas uma pequena rachadura; ele estraçalha a janela inteira. O artigo demonstra que este ataque funciona contra todos os 16 conjuntos de parâmetros propostos para os esquemas de criptografia EGMC. Isso significa que todas as versões da fechadura que foram sugeridas para uso agora são consideradas quebradas.

Para dar uma ideia de quão eficaz isso é, o artigo analisa um conjunto específico de números que deveria oferecer segurança de 128 bits (um nível padrão de segurança). O autor mostra que seu ataque reduz esse nível de segurança para apenas 35 bits. No mundo da criptografia, isso é como passar de um cofre com uma combinação de um milhão de dígitos para uma fechadura que uma criança poderia abrir em segundos.

O artigo fornece um exemplo concreto desse poder: usando seu método, os pesquisadores foram capazes de recuperar a chave secreta para aquele nível de segurança de 128 bits em menos de 10 minutos. Isso não foi apenas uma ideia teórica; eles realmente construíram um programa de computador para fazer isso.

O Que o Artigo Descarta

É importante notar o que este artigo diz que não funciona. O autor explica que tentativas anteriores de quebrar esses códigos dependiam de métodos "combinatórios", que envolvem adivinhar tanto o embaralhamento de linhas quanto o de colunas ao mesmo tempo. O artigo argumenta que esse modo antigo é muito lento e ineficiente comparado ao novo abordagem "híbrida".

Além disso, o artigo argumenta contra a ideia de que simplesmente aumentar os parâmetros (adicionar mais ruído) resolverá o problema para todos os casos. O autor mostra que, para certos tipos desses códigos — especificamente quando um dos fatores de ruído (seja o número de linhas extras ou o número de colunas extras) é zero — o ataque torna-se tão rápido que roda em "tempo polinomial". Isso significa que, não importa o quanto você aumente o tamanho da fechadura nesses casos específicos, o ataque ainda será rápido o suficiente para quebrá-la. A única maneira de potencialmente consertar isso, sugere o artigo, seria mudar o design fundamental para que ambos os fatores de ruído sejam não-zero e grandes o suficiente para deter o ataque, mas o autor alerta que isso pode tornar as chaves e mensagens grandes demais para serem úteis.

Quão Certos Eles Estão?

O artigo é muito confiante em seus resultados. O autor não apenas adivinhou; ele forneceu uma prova matemática completa de como seu ataque funciona e a sustentou com uma implementação de computador funcional. Ele afirma explicitamente que seu ataque quebra todas as versões propostas do esquema. Ele também compara seus resultados com ataques anteriores, mostrando que seu método é significativamente mais rápido e poderoso. O artigo conclui que os esquemas de criptografia EGMC não são mais seguros para uso e que a comunidade de segurança precisa seguir em frente para designs diferentes.

Resumo Técnico: Quebra dos Esquemas de Criptografia de Gabidulin MinRank ACDGV sobre Códigos de Matriz

Enunciado do Problema
O artigo aborda a segurança dos Códigos de Matriz Gabidulin Aprimorados (EGMC), um esquema de mascaramento introduzido por Aragon et al. na Asiacrypt 2024. O EGMC foi projetado para ocultar a estrutura algébrica dos códigos de matriz Gabidulin, permitindo esquemas de criptografia compactos do tipo McEliece e Niederreiter com textos cifrados pequenos (por exemplo, 65 bytes para 128 bits de segurança). A segurança do EGMC baseia-se no problema de Indistinguibilidade Decisional EGMC: a suposição de que um código EGMC mascarado é computacionalmente indistinguível de um código de matriz aleatório. A criptoanálise anterior, especificamente um ataque de núcleo baseado em MinRank por Porwal et al. (Eurocrypt 2026), demonstrou ataques de tempo exponencial que quebraram um subconjunto dos conjuntos de parâmetros propostos, mas deixaram outros seguros. O autor investiga se a construção EGMC retém estrutura oculta suficiente para ser quebrada de forma mais eficiente.

Metodologia
O autor propõe um novo distinguidor "híbrido" e um subsequente ataque de recuperação de chave que combina adivinhação combinatória com resolução algébrica. Ao contrário dos distinguidores anteriores que realizam força bruta em ambas as matrizes de compressão de linha e coluna, este ataque adivinha apenas uma matriz de compressão e resolve para a outra usando técnicas algébricas.

O ataque opera em duas direções primárias:

Adivinha- $V$ -resolve- $U$ (Guess- $V$ -solve- $U$ ): O atacante adivinha uma matriz de compressão de coluna $V$ e resolve algebricamente para uma matriz de compressão de linha $U$ .
Adivinha- $U$ -resolve- $V$ (Guess- $U$ -solve- $V$ ): O atacante adivinha uma matriz de compressão de linha $U$ e resolve para uma matriz de compressão de coluna $V$ .

Modelagem e Resolução Algébrica
Uma vez que uma matriz de compressão válida é adivinhada, o código público é comprimido em um subespaço equivalente a um código Gabidulin curto (especificamente um código $[k+1, k]$ ). O autor modela a condição de que este código comprimido deve ser um hiperplano $F_{q^m}$ anulado por um vetor específico. Isso leva a um sistema de equações bilineares que, após linearização, resulta em um sistema linear homogêneo sobre o corpo de extensão $F_{q^m}$ .

O núcleo do ataque envolve encontrar uma solução de posto-1 dentro do núcleo deste sistema linear. O autor observa que o núcleo admite uma base com entradas no corpo base $F_q$ . Consequentemente, o problema reduz-se a encontrar uma combinação linear dessas matrizes de base que resulte em uma matriz de posto-1. Isso é formulado como um sistema de equações quadráticas (anulação de menores $2 \times 2$ ).

Para resolver este sistema quadrático de forma eficiente, o autor emprega o método do autovalor (método do autovalor de Stickelberger) para sistemas polinomiais de dimensão zero. Eles aproveitam a estabilidade de Frobenius do núcleo para realizar computações sobre o corpo menor $F_q$ em vez de $F_{q^m}$ , reduzindo significativamente a complexidade. Uma conjectura fundamental (Conjectura 1) postula que a álgebra quociente do ideal gerado pelos menores tem uma dimensão igual a $m$ , garantindo que o sistema seja de dimensão zero e solucionável via autovalores.

Principais Contribuições

Distinguidor Híbrido: O artigo introduz um distinguidor que evita o custo total de força bruta dos métodos anteriores ao resolver para uma matriz de compressão algebricamente.
Recuperação de Chave em Tempo Polinomial: O autor demonstra que, se um dos fatores de anexação $\ell_1$ ou $\ell_2$ for zero, o ataque torna-se de tempo polinomial. Isso ocorre porque o fator de adivinhação exponencial desaparece, deixando apenas a etapa de resolução algébrica, que recupera a matriz de compressão oculta de forma eficiente.
Extensão de Código: Após recuperar um código Gabulín pontuado (curto), o autor fornece um algoritmo de tempo polinomial para estender este código de volta a um código Gabulín secreto de comprimento total, explorando a estrutura $q$ -Frobenius dos códigos Gabulín.
Decriptação Universal: A chave secreta equivalente recuperada (trapdoor) permite a decriptação de ambos os textos cifrados EGMC-McEliece e EGMC-Niederreiter.

Resultos
O ataque quebra todos os 16 conjuntos de parâmetros propostos para esquemas de criptografia EGMC-Niederreiter.

Redução de Segurança: Para o conjunto de parâmetros visando 128 bits de segurança com parâmetros $(2, 17, 37, 4, 0)$ , o ataque reduz o nível de segurança de um alegado 186 bits para aproximadamente 35 bits.
Eficiência: Na implementação do autor, a chave secreta equivalente para o conjunto de parâmetros de 128 bits é recuperada em menos de 10 minutos.
Comparação: O ataque supera as melhores abordagens anteriores (combinatórias e baseadas em MinRank) por margens largas, conforme mostrado na Tabela 1 do artigo.

Significância e Alegações
O artigo afirma que a construção EGMC, conforme proposta, falha em fornecer segurança pós-quântica para as famílias específicas de parâmetros onde $\ell_1 = 0$ ou $\ell_2 = 0$ . O autor argumenta que simplesmente aumentar os parâmetros sem mudar a construção de mascaramento não restaura a segurança para essas famílias, pois a etapa de resolução algébrica permanece de tempo polinomial.

O autor observa que um reparo potencial exigiria manter ambos $\ell_1$ e $\ell_2$ não nulos e suficientemente grandes para garantir que o mínimo das duas direções de ataque exceda o nível de segurança alvo. No entanto, ele alerta que aumentar esses parâmetros diretamente aumenta os tamanhos da chave pública e do texto cifrado, e resta investigar se tal reparo permaneceria competitivo com outros esquemas baseados em códigos. O artigo conclui que os parâmetros atuais do EGMC são inseguros e que o ataque proposto fornece tanto um distinguidor quanto um mecanismo completo de recuperação de chave.

A Grande Descoberta do Artigo

O Que o Artigo Realmente Quebra

O Que o Artigo Descarta

Quão Certos Eles Estão?

Mais como este