Algoritmo quântico de Simon: uma possível virada teórica, não uma crise imediata para a criptografia pós-quântica

Mas há uma diferença importante entre uma possível descoberta teórica e uma quebra prática de sistemas. Até o início de agosto de 2026, o trabalho continuava sem revisão por pares, não havia sido confirmado ou refutado de forma independente e não apresentava um ataque implementado contra qualquer criptossistema padronizado .

O que o preprint afirma

O DCP pertence à família de problemas de subgrupos ocultos, na qual o objetivo é recuperar uma informação escondida a partir de amostras quânticas. Ele é estudado há anos por sua relação com problemas de reticulados e com a segurança pós-quântica.

As principais alegações de Simon são:

• Um solucionador de DCP em tempo polinomial. O algoritmo proposto resolveria o DCP em tempo polinomial em um computador quântico. A abordagem se apoia na redução de Regev, que conectou o Problema do Subgrupo Diédrico ao DCP .
• Uma possível resposta para uma lacuna de 20 anos. Desde que o trabalho de Regev relacionou o DCP a problemas de reticulados, permaneceu em aberto a obtenção de um algoritmo eficiente para o problema. Se a prova estiver correta, o novo resultado poderá preencher essa lacuna, que remonta aproximadamente a 2004 .
• Uma técnica diferente das abordagens anteriores. O artigo substitui um oráculo importante de métodos prévios por uma técnica descrita como “block-and-query”, voltada à extração de informações sobre o subgrupo oculto .
• Consequências alegadas para problemas de reticulados. O texto afirma que o algoritmo pode ser combinado com reduções de Regev e aprimoramentos de Brakerski, Kirshanova, Stehlé e Wen . O resultado seria a obtenção de algoritmos quânticos de tempo polinomial para problemas como uma aproximação por fator polinomial do vetor mais curto — o SVP, ou Shortest Vector Problem — e o LWE, sigla de Learning With Errors .

O preprint também afirma que o método conseguiria tolerar uma taxa de amostras defeituosas de até 1/O(log n). Essa tolerância seria necessária para combinar o algoritmo com a cadeia de reduções e, segundo o artigo, resolver problemas de reticulados de maneira eficiente .

Por que a comunidade está cautelosa

A reação inicial não foi de aceitação imediata, mas de escrutínio intenso. O texto é identificado como “Preliminary Draft” e foi disponibilizado no servidor ePrint da IACR em agosto de 2026 . Portanto, ainda não passou pelo processo usual de avaliação por especialistas de uma conferência ou revista científica.

As principais razões para a cautela são:

• Provas essenciais aparecem como esboços. Análises iniciais observaram que algumas demonstrações consideradas fundamentais para o resultado são apresentadas de forma resumida, sem todos os detalhes necessários para uma verificação independente .
• A conclusão sobre SVP e LWE depende parcialmente de referências não publicadas. A etapa final do argumento é descrita, em parte, com base em comunicações pessoais ainda não acompanhadas por derivações publicadas .
• Ainda não há confirmação independente. Nos dias que se seguiram à divulgação, não havia uma verificação ou refutação independente publicada . A orientação predominante foi priorizar os fatos e a checagem matemática antes de tirar conclusões.
• O resultado é teórico. O trabalho não contém uma implementação de ataque contra um sistema padronizado. O alvo direto é o DCP, não uma instância operacional de ML-KEM, ML-DSA ou outro mecanismo adotado em padrões atuais .

Em termos simples: o ponto que precisa ser validado primeiro é a prova do algoritmo. Mesmo que a solução do DCP esteja correta, ainda será necessário verificar cuidadosamente cada redução e cada hipótese usada para transferir o resultado a problemas específicos de criptografia.

O que isso significa para ML-KEM e ML-DSA

Para empresas e órgãos que estão implementando ou avaliando os padrões de criptografia pós-quântica do NIST, a orientação imediata permanece a mesma: não há, com base nesse preprint, motivo para interromper a migração ou trocar parâmetros .

Não existe uma ameaça prática imediata

O trabalho não implementa um ataque contra o ML-KEM, mecanismo de encapsulamento de chaves padronizado no FIPS 203, nem contra o ML-DSA, algoritmo de assinaturas digitais definido no FIPS 204 . Também não há indicação de que qualquer conjunto de parâmetros do NIST tenha sido atacado .

A conexão com os padrões é indireta

O DCP possui conexões conhecidas com problemas de reticulados. Porém, transformar um algoritmo eficiente para DCP em um ataque concreto contra as hipóteses específicas usadas pelo ML-KEM e pelo ML-DSA é uma etapa teórica adicional.

Esses padrões dependem, respectivamente, de variantes estruturadas relacionadas ao Module-LWE e ao Module-SIS. O fato de um algoritmo resolver uma classe de problemas de reticulados não demonstra, por si só, que ele quebra essas instâncias estruturadas específicas .

O risco, por enquanto, é estrutural e não operacional

Se a alegação for validada, ela poderá fortalecer a hipótese de que computadores quânticos conseguem resolver eficientemente certos problemas de reticulados. Isso seria importante para a avaliação de longo prazo dos fundamentos da criptografia pós-quântica.

Ainda assim, “problemas de reticulados” é uma categoria ampla. Os algoritmos do NIST usam estruturas e distribuições específicas, e a distância entre um resultado geral sobre DCP e um ataque efetivo contra ML-KEM ou ML-DSA ainda não foi demonstrada .

O contexto dos resultados anteriores

A área já vinha registrando avanços em versões relacionadas do problema. Em 2025, Bai e colaboradores apresentaram um algoritmo quântico de tempo quase polinomial para uma variante restrita do DCP, o Extrapolated Dihedral Coset Problem, sobre módulos que são potências de dois .

A alegação de Simon de obter tempo polinomial para o DCP completo representaria um salto significativo além desse resultado. É justamente por isso que o preprint chamou atenção — e também por isso que seus detalhes precisam ser examinados com cuidado antes de qualquer revisão de parâmetros criptográficos.

O consenso provisório: verificar antes de reagir

Analistas da indústria de segurança pós-quântica descreveram a reação inicial como de “forte ceticismo”, citando os esboços de prova e a dependência de referências não publicadas . Ao mesmo tempo, a importância potencial da afirmação não é ignorada.

O impacto sobre a criptografia baseada em reticulados é condicional: depende de a prova estar correta e de as reduções até os problemas específicos relevantes para os padrões realmente preservarem as condições necessárias . Resolver o DCP não equivale automaticamente a quebrar ML-KEM ou ML-DSA.

Até aquele momento, NIST, laboratórios acadêmicos e organismos de padronização ainda não haviam emitido declarações formais sobre o preprint . Isso é compatível com a idade do trabalho e com a necessidade de uma análise matemática independente.

A conclusão mais responsável, portanto, é dupla: o artigo de Daniel Simon apresenta uma reivindicação teórica potencialmente histórica, mas ainda não um resultado estabelecido. E, no plano prático, os padrões ML-KEM e ML-DSA continuam sem um ataque demonstrado com base nesse trabalho — portanto, não há razão imediata para tratá-los como quebrados ou alterar os planos de adoção da criptografia pós-quântica .