O que é criptografia probabilística?

A criptografia tem sido uma área vital no desenvolvimento da tecnologia blockchain, mas isso não seria possível sem o desenvolvimento de um conceito básico para ela: criptografia probabilística.

Quando falamos de criptografia probabilística, nos referimos a um algoritmo capaz de aplicar aleatoriedade a um mecanismo de criptografia. Dessa forma, o que o desenvolvedor dessa função criptográfica busca é algo muito simples: para cada entrada de dados, obtenha uma saída diferente para cada interação realizada. Assim, os algoritmos de criptografia probabilística buscam oferecer um nível de segurança superior ao obtido pelas técnicas determinísticas atuais.

Esta ideia serve para melhorar os sistemas de criptografia assimétrica que nós conhecemos. E a partir deste ponto, podemos entender sua importância: a criptografia probabilística é o alicerce fundamental para proteger a privacidade da nossa vida digital, não apenas em blockchain, mas também na Internet e em qualquer outro aspecto relacionado a este mundo agora e no futuro próximo.

O primeiro sistema de criptografia probabilística

A origem do primeiro sistema de cifra probabilística pode ser rastreada até o desenvolvimento de Ralph Merkle com seu trabalho Secure Communications over Insecure Channels. Este trabalho estava tão à frente de seu tempo que em sua apresentação inicial na Association for Computing Machinery (ACM) em 1975, foi descartado como uma impossibilidade.

Mas em 1978, um ano após o trabalho de Whitfield Diffie y Martin Hellmann e seu protocolo criptográfico Diffie-Hellman assimétrico, foi finalmente considerado como algo possível deixando uma coisa clara: o nascimento da criptografia probabilística e dos sistemas de chave pública não era apenas uma possibilidade, mas o futuro da criptografia.

Assim, as propostas de Ralph Merkle, Whitfield Diffie e Martin Hellman se tornaram as primeiras propostas criptográficas que utilizaram elementos de criptografia probabilística para sua operação. Seu sucesso reside no fato de que este novo esquema foi capaz de proteger qualquer canal de comunicação mesmo em um ambiente de comunicação inseguro.

Esse avanço foi o que levou à criação de um dos primeiros sistemas de criptografia assimétrica com os elementos probabilísticos mais utilizados no mundo: o algoritmo RSA. RSA ainda é usado hoje na Internet e em muitos sistemas digitais em todo o mundo. Claro, todo esse esquema também é usado no restante dos sistemas criptográficos assimétricos, como os conhecidos ECDSA, EdDSA, Schnorr, entre outros, o que deixa claro o grau de importância desse avanço.

Melhorando o sistema

Agora, o uso de algoritmos probabilísticos em RSA é realmente muito pequeno. Geralmente, é usado para uma função básica: os produtores de números pseudo-aleatórios ou PRNG (Pseudo-random number generator). Lembremos que os PRNGs se encarregam de nos ajudar a obter os números e a entropia que podemos considerar seguros e, portanto, são a base da segurança de nossos atuais algoritmos de criptografia assimétrica. Esses PRNGs são criados usando algoritmos probabilísticos e, portanto, algoritmos de criptografia assimétrica são considerados algoritmos de criptografia probabilística, embora não apliquem totalmente esse esquema.

Embora isso seja seguro o suficiente, mesmo para nossos padrões atuais, a segurança desses algoritmos pode ser estendida estendendo o uso de propriedades probabilísticas ao restante do algoritmo de criptografia. Ou seja, aplicar a aleatoriedade não apenas ao gerador de números, mas também a todo o sistema de criptografia, o que seria um grande avanço comparável ao próprio nascimento da criptografia assimétrica.

Este foi precisamente o trabalho que dois grandes criptógrafos deram vida, Shafi Goldwasser y Silvio Micali (criador de Algorand). Em 1982, Goldwasser e Micali introduziram o conhecido protocolo criptográfico Goldwasser-Micali. Seu maior avanço é que este é o primeiro sistema criptográfico totalmente probabilístico conhecido mundialmente.

O trabalho de Goldwasser e Micali cria um sistema assimétrico seguro baseado no problema de resíduo quadrático descrito por Carl Friedrich Gauss no ano de 1801. Este problema matemático é amplamente utilizado em criptografia, sendo o melhor exemplo de sua implementação o algoritmo PRNG BBS (gerador de números pseudoaleatórios BBS), criado em 1986 por Lenore Blum, Manuel Blum e Michael Shub.

Foi com base nesse sistema que Goldwasser e Micali criaram um algoritmo capaz de gerar uma função cascata probabilística em que cada valor gerado pela fatoração de números gerados aleatoriamente serve para alimentar um algoritmo de criptografia inteiramente probabilístico. Assim, um texto pode ser tomado e criptografado sequencialmente, desta forma cada sequência dá um resultado totalmente diferente, você nunca verá o mesmo arquivo com criptografia idêntica, não importa quantas iterações de criptografia você execute. Você pode ler uma explicação matemática estendida do sistema neste link.

Segurança do sistema de criptografia probabilística

Agora, por que chegar a esse nível? A resposta para isso é simples: melhorar nossa segurança. O sistema de cifra probabilística introduzido por Goldwasser e Micali é talvez um dos maiores quebra-cabeças de criptoanálise que podem ser criados.

Por exemplo, um texto de 500 caracteres teria mais de 10^100000 combinações de criptografia diferentes, que supõe um nível de resultado computacionalmente não analisável no momento. Isso é ainda maior do que os recursos de criptografia que podem ser obtidos com algoritmos como AES, ECDSA e EdDSA combinados.

O problema com sistemas de criptografia probabilística é que sua criação usando máquinas determinísticas sempre cria uma lacuna ou espaço no qual não podemos verificar totalmente sua segurança. Simplificando, teoricamente eles são excelentes, mas formalmente no nível de implementação algorítmica não podemos garantir sua total segurança. Em essência, isso poderia ser resolvido com o próximo salto na era da computação: os computadores quânticos, pois por sua natureza são probabilísticos e poderíamos verificar totalmente a segurança desses sistemas criptográficos.

Além de criar algoritmos eficientes, uma vez que as implementações de criptografia probabilística existentes são computacionalmente ineficientes e não compensam sua segurança no que diz respeito ao poder computacional e desempenho que oferecem. Dito isto, ainda há muito a ser pesquisado nesta área até que possamos finalmente desenvolver algoritmos complexos que explorem todo o potencial desta nova melhoria em nossos sistemas de criptografia, mas por enquanto teremos que esperar um pouco mais e melhorar o bases probabilísticas que já protegem nossas implementações atuais.