💻 computer science

Quantum Key Search Algorithms under Side-channel Attack

Este artigo propõe um algoritmo de busca de chave quântica aprimorado que aproveita distribuições de erro induzidas por ataques de canal lateral para alcançar um ganho superquadrático sobre métodos clássicos e superar abordagens quânticas existentes, como a de Glaser, ao mesmo tempo em que aborda desafios de preparação de estado de entrada por meio de uma implementação eficiente de estados de Dicke.

Autores originais: Yunteng Yang, Jianhong Shi, Hailong Zhang, Hongwei Li, Xiangqun Fu, Yonghui Yang, Yubing Zhu, Yanyang Zhou

Publicado 2026-08-12

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Yunteng Yang, Jianhong Shi, Hailong Zhang, Hongwei Li, Xiangqun Fu, Yonghui Yang, Yubing Zhu, Yanyang Zhou

Artigo original sob licença CC BY 4.0 (https://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ê está tentando decifrar a combinação de um cadeado em um cofre gigante e de alta tecnologia. No mundo da segurança digital, esse "cadeado" é uma chave criptográfica — uma longa sequência de 0s e 1s que protege suas mensagens, contas bancárias e segredos. Durante décadas, a única maneira de abrir esse cofre era tentar cada uma das combinações possíveis, uma por uma, até ter sorte. É como tentar todas as chaves em um chaveiro enorme; se houver um bilhão de chaves, você pode ter que tentar meio bilhão antes de encontrar a certa. Esta é a maneira "clássica" de fazer as coisas, e é lenta.

Então, cientistas descobriram uma ferramenta mágica chamada "computador quântico". Pense nele não como uma calculadora mais rápida, mas como um mago que pode olhar para muitas chaves ao mesmo tempo. Usando um truque famoso chamado algoritmo de Grover, esse mago pode encontrar a chave certa muito mais rápido do que o método antigo — reduzindo o tempo de um bilhão de tentativas para cerca de trinta mil. Mas aqui está a reviravolta: e se você não tiver que começar do zero? E se um ladrão sorrateiro já tivesse espiado o cofre e obtido uma versão ruidosa, borrada da chave? Talvez ele tenha visto que a chave era "majoritariamente" 101010, mas alguns bits estavam imprecisos. Isso é chamado de "ataque de canal lateral" (side-channel attack). É como encontrar uma impressão digital no cofre que lhe dá uma dica, mesmo que não seja perfeita. A grande questão para os cientistas é: podemos usar essas dicas borradas para tornar o mago quântico ainda mais inteligente e rápido?

Este artigo, escrito por uma equipe de pesquisadores da Information Engineering University, mergulha profundamente exatamente nesse cenário. Eles perguntam: se um atacante possui uma chave ruidosa com alguns erros (como uma foto borrada da solução), como podemos usar computadores quânticos para encontrar a chave real mais rápido do que nunca?

Os pesquisadores primeiro observaram como um computador comum lidaria com isso. Eles perceberam que, se você sabe que a chave está "majoritariamente" correta, não deve adivinhar aleatoriamente. Em vez disso, você deve começar adivinhando a chave que se parece exatamente com a chave ruidosa, depois adivinhar chaves que têm apenas um pequeno erro, depois dois erros, e assim por diante. É como pesquisar em uma biblioteca começando pelos livros que mais se parecem com o que você está procurando, em vez de entrar e pegar livros aleatórios no fundo da sala. Eles calcularam exatamente quantas tentativas esse método clássico "inteligente" levaria.

Em seguida, eles construíram um novo algoritmo quântico para fazer o mesmo, mas com o poder da mecânica quântica. Eles notaram que métodos quânticos anteriores tentavam dividir o espaço de busca em blocos que cresciam em um padrão geomético (1, depois 10, depois 100). No entanto, os pesquisadores descobriram que as dicas da "chave ruidosa" na verdade criam um padrão muito específico baseado em quantos bits estão errados (a distância de Hamming). Em vez de usar um padrão geométrico, eles decidiram agrupar as chaves pelo número de erros que elas possuem: um grupo para chaves com 0 erros, um grupo para chaves com 1 erro, um grupo para 2 erros, e assim por diante.

Eles desenharam uma estratégia onde o computador quântico aborda esses grupos um por um, começando pelo grupo que é mais provável que contenha a resposta. Para fazer isso funcionar, eles tiveram que resolver um problema complicado: como preparar o computador quântico para olhar para apenas as chaves que têm, digamos, exatamente 3 erros, sem perder tempo com as outras. Eles resolveram isso usando um estado quântico especial chamado "estado de Dicke". Você pode pensar no estado de Dicke como um baralho de cartas perfeitamente organizado onde cada carta tem exatamente o mesmo número de corações vermelhos. Uma vez que eles têm esse estado organizado, eles podem facilmente inverter as cartas para corresponder à chave ruidosa que possuem. Essa preparação é eficiente e não exige equipamentos extras ou complicados.

Quando rodaram simulações para testar seu novo método, os resultados foram impressionantes. Eles usaram uma chave de 256 bits (uma chave muito longa e segura) com uma taxa de erro minúscula de 1% (significando que a chave ruidosa estava 99% correta).

Um computador clássico padrão precisaria fazer cerca de $2^{256}$ tentativas se não tivesse dicas.
Com a dica ruidosa, um computador clássico inteligente ainda precisaria de cerca de $2^{62.29}$ tentativas.
O novo algoritmo quântico deles, no entanto, precisou de apenas cerca de $2^{19.77}$ tentativas.

Isso significa que o método quântico deles é significativamente mais rápido do que o método clássico inteligente. Eles calcularam um "fator de aceleração" de 3,15, que é maior do que o fator de 2,73 alcançado por métodos anteriores (como os de Glaser). Em termos simples, o mago quântico deles não está apenas olhando para mais chaves ao mesmo tempo; ele está olhando para as chaves certas primeiro, graças à forma específica como organizaram a busca.

O artigo também argumenta explicitamente contra o uso da estratégia antiga de blocos de crescimento geométrico (como o algoritmo de Montanaro) para este tipo específico de problema de chave ruidosa. Eles mostram que, como os erros seguem uma "distribuição de Bernoulli" (um padrão de inversões aleatórias), a abordagem geométrica não é a mais eficiente. A abordagem de "distância de Hamming" deles, que agrupa as chaves pelo número exato de erros, é um ajuste melhor para a realidade.

Em resumo, esta pesquisa sugere que, ao combinar as "dicas borradas" de ataques de canal lateral com uma estratégia de busca quântica inteligentemente organizada, podemos quebrar chaves muito mais rápido do que antes. Embora esses resultados sejam baseados atualmente em simulações e provas matemáticas, e não em um computador quântico físico executando o código, a matemática mostra um caminho claro para uma busca de chave quântica super rápida que supera tanto a adivinhação convencional quanto tentativas quânticas anteriores. A equipe conclui que este método não é apenas teoricamente sólido, mas também praticamente viável de construir, pois a preparação do "estado de Dicke" que propuseram pode ser feita com um número gerenciável de etapas e sem a necessidade de hardware extra e complexo.

Resumo Técnico: Algoritmos de Busca de Chave Quântica sob Ataque de Canal Lateral

Declaração do Problema
Esta pesquisa aborda o problema da busca de chave em algoritmos criptográficos quando um atacante possui uma chave ruidosa derivada de ataques de canal lateral (SCA - Side-Channel Attacks). Neste cenário, o atacante obtém uma chave $Y$ que difere da verdadeira chave alvo $k^*$ por um certo número de inversões de bits (distância de Hamming). A distribuição de probabilidade do espaço de chaves não é uniforme; em vez disso, ela segue uma distribuição de Bernoulli $n$ -dobrada determinada pela taxa de erro de bit (BER), $\alpha$ . O desafio é buscar eficientemente este espaço de chaves não uniforme para encontrar $k^*$ , aproveitando a informação prévia fornecida pela chave ruidosa. Enquanto a busca clássica por força bruta requer $O(N)$ consultas e o algoritmo de Grover padrão oferece $O(\sqrt{N})$ , nenhum dos dois explora totalmente a estrutura específica da distribuição de Bernoulli induzida por SCAs. Além disso, abordagens quânticas existentes, como o algoritmo de Montanaro, enfrentam dificuldades na preparação dos estados de superposição iniciais específicos necessários para blocos de chaves com probabilidades posteriores iguais.

Metodologia
Os autores propõem um framework abrangente que abrange modelagem teórica, design de algoritmo e preparação de estado:

Modelagem Probabilística: O estudo modela a distribuição do espaço de chaves assumindo inversões de bits independentes e identicamente distribuídas (i.i.d.) com probabilidade $\alpha$ . Usando o teorema de Bayes, demonstra-se que a probabilidade posterior de uma chave candidata depende exclusivamente de sua distância de Hamming $d$ em relação à chave ruidosa $Y$ . Isso estabelece que chaves com a mesma distância de Hamming compartilham a mesma probabilidade posterior.
Linha de Base Clássica: Um algoritmo de busca de chave clássico é derivado, que percorre as chaves candidatas em ordem decrescente de probabilidade posterior (ou seja, começando da distância de Hamming $d=0$ até $d=n$ ). A complexidade de consulta esperada $G_c$ é calculada estritamente com base na distribuição binomial das chaves candidatas em cada distância.
Algoritmo Quântico Melhorado:
- Estratégia de Partição: Diferente do algoritmo de Montanaro, que particiona o espaço de chaves em blocos de crescimento geométrico $\{1, c, c^2, \dots\}$ , este artigo propõe particionar o espaço de chaves em $(n+1)$ blocos $\{R_0, R_1, \dots, R_n\}$ baseados estritamente na distância de Hamming $d$ . Cada bloco $R_d$ contém todas as $\binom{n}{d}$ chaves candidatas com exatamente $d$ erros de bit.
- Execução da Busca: O algoritmo itera através desses blocos em ordem de decréscimo de probabilidade (aumento de $d$ ). Para cada bloco $R_d$ , ele prepara uma superposição uniforme das chaves naquele bloco e aplica o algoritmo de Grover.
- Análise de Complexidade: A complexidade de consulta quântica $G_q$ é derivada somando os custos da busca de Grover sobre cada bloco, ponderados pela probabilidade de a chave alvo residir naquele bloco.
Preparação do Estado Inicial: Para resolver a dificuldade de preparar o estado de superposição específico para cada bloco $R_d$ $R_{d}$ , os autores estabelecem uma equivalência entre o estado da chave candidata e o estado Dicke $|D^n_d\rangle$ $∣ D_{d}^{n} ⟩$ . Eles provam que a superposição uniforme de chaves na distância de Hamming $d$ $d$ de $Y$ $Y$ pode ser gerada aplicando um produto tensorial de portas Pauli-X ( $X^{\otimes Y}$ $X^{\otimes Y}$ ) ao estado Dicke $|D^n_d\rangle$ $∣ D_{d}^{n} ⟩$ .
- Implementação: O estado Dicke é preparado usando um circuito de profundidade curta, do tipo "dividir para conquistar" (baseado no trabalho de Bärtschi e Eidenbenz) que não requer qubits auxiliares. O estado final é obtido aplicando $O(d)$ portas X baseadas na chave ruidosa $Y$ .

Principais Contribuições

Derivação Teórica: O artigo fornece uma derivação rigorosa da complexidade computacional para busca de chave tanto clássica quanto quântica sob condições de ataque de canal lateral, modelando especificamente a distribuição de Bernoulli $n$ -dobrada.
Melhoria Algorítmica: Introduz um algoritmo de busca de chave quântica melhorado que utiliza uma estratégia de partição de blocos baseada na distância de Hamming. Esta estratégia mostra-se mais consistente com a distribuição real de chaves em cenários de SCA do que a partição de crescimento geométrico usada no algoritmo de Montanaro.
Solução de Preparação de Estado: O trabalho resolve o gargalo de preparação do estado de entrada transformando o problema em preparação de estado Dicke. Demonstra-se que o estado necessário pode ser gerado com $O(nd)$ portas CNOT e baixa profundidade de circuito ( $O(d \log \frac{n}{d})$ para topologia de armadilha de íons ou $O(\sqrt{nd})$ para topologia supercondutora) sem qubits auxiliares.

Resultos
Resultados de simulação para uma chave criptográfica de 256 bits com uma taxa de erro de bit (BER) de 1% ( $\alpha = 0,01$ ) demonstram ganhos significativos de desempenho:

Redução de Complexidade: A complexidade de consulta para o algoritmo clássico sob condições de SCA cai de $2^{256}$ (sem SCA) para $2^{62,29}$ . O algoritmo quântico proposto reduz isso ainda mais para $2^{19,77}$ .
Fator de Aceleração (Speedup): O algoritmo quântico proposto alcança um fator de aceleração de 3,15 em relação ao algoritmo clássico sob condições de SCA. Isso é comparado ao fator de aceleração de 2,73 relatado por Glaser et al. (que analisaram o algoritmo de Montanaro) sob as mesmas condições. Os autores observam que sua eficiência de busca é aumentada em 15,38% em comparação com a eficiência alcançada pelo algoritmo de crescimento geométrico de Montanaro proposto em [9].
Comparação com Limites: O artigo afirma que a complexidade de consulta quântica derivada ( $2^{19,77}$ ) é mais precisa e estreita do que os limites superior/inferior ( $2^{21,59}$ e $2^{17,59}$ ) estimados por Glaser para o algoritmo de Montanaro neste cenário de distribuição específica.
Eficiência de Recursos: O esquema de preparação de estado mostrou-se viável para circuitos de profundidade curta, com contagens de recursos específicas fornecidas para $n=256$ e $d=4$ (por exemplo, 1024 portas CNOT, 0 qubits auxiliares).

Significância
O artigo afirma que sua pesquisa fornece uma solução de cadeia completa, desde a análise teórica até a implementação prática para criptoanálise quântica sob ataques de canal lateral. Ao aproveitar a estrutura específica do ruído de canal lateral (distribuição de Bernoulli), o algoritmo proposto alcança um aceleração super-quadrática sobre seus equivalentes clássicos, superando adaptações de busca quântica anteriores, como a de Montanaro. A capacidade de preparar os estados iniciais necessários usando circuitos de profundidade curta e sem ancilas aborda uma barreira crítica para o implantação prática da busca de chave quântica. Os autores afirmam que estes resultados oferecem uma estimativa de complexidade mais precisa e uma estratégia de busca mais eficiente para cenários onde a informação prévia na forma de uma chave ruidosa está disponível. O trabalho futuro é identificado como a exploração da integração deste algoritmo com cifras específicas (AES, SM4) e a análise do impacto do ruído quântico.

Mais como este