💻 computer science

Quantum Cryptanalysis on IBM Quantum Hardware: Extending Even--Mansour Period Recovery from $N=4$ to $N=10$

Este artigo apresenta uma demonstração genuína e não compilada em hardware quântico real da IBM de criptoanálise quântica fiel aos livros didáticos usando o algoritmo de Simon para recuperar períodos ocultos para estruturas de cifras Even-Mansour e Feistel até tamanhos recordes (N=10), ao mesmo tempo em que fornece um benchmark abrangente de cinco ataques através de quatro paradigmas de cifras simétricas com ressalvas explícitas em relação ao seu escopo, dependência de mitigação de erro e falta de ameaça à criptografia moderna em escala total.

Autores originais: Taebong Kim, Youngsik Hong, Minsik Kim, Sunyoung Choi, Jaewon Jang, Junghoon Shin, Minseo Kim

Publicado 2026-07-22

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Taebong Kim, Youngsik Hong, Minsik Kim, Sunyoung Choi, Jaewon Jang, Junghoon Shin, Minseo Kim

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 um mundo onde códigos secretos não estão apenas trancados em um cofre, mas escondidos dentro de um labirinto pelo qual apenas um fantasma pode caminhar. Este é o reino da criptoanálise quântica, um ramo da ciência onde pesquisadores usam as regras estranhas e misteriosas da física quântica para testar o quão fortes são nossos cadeados digitais. Para entender isso, você precisa saber três coisas simples. Primeiro, "cifras simétricas" são como uma chave única que tranca e destranca um baú de tesouro; se você tem a chave, pode abri-lo, mas se não tiver, ficará preso. Segundo, "computadores quânticos" são máquinas especiais que podem tentar muitos caminhos em um labirinto ao mesmo tempo, ao contrário dos computadores normais que devem tentar um caminho, depois outro, depois outro. Finalmente, há um truque famoso chamado "algoritmo de Simon", que é como um detetive superinteligente que pode encontrar um padrão oculto em uma bagunça caótica muito mais rápido do que um detetive comum, mas apenas se a bagunça tiver uma estrutura repetitiva muito específica.

Por que alguém se importa? Porque se um computador quântico puder encontrar esses padrões facilmente, as chaves secretas que protegem nossas contas bancárias, mensagens e segredos nacionais poderiam ser quebradas. Mas aqui está o detalhe: construir um computador quântico que seja grande o suficiente e silencioso o suficiente para realmente fazer isso é incrivelmente difícil. Eles são atualmente muito ruidosos, como tentar ouvir um sussurro em um show de rock. Este artigo é sobre uma equipe de pesquisadores que tentou ensinar um computador quântico real e ruidoso a encontrar esses padrões ocultos em códigos secretos, expandindo os limites do que é possível atualmente no mundo real.

O Artigo: Um Detetive Quântico em um Palco Ruidoso

Os pesquisadores, trabalhando com um computador quântico real fabricado pela IBM (especificamente o chip "ibm_kingston"), decidiram jogar um jogo de "encontrar o padrão oculto". Eles se concentraram em um tipo específico de estrutura de código secreto chamado cifra Even-Mansour. Imagine esta cifra como uma máquina que recebe um número secreto (a chave) e embaralha uma mensagem. O objetivo do ataque é encontrar o "período" — um ritmo repetitivo oculto na forma como a máquina embaralha os dados. Se você encontrar o ritmo, poderá descobrir a chave secreta.

No passado, cientistas haviam conseguido fazer isso apenas em versões muito pequenas e simples do código (onde o número secreto tinha apenas 4 bits de comprimento). Esta equipe queria ver até onde poderiam levar a máquina real. Eles conseguiram encontrar o ritmo oculto com sucesso para uma versão onde o número secreto tinha 10 bits de comprimento. Isso pode não parecer muito para você, mas no mundo do hardware quântico, saltar de 4 para 10 é um salto massivo. É como passar de equilibrar-se em um pé para correr uma maratona em uma corda bamba.

Eles não pararam por aí. Também testaram suas habilidades de detetive em outros tipos de estruturas de código:

O Feistel de 3 Rodadas: Uma estrutura usada em códigos antigos (como o famoso DES). Eles encontraram com sucesso o ritmo oculto para tamanhos de bloco de 6 e 8.
Bernstein-Vazirani: Um quebra-cabeça linear mais simples. Eles encontraram um segredo de 16 bits em apenas uma única pergunta (query), exatamente o que a matemática prometia.
Busca de Grover: Eles testaram um método para buscar chaves não estruturadas, mostrando que o computador quântico poderia encontrar uma chave em cerca de 13 passos, quando um computador normal precisaria de 256 passos.

