A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions

Este artigo apresenta uma nova codificação QUBO compacta para fórmulas de lógica computacional que, ao reduzir drasticamente o número de variáveis lógicas em algoritmos criptográficos como AES e SHA, aumenta a vulnerabilidade desses sistemas contra futuros annealers quânticos.

O essencial

Imagine que você tem um cofre digital super complexo (como um algoritmo de criptografia AES ou SHA) e quer descobrir a chave secreta para abri-lo. Para fazer isso em um computador comum, você teria que tentar bilhões de combinações, o que levaria séculos.

Mas e se existisse um tipo de "computador mágico" (chamado Quantum Annealer) capaz de encontrar a chave perfeita instantaneamente? O problema é que esses computadores mágicos não entendem a linguagem dos cofres (circuitos lógicos complexos). Eles só falam uma língua muito específica e simples: o QUBO.

Este artigo é sobre como os autores criaram um tradutor super eficiente para converter esses cofres complexos em linguagem QUBO, tornando-os muito menores e mais fáceis para o computador mágico entender.

Aqui está a explicação passo a passo, usando analogias do dia a dia:

1. O Problema: A "Caixa de Ferramentas" Gigante

Antes deste trabalho, para traduzir um algoritmo de criptografia para QUBO, os cientistas precisavam de uma "caixa de ferramentas" (variáveis) gigantesca. Era como tentar montar um quebra-cabeça de 10.000 peças usando apenas peças de 10.000 peças, quando na verdade você só precisava de 1.000.

Isso tornava o problema impossível de resolver nos computadores atuais, porque a "caixa" era grande demais para caber na memória do computador mágico.

2. A Solução: O "Encolhedor Mágico" (ILP e Padrões)

Os autores desenvolveram uma nova estratégia para encolher essa caixa de ferramentas. Eles usaram uma técnica matemática chamada Programação Linear Inteira (ILP).

• A Analogia: Imagine que você tem que empacotar móveis para uma mudança. A maneira antiga era colocar cada móvel em uma caixa separada, desperdiçando espaço.
• A Nova Maneira: Os autores criaram um algoritmo que analisa os móveis e descobre: "Ei, essa mesa e essa cadeira cabem perfeitamente juntas em uma caixa menor, se eu girá-las de um jeito específico".
• O Resultado: Eles encontraram padrões (como "Root Squeezing Theorem") que permitem empacotar a lógica complexa em muito menos variáveis. Eles descobriram que, em vez de usar uma variável para cada "sim/não" de uma operação, podem usar uma única variável inteligente para representar várias operações ao mesmo tempo.

3. Os "Truques" Específicos (XOR, OR e AND)

A criptografia é feita de blocos de construção lógicos:

• XOR (Ou Exclusivo): Como um interruptor que só acende se você apertar um botão ímpar de vezes.
• OR (Ou): Como uma luz que acende se qualquer um dos interruptores estiver ligado.
• AND (E): Como uma luz que só acende se todos os interruptores estiverem ligados.

O artigo mostra como criar "atalhos" para esses blocos.

• Para o XOR: Eles usam uma técnica de "paridade" (contar se a soma é par ou ímpar) que economiza muitas peças.
• Para o OR e AND: Eles usam uma técnica chamada "Espremer Raízes" (Root Squeezing). Imagine que você tem uma faixa de números de 1 a 10. Em vez de precisar de 4 bits para representar cada número, eles criaram um código onde um único código de 3 bits pode representar dois números diferentes ao mesmo tempo, cortando o tamanho da caixa pela metade.

4. O Teste de Fogo: Quebrando Cofres Reais

Para provar que o método funciona, eles aplicaram essa "caixa de ferramentas encolhida" nos algoritmos de criptografia mais famosos do mundo:

• AES: O padrão usado para proteger bancos e mensagens no WhatsApp.
• SHA e MD5: Algoritmos usados para verificar a integridade de arquivos e senhas.

Os Resultados Espetaculares:

