Imagine que você tivesse algum conhecimento útil – talvez uma receita secreta ou a chave de uma cifra. Você poderia provar a um amigo que tinha esse conhecimento, sem revelar nada sobre isso? Os cientistas da computação provaram há mais de 30 anos que isso seria possível, se você usasse o que é chamado de prova de conhecimento zero.
Para entender essa ideia de maneira simples, suponhamos que você queira mostrar ao seu amigo que sabe como passar por um labirinto, sem divulgar detalhes do caminho. Você poderia simplesmente atravessar o labirinto dentro de um limite de tempo, enquanto seu amigo estava proibido de assistir. (O limite de tempo é necessário porque, com tempo suficiente, qualquer um pode eventualmente encontrar a saída por tentativa e erro.) Seu amigo saberia que você poderia fazer isso, mas não saberia como.
As provas de conhecimento zero são úteis para criptógrafos, que trabalham com informações secretas, mas também para pesquisadores de complexidade computacional, que tratam de classificar a dificuldade de diferentes problemas. “Muita criptografia moderna depende de suposições de complexidade – na suposição de que certos problemas são difíceis de resolver, então sempre houve algumas conexões entre os dois mundos”, disse Claude Crepeau, cientista da computação da Universidade McGill. “Mas [essas] provas criaram todo um mundo de conexões.”
As provas de conhecimento zero pertencem a uma categoria conhecida como provas interativas, portanto, para aprender como as primeiras funcionam, é útil compreender as últimas. Primeiro descrito em um artigo de 1985 dos cientistas da computação Shafi Goldwasser, Silvio Micali e Charles Rackoff, as provas interativas funcionam como um interrogatório: por meio de uma série de mensagens, uma parte (o provador) tenta convencer a outra (o verificador) de que uma determinada afirmação é verdadeira. Uma prova interativa deve satisfazer duas propriedades. Primeiro, uma afirmação verdadeira acabará sempre por convencer um verificador honesto. Em segundo lugar, se a afirmação dada for falsa, nenhum provador – mesmo aquele que finge possuir certo conhecimento – pode convencer o verificador, exceto com uma probabilidade insignificantemente pequena.
As provas interativas são de natureza probabilística. O provador poderia responder corretamente a uma ou duas perguntas simplesmente por sorte, por isso é necessário um número suficientemente grande de desafios, todos os quais o provador deve acertar, para que o verificador fique confiante de que o provador sabe de facto que a afirmação é verdadeira.
Esta ideia de interações surgiu quando Micali e Goldwasser – então estudantes de pós-graduação na Universidade da Califórnia, Berkeley – ficaram intrigados com a logística de jogar pôquer em rede. Como todos os jogadores podem verificar que quando um deles recebe uma carta do baralho virtual, o resultado é aleatório? Provas interativas podem abrir o caminho. Mas então, como os jogadores podem verificar se todo o protocolo – o conjunto completo de regras – foi seguido corretamente, sem revelar a mão de cada jogador ao longo do caminho?
Para atingir este objetivo, Micali e Goldwasser acrescentaram uma terceira propriedade às duas necessárias para uma prova interativa: a prova não deve revelar nada sobre o conhecimento em si, apenas a veracidade da afirmação. “Existe a noção de seguir um protocolo, no final do qual você acredita que [os jogadores de pôquer] não sabem nada além do que deveriam saber”, disse Goldwasser.
Vamos considerar o exemplo clássico. Alice quer provar a Bob que um determinado gráfico G — uma coleção única de vértices (pontos) conectados por arestas (linhas) — tem um “ciclo hamiltoniano”. Isso significa que o gráfico tem um caminho que visita cada ponto exatamente uma vez e termina no mesmo ponto de onde começou. Alice poderia fazer isso simplesmente mostrando a Bob o caminho que faz isso, mas é claro que ele também saberia o caminho.
Veja como Alice pode convencer Bob de que ela sabe que tal caminho existe, sem mostrá-lo a ele. Primeiro ela desenha um novo gráfico, H, isso não parece G mas é semelhante de uma forma crucial: tem o mesmo número de vértices, conectados da mesma maneira. (Se G realmente tem um ciclo hamiltoniano, essa semelhança significa H também.) Então, depois de cobrir todas as bordas H com fita adesiva, ela trava H em uma caixa e dá a caixa para Bob. Isso o impede de ver diretamente, mas também impede que ela o altere. Então Bob faz uma escolha: ou ele pode pedir a Alice que mostre isso H realmente é semelhante a G, ou ele pode pedir a ela que lhe mostre o ciclo hamiltoniano em H. Ambas as solicitações devem ser fáceis para Alice, assumindo que H realmente é semelhante o suficiente para G, e que ela realmente conhece o caminho.
Claro, mesmo que Alice não conheça o ciclo hamiltoniano em G, ela pode tentar enganar Bob, desenhando gráficos que não sejam semelhantes aos G, ou enviando gráficos para os quais ela não conhece o caminho. Mas depois de jogarem várias rodadas, a chance de Alice enganar Bob todas as vezes torna-se extremamente pequena. Se ela acertar tudo, eventualmente Bob ficará convencido de que Alice conhece um ciclo hamiltoniano no gráfico G, sem que Bob nunca tenha visto.
Após o artigo inicial que descreveu pela primeira vez tais provas, Micali e dois matemáticos – Oded Goldreich e Avi Wigderson – descobriram uma consequência inesperada com efeitos de longo alcance. Tem a ver com uma categoria principal de problemas de dificuldade aproximadamente igual, conhecida como NP. Esses problemas são difíceis de resolver, mas suas soluções são fáceis de verificar. Os três pesquisadores descobriram que, se a criptografia for verdadeiramente segura é possível, então a solução para todos os problemas em NP também pode ser provada com uma prova de conhecimento zero. Este estudo ajudou pesquisadores conceber de variantes de provas de conhecimento zero que nem sequer exigem criptografia segura; estas são conhecidas como provas interativas com vários provadores.
E em 1988, Micali e outros mostrou que se um provador e um verificador compartilham uma pequena sequência de bits aleatórios, nenhuma interação é necessária. Teoricamente, isso significava que as provas de conhecimento zero não precisam ser interativas, o que implicaria que a comunicação constante entre duas partes não é necessária. Isto os tornaria muito mais úteis para os pesquisadores, mas foi somente depois da virada do século 21 que tais provas decolaram.
“No final dos anos 2000, começamos a ver a evolução de técnicas eficientes para a construção de provas de conhecimento zero”, disse Mateus D. Verde, criptógrafo da Universidade John Hopkins. “Chegamos ao ponto em que percebemos: 'Espere um segundo, pode realmente haver uma maneira de usar isso na prática'”.
Agora, um provador poderia enviar uma única mensagem a um verificador sem que ambos precisassem estar online, e os pesquisadores poderiam criar uma prova muito curta que pudesse ser verificada rapidamente, mesmo para problemas muito complicados. Isto levou a vários usos práticos, como a capacidade de verificar rapidamente o blockchain após uma transação de criptomoeda, ocultando os detalhes da transação. E em 2016, um grupo de físicos mostrou como as provas de conhecimento zero podem ajudar no desarmamento nuclear: Sem revelar qualquer segredo sobre a concepção da sua ogiva nuclear, um país poderia agora provar aos inspectores nucleares se a ogiva está activa ou inactiva.
Mais recentemente, os avanços na computação quântica obrigaram Crépeau a testar a resistência de pesquisas anteriores para garantir que os protocolos de conhecimento zero ainda sejam viáveis. Em 2021, ele ajudou demonstrar que as provas interativas de vários provadores mantêm seu sigilo mesmo quando computadores quânticos estão envolvidos, mas atingir o mesmo nível de segurança torna o protocolo muito mais lento. A descoberta é uma boa notícia, disse ele, mas novas preocupações surgirão à medida que a tecnologia avança.
“Todo tipo de computação que possamos fazer no futuro envolverá computadores quânticos”, disse Crépeau. “Portanto, como bons criptógrafos paranóicos, sempre que avaliamos a segurança de um sistema, queremos ter certeza de que nosso sistema está seguro.”
Nota do editor: Shafi Goldwasser recebeu financiamento da Simons Foundation, que também financia este publicação editorial independente. As decisões de financiamento da Simons Foundation não têm influência em nossa cobertura.