O Choque de Realidade: O Quão Bom Foi?

Esta é a parte mais importante da história, e a parte em que os autores são muito, muito honestos. Embora tenham encontrado os padrões, eles não quebraram o código de uma forma que lhes permitisse roubar sua conta bancária hoje.

Para os quebra-cabeças maiores (onde o segredo tinha 6 bits ou mais), o computador quântico ficou um pouco "ruidoso" e confuso. Ele não apontou para a única resposta correta imediatamente. Em vez disso, ele deu uma lista dos principais candidatos. Os pesquisadores então usaram um computador comum para verificar os principais 16, 32, 64 ou 128 candidatos da lista quântica. A verdadeira chave secreta geralmente era encontrada muito no topo dessa lista (frequentemente dentro dos primeiros 63 candidatos), o que é muito melhor do que adivinhar aleatoriamente.

Os autores são muito claros: isso ainda não é uma "vantagem quântica".

Sem Solução Mágica: Eles não quebraram as versões completas e reais de códigos famosos como AES ou RSA. Eles apenas quebraram versões reduzidas e simplificadas das estruturas.
Sem Supervelocidade: Para os quebra-cabeças maiores, o computador quântico não resolveu tudo sozinho. Ele estreitou a lista de suspeitos, mas um computador comum ainda teve que fazer o trabalho final. O ganho de velocidade que viram foi no número de perguntas feitas, não no tempo total levado para quebrar o código.
Ruído vs. Perfeição: Eles usaram "mitigação de erro" (uma forma elegante de dizer que limparam os dados ruidosos) em vez de "correção de erro" (que corrigiria os erros perfeitamente). Isso significa que seus resultados são impressionantes para a tecnologia atual, mas não são a solução final e perfeita.

O Panorama Geral

A equipe também executou uma simulação massiva em um supercomputador para ver até onde isso poderia ir se tivessem máquinas perfeitas e sem ruído. Eles descobriram que, embora um computador quântico pudesse teoricamente lidar com esses quebra-cabeças facilmente, um computador normal ficaria sem memória tentando simular um computador quântico com apenas 25 qubits (as unidades básicas de informação quântica). Um quebra-cabeça ligeiramente maior exigiria 4,5 petabytes de memória — mais do que a maioria dos centros de dados possui!

Então, qual é a conclusão? Este artigo é um "recorde mundial" de quão grande uma estrutura de código secreto um computador quântico real e ruidoso conseguiu analisar com sucesso. Ele prova que a matemática funciona em hardware real, mesmo que o hardware ainda seja um pouco instável. É uma prova de conceito que diz: "Nós podemos fazer isso, mas precisamos de máquinas melhores e mais silenciosas antes de podermos realmente quebrar os segredos do mundo real". Os autores tornaram seu código e dados públicos para que qualquer pessoa possa verificar seu trabalho, garantindo que isso não seja apenas uma afirmação, mas um passo reproduzível à frente na corrida entre computadores quânticos e códigos secretos.

Resumo Técnico: Criptoanálise Quântica em Hardware IBM Quantum

Declaração do Problema

A pesquisa teórica estabeleceu há muito tempo que estruturas de cifras simétricas específicas, como a cifra Even–Mansour e redes Feistel de 3 rodadas, podem ser reduzidas a problemas de período oculto solucionáveis pelo algoritmo de Simon. No entanto, existe uma lacuna significativa entre essas reduções teóricas e a execução prática em dispositivos quânticos de escala intermediária ruidosa (NISQ). Antes deste trabalho, as demonstrações de recuperação de chave em hardware real foram limitadas a parâmetros de segurança muito pequenos (especificamente $N=4$ ) devido ao ruído do dispositivo e à falta de correção de erros tolerante a falhas. O desafio reside em estender esses ataques para tamanhos de estrutura maiores ( $N > 4$ ) em hardware real, mantendo a integridade algorítmica "genuína" — o que significa que os circuitos devem implementar os mapas chaveados reais sem atalhos de transpilação que trivializariam a busca.

Metodologia

Os autores executaram criptoanálise quântica "genuína, não compilada e fiel ao modelo teórico" no processador IBM ibm_kingston (geração Heron) utilizando o framework Qiskit. A metodologia é caracterizada pelos seguintes componentes:

Escopo Algorítmico: O estudo visa quatro paradigmas de design de cifras simétricas:
1. Estrutura Linear: Algoritmo de Bernstein–Vazirani (consulta única).
2. Busca Não Estruturada: Algoritmo de Grover aplicado a uma busca de chave SPN (Rede de Substituição-Permutação) reduzida.
3. Problemas de Período Oculto: Algoritmo de Simon aplicado a:
  - Cifra Even–Mansour.
  - Forja de CBC-MAC.
  - Construção Feistel de 3 rodadas (família DES).
Estratégia de Execução:
- Hardware Real: Os experimentos utilizaram uma pilha abrangente de mitigação de erro de leitura (incluindo calibração, desacoplamento dinâmico e twirling), em vez de correção de erro tolerante a falhas.
- Abordagem Híbrida para $N > 5$ : Para instâncias de Even–Mansour onde o ruído impediu uma recuperação "rank-1" limpa, os autores empregaram um híbrido de estreitamento quântico + verificação clássica. O circuito quântico gerou uma lista curta dos principais candidatos (ex: top-16 ou top-128), que foram então verificados classicamente.
- Validação: Todos os resultados de hardware foram validados cruzados contra chaves de controle independentes para garantir que os períodos recuperados não fossem artefatos de seleções de chaves específicas.
- Simulação: Um benchmark de busca em largura foi conduzido utilizando simulação de estado vetorial genuína (em hardware NVIDIA B200) até o limite de memória clássica de 25 qubits para validar os circuitos não compilados.

Principais Resultados

1. Extensão da Fronteira de Hardware Real

O artigo relata a recuperação do período oculto de Even–Mansour até o parâmetro de segurança $N = 10$ em hardware real.

$N = 5$ : Alcançou uma recuperação rank-1 limpa (Simon diferencial) onde a chave verdadeira foi o principal candidato.
$N = 6$ a $N = 10$ : Alcançado via abordagem híbrida. Embora a chave verdadeira nem sempre tenha sido o único saída do topo devido ao ruído, seu ranking acompanhou o limite de aniversário (birthday bound) ( $2^{n/2}$ ), permanecendo ordens de magnitude abaixo da expectativa aleatória ( $2^{n-1}$ ).
Comparação: Isso excede o maior tamanho de $N = 4$ previamente relatado em hardware real.

2. Recuperação de Feistel e Estrutura Linear

Feistel de 3 Rodadas: Recuperou claramente o período para tamanhos de bloco 6 e 8 (rank-1, exato) em hardware real. Uma instância de bloco-10 com 21 qubits foi verificada em simulação e submetida ao hardware.
Bernstein–Vazirani: Extraiu com sucesso um segredo linear de 16 bits em uma única consulta em hardware real.

3. Separação de Complexidade

O estudo demonstra a separação teórica de complexidade de consulta:

Ataques baseados em Simon: Complexidade de consulta clássica exponencial ( $2^{n/2}$ ) vs. consultas quânticas polinomiais ( $\Theta(n)$ ).
Ataques baseados em Grover: Aceleração quadrática (ex: recuperar uma chave de 8 bits em $\approx 13$ iterações vs. 256 avaliações clássicas).

Significância e Alegações

Os autores enquadram explicitamente suas contribuições com foco na honestidade e reprodutibilidade, evitando o exagero de "vantagem quântica".

Demonstração em Hardware Real: A principal contribuição é a demonstração de criptoanálise quântica genuína em hardware real em tamanhos de estrutura recordes ( $N=10$ para Even–Mansour), preenchendo a lacuna entre reduções teóricas e execução física.
Abrangência de Cobertura: O trabalho fornece um benchmark abrangente através de quatro paradigmas criptográficos distintos (Linear, Não Estruturado, Período Oculto) e cinco ataques específicos, todos validados até o limite de simulação clássica.
Sem Vantagem Quântica de Ponta a Ponta: O artigo afirma explicitamente que esses ataques não constituem uma vantagem quântica sobre métodos clássicos em termos de custo de ponta a ponta. Os ataques seguem assintoticamente o limite de aniversário, o que significa que a busca de colisões clássica alcança uma escalabilidade comparável. A separação é estritamente na complexidade de consulta para o distinguidor, não no custo computacional total.
Limitações de Escopo:
- Os ataques visam construções reduzidas ou estruturadas (Even–Mansour, Feistel de 3 rodadas, SPN reduzida), não AES completo, RSA ou DES de 16 rodadas.
- Os resultados dependem de mitigação de erro, não de correção de erro tolerante a falhas.
- O modelo de oráculo Q2 (consulta quântica) é assumido, embora os autores reconheçam suas limitações práticas e notem que reduções offline-Simon podem relaxar algumas suposições para Q1.

Em resumo, este artigo serve como um benchmark rigoroso e reprodutível de algoritmos quânticos genuínos em hardware NISQ, demonstrando que, embora os dispositivos atuais não possam quebrar cifras modernas de escala total, eles podem executar com sucesso reduções criptanalíticas complexas em primitivas estruturadas em tamanhos anteriormente inalcançáveis em hardware real.