Algoritmos pós-quânticos: baseado em látex

No início existia a "Bomba", a máquina de calcular projetada por Alan Turing capaz de decifrar as mensagens do enigma. Na época, o enigma era o sistema criptográfico mais seguro usado pelas forças nazistas para comunicações militares e proporcionava uma vantagem significativa para suas operações. O Enigma é baseado em um problema matemático de tal complexidade que não pode ser resolvido por um único indivíduo ou por um grupo de estudiosos.

Por esta razão, Turing, analisando o modelo matemático que está na base do enigma, projetou uma máquina que implementou um algoritmo para resolver este problema, com o auxílio da eletrônica que permitiu reduzir os tempos de execução do 'algoritmo. Graças a esta máquina, os criptógrafos aliados aumentaram sua capacidade computacional e isso lhes permitiu explorar todo o espaço de busca de soluções até encontrar a resposta correta. Esta invenção foi uma das causas que permitiu aos Aliados ganhar a guerra contra a Alemanha nazista.

Algoritmos pós-quânticos: o século 21

Temos um algoritmo de criptografia baseado em um problema matemático que não pode ser resolvido com as ferramentas atuais em um período de tempo operacionalmente baixo . O algoritmo atual que garante a segurança de nossas comunicações é o RSA (Rivest, Shamir Adleman) , um sistema de criptografia assimétrica baseado no uso de números primos. Em suma, Alice e bob escolhem dois números primos diferentes, esses números representam sua chave privada. A chave pública do sistema nada mais é do que o produto desses dois números.

O poder deste algoritmo reside no fato de que a fatoração do número primo (ou seja, encontrar as chaves privadas) de um número é atualmente um problema que não pode ser resolvido em tempo polinomial (ou seja, o resultado chega, mas não é certo que ainda iremos estar vivo para admirá-lo.).

Então no momento não existe uma "bomba" capaz de quebrar esse sistema?

Hum, realmente não. Como podemos ler em vários artigos , a IBM conseguiu criar o primeiro computador quântico , que é um computador com alto desempenho computacional e que colocaria os atuais sistemas de criptografia de joelhos. Por isso, os desafios matemáticos atuais no campo criptográfico convergem para a criação de problemas ainda mais complexos , ou seja, com maior complexidade computacional do que os modernos computadores quânticos.

Existem diferentes tipos de algoritmos pós-quânticos que estão sendo estudados para entender se eles resistem ou não a um ataque de força bruta por um computador quântico e eles são explicados perfeitamente neste artigo . Em vez disso, analisaremos a criptografia baseada em rede que usa construções algébricas bidimensionais conhecidas como "redes" , resistentes a esquemas de computação quântica.

Uma rede é uma grade infinita de pontos. O problema computacional no qual a tecnologia baseada em rede se baseia é o “Problema do Vetor Mais Curto” , que requer a identificação da origem do ponto na grade que está mais próximo de um ponto central fixo no espaço. Em SVP tentamos encontrar, a partir de uma rede geométrica, um vetor diferente de zero de norma mínima pertencente à rede; uma aproximação dele, muito útil em criptografia, é o SVP γ, ou seja, encontrar o menor vetor diferente de zero dentro de uma aproximação γ. Os dois problemas são considerados computacionalmente muito difíceis.

Quais são os benefícios do SVP?

Como já mencionado, é um problema computacionalmente difícil, os melhores algoritmos pós quânticos para resolvê-lo possuem complexidade de ordem exponencial em relação ao tamanho da rede. Os cálculos são realizados com facilidade, com baixo custo computacional. Isso possibilitaria realizar operações de criptografia mesmo em aparelhos com pouco poder de computação e, consequentemente, mais baratos.

Além disso, deve-se lembrar que atualmente não existem grandes alternativas ao RSA. Essas alternativas serão realmente necessárias no caso da descoberta de um algoritmo de fatoração de tempo polinomial. Um algoritmo de fatoração capaz de operar em tempo polinomial já é conhecido por computadores quânticos; no entanto, atualmente não há ataques quânticos conhecidos no SVP.

Finalmente, uma propriedade muito interessante é que a dificuldade de qualquer instância do problema é a mesma do pior caso . Se pudéssemos resolver uma instância desse problema, seríamos capazes de resolver todas as instâncias, mas igualmente todas as instâncias têm a mesma complexidade de pior caso.

Artigo por Jacopo Iezzi

O artigo Algoritmos pós-quânticos: baseado em látex vem de Tech CuE | Engenharia de close-up .