A revolução quântica

Há, pois, uma vastíssima (para não dizer infinita) biblioteca de problemas que apenas os computadores conseguem resolver, em segundos, minutos ou horas. Mas e se existirem problemas que nem os computadores mais potentes, com toda a sua rapidez, conseguem destrinçar num tempo de escala humana, digamos, numa geração? É essa a premissa da criptografia atual, que está na base de todas as soluções de segurança na Internet, desde a assinatura digital, até às criptomoedas, sem esquecer serviços populares como os de “streaming” e todo o comércio feito de forma eletrónica.

A criptografia baseia-se na ideia de que há problemas matemáticos, bem identificados, que são inviáveis de serem resolvidos, em tempo útil, por um computador, ou mesmo por uma rede de milhões de computadores muito rápidos.

Isso não quer dizer que não exista muita gente determinada a tentar fazê-lo. Quer estejam no lado dos defensores, quer no dos atacantes, tentam encontrar problemas e soluções que consigam atalhar, ou prolongar, o tempo normal para efetuar uma tarefa. Estas soluções e problemas são categorizados pelo valor pelo qual aumentam, ou diminuem, uma determinada solução em relação à escala de tempo normal que levaria a ser encontrada.

## Tempo Constante

Se acrescentarmos recursos adicionais para resolver um problema, tais como mais memória, um processador mais rápido, mais espaço no disco rígido, ou mesmo mais computadores e se esta adição não resultar numa solução mais rápida, diremos que esta é uma solução de “tempo constante”. Por exemplo, se for necessária uma pessoa por dia para concretizar determinadas cem tarefas e se adicionarmos uma pessoa e ambas ainda só efetuarem cem tarefas por dia, em conjunto, o recurso adicional resultou numa solução de tempo constante. Se estiver a tentar resolver um problema mais rapidamente, as soluções a tempo constante não ajudam e são contraproducentes. Se está a tentar defender-se contra um atacante, e se tudo o que ele tem são ataques a tempo constante, é um benefício.

Se acrescentar recursos acelera a solução, é bom para o atacante e menos bom para o defensor. Se a adição de recursos resultar no mesmo número de tarefas a serem realizadas por cada indivíduo adicionado, dá-se o nome de “tempo linear” (ou “tempo direto”). Por exemplo, uma pessoa efetua dez tarefas, duas pessoas efetuam 20 tarefas, e três pessoas efetuam 30 tarefas (cada pessoa está a fazer apenas dez tarefas, mas juntas fazem mais tarefas).

Se a adição de cada recurso adicional acrescentar o dobro da velocidade de cada coleção de recursos anterior, a isso chama-se “tempo exponencial”. Por exemplo, uma pessoa efetua cem tarefas por dia, duas pessoas efetuam 200 tarefas, três pessoas efetuam 400 tarefas, e quatro pessoas efetuam 800 tarefas, e assim por diante. É assim que os computadores binários (ou seja, baseados em potências de dois) funcionam intrinsecamente. Cada bit adicionado duplica a capacidade de cálculo atribuída ao(s) bit(s) anterior(es). Qualquer adição de recursos, seja um recurso computacional ou um algoritmo que possa completar soluções mais rapidamente do que o tempo exponencial, é considerada uma ameaça a problemas que são defendidos utilizando tempo exponencial (ou abaixo de tempo exponencial).

Os matemáticos e os criptógrafos criaram problemas e soluções que requerem muito mais esforço de trabalho do que o tempo exponencial. Soluções de escala de tempo conhecidas como, por exemplo, fatorial são enormes melhorias no tempo exponencial e são conhecidas como de tempo “superexponencial”.

Qualquer recurso que forneça estes tipos de melhorias em soluções de tempo é uma ameaça para as “coisas” protegidas confiando em defesas de tempo exponencial. Isto é válido, em particular, para ataques criptográficos mais eficazes que o tempo exponencial e que são um desafio às soluções criptográficas que confiam na proteção do tempo exponencial.

## Problemas e Soluções Superexonenciais

A emergência dos computadores quânticos dá origem a problemas e soluções superexponenciais. Em geral, problemas criptográficos ou soluções que funcionem apenas em tempo exponencial ou menos, são hoje considerados de reduzida relevância. Mas problemas e soluções numa das escalas de tempo superexponencial, especialmente num dos métodos mais rápidos, como o fatorial, despertam muito interesse na comunidade da criptografia. Significam que cada recurso adicional acrescenta um benefício tremendo sobre os problemas e soluções de escala “normal” problemas exponenciais de escala temporal e soluções.

Algoritmos quânticos são uma série de passos matemáticos que se baseiam em teorias e propriedades quânticas que, se seguidos num dispositivo quântico, darão um determinado resultado. Durante décadas, muito do que os computadores quânticos poderiam eventualmente fazer era descrito apenas em artigos teóricos. Ter computadores e dispositivos quânticos funcionais transportou o mundo da mecânica quântica da teoria para o mundo real.

Com um computador quântico, os cientistas podem pegar num problema que é tratado por um determinado algoritmo quântico, aplicar o algoritmo, e observar os resultados. A maioria dos algoritmos quânticos é considerada revolucionária no que se refere aos aumentos de velocidade face aos computadores tradicionais ou face aos tipos de problemas anteriormente considerados insolúveis e que agora podem ser endereçados.

Em última análise, grande parte da criptografia atual pode ser quebrada por uma combinação de algoritmos e computadores quânticos capazes de os executar. E este é um facto tão inexorável que todos os que dependem da criptografia para as suas atividades quotidianas, ou seja todos nós, devem estar, quanto mais cedo melhor, cientes de que acontecerá, para se preparem com tempo e cuidado para talvez a mais radical das transformações nas tecnologias informáticas desde o aparecimento da Internet.