• Para o AES-256 (o cofre mais forte), eles reduziram o tamanho do problema em mais de 8 vezes.
• Em vez de precisar de cerca de 250.000 variáveis (como nos métodos antigos), eles conseguiram fazer com apenas 30.000.
• Isso significa que, com os computadores quânticos do futuro (que terão cerca de 30.000 "bits" de capacidade), será possível quebrar esses cofres que hoje são considerados inquebráveis.

5. Por que isso importa? (O Perigo e a Oportunidade)

• O Perigo: Isso mostra que a criptografia atual pode estar em risco. Se os computadores quânticos evoluírem rápido, eles poderão usar essa "tradução eficiente" para descobrir chaves secretas em minutos, não em séculos.
• A Oportunidade: Para os cientistas, isso é uma vitória. Significa que estamos aprendendo a falar a língua dos computadores quânticos de forma muito mais eficiente. Isso permite resolver problemas complexos de logística, finanças e inteligência artificial que antes eram impossíveis.

Resumo Final

Pense neste artigo como a criação de um super-compactador de arquivos para a linguagem dos computadores quânticos. Antes, tentar resolver um problema de criptografia era como tentar carregar um caminhão inteiro de areia em um carro de brinquedo. Agora, os autores descobriram como transformar essa areia em um cubo de gelo pequeno e leve, que cabe perfeitamente no carro de brinquedo, permitindo que ele viaje rápido e chegue ao destino (a solução do problema) muito antes do que imaginávamos.

Eles provaram que, com a lógica certa, podemos fazer o impossível parecer fácil, mesmo que isso signifique que nossos cofres digitais precisarão ser redesenhados para o futuro.

Resumo técnico

Resumo Técnico: Codificação Compacta QUBO para Fórmulas Lógicas Computacionais

1. O Problema

O artigo aborda o desafio de codificar problemas de otimização combinatória, especificamente aqueles relacionados a algoritmos de criptografia e funções de hash, no formato de Otimização Binária Quadrática Sem Restrições (QUBO).

• Contexto: A QUBO é fundamental para o funcionamento de annealers quânticos (como os da D-Wave), que buscam o mínimo global de uma função de energia.
• Desafio: As codificações tradicionais de problemas lógicos (SAT) para QUBO frequentemente resultam em um número excessivo de variáveis binárias (qubits lógicos) e coeficientes de grande magnitude. Isso torna os problemas intratáveis para hardware quântico atual, que possui recursos limitados (número de qubits físicos e precisão numérica).
• Objetivo: Desenvolver uma estratégia de codificação que minimize drasticamente o número de variáveis e mantenha os coeficientes baixos, permitindo que algoritmos complexos (como AES-256 e SHA-256) sejam mapeados para dispositivos quânticos futuros.

2. Metodologia

Os autores propõem uma abordagem sistemática baseada em Programação Linear Inteira (ILP) para descobrir padrões de codificação ótimos.

• Abordagem Baseada em ILP:

  • Em vez de tentar resolver o problema SAT diretamente via QUBO, o objetivo é encontrar padrões de mapeamento reutilizáveis.
  • O método formula um problema de ILP onde o objetivo é encontrar coeficientes para uma função quadrática $g(x, s)$ (onde $x$ são as variáveis de entrada e $s$ são variáveis de substituição/ancilares) tal que:
    1. $g(x, s) = 0$ para os termos mínimos (soluções válidas) do problema lógico original.
    2. $g(x, s) > 0$ para todas as outras combinações.
  • O ILP busca o menor número de variáveis de substituição ($s$) necessárias para satisfazer essas condições.

• Teoremas e Padrões Descobertos:

  • Teorema de Espreitamento de Raízes (Root Squeezing Theorem): Permite codificar restrições de intervalo (ex: $L \le \sum x_i \le H$) usando uma forma de produto de duas equações lineares, reduzindo o número de variáveis de substituição em comparação com a simples quadratura.
  • Codificação de Paridade (XOR): Desenvolvimento de uma representação binária "relaxada" para variáveis de substituição que cobrem apenas números ímpares, otimizando a contagem de bits para cláusulas XOR de múltiplas entradas.
  • Codificação de OR e AND: Uso de fórmulas de produto (para OR) e somas de quadrados ou produtos diretos (para AND) que evitam a introdução desnecessária de variáveis auxiliares.
  • Estratégia de "Marcadores Lógicos": Para circuitos complexos, o método identifica portas lógicas de múltiplas entradas (AND, OR, XOR) e aplica as fórmulas otimizadas descobertas, tratando sub-expressões como variáveis substituídas.

3. Contribuições Principais

1. Generalização de Formas Normais SAT: O trabalho estende as técnicas de codificação para cobrir não apenas CNF (Forma Normal Conjuntiva), mas também DNF (Disjuntiva), ANF (Normal Algébrica) e PES (Produto de Somas Exclusivas), que são cruciais para algoritmos criptográficos.
2. Redução de Variáveis: A metodologia demonstra uma redução de milhares de variáveis lógicas em comparação com trabalhos anteriores, mantendo a matriz QUBO esparsa e os coeficientes gerenciáveis.
3. Aplicação em Criptografia: A aplicação prática e bem-sucedida em algoritmos de ponta, incluindo:
   • AES-128/192/256: Codificação completa das rondas de substituição (S-boxes) e permutações.
   • Funções de Hash: MD5, SHA-1 e SHA-256.
4. Otimização de S-boxes: Uso de busca exaustiva via ILP para encontrar circuitos booleanos ótimos para inversão multiplicativa em campos finitos ($GF(2^8)$), essenciais para o AES.

4. Resultados

Os resultados experimentais mostram melhorias drásticas em relação aos estados da arte anteriores (como os trabalhos de Ref. [36] e [74]):

• AES-256: A codificação proposta utiliza apenas 12% do número de variáveis QUBO necessárias nos melhores métodos anteriores.
  • Comparação: O método anterior exigia ~250.000 variáveis; o novo método requer apenas 29.330 (para criptografia) e 31.242 (para descriptografia).
• AES-128/192: Reduções de 76% e 88% no número de variáveis, respectivamente.
• Funções de Hash:
  • SHA-256: Redução de 47.808 variáveis (método anterior) para 30.255 (com blocos de tamanho 6) ou 42.899 (com blocos de tamanho 1 para coeficientes menores).
  • MD5: Redução de 17.280 para 10.272 variáveis.
• Esparsidade e Coeficientes: As matrizes QUBO geradas possuem alta esparsidade (entre 0,04% e 0,52%), o que é ideal para o embedding em hardware de annealing quântico com conectividade limitada. A magnitude dos coeficientes foi controlada através de estratégias de blocos (block-wise) para a adição modular.

5. Significado e Impacto

• Vulnerabilidade Criptográfica: A redução drástica no tamanho das instâncias QUBO aumenta a vulnerabilidade teórica dos algoritmos de criptografia contra futuros annealers quânticos. O artigo sugere que máquinas quânticas capazes de lidar com ~30.000 variáveis lógicas (previstas para o futuro próximo) poderiam potencialmente quebrar o AES-256, algo que era considerado impossível com as codificações anteriores.
• Avanço em QUBO: O trabalho estabelece um novo padrão para a codificação eficiente de problemas lógicos complexos, fornecendo "blocos de construção" (CNF, DNF, ANF) otimizáveis via ILP.
• Limitações e Futuro: Embora os resultados sejam promissores, o tamanho atual ainda excede a capacidade dos annealers quânticos comerciais atuais. O trabalho destaca a necessidade de melhorar os solucionadores de ILP para lidar com funções booleanas maiores e de gerenciar o compromisso (trade-off) entre o número de variáveis e a magnitude dos coeficientes (precisão numérica) para hardware real.

Em suma, o artigo demonstra que a otimização inteligente da codificação lógica pode transformar problemas de criptografia "intratáveis" em problemas potencialmente solucionáveis por hardware quântico em desenvolvimento, redefinindo as expectativas sobre a segurança pós-quântica de algoritmos simétricos